Example: loop - blancas/eisen GitHub Wiki

This page explains how the loop construct is implemented in Eisen. To avoid interference, we won't call init-eisen as it install the implementation of loop from the blancas.eisen.clojure namespace. Though semantically the same, the syntax we'll use is the following:

'loop' ( val-decl | fun-decl )*
'in' expr ( ';' expr ')'* 'end'

We'll start the code by importing the namespaces mentioned above.

(use 'blancas.eisen.core)
(use '[blancas.eisen.parser :only (bindings in-sequence word)])
(use '[blancas.eisen.trans :only (trans-bindings trans-exprs)])
(use '[blancas.kern.core :only (bind return run)])
(use '[blancas.morph.core :only (monad)])
(use '[blancas.morph.transf :only (->right modify-se)])
(use '[clojure.set :only (difference)])

This is a construct that establishes local bindings to names that are visible to the expressions in the body, here inside the in-end block. This is important for the translation because all names must have been previously declared. Thus we'll store any names from the local bindings in the compiler's data environment.

The implementation of the Eisen translator avoids global data. Eisen uses Morph a library of constructs called monads. Using the Imperative monad gives us the ability to return successful result as Right values, and unsuccessful ones as Left values, while nicely sequencing our processing and stopping as soon as some function returns a Left value. You can find a guide and examples in the Morph Wiki.

Furthermore, from any function that participates in the monad (by returning a Left or Right value) we have the ability to store and retrieve values to a data environment managed by the monad, but one that is not global. This is where we store the names form the bindings for use in the translation of the loop's body.

The Parsing Function

Parsing a loop expression is done in two steps: the bindings and the body. Fortunately, the compiler provides parsing functions for both cases. The function must return a map whose fields are:

A token that uniquely identifies this construct.
The parsed bindings (name-value pairs).
The functions in the loop's body, inside the in-end block.

The function is defined as follows:

(def loopex
  "Parses a loop expression.

   'loop' ( (val-decl) | (fun-decl) )*
   'in' expr ( ';' expr )* 'end'"
  (bind [_     (word "loop") 
         decls bindings 
         exprs in-sequence]
    (return {:token :loop-expr :decls decls :exprs exprs})))

The parsers bindings and in-sequence are predefined and used by the compiler in other features. The parser in-sequence parses from the in word, any number of expressions, and the end word.

We may test this loop parser with the Kern function run.

(run loopex "loop x = 0 in  if x > 10 then x else recur (x+1)  end")
;; {:token :loop-expr,
;;  :decls
;;  ({:token :val,
;;    :name "x",
;;    :value
;;    {:token :dec-lit, :value 0, :pos {:src "", :line 1, :col 10}}}),
;;  :exprs
;;  [{:token :cond-expr,
;;    :test
;;    {:token :BINOP,
;;     :op {:token :token, :value ">", :pos {:src "", :line 1, :col 21}},
;;     :left
;;     {:token :identifier, :value "x", :pos {:src "", :line 1, :col 19}},
;;     :right
;;     {:token :dec-lit, :value 10, :pos {:src "", :line 1, :col 23}}},
;;    :then
;;    {:token :identifier, :value "x", :pos {:src "", :line 1, :col 31}},
;;    :else
;;    {:token :fun-call,
;;     :value
;;     [{:token :identifier,
;;       :value "recur",
;;       :pos {:src "", :line 1, :col 38}}
;;      {:token :seq-expr,
;;       :value
;;       [{:token :BINOP,
;;         :op {:token :sym, :value \+, :pos {:src "", :line 1, :col 46}},
;;         :left
;;         {:token :identifier,
;;          :value "x",
;;          :pos {:src "", :line 1, :col 45}},
;;         :right
;;         {:token :dec-lit,
;;          :value 1,
;;          :pos {:src "", :line 1, :col 47}}}]}]}}]}

The Translation Function

The main translator will call our translation function with the parsed AST that corresponds to this feature. Thus we can expect the passed map to have fields :decl and :exprs. Since the declarations contain bindings that may appear in the body, we'll extract the names from the AST and put them in the compiler's data environment. The steps of the translator function as as follows:

Extract the declared names from the AST.
Add the names to the environment.
Translate the binding declarations using the function trans-bindings.
Translate the expressions in the body using the function trans-exprs.
Remove the names from the environment.

The compiler's data environment in a set, so we pass into and difference to the function modify-se to add and remove the names, respectively. Finally, with the translated code the function puts together the loop form for evaluation in Clojure.

The translator function is written as follows:

(defn trans-loopex
  "Translates a loop expression."
  [{:keys [decls exprs]}]
  (let [env (map (comp symbol :name) decls)]
    (monad [_     (modify-se into env)
	    decls (trans-bindings decls)
            exprs (trans-exprs exprs)
	    _     (modify-se difference env)]
      (->right `(loop [~@(apply concat decls)] ~@exprs)))))

Installing Loop

Now that we have our parsing and translation functions we now have to add it to the Eisen library with the function add-expression. We supply the unique token, the parsing function, the translation function, and any words we want to reserve for this expression, in this case unless.

(add-expression :loop-expr loopex trans-loopex "loop")

We may now try the simple test expression used above.

(eisen= "loop x = 0 in  if x > 10 then x else recur (x+1)  end")
;; 11