archives

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.