Functions that take functions as arguments or return functions as values. This is the mechanism of abstraction — patterns become parameters.
Procedures as arguments — summation
Three procedures — sum of integers, sum of cubes, sum of the pi series — share the same structure. The only difference is which function to apply and which term comes next. Extract the pattern: sum takes term and next as arguments.
Scheme
; Summation as a higher-order procedure.; sum(term, a, next, b) = term(a) + term(a+1) + ... + term(b)
(define (sum term a next b)
(if (> a b)
0
(+ (term a) (sum term (next a) next b))))
(define (inc n) (+ n 1))
(define (identity x) x)
(define (cube x) (* x x x))
; Sum of integers 1..10
(display "sum(1..10) = ")
(display (sum identity 1 inc 10)) (newline)
; Sum of cubes 1..5
(display "sum(1^3..5^3) = ")
(display (sum cube 1 inc 5)) (newline)
; Pi/8 series: 1/(1*3) + 1/(5*7) + 1/(9*11) + ...
(define (pi-term x) (/ 1.0 (* x (+ x 2))))
(define (pi-next x) (+ x 4))
(display "pi approx = ")
(display (* 8 (sum pi-term 1 pi-next 1000)))
Python
# Summation as a higher-order functiondef summation(term, a, nxt, b):
total = 0while a <= b:
total += term(a)
a = nxt(a)
return total
inc = lambda n: n + 1
identity = lambda x: x
cube = lambda x: x ** 3print(f"sum(1..10) = {summation(identity, 1, inc, 10)}")
print(f"sum(1^3..5^3) = {summation(cube, 1, inc, 5)}")
pi_term = lambda x: 1.0 / (x * (x + 2))
pi_next = lambda x: x + 4print(f"pi approx = {8 * summation(pi_term, 1, pi_next, 1000):.6f}")
Lambda — anonymous procedures
Sometimes naming a procedure is overkill. lambda creates a procedure without binding it to a name. It's the same mechanism as define — just without the name.
Scheme
; Lambda: anonymous procedures.; (lambda (params) body); Instead of (define (square x) (* x x)):
(display "lambda square: ")
(display ((lambda (x) (* x x)) 5)) (newline)
; Use lambdas directly in higher-order calls:
(define (sum term a next b)
(if (> a b) 0
(+ (term a) (sum term (next a) next b))))
; Sum of squares, no need to define square separately:
(display "sum of squares 1..5 = ")
(display (sum (lambda (x) (* x x))
1
(lambda (x) (+ x 1))
5))
; 1 + 4 + 9 + 16 + 25 = 55
Python
# Lambda in Pythonprint(f"lambda square: {(lambda x: x * x)(5)}")
def summation(term, a, nxt, b):
total = 0while a <= b:
total += term(a)
a = nxt(a)
return total
result = summation(lambda x: x * x, 1, lambda x: x + 1, 5)
print(f"sum of squares 1..5 = {result}") # 55
Let — local bindings
let creates local variables. It's syntactic sugar for an immediately-applied lambda. The scope is the body of the let expression.
Scheme
; let is syntactic sugar for ((lambda (vars) body) values); f(x, y) = x(1+xy)^2 + y(1-y) + (1+xy)(1-y); with a = 1+xy, b = 1-y:
(define (f x y)
(let ((a (+ 1 (* x y)))
(b (- 1 y)))
(+ (* x (square a))
(* y b)
(* a b))))
(define (square x) (* x x))
(display "f(1, 2) = ")
(display (f 12)) (newline)
; let is literally: ((lambda (a b) body) (+ 1 (* x y)) (- 1 y)); The bindings are evaluated in the enclosing scope,; so a and b can't refer to each other.
(display "f(3, 4) = ")
(display (f 34))
Python
# Local bindings โ Python just uses assignmentdef f(x, y):
a = 1 + x * y
b = 1 - y
return x * a**2 + y * b + a * b
print(f"f(1, 2) = {f(1, 2)}")
print(f"f(3, 4) = {f(3, 4)}")
Procedures as returned values
Functions that return functions are the other half of higher-order programming. average-damp takes a function and returns a smoothed version. This is the building block for Newton's method and fixed-point search.
Scheme
; Returning procedures: average-damp and compose.
(define (average x y) (/ (+ x y) 2))
; average-damp takes a function, returns a smoothed version
(define (average-damp f)
(lambda (x) (average x (f x))))
; Square root via fixed-point of average-damped y -> x/y
(define tolerance 0.00001)
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
(define (sqrt x)
(fixed-point (average-damp (lambda (y) (/ x y))) 1.0))
(display "sqrt(2) = ") (display (sqrt 2)) (newline)
(display "sqrt(9) = ") (display (sqrt 9)) (newline)
; compose: (compose f g)(x) = f(g(x))
(define (compose f g)
(lambda (x) (f (g x))))
(define (square x) (* x x))
(define (inc x) (+ x 1))
(display "(square . inc)(6) = ")
(display ((compose square inc) 6))
; (6+1)^2 = 49
Newton's method finds zeros of a function. Expressed as a fixed-point search on the Newton transform. The whole thing composes from pieces we already have: fixed-point, average-damp, the derivative. Each layer names one idea.
Scheme
; Newton's method: find x where g(x) = 0.; Newton transform: x -> x - g(x)/g'(x); Then find the fixed point of the transform.
(define tolerance 0.00001)
(define dx 0.00001)
(define (fixed-point f first-guess)
(define (try guess)
(let ((next (f guess)))
(if (< (abs (- guess next)) tolerance)
next
(try next))))
(try first-guess))
(define (deriv g)
(lambda (x) (/ (- (g (+ x dx)) (g x)) dx)))
(define (newton-transform g)
(lambda (x) (- x (/ (g x) ((deriv g) x)))))
(define (newtons-method g guess)
(fixed-point (newton-transform g) guess))
; sqrt(x) = find y where y^2 - x = 0
(define (sqrt x)
(newtons-method (lambda (y) (- (* y y) x)) 1.0))
(display "sqrt(2) = ") (display (sqrt 2)) (newline)
(display "sqrt(25) = ") (display (sqrt 25)) (newline)
; Cube root: find y where y^3 - x = 0
(define (cbrt x)
(newtons-method (lambda (y) (- (* y y y) x)) 1.0))
(display "cbrt(8) = ") (display (cbrt 8))
Python's lambda is limited to single expressions; Scheme's lambda takes a full body. For multi-statement procedures-as-values, Python uses def inside def. The let form has no direct Python equivalent — Python uses sequential assignment, which allows later bindings to reference earlier ones (unlike let, where all bindings are evaluated in the enclosing scope). SICP also introduces let* for sequential binding, which matches Python's behavior more closely.
Higher-order function