2 Pure Functional Programming

2.1 Lambda

The defining feature of functional programming is that functions are first-class values. This means that they can be treated like numbers or strings. They can be stored in data structures, used as arguments, produced as the result of evaluating a function, and, perhaps most importantly, they can be created dynamically during computation.

Because the result of an expression can be a function that we might wish to apply, function application is slightly more general than before. Previously, the first thing after the open parenthesis in a function application was the name of a pre-defined or user-defined function; now it can be an expression whose value is the function to be applied.

> (define (translate s)     (cond       [(equal? s 'plus) +]       [(equal? s 'minus) -]))

> ((translate 'plus) 3 4)

7

The form that creates a function dynamically is lambda, named after the similar notation used by Church in the lambda calculus. Here is a function that squares its argument.

(lambda (x) (* x x))

This function is anonymous (has no name). We saw earlier how to define named functions.

(define (square x)

(* x x))

Unlike this define form, the use of lambda creates an expression. The result of evaluating this expression is a function value. One of the things we can do with this value is bind a name to it.

(define square

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

Not only is this definition equivalent to the earlier one, but the earlier one is syntactic sugar for this one (the earlier one is translated to this one before the program is run). That is, all definitions bind names to values. Function definitions bind names to lambda expressions.

The previous example suggests that a lambda expression is simply a value, like 42 or "forty-two", without any further need for evaluation. However, the following example suggests that things are a bit more complicated than that.

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

> (make-adder 3) #<procedure>

We see that the value of (make-adder 3) is a procedure (function). But the value of this function cannot be (lambda (y) (+ x y)), because x is a free variable in this expression (its binding occurrence is not within the expression). When we evaluate (make-adder 3), the name x is bound to 3 for the duration of the evaluation of the body expression of make-adder. So (make-adder 3) is functionally equivalent to (lambda (y) (+ 3 y)).

> ((make-adder 3) 4)

7

The result of evaluating a lambda expression is a closure, consisting of the expression plus bindings for all of its free variables. This is the key to the power of lambda. A lambda expression specifies a future computation to be carried out zero or more times, with some information from the time of creation of the closure (the code and free variable bindings) and some information to be supplied in future (bindings for the parameters). This allows us to write code that is more expressive and more readable.

As another example of the use of closures, consider the following "alternative" implementation of the basic list primitives.

(define (cons f r) (lambda (b) (if b f r)))

(define (first lst) (lst true))

(define (rest lst) (lst false))

This seems mysterious at first glance. The result of applying this version of cons to two arguments is a closure where the free variables f and r in the expression (lambda (b) (if b f r)) are bound to those two arguments. The code in the closure is a function that accepts a message or switch (the Boolean value of the parameter b) and produces one of the two values stored in the closure. This idea can be extended to a general object/class system, and the message-passing metaphor is useful in object-oriented programming. (Racket provides such a system.)

Since a lambda expression may appear anywhere that an expression may appear, including inside another lambda expression, the notion of scope becomes more complicated. The scope of a parameter of a lambda expression is the body of the expression, except for (as before) the scopes of any binding occurrences of the same name.

2.2 Higher-Order Functions

A higher-order function is a function that consumes a function as an argument, or produces a function as a result. The ability to write higher-order functions permits us to abstract many common recursive patterns. The map function has two arguments, a function (itself consuming one argument) and a list. It produces the list that results from applying the function to each item in the argument list.

> (map (lambda (x) (* x x)) '(1 2 3 4 5))

'(1 4 9 16 25)

> (map odd? '(1 2 3 4 5))

'(#t #f #t #f #t)

Although map is pre-defined, we can easily write it.

(define (map f lst)

(cond

[(empty? lst) empty]

[else (cons (f (first lst)) (map f (rest lst)))]))

The pre-defined map is more general than the above code, as it can consume n list arguments, if its first argument is a function that itself consumes n arguments. The kth element of the resulting list is the result of applying the function to the kth elements of the argument lists.

> (map + '(1 2 3) '(4 5 6))

'(5 7 9)

Similarly, we can write the pre-defined filter, which consumes a Boolean-valued function and a list, and produces the list of all items in the argument list that produce true when the function is applied.

> (filter odd? '(1 2 3 4 5))

'(1 3 5)

(define (filter f lst)

(cond

[(empty? lst) empty]

[(f (first lst)) (cons (first lst) (filter f (rest lst)))]

[else (filter f (rest lst))]))

Recall the example of summing the values in a list, presented earlier.

(define (sum-list lst)

(cond

[(empty? lst) 0]

[else (+ (first lst) (sum-list (rest lst)))]))

We can generalize this at two points: the value produced in the base case (when the list is empty), and the function used to combine the first element of the list with the result of the recursive call.

We can also generalize the tail-recursive version we wrote.

foldr and foldl are pre-defined. When the combine argument is not straightforward to express, it might be better to use an iteration or comprehension (discussed later).

We have seen that some pre-defined functions such as + can consume an arbitrary number of arguments. It is sometimes convenient to apply such a function to an already-computed list of arguments. The apply function does just this.

> (apply + '(1 2 3 4 5))

15

We can write user-defined functions that consume an arbitrary number of arguments.

(define sqr-list   (lambda args     (map sqr args)))

> (sqr-list 1 2 3) '(1 4 9)

Here is another way of writing the previous example.

(define (sqr-list . args)

(map sqr args))

The dot signifies that the identifier that follows is a "rest" argument. It can be preceded by any number of required regular arguments.

Racket also supports the specification of optional arguments with default values, and keyword arguments which can appear in any order. The case-lambda form simplifies the case where a function has different behaviour depending mainly on the number of arguments. For details of these features, see the section Functions: lambda in the Racket Guide.

2.3 Local Variables

For readability, efficiency, and organization, it is often useful to bind a name to a value but have the binding operate in a limited context. We have already seen one way to get local scope, by using lambda:

> ((lambda (x y)      ; expression using x and y, such as      (+ (* x x) (* y y)))    (+ 1 2) (+ 3 4))

58

The let form is syntactic sugar for this.

> (let ([x (+ 1 2)]         [y (+ 3 4)])     (+ (* x x) (* y y)))

58

The square brackets here around each name-expression pair, as with their use for question-answer pairs in cond, are purely a convention for readability; parentheses may be used instead.

We may wish to have the expression in a later name-expression pair refer to an earlier name. This can be done by nesting let expressions, with one pair per let, but the resulting code is not very readable. The let* form is syntactic sugar for this.

> (let* ([x (+ 1 2)]          [y (+ x 4)])     (* x y))

21

In order to define a local function using let or let*, we must use lambda to describe the function. But neither form allows the definition of mutually-recursive functions. The letrec form takes care of this.

> (letrec ([even? (lambda (n) (or (zero? n)                                   (odd? (sub1 n))))]            [odd?  (lambda (n) (and (not (zero? n))                                    (even? (sub1 n))))])     (even? 12))

#t

The local form combines the features of let* and letrec, but uses define for readability (this also aids in code refactoring):

> (local [(define (even n)             (or (zero? n)                 (odd? (sub1 n))))           (define (odd n)             (and (not (zero? n))                  (even? (sub1 n))))]     (even? 12))

#t

Racket also permits internal definitions within the body of a defined function or lambda expression.

(define (sum-list lst)

(define (sum-list-helper lst acc)

(cond

[(empty? lst) acc]

[else (sum-list-helper (rest lst) (+ acc (first lst)))]))

(sum-list-helper lst 0))

2.4 Pattern Matching

Accessor functions for lists and structures have simple syntax, but can lead to verbose and hard-to-read code for manipulating complex data structures. The match form resembles cond. Its arguments consist of a target expression (which is reduced to a value) and a sequence of pattern-answer pairs. The target value is matched against each pattern in turn, and when a match is found, the corresponding answer expression is evaluated and becomes the value of the match expression. Patterns have a recursive structure, and subpatterns can bind names to matched sub-values that can then be used in the corresponding answer expression.

The simplest patterns are Racket values, including those expressed using hash-sign or quote notation.

(define (test1 v)   (match v     [1 "one"]     ["two" (+ 1 1)]     ['three (- 5 2)]     ['(a b c) "that list"]))

> (test1 (cons 'a (cons 'b (cons 'c empty)))) "that list" > (test1 1) "one"

A single identifier as a pattern matches any value, and binds the identifier to that value. As a complete pattern, this can be used as the equivalent of else for cond. But it is more often used as a sub-pattern or pattern variable. Compound patterns binding names to parts of lists and structures can be created using pattern variables with cons, list, and the names of user-defined structures.

An ellipsis (...) after a pattern matches zero or more times, and a pattern variable within the pattern is bound to a list of matches. Thus the patterns (cons f r) and (list f r...) behave identically.

> (match '((76 trombones) (110 cornets) (1000 reeds) (50 cannon))     [(list (list number instrument)...) (apply + number)])

1236

quasiquote has a special meaning in a pattern: it acts like quote, but unquote escapes back to patterns (whereas it escapes back to expressions when used within a quasiquoted expression).

> (match '(1 2 3 4)     [`(1 2 ,x ,y) `(2 ,y ,x 1)])

'(2 4 3 1)

There are further match forms to generalize lambda, let, and define. For details of these, see the section Pattern Matching in the Racket Reference, which also describes additional ways to construct patterns.