M15: Lambda

Change DrRacket’s language level to “Intermediate Student with Lambda”.

When we do the evaluation in the substitution model, the function is given a name. But it is not a name that appears in the program and the programmer cannot predict it. So perhaps it is more accurate to say it has a secret name, which is also true of someone who is anonymous.

eat-apples, along with keep-odds, are the functions we used to motivate filter at the beginning of M14. The purpose of eat-apples is to consume a list of symbols, keeping only those that are not the symbol 'apple.

We did a variation of this code in the video m15.30_db_example with make-between:

(define (make-between n m)
  (local [(define (f x) (and (<= n x) (<= x m)))] f))

(filter (make-between 2 4) (list 0 1 2 3 4 5 6)) ⇒ (list 2 3 4)

It’s just that we “hid” the local in the function make-between.

The comment about needing to provide a name still applies: we had to come up with the name f in make-between.

When a function produced in a local is only used once, there’s a lot of code that isn’t actually needed. lambda gets rid of it.

All we really need is a list of the parameter names and the expression using them. Add lambda and we’ve got it.

DrRacket will also accept the Greek letter λ in place of lambda. Look in the “Insert” menu for a keyboard shortcut. Also notice the stylized λ in DrRacket’s icon:

Here are some other examples of using lambda with filter:

(define lst (list 3 5 9 5 5 4))
(filter (lambda (x) (= 5 x)) lst)                   ⇒ (list 5 5 5)
(filter (lambda (x) (and (<= 3 x) (<= x 5))) lst)   ⇒ (list 3 5 5 5 4)
(filter (lambda (s) (char>? s #\Z)) (list #\B #\a #\y)) ⇒ (list #\a #\y)

Note the double open parentheses at the beginning of the rule.

We saw double open parentheses several times in M14. The inner pair is used to “compute” the function to use for the outer pair.

In the past “compute” has meant lookup in a table (lookup-al from the arithmetic expression example) or using a function and local to make it (e.g. make-adder) or sometimes to use local directly.

Now, “compute” can also mean “use this function” (the lambda expression).

In the trace, the first substitution step applies the user-defined function substitution rule from M02 to substitute (list 'pear 'apple) into the body of eat-apples.

The second substitution step applies the same rule, this time substituting the lambda expression every place the parameter pred? occurs in my-filter’s body expression. (list 'pear 'apple) is substituted into my-filter as well.

The result is the rewritten body of my-filter. It has the curious double open parentheses in the second clause of the cond.

==>* indicates places where multiple steps are taken.

The version of make-adder on the left includes a local with a function name that is only used once – the pattern that can be replaced with lambda. That’s what appears on the right.

Note that the traces are different but give the same answer.

Here’s the difference the last paragraph on the slide makes. Both code fragments produce the same result, but the second one involves an extra step because i-earned is bound to a value that needs to be substituted into the expression.

Let’s rewrite make-adder in several steps to arrive at the code shown in the slide. Start with our first definition of make-adder using local:

(define (make-adder x) (local [(define (f y) (+ x y))] f))

Replace the local with the equivalent lambda expression:

(define (make-adder x) (lambda (y) (+ x y)))

This version uses our traditional notation for a function definition, (define (make-adder x) ...). We can also use lambda one more time to make a function that is bound to the identifer make-adder:

(define make-adder (lambda (x) (lambda (y) (+ x y))))

Finally, indent to match the slide.

Tracing lambda expressions can be tricky, mostly due to the deeply nested parentheses. One aid is to look for the pattern ((lambda ...) ...).
The inner set of parentheses is defining a function. The outer set of parentheses is applying that function to the arguments represented by the last ....

Watch for this pattern twice while stepping through ((make-adder 3) 4):

Another confusing situation is having more than two open parentheses before a lambda. Apply the ((lambda ...) ...) first. It is not yet completely evaluated but must be before the outer set(s) of parentheses can be dealt with.

In the following stepper, the two lambda expressions are almost the same, but not quite. They result in the same answer, but get there in two different ways. Note that both of them apply the left-most instance of ((lambda ...) ...).

Racket allows parentheses () and square brackets [] to be used interchangeably, so long as they are nested in pairs. ([])[] is allowed but ([)] is not.

So far we’ve used square brackets only for conditional and local expressions. You may find them helpful when parentheses become deeply nested, as well.