page 2  (24 pages) 1 3

ture!). Due to higher level basic operations, modern functional languages allow a mathematical style of thinking while programming, for example using function composition, partial function application, set comprehension and pattern matching. This is possible since these mathematical operations are known to give computable results when applied to computable arguments.

On digital computers mathematical operations are specified by textual objects, e.g. programs and their parts, for example expressions. It is well known that many mathematical operations can be faithfully realized by operations on symbolic expressions. A classic example is algebraic symbol manipulation, which abstractly but correctly describes concrete operations on numbers, matrices, etc. The term symbolic computation" often refers to such manipulations when realized on the computer, but can equally well be interpreted more broadly: to describe the entire theme of this article.

1.2 Operations on Functions and Programs

Two useful operations on (mathematical) functions are:

ffl Composition of f with g, written as f ; g or g ffi f .

ffl Function specialization of f(x; y), obtaining a one-argument function by freezing" x to a fixed value, e.g. x = a.

Corresponding symbolic operations on programs (assuming for concreteness that they are written in the >=-calculus):

ffl Symbolic composition: suppose f; g are computable by expressions ef ; eg. Then their composition is computable by expression >=x:eg(ef (x))

ffl Partial evaluation: the specialization of function f to x = a can be realized symbolically as the program >=y:ef (a; y). A well-known version of the same result, in the context of recursive function theory, is Kleene's s-m-n theorem [12,16].

1.3 Efficient Operations on Programs

The symbolic operations above have a common characteristic: while computable, they do not lead to particularly efficient programs. For example the composition program is no faster than just running the two programs from which it is constructed, one after the other. The main theme of this article is the efficient implementation of program operations that realize mathematical operations, in particular function composition and specialization. We begin with an example of each.

Composition

Consider the composition sum ffi squares ffi oneto, where oneto(n) = [n; n ? 1; . . . ; 2; 1] yields a list of the first n natural numbers, squares[a1; a2; . . . an] = [a2
1; a2
2; . . . ; a2
n] squares each element in a list, and
sum[a1; a2; . . . an] = a1 +a2+ . . . +an sums a list's elements. A straightforward program to compute sum ffi squares ffi oneto(n) is:

f(n) = sum(squares(oneto(n)))
squares(l) = if l = [] then [] else cons(head(l)**2, squares(tail(l)))
sum(l) = if l = [] then [] else head(l) + sum(tail(l))
oneto(n) = if n = then [] else cons(n, oneto(n-1))

A significantly more efficient and listless" program [21] for sum ffi squares ffi oneto is:

g(n) = if n = then else n**2 + g(n-1)