Menu
This is the lambda calculus representation for the AND operator:
lambda(m).lambda(n).lambda (a).lambda (b). m(n a b) b
Can anyone help me in understanding this representation?
294
Evaluation is done by repeatedly finding a reducible expression (called a redex) and reducing it by a function evaluation until there are no more redexes. Example 1: The lambda expression (λx. x)y in its entirety is a redex that reduces to y.
Lisp was not based on lambda calculus, but rather Kleene's work on recursive functions. At the time, McCarthy had heard of lambda calculus but had not yet studied it! Lisp's M-language was first-order, that is, functions could not be passed around.
Semantics of Lambda Expressions Evaluating a lambda expression is called reduction . The basic reduction rule involves substituting expressions for free variables in a manner similar to the way that the parameters in a function definition are passed as arguments in a function call.
The abstraction form lets us define functions. In lambda calculus, an abstraction (a function) takes one parameter — the x in ( λ x . M ) and has a body — the M . M is any possible expression in lambda calculus.
To understand how to represent Booleans in lambda calculus, it helps to think about an IF expression, "if a then b else c". This is an expression which chooses the first branch, b, if it is true, and the second, c, if it is false. Lambda expressions can do that very easily:
lambda(x).lambda(y).x
will give you the first of its arguments, and
lambda(x).lambda(y).y
gives you the second. So if a is one of those expressions, then
a b c
gives either b or c, which is just what we want the IF to do. So define
true = lambda(x).lambda(y).x
false = lambda(x).lambda(y).y
and a b c will behave like if a then b else c.
Looking inside your expression at (n a b), that means if n then a else b.
Then m (n a b) b means
if m then (if n then a else b) else b
This expression evaluates to a if both m and n are true, and to b otherwise. Since a is the first argument of your function and b is the second, and true has been defined as a function that gives the first of its two arguments, then if m and n are both true, so is the whole expression. Otherwise it is false. And that's just the definition of and!
All this was invented by Alonzo Church, who invented the lambda calculus.
130
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
