Constant applicative form
functional programming
(CAF) A supercombinator which is not a lambda abstraction. This includes truly constant expressions such as 12, (+ 1 2), [1, 2, 3] as well as partially applied functions such as (+ 4). Note that this last example is equivalent under eta abstraction to \ x . + 4 x which is not a CAF.
Since a CAF is a supercombinator, it contains no free variables. Moreover, since it is not a lambda abstraction it contains no variables at all. It may however contain identifiers which refer to other CAFs, e.g.
c 3 where c = (* 2).
A CAF can always be lifted to the top level of the program. It can either be compiled to a piece of graph which will be shared by all uses or to some shared code which will overwrite itself with some graph the first time it is evaluated. A CAF such as
ints = from 1 where from n = n : from (n+1)
can grow without bound but may only be accessible from within the code of one or more functions. In order for the garbage collector to be able to reclaim such structures, we associate with each function a list of the CAFs to which it refers. When garbage collecting a reference to the function we collect the CAFs on its list.
[The Implementation of Functional Programming Languages, Simon Peyton Jones (http://research.microsoft.com/%7Esimonpj/papers/slpj-book-1987/PAGES/224.HTM)].
(2006-10-12)
Read Also:
- Constant de Rebecque
[kawn-stahn duh ruh-bek] /kɔ̃ˈstɑ̃ də rəˈbɛk/ noun 1. Henri Benjamin [ahn-ree ban-zha-man] /ɑ̃ˈri bɛ̃ ʒaˈmɛ̃/ (Show IPA), (Benjamin Constant) 1767–1830, French statesman and author, born in Switzerland.
- Constant-dollar
noun 1. a dollar valued according to its purchasing power in an arbitrarily set year and then adjusted for price changes in other years so that real purchasing power can be compared by giving prices as they would presumably be in the base year.
- Constant folding
compiler A compiler optimisation technique where constant subexpressions are evaluated at compile time. This is usually only applied to built-in numerical and boolean operators whereas partial evaluation is more general in that expressions involving user-defined functions may also be evaluated at compile time. (1997-02-20)
- Constantia
[kon-stan-shuh, -shee-uh] /kɒnˈstæn ʃə, -ʃi ə/ noun 1. a female given name, form of . /kɒnˈstænʃə/ noun (South African) 1. a region of the Cape Peninsula 2. any of several red or white wines produced around Constantia
- Constantine
[kon-stuh n-teen or for 1, 3, -tahyn; for 2, 3 also French kawn-stan-teen] /ˈkɒn stənˌtin or for 1, 3, -ˌtaɪn; for 2, 3 also French kɔ̃ stɛ̃ˈtin/ noun 1. died a.d. 715, pope 708–715. 2. a city in NE Algeria. 3. a male given name. [kon-stuh n-teen, -tahyn] /ˈkɒn stənˌtin, -ˌtaɪn/ noun 1. (Flavius Valerius […]