(CAF) (Functional programming) 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. (1994-11-30)
