Editor's Note: Over the past few years, a new method of developing and writing computer programs called "functional programming" has evolved without getting much attention from the general public. Nevertheless, this novel paradigm may influence programming five to ten years from now. Every second year, the advances in this area are discussed at the Conference on Functional Programming and Computer Architecture (FPCA). FPCA '89 was held in London, England and DDJ correspondent Ronald Fischer was there; here is his report.

To start with, forget everything you have ever learned about computer programming. During the last decade, a new way of writing programs has slowly developed: The "Functional Programming Paradigm," which lacks some of the most salient features of traditional programming languages. Most notably among those missing features are looping constructs and the destructive assignment to memory variables. In some respects, this new programming style appears to be more like writing mathematical equations than developing algorithms. Its proponents in fact hope that it leads to more bug-free software, because programs may be proved correct by mathematical means, instead of by debugging. As an example, consider a function SUM, which returns the sum of a list of numbers:

     DEC SUM: LIST(NUM)-> NUM;
   --- SUM(NIL) <= 0;
   --- SUM(H::T) <= H + SUM(T);

This example is coded in a "real" functional language called "Hope+." I have chosen this language because of its straightforward syntax. Hope+ programs are easy to understand even if you are not yet comfortable with functional programming (FP for short).

The first line DEClares the function SUM as a mapping from the set "list of numbers" onto the set "numbers." The next two lines describe what SUM actually does: If applied to an empty list, SUM returns zero. If SUM is instead applied to a list consisting of a head H and a tail T, it sums up the tail and adds it to the head element. For Prolog programmers, this way of thinking may be familiar. Actually, there is a strong relationship between "pure" Prolog (that is, no "cut," no side effects, no extra logic features) and Hope+, as you may easily model one with the other.

Functional programs are appealing because they are free of side effects. They are called "referential transparent," which means that two successive invocations of a function with the same arguments always yield the same results. In traditional languages such as C, this may or may not be the case. Here is a C function that is not referential transparent:

     int foo(int n);
   { static int c=O;
   return n+getchar( )+(c++);
   }

You can argue that some programs are impossible to write without relying on side effects. Interactive input/output comes to mind, or generation of random numbers. As we will see shortly, this is not true: Every conventional program can be written in functional style. But first, it is necessary to understand a few little FP basics.

The roots of FP can be traced back to the famous mathematician Alonzo Church, who developed in 1941 a notation to reason about mathematical functions without giving them explicit names, that is, anonymous functions. This notation was called the "lambda calculus," and a function that returns the square of its argument looks similar to this in Church's notation: x.x*x

The argument x is listed to the left of the period. In order to calculate the square of a particular number, say 5, you write (x.x*x) 5.

It can be shown (but to do so would require a separate article the length of this one) that every function and thus every computer program could be written as a series of -- possibly nested -- lambda expressions. This is not obvious at all; just think of how you would write a recursive function such as SUM as a lambda expression. Note that you must not use names (for example, SUM) to accomplish the recursive call, because functions in the lambda calculus are unnamed. Besides, N.G. de Bruijn proved in 1972 that it is even possible to dispense with the names of the variables, too!

The first application of Church's theory was incorporated into the programming language Lisp, where the previously defined function to square its argument could be written as ( X (* X X)). Lisp could be very close to functional programming, but for efficiency reasons, Lisp designer McCarthy soon had to abandon this concept in favor of a more traditional approach. For example: (SETQ V 5) replaces the previous value of V with the new value 5. Destructive assignments, however, are forbidden in any FP language.

It was not before the 1970s that researchers really began to investigate the possibility of a pure functional language. In 1978, Fortran inventor John Backus published his now historic paper, "Can Programming Be Liberated From the Von-Neumann Style," where he described a new functional language called "FP." Soon after, research activity took off.

Cheaper memory and faster CPUs made functional programming usable. Hope+ was developed and used internally at universities for teaching purposes and for application programming. The first full-featured and commercially available compiler for a functional language was announced in 1985 at the International Conference on Functional Programming and Computer Architecture (FPCA '85) at Nancy, France, by researcher David Turner. The language implemented was called "MIRANDA" and introduced a formalism called "currying" (named after the theoretician Haskell B. Curry): A function of n arguments may be treated as a concatenation of n single-argument functions. Thus, if PLUS expects two arguments and returns their sum, the expression PLUS 1 denotes a new function of one argument, which simply adds 1 to it.

Miranda and Hope+ are not only pure functional languages for use in research; they are also intended to be used for application programming. As mentioned earlier, there seems to be a conflict between referential transparency and some real-world problems such as input/output. Of course, input from the terminal could be regarded as a list of characters that can be passed at once to a function for processing. Because output to the screen may be regarded as a similar list, one may be tempted to define a program doing interactive I/O in the following way: DEC DIALOGUE: LIST(CHAR)-> LIST(CHAR);

But this requires the program to anticipate the whole input at once and in advance! In an interactive environment, however, most input will not be available until at least part of the output has been written to the screen.

One solution to this problem is termed "lazy evaluation." During function evaluation, the program consumes only as much from its (input) parameters as is necessary for the communication with the terminal. Therefore, although DIALOGUE conceptually accesses all of its input at the beginning and delivers all of its output at the end of the computation, the code generated by the compiler manages the interleaving of input and output. The programmer, of course, need not worry.

     DEC silly: LIST(CHAR)->LIST(LIST(CHAR)):
   --silly(NIL)<=["Thank you for using <silly>"];
     --silly(onechar::remaining) <=
             (IF member(onechar, "0123456789") THEN "That's fine!\n"
             ELSE "Please type only digits!\n") :: silly(remaining);

     TYPEVAR any_type:
     DEC member: any_type #LIST (any_type)->TRUVAL;
    --member(_,NIL)<=FALSE;
     --member(a,a :: t)<=TRUE;
     --member(a,_ :: t)<=member(a,t);

  TOFILE(term_in,silly(FROMFILE (term_out));

term_in and term_out are not part of the language definition, but identifiers such as these should be provided by the respective Hope+ installation. Due to lazy evaluation, the user gets a response after each typed character.

Infinite data structures like the terminal input mentioned are called "streams." Streams are not only useful for input/output. The following Hope+ function returns an infinite list of successive integers, starting with N: DEC ILIST: NUM ->LIST(NUM); -- FROM(N) <= N :: FROM(N+1); This would be impossible to accomplish without lazy evaluation, because a call to ILIST would lead to a non-terminating loop. In Hope+, however, it is perfectly reasonable to work with those functions and structures.

So, what if you decide to use functional programming in real projects? There are a lot of compilers for imperative languages such as Fortran, C, Pascal, and even Smalltalk and Prolog, but if you go to a software store and ask for a nifty little FP system for your work-station, you will be disappointed.

Indeed, the present situation is reminiscent of the time the first Fortran compilers became available in the mid-1950s: Insiders knew that something revolutionary was going on, but how were they to participate? The situation with functional programming appears similar, but as it happens it could be worse.

Presently, the most advanced products run under Unix. This comes as no surprise because this operating system is prominent among universities. Hope+, for instance, runs under Unix. This compiler is not freely available, however, so you have to contact a university computer science department to get a copy. For instance, Imperial College of London runs a copy of Hope+ in its functional programming laboratory.

At present, only one language providing full laziness is commercially available: Miranda, the programming language invented by David Turner. Turner, who at the time worked at the University of Kent in England, founded his own company, Research Software Ltd., in order to market his compiler, which is currently available on Sun, Apollo, VAX (running Ultrix), and the Hewlett-Packard 9000 series.

One of Miranda's attractive features is its provision for strong typing without requiring the programmer to write any type declarations for variables. The compiler simply deduces the type of a function from its applications, and reports any inconsistencies it finds.

Data abstraction is realized by "constructor functions," which can be compared to user-defined types in traditional languages. To define a type tree representing a binary tree of numbers, you simply write: tree:: = niltree | node num tree tree.

In this equation, num is a predefined, primitive type, while the remaining words are user defined and introduced to the system with this equation. A function sumtree, which sums up all numbers stored in a tree, could be written like this:

     sumtree niltree = 0
   sumtree (node number left right) = number + sumtree left + sumtree right

New trees are built by the application of the constructors. The expression: node 5 (node 2 niltree niltree) niltree returns a tree whose root contains the number 5, whose left branch contains 2, and whose right branch is empty.

  || MIRANDA example program
  || defining a tree whose nodes can be any type
  || the type is represented by the asterisk symbol tree*::=niltree
  | node * (tree *) (tree *)

  || Now implementing a sort algorithm
  || To sort a tree, first flatten it to get a list of nodes
  || Next build a sorted tree from the list sort = flatten buildsorted

  || This defines how to flatten a tree
  flatten niltree = {}|| Flattening an empty tree gives the empty list
  || To flatten any other tree, flatten the left subtree first,
  || append the root, and append the flattened right subtree.
  flatten (node a left right) = flatten left ++ [a] ++ flatten right

  || This defines how to build a sorted tree from an unsorted list
  || Note: "<= and ">" must be defined on tree nodes!
  buildsorted   = foldr insert niltree || foldr is a predefined transformer!

       where
       insert a niltree = node a niltree niltree
       insert a (node b left right)
              = node b (insert a left) right, a<=b
              = node b left (insert a right), a>b

Miranda is unique in that it is already used for many industrial applications. Among the steadily increasing community of Miranda users are Toshiba, Signetics, Shell Netherlands, BP (UK), Olivetti, Logica Cambridge, and ICL. The British company Logica Cambridge uses Miranda currently for the design of Viper 2, a special-purpose microprocessor for real-time control.

For MS-DOS and OS/2, there are fewer possibilities for doing FP today. This is understandable, because these operating systems are used extensively in the scientific community. Also, due to memory limitations, porting a compiler such as Miranda to MS-DOS is a non-trivial, if not impossible, task. The market for OS/2, on the other hand, is not considered important enough yet to justify the cost of a conversion.

  # Defining the FACTORIAL function in NIAL
  # i.e., factorial 4 results in 16

  factorial IS FORK
       [1>=, 1 first,
        times [pass, factorial (1 CONVERSE minus)]
       ]

  # Defining the AVERAGE of a list of values
  # i.e., average 3 9 5 3 results in 4
  average IS/[sum,tally]

Some Lisp dialects also enforce, or at least enable, programming in a functional style. PC-Scheme, an implementation of the Lisp-derivate Scheme by hardware manufacturer Texas Instruments, is an example. The compiler is well made, but the user interface lacks speed and sophistication. There is also a functional Lisp derivate called "Le-Lisp," implemented at a French university for Unix and DOS. A public domain version of Backus's FP was implemented in C by Arch D. Robinson, Urbana, Illinois. It runs on Unix and MS-DOS, but may be used only for educational purposes because it is so slow.

The papers presented at FPCA '89 covered a wide range of subjects, from purely theoretical subjects to industrial applications. As with the introduction of Miranda in 1985, this year's conference revealed a new and widely discussed programming language called "Haskell," named after Haskell Curry (creator of the "currying functions" of the Miranda language). So what's the advantage of Haskell over Miranda?

While Miranda certainly is suitable for every kind of program development, it does not particularly support large projects with tens of programmers writing hundreds of modules concurrently. Haskell, on the other hand, supports modular programming by requiring the definition of clean interfaces between modules and of abstract data types. In some respects, Miranda is to Haskell as Pascal is to Modula-2: The spirit is the same, but the latter is more advanced.

Second, and even more important: Haskell is free! This means that for a nominal fee covering shipping and handling, anyone can get the original software including the source code and port it to any operating system for resale. Of course, there will be a version available ready to use that has to be paid for.

  main resps =
        [ ReadFile "FOO" Text,
               case resps of
                     (Return Val:_)->
                            AppendChan "stdout" Text Val]

Another interesting feature of Haskell is its relationship to object-oriented programming (OOP). Haskell has objects, classes, multiple inheritance, and all other OOP features except one, of course: Haskell objects don't have internal "states," because this would contradict the referential transparency of FP.

Other papers covered the union of FP and OOP, and also of FP and logic programming, the paradigm used in Prolog. The latter has been proved possible by Erik Ruf, an ambitious young researcher from Stanford University. While demonstrating his ability to speak close to the speed of light, he presented an extension to the programming language Scheme. Scheme is a deviation of Lisp that doesn't offer lazy evaluation, but enforces programming in FP style for subprograms that don't rely on interactive input/output such as compilers. Ruf's extension, Log-Scheme, simulates all constructs of Prolog, including unification and extra logical features such as "The Cut."

Maybe the most interesting question from the conference is not, "Should I use FP or OOP or logic programming in the future?" but "Why not use them all together?"

A great deal of the presented papers focused on the difficulties experienced during the implementation of FP compilers. Among the topics were the aggregate assignment problem, strictness analysis, and abstract interpretation.

Adrienne Bloss from the Virginia Polytechnic Institute for example, worked on the aggregate assignment problem. Aggregates (that is, arrays or records) are necessary for storing huge amounts of data in an uniform way. Because destructive assignment is forbidden in the functional programming paradigm, how do I, then, "update" an array? In theory, the solution is easy: You just have to define an "update function." The following example looks like Hope+ again, but because this language does not provide arrays at all (lists are used instead), I simply invented them for the sake of clarity:

Thus, let ARRAY(T) be an (open ended) array of type T. The update function must be declared like this: TYPEVAR T; DEC UPD: ARRAY(T) # NUM # T -> ARRAY(T);

UPD(A, N, V) therefore returns a copy of the array A, except the Nth element is replaced by V. Obviously this involves a lot of copying and memory management at run time, especially when the arrays are large. In fact, this is one of the main obstacles when writing efficient FP compilers. Adrienne Bloss investigates the possibility of doing an in-place-update instead of copying, for example, a destructive assignment of V to the Nth element of A. This is not always safe. In the context LET A=some array IN TOFILE(term_out, UPD (A, 4,155)), the previous value of A need not be kept in memory, while a function call like F(UPD(A, N1, V1), UPD-(A, N2, V2), G(A)), which involves some auxiliary functions F and G, makes copying necessary. Of course, this decision is made by the compiler. The programmer still thinks in terms of functions free from side effects.

Another problem area in FP is strictness analysis. As mentioned earlier, input,/output and infinite data structures are handled by lazy (delayed) evaluation. This works fine in theory, but produces much overhead when applied to every argument of every function in a functional program.

To optimize the code produced, the compiler should know when it can safely use a traditional, non-lazy parameter passing mechanism. Such function parameters are called "strict." of course, the programmer could provide the necessary information. But this would introduce a new class of errors: Arguments erroneously declared "strict" would cause the program to loop forever. On the other hand, programmers themselves are "lazy" and tend to declare more arguments lazy than necessary, just to avoid such errors. This would lead to correct, but inefficient programs.

Enter strictness analysis. Here, the compiler tries to find out which function arguments can safely be assumed to be strict by examining the source code. This is not an easy task, because parameters may be passed through to other functions, which in turn must be analyzed. Most problems regarding strictness analysis are solved now, although not always in an optimal way: This kind of optimization is still very time consuming.

A tutorial on the state-of-the-art of abstract interpretation was given by John Hughes, also a co-author of the Haskell programming language. He defines abstract interpretation as "a compile-time analysis technique to predict information about a program's behavior from partial information about its inputs." The idea behind this is simple: The more the compiler knows about the program, the more efficient code may be produced. A typical example is the SIGN function: SIGN(X) is defined to be -1 for negative X and +1 for positive X. SIGN(O) equals zero.

Suppose a program contains the following function definition (the "sharp" symbol, #, separates the function parameters):

     DEC F:NUM # NUM-> NUM;
     -- F(I,J)<=I*SIGN(I*J);

Now imagine that the compiler is able to prove that on every concrete invocation of function F, both arguments supplied always have the same sign. The compiler then can conclude that SIGN(I*J) always produces +1 and F therefore reduces to:

     DEC F:NUM # NUM-> NUM;
     -- F(I,J)<=I*SIGN(I*J);

As a next step, the function F is obviously not necessary at all, because it does not perform any computation. This means that no code for F is generated, and that every application of, say, F(A,B) is simply replaced by its first argument, A. The conference also attracted some researchers from other areas who are normally not associated with functional programming in the scientific community. Among the audience, there was for instance Professor Tim Teitelbaum of Cornell University. Teitelbaum became quite famous due to his work on the Cornell Program Synthesizer, an integrated program development system that analyzes and compiles the program while it is being entered. What motivated Professor Teitelbaum to make the trip to Europe and show interest in an entirely different subject?

"The work with the synthesizer generator is motivated by an interest in incremental computation," says Tim Teitelbaum, adding, "In the past, we have used attribute grammars for this purpose. But attribute grammars are not the only game in town. A lot of people consider functional programs a more natural way for expressing incremental compilation." For the current version of his program synthesizer, Teitelbaum and his students already use a special technique derived from FP called "memorization," where function results are automatically stored in a table after the first evaluation, and retrieved quickly when the function happens to be called again with the same argument.

Clearly, implementation problems are no longer stumbling blocks. Lazy evaluation is a commonly-used technique, at least at universities, and FP systems perform well enough to be used for practical purposes, fast workstations and a few megabytes of memory provided. This contrasts with the conference held at Nancy four years ago, where only two examples of very special industrial applications were mentioned.

Despite its name, this year's FPCA covered many topics on functional programming, but practically none on computer architecture. This is surprising, because parallelism in hardware especially would gain a lot from functional programming: Due to referential transparency, all arguments to a function may be safely evaluated in parallel without worrying about possible conflicts. Despite this, the resolution of many implementation problems has obviously shifted towards a software instead of hardware solution.

The implications of this fact are not yet apparent. Perhaps most researchers concentrate on sequential machines because those are available today and in widespread use. The opinions are not undivided, however. Tim Teitelbaum, for instance, assumes that, "The future will be dominated by parallel architecture. The issue of how to program such machines is still very open. If it turns out that the FP people really have the answer, then we will necessarily switch over to functional programming in order to get the benefits of the parallelism."

The next conference, FPCA '91, will be held in the United States. At that time, the first version of Haskell should be up and running. Maybe the revolution has already begun.

DDJ: Simon, you promise that your new language called "Haskell" will be a standard and will be freely available. In what way do you mean it's free and everybody will have it? Will it be like SNOBOL4, so everybody can have the source code for it?

P-J: Sure, the main aspect for it is that anybody can implement it and distribute their implementations.

DDJ: Such as early Unix?

P-J: That's right. Anybody can use Haskell and distribute it.

DDJ: What do you think when it will be available?

P-J: Well, to the end of next year [i.e., 1990], we will have a first-time beta version. Until the end of the following year, we expect to have a full working version.

DDJ: What do you think will be the reaction from the industry? Will Haskell become an established standard in 10 or 20 years?

P-J: Oh, we already have several industrial promises involving functional projects, so the industry is showing some interest. One of them is British Telecom. Another one has been ICL. They were recently involved in a large European project to do with declarative [i.e., functional] programming.

DDJ: Do they actually use functional programming for applications work?

P-J: Mainly it's restricted at the moment to industrial research labs, because available implementations just haven't been fast enough. Nowadays we are just beginning to get to a state, where we've got implementations of functional languages where you're only losing a small factor over writing in Fortran or C, and the productivity benefits you pick up from writing in functional languages then become sufficiently severe.

DDJ: Do you think that education will be an issue?

P-J: Well, I think education is an important thing. That's why Pascal became so important, because it was taught in a lot of universities, so a whole generation of students went out knowing Pascal. We have already started teaching our students functional programming in their first year; we also teach imperative languages later on as well. So, functional programming may become more widespread now. -- R.F.

Copyright © 1989, Dr. Dobb's Journal