A simple metacircular interpreter in Clojure
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
dev
resources
src/metacircular
test/metacircular
.gitignore
LICENSE
README.org
project.clj

README.org

metacircular-clj

This is a simple metacircular evaluator/interpreter in Clojure.

Usage

Launch a REPL with lein run

$ lein run
metacircular-clj REPL (enter :exit to leave)
--------------------------------------------

* (->> (range 10) (filter even?) (map inc))
[1 3 5 7 9]

Evaluate expressions with metacircular.core/eval

(require '[metacircular.core :as c])

(c/eval '(map inc (range 10))) ;=> [1 2 3 4 5 6 7 8 9 10]

To analyze an expression, use metacircular.analyzer/analyze. Note that the relationship between the evaluation environment and the analyzer environment is a bit awkward, and that the map returned will be large.

(defn elide-env [node]
  (reduce-kv (fn [result k v]
               (cond
                (= k :env)  (assoc result k 'ENV)
                (vector? v) (assoc result k (map elide-env v))
                (map? v)    (assoc result k (elide-env v))
                :else       (assoc result k v)))
             {}
             node))

(let [env (-> @c/default-env (c/analyzer-env))]
  (elide-env (a/analyze '(+ 1 1) env)))
;=>
{:args ({:env ENV, :form 1, :op const} {:env ENV, :form 1, :op const}),
 :fn
 {:env ENV,
  :form +,
  :op var,
  :obj #<core$_PLUS_ clojure.core$_PLUS_@1af19d7>},
 :env ENV,
 :form (+ 1 1),
 :op invoke}

*print-length* and *print-level* are both set low by default in dev/user.clj to keep large AST nodes from spamming the REPL.

To execute an AST node as produced by analyze, use metacircular.core/exec

(def node
  (let [env (-> @c/default-env (c/analyzer-env))]
    (a/analyze '(map inc (range 10)) env)))

(c/exec node) ;=> [1 2 3 4 5 6 7 8 9 10]

View macroexpansions with metacircular.core/expand1, metacircular.core/expand, and metacircular.core/expand-all

(def form '(->> (range 10) (filter even?) (map inc)))

(c/expand1 form)    ;=> (->> (->> (range 10) (filter even?)) (map inc))
(c/expand form)     ;=> (map inc (->> (range 10) (filter even?)))
(c/expand-all form) ;=> (map inc (filter even? (range 10)))

“Standard Library”

A number of functions are pulled in from clojure.core, clojure.set, and clojure.string - see metacircular.core/primitives for the list.

The rest of the standard library (mostly macros and higher order functions) are defined in resources/core.mclj.

Features

  • Higher order functions
  • Multiple-arity and variable-arity functions
  • Destructuring (with caveats)
  • Analyzer
  • Macros
  • Tail call elimination

Implementation Notes

As few special operators are used as possible. Several operators which are special in Clojure are simple macros here (for instance, let, do, and letfn).

Almost all of the “magic” is in fn. This gives the implementation a Scheme-like character in some ways, and may be influenced by the fact that I first encountered metacircular evaluators in The Little Schemer and SICP.

Another Scheme-ism is that “vars” (really just globals) are immutable but let bindings are mutable. This is because it made it simple to implement letfn as a macro; otherwise it would have needed to be a special operator, which I wanted to avoid.

Destructuring is implemented differently than in Clojure (it’s a feature of fn rather than a macro) and, as a result, has somewhat different semantics. Specifically, everything in the bindings spec is treated as a literal. So, for instance:

(let [foo :the-foo
      {:keys [x] :or {x foo}} {}]
  x)

;; in clojure, :the-foo
;; in metacircular, the symbol foo