The challenge is to write an interpreter for the untyped lambda calculus in as few characters as possible. We define the untyped lambda calculus as follows:
There are the following three kinds of expressions:
A lambda expression has the form
(λ x. e)where
xcould be any legal variable name and
eany legal expression. Here
xis called the parameter and
eis called the function body.
For simplicity's sake we add the further restriction that there must not be a variable with the same name as
xcurrently in scope. A variable starts to be in scope when its name appears between
.and stops to be in scope at the corresponding
- Function application has the form
aare legal expressions. Here
fis called the function and
ais called the argument.
- A variable has the form
xis a legal variable name.
A function is applied by replacing each occurrence of the parameter in the functions body with its argument. More formally an expression of the form
((λ x. e) a), where
x is a variable name and
a are expressions, evaluates (or reduces) to the expression
e' is the result of replacing each occurrence of
A normal form is an expression which can not be evaluated further.
Your mission, should you choose to accept it, is to write an interpreter which takes as its input an expression of the untyped lambda calculus containing no free variables and produces as its output the expression's normal form (or an expression alpha-congruent to it). If the expression has no normal form or it is not a valid expression, the behaviour is undefined.
The solution with the smallest number of characters wins.
A couple of notes:
- Input may either be read from stdin or from a filename given as a command line argument (you only need to implement one or the other - not both). Output goes to stdout.
- Alternatively you may define a function which takes the input as a string and returns the output as a string.
- If non-ASCII characters are problematic for you, you may use the backslash (
\) character instead of λ.
- We count the number of characters, not bytes, so even if your source file is encoded as unicode λ counts as one character.
- Legal variable names consist of one or more lower case letters, i.e. characters between a and z (no need to support alphanumeric names, upper case letters or non-latin letters - though doing so will not invalidate your solution, of course).
- As far as this challenge is concerned, no parentheses are optional. Each lambda expression and each function application will be surrounded by exactly one pair of parentheses. No variable name will be surrounded by parentheses.
- Syntactic sugar like writing
(λ x y. e)for
(λ x. (λ y. e))does not need to be supported.
- If a recursion depth of more than 100 is required to evaluate a function, the behaviour is undefined. That should be more than low enough to be implemented without optimization in all languages and still large enough to be able to execute most expressions.
- You may also assume that spacing will be as in the examples, i.e. no spaces at the beginning and end of the input or before a
.and exactly one space after a
.and between a function and its argument and after a
Sample Input and Output
((λ x. x) (λ y. (λ z. z)))
(λ y. (λ z. z))
(λ x. ((λ y. y) x))
(λ x. x)
((λ x. (λ y. x)) (λ a. a))
(λ y. (λ a. a))
(((λ x. (λ y. x)) (λ a. a)) (λ b. b))
(λ a. a)
((λ x. (λ y. y)) (λ a. a))
(λ y. y)
(((λ x. (λ y. y)) (λ a. a)) (λ b. b))
(λ b. b)
((λx. (x x)) (λx. (x x)))
Output: anything (This is an example of an expression that has no normal form)
(((λ x. (λ y. x)) (λ a. a)) ((λx. (x x)) (λx. (x x))))
(λ a. a)(This is an example of an expression which does not normalize if you evaluate the arguments before the function call, and sadly an example for which my attempted solution fails)
((λ a. (λ b. (a (a (a b))))) (λ c. (λ d. (c (c d)))))
`(λ a. (λ b. (a (a (a (a (a (a (a (a b))))))))))This computes 2^3 in Church numerals.