Lambda calculus; lazy evaluation and normal evaluation

Question

I'm relatively new to functional programming and while learning about it, I bumped into lambda calculus. The thing is that I found some questions but I don't really have the notions to answer them, and I was unable to find them so I am asking for help. I have the following lambda expression:

( \x.x ( \x.x \x.x ))

And I am asked to do a lazy evaluation on it. Of course, I do not really know what lazy evaluation is. My idea for evaluating this would be:

1. ( \x.x ( \x.x ))
2. ( \x.x ) ?

Which I am sure would be wrong since no result is given. Can anyone please point me in the right direction? I just to be sure when asked to do a normal evaluation or a lazy evaluation, what I must do.

Thank you for your time!

Answer 1

For lazy application (CallByName, CBN) a lambda is like a struct or list by containment of the parameters. Only when members are accessed, e.g. via pattern matching, it is evaluated to that point. Application goes outside-in step-by-step, which is the same as right-associative.

For CallByValue (CBV) the evaluation goes inside-out, if all parameters are available inside. For recursive definitions this leads to infinite loops.

In your case, by name:

    (\x.x ( \x.x \x.x ))
    \x.x ( \x.x \x.x )
    ( \x.x \x.x )
    \x.x \x.x
    \x.x

By value:

    (\x.x ( \x.x \x.x ))
    \x.x ( \x.x \x.x )
    \x.x ( \x.x )
    ( \x.x )
    \x.x