Functional Programming

The functional programming languages, such as Haskell [PJ03], Lisp [McC62], Miranda [Tho96], Scheme [Spe09] and SML [Mil90], are based on Alonzo Church's λ-calculus [Chu41]. Turing machines, λ-calculus, and combinatorial logic are all equivalent in that they can compute exactly the same things but since the λ-calculus is the most like a programming language it has a good claim to being the prototype programming language.

Lazy evaluation, which is the evaluation strategy of the "pure" functional programming languages, permits some interesting programming techniques including circular programs [All89, All93], that is, recursively defined data structures and mutually recursive functions and data structures (corecursion). There are some examples from here to here.


[All89] Lloyd Allison, 'Circular Programs and Self-Referential Structures', Software Practice & Experience, 19(2), pp.99-109, doi:10.1002/spe.4380190202, February 1989.
[All93] Lloyd Allison, 'Applications of Recursively Defined Data Structures', Australian Computer Journal, 25(1), pp.14-20, arxiv:2206.12795, 1993.
[Chu41] A. Church, 'The Calculi of Lambda Conversion', Princeton Univ. Press, Annals of Mathematical Studies (AM-6), isbn:0691083940, isbn13:978-0691083940, jstor:j.ctt1b9x12d, Aug. 1941.
[McC62] J. McCarthy et al, 'Lisp 1.5 Programmer's Manual', MIT Press, isbn13:978-0262130110, Aug. 1962.
[Mil90] R. Milner et al, 'The Definition of Standard ML', (SML), MIT Press, isbn:0262631326, isbn13:978-0262631327, 1990.
[PJ03] S. Peyton Jones (ed), 'Haskell 98 Language and Libraries: The Revised Report', Cambridge University Press, isbn:0521826144, isbn13:978-0521826143, 2003.
[Spe09] M. Sperber et al, 'Revised Report on the Algorithmic Language Scheme', J. Functional Programming, 19 suppl.1, pp.1-301, doi:10.1017/S0956796809990074, Aug. 2009.
[Tho96] S. Thompson, 'Miranda: The Craft of Functional Programming', Pearson Ed ESL, isbn:0201422794, isbn13:978-0201422795, 1996.