Help for 2.3.4

Remember in class, I said that we couldn't execute expressions with free vars? The vars either need to be bound in the expression, or bound at the global level. That's not strictly true since if you have an expression that has a free variable, but it never uses it, then it doesn't matter. Here's an example in Scheme:


(if (< 3 4) 1 foo)

If you execute this, you'll always get 1 and you'll never get an error even though foo is free. Your job is to do the same thing, but for an expression in the lambda calculus (where you don't have conditionals or special forms of any kind).

Here's a few hints:

Use the substitution model to execute your examples, not Scheme.
Remember that the variable is free in the expression you create, that doesn't mean its unbound at the global level. Nevertheless, whatever it happens to be bound to, the result of evaluating your expression should be the same.
Suppose I have a function that makes no use of its formal parameter. That is, its value is independent of any value that gets passed into it. Here's an example:
```
(lambda (x) (lambda (y) y))
```
This function takes a value, x, and returns a lambda expression which doesn't rely on it. This function has the same value independent of what it is applied to. Can you use this function (unchanged) as part of a lambda calculus expression that has a free variable, but whose value is independent of that variable?

If there are problems with this page, please send mail to <cs330ta@cs.byu.edu>
If you have a comment about the class, please send mail to <seamons@cs.byu.edu>

© 1994-2009, Phillip J. Windley and Bryan S. Morse. All rights reserved.
Reproduction of all or part of this work is permitted for educational or research use provided that this copyright notice is included in any copy.

Last updated at 9:18 pm on Friday, September 03, 2004.