title: Evolving data structure
body: <p>I'm trying to write a compiler for a C-like language in Haskell.  The compiler progresses by transforming an AST.  The first pass parses the input to create the AST, tying a knot with the symbol table to allow symbols to be located before they have been defined without the need for forward references.</p>
  
  <p>The AST contains information about types and expressions, and there can be connections between them; e.g. <code>sizeof(T)</code> is an expression that depends on a type <code>T</code>, and <code>T[e]</code> is an array type that depends on a constant expression <code>e</code>.</p>
  
  <p>Types and expressions are represented by Haskell data types like so:</p>
  
  <pre><code>data Type = TypeInt Id
            | TypePointer Id Type -- target type
            | TypeArray Id Type Expr -- elt type, elt count
            | TypeStruct Id [(String, Type)] -- [(field name, field type)]
            | TypeOf Id Expr
            | TypeDef Id Type
  
  data Expr = ExprInt Int -- literal int
            | ExprVar Var -- variable
            | ExprSizeof Type
            | ExprUnop Unop Expr
            | ExprBinop Binop Expr Expr
            | ExprField Bool Expr String -- Bool gives true=&gt;s.field, false=&gt;p-&gt;field
  </code></pre>
  
  <p>Where <code>Unop</code> includes operators like address-of (<code>&amp;</code>), and dereference (<code>*</code>), and <code>Binop</code> includes operators like plus (<code>+</code>), and times (<code>*</code>), etc...</p>
  
  <p>Note that each type is assigned a unique <code>Id</code>.  This is used to construct a type dependency graph in order to detect cycles which lead to infinite types.  Once we are sure that there are no cycles in the type graph, it is safe to apply recursive functions over them without getting into an infinite loop.</p>
  
  <p>The next step is to determine the size of each type, assign offsets to struct fields, and replace <code>ExprField</code>s with pointer arithmetic.  In doing so, we can determine the type of expressions, and eliminate <code>ExprSizeof</code>s, <code>ExprField</code>s, <code>TypeDef</code>s, and <code>TypeOf</code>s from the type graph, so our types and expressions have evolved, and now look more like this:</p>
  
  <pre><code>data Type' = TypeInt Id
             | TypePointer Id Type'
             | TypeArray Id Type' Int -- constant expression has been eval'd
             | TypeStruct Id [(String, Int, Type')] -- field offset has been determined
  
  data Expr' = ExprInt Type' Int
             | ExprVar Type' Var
             | ExprUnop Type' Unop Expr'
             | ExprBinop Type' Binop Expr' Expr'
  </code></pre>
  
  <p>Note that we've eliminated some of the data constructors, and slightly changed some of the others.  In particular, <code>Type'</code> no longer contains any <code>Expr'</code>, and every <code>Expr'</code> has determined its <code>Type'</code>.</p>
  
  <p>So, finally, the question: Is it better to create two almost identical sets of data types, or try to unify them into a single data type?</p>
  
  <p>Keeping two separate data types makes it explicit that certain constructors can no longer appear.  However, the function which performs constant folding to evaluate constant expressions will have type:</p>
  
  <pre><code>foldConstants :: Expr -&gt; Either String Expr'
  </code></pre>
  
  <p>But this means that we cannot perform constant folding later on with <code>Expr'</code>s (imagine some pass that manipulates an <code>Expr'</code>, and wants to fold any emerged constant expressions).  We would need another implementation:</p>
  
  <pre><code>foldConstants' :: Expr' -&gt; Either String Expr'
  </code></pre>
  
  <p>On the other hand, keeping a single type would solve the constant folding problem, but would prevent the type checker from enforcing static invariants.</p>
  
  <p>Furthermore, what do we put into the unknown fields (like field offsets, array sizes, and expression types) during the first pass?  We could plug the holes with <code>undefined</code>, or <code>error "*hole*"</code>, but that feels like a disaster waiting to happen (like <code>NULL</code> pointers that you can't even check).  We could change the unknown fields into <code>Maybe</code>s, and plug the holes with <code>Nothing</code> (like <code>NULL</code> pointers that we <em>can</em> check), but it would be annoying in subsequent passes to have to keep pulling values out of <code>Maybe</code>s that are always going to be <code>Just</code>s.</p>