From what I've read, conditionals (like the cond statement in lisp) do not need to be primitive if normal order evaluation is used.

Using lambda calculus and normal order evaluation, how can you emulate if and cond statements?

(cond (<p1> <e1>)
      (<p2> <e2>)
      (<pn> <en>))

(if <predicate> <consequent> <alternative>)

References to SICP are welcome, though a simpler example would be helpful.

(Definitions of cond and if taken from Section 1.1.6 of SICP)

  • 3
    $\begingroup$ Church encoded booleans would be the thing to look at here. Note that cond is easy to emulate using nested ifs. $\endgroup$ Dec 16 '15 at 17:19

Here is the church notation:

TRUE: $\lambda ab.a$

FALSE: $\lambda ab.b$

IF: $\lambda pxy.pxy$

By passing a church boolean as a predicate to the IF function, we choose one of two alternatives. TRUE chooses the first argument passed to it, and FALSE chooses the second.

We can derive COND by folding IF across a list of (condition, result) pairs

You can find wikipedia's explanation here, as well as assorted lambda calculus derivations here.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.