To learn more
The computation model for functional languages is l-calculus, which
was invented by Alonzo Church in 1932. Church's goal was to define a
notion of effective computability through the medium of
l-definability. Later, it became apparent that the notion thus
introduced was equivalent to the notions of computability in the sense of
Turing (Turing machine) and Gödel-Herbrand (recursive functions). This
coïncidence leads one to think that there exists a universal notion of
computability, independent of particular formalisms: this is Church's
thesis. In this calculus, the only two constructions are abstraction and
application. Data structures (integers, booleans, pairs, ...) can be coded
by l-termes.
Functional languages, of which the first representative was Lisp,
implement this model and extend it mainly with more efficient data
structures. For the sake of efficiency, the first functional languages
implemented physical modifications of memory, which among other things
forced the evaluation strategy to be immediate, or strict, evaluation. In
this strategy, the arguments of functions are evaluated before being passed
to the function. It is in fact later, for other languages such as
Miranda, Haskell, or LML, that the strategy of delayed (lazy, or
call-by-need) evaluation was implemented for pure functional languages.
Static typing, with type inference, was promoted by the ML family at the
start of the 80's. The web page
Link
http://www.pps.jussieu.fr/~cousinea/Caml/caml_history.html
presents a historical overview of the ML language.
Its computation model is typed l-calculus,
a subset of l-calculus. It guarantees that no
type error will occur during program execution.
Nevertheless ``completely correct'' programs can be rejected by ML's type
system. These cases seldom arise and these programs can always be
rewritten in such a way as to conform to the type system.
The two most-used functional languages are Lisp and ML,
representatives of impure functional languages. To deepen the functional
approach to programming, the books [ASS96] and
[CM98]
each present a general programming course using the languages
Scheme (a dialect of Lisp) and Caml-Light, respectively.