constant applicative form
(foldoc) | constant applicative form
CAF
(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)
|