https://wiki.haskell.org/index.php?title=Constant_applicative_form&feed=atom&action=historyConstant applicative form - Revision history2024-03-19T12:59:26ZRevision history for this page on the wikiMediaWiki 1.35.5https://wiki.haskell.org/index.php?title=Constant_applicative_form&diff=66328&oldid=prevAtravers: Old HaWiki Q&A content transferred to ":Talk"2023-06-12T06:31:23Z<p>Old HaWiki Q&A content transferred to ":Talk"</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 06:31, 12 June 2023</td>
</tr><tr>
<td colspan="2" class="diff-lineno">Line 17:</td>
<td colspan="2" class="diff-lineno">Line 17:</td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>===Q&A discussion from HaWiki===</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>:''What is the difference between ''<hask>((+) 4)</hask>'' and ''<hask>\x -> (+) 4 x</hask>'', apart from the obvious difference in notation? (I have braced the + to make the expressions compliant with Haskell syntax.)''</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>::One is an application that returns a function and may imply some work in general, the other is a syntactic value (a lambda abstraction).</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>:''If notation really happens to matter so much, then what about ''<hask>(4 +)</hask>'' and ''<hask>(+ 4)</hask>''? Are '''both''' of these CAFs? If we take away the nifty syntax, how do we express ''<hask>(+ 4)</hask>'' then? Or is it no longer a CAF? ;)''</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>::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</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>:::''--- Rambler'' ''I'm afraid I still don't get it (or maybe I do, but I secretly wish it didn't mean '''that'''...) To the best of my understanding of the matter, `flip (+) 4` should return something that should behave exactly as `\x -> x + 4` would. Moreover, even if I take it for granted that `flip (+) 4` differs dramatically from `\x -> x + 4`, what happens when we expand the former?</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>:::'''''There is no difference in ''behavior'' as far as meaning is concerned. They are just treated differently. -- DerekElkins'''''</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>:::Suppose `flip` is defined as `\f x y -> f y x` (which it probably is, anyway,) then `flip (+) 4 where flip = \f x y -> f y x` is obviously not a CAF, according to the definition.</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>:::What about `flip (+) 4 where flip f x y = f y x`???''</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>::::''I believe that FOLDOC is incorrect here. A better way of thinking about CAFs is that a CAF is anything that can be let floated (see [[lifting pattern]]) to the top level. So a CAF can not only call other CAFs, but also other [[super combinator]]s.''</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>:::::I believe that's already granted, according to the definition of a [[super combinator]]. A CAF may reference any [[super combinator]] simply by virtue of being one.</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>::::''The difference between <hask>flip (+) 4</hask> and <hask>\x -> x + 4</hask> is that in a pure lambda calculus implementation, the former can be reduced but the latter cannot. Remember that <hask>\f x y -> f y x</hask> is a shorthand for <hask>\f -> (\x -> (\y -> f y x)))</hask>, which means if given two arguments, it can be reduced. --AndrewBromage''</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>:::::Fine, is it then irreducibility that makes CAFs special? If so, then the current formulation of the definition clearly misses the point. If not, then why is this distinction relevant in the context of the definition?</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>:::::In any case, I am left wondering 1) why irreducible expressions might be of such interest (apart from the trivially imaginable,) and 2) whatever happened to the proverbial [[referential transparency]]. It just struck me lately that my difficulty may be due to the fact that I am trying to make sense of CAFs in a broad theoretical context, whereas they may be simply an implementation instrument -- is this the case? --Rambler</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>:'''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'''</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>::''OK, it definitely makes sense now, thanks to everyone for the explanations and references. --Rambler''</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==See also==</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==See also==</div></td>
</tr>
</table>Atravershttps://wiki.haskell.org/index.php?title=Constant_applicative_form&diff=65279&oldid=prevAtravers at 08:51, 10 August 20222022-08-10T08:51:26Z<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 08:51, 10 August 2022</td>
</tr><tr>
<td colspan="2" class="diff-lineno">Line 43:</td>
<td colspan="2" class="diff-lineno">Line 43:</td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==See also==</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==See also==</div></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Simon Peyton Jones' [<del class="diffchange diffchange-inline">http</del>://<del class="diffchange diffchange-inline">research</del>.<del class="diffchange diffchange-inline">microsoft</del>.<del class="diffchange diffchange-inline">com</del>/<del class="diffchange diffchange-inline">%7Esimonpj</del>/<del class="diffchange diffchange-inline">papers/slpj</del>-<del class="diffchange diffchange-inline">book</del>-<del class="diffchange diffchange-inline">1987/index.htm</del> Implementation of Functional Programming Languages] for more about this and related terms.</div></td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Simon Peyton Jones' [<ins class="diffchange diffchange-inline">https</ins>://<ins class="diffchange diffchange-inline">simon</ins>.<ins class="diffchange diffchange-inline">peytonjones</ins>.<ins class="diffchange diffchange-inline">org</ins>/<ins class="diffchange diffchange-inline">publications-1980</ins>/<ins class="diffchange diffchange-inline">#the</ins>-<ins class="diffchange diffchange-inline">implementation</ins>-<ins class="diffchange diffchange-inline">of-functional-programming-languages</ins> Implementation of Functional Programming Languages] for more about this and related terms.</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* [[Memoization#Memoising_CAFS|Memoising constant applicative forms]]</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* [[Memoization#Memoising_CAFS|Memoising constant applicative forms]]</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Glossary]]</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Glossary]]</div></td>
</tr>
</table>Atravershttps://wiki.haskell.org/index.php?title=Constant_applicative_form&diff=55632&oldid=prevHowardBGolden: Add link to Memoization#Memoising_CAFS2013-04-01T22:40:28Z<p>Add link to <a href="/Memoization#Memoising_CAFS" title="Memoization">Memoization#Memoising_CAFS</a></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 22:40, 1 April 2013</td>
</tr><tr>
<td colspan="2" class="diff-lineno">Line 44:</td>
<td colspan="2" class="diff-lineno">Line 44:</td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==See also==</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==See also==</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* Simon Peyton Jones' [http://research.microsoft.com/%7Esimonpj/papers/slpj-book-1987/index.htm Implementation of Functional Programming Languages] for more about this and related terms.</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* Simon Peyton Jones' [http://research.microsoft.com/%7Esimonpj/papers/slpj-book-1987/index.htm Implementation of Functional Programming Languages] for more about this and related terms.</div></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* [[Memoising constant applicative forms]]</div></td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* [[<ins class="diffchange diffchange-inline">Memoization#Memoising_CAFS|</ins>Memoising constant applicative forms]]</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Glossary]]</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Glossary]]</div></td>
</tr>
</table>HowardBGoldenhttps://wiki.haskell.org/index.php?title=Constant_applicative_form&diff=24524&oldid=prevAndrewBromage: Syntax fixen2008-12-06T01:27:41Z<p>Syntax fixen</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 01:27, 6 December 2008</td>
</tr><tr>
<td colspan="2" class="diff-lineno">Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Also referred to as CAF.</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Also referred to as CAF.</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Any [[super combinator]] which is not a [[lambda abstraction]]. This includes truly constant expressions such as <hask>12, <ins class="diffchange diffchange-inline">(</ins>(+<ins class="diffchange diffchange-inline">)</ins> 1 2), [1,2,3]</hask> as well as partially applied functions such as <hask><ins class="diffchange diffchange-inline">(</ins>(+<ins class="diffchange diffchange-inline">)</ins> 4)</hask>. Note that this last example is equivalent under eta abstraction to <hask>\ x -> <ins class="diffchange diffchange-inline">(</ins>+<ins class="diffchange diffchange-inline">)</ins> 4 x</hask> which is not a CAF.</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Examples and discussions==</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Examples and discussions==</div></td>
</tr>
<tr>
<td colspan="2" class="diff-lineno">Line 7:</td>
<td colspan="2" class="diff-lineno">Line 7:</td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><haskell></div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><haskell></div></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>c 3 where c = (* 2<del class="diffchange diffchange-inline">).</del></div></td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>c 3 where c = (*<ins class="diffchange diffchange-inline">)</ins> 2</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></haskell></div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></haskell></div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
</table>AndrewBromagehttps://wiki.haskell.org/index.php?title=Constant_applicative_form&diff=6908&oldid=prevBrettGiles: HaWiki conversion2006-10-12T01:33:03Z<p>HaWiki conversion</p>
<p><b>New page</b></p><div>Also referred to as CAF.<br />
<br />
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.<br />
<br />
==Examples and discussions==<br />
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.<br />
<br />
<haskell><br />
c 3 where c = (* 2).<br />
</haskell><br />
<br />
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<br />
<br />
<haskell><br />
ints = from 1 where from n = n : from (n+1)<br />
</haskell><br />
<br />
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.<br />
<br />
<br />
<br />
===Q&A discussion from HaWiki===<br />
:''What is the difference between ''<hask>((+) 4)</hask>'' and ''<hask>\x -> (+) 4 x</hask>'', apart from the obvious difference in notation? (I have braced the + to make the expressions compliant with Haskell syntax.)''<br />
::One is an application that returns a function and may imply some work in general, the other is a syntactic value (a lambda abstraction).<br />
<br />
:''If notation really happens to matter so much, then what about ''<hask>(4 +)</hask>'' and ''<hask>(+ 4)</hask>''? Are '''both''' of these CAFs? If we take away the nifty syntax, how do we express ''<hask>(+ 4)</hask>'' then? Or is it no longer a CAF? ;)''<br />
<br />
::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<br />
<br />
:::''--- Rambler'' ''I'm afraid I still don't get it (or maybe I do, but I secretly wish it didn't mean '''that'''...) To the best of my understanding of the matter, `flip (+) 4` should return something that should behave exactly as `\x -> x + 4` would. Moreover, even if I take it for granted that `flip (+) 4` differs dramatically from `\x -> x + 4`, what happens when we expand the former?<br />
:::'''''There is no difference in ''behavior'' as far as meaning is concerned. They are just treated differently. -- DerekElkins'''''<br />
:::Suppose `flip` is defined as `\f x y -> f y x` (which it probably is, anyway,) then `flip (+) 4 where flip = \f x y -> f y x` is obviously not a CAF, according to the definition.<br />
:::What about `flip (+) 4 where flip f x y = f y x`???''<br />
::::''I believe that FOLDOC is incorrect here. A better way of thinking about CAFs is that a CAF is anything that can be let floated (see [[lifting pattern]]) to the top level. So a CAF can not only call other CAFs, but also other [[super combinator]]s.''<br />
:::::I believe that's already granted, according to the definition of a [[super combinator]]. A CAF may reference any [[super combinator]] simply by virtue of being one.<br />
::::''The difference between <hask>flip (+) 4</hask> and <hask>\x -> x + 4</hask> is that in a pure lambda calculus implementation, the former can be reduced but the latter cannot. Remember that <hask>\f x y -> f y x</hask> is a shorthand for <hask>\f -> (\x -> (\y -> f y x)))</hask>, which means if given two arguments, it can be reduced. --AndrewBromage''<br />
:::::Fine, is it then irreducibility that makes CAFs special? If so, then the current formulation of the definition clearly misses the point. If not, then why is this distinction relevant in the context of the definition?<br />
:::::In any case, I am left wondering 1) why irreducible expressions might be of such interest (apart from the trivially imaginable,) and 2) whatever happened to the proverbial [[referential transparency]]. It just struck me lately that my difficulty may be due to the fact that I am trying to make sense of CAFs in a broad theoretical context, whereas they may be simply an implementation instrument -- is this the case? --Rambler<br />
<br />
:'''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'''<br />
<br />
::''OK, it definitely makes sense now, thanks to everyone for the explanations and references. --Rambler''<br />
<br />
==See also==<br />
* Simon Peyton Jones' [http://research.microsoft.com/%7Esimonpj/papers/slpj-book-1987/index.htm Implementation of Functional Programming Languages] for more about this and related terms.<br />
* [[Memoising constant applicative forms]]<br />
[[Category:Glossary]]</div>BrettGiles