constant applicative form

(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 garbagecollector 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)