Constant applicative form
m (Syntax fixen)
m (Add link to Memoization#Memoising_CAFS)
Latest revision as of 22:40, 1 April 2013
Also referred to as CAF.Any super combinator which is not a lambda abstraction. This includes truly constant expressions such as
 1 Examples and discussions
Since a CAF is a super combinator, 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.
 1.1 Q&A discussion from HaWiki
- What is the difference between and((+) 4), apart from the obvious difference in notation? (I have braced the + to make the expressions compliant with Haskell syntax.)\x -> (+) 4 x
- One is an application that returns a function and may imply some work in general, the other is a syntactic value (a lambda abstraction).
- If notation really happens to matter so much, then what about and(4 +)? Are both of these CAFs? If we take away the nifty syntax, how do we express(+ 4)then? Or is it no longer a CAF? ;)(+ 4)
- It depends on how they desugar. `(4 +)` presumably desugars to `((+) 4)` and so is a CAF. If (+ 4) desugars to `\x -> x + 4` it isn't, if it desugars to `flip (+) 4` it is. -- DerekElkins
- What about `flip (+) 4 where flip f x y = f y x`???
- The difference between andflip (+) 4\x -> x + 4is a shorthand for\f x y -> f y x\f -> (\x -> (\y -> f y x)))
- You've inverted it slightly (or it reads that way): it's reducibility that makes CAFs special. Since they are reducible they may imply work; work that could be saved. Nevertheless, yes, one typically doesn't care whether something's a CAF or not as far as meaning goes. Read the relevant parts of the book I linked to below, if you haven't already. As for ReferentialTransparency, whether or not something is viewed as a CAF doesn't change it's meaning, i.e. it is just a different implementation of the same function. -- DerekElkins
- OK, it definitely makes sense now, thanks to everyone for the explanations and references. --Rambler
 2 See also
- Simon Peyton Jones' Implementation of Functional Programming Languages for more about this and related terms.
- Memoising constant applicative forms