Arboretuum | Cat's Eye Technologies

Arboretuum is an experimental language based on forest-rewriting, a variant of tree-rewriting in which multiple trees are rewritten simultaneously. The language was intended for specifying compilers, with each tree representing a major compiler data structure (AST, symbol table, output buffer, etc.,) however, this idea was not entirely successful. Regardless, Arboretuum is Turing-complete, as tree-rewriting is simply a special case of forest-rewriting.

Sample Program

(
  (
    (ast:   (let a 4 (+ 3 (* a 3))) )
    (stab:  eot)
    (out:   halt)
  )
  (
    ((ast:  (let #(n sym) #(v) #(expr)) => #(expr)            )
     (stab: eot                         => (#(n) #(v) EOT)    ))
    ((ast:  #(n sym)                    => #(v)               )
     (stab: (#(n) #(v) #(tab))          => (#(n) #(v) #(tab)) ))
    ((ast: #(a num)                     => _                  )
     (out: halt                         => (push #(a) halt)   ))
    ((ast: (+ _ _)                      => _                  )
     (out: halt                         => (add halt)         ))
    ((ast: (* _ _)                      => _                  )
     (out: halt                         => (mul halt)         ))
  )
)