new AST approach, testing

9 files changed, 555 insertions, 559 deletions

diff --git a/ast.moon b/ast.moon
deleted file mode 100644
index 336f463..0000000
--- a/ast.moon
+++ /dev/null
@@ -1,230 +0,0 @@
-import Const, Forward from require 'base'
-import Scope from require 'scope'
-unpack or= table.unpack
-
-hash = (tbl) ->
-  mt = getmetatable tbl
-  setmetatable tbl, nil
-  str = tostring tbl
-  setmetatable tbl, mt
-
-  '#' .. str\sub 10
-
-class ASTNode
-  -- first pass (outin):
-  -- * expand macros (mutate scopes)
-  -- * resolve symbols
-  expand: (scope) =>
-
-  -- second pass (inout):
-  -- * setup expressions (spawn/patch)
-  patch: (map) =>
-
-  -- runtime pass (inout)
-  update: (dt) =>
-
-  -- return a copy
-  clone: (tag_prefix) =>
-
-class Atom extends ASTNode
-  type: 'Atom'
-
-  new: (@raw, @atom_type) =>
-
-  unescape = (str) ->
-    str = str\gsub '\\"', '"'
-    str = str\gsub "\\'", "'"
-    str = str\gsub "\\\\", "\\"
-    str
-  expand: (scope) =>
-    @value = switch @atom_type
-      when 'num'
-        Const 'num', tonumber @raw
-      when 'strq', 'strd'
-        Const 'str', unescape @raw
-      when 'sym'
-        assert (scope\get @raw), "undefined reference to symbol '#{@raw}'"
-      else
-        error "unknown atom type: '#{@atom_type}'"
-
-    @value
-
-  expand_quoted: =>
-    switch @atom_type
-      when 'num'
-        Const 'num', tonumber @raw
-      when 'strq', 'strd'
-        Const 'str', unescape @raw
-      when 'sym'
-        Const 'sym', @raw
-      else
-        error "unknown atom type: '#{@atom_type}'"
-
-  _walk: => coroutine.yield @type, @
-
-  stringify: =>
-    switch @atom_type
-      when 'sym', 'num'
-        @raw
-      when 'strq'
-        "'#{@raw}'"
-      when 'strd'
-        "\"#{@raw}\""
-      else
-        error "unknown atom type: '#{@atom_type}'"
-
-  -- atoms are immutable
-  clone: (tag_prefix) => Atom @raw, @atom_type
-
-  @make_num:  (match) -> Atom match, 'num'
-  @make_sym:  (match) -> Atom match, 'sym'
-  @make_strd: (match) -> Atom match, 'strd'
-  @make_strq: (match) -> Atom match, 'strq'
-
-  __tostring: =>
-    "<Atom#{hash @} #{@stringify!}>"
-
-class Xpr extends ASTNode
-  type: 'Xpr'
-
-  -- either:
-  -- * style, tag, parts, white
-  -- * style, tag, parts
-  -- * style, parts
-  new: (@style, tag, parts, white) =>
-    if white
-      for i, part in ipairs parts
-        @[i] = part
-    else
-      if not parts
-        parts = tag
-        tag = nil
-
-      @white = {}
-      @white[0] = parts[1]
-
-      for i = 2,#parts,2
-        @[i/2] = parts[i]
-        @white[i/2] = parts[i+1]
-
-    @tag = tag
-
-  expand: (scope) =>
-    @[1]\expand scope
-    head = @head!
-
-    @scope = Scope @, scope
-
-    switch head.type
-      when 'macrodef'
-        Macrodef = head\getc!
-        @macro = Macrodef @
-        @value = @macro\expand scope
-      else
-        for child in *@[2,]
-          child\expand @scope
-
-    @value or Forward @
-
-  patch: (map) =>
-    L\trace "patching #{@deep_tostring!}"
-    prev = map[@tag]
-
-    if @macro
-      -- forward for macros
-      if prev and prev.macro then prev.macro\destroy!
-      elseif prev and prev.value then prev.value\destroy!
-      @macro\patch map
-      return
-
-    compatible = prev and
-                 prev.value and
-                 prev\head! == head
-
-    for child in *@
-      L\push child\patch, map
-    head = @head!
-
-    if compatible
-      -- continued existance
-      @value = prev.value
-      @value\setup @tail!
-      L\trace "continued with", @tail!
-    else
-      -- destroy + recreate
-      prev.value\destroy! if prev and prev.value
-      @value = head\getc!\spawn @tail!
-      L\trace "recreated with", @tail!
-
-  update: (dt) =>
-    if @macro
-      @macro\update dt
-      return
-
-    L\trace "updating #{@}"
-    for child in *@[2,]
-      L\push child\update, dt
-
-    @value\update dt
-
-  head: => @[1].value
-  tail: => unpack [p.value for p in *@[2,]]
-
-  _walk: (dir, yield_self=true) =>
-    coroutine.yield @type, @ if yield_self and dir == 'outin'
-
-    for frag in *@
-      frag\_walk dir
-
-    coroutine.yield @type, @ if yield_self and dir == 'inout'
-
-  walk: (dir, yield_self=true) =>
-    assert dir == 'inout' or dir == 'outin', "dir has to be either inout or outin"
-    coroutine.wrap -> @_walk dir, yield_self
-
-  stringify: =>
-    buf = ''
-    buf ..= @white[0]
-    for i, frag in ipairs @
-      buf ..= frag\stringify!
-      buf ..= @white[i]
-
-    switch @style
-      when 'naked'
-        buf
-      when '('
-        tag = if @tag then "[#{@tag}]" else ''
-        '(' .. tag .. buf .. ')'
-      else
-        error "unknown sexpr style: '#{@style}'"
-
-  clone: (tag_prefix) =>
-    parts = [part\clone tag_prefix for part in *@]
-    Xpr @style, "#{tag_prefix}.#{@tag}", parts, @white
-
-  make_sexpr: (...) -> Xpr '(', ...
-  make_nexpr: (...) -> Xpr 'naked', ...
-
-  deep_tostring: =>
-    buf = "("
-    buf ..= "[#{@tag}]" if @tag
-    buf ..= "#{@[1].raw}"
-    buf ..= " #{table.concat [tostring child for child in *@], ' '}" if #@ > 1
-    buf ..= ")"
-    buf
-
-  __tostring: =>
-    if @style == 'naked'
-      return 'ROOT'
-
-    buf = "("
-    buf ..= "[#{@tag}]" if @tag
-    buf ..= "#{@[1].raw}"
-    buf ..= " ..." if #@ > 1
-    buf ..= ")"
-    buf
-
-{
-  :Atom
-  :Xpr
-}
diff --git a/base.moon b/base.moon
index cdc80e6..b623b7b 100644
--- a/base.moon
+++ b/base.moon
@@ -1,76 +1,79 @@
-import is_object from require 'moon'
 import Scope from require 'scope'
 
+unpack or= table.unpack
+
+ancestor = (klass) ->
+  assert klass, "cant find the ancestor of nil"
+  while klass.__parent
+    klass = klass.__parent
+  klass
+
 class Op
+-- common
   new: (...) =>
     @setup ...
 
-  update: (dt) =>
-
   get: => @value
   getc: =>
     L\warn "stream #{@} cast to constant"
     @value
 
+-- interface
+  update: (dt) =>
+
   destroy: =>
 
+-- static
   __tostring: => "<op: #{@@__name}>"
   __inherited: (cls) => cls.__base.__tostring = @__tostring
 
   spawn: (Opdef, ...) ->
     Opdef ...
 
-class Macro
-  new: (@node) =>
-    -- print "creating Macro #{@@__name}", debug.traceback!
-
-  -- forwarded from ASTNode
-  -- `scope` is the parent scope.
-  -- should :expand or :expand_quoted all subexprs
-  -- should return `Const` of `forward` if it has a value
-  expand: (scope) =>
-    L\trace "expanding #{@}"
-    for child in *@node[2,]
-      L\push child\expand, @node.scope
-
-    nil
-
-  -- forwarded from ASTNode
-  -- should dispatch :patch on all :expanded subexprs
-  -- should setup @value if it is an Op
-  patch: (map) =>
-    L\trace "patching #{@}"
-    for child in *@node[2,]
-      L\push child\patch, map
-
-  -- forwarded from ASTNode
-  -- should dispatch :update on all :expanded subexprs and @node.value
-  update: (dt) =>
-    L\trace "updating #{@}"
-    for child in *@node[2,]
-      L\push child\update, dt
+class Action
+-- common
+  new: (head, @tag, @registry) =>
+    @patch head
+
+  register: =>
+    @tag = @registry\register @, @tag
 
-    @node.value\update dt if @node.value
+-- interface
+  -- * eval args
+  -- * perform scope effects
+  -- * patch nested exprs
+  -- * return runtime-tree value
+  eval: (scope, tail) => error "not implemented"
 
-  -- forwarded from ASTNode
-  -- should dispatch :destroy to all allocated Ops
+  -- free resources
   destroy: =>
-    L\trace "destroying #{@}"
-    @node.value\destroy! if @node.value
 
-  __tostring: => "<macro: #{@@__name}>"
-  __inherited: (cls) => cls.__base.__tostring = @__tostring
+  -- update this instance for :eavl() with new head
+  -- if :patch() returns false, this instance is :destroy'ed and recreated instead
+  -- must *not* return false when called after :new()
+  -- only considered if Action types match
+  patch: (head) =>
+    if head == @head
+      true
 
-class Forward
-  new: (@node) =>
+    @head = head
 
-  get: => (assert @node.value, "node never patched! #{@}")\get!
-  getc: => (assert @node.value, "node never patched! #{@}")\getc!
+-- static
+  @get_or_create: (ActionType, head, tag, registry) ->
+    last = tag and registry\find tag
+    compatible = last and
+                 last.__class == ActionType and
+                 last\patch head
 
-  update: =>
-  destroy: =>
+    if not compatible
+      last\destroy! if last
+      compatible = ActionType head, tag, registry
 
-  __tostring: => "<fwd: #{@node}>"
+    with compatible
+      \register!
+
+  __tostring: => "<action: #{@@__name}>"
+  __inherited: (cls) => cls.__base.__tostring = @__tostring
 
 class Const
   types = {
@@ -80,27 +83,60 @@ class Const
     num: true
     op: true
     opdef: true
-    macrodef: true
+    builtin: true
   }
-  new: (@type, @value) =>
+
+-- Value interface
+  new: (@type, @value, @raw) =>
     assert types[@type], "invalid Const type: #{@type}"
 
-  get: => @value
-  getc: => @value
+  get: (type) =>
+    assert not type or type == @type, "#{@} is not a #{type}"
+    @value
 
-  update: =>
-  destroy: =>
+  getc: (type) =>
+    assert not type or type == @type, "#{@} is not a #{type}"
+    @value
+
+-- AST interface
+  eval: (scope) =>
+    switch @type
+      when 'num', 'str'
+        @
+      when 'sym'
+        assert (scope\get @value), "undefined reference to symbol '#{@raw}'"
+      else
+        error "cannot evaluate #{@}"
 
+  quote: => @
+
+  stringify: => @raw
+
+-- static
   __tostring: =>
     value = if @type\match 'def$' then @value.__name else @value
     "<#{@type}: #{value}>"
 
-  ancestor = (klass) ->
-    assert klass, "cant find the ancestor of nil"
-    while klass.__parent
-      klass = klass.__parent
-    klass
-  wrap: (val, name='(unknown)') ->
+  __eq: (other) =>
+    other.type == @type and other.value == @value
+
+  unescape = (str) ->
+    str = str\gsub '\\"', '"'
+    str = str\gsub "\\'", "'"
+    str = str\gsub "\\\\", "\\"
+    str
+
+  @parse: (type, sep) =>
+    switch type
+      when 'num' then (match) -> @ 'num', (tonumber match), match
+      when 'sym' then (match) -> @ 'sym', match, match
+      when 'str' then (match) -> @ 'str', (unescape match), sep .. match .. sep
+
+  @num: (num) -> Const 'num', num
+  @str: (str) -> Const 'str', str
+  @sym: (sym) -> Const 'sym', sym
+
+  @wrap: (val, name='(unknown)') ->
     typ = switch type val
       when 'number' then 'num'
       when 'string' then 'str'
@@ -109,18 +145,18 @@ class Const
           -- a class
           switch ancestor val
             when Op then 'opdef'
-            when Macro then 'macrodef'
+            when Action then 'builtin'
             else
               error "#{name}: cannot wrap class '#{val.__name}'"
-        elseif klass = val.__class
+        elseif val.__class
           -- an instance
-          switch ancestor klass
+          switch ancestor val.__class
             when Op then 'op'
             when Scope then 'scope'
-            when Const, Forward
+            when Const
               return val
             else
-              error "#{name}: cannot wrap '#{klass.__name}' instance"
+              error "#{name}: cannot wrap '#{val.__class.__name}' instance"
         else
           -- plain table
           return Const 'scope', Scope.from_table val
@@ -129,9 +165,76 @@ class Const
 
     Const typ, val
 
+local builtin
+class Cell
+-- common
+  new: (@tag, @children, @white) =>
+    builtin or= require 'lib.builtin'
+
+  head: => @children[1]
+  tail: => [c for c in *@children[2,]]
+
+-- AST interface
+  eval: (scope, registry) =>
+    head = @head!\eval scope, registry
+    Action = switch head.type
+      when 'opdef'
+        -- scope\get 'op-invoke'
+        builtin['op-invoke']
+      when 'fndef'
+        -- scope\get 'fn-invoke'
+        builtin['fn-invoke']
+      when 'builtin'
+        head\getc!
+      else
+        error "cannot evaluate expr with head #{head}"
+
+    action = Action\get_or_create head, tag, registry
+    action\eval scope, @tail!
+
+  quote: (scope, registry) =>
+    tag = registry\register @, @tag
+    children = [child\quote scope, registry for child in *@children]
+    Cell tag, children, @white, @style
+
+  stringify: (inner=false) =>
+    buf = ''
+    buf ..= @white[0]
+    for i, child in ipairs @children
+      buf ..= child\stringify!
+      buf ..= @white[i]
+
+    return buf if inner
+
+    tag = if @tag then "[#{@tag\stringify!}]" else ''
+    '(' .. tag .. buf .. ')'
+
+-- static
+  parse_args = (tag, parts) ->
+    if not parts
+      parts, tag = tag, nil
+
+    children, white = {}, { [0]: parts[1] }
+
+    for i = 2,#parts,2
+      children[i/2] = parts[i]
+      white[i/2] = parts[i+1]
+
+    tag, children, white
+  @parse: (...) =>
+    tag, children, white = parse_args ...
+    @ tag, children, white
+
+class RootCell extends Cell
+  head: => Const.sym 'do'
+  tail: => @children
+
+  stringify: =>
+    super\stringify true
+
 {
   :Op
-  :Macro
-  :Forward
   :Const
+  :Action
+  :Cell, :RootCell
 }
diff --git a/lib/builtin.moon b/lib/builtin.moon
index 440e553..96eb0f0 100644
--- a/lib/builtin.moon
+++ b/lib/builtin.moon
@@ -1,4 +1,4 @@
-import Macro, Const, Forward from require 'base'
+import Action, Const, Cell from require 'base'
 import Scope from require 'scope'
 
 -- (def sym1 val-expr1
@@ -8,33 +8,26 @@ import Scope from require 'scope'
 --
 -- if val-expr is a expand-time constant, defines a `Const`,
 -- otherwise places a `Forward` for the expr
-class def extends Macro
-  expand: (scope) =>
+class def extends Action
+  expand: (scope, tail) =>
     L\trace "expanding #{@}"
-    assert #@node > 2, "'def' requires at least 3 arguments"
-    assert #@node % 2 == 1, "'def' requires an even number of arguments"
+    assert #tail > 1, "'def' requires at least 2 arguments"
+    assert #tail % 2 == 0, "'def' requires an even number of arguments"
 
     L\push ->
-      for i=2,#@node,2
-        name, val_expr = @node[i], @node[i+1]
-        assert name.atom_type == 'sym', "'def's argument ##{i} has to be a symbol"
-        name = name\expand_quoted!\getc!
-
-        scope\set name, val_expr\expand @node.scope
-
-        -- @TODO: expand to Forward in Xpr:expand
-        -- if val = val_expr\expand @node.scope
-        --   -- expand-time constant
-        --   scope\set name, val
-        -- else
-        --   -- patch-time expression
-        --   scope\set name, Forward val_expr
+      for i=1,#tail,2
+        name, val_expr = tail[i], tail[i+1]
+        name = (name\quote scope, @registry)!\getc!
+        assert name.type == 'sym', "'def's argument ##{i} has to be a symbol"
+
+        scope\set name, val_expr\eval scope, @registry
+
     nil
 
-  patch: (map) =>
+  patch: (registry) =>
     L\trace "patching #{@}"
     for child in *@node[3,,2]
-      L\push child\patch, map
+      L\push child\patch, registry
 
   update: (dt) =>
     L\trace "updating #{@}"
@@ -45,14 +38,12 @@ class def extends Macro
 --
 -- require a lua module and return its `Scope`
 -- name-str has to be an expand-time constant
-class _require extends Macro
-  expand: (scope) =>
+class require_mod extends Action
+  expand: (scope,  tail) =>
     L\trace "expanding #{@}"
-    assert #@node == 2, "'require' takes only one parameter"
-    for child in *@node[2,]
-      L\push child\expand, @node.scope
+    assert #tail == 1, "'require' takes only one parameter"
 
-    name = @node\tail!
+    name = L\push tail[1]\eval, scope, @registry
     assert name.type == 'str', "'require' only works on strings"
 
     L\trace @, "loading module #{name}"
@@ -63,87 +54,104 @@ class _require extends Macro
 --
 -- merge scopes into parent scope
 -- scopes have to be expand-time constants
-class use extends Macro
-  expand: (scope) =>
+class use extends Action
+  eval: (scope, tail) =>
     L\trace "expanding #{@}"
-    for child in *@node[2,]
-      value = L\push child\expand, @node.scope
+    for child in *tail
+      value = L\push child\eval, scope, @registry
       L\trace @, "merging #{value} into #{scope}"
       assert value.type == 'scope', "'use' only works on scopes"
       scope\use value\getc!
 
     nil
 
--- ((fn ...) arg-expr1 [arg-expr2]...)
+-- (fn (p1 [p2]...) body-expr)
 --
--- invoke a function
-class FunctionInvocation extends Macro
-  new: (@node, @params, @body_tpl) =>
-    super @node
+-- declare a function
+--
+-- pX are symbols that will resolve to a 'Forward' in the body
+class fn extends Action
+  class FnDef
+    new: (@params, @body) =>
 
-  expand: (scope) =>
+  eval: (scope, tail) =>
     L\trace "expanding #{@}"
-    assert (#@params + 1) == #@node, "argument count mismatch in #{@node[1]}"
+    assert #tail == 2, "'fn' takes exactly two arguments"
+    { params, body } = tail
 
-    for i=1,#@params
-      param = @params[i]\getc!
-      argument = @node[i+1]
-      L\trace "EXPANDING ARG", argument
-      @node.scope\set param, L\push argument\expand, scope
+    assert params.__class == Cell, "'fn's first argument has to be an expression"
+    param_symbols = for param in *params
+      assert param.type == 'sym', "function parameter declaration has to be a symbol"
+      param\quote scope, @registry
 
-    @body = @body_tpl\clone @node.tag
-    val = @body\expand @node.scope
-    val
+    body = body\quote scope, @registry
+    Const 'fndef', FnDef param_symbols, body
 
-  patch: (map) =>
-    L\trace "patching #{@}:"
-    for child in *@node[2,]
-      L\push child\patch, map
+class op_invoke extends Action
+  patch: (head) =>
+    return true if head == @head
 
-    @body\patch map
+    @op\destroy! if @op
 
-  update: (dt) =>
-    L\trace "updating #{@}:"
-    @body\update dt
+    @head = head
+    assert @head.type == 'fndef', "cant op-invoke #{@head}"
+    @op = @head\getc!!
+  
+    true
+    
+  eval: (scope, tail) =>
+    args = [expr\eval scope, @registry for expr in *tail]
+    with @op
+      \patch unpack args
 
-    for child in *@node[2,]
-      L\push child\update, dt
+class fn_invoke extends Action
+  -- @TODO:
+  -- need to :patch() the case where the new head is a new fndef
+  -- but corresponds to the last head over time
 
-  destroy: (dt) =>
-    L\trace "destroying #{@}"
-    @body.value\destroy! if @body.value
+  patch: (head) =>
+    return true if head == @head
 
-  mt = { __call: (...) => @call ... }
-  with_def: (params, body) ->
-    call = (node) => FunctionInvocation node, params, body
-    setmetatable { :call, __name: 'Invocation' }, mt
+    @head = head
 
--- (fn (p1 [p2]...) body-expr)
---
--- declare a function
---
--- pX are symbols that will resolve to a 'Forward' in the body
-class fn extends Macro
-  expand: (scope) =>
-    L\trace "expanding #{@}"
-    assert #@node == 3, "'fn' takes exactly three arguments"
-    params, body = @node[2], @node[3]
+    true
 
-    assert params.type == 'Xpr', "'fn's first argument has to be an expression"
-    param_symbols = for param in *params
-      assert param.atom_type == 'sym', "function parameter declaration has to be a symbol"
-      param\expand_quoted!
+  eval: (scope, tail) =>
+    assert @head.type == 'fndef', "cant fn-invoke #{@head}"
+    { :params, :body } = @head\getc!
 
-    Const 'macrodef', FunctionInvocation.with_def param_symbols, body
+    assert #params == #tail, "argument count mismatch in #{@head}"
 
-  patch: (map) =>
-    L\trace "patching #{@}"
+    fn_scope = Scope @, scope
 
-  update: (dt) =>
+    for i=1,#params
+      name = params[i]\getc!
+      argm = tail[i]
+      L\trace "EXPANDING ARG", argument
+      fn_scope\set name, L\push argm\eval, scope, @registry
+
+    body\expand fn_scope, @registry
+
+class do_expr extends Action
+  class DoWrapper
+    new: (@children) =>
+
+    update: (dt) =>
+      for child in *@children
+        child\update dt
+
+    get: => @children[#@children]\get!
+    getc: => @children[#@children]\getc!
+
+  eval: (scope, tail) =>
+    DoWrapper [expr\eval scope, @registry for expr in *tail]
 
 {
-  :def
-  require: _require
-  :use
+  'op-invoke': op_invoke
+  'fn-invoke': fn_invoke
+  'do': do_expr
+
+  require: require_mod
+  :def, :use
   :fn
 }
diff --git a/parsing.moon b/parsing.moon
index 8e53ec6..ba1f02e 100644
--- a/parsing.moon
+++ b/parsing.moon
@@ -1,4 +1,4 @@
-import Atom, Xpr from require 'ast'
+import Const, Cell, RootCell from require 'base'
 import R, S, P, V, C, Ct from require 'lpeg'
 
 -- whitespace
@@ -12,36 +12,36 @@ space  = (wc^1 * (comment * wc^1)^0) / 1 -- required whitespace
 mspace = (comment + wc)^0 / 1            -- optional whitespace
 
 -- atoms
-sym = ((R 'az', 'AZ') + (S '-_+*/.!?')) ^ 1 / Atom.make_sym
+sym = ((R 'az', 'AZ') + (S '-_+*/.!?')) ^ 1 / Const\parse 'sym'
 
-strd = '"' * (C ((P '\\"') + (P '\\\\') + (1 - P '"'))^0) * '"' / Atom.make_strd
-strq = "'" * (C ((P "\\'") + (P '\\\\') + (1 - P "'"))^0) * "'" / Atom.make_strq
+strd = '"' * (C ((P '\\"') + (P '\\\\') + (1 - P '"'))^0) * '"' / Const\parse 'str', '\"'
+strq = "'" * (C ((P "\\'") + (P '\\\\') + (1 - P "'"))^0) * "'" / Const\parse 'str', '\''
 str = strd + strq
 
 digit = R '09'
 int = digit^1
 float = (digit^1 * '.' * digit^0) + (digit^0 * '.' * digit^1)
-num = (float + int) / Atom.make_num
+num = (float + int) / Const\parse 'num'
 
 atom = num + sym + str
 
-expr = (V 'sexpr') + atom
+expr = (V 'cell') + atom
 explist = Ct mspace * (V 'expr') * (space * (V 'expr'))^0 * mspace
 
-tag = (P '[') * (int / tonumber) * (P ']')
-sexpr = (P '(') * tag^-1 * (V 'explist') * (P ')') / Xpr.make_sexpr
+tag = (P '[') * atom * (P ']')
+cell = (P '(') * tag^-1 * (V 'explist') * (P ')') / Cell\parse
 
-nexpr = P {
-  (V 'explist') / Xpr.make_nexpr
-  :expr, :explist, :sexpr
+root = P {
+  (V 'explist') / RootCell\parse
+  :expr, :explist, :cell
 }
 
-sexpr = P {
-  'sexpr'
-  :expr, :explist, :sexpr
+cell = P {
+  'cell'
+  :expr, :explist, :cell
 }
 
-program = nexpr * -1
+program = root * -1
 
 {
   :comment
@@ -49,7 +49,7 @@ program = nexpr * -1
   :atom
   :expr
   :explist
-  :sexpr
-  :nexpr
+  :cell
+  :root
   :program
 }
diff --git a/registry.moon b/registry.moon
index 58a7f82..3fb5533 100644
--- a/registry.moon
+++ b/registry.moon
@@ -1,55 +1,67 @@
 import Scope from require 'scope'
+import Const from require 'base'
 
 class Registry
-  new: (@env) =>
+  new: () =>
     @globals = Scope!
-    for k, v in pairs require 'lib.builtin'
-      @globals\set_raw k, v
+    @globals\use Scope.from_table require 'lib.builtin'
 
+    @prev_map = {}
     @map = {}
 
   --
 
-  gentag: => #@map + 1
+  step: =>
+    for tag, val in pairs @prev_map
+      if not @map[tag]
+        val\destroy!
+
+    @prev_map, @map = @map, {}
+
+  register: (expr, tag) =>
+    tag or= @gentag!
+    @map[tag\getc 'num'] = expr
+    tag
+
+  prev: (tag) =>
+    @prev_map[tag\getc 'num']
+
+  gentag: =>
+    num = (math.max #@map, #@prev_map) + 1
+
+    while @map[num] or @prev_map[num]
+      num += 1
+
+    Const.num num
 
   retag: (@root) =>
     scope = Scope @root, @globals
 
+    @prev, @next, @tmp = @next, {}, {}
+
     -- first pass (outin):
     -- * expand macros (mutate scopes)
     -- * resolve symbols
+    -- * :register exprs
     for child in *@root
-      child\expand scope
-
-    -- second pass (inout):
-    -- * tag untagged exprs
-    -- * destroy orphaned exprs
-    seen = {}
-    to_tag = for typ, node in @root\walk 'inout', false
-      continue unless typ == 'Xpr'
-
-      if node.tag
-        @map[node.tag] = node
-        seen[node.tag] = true
-        continue
-
-      node
+      child\expand scope, @
 
-    for tag, expr in pairs @map
-      if not seen[tag]
+    -- destroy removed expr values
+    for tag, expr in pairs @prev
+      if not @next[i]
         expr.value\destroy! if expr.value
-        @map[tag] = nil
 
-    for sexpr in *to_tag
+    -- upgrade tmp tags
+    for _, expr in pairs @tmp
       tag = @gentag!
-      sexpr.tag = tag
-      @map[tag] = sexpr
+      expr.tag = tag
+      @next[tag] = expr
 
   patch: =>
     -- third pass (inout):
     -- * patch expressions (spawn/patch)
     for child in *@root
-      child\patch @map
+      child\patch @
 
   --
 
diff --git a/spec/ast_spec.moon b/spec/ast_spec.moon
deleted file mode 100644
index 1cf6c30..0000000
--- a/spec/ast_spec.moon
+++ /dev/null
@@ -1,91 +0,0 @@
-import Atom, Xpr from require 'ast'
-import Scope from require 'scope'
-import Logger from require 'logger'
-Logger.init 'silent'
-
-describe 'Atom', ->
-  expand = (typ, str, ...) ->
-    atom = Atom["make_#{typ}"] str
-    atom\expand ...
-    atom.value\getc!
-
-  describe 'sym', ->
-    it 'expand correctly', ->
-      values = { a: 1, b: 2, c: 44, 'long_name': 'str',
-                 'name/with/slash': 3 }
-
-      scope = Scope.from_table values
-
-      for k,v in pairs values
-        assert.is.equal v, expand 'sym', k, scope
-
-  describe 'num', ->
-    it 'expand correctly', ->
-      assert.is.equal 1,    expand 'num', '1'
-      assert.is.equal 0,    expand 'num', '0'
-      assert.is.equal .1,   expand 'num', '.1'
-      assert.is.equal .123, expand 'num', '.123'
-      assert.is.equal 20,   expand 'num', '20'
-      assert.is.equal 20,   expand 'num', '20.'
-      assert.is.equal 20.1, expand 'num', '20.1'
-
-  describe 'strd', ->
-    it 'expand correctly', ->
-      assert.is.equal 'hello',       expand 'strd', 'hello'
-      assert.is.equal 'hello world', expand 'strd', 'hello world'
-      assert.is.equal '',            expand 'strd', ''
-      assert.is.equal '\\',          expand 'strd', '\\\\'
-      assert.is.equal "'",           expand 'strd', "\\'"
-      assert.is.equal '"',           expand 'strd', '\\"'
-      assert.is.equal "a string with ' inside",
-                      expand 'strd', "a string with ' inside"
-
-  describe 'strq', ->
-    it 'expand correctly', ->
-      assert.is.equal 'hello',       expand 'strq', 'hello'
-      assert.is.equal 'hello world', expand 'strq', 'hello world'
-      assert.is.equal '',            expand 'strq', ''
-      assert.is.equal '\\',          expand 'strq', '\\\\'
-      assert.is.equal "'",           expand 'strq', "\\'"
-      assert.is.equal '"',           expand 'strq', '\\"'
-      assert.is.equal 'a string with " inside',
-                      expand 'strq', 'a string with " inside'
-
-describe 'Xpr', ->
-  describe 'can be tagged', ->
-    xpr = Xpr.make_sexpr 2, {''}
-    assert.is.equal 2, xpr.tag
-    assert.is.equal '([2])', xpr\stringify!
-
-  describe 'can be walked', ->
-    a1 = Atom.make_num '1'
-    a2 = Atom.make_num '2'
-    a3 = Atom.make_num '3'
-    x1   = Xpr.make_sexpr { '', a1, '' }
-    x21  = Xpr.make_sexpr { '', a2, '' }
-    x22  = Xpr.make_sexpr { '', a3, '' }
-    x2   = Xpr.make_sexpr { '', x21, ' ', x22, '' }
-    root = Xpr.make_nexpr { '', x1, ' ', x2, '' }
-
-    assert_yields = (expected_order, iter) ->
-      for val in *expected_order
-        got_typ, got_val = iter!
-        assert.is.equal val.type, got_typ
-        assert.is.equal val, got_val
-      assert.is.nil iter!
-
-    it 'inside-out', ->
-      assert_yields { a1, x1, a2, x21, a3, x22, x2, root }, root\walk 'inout'
-
-    it 'inside-out, skipping the root', ->
-      assert_yields { a1, x1, a2, x21, a3, x22, x2 }, root\walk 'inout', false
-
-    it 'outside-in', ->
-      assert_yields { root, x1, a1, x2, x21, a2, x22, a3 }, root\walk 'outin'
-
-    it 'outside-in, skipping the root', ->
-      assert_yields { x1, a1, x2, x21, a2, x22, a3 }, root\walk 'outin', false
-
-    it 'errors when direction is wrong or absent', ->
-      assert.has.errors -> root\walk!
-      assert.has.errors -> root\walk 'backandforth'
diff --git a/spec/const_spec.moon b/spec/const_spec.moon
new file mode 100644
index 0000000..4e4028f
--- /dev/null
+++ b/spec/const_spec.moon
@@ -0,0 +1,123 @@
+import Const, Op, Action from require 'base'
+import Scope from require 'scope'
+import Logger from require 'logger'
+Logger.init 'silent'
+
+class TestOp extends Op
+  new: (...) => super ...
+
+class TestAction extends Action
+  new: (...) =>
+
+describe 'Const', ->
+  describe 'wraps', ->
+    test 'numbers', ->
+      got = Const.wrap 3
+      assert.is.equal 'num', got.type
+      assert.is.equal 3, got.value
+
+    test 'strings', ->
+      got = Const.wrap "im a happy string"
+      assert.is.equal 'str', got.type
+      assert.is.equal "im a happy string", got.value
+
+    test 'Consts', ->
+      pi = Const 'num', 3.14
+      got = Const.wrap pi
+
+      assert.is.equal pi, got
+
+    test 'Opdefs', ->
+      got = Const.wrap TestOp
+
+      assert.is.equal 'opdef', got.type
+      assert.is.equal TestOp, got.value
+
+    test 'Bultins', ->
+      got = Const.wrap TestAction
+
+      assert.is.equal 'builtin', got.type
+      assert.is.equal TestAction, got.value
+
+    test 'Scopes', ->
+      sub = Scope!
+      got = Const.wrap sub
+
+      assert.is.equal 'scope', got.type
+      assert.is.equal sub, got.value
+
+    test 'tables', ->
+      pi = Const 'num', 3.14
+      got = Const.wrap { :pi }
+
+      assert.is.equal 'scope', got.type
+      assert.is.equal pi, got.value\get 'pi'
+
+  describe 'unwraps', ->
+    test 'get!, getc!', ->
+      assert.is.equal 3.14, (Const.num 3.14)\getc!
+      assert.is.equal 'hi', (Const.str 'hi')\getc!
+      assert.is.equal 'hi', (Const.sym 'hi')\getc!
+
+      assert.is.equal 3.14, (Const.num 3.14)\get!
+      assert.is.equal 'hi', (Const.str 'hi')\get!
+      assert.is.equal 'hi', (Const.sym 'hi')\get!
+
+    test 'with type assert', ->
+      assert.is.equal 3.14, (Const.num 3.14)\getc 'num'
+      assert.is.equal 'hi', (Const.str 'hi')\getc 'str'
+      assert.is.equal 'hi', (Const.sym 'hi')\getc 'sym'
+      assert.has_error -> (Const.num 3.14)\getc 'sym'
+      assert.has_error -> (Const.str 'hi')\getc 'num'
+      assert.has_error -> (Const.sym 'hi')\getc 'str'
+
+      assert.is.equal 3.14, (Const.num 3.14)\get 'num'
+      assert.is.equal 'hi', (Const.str 'hi')\get 'str'
+      assert.is.equal 'hi', (Const.sym 'hi')\get 'sym'
+      assert.has_error -> (Const.num 3.14)\get 'sym'
+      assert.has_error -> (Const.str 'hi')\get 'num'
+      assert.has_error -> (Const.sym 'hi')\get 'str'
+
+  describe 'checks equality', ->
+    test 'using the type', ->
+      val = Const 'num', 3
+      assert.is.equal (Const.num 3), val
+      assert.not.equal (Const.str '3'), val
+
+      val = Const 'str', 'hello'
+      assert.is.equal (Const.str 'hello'), val
+      assert.not.equal (Const.sym 'hello'), val
+
+    test 'using the value', ->
+      val = Const 'num', 3
+      assert.is.equal (Const.num 3), val
+      assert.not.equal (Const.num 4), val
+
+  describe 'evaluates literal', ->
+    test 'constants to themselves', ->
+      assert_noop = (val) -> assert.is.equal val, val\eval!
+
+      assert_noop Const.num 2
+      assert_noop Const.str 'hello'
+
+    test 'symbols in the scope', ->
+      scope = with Scope!
+        \set 'number', Const.num 3
+        \set 'hello', Const.str "world"
+        \set 'goodbye', Const.sym "again"
+
+      assert_eval = (sym, val) ->
+        const = Const.sym sym
+        assert.is.equal val, const\eval scope
+
+      assert_eval 'number', Const.num 3
+      assert_eval 'hello', Const.str "world"
+      assert_eval 'goodbye', Const.sym "again"
+
+  describe 'quotes literals', ->
+    test 'as themselves', ->
+      assert_noop = (val) -> assert.is.equal val, val\quote!
+
+      assert_noop Const.num 2
+      assert_noop Const.str 'hello'
+      assert_noop Const.sym 'world'
diff --git a/spec/parsing_spec.moon b/spec/parsing_spec.moon
index 05f1f85..4bd5067 100644
--- a/spec/parsing_spec.moon
+++ b/spec/parsing_spec.moon
@@ -1,4 +1,5 @@
-import space, atom, expr, explist, sexpr, nexpr, program, comment from require 'parsing'
+import space, atom, expr, explist, cell, program, comment from require 'parsing'
+import Const from require 'base'
 import Logger from require 'logger'
 Logger.init 'silent'
 
@@ -14,58 +15,81 @@ verify_parse_nope = (parser, str) ->
 describe 'atom parsing', ->
   test 'symbols', ->
     sym = verify_parse_nope atom, 'some-toast nope'
-    assert.is.equal 'sym', sym.atom_type
-    assert.is.equal 'some-toast', sym.raw
+    assert.is.equal 'sym', sym.type
+    assert.is.equal 'some-toast', sym\getc!
     assert.is.equal 'some-toast', sym\stringify!
 
   describe 'numbers', ->
     it 'parses ints', ->
       num = verify_parse_nope atom, '1234 nope'
-      assert.is.equal 'num', num.atom_type
-      assert.is.equal '1234', num.raw
+      assert.is.equal 'num', num.type
+      assert.is.equal 1234, num\getc!
       assert.is.equal '1234', num\stringify!
 
     it 'parses floats', ->
       num = verify_parse_nope atom, '0.123 nope'
-      assert.is.equal 'num', num.atom_type
-      assert.is.equal '0.123', num\stringify!
+      assert.is.equal 'num', num.type
+      assert.is.equal 0.123, num\getc!
 
       num = verify_parse_nope atom, '.123 nope'
-      assert.is.equal 'num', num.atom_type
-      assert.is.equal '.123', num\stringify!
+      assert.is.equal 'num', num.type
+      assert.is.equal 0.123, num\getc!
 
       num = verify_parse_nope atom, '0. nope'
-      assert.is.equal 'num', num.atom_type
-      assert.is.equal '0.', num\stringify!
+      assert.is.equal 'num', num.type
+      assert.is.equal 0, num\getc!
 
   describe 'strings', ->
     it 'parses double-quote strings', ->
       str = verify_parse_nope atom, '"help some stuff!" nope'
-      assert.is.equal 'strd', str.atom_type
-      assert.is.equal 'help some stuff!', str.raw
-      assert.is.equal '"help some stuff!"', str\stringify!
+      assert.is.equal 'str', str.type
+      assert.is.equal 'help some stuff!', str\getc!
 
     it 'parses single-quote strings', ->
       str = verify_parse_nope atom, "'help some stuff!' nope"
-      assert.is.equal 'strq', str.atom_type
-      assert.is.equal "help some stuff!", str.raw
-      assert.is.equal "'help some stuff!'", str\stringify!
+      assert.is.equal 'str', str.type
+      assert.is.equal "help some stuff!", str\getc!
 
     it 'handles escapes', ->
-      str = verify_parse_nope atom, '"string with \\"quote\\"s" nope'
-      assert.is.equal 'strd', str.atom_type
-      assert.is.equal 'string with \\"quote\\"s', str.raw
-      assert.is.equal '"string with \\"quote\\"s"', str\stringify!
+      str = verify_parse_nope atom, '"string with \\"quote\\"s and \\\\" nope'
+      assert.is.equal 'str', str.type
+      assert.is.equal 'string with \"quote\"s and \\', str\getc!
 
-describe 'nexpr parsing', ->
+      str = verify_parse_nope atom, "'string with \\'quote\\'s and \\\\' nope"
+      assert.is.equal 'str', str.type
+      assert.is.equal "string with \'quote\'s and \\", str\getc!
+
+describe 'Cell', ->
+  test 'basic parsing', ->
+    node = verify_parse cell, '( 3   ok-yes
+                                "friend" )'
+
+    assert.is.equal 3, #node.children
+    assert.is.equal (Const.num 3), node.children[1]
+    assert.is.equal (Const.sym 'ok-yes'), node.children[2]
+    assert.is.equal (Const.str 'friend'), node.children[3]
+
+  test 'tag parsing', ->
+    node = verify_parse cell, '([42]tagged 2)'
+
+    assert.is.equal 2, #node.children
+    assert.is.equal (Const.num 42), node.tag
+
+  test 'tag parsing with whitespace', ->
+    node = verify_parse cell, '([42]
+        tagged 2)'
+
+    assert.is.equal 2, #node.children
+    assert.is.equal (Const.num 42), node.tag
+
+describe 'RootCell parsing', ->
   describe 'handles whitespace', ->
     verify = (str) ->
-      node = verify_parse nexpr, str
+      node = verify_parse program, str
 
-      assert.is.equal 'naked', node.style
-      assert.is.equal 2, #node
-      assert.is.equal '3', node[1].raw
-      assert.is.equal 'ok-yes', node[2].raw
+      assert.is.equal 2, #node.children
+      assert.is.equal (Const.num 3), node.children[1]
+      assert.is.equal (Const.sym 'ok-yes'), node.children[2]
 
     it 'at the front of the string', ->
       verify ' 3\tok-yes'
@@ -76,25 +100,6 @@ describe 'nexpr parsing', ->
     it 'everywhere', ->
       verify ' 3\tok-yes\n'
 
-describe 'sexpr', ->
-  test 'basic parsing', ->
-    node = verify_parse sexpr, '( 3   ok-yes
-                                "friend" )'
-
-    assert.is.equal '(', node.style
-    assert.is.equal 3, #node
-    assert.is.equal '3', node[1].raw
-    assert.is.equal 'ok-yes', node[2].raw
-    assert.is.equal 'friend', node[3].raw
-
-  test 'tag parsing', ->
-    node = verify_parse sexpr, '([42]tagged 2)'
-
-    assert.is.equal '(', node.style
-    assert.is.equal 2, #node
-
-    assert.is.equal 42, node.tag
-
 test 'whitespace', ->
   assert.is.equal '  ', space\match '  '
   assert.is.equal '\n\t ', space\match '\n\t '
diff --git a/spec/registry_spec.moon b/spec/registry_spec.moon
new file mode 100644
index 0000000..fd33981
--- /dev/null
+++ b/spec/registry_spec.moon
@@ -0,0 +1,66 @@
+import Registry from require 'registry'
+import Const from require 'base'
+
+mk = ->
+  mock {
+    destroy: =>
+  }
+
+describe 'registry', ->
+  registry = Registry!
+
+  a, b, c = mk!, mk!, mk!
+
+  it 'registers new items', ->
+    assert.is.equal (Const.num 1), registry\register a, nil
+    assert.is.equal (Const.num 2), registry\register b, nil
+
+  it 'is empty until stepped', ->
+    assert.is.nil registry\prev Const.num 1
+    assert.is.nil registry\prev Const.num 2
+    assert.is.nil registry\prev Const.num 3
+
+    registry\step!
+
+  it 'memorizes items', ->
+    assert.is.equal a, registry\prev Const.num 1
+    assert.is.equal b, registry\prev Const.num 2
+    assert.is.nil      registry\prev Const.num 3
+
+  it 'destroyes lost items', ->
+    assert.is.equal (Const.num 2), registry\register b, Const.num 2
+    assert.is.equal (Const.num 3), registry\register c, nil
+
+    assert.is.equal a, registry\prev Const.num 1
+    assert.is.equal b, registry\prev Const.num 2
+    assert.is.nil      registry\prev Const.num 3
+
+    assert.stub(a.destroy).was.not_called!
+    assert.stub(b.destroy).was.not_called!
+    assert.stub(c.destroy).was.not_called!
+
+    registry\step!
+
+    assert.stub(a.destroy).was.called_with a
+    assert.stub(b.destroy).was.not_called!
+    assert.stub(c.destroy).was.not_called!
+
+    assert.is.nil      registry\prev Const.num 1
+    assert.is.equal b, registry\prev Const.num 2
+    assert.is.equal c, registry\prev Const.num 3
+
+  it 'fills holes', ->
+    assert.is.equal (Const.num 1), registry\register a, nil
+    assert.is.equal (Const.num 2), registry\register b, Const.num 2
+    assert.is.equal (Const.num 3), registry\register c, Const.num 3
+
+    assert.is.nil      registry\prev Const.num 1
+    assert.is.equal b, registry\prev Const.num 2
+    assert.is.equal c, registry\prev Const.num 3
+
+    registry\step!
+
+    assert.is.equal a, registry\prev Const.num 1
+    assert.is.equal b, registry\prev Const.num 2
+    assert.is.equal c, registry\prev Const.num 3
+