Lesson 2

Goal

After this lesson you should be able to pass a procedure as an argument, write a small anonymous procedure with lambda, return a procedure from another procedure, and use let for local names.

The larger idea is simple but important: in Scheme, procedures are values. A number can be named, passed to a procedure, returned from a procedure, or placed in a list. A procedure can also do those things. This is one reason Scheme is a small language with a large reach.

Procedures as Values

You have already used names for procedures:

(define (square-number n)
  (* n n))

The name square-number is bound to a procedure. You can call it:

If you evaluate a procedure name by itself, an implementation will usually print some implementation-specific representation of the procedure. Do not depend on that printed form. The portable fact is that the value is a procedure, and you can test that with procedure?.

This is different from quotation. The expression square-number asks for the value bound to that identifier. The expression 'square-number is a symbol.

Generalizing with an Ordinary Value

Before passing procedures, start with a more familiar kind of generalization. Several area formulas have the same shape: multiply a shape-specific factor by the square of one length.

(define pi-approx 3.141592654)

(define square-factor 1)
(define circle-factor pi-approx)
(define sphere-factor (* 4 pi-approx))
(define hexagon-factor (* (sqrt 3) 1.5))

(define (area shape-factor r)
  (* shape-factor r r))

The procedure area does not know whether the factor means a square, circle, sphere, or regular hexagon. The factor is data supplied by the caller.

This example names the factors with -factor suffixes. R7RS already provides a standard procedure named square, so using square-factor avoids a misleading collision.

Generalizing with a Procedure

Now look at a pattern where the part that changes is not a number but a computation.

(define (square-number n)
  (* n n))

(define (cube-number n)
  (* n n n))

The sum of squares from 1 through 5 is:

(+ (square-number 1)
   (square-number 2)
   (square-number 3)
   (square-number 4)
   (square-number 5))

The sum of cubes has the same structure, but the term procedure changes. We can make that changing procedure an argument.

(define (sum-from-to term a b)
  (if (> a b)
      0
      (+ (term a)
         (sum-from-to term (+ a 1) b))))

sum-from-to is a higher-order procedure because it takes a procedure as an argument. The parameter term is used in operator position: (term a) calls whichever procedure the caller supplied.

The recursion in this lesson is still simple numeric recursion. Later lessons will spend more time on how to design recursive procedures deliberately.

Anonymous Procedures with lambda

Sometimes a procedure is useful only at one call site. Naming it is allowed, but the name can add noise. lambda creates a procedure without requiring a top-level name.

(lambda (x)
  (* x x x))

A lambda form does not run its body when the procedure is created. The body runs when the resulting procedure is called.

You can also call an anonymous procedure directly:

The extra pair of parentheses is doing real work. The inner expression (lambda (x) (* x x)) produces a procedure. The outer expression calls that procedure with 9.

Filtering with a Predicate

A predicate is a procedure used as a question. By convention, predicate names often end in ?, such as number?, symbol?, null?, and even?.

Here is a small list filter written with the R7RS list procedures introduced in Lesson 1:

(define (filter-list pred items)
  (cond
    ((null? items) '())
    ((pred (car items))
     (cons (car items)
           (filter-list pred (cdr items))))
    (else
     (filter-list pred (cdr items)))))

This is another higher-order procedure. The parameter pred is expected to be a predicate. The recursive structure walks through the list. When the first item passes the predicate, cons keeps it; otherwise the item is skipped.

This lesson uses the name filter-list because R7RS-small does not provide a standard filter binding. Some Scheme implementations and libraries do, but a portable lesson should say where such procedures come from.

Returning Procedures

A procedure can also produce a procedure as its result.

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

make-adder returns a new procedure. That new procedure remembers the value of n from the call that created it.

This remembered surrounding context is called lexical scope. The essential point here is: the inner procedure can still use n after make-adder has returned.

Another common higher-order procedure is composition:

(define (compose f g)
  (lambda (x)
    (f (g x))))

compose returns a procedure that first applies g, then applies f to that result.

Read the last expression from the inside out: add one to 4, then square the result.

Returning a Small Result List

Lesson 1 introduced list as the standard constructor for proper lists. The next example uses it to return two related values together. More precise multiple-value returns are possible in Scheme, but a small proper list is enough for this local-naming example.

Local Names with let

Sometimes an expression has a useful intermediate value. The quadratic formula is a good example. This lesson uses it only to show local names; it is not yet a lesson about numerical robustness.

(define (quadratic-roots a b c)
  (let ((d (sqrt (- (* b b) (* 4 a c))))
        (minus-b (- b))
        (two-a (* 2 a)))
    (list (/ (+ minus-b d) two-a)
          (/ (- minus-b d) two-a))))

The bindings introduced by let are local to the body of the let. Here, d, minus-b, and two-a are names used only while constructing the list of roots.

This example assumes two real roots. A production version would check the inputs and decide what to do when the discriminant is negative.

let is not assignment. It does not permanently change a variable. It gives local names to values while the let body is evaluated.

There is one early caution: the bindings in a single let are not a sequence where later bindings see earlier ones. They are computed from the surrounding environment.

The result is 6, not 11, because y used the outer x. A later lesson will introduce let*, which is the sequential version.

How let Relates to lambda

The idea behind let can be expressed with lambda.

(let ((d 10))
  (+ d d))

means the same thing as:

((lambda (d)
   (+ d d))
 10)

In practice, let is often easier to read because the local name appears next to the expression that computes its value. Remember the relationship, though: let is local naming built from the same procedure-call idea you already know.

First Complete Example

The published example source for this lesson checks shape factors, summation, lambda, filtering, procedure-returning procedures, composition, and let.

(define (sum-from-to term a b)
  (if (> a b)
      0
      (+ (term a)
         (sum-from-to term (+ a 1) b))))

(define (filter-list pred items)
  (cond
    ((null? items) '())
    ((pred (car items))
     (cons (car items)
           (filter-list pred (cdr items))))
    (else
     (filter-list pred (cdr items)))))

The full source file has a highlighted view at /examples/r7rs/intro/lesson-02/ and a raw source link from that page.

When working from the source tree used to build this site, run the example suite with:

scripts/test_examples_chicken.sh

Exercises

These exercises are original and small. Use the browser examples above or copy the checked source file into your local Scheme implementation.

• Define double-number, then use sum-from-to to add the doubles of the numbers from 1 through 5.
• Use sum-from-to with a lambda to sum (+ (* x x) x) from 1 through 4.
• Use filter-list to keep only the odd numbers in '(1 2 3 4 5 6 7).
• Use filter-list with a lambda to keep only numbers greater than 10.
• Define make-multiplier, analogous to make-adder, and use it to create triple.
• Define twice, a procedure that takes a procedure f and returns a procedure that applies f two times.
• Use let to avoid repeating (+ width height) inside a rectangle-perimeter calculation.
• Explain why the let example with x returns 6 rather than 11.

What Comes Next

The next lesson is Lesson 3: recursion, iteration, and growth. It uses the list procedures and higher-order habits introduced so far to reason about one-pass work, nested work, tail calls, and repeated computation.

Before moving on, make sure you can explain these ideas without guessing:

• Why sum-from-to is higher-order.
• Why (lambda (x) (* x x)) creates a procedure rather than immediately multiplying anything.
• Why (term a) calls the procedure supplied as term.
• Why filter-list uses a predicate.
• Why (make-adder 10) returns a procedure.
• Why let bindings are local and not assignment statements.