title: Differences between HOAS and FOAS
body: <p>In trying to decide if a EDSL is prudent for my project, I read <a href="http://www.cse.chalmers.se/~josefs/publications/TFP12.pdf">this paper</a> and <a href="http://www.cse.chalmers.se/~josefs/publications/haskell2013.pdf">this paper</a>, describing the implementation of meta-repa. They both mention HOAS and FOAS. From the first paper, </p>
  
  
  
  <blockquote>
  <pre class="lang-hs prettyprint-override"><code> data FunC a where
    LitI :: Int -&gt; FunC Int
    LitB :: Bool -&gt; FunC Bool
    If :: FunC Bool -&gt; FunC a -&gt; FunC a -&gt; FunC a
    While :: (FunC s -&gt; s -&gt; FunC Bool) -&gt; (FunC s -&gt; FunC s) 
                  -&gt; FunC s -&gt; FunC s
    Pair :: FunC a -&gt; FunC b -&gt; FunC (a, b)
    Fst :: FunC (a, b) -&gt; FunC a
    Snd :: FunC (a, b) -&gt; FunC b
    Prim1 :: String -&gt; (a -&gt; b) -&gt; FunC a -&gt; FunC b
    Prim2 :: String -&gt; (a -&gt; b -&gt; c) -&gt; FunC a -&gt; FunC b -&gt; FunC c
    Value :: a -&gt; FunC a
    Variable :: String -&gt; FunC a
  </code></pre>
    
    <p>We have also chosen Higher Order Abstract Syntax to represent
    constructs with variable binding. In the above data type, the only
    higher-order construct is <code>While</code>.</p>
  </blockquote>
  
  <p>What about the <code>While</code> constructor makes it HOAS? Why are none of the other constructors HOAS?</p>
  
  <p>In the second paper, <a href="https://github.com/jankner/meta-repa">meta-repa code</a> is written in a HOAS tree, then transformed (at compile-time) to a FOAS for further processing. Again, I don't understand what makes the data defined in HOAS.hs HOAS while the data defined in FOASTyped is FOAS. The mysterious quote from that paper is:</p>
  
  <blockquote>
    <p>The type <code>Expr</code> [in HOAS.hs] uses higher order abstract syntax to represent programs.
    This representation is convenient for programming with but somewhat
    less ideal for rewriting programs. The AST is therefore converted into
    a first order representation[.] A
    possible implementation would have been to skip the [HOAS] <code>Expr</code> type and
    generate the ﬁrst order representation directly. We have kept the
    higher order representation partly because it helps maintain the type
    safety of the implementation and partly because it allows us to write
    a well typed, tagless interpreter.</p>
  </blockquote>
  
  <p>Is there some general way in which HOAS is more difficult to transform than FOAS? How does HOAS help with type safety compared to FOAS?</p>
  
  <p>I've read the Wikipedia article on FOAS and HOAS, but that didn't clear anything up for me. </p>
  
  <p>Wikipedia suggests that HOAS is useful in languages with <em>variable binders</em> (also mentioned in the first quote). What is a variable binder, how does Haskell implement it, and what languages don't have variable binders?</p>