Saturday, September 13, 2008

Implementing conditionals using lambda calculus

Lambda calculus is a way of modelling programming constructs by using only function definition and function application.
This shows you how to model if-then-else using lambda calculus
>>> true = lambda x, y: x
>>> false = lambda x, y: y
>>> ifelse = lambda x, y, z: x(y,z)
>>> ifelse(false, 1, 2)
2
>>> ifelse(true, 1, 2)
1
>>>
Well that was simple enough...Now for some explanation..We'll look at it top-down.
The chracters in this play are ifelse function, true function and false function [All characters are functions :-)]. The ifelse function takes three arguments and let's it's condition argument chose between 2nd (then-expression) and 3rd (else-expression) arguments. The true function always chooses true's first argument and false always chooses false's 2nd argument.
Note: - There is one catch though. Since python uses applicative order evaluation, this if else doesn't work exactly like the built-in ifelse construct. The following code will cause an out-of-memory exception.
>>> def p(): p()
...
>>> ifelse(false, p(), 1)

No comments: