Latest change Dec 17, 2022

Warning: under development!

A Brief Survey of Functional Programming Languages

Disclaimer: we make no claims whatever that this page is complete or even correct in all regards. It is simply a compilation of notes, links, and other information that I have gathered, for the purpose of providing my functional programming students with some historical context. Please mail reports on any bugs you find!

Theoretical roots

Functional programming draws heavily from the Lambda Calculus. The Lambda Calculus is really a branch of logic, developed in the 20's and 30's. It was developed by logicians who wanted to explore how to define functions formally and how to use this formalism as a foundation for mathematics.

The Lambda Calculus is an extremely simple formal language of functions. It is surprisingly powerful - much of mathematics can be defined in it! The first developments were by Schönfinkel (1924), and Curry (1930): they defined a variation called combinatory logic. Church (1932/1933) then defined the first version of the actual Lambda Calculus. These early logicians had no intention to define any programming languages. (There weren't even any computers then!)

Some Historical and Current Functional Languages

Much later, functional programming was invented. McCarthy defined the first versions of LISP around 1960. This is the first "real" functional programming language. See McCarthy's own History of Lisp.

There have been many dialects of LISP over the years. The predominant dialects now are mainly Common Lisp, and Scheme. LISP has been (and is) widely used in areas like AI, and as macro language on top of software, for instance AutoLISP for AutoCad (CAD software) and elisp for emacs (text editor).

In the late 70's, Backus put forward the idea of a "pure", higher order programming language with syntax similar to combinatory logic. He defined the language FP, which has been very influential for the further development of functional languages. An important idea in FP is that of higher order functions, i.e., functions that take functions as arguments or return them as results.

At about the same time, researchers at Univ. Edinburgh who dealt with automatic theorem proving found they needed a language to express strategies for proof search. They defined the language ML ("Meta-Language") for this purpose. Soon, they found out that ML actually could serve as a powerful general programming language, and it developed into such. Besides being higher-order like FP (but richer in syntax), it hosts important features like type inference, i.e., the ability to infer types for all parts of the program without there being any explicit type declarations. Many features of Haskell originate in ML, and the languages have quite similar "look-and-feel". Like Lisp there have been many dialects of ML. It is still a widely used functional language, which is often used as language in basic courses on functional programming. Two important dialects of ML, with good implementations, are Standard ML of New Jersey (SML) and OCaml.

Another ML-like language is Miranda, developed in 1985-1986. It is one of the first lazy, or non-strict functional languages. Such languages try to defer evaluation of expressions until the result is needed. This gives a different semantics to the language than if "eager" evaluation is used, and makes it possible to use features such as potentially infinite data structures.

The functional language that is probably being most used in industry is Erlang, a functional language with concurrent processes. Erlang was developed at Ericsson primarily for telecom applications, but it is a general programming language. Erlang has been around since the late eighties.

Functional languages have also been developed for scientific computing applications. The main reason to use functional languages for this kind of application is the very straightforward parallelization of functional programs, which was hoped to outweigh the loss of efficiency that functional program often experience from their more costly evaluation mechanisms and memory requirements. Two prominent representatives for this class of languages are Sisal and Id Nouveau.

Haskell was defined as an attempt to create "the" standard, non-strict, higher order functional language. It contains many of the features from earlier functional languages, such as higher order functions, type inference, and non-strict semantics. A novel invention in Haskell is type classes, a structured form of overloading that is reminiscent of how method names are overloaded in object-oriented languages. The first version of Haskell (1.0) was defined in 1990. Today Haskell is being alive and well, with a maintained compiler, and it is used in many projects.


Björn Lisper
bjorn.lisper (at) mdu.se