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 M15. 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.

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)

;; my-filter:  (X -> Bool) (listof X) -> (listof X)
(define (my-filter pred? lst)
  (cond [(empty? lst) empty]
        [(pred? (first lst))
         (cons (first lst) (my-filter pred? (rest lst)))]
        [else (my-filter pred? (rest lst))]))

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 my-filter.

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.

We saw double open parentheses several times in M15. 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.

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:

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

In the following stepper example, foo is defined as a constant. The value of foo is a function, which is fine since in M15 we learned that functions are first-class values. Like any constant, its value needs to be substituted into the expression.

Once that is done, the lambda substitution rule is applied.

To make the transformation in the slide more carefully, shorten the names so everything can fit on a single line. Then the original function is

(define i-rate 0.03)
(define (i-earn amount) (* i-rate amount))

Use a local expression to create an anonymous function (like we did in M15) and bind it to the name i-earn:

(define i-earn (local [(define (f amount) (* i-rate amount))] f))

But the local can be replaced with the lambda expression (lambda (amount) (* i-rate amount)):

(define i-earn (lambda (amount) (* i-rate amount)))

To recap, rewriting a “regular” function to use lambda involves two changes. First, pull the function name to be the define’s identifier. Second, insert lambda with a pair of parentheses.

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.

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.