freesect-0.6: Doc/index.html
<html>
<head>
<title>Free Sections : A Haskell Syntax Extension</title>
<!--LINK HREF="base.css" REL="stylesheet" TYPE="text/css"-->
<style type="text/css">/*<![CDATA[*/
body { font-family: "Ariel"; font-size: 17; }
h2 {
color: #222;
font-size: 16pt;
margin-top: 24px;
margin-bottom: 16px;
}
pre, pre2 {
font-weight: bold;
}
pre2, pre3 {
font-family: "Courier New";
padding: 0 0 0 0;
margin: 0 0 0 0;
border: 0 0 0 0;
}
pre4 {
font-family: "Courier New";
font-size: 12pt;
padding: 0 0 0 0;
margin: 0 0 0 0;
border: 0 0 0 0;
}
pre.showhide2 {
font-family: "Courier New";
padding: 0 0 0 0;
margin: 0 0 0 0;
border: 0 0 0 0;
}
pre.showhide3 {
font-family: "Courier New";
padding: 0 0 0 0;
margin: 0 0 0 0;
border: 0 0 0 0;
}
pre.showhide4 {
font-family: "Courier New";
padding: 0 0 0 0;
margin: 0 0 0 0;
border: 0 0 0 0;
}
A:link { font-weight: bold; color: #27e; text-decoration: none; }
A:visited { font-weight: bold; color: #14a; text-decoration: none; }
A:hover { font-weight: bold; color: #795; text-decoration: none; }
/*]]>*/
</style>
<script type="text/javascript">
function collapse(button,cls)
{
var goodies = document.querySelectorAll(cls);
for( var i=0;i<goodies.length;i++ ){
n = goodies[i].style;
if( n.display == "none" ){
n.display = "block";
}else{
n.display = "none";
}
}
}
</script>
</head>
<body>
<p>
<h1 style="font-size: 22pt; margin-bottom: 0;">Free Sections</h1>
<h3 style="margin-top: 10px; margin-bottom: 0;">Haskell Syntax Extension</h3>
<h5 style="margin-top: 10px; margin-bottom: 28px;">by Andrew Seniuk</h5>
<div style="color: #B52; font-size: 9pt; font-weight: bold; margin-left: 20px; margin-right: 20%; margin-bottom: 15px; margin-top: 10px;">The reader is strongly encouraged to navigate to <a href="http://www.fremissant.net/freesect">fremissant.net/freesect</a> as these documents are currently experiencing rapid growth and refinement. The local files represent the best documentation available at packaging of this v.0.0.5 source distribution (March 11, 2012).</div>
<i>Free sections</i> are syntactic sugar to extend the usual notion of
"section" in functional programming.
Recall that a section is just a function which has been applied to some
but not all of its arguments.
Unless the function is modified, arguments must be supplied in the
lexical order determined by the function binding's parameters.
For instance, <pre2>f 4 True</pre2> is partially applied, but is still a function type and can absorb two more arguments of types <pre2>Char</pre2> and <pre2>Float</pre2>, in that order.
<pre> f :: Int -> Bool -> Char -> Float -> String
f 4 True -- Char -> Float -> String
</pre>
By using wildcard symbols (<pre2>__</pre2>, a
double-underscore), any subset of values occurring in a RHS context can
be deferred, in the same spirit as partial function application.
Special brackets (<pre2>_[…]_</pre2>) are used to delimit
the lexical extent (or context) of the section, although these can
sometimes be omitted (details below).
The free section is then a function with arity at least equal to the
number of wildcards, and behaves as if a helper function had been
defined which shuffled the argument order of the functional expression,
turning it into a normal section.
<p>
Philosophically, use of this sort of syntax promotes "higher-order programming", since any expression can so easily be made into a function, in numerous ways, simply by replacing parts of it with freesect wildcards.
That this is worthwhile is demonstrated by the frequent usefulness of sections.
<p>
Some examples, including illustrations of context inferencing:
<ul id="examples">
<li><pre2>_[ __ ]_ <=> ( __ ) <=> id</pre2></li>
<li><pre2>map _[ (+) __ 2 ]_ [1,2,3] => [3,4,5]</pre2></li>
<li><pre2>map ( (+) __ 2 ) [1,2,3] => [3,4,5]</pre2></li>
<li><pre2>zipWith $ f __ $ g __ z <=> zipWith _[ f __ $ g __ z ]_</pre2></li>
</ul>
<p>
For a more complex example, consider a situation where some API provides you with the dreaded <pre2>dreadme</pre2> function, which you have need of using.
The example is designed to show that you can really put the <pre2>__</pre2>'s anywhere on a RHS that an expression can go.
<pre> {-# LANGUAGE FreeSections #-} -- use "{- #" if compiling with ghc -F
tableA = [ [1,2,3], [4,5], [6,7,8,9] ]
tableB = [ [9,8,7], [6,5], [4,3,2,1] ]
data D a = D Int [a]
v = map3 _[ dreadme tableA __ (repeat True,__) (D __ [(+),(*)]) ]_
[tableA,tableB]
[0..]
[-1,1]
</pre>
FreeSect rewrites the RHS of <pre2>v</pre2> (where <pre2>fs0…fs2</pre2> must be fresh identifiers) to:
<pre> v = map3 (\ fs0 fs1 fs2 -> dreadme tableA fs0 (repeat True,fs1) (D fs2 [(+),(*)]) )
[tableA,tableB]
[0..]
[-1,1]
</pre>
(Here is <a id="collapsed1" href="#collapsed1" onclick="collapse(this,'.showhide1');">the rest</a> of the code to make a closed module.)
<pre class="showhide1" style="display: none;"> dreadme :: [[Int]] -> [[Int]] -> ([Bool],Int) -> D (Int->Int->Int) -> String
dreadme tabA tabB (ps,q) (D wt flst)
= show $ map (!!q) $ map2 f tabA tabB
where f rowA rowB = map2 (<) (repeat rowA)
$ map2' (filter' ps flst) rowB (map ((q+).(wt*)) rowB)
(<a id="collapsed2" href="#collapsed2" onclick="collapse(this,'.showhide2'); collapse(this,'.showhide3');">base cases</a>)<pre class="showhide2" style="display: block;"> filter' :: [Bool] -> [a] -> [a]
filter' (p:ps) (x:xs) = if p then x:filter' ps xs
else filter' ps xs
map2 :: (a->b->c) -> [a] -> [b] -> [c]
map2 f (x:xs) (y:ys) = (f x y) : map2 f xs ys
map2' :: [a->a->a] -> [a] -> [a] -> [[a]]
map2' (f:fs) xs ys = (map2 f xs ys) : map2' fs xs ys
map3 :: (a->b->c->d) -> [a] -> [b] -> [c] -> [d]
map3 f (x:xs) (y:ys) (z:zs) = (f x y z) : map3 f xs ys zs
</pre><pre class="showhide3" style="display: none;"> filter' :: [Bool] -> [a] -> [a]
filter' (p:ps) (x:xs) = if p then x:filter' ps xs
else filter' ps xs
map2 :: (a->b->c) -> [a] -> [b] -> [c]
map2 f _ [] = []
map2 f [] _ = []
map2 f (x:xs) (y:ys) = (f x y) : map2 f xs ys
map2' :: [a->a->a] -> [a] -> [a] -> [[a]]
map2' [] _ _ = []
map2' _ [] _ = []
map2' _ _ [] = []
map2' (f:fs) xs ys = (map2 f xs ys) : map2' fs xs ys
map3 :: (a->b->c->d) -> [a] -> [b] -> [c] -> [d]
map3 f _ _ [] = []
map3 f _ [] _ = []
map3 f [] _ _ = []
map3 f (x:xs) (y:ys) (z:zs) = (f x y z) : map3 f xs ys zs
main = print v
</pre></pre>
<h2>Some virtues of the new syntax</h2>
Although the rewrite provided by the extension is simple, there are
advantages of free sections relative to explicitly written lambdas:
<ul>
<li>the lambda forces the programmer to invent names for the wildcards</li>
<li>the lambda forces the programmer to repeat those names, and place them correctly</li>
<li>freesect wildcards stand out vividly, indicating where the awaited expressions will go</li>
<li>reading the lambda requires visual pattern-matching between left and right sides of the lambda
</li><li>the lambda is longer overall, and prefaces the expression of interest with something like micro-boilerplate</li>
</ul>
On the other hand, the lambda is more powerful and can achieve arbitrary permutations without further ado.
<h2>Implementation</h2>
The <a href="http://fremissant.net/freesect/freesect-0.0.5.tar.gz">implementation</a> seems to be working.
The <pre2>freesect</pre2> package can also be installed from <a href="http://hackage.haskell.org/package/freesect">Hackage</a>, for instance using <pre2>cabal-install</pre2>.
I offer fair warning that I'm <i>not</i> a good Haskell coder, but this does demonstrate how a person of modest abilities can use <a href="http://hackage.haskell.org/package/syb">SYB</a> with <a href="http://hackage.haskell.org/package/haskell-src-exts">HSE</a> to create a robust Haskell syntax extension.
<h2>Default context inferencing</h2>
A default context is automatically applied when the <pre2>_[…]_</pre2> grouping syntax is omitted.
Defining this default can be tricky, and a bit arbitrary, so for robust code it's best to use explicit bracketing.
As of v.0.0.5, when the <pre2>_[…]_</pre2> are omitted, the defaulting rules are as follows:
The semilattice join of all unbacketed wildcards in a RHS are given context of the innermost enclosing parentheses or infix <pre2>$</pre2> operation.
If no such parentheses or infix <pre2>$</pre2> are present, the whole RHS becomes the default context.
Some of the examples at the top of the page demonstrate these rules.
One hopes that the default will result in a type error, should the inferred context differ from the intended.
I haven't thought of any situation where more than one bracketing of freesect wildcards yield typeable expressions, but neither have I ruled it out.
A context inference policy based on typeability tests among various possible scopes would also be possible...
<h2>Background</h2>
There was <a href="http://fremissant.net/freesect/irc.html">discussion</a>
about this on the <pre4>#haskell</pre4> IRC channel.
Strangely, <pre4><eyebloom></pre4> suggested the same thing an hour after I had started making inquiries about how to go about writing an extension -- and this is the one I had in mind.
It's an extraordinary coincidence, as I first sketched the idea in 2003, and had never seen it mentioned <i>per se</i>, beyond discussions of point-free and the like.
(Despite <pre4><eyebloom></pre4> asking to be contacted if I wanted to work on this, my email was never answered; I didn't run off with their idea!)
The principal example from that chat is described here.
<br />
<pre style="font-weight: normal;">
<dolio> map (foo (g _) x) (h _)
<dolio> Matter of fact, what does "map (foo (g _) x) (h _)" mean?
</pre>
Given the present context inferencing policy,
<pre>
(map (foo (g _) x) (h _)) => \ y z -> map (foo (g y) x) (h z)
</pre>
The outer parentheses might be necessary, depending on the larger context of the expression.
This interpretation might not be what the programmer intended, in which case at least a <pre2>$</pre2> is needed
<pre>
(map $ (foo (g __) x) (h __)) => map ( \ y z -> (foo (g y) x) (h z) )
</pre>
Finally, if two separate free sections were intended, the programmer would need to use <pre2>_[…]_</pre2> bracketing for at least one of them
<pre>
map _[foo (g __) x]_ _[h __]_
<=> map (foo (g __) x) _[h __]_
<=> map _[foo (g __) x]_ (h __)
<=> (map _[foo (g __) x]_ $ h __)
</pre>
all of which are rewritten by FreeSect to
<pre>
map (\y->foo (g y) x) (\z->h z)
</pre>
This interpretation cannot by typed, since the second argument of <pre2>map</pre2> must be have kind <pre2>*</pre2>, while <pre2>\z->h z</pre2> has kind <pre2>*->*</pre2>.
<h2>Other details</h2>
Nested free sections work correctly, thanks to bottom-up traversal.
Note that, as wildcards are syntactically indistinguishable, it is impossible for an enclosing freesect to have a wildcard inside any enclosed freesect.
<p>
Fresh identifiers generated by FreeSect are guaranteed to be unique among names referenced within a module.
There is no danger of exporting these names inadvertently, as they never have top-level scope.
Imported names which are in scope but never used will not incur conflicts.
<p>
A few things don't work quite right yet.
Guarded RHS's are not yet handled.
Default free section contexts in <pre2>let</pre2> expressions need to be parenthesised.
Work continues...
<h2>How to run it</h2>
The extension runs as a preprocessor.
This can be done with or without the knowledge of GHC.
If you use <pre2>ghc -F</pre2> (see scripts in the download), then unfortunately GHC checks language pragmas before preprocessing, which means you cannot declare <pre2>{-# LANGUAGE FreeSections #-}</pre2> at the top.
Although the patched HSE is capable of rejecting source which uses free sections without the pragma, this feature is disabled for interoperability with GHC.
All compilers are supported by running FreeSect as an independent preprocessor, but there are some inconveniences involving temporary files.
<h2>Feedback</h2>
Please provide feedback on the FreeSect <a href="http://www.mail-archive.com/haskell-cafe@haskell.org/msg97643.html">haskell-cafe</a> mailing list thread.
<p>
<div style="margin-top: 30px;">Kind Reg'ds,</div>
<div style="margin-top: 10px;">Andrew Seniuk</div>
<div style="font-family: Courier New; font-size: 8pt; font-weight: bold; margin-top: 0px;"><rasfar> on #haskell</div>
<div style="font-size: 8pt; margin-top: 8px;"> Feb. 29, 2012</div>
<br />
<br />
</body></html>