expander-design.md

+# Sweet.js
+
+## Core Structures
+
+The main data types are `Syntax` and `TermTree`:
+
+    Syntax :: {
+        token   :: Token,
+        context :: Context,
+        mark    :: (Int?) -> Syntax
+        rename  :: (Syntax or [Syntax], Str) -> Syntax
+        push_dummy_rename :: (Str) -> Syntax
+        swap_dummy_rename :: (Syntax, Str, Str) -> Syntax 
+    }
+
+The `Syntax` object holds the token (a holdover data structure from esprima which knows about the token's value and line numbers) and its context (a structure of marks and renames used for hygiene) along with a couple of methods to help with hygiene.
+
+Each `Syntax` object is in one-to-one correlation with an individual token.
+
+In contrast, the `TermTree` object holds a collection of of `Syntax` objects in a closer and closer approximation of the final AST.
+
+    TermTree :: {
+        destruct :: () -> [Syntax]
+    }
+
+It's basically an AST, just not as complete as the final AST generated by esprima. Productions in the grammar then are represented by individual term trees:
+
+    BinOp extends TermTree :: {
+        left    :: TermTree
+        op      :: TermTree
+        right   :: TermTree
+    }
+
+## expand
+
+The main entry point into the expander is, appropriately enough, `expand`:
+
+    expand :: ([Syntax], Map, Map) -> [TermTree]
+    function expand(toks, env, ctx) { ... }
+
+The `expand` function is primarily responsible for handling hygiene. Most of its work happens when dealing with functions (renaming all the parameters and whatnot). The `env` param is a mapping from identifiers to macro definitions and `ctx` is a mapping of names to names (used for hygiene).
+
+The `expand` function delegates to two sub expand like functions:
+
+    expandToTermTree :: ([Syntax], Map) -> {terms: [TermTree], env: Map}
+
+Responsible for converting the syntax to TermTrees and loading any macro definitions it finds into the new `env` map.
+
+    expandTermTreeToFinal :: (TermTree, Map, Map) -> TermTree
+
+Responsible for packing each term tree into its final state. This means recursively expanding sub trees and handling various hygiene tasks.
+
+These are roughly analogous to `parse1` and `parse2` in the honu paper.
+
+## enforest
+
+The `enforest` function deals with transforming `Syntax` objects to a `TermTree`:
+
+    enforest :: ([Syntax], Map) -> {
+        result  :: TermTree
+        rest    :: [Syntax] 
+    }
+
+
+# Honu
+
+The main contracts for honu:
+
+    parse    :: ([Syntax], Env)     -> AST
+    parse1   :: ([Syntax], Env)     -> ([TermTree], Env)
+    parse2   :: ([TermTree], Env)   -> AST
+
+    enforest :: ([Syntax], Env)     -> (TermTree, [Syntax])
+
+    data TermTree = Macro Str [Syntax]
+                  | Expr [TermTree]
+                  | Bop TermTree Str TermTree
+                  | Fun Str [TermTree] [Syntax]
+                  | Block [Syntax]
+                  | Id Syntax
+                  | Lit Syntax
+                  | Call [TermTree] [TermTree]
+
+Some partial pattern matching definitions in a haskelly notation:
+
+    parse :: ([Syntax], Env) -> AST
+    parse stx env = let (terms, env') = parse1 stx env 
+                    in parse2 terms env'
+
+    parse1 :: [Syntax] -> Env -> ([TermTree], Env)
+    parse1 [] env = ([], env)
+    parse1 in env = 
+        case (enforest in env) of
+            (Macro n b, rest)  -> parse1 rest (update n (loadm b))
+            (Expr e, rest)     -> (Expr e) : (parse1 rest env)
+            -- case when var declaration (somewhat complicated)
+
+    parse2 :: [TermTree] -> Env -> AST
+    parse2 forms env = map parse2' forms 
+
+    parse2' (Fun n vs b) env = FunAST n vs (parse b (aug env vs))
+    parse2' (Block b) env    = BlockAST (parse b env)
+    parse2' (Id i) env       = IdAST i
+    parse2' (Lit l) env      = LitAST l
+    parse2' (Call l r) env   = CallAST (parse2 l env) (parse2 r env) 
+    parse2' (Bop l o r) env  = BopAST (parse2 l env) o (parse2 r env) 
+
+And the `enforest` function itself:
+
+    data Syntax = LitR Int
+                | IdR Str
+                | BinopR Str
+                | ParenR [Syntax]
+                | ...
+
+    enforest :: [Syntax] -> Env -> (TermTree, [Syntax])
+
+    enforest (LitR n:rest) env = enforest (Lit n:rest) env
+    enforest (IdR i:rest) env 
+        | lookup i env == Var id  = enforest (Id id:rest) env
+        | lookup i env == Macro t = enforest (t rest) env
+    enforest (ltree:(IdR i):rest) env
+        | lookup i env == BopR op = case enforest rest env of
+            (rtree, rest) -> enforest (Bop ltree op rtree:rest) env
+    -- similar for uop
+    enforest (ltree:ParenR args:rest) 
+        | -- each arg must enforest to have no `rest`
+        = enforest (Call ltree argtrees:rest) env 
+