As a summer project I am trying to learn lambda calculus. I am not that good with math but I have learned myself several programming languages and somehow got the idea that learning lambda calculus would be somewhat like learning another programming language (you are welcome to correct me on that one).

I have used lambda expressions in languages like F# and C#. But I am learning lambda calculus with the book "Lambda calculus and combinators: An introduction".

In this book we are shown several examples of lambda expressions that look really familiar, but they continue the book with parenthesis omitted. The first excersise is to fill in parenthesis and lambda-symbols in lambda expressions that have been omitted.

My question is: What are the "rules" for use of parentheses in lambda expressions?

Example: $xyz(yx)$ becomes $(((xy)z)(yx))$.

I can't seem to figure out what determines where the parenthesis goes...


The convention is that expressions associate from the left: $uvxyz$, for instance, is the same as $(uv)xyz$, which is the same as $((uv)x)yz$, $(((uv)x)y)z$, and finally $((((uv)x)y)z)$. In your example let $u$ stand for $(yx)$; then $xyz(yx)$ is $xyzu$, $(xy)zu$, $((xy)z)u$, and finally $(((xy)z)u)$, or $(((xy)z)(yx))$.

  • 3
    $\begingroup$ A good answer should also include the rules for λ... $\endgroup$ – Eli Barzilay Jul 8 '11 at 21:16
  • $\begingroup$ Great answer, but I believe you've got the yx transposed in the final answer when you substitute for u right at the last step. Shouldn't it be (((xy)z)(yx)) instead of (((xy)z)(xy)) ? $\endgroup$ – Lqueryvg Nov 19 '14 at 12:04
  • $\begingroup$ @Lqueryvg: Thanks for catching the typo; fixed. $\endgroup$ – Brian M. Scott Nov 19 '14 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.