Lambda expressions and parentheses

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Prelates, Moderators General

Lambda expressions and parentheses

Postby nykevin » Fri Feb 17, 2012 6:55 am UTC

I'm taking a class in programming languages, and I'm having a little difficulty with lambda calculus. Our professor told us that the syntax for lambda expressions is as follows, where v is a variable.
e := v \;|\; \lambda v.e \;|\; (e\,e)

He also very explicitly told us that we were never to leave off parentheses, as this would change the meaning. We also did several examples in this notation; here's our formulation of Church numerals:
\begin{eqnarray} \lambda f.\lambda x.x & \equiv & 0 \\
\lambda f.\lambda x. (f\,x) & \equiv & 1 \\
\lambda f.\lambda x. (f\,(f\,x)) & \equiv & 2 \\
& \vdots &
\end{eqnarray}


On the other hand, Wikipedia's formulation of lambda calculus is a little different:
e := v \;|\; (\lambda v.e) \;|\; (e\,e)

Wikipedia also states that the outermost parentheses can be omitted "to keep the notation... uncluttered" and does a number of other minor abbreviations.

Both sources present their side as definitive and do not acknowledge alternative formulations; Wikipedia does state that dropping the outer parentheses is a "usual convention" and presumably not universal.

I guess what I'm asking is whether there is any one "definitive" notation here, and if not, which one is awesomer.

Incidentally, one of our assignments we're to build a Scheme parser, which appears to be closer to the Wikipedia notation; the professor did not mention this and I think it may cause considerable confusion once other people start looking at it.

Honestly, the first notation makes more sense to me since a beta-reduction won't have extra internal parentheses to deal with; maybe it's just because I was introduced to it first.
nykevin
 
Posts: 13
Joined: Wed Sep 29, 2010 5:45 pm UTC

Re: Lambda expressions and parentheses

Postby Laguana » Fri Feb 17, 2012 8:48 am UTC

The way I recall it being first presented, parentheses were separate. Really all they do is disambiguate a flattened parse tree. Once you have a parse tree, they add nothing to it.

This is purely anecdotal, but in my experience it is common to treat application as left-associative (that is, "a b c" = "(a b) c") and to omit parenthesis which don't change that, since it makes it easier to read.
Laguana
 
Posts: 49
Joined: Sat Jan 19, 2008 10:13 pm UTC

Re: Lambda expressions and parentheses

Postby headprogrammingczar » Fri Feb 17, 2012 5:36 pm UTC

The other convention is to have lambdas extend as far right as possible.
Code: Select all
f λx. g x y     <=>     f (λχ. g x y)
-- NOT --
f (λχ. g) x y


It's just order of operations, essentially. The fact that Wikipedia and your professor both made a big deal out of it is, from what I have seen, a very common problem when teaching lambda calculus.
It seems to me like lambda calculus gets taught as a form of string manipulation, and a huge deal is made out of what could trivially be described as lexical scope and precedence rules.
You'll likely encounter this again with α-reduction and β-reduction.
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you
User avatar
headprogrammingczar
 
Posts: 3015
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

Re: Lambda expressions and parentheses

Postby letterX » Fri Feb 17, 2012 6:19 pm UTC

headprogrammingczar wrote:It seems to me like lambda calculus gets taught as a form of string manipulation, and a huge deal is made out of what could trivially be described as lexical scope and precedence rules.
You'll likely encounter this again with α-reduction and β-reduction.


Yeah, lambda expressions should really be treated as syntax trees or terms, and not as strings. I have a suspicion that the continued insistence on thinking of them as rules for string manipulation is because strings take up much less board space than syntax trees.

Also, if you use De Bruijn indices for variables, then alpha reduction goes away and beta reduction is greatly simplified due to not having to worry about variable capture. But again, it's much more difficult for humans to read, so it doesn't get used when writing out lambda expressions.
letterX
 
Posts: 523
Joined: Fri Feb 22, 2008 4:00 am UTC
Location: Ithaca, NY


Return to Computer Science

Who is online

Users browsing this forum: No registered users and 2 guests

cron