News for hackers. Stuff that matters.
Re:Lambda Calculus by loup-vaillant on Tuesday October 13, 2009 @05:52AM (#878746)
> Anything evaluating lambda expressions then has to deal with that or you'd have to expand the syntax of the calculus to contain a termination function which 'magically' decides that enough is enough.

This isn't so magic. I don't know all the details, but it has been proved that:

* If some expression can be reduced to normal form, this normal form is unique (modulo variable naming —alpha conversion).

* There is a systematic (mechanic) strategy which guarantee to reach normal form, if it exist at all : normal order reduction.

Normal order reduction reduces the outer-most redex in an expression (instead of the inner-most one when you do eager evaluation —call by name). This is why you don't need `if`.

A small example:

    true  = \t f. t
    false = \t f. f

    if = \b t f. b t f

    nt = something_that_doesn't_reduce_to_normal_form
    id = \x. x
Now, trying to reduce this expression (in normal order):

    if false nt id -- outer redex = if X X X
    false nt id    -- outer redex = false X X
    id             -- normal form = \x. x
Now, without using definitions (except for `nt`):

    (\b t f. b t f) (\t f. f) nt (\x. x)
    (\t f. f) nt (\x. x)
    (\x. x)
Finally, the outer-most thing may not be a redex. (but you can still reduce inner-redexes). This is the weak head normal form. For example:

    \x. ((\x. x) x) -- weak head normal form. Outer redex = (\x. x) X
    \x. x           -- plain normal form
You can decide whether weak head normal form is enough, or go to normal form.

There are no comments on this comment yet.