<div><span class="gmail_quote">On 12/26/07, <b class="gmail_sendername">Cristian Baboi</b> <<a onclick="return top.js.OpenExtLink(window,event,this)" href="mailto:cristian.baboi@gmail.com" target="_blank">cristian.baboi@gmail.com
</a>> wrote:</span>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">The reason I want to build functions of type String -> (a -> b) is because<br>I want to see how far I can get with "functions are first class citizens"
<br>in Haskell. I thought that if I read the function from an external source,<br>there is no way the compiler could know what I'll read. I want to see if I<br>can build a Haskell function at runtime, not a data structure that I can
<br>interpret.</blockquote>
<div> </div>
<div>Those two questions are intimately related, though. Consider the following simple program:</div>
<div> </div>
<div>> {-# LANGUAGE GADTs #-}</div>
<div>> module Compile where</div>
<div>></div>
<div>> data Term a where</div>
<div>> App :: Term (a -> b) -> Term a -> Term b</div>
<div>> Prim :: a -> Term a</div>
<div> </div>
<div>Implementation of lambda-abstractions is left as an exercise for the reader.</div>
<div> </div>
<div>> compile :: Term a -> a</div>
<div>
<div>> compile (Prim x) = x</div>> compile (App x y) = compile x $ compile y</div>
<div> </div>
<div>
<div>While "compile" looks like an interpreter (and it is), there is no reason why "a" has to be a concrete data type; it could be a function type, as demonstrated here:</div>
<div> </div></div>
<div>> uncompiled_func :: Term (Int -> Int)</div>
<div>> uncompiled_func = App (Prim (+)) (Prim 1)</div>
<div>></div>
<div>> compiled_func :: Int -> Int</div>
<div>> compiled_func = compile uncompiled_func</div>
<div> </div>
<div>The first time you evaluate "compiled_func", you'll run the "compiler" which will create a function for you. Consider the lazy evaluation order of this program:</div>
<div> </div>
<div>> result :: Int</div>
<div>> result = compiled_func 3 + compiled_func 4</div>
<div> </div>
<div>I'll use "let" to represent sharing and "plus#" to represent the primitive operation of adding two numbers which (+) is defined in terms of.</div>
<div>That is, (+) = \x y -> plus# x y</div>
<div> </div>
<div>result</div>
<div>=> compiled_func 3 + compiled_func 4</div>
<div>=> (\x y -> plus# x y) (compiled_func 3) (compiled_func 4)</div>
<div>=> plus# (compiled_func 3) (compiled_func 4)</div>
<div>=> let compiled_func = compile uncompiled_func in plus# (compiled_func 3) (compiled_func 4)</div>
<div> (evaluating compiled_func)</div>
<div> compile (App (Prim (+)) (Prim 1))</div>
<div> => compile (Prim (+)) (compile (Prim 1))</div>
<div> => (+) (compile (Prim 1))</div>
<div> => (\x y -> plus# x y) (compile (Prim 1))</div>
<div> => (\y -> plus# (compile (Prim 1)) y)</div>
<div> which is WHNF</div>
<div>=> let compiled_func = (\y -> plus# (compile (Prim 1)) y) in plus# (compiled_func 3) (compiled_func 4)</div>
<div>=> let inner = (compile (Prim 1)); compiled_func = \y -> plus# inner y in plus# (compiled_func 3) (compiled_func 4)</div>
<div>
<div>=> let inner = (compile (Prim 1)) in plus# (plus# inner 3) ((\y -> plus# inner y) 4)</div>=> let inner = 1 in plus# (plus# inner 3) ((\y -> plus# inner y) 4)</div>
<div>=> plus# 4 ((\y -> plus# 1 y) 4)</div>
<div>=> plus# 4 (plus# 1 4)</div>
<div>=> plus# 4 5</div>
<div>=> 9</div>
<div> </div>
<div>Note that "compile" only gets run once on each subexpression; the end result is that you end up with a regular Haskell function which does no interpretation at all!</div>
<div> </div>
<div>All that remains is creation of something of type "Term a" from an untyped representation. Oleg's done the work here and you can see a full implementation in this message:</div><a href="http://www.haskell.org/pipermail/haskell-cafe/2007-October/032591.html">
http://www.haskell.org/pipermail/haskell-cafe/2007-October/032591.html</a>
<div> </div>
<div> -- ryan</div></div>