Previous | Table of Contents | Next |
The most recent official release of the Scheme reference manual includes a hygienic macro system. The notation is somewhat different from what is shown above:
(define-syntax times (syntax-rules () ((times n) (lambda (x) (* x n)))))
The empty list after the phrase syntax-rules is used to contain literals, symbols that appear in the macro pattern that must appear identically in the macro invocation. For example, if you want to define a macro to change the format of if to
(if <condition> then <consequent> else <alternative>)
then the words then and else are literals in the macro pattern.
Hygienic macros make it straightforward to write syntactic extensions without worrying about the possibility of name capture. Unfortunately, in some cases a deliberate name capture is needed. The standard example is the definition of a looping control structure, such as for or while in the C family of languages, inside which specific names are used for escape mechanisms, such as break or continue. In these cases, the word break as used in a macro invocation should mean the same thing that break means in the macro definition. Therefore, some mechanism is needed to allow name capture when its wanted. As of this writing, there is no agreement among Schemers about the form that that mechanism will take.
In most languages, a computer program consists of a sequence of steps. (Some of the steps may be conditional or may be repeated.) A functional program is built not as a sequence of steps, but as a composition of functions. Here is a really simple example:
(define (second sequence) (car (cdr sequence))) > (second (Scheme programmers have more fun)) programmers
The function second is defined as a composition of the functions car (the first member of a list) and cdr (all but the first member). I am asking for the first member of the sublist containing all but the first member, but the first member of that sublist is the second member of the entire original list.
In principle, a language that has the ability to create procedures (that is, lambda) and the ability to invoke procedures does not need any other features. It can carry out any possible computation. You dont even need numbers; they can be represented as functions, and the arithmetic operations can be represented as functions of functions. Of course, you wouldnt want to have to reinvent arithmetic for every program, and so even Scheme, with its minimalist philosophy, provides some built-in (primitive) procedures and has other data types in addition to the procedure.
You dont even need the ability to assign a value to a name. Instead of using define to create a procedure named second, I could have said this:
> ((lambda (second) (second(Scheme programmers have more fun))) (lambda (sequence) (car (cdr sequence))) programmers
Even enthusiasts of functional programming usually take advantage of the convenience of define, but in functional programming, it is forbidden to change the value of a variable. There are no assignments of the x=x+1 sort. Most name/value associations are made not by assignment, but by calling a procedure; the procedures formal parameters (such as sequence) are associated with the actual values given in the procedure call. Calling the same procedure again does not change the value of sequence. Instead, it creates a new, separate variable that has the same name. (This idea of local variables is, of course, not unique to Scheme.)
Functional programming can directly express recurrence relations. For example, in Pascals triangle, every number is the sum of the two numbers above it, except for the first and last numbers of each row, which are 1.
(define (pascal row column) (if (or (= column 0) (= column row)) 1 (+ (pascal (- row 1) (- column 1)) (pascal (- row 1) column))))
This procedure is too slow for large row numbers (it takes exponential time) because it does many redundant calculations of numbers in higher rows. But it is a good starting point and can be elaborated into an efficient version that still represents the underlying mathematical relationship without introducing extraneous variable assignments along the lines of
for i = 0 to row {...}
Using procedures as data is also an important part of functional programming. Youve already seen map, which takes a procedure as one of its arguments and invokes the procedure repeatedly, and make-adder, which takes a number as its argument and returns a procedure whose behavior depends on that number. Heres another example:
(define (filter procedure values) (if (null? values) () (if (procedure (car values)) (cons (car values) (filter procedure (cdr values))) (filter procedure (cdr values))))) (define (even? number) (= (remainder number 2) 0)) > (filter even? (781 24 15 3 6 49 14)) (24 6 14)
The procedure filter takes as its first argument a predicate procedureone that returns either true or false. filters second argument is a list. filter calls the given predicate repeatedly, once for each member of the list argument. It constructs and returns a new list5 containing only those members of the original list for which the predicate returns true.
5Constructs and returns a new list implies that the original argument list is not changed. In functional programming, there are no changes to existing data structures.
Here is an example of functional programming in which both the argument and return value are procedures:
(define (derivative func) (lambda (x) (/ (- (func (+ x 0.0000001)) (func x)) 0.0000001)))
Previous | Table of Contents | Next |