Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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...

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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))$.

share|improve this answer
A good answer should also include the rules for λ... –  Eli Barzilay Jul 8 '11 at 21:16
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)) ? –  Lqueryvg Nov 19 at 12:04
@Lqueryvg: Thanks for catching the typo; fixed. –  Brian M. Scott Nov 19 at 16:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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