Frequently Asked Questions for comp.lang.functional

• No changes this month.

This section gives brief answers to a number of general questions concerning functional programming languages, and some pointers to relevant literature and internet resources.

What is a "functional programming language"?

Where can I find out more about the history and motivation for functional programming?

Here are two useful references:

Are there any textbooks about functional programming?

Yes, here are a selection:

Programming:

Are there any journals and conferences about functional programming?

Yes, here are a selection:

Journals:

Are there any schools and workshops on functional programming?

Yes, here are a selection:

Schools:

Are functional programming languages useful in education?

Functional languages are gathering momentum in education because they facilitate the expression of concepts and structures at a high level of abstraction. Many university computing science departments now make use of functional programming in their undergraduate courses; indeed, a number of departments teach a functional language as their first programming language. Further information about the use of functional programming languages in education (including links to relevant conferences and workshops) is available on the web from:

This section gives brief answers to a number of technical questions concerning functional programming languages, and some pointers to relevant literature and internet resources.

What is a "purely functional" programming language?

This question has been the subject of some debate in the functional programming community. It is widely agreed that languages such as Haskell and Miranda are "purely functional", while SML and Scheme are not. However, there are some small differences of opinion about the precise technical motivation for this distinction. One definition that has been suggested is as follows:

The term "purely functional" is often used to describe languages that perform all their computations via function application. This is in contrast to languages, such as Scheme and Standard ML, that are predominantly functional but also allow `side effects' (computational effects caused by expression evaluation that persist after the evaluation is completed).

Sometimes, the term "purely functional" is also used in a broader sense to mean languages that might incorporate computational effects, but without altering the notion of `function' (as evidenced by the fact that the essential properties of functions are preserved.) Typically, the evaluation of an expression can yield a `task', which is then executed separately to cause computational effects. The evaluation and execution phases are separated in such a way that the evaluation phase does not compromise the standard properties of expressions and functions. The input/output mechanisms of Haskell, for example, are of this kind.

• "What is a purely functional language", Amr Sabry, Journal of Functional Programming, 8(1):1-22, Cambridge University Press, January 1998.

What is "currying", and where does it come from?

Currying has its origins in the mathematical study of functions. It was observed by Frege in 1893 that it suffices to restrict attention to functions of a single argument. For example, for any two parameter function f(x,y), there is a one parameter function f' such that f'(x) is a function that can be applied to y to give (f'(x))(y) = f (x,y). This corresponds to the well known fact that the sets (AxB -> C) and (A -> (B -> C)) are isomorphic, where "x" is cartesian product and "->" is function space. In functional programming, function application is denoted by juxtaposition, and assumed to associate to the left, so that the equation above becomes f' x y = f(x,y).

Apparently, Frege did not pursue the idea further. It was rediscovered independently by Schoenfinkel, together with the result that all functions having to do with the structure of functions can be built up out of only two basic combinators, K and S. About a decade later, this sparked off the subject of combinatory logic, invented by Haskell Curry. The term "currying" honours him; the function f' in the example above is called the "curried" form of the function f. From a functional programming perspective, currying can be described by a function:

curry : ((a,b) -> c) -> (a -> b -> c)

The inverse operation is, unsurprisingly, refered to as uncurrying:

uncurry : (a -> b -> c) -> ((a,b) -> c)

For further reading, see:

• "Highlights of the history of the lambda-calculus", J. Barkley Rosser, ACM Lisp and Functional Programming, 1982.

• "Ueber die Bausteine der mathematischen Logik", Moses Sch\"onfinkel, Mathematische Annalen, 92, 1924. An English translation, "On the building blocks of mathematical logic", appears in "From Frege to G\"odel", Jean van Heijenoort, Harvard University Press, Cambridge, 1967.

• "Combinatory logic", Haskell B. Curry and Robert Feys, North-Holland, 1958. This work also contains many references to earlier work by Curry, Church, and others.

What is a "monad", and what are they used for?

The concept of a monad comes from category theory; full details can be found in any standard textbook on the subject. Much of the interest in monads in functional programming is the result of recent papers that show how monads can be used to describe all kinds of different programming language features (for example, I/O, manipulation of state, continuations and exceptions) in purely functional languages such as Haskell:

How can I write a "parser" in a functional programming language?

A parser is a program that converts a list of input tokens, usually characters, into a value of the appropriate type. A simple example might be a function to find the integer value represented by a string of digits. A more complex example might be to translate programs written in a particular concrete syntax into a suitable abstract syntax as the first stage in the implementation of a compiler or interpreter. There are two common ways to write a parser in a functional language:

What does it mean to say that a functional programming language is "strict" or "non-strict"?

Here's one (operational) way to explain the difference:

• In a strict language, the arguments to a function are always evaluated before it is invoked. As a result, if the evaluation of an expression exp does not terminate properly (for example, because it generates a run-time error or enters an infinite loop), then neither will an expression of the form f(exp). ML and Scheme are both examples of this.

• In a non-strict language, the arguments to a function are not evaluated until their values are actually required. For example, evaluating an expression of the form f(exp) may still terminate properly, even if evaluation of exp would not, if the value of the parameter is not used in the body of f. Miranda and Haskell are examples of this approach.

There is much debate in the functional programming community about the relative merits of strict and non-strict languages. It is possible, however, to support a mixture of these two approaches; for example, some versions of the functional language Hope do this.

What is the performance of functional programs like?

In some circles, programs written in functional languages have obtained a reputation for lack of performance. Part of this results from the high-level of abstraction that is common in such programs and from powerful features such as higher-order functions, automatic storage management, etc. Of course, the performance of interpreters and compilers for functional languages keeps improving with new technological developments.

Here are a selection of references for further reading:

Where can I find out about applications of functional programming?

Here are a selection of places to look:

This section gives some pointers to other internet resources on functional programming.

This section gives a brief overview of a number of programming languages that support aspects of the functional paradigm, and some pointers to relevant literature and internet resources. The table below classifies the languages into strict/non-strict and sequential/concurrent, and may be useful when searching for suitable languages for particular applications. Some of the languages have multiple versions with different classifications (see the language overviews for further details), but for simplicity only the most common version of each language is considered in the table.

	Sequential:	Concurrent:
Strict:	ASpecT Caml FP J Mercury ML OPAL Scheme	Erlang NESL Oz Pizza Sisal
Non-strict:	Gofer Haskell Hope Hugs Miranda	Clean Id

ASpecT is a strict functional language, developed at the University of Bremen, originally intended as an attempt to provide an implementation for (a subset of) Algebraic Specifications of Abstract Datatypes. The system was designed to be as user-friendly as possible, including overloading facilities and a source-level debugger. For reasons of efficiency, the system uses call-by-value evaluation and reference counting memory management.

Over the years more and more features have been added, including subsorting, functionals, and restricted polymorphism. The ASpecT compiler translates the functional source code to C, resulting in fast and efficient binaries. ASpecT has been ported to many different platforms, including Sun3, Sun4, Dec VAX, IBM RS6000, NeXT, Apple A/UX, PC (OS/2, Linux), Amiga and Atari ST/TT. The ASpecT compiler is available by ftp from:

Host:	ftp.Uni-Bremen.DE;
Directory:	/pub/programming/languages/ASpecT.

The most important application of ASpecT to date is the interactive graph visualization system daVinci; currently (September '96), version 2.0.x is composed of 34.000 lines of ASpecT code, 12.000 lines of C code and 8000 lines of Tcl/Tk code. daVinci is an X11 program, and is available for UNIX workstations from Sun, HP, IBM, DEC, SGI, and for Intel PCs with a UNIX operating system. Further information about daVinci is available on the web from:

Caml is a dialect of the ML language developed at INRIA that does not comply to the Standard, but actually tries to go beyond the Standard, in particular in the areas of separate compilation, modules, and objects. Two implementations of Caml are available:

• The older implementation, Caml Light, is distinguished by its small size, modest memory requirements, availability on microcomputers, simple separate compilation, interface with C, and portable graphics functions. It runs on most Unix machines, on the Macintosh and on PCs under Ms Windows and MSDOS. The current version at the time of writing is 0.71.

• A more ambitious implementation, Objective Caml (formerly known as Caml Special Light), is also available. It adds the following extensions to Caml Light:
  • Full support for objects and classes, here combined for the first time with ML-style type reconstruction;

  • A powerful module calculus in the style of Standard ML, but providing better support for separate compilation;

  • A high-performance native code compiler, in addition to a Caml Light-style bytecode compiler.

  Objective Caml is available for Unix and Windows 95/NT, with the native-code compiler supporting the following processors: Alpha, Sparc, Pentium, Mips, Power, HPPA.

Both implementations of Caml are available by ftp from:

Host:	ftp.inria.fr;
Directory:	/lang/caml-light.

Further information about Caml is available on the web from:

The Concurrent Clean system is a programming environment for the functional language Concurrent Clean, developed at the University of Nijmegen in The Netherlands. The system is one of the fastest implementations of functional languages available at the time of writing. Through the use of uniqueness typing, it is possible to write purely functional interactive programs, including windows, menus, dialogs, etc. It is also possible to develop real-life applications that interface with non-functional systems. With version 1.0, the language emerged from an intermediate language to a proper programming language. Features provided by the language include:

• Lazy evaluation;
• Modern input/output;
• Annotations for parallelism;
• Automatic strictness analysis;
• Annotations for evaluation order;
• Inferred polymorphic uniqueness types;
• Records, mutable arrays, module structure;
• Existential types, type classes, constructor classes;
• Strong typing, based on the Milner/Mycroft scheme.

Concurrent Clean is available for PCs (Microsoft Windows, Linux), Macintoshes (Motorola, PowerPC), and Sun4s (Solaris, SunOS). The system is available by ftp from:

Host:	ftp.cs.kun.nl;
Directory:	/pub/Clean.

Further information about Concurrent Clean is available on the web from:

Erlang is a dynamically typed concurrent functional programming language for large industrial real-time systems. Features of Erlang include:

• Modules;
• Recursion equations;
• Explicit concurrency;
• Pattern matching syntax;
• Dynamic code replacement;
• Foreign language interface;
• Real-time garbage collection;
• Asynchronous message passing;
• Relative freedom from side effects;
• Transparent cross-platform distribution;
• Primitives for detecting run-time errors.

Erlang is freely available on the web from:

FP is a side-effect free, combinator style language, described in:

• "Can programming be liberated from the von Neumann style?", John Backus, Communications of the ACM, 21, 8, pp.613-641, 1978.

A interpreter and a compiler (to C) for FP are available by ftp from:

Host:	gatekeeper.dec.com;
Directory:	pub/usenet/comp.sources.unix/volume13/funcproglang;
Directory:	pub/usenet/comp.sources.unix/volume20/fpc.

The Illinois FP system supports a modified version of FP that has a more Algol-like syntax and structure, and is described in the following article:

• "The Illinois functional programming interpreter", Arch D. Robison, Proceedings of the SIGPLAN '87 Symposium on Interpreters and Interpretive Techniques, SIGPLAN notices, Volume 22, Number 7, July 1987.

The Gofer system provides an interpreter for a small language based closely on the current version of the Haskell report. In particular, Gofer supports lazy evaluation, higher-order functions, polymorphic typing, pattern-matching, support for overloading, etc.

The most recent version of Gofer, 2.30a, is available by ftp from:

Host:	ftp.cs.nott.ac.uk;
Directory:	/nott-fp/languages/gofer.

Gofer runs on a wide range of machines including PCs, Ataris, Amigas, etc. as well as larger Unix-based systems. A version for the Apple Macintosh is also available, by ftp from:

Host:	ftp.dcs.glasgow.ac.uk;
Directory:	/pub/haskell/gofer/macgofer.

Please note the spelling of Gofer, derived from the notion that functional languages are GO(od) F(or) E(quational) R(easoning). This is not to be confused with `Gopher', the widely used internet distributed information delivery system.

In the mid-1980s, there was no "standard" non-strict, purely-functional programming language. A language-design committee was set up in 1987, and the Haskell language is the result. At the time of writing, Haskell 98 is the latest version of the language. Further information about Haskell, including the latest version of the Haskell report, is available on the web from:

Hope is a small polymorphically-typed functional language, and was the first language to use call-by-pattern. Hope was originally strict, but there are versions with lazy lists, or with lazy constructors but strict functions. Further information is available on the web from:

Hugs, the Haskell User's Gofer System, is an interpreted implementation of Haskell with an interactive development environment much like that of Gofer. Further information about Hugs is available on the web from:

Id is a dataflow programming language, whose core is a non-strict functional language with implicit parallelism. It has the usual features of many modern functional programming languages, including a Hindley/Milner type inference system, algebraic types and definitions with clauses and pattern matching, and list comprehensions.

J was designed and developed by Ken Iverson and Roger Hui. It is similar to the language APL, departing from APL in using using the ASCII alphabet exclusively, but employing a spelling scheme that retains the advantages of the special alphabet required by APL. It has added features and control structures that extend its power beyond standard APL. Although it can be used as a conventional procedural programming language, it can also be used as a pure functional programming language. Further information about J is available on the web from:

Miranda was designed in 1985-6 by David Turner with the aim of providing a standard non-strict purely functional language, and is described in the following articles:

• "Miranda: a non-strict functional language with polymorphic types", D.A. Turner, Proceedings FPLCA, Nancy, France, September 1985 (Springer LNCS vol 201, pp 1-16).

• "An overview of Miranda", D.A. Turner, SIGPLAN Notices, vol 21, no 12, pp 158-166, December 1986.

Miranda was the first widely disseminated language with non-strict semantics and polymorphic strong typing, and is running at over 600 sites, including 250 universities. It is widely used for teaching, often in conjunction with "Introduction to Functional Programming", by Bird and Wadler, which uses a notation closely based on Miranda. It has also had a strong influence on the subsequent development of the field, and provided one of the main inputs for the design of Haskell.

The Miranda system is a commercial product of Research Software Limited. Miranda release two (the current version at the time of writing) supports unbounded precision integers and has a module system with provision for parameterized modules and a built in "make" facility. The compiler works in conjunction with a screen editor and programs are automatically recompiled after edits. There is also an online reference manual.

Further information about Miranda is available by email from:

Mercury is a logic/functional programming language, which combines the clarity and expressiveness of declarative programming with advanced static analysis and error detection facilities. It has a strong type system, a module system (allowing separate compilation), a mode system, algebraic data types, parametric polymorphism, support for higher-order programming, and a determinism system --- all of which are aimed at both reducing programming errors and providing useful information for programmers and compilers.

The Mercury compiler is written in Mercury itself, and compiles to C. The compiler is available for a variety of platforms running Unix and Microsoft operating systems.

Further information about Mercury is available on the web from:

ML stands for meta-language, and is a family of advanced programming languages with (usually) functional control structures, strict semantics, a strict polymorphic type system, and parameterized modules. It includes Standard ML, Lazy ML, CAML, CAML Light, and various research languages. Implementations are available on many platforms, including PCs, mainframes, most models of workstation, multi-processors and supercomputers. ML has many thousands of users, and is taught to undergraduates at many universities.

NESL is a fine-grained, functional, nested data-parallel language, loosly based on ML. It includes a built-in parallel data-type, sequences, and parallel operations on sequences (the element type of a sequence can be any type, not just scalars). It is based on eager evaluation, and supports polymorphism, type inference and a limited use of higher-order functions. Currently, it does not have support for modules and its datatype definition is limited. Except for I/O and some system utilities it is purely functional (it does not support reference cells or call/cc).

The NESL compiler is based on delayed compilation and compiles separate code for each type a function is used with (compiled code is monomorphic). The implementation therefore requires no type bits, and can do some important data-layout optimizations (for example, double-precision floats do not need to be boxed, and nested sequences can be laid out efficiently across multiple processors.) For several small benchmark applications on irregular and/or dynamic data (for example, graphs and sparse matrices) it generates code comparable in efficiency to machine-specific low-level code (for example, Fortran or C.)

The current implementation of NESL runs on workstations, the Connection Machines CM2 and CM5, the Cray Y-MP and the MasPar MP2.

Further information about NESL is available on the web from:

The language OPAL has been designed as a testbed for the development of functional programs. Opal molds concepts from Algebraic Specification and Functional Programming, which shall favor the formal development of large production-quality software that is written in a purely functional style. The core of OPAL is a strongly typed, higher-order, strict applicative language that belongs to the tradition of Hope and ML. The algebraic flavour of OPAL shows up in the syntactical appearance and in the preference of parameterization to polymorphism.

OPAL is used for research on the highly optimizing compilation of applicative languages. This has resulted in a compiler which produces very efficient code. The OPAL compiler itself is entirely written in OPAL. Installation is straightforward and has been successfully performed for SPARCs, DECstations, NeXTs, and PCs running LINUX.

Further information about OPAL is available by ftp from:

Host:	ftp.cs.tu-berlin.de;
Directory:	/pub/local/uebb/.

Oz is a concurrent constraint programming language designed for applications that require complex symbolic computations, organization into multiple agents, and soft real-time control. It is based on a new computation model providing a uniform foundation for higher-order functional programming, constraint logic programming, and concurrent objects with multiple inheritance. From functional languages Oz inherits full compositionality, and from logic languages Oz inherits logic variables and constraints (including feature and finite domain constraints.) Search in Oz is encapsulated (no backtracking) and includes one, best and all solution strategies.

DFKI Oz is an interactive implementation of Oz featuring am Emacs programming interface, a concurrent browser, an object-oriented interface to Tcl/Tk, powerful interoperability features (sockets, C, C++), an incremental compiler, a garbage collector, and support for stand-alone applications. Performance is competitive with commercial Prolog and Lisp systems. DFKI Oz is available for many platforms running Unix/X, including Sparcs and 486 PCs, and has been used for applications including simulations, multi-agent systems, natural language processing, virtual reality, graphical user interfaces, scheduling, placement problems, and configuration.

Further information about Oz is available on the web from:

Pizza is a strict superset of Java that incorporates three ideas from functional programming:

• Parametric polymorphism;
• Higher-order functions;
• Algebraic data types.

Pizza is defined by translation into Java and compiles into the Java Virtual Machine, requirements which strongly constrain the design space. Thus Pizza programs interface easily with Java libraries, and programs first developed in Pizza may be automatically converted to Java for ease of maintenance. The Pizza compiler is itself written in Pizza, and may be used as a replacement for Sun's Java compiler (except that the Pizza compiler runs faster).

Pizza was designed by Martin Odersky and Philip Wadler, and implemented by Odersky. The design is described in the following paper:

• "Pizza into Java: translating theory into practice", Martin Odersky and Philip Wadler, 24th ACM Symposium on Principles of Programming Languages, Paris, January 1997.

The paper, downloads, and other information on Pizza is available on the web from any of the following locations (which mirror each other):

Scheme is a dialect of Lisp that stresses conceptual elegance and simplicity. It is specified in R4RS and IEEE standard P1178. Scheme is much smaller than Common Lisp; the specification is about 50 pages. Scheme is often used in computer science curricula and programming language research, due to its ability to simply represent many programming abstractions.

Further information about Scheme is available on the web from:

Sisal (Streams and Iteration in a Single Assignment Language) is a functional language designed with several goals in mind: to support clear, efficient expression of scientific programs; to free application programmers from details irrelevant to their endeavors; and, to allow automatic detection and exploitation of the parallelism expressed in source programs.

Sisal syntax is modern and easy to read; Sisal code looks similar to Pascal, Modula, or Ada, with modern constructs and long identifiers. The major difference between Sisal and more conventional languages is that it does not express explicit program control flow.

Sisal semantics are mathematically sound. Programs consist of function definitions and invocations. Functions have no side effects, taking as inputs only explicitly passed arguments, and producing only explicitly returned results. There is no concept of state in Sisal. Identifiers are used, rather than variables, to denote values, rather than memory locations.

The Sisal language currently exists for several shared memory and vector systems that run Berkeley Unix(tm), including the Sequent Balance and Symmetry, the Alliant, the Cray X/MP and Y/MP, Cray 2, and a few other less well-known ones. Sisal is available on sequential machines such as Sparc, RS/6000, and HP. Sisal also runs under MS-DOS and Macintosh Unix (A/UX). It's been shown to be fairly easy to port the entire language system to new machines.

Further information about Sisal is available on the web from: