1

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!

Vaduva Mihaita Bogdan
  • 13
  • So a Google search for "lambda calculus lazy evaluation" gives https://en.wikipedia.org/wiki/Lazy_evaluation in the first two hits. The information about working with infinite data structures is immediately relevant to your particular lambda expression. If you are still seeking help, please clarify. (Also, why did a minus sign appear in your evaluation of the expression?) – Eric Towers Sep 08 '17 at 13:38
  • Thank you for your answer! First of all, sorry, I was just trying to show the steps of my evaluation. Now I have edited the question and it should ok. I would still need help to understand how to evaluate a lambda expression. I still don't know if my evaluation is correct. – Vaduva Mihaita Bogdan Sep 08 '17 at 13:44
  • FYI, maybe this question may also be suited for the Computer Science SE. – Karlo Sep 08 '17 at 13:45

1 Answers1

0

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
Roland Puntaier
  • 109