The lambda calculus is a system of functional programming. Lambda calculus consists of variables, abstractions, and applications.
A variable is simply a name denoting a function parameter. It is a single letter. An abstraction is a "function literal" of sorts, it consists of a backslash
\ followed by a variable name, and then an expression, which is the function body. For example, the function
\x.x is a function which takes an argument
x and returns
x, a.k.a. the identity function. Abstractions can also return other abstractions. For example,
\x.\y.x is a function which takes an argument
x and returns a new function that returns
There is also application. In application, you remove the header on the first value and substitute all instances of the function's argument with the value it is applied to. For example, to apply
\y.y, substitute all
(\y.y)(\y.y) (Parenthesis may need to be added for clarification.) Applications are denoted in an expression by writing the two values next to each other, where the first is the function to apply and the second is the argument to apply to. For example, you can write
xy to apply x to y. However, you may need parenthesis (for example in
The first lambda calculus notation is the one I just described.
The second lambda calculus notation does not need parenthesis. It matches the following grammar:
<expression> ::= <variable> || <abstraction> || <application> <abstraction> ::= "\" <variable> <expression> <application> ::= "`" <expression> <expression>
<variable> can be any uppercase or lowercase letter. This is an example of an expression in the second notation:
Your task is to write a program that takes a lambda calculus expression in the first notation and outputs it rewritten in the second notation.
- Every variable name is 1 letter.
- Abstractions in the first notation go as far as possible, and application goes left to right:
d(abc) -> `d``abc.
- You do not have to deal with free/bound variables and scoping.
\a.a -> \aa (\x.xx)(\x.xx) -> `\x`xx\x`xx \x.\y.\z.xz(yz) -> \x\y\z``xz`yz (\S.\K.SKK)(\x.\y.\z.xz(yz))(\p.\q.p) -> ``\S\K``SKK\x\y\z``xz`yz\p\qp