Lambda expressions and parentheses

[nykevin]

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.

[Laguana]

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.

[headprogrammingczar]

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.

[letterX]

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.