How to Evaluate Lambda Expressions

This is a bit of beginners questions, but I feel like I'm missing something when it comes to evaluating lambda expressions. I've been reading chapter 5 of this book about lambda calculus.

I understand how to evaluate expressions/statements in procedural languages. For example given a statement and parse tree such as:

a=b*(5+C)

    stmt
   /  | \
  a   =  expr
        /  | \
       b   *  expr
             /  | \
            5   +  c

This statement is evaluated by simply doing a depth first walk of the tree. But for lambda expression it doesn't seem to be such a simple procedure. Given the following grammar for a lambda expression:

expr := var 
       | const 
       | ( expr expr ) 
       | ( Î» var . expr )

How do you evaluate the following expression and parse tree?

(Î».x(Î».y(add(x y))5)3)

        expr
     / /    \  \
    /  |     |  \
   (  expr  expr )
    / |  \     \
   /  |   \     \
  Î». var  expr   cont
    /   / /  \ \    \
   /   /  |   | \    \
  x  (  expr expr )   3
    /  /  \     \      
   /  /    |     \      
  Î». var expr    const
    /   /  |  \     \
   /   /   |   \     \
  y   (expr expr )     5
        /   |  \
       /    |   \
   const   (expr expr}
    |        |    |
   add      var  var
             |    |
             x    y

Thanks in advance and please excuse the poor ascii art! If it's not intelligible, let me know.

Three approaches

You might find Chapter 2 of Implementing functional languages: a tutorial helpful. It describes how to do lazy graph reduction, which is one way to evaluate the tree you gave.

Note that there are a number of other ways to evaluate lambda expressions, including term rewriting (cf. The substitution model for procedure application):

   (Î».x(Î».y(add(x y))5)3)
=> (Î».y(add(3 y))5)
=> (add(3 5))
=> ...

Rewriting can be an expensive model in practice. It can be optimized by using the environment model of evaluation. Oleg explained this best:

Granted, doing substitutions is expensive [*], therefore, it makes sense to delay them and execute by need. Thus environment was invented as a list of pending substitutions. Now, when we pass an abstraction around, we also need to pass the list of substitutions that should be performed but weren't -- we need to enclose the environment. The environment is merely a _lazy_ substitution, an optimization technique.

[Edit: P.S. The procedural/imperative example given in the topic doesn't perform any binding of variables, which is why it appears simpler. If you consider the semantics of variable declaration and function definition, the imperative model is not so different, particularly if nested function definitions are allowed, as in Pascal. I.e. the issues here are not entirely unique to lambda expressions.]

By Anton van Straaten at Sun, 2007-03-04 16:45 | login or register to post comments

Type error

Perhaps your issue is with the example. (3 5) is a type error, because 5 is applied to 3, but 3 is not a function. Usually add would be a curried function and the syntax would be ((add 3) 5).

By Sjoerd Visscher at Sun, 2007-03-04 18:58 | login or register to post comments

Superfluous parenthesis

You don't really need the inside parenthesis. I guess the original topic had that mistake because the author is more familiar with function calls add(x, y)

Sorry I am rambling. What I mean is:

(add 3 5)

By Denis Bredelet -jido at Mon, 2007-03-12 23:05 | login or register to post comments

Lambda the Ultimate

User login

Navigation