C211 Ultra Brain Strain 1: Operation Lambda! 23 October 2003

Summary

You've learned about lambda, you've learned about how scheme evaluates expressions--Now it's time to apply that knowledge and figure out this brain-strain!

Note: This exercise is not required, but it will be a good challenge and help you learn more intracasies.

Recall that (lambda (a) a) is a pretty simple function. All it does is evaluate a and return the result. You could just as easily written ((lambda (a) a) x) as x. So why the blatently simple expression? Well, it defers evaluation. For example, you can define a procedure in the global environment and then use it sometime later--in the meantime, you can pass it around like a individually-packaged tool.

Also recall what quote does! All of these are the same expression:

• (quote (quote x))
• '(quote x)
• ''x

Also remember that when you create identifiers or literals (such as variables like ls or x or tree?) you can use pretty much anything you want! That's right, I could write some procedures named car and cdr if I wanted and my new procedures would shadow the built-in car and cdr so I could not use them anymore! If I really wanted to screw with someone's head, I could even switch those two! Try it. Copy and paste this code into scheme, then test out the operators + and *.

(define x +)
(define + *)
(define * x)

(= (+ 1 2) 3)
(= (* 1 2) 2)

Rewriting Lambdas

Remember what our stupid useless lambda expression looked like before?

(define not-so-evil
  (lambda (a) a))

(define not-so-evil
  (lambda (lambda) lambda))

Variable *airity λ

Now you have to learn something new (that's why this isn't required for lab): If you define a procedure using (lambda x x) instead of (lambda (x) x) IT IS NOT THE SAME THING! If you think about the english words, the second expression is: "create a procedure that takes a list of parameters that looks like (x) and that's it." The first expression is: "Create a procedure that takes a list of parameters and we'll call it x." Notice the subtle difference? In one case, the formals list is actually a list, in the other it is an identifier. What does this mean? Well, you get some flexibility.

Try these out:

> (define not-evil
    (lambda (x) x))

> (define kinda-evil
    (lambda x x))

> (not-evil 3)
3

> (kinda-evil 3)
(3)

> (kinda-evil 1 2 3 4 5 6 7 8 9 10)
(1 2 3 4 5 6 7 8 9 10)

> (kinda-evil)
()

This is EVIL!

Okay, now you have to show me the reduction of this nice little code snippit using only the following transformations:

1. (lambda (x) x) = (lambda (y) y) for any identifiers x and y. In the body of the second lambda expression, you MUST replace all occurences of x with y.
2. 'k = (quote k)
3. ((lambda (a) a) b) = b This is just a procedure application.

Your Mission

Should you chose to accept it is: step-by-step, reduce the following expression into a very short expression that can't be reduced any more. Each step must be a step from the list above, you can't do anything else. For each change you make, explain why you did it and which step you're using. Also, each time you apply one of those transformations you MUST test the expression so you know (and can prove) that it is functionally the same!

It should take you about eight steps. Here it is:

(define evil
  ((lambda (lambda)
     ((lambda lambda) lambda))
   ((lambda 'lambda 'lambda)
    (lambda (lambda)
      (lambda lambda))
    (lambda (lambda)
      lambda))))

> (evil 'x)
x

> (evil 'x 'y)
Error: incorrect number of arguments to #<procedure>.
Type (debug) to enter the debugger.

> (evil)
Error: incorrect number of arguments to #<procedure>.
Type (debug) to enter the debugger.

> (evil +)
#<procedure +>