Abstracting the loop itself
Look back at the list procedures of the last lesson. sum-list walks a list and combines elements with +. A procedure to multiply them would be identical except for *. One that keeps only the even elements has the same shape as one that keeps only the long strings, except for the test. Writing each from scratch is repetitive and error-prone.
In Scheme the varying part can simply be a parameter, because procedures are values. A procedure that takes another procedure as an argument, or returns one as its result, is called a higher-order procedure. With a few of them (map, filter and fold) almost every loop over a list becomes a one-line expression, and the intent of the code becomes visible: "the squares of the odd numbers", not "a loop with an accumulator and an if".
Procedures that return procedures lead to the second big idea of this lesson: the closure, a procedure bundled with the environment it was created in. Closures can remember values, and with assignment they can keep private state that changes over time, which is all you need to build objects.
Higher-order procedures, folds and closures
Definition— Higher-order procedure
A procedure that takes a procedure as an argument or returns one. map and for-each are built in; filter and the folds are in SRFI 1 and most implementations, and are easy to write yourself.
Definition— Fold
A procedure that combines the elements of a list into a single value with a two-argument procedure and a starting value. fold-left combines from the first element onwards, carrying an accumulator; fold-right combines from the last element backwards. Every reduce-like loop is a fold.
Definition— Closure
A procedure together with the environment in which it was created. When a lambda expression is evaluated, the resulting procedure keeps a reference to the current environment, so it can still use the variables visible there, even after the procedure that created it has returned.
(import (scheme base) (scheme write))
(define (filter keep? lst)
(cond ((null? lst) '())
((keep? (car lst)) (cons (car lst) (filter keep? (cdr lst))))
(else (filter keep? (cdr lst)))))
(define (fold-left combine acc lst)
(if (null? lst)
acc
(fold-left combine (combine acc (car lst)) (cdr lst))))
(define (fold-right combine init lst)
(if (null? lst)
init
(combine (car lst) (fold-right combine init (cdr lst)))))
(define numbers '(3 8 5 12 7 10))
(write (map (lambda (n) (* n n)) numbers)) (newline)
(write (map + '(1 2 3) '(10 20 30))) (newline)
(write (filter odd? numbers)) (newline)
(write (fold-left + 0 numbers)) (newline)
(write (fold-left max (car numbers) (cdr numbers))) (newline)
(write (fold-left (lambda (acc x) (cons x acc)) '() '(a b c))) (newline)
(write (fold-right cons '() '(a b c))) (newline)
(write (fold-left - 0 '(1 2 3)) ) (newline)
(write (fold-right - 0 '(1 2 3))) (newline)
(write (apply max numbers)) (newline)
(write (fold-left + 0 (map (lambda (n) (* n n)) (filter odd? numbers)))) (newline)
(for-each (lambda (name score) (display name) (display ": ") (write score) (newline))
'("Ama" "Ravi" "Sofia") '(91 78 85))(9 64 25 144 49 100)
(11 22 33)
(3 5 7)
45
12
(c b a)
(a b c)
-6
2
12
83
Ama: 91
Ravi: 78
Sofia: 85mapapplies a procedure to each element and collects the results. Given several lists, it walks them in step, passing one element from each.filterkeeps the elements for which the predicate is true.fold-leftis tail-recursive: it carries the accumulator forward.fold-rightis not, but it preserves order naturally: foldingconsfrom the right over a list with'()copies the list, while folding it from the left (with the arguments flipped) reverses it.- The two folds differ for operations that are not associative.
fold-left -computes ;fold-right -computes . applycalls a procedure with a list of arguments.(apply max numbers)is the idiomatic maximum of a list.- The penultimate line is a pipeline: the sum of the squares of the odd numbers, .
for-eachis likemapbut is called only for its side effects, and it guarantees to go through the elements in order.
Example— A class report in three expressions
Suppose each student's record is a list of a name followed by test scores. With average defined as (/ (fold-left + 0 xs) (length xs)):
(define class
'(("Ama" 91 84 88) ("Ravi" 62 70 58) ("Sofia" 77 81 90) ("Tariq" 45 52 49)))
(define averages
(map (lambda (row) (cons (car row) (average (cdr row)))) class))
;; => (("Ama" . 263/3) ("Ravi" . 190/3) ("Sofia" . 248/3) ("Tariq" . 146/3))
(map car (filter (lambda (entry) (>= (cdr entry) 60)) averages))
;; => ("Ama" "Ravi" "Sofia")
(fold-left (lambda (best entry) (if (> (cdr entry) (cdr best)) entry best))
(car averages) (cdr averages))
;; => ("Ama" . 263/3)Each step is one higher-order procedure with a small lambda saying what is special about this problem. map turns records into name-average pairs; filter keeps those at 60 or above, and map car extracts the names; a fold with "keep the better of the two" finds the top student. Notice what is absent: no index variables, no if for an empty accumulator, no off-by-one errors. Because the averages are exact rationals (263/3 is 87 and two thirds), comparisons are exact too; convert with inexact only when you print them for people.
(SRFI 1 also defines a fold, with the element as the first argument of the combining procedure. Argument conventions for folds vary between libraries and languages, which is one reason to know how to write your own.)
Procedures that make procedures
(import (scheme base) (scheme write))
(define (compose . fs)
(if (null? fs)
(lambda (x) x)
(lambda (x) ((car fs) ((apply compose (cdr fs)) x)))))
(define (curry f . early)
(lambda late (apply f (append early late))))
(define (twice f) (lambda (x) (f (f x))))
(define (make-adder n) (lambda (x) (+ x n)))
(define add5 (make-adder 5))
(define inc-then-double (compose (lambda (x) (* 2 x)) (make-adder 1)))
(write (list (add5 10) ((make-adder 100) 1))) (newline)
(write (inc-then-double 6)) (newline)
(write (((twice twice) add5) 0)) (newline)
(write (map (curry * 3) '(1 2 3))) (newline)
(write ((curry string-append "Dr. ") "Achebe")) (newline)
(define (insert x sorted less?)
(cond ((null? sorted) (list x))
((less? x (car sorted)) (cons x sorted))
(else (cons (car sorted) (insert x (cdr sorted) less?)))))
(define (sort-by less? lst)
(let loop ((lst lst) (sorted '()))
(if (null? lst)
sorted
(loop (cdr lst) (insert (car lst) sorted less?)))))
(define cities '(("Lagos" . 15.4) ("Lima" . 10.9) ("Seoul" . 9.6) ("Cairo" . 22.6)))
(write (sort-by < '(5 2 9 1 7))) (newline)
(write (sort-by string<? '("pear" "fig" "apple"))) (newline)
(write (map car (sort-by (lambda (a b) (> (cdr a) (cdr b))) cities))) (newline)(15 101)
14
20
(3 6 9)
"Dr. Achebe"
(1 2 5 7 9)
("apple" "fig" "pear")
("Cairo" "Lagos" "Lima" "Seoul")make-adderreturns a new procedure each time it is called, each remembering its ownn.add5is a closure over an environment wherenis 5.composebuilds a procedure that applies its arguments right to left, like mathematical :inc-then-doubleadds 1 to 6, then doubles, giving 14. With no arguments it returns the identity procedure.twicereturns a procedure that appliesftwo times.(twice twice)therefore applies its argument four times, so adding 5 four times to 0 gives 20. Puzzles like this are a good test of whether you think of procedures as values.curryfixes some leading arguments now and accepts the rest later.(curry * 3)is "multiply by 3".sort-byis an insertion sort parameterised by its comparison. The same procedure sorts numbers with<, strings withstring<?, and city records by a custom rule (here, by the number after the dot, largest first). R7RS-small has no sorting procedure, but most implementations provide one, often through SRFI 132'slist-sort, and they too take the comparison as an argument. Insertion sort takes time; real libraries use merge sort or similar algorithms.
Closures with state
So far closures have only remembered values. With set!, which changes the value of an existing variable, they can also update them. The variable lives in the environment captured by the closure, so nothing outside can see or touch it.
(import (scheme base) (scheme write))
(define (make-counter)
(let ((count 0))
(lambda ()
(set! count (+ count 1))
count)))
(define c1 (make-counter))
(define c2 (make-counter))
(c1) (c1) (c1)
(c2)
(write (list (c1) (c2))) (newline)
(define (make-stack)
(let ((items '()))
(lambda (message . args)
(case message
((push!) (set! items (cons (car args) items)) items)
((pop!) (if (null? items)
(error "stack is empty")
(let ((top (car items)))
(set! items (cdr items))
top)))
((peek) (car items))
((size) (length items))
(else (error "unknown message" message))))))
(define s (make-stack))
(s 'push! 'a)
(s 'push! 'b)
(s 'push! 'c)
(let* ((before (s 'size))
(popped (s 'pop!))
(top (s 'peek))
(after (s 'size)))
(write (list before popped top after))
(newline))
(define (memoize f)
(let ((cache '()))
(lambda (n)
(let ((hit (assv n cache)))
(if hit
(cdr hit)
(let ((value (f n)))
(set! cache (cons (cons n value) cache))
value))))))
(define slow-calls 0)
(define fib
(memoize
(lambda (n)
(set! slow-calls (+ slow-calls 1))
(if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))))
(write (fib 80)) (newline)
(write slow-calls) (newline)(4 2)
(3 c b 2)
23416728348467685
81Counters. Each call to make-counter evaluates the let, creating a new environment with its own count, and returns a closure over it. c1 and c2 therefore count independently: after three calls and one call, the next calls return 4 and 2.
Objects by message passing. make-stack returns a single procedure that dispatches on a message symbol. The list items is completely private: the only way to reach it is through the messages the procedure understands. This is an object, with encapsulated state and methods, built from nothing but lambda, let and set!. Sussman and Steele's discovery in 1975 that Hewitt's actors and closures were the same thing is essentially this observation.
Memoisation. memoize wraps any one-argument procedure with a private cache, a list of (argument . result) pairs. The memoised fib is still tree-recursive in its definition, but each value is computed once: 81 real computations for n from 0 to 80, instead of the roughly calls the naive version would make.
Note
Why let* around the stack calls? Because the order in which a procedure's arguments are evaluated is unspecified, and Chibi-Scheme happens to evaluate them right to left. Written as (list (s 'size) (s 'pop!) (s 'peek) (s 'size)), the program printed (2 c c 3) when run with Chibi: the last size ran first. let* makes the order explicit and portable. Whenever operands have side effects, sequence them yourself.
Where closures came from
The mathematics behind this lesson is older than computers. In the 1930s Alonzo Church's lambda calculus treated functions as values that can be applied, passed and returned, and showed that this alone is enough to express any computation. Lisp borrowed the word lambda in 1958, but early Lisps implemented variable lookup dynamically, and returning a function from a function did not reliably remember the variables it was created with. Programmers of the 1960s called this the funarg problem, and solving it properly required keeping environments alive after the call that created them, exactly what a closure does. Peter Landin's work in the 1960s on the mechanical evaluation of expressions gave the idea a precise form.
Scheme, in 1975, was the first widely known Lisp to combine lexical scope with first-class procedures throughout, and it showed that closures were practical, not merely theoretical. The idea then spread far beyond the Lisp family. Common Lisp adopted lexical scope in the 1980s. Brendan Eich has said that he was recruited to Netscape in 1995 with the idea of putting Scheme in the browser; JavaScript ended up with a very different syntax, but its functions are closures in exactly Scheme's sense. Today closures are part of Python, Ruby, Java (since lambdas in Java 8), C#, C++, Swift, Rust and Go, and the higher-order trio of map, filter and fold appears in nearly every mainstream standard library.
Functional style in practice
Scheme does not force a functional style, but it rewards one, and experienced Scheme programmers follow a few habits.
- Prefer
map,filterand folds to hand-written loops when they fit. They name the pattern, and a reader recognises it instantly. - Use
for-each, notmap, for side effects.mapmay apply its procedure in any order (R7RS leaves it unspecified) and builds a result list you then throw away. - Keep
set!inside closures. Assignment to a variable that only one closure can reach is easy to reason about. Assignment to global variables from many places is not. By convention, procedures that mutate state end in!. - Pass behaviour, not flags. Instead of a
sortwith adescending?flag, pass the comparison. Instead of a report with ten options, pass small procedures that format each part. - Mind the cost of building lists.
filterandmapeach build a new list. Chaining several over a long list is usually fine; for performance-critical code, a single fold or namedletavoids the intermediate lists.
Common mistakes
Misconception
Thinking a closure copies the values it uses. A closure keeps a reference to the environment, so it sees later changes to those variables. If two closures are created in the same environment, a set! through one is visible through the other. That is how a pair of procedures, say deposit! and balance, can share private state.
Misconception
Using map to print. (map display '(1 2 3)) may print in any order and returns a list of unspecified values. Use for-each.
Misconception
Using set! on a variable that does not exist yet. set! changes an existing binding; it does not create one. Use define (or a let) first.
Misconception
Mixing up fold argument orders. In this lesson's fold-left the accumulator comes first, (combine acc x); in SRFI 1's fold the element comes first, (kons x acc). Read the documentation of the fold you are using, and test with a non-commutative operation such as cons or - to be sure.
Exercises
1. Higher-order procedures and closures
Warm-upComputationalWhat does this print?
(write (map (lambda (x y) (* x y)) '(1 2 3) '(4 5 6)))
2. Higher-order procedures and closures
CoreComputationalUsing the lesson's fold-left, what does this return?
(fold-left (lambda (acc x) (+ (* acc 10) x)) 0 '(2 0 2 6))
3. Higher-order procedures and closures
CoreComputationalUsing the lesson's fold-right, what does this print?
(write (fold-right (lambda (x acc) (cons (* 2 x) acc)) '() '(1 2 3)))
4. Higher-order procedures and closures
Warm-upComputationalWith the lesson's twice and make-adder, what is ((twice (make-adder 3)) 10)?
5. Higher-order procedures and closures
CoreComputationalWith the lesson's make-counter, what does this print?
(define a (make-counter))
(define b a)
(a)
(b)
(write (a))
6. Higher-order procedures and closures
Warm-upComputationalUsing the lesson's filter, what does this print?
(write (filter (lambda (s) (> (string-length s) 3))
'("tea" "coffee" "mate" "kvass")))
7. Higher-order procedures and closures
StretchHumanWhat does this program print?
(define (make-account)
(let ((balance 0))
(list (lambda (n) (set! balance (+ balance n)))
(lambda () balance))))
(define acct (make-account))
((car acct) 50)
((car acct) 25)
(write ((cadr acct)))
8. Higher-order procedures and closures
CoreHumanYou want to print each element of a list on its own line, in order. Which is the right tool?
Further reading and resources
- R7RS-small, section 6.10: Control featuresThe definitions of map, for-each, apply and related procedures.
- SRFI 1: List libraryStandard names and argument orders for fold, filter, reduce and friends.
- SRFI 132: Sort librariesThe common sorting interface, provided by many implementations.
- Structure and Interpretation of Computer Programs, sections 1.3 and 3.1 · Harold Abelson and Gerald Jay Sussman with Julie SussmanHigher-order procedures, and local state through assignment.