Use of Parentheses in Lambda Calculus – Calculus Guide

calculuslambda-calculus

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…

Best Answer

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