View source for Constant applicative form

Also referred to as CAF.

Any  [[super combinator]] which is not a [[lambda abstraction]]. This includes truly constant expressions such as <hask>12, ((+) 1 2), [1,2,3]</hask> as well as partially applied functions such as <hask>((+) 4)</hask>. Note that this last example is equivalent under eta abstraction to <hask>\ x  -> (+) 4 x</hask> which is not a CAF.

==Examples and discussions==
Since a CAF is a [[super combinator]], it contains no [[free variable]]s. 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.

<haskell>
c 3 where c = (*) 2
</haskell>

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

<haskell>
ints = from 1  where  from n = n : from (n+1)
</haskell>

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.

==See also==
* Simon Peyton Jones' [https://simon.peytonjones.org/publications-1980/#the-implementation-of-functional-programming-languages Implementation of Functional Programming Languages] for more about this and related terms.
* [[Memoization#Memoising_CAFS|Memoising constant applicative forms]]
[[Category:Glossary]]