Custom language - FOR loop in a clojure interpeter?

Question

I have a basic interpreter in clojure. Now i need to implement

for (initialisation; finish-test; loop-update) {
    statements
}  

Implement a similar for-loop for the interpreted language. The pattern will be:

(for variable-declarations end-test loop-update do statement)

The variable-declarations will set up initial values for variables.The end-test returns a boolean, and the loop will end if end-test returns false. The statement is interpreted followed by the loop-update for each pass of the loop. Examples of use are:

(run ’(for ((i 0)) (< i 10) (set i (+ 1 i)) do (println i)))

(run ’(for ((i 0) (j 0)) (< i 10) (seq (set i (+ 1 i)) (set j (+ j (* 2 i)))) do (println j)))

inside my interpreter. I will attach my interpreter code I got so far. Any help is appreciated.

Interpreter

(declare interpret make-env) ;; needed as language terms call out to 'interpret'

(def do-trace false) ;; change to 'true' to show calls to 'interpret'

;; simple utilities

(def third ; return third item in a list
 (fn [a-list]
  (second (rest a-list))))

(def fourth ; return fourth item in a list
 (fn [a-list]
  (third (rest a-list))))

(def run ; make it easy to test the interpreter
 (fn [e]
  (println "Processing: " e)
  (println "=> " (interpret e (make-env)))))

;; for the environment

(def make-env
  (fn []
    '()))

(def add-var
  (fn [env var val]
    (cons (list var val) env)))

(def lookup-var
  (fn [env var]
    (cond (empty? env) 'error
          (= (first (first env)) var) (second (first env))
          :else (lookup-var (rest env) var))))

;; for terms in language

;; -- define numbers

(def is-number?
 (fn [expn]
  (number? expn)))

(def interpret-number
 (fn [expn env]
  expn))

;; -- define symbols

(def is-symbol?
  (fn [expn]
    (symbol? expn)))

(def interpret-symbol
  (fn [expn env]
    (lookup-var env expn)))

;; -- define boolean

(def is-boolean?
  (fn [expn]
    (or
      (= expn 'true)
      (= expn 'false))))

(def interpret-boolean
  (fn [expn env]
    expn))

;; -- define functions

(def is-function?
  (fn [expn]
    (and 
      (list? expn)
      (= 3 (count expn))
      (= 'lambda (first expn)))))

(def interpret-function ; keep function definitions as they are written
  (fn [expn env]
    expn))

;; -- define addition

(def is-plus?
 (fn [expn]
  (and 
   (list? expn)
   (= 3 (count expn))
   (= '+ (first expn)))))

(def interpret-plus
 (fn [expn env]
  (+ 
   (interpret (second expn) env)
   (interpret (third expn) env))))

;; -- define subtraction

(def is-minus?
 (fn [expn]
  (and 
   (list? expn)
   (= 3 (count expn))
   (= '- (first expn)))))

(def interpret-minus
 (fn [expn env]
  (- 
   (interpret (second expn) env)
   (interpret (third expn) env))))

;; -- define multiplication

(def is-times?
 (fn [expn]
  (and 
   (list? expn)
   (= 3 (count expn))
   (= '* (first expn)))))

(def interpret-times
 (fn [expn env]
  (* 
   (interpret (second expn) env)
   (interpret (third expn) env))))

;; -- define division

(def is-divides?
 (fn [expn]
  (and 
   (list? expn)
   (= 3 (count expn))
   (= '/ (first expn)))))

(def interpret-divides
 (fn [expn env]
  (/ 
   (interpret (second expn) env)
   (interpret (third expn) env))))

;; -- define equals test

(def is-equals?
  (fn [expn]
    (and
      (list? expn)
      (= 3 (count expn))
      (= '= (first expn)))))

(def interpret-equals
  (fn [expn env]
    (=
      (interpret (second expn) env)
      (interpret (third expn) env))))

;; -- define greater-than test

(def is-greater-than?
  (fn [expn]
    (and
      (list? expn)
      (= 3 (count expn))
      (= '> (first expn)))))

(def interpret-greater-than
  (fn [expn env]
    (>
      (interpret (second expn) env)
      (interpret (third expn) env))))

;; -- define not

(def is-not?
  (fn [expn]
    (and 
      (list? expn)
      (= 2 (count expn))
      (= 'not (first expn)))))

(def interpret-not
  (fn [expn env]
    (not
      (interpret (second expn) env))))

;; -- define or

(def is-or?
  (fn [expn]
    (and
      (list? expn)
      (= 3 (count expn))
      (= 'or (first expn)))))

(def interpret-or
  (fn [expn env]
    (or
      (interpret (second expn) env)
      (interpret (third expn) env))))

;; -- define and

(def is-and?
  (fn [expn]
    (and
      (list? expn)
      (= 3 (count expn))
      (= 'and (first expn)))))

(def interpret-and
  (fn [expn env]
    (and
      (interpret (second expn) env)
      (interpret (third expn) env))))

;; -- define print

(def is-print?
     (fn [expn]
  (and
    (list? expn)
    (= 2 (count expn))
    (= 'println (first expn)))))

(def interpret-print
     (fn [expn env]
  (println (interpret (second expn) env))))

;; -- define with

(def is-with?
  (fn [expn]
    (and
      (list? expn)
      (= 3 (count expn))
      (= 'with (first expn)))))

(def interpret-with
  (fn [expn env]
    (interpret (third expn)
               (add-var env 
                        (first (second expn))
                        (interpret (second (second expn)) env)))))

;; -- define if

(def is-if?
  (fn [expn]
    (and
      (list? expn)
      (= 4 (count expn))
      (= 'if (first expn)))))

(def interpret-if
  (fn [expn env]
    (cond (interpret (second expn) env) (interpret (third expn) env)
          :else                         (interpret (fourth expn) env))))

;; -- define function-application

(def is-function-application?
  (fn [expn env]
    (and
      (list? expn)
      (= 2 (count expn))
      (is-function? (interpret (first expn) env)))))

(def interpret-function-application
  (fn [expn env]
    (let [function (interpret (first expn) env)]
      (interpret (third function)
                 (add-var env
                          (first (second function))
                          (interpret (second expn) env))))))

;; the interpreter itself

(def interpret
  (fn [expn env]
    (cond do-trace (println "Interpret is processing: " expn))
    (cond 
      ; basic values
      (is-number? expn) (interpret-number expn env)
      (is-symbol? expn) (interpret-symbol expn env)
      (is-boolean? expn) (interpret-boolean expn env)
      (is-function? expn) (interpret-function expn env)
      ; built-in functions
      (is-plus? expn) (interpret-plus expn env)
      (is-minus? expn) (interpret-minus expn env)
      (is-times? expn) (interpret-times expn env)
      (is-divides? expn) (interpret-divides expn env)
      (is-equals? expn) (interpret-equals expn env)
      (is-greater-than? expn) (interpret-greater-than expn env)
      (is-not? expn) (interpret-not expn env)
      (is-or? expn) (interpret-or expn env)
      (is-and? expn) (interpret-and expn env)
      (is-print? expn) (interpret-print expn env)
      ; special syntax
      (is-with? expn) (interpret-with expn env)
      (is-if? expn) (interpret-if expn env)
      ; functions
      (is-function-application? expn env) (interpret-function-application expn env)
      :else 'error)))

;; tests of using environment

(println "Environment tests:")
(println (add-var (make-env) 'x 1))
(println (add-var (add-var (add-var (make-env) 'x 1) 'y 2) 'x 3))
(println (lookup-var '() 'x))
(println (lookup-var '((x 1)) 'x))
(println (lookup-var '((x 1) (y 2)) 'x))
(println (lookup-var '((x 1) (y 2)) 'y))
(println (lookup-var '((x 3) (y 2) (x 1)) 'x))

;; examples of using interpreter

(println "Interpreter examples:")
(run '1)
(run '2)
(run '(+ 1 2))
(run '(/ (* (+ 4 5) (- 2 4)) 2))
(run '(with (x 1) x))
(run '(with (x 1) (with (y 2) (+ x y))))
(run '(with (x (+ 2 4)) x))
(run 'false)
(run '(not false))
(run '(with (x true) (with (y false) (or x y))))
(run '(or (= 3 4) (> 4 3)))
(run '(with (x 1) (if (= x 1) 2 3)))
(run '(with (x 2) (if (= x 1) 2 3)))
(run '((lambda (n) (* 2 n)) 4))
(run '(with (double (lambda (n) (* 2 n)))
            (double 4)))
(run '(with (sum-to (lambda (n) (if (= n 0) 0 (+ n (sum-to (- n 1))))))
            (sum-to 100)))
(run '(with (x 1)
            (with (f (lambda (n) (+ n x)))
                  (with (x 2)
                        (println (f 3))))))

Added is-for? and interpret-for but still not sure not the best way to write it.

;; -- define for loop

(def is-for? 
  (fn [expn] 
    (and (list? expn) 
      (= 6 (count expn)) 
      (= 'for (first expn))
      (= 'do (fifth expn) ) 
      (list? (fourth expn)))))

(def interpret-for
  (fn [expn env]
    ()))

;;-inserted into def interpret

      (is-for? expn) (interpret-for expn env)

Answer 1

I'm happy to see that you are implementing your own language! It is an eye-opening experience because you are forced to understand the subtle details in the meaning of a language.

It is not obvious how to add a for loop construct to the language in its current form. Until now your language looks very functional in its style. The meaning of an expression is described in terms of the meaning of its subexpressions. Very nice! Some side-effects are possible too, like println.

The problem with the current form of the interpreter is that there isn't any way for an expression to change its environment. In other words, you don't have any way to assign variables. For an imperative looping construct like "for", this is needed. Now would be a good time to decide whether you want loops to be imperative (like "for") or functional (using recursion or something like loop/recur in Clojure).

To answer the actual question, I will describe how to add imperative constructs to the language and add "for". I will first describe a purely functional approach.

First you need to implement the "set" construct. What does it do? Given '(set x 2) and the environment '((x 1)) it should produce a new environment like '((x 2)). This does fit well with the existing interpret functions since they receive an expression and an environment and return a value. We need to be able to return the modified environment too in order to implement set!

One solution is to change the contract of the "interpret-foo" functions and let them return a pair of a value and an environment. Here is how interpret-plus looks in the new scheme:

(defn interpret-plus [plus-expn env0]
  (let [[_ l-expn r-expn] plus-expn
        [l-val env1] (interpret l-expn env0)
        [r-val env2] (interpret r-expn env1)]
    [(+ val1 val2) env2]))

Notice how the effects of modifying the environment is "threaded" through the interpret calls. I also took the liberty of reorganizing the code a bit: (def f (fn ...)) → (defn f ...), (f (first x) (second x)) → (let [[a b] x] (f a b)), (list a b) → [a b]. In the new scheme "set" is easy to implement:

(defn set-var [env var val]
  (cond (empty? env) 'error
        (= (first (first env)) var) (cons (list var val) (rest env))
        :else (cons (first env) (set-var (rest env) var val))))

(defn interpret-set [set-expn env0]
  (let [[_ var val-expn] set-expn
        [val env1] (interpret val-expn env0)]
    [val (set-var env1 var val)]))

Here I chose to let the (set ...) expression evaluate to the value it bound to the variable, like = does in C. Other values like nil or 'ok are fine too. The "for" construct can now be implemented:

(defn apply-decl [decl env0]
  (let [[var expn] decl
        [val env1] (interpret expn env0)]
    (add-var env1 var val)))

(defn apply-decls [decls env0]
  (reduce (fn [env decl]
            (apply-decl devl env))
          env0
          decls))

(defn interpret-for [for-expn env0]
  (let [[_ decls end-test loop-update _ statement] for-expn
        env1 (apply-decls devls env0)]
    (loop [env env1]
      (let [[end-test-val env2] (interpret end-test env)]
        (if end-test-val
          (let [[_ env3] (interpret statement env2)
                [_ env4] (interpret loop-update env3)]
            (recur env4))
          [nil env2])))))

(defn interpret-seq [seq-expn env0]
  (reduce (fn [env expn]
            (let [[_ env1] (interpret expn env)]
              env1))
          env0
          (rest seq-expn)))

There it is! This is a purely functional implementation. You could also "borrow" side-effect features from Clojure and allow the environments to mutate internally. The code becomes shorter, but less explicit. Here is an alternative implementation in the original interpreter scheme (where the interpret functions just return a value):

(defn make-env []
 '())

(defn add-var [env var val]
  (cons (list var (atom val))
        env))

(defn lookup-var [env var]
  (cond (empty? env) 'error
        (= (first (first env)) var) (deref (second (first env)))
        :else (recur (rest env) var)))

(defn set-var [env var val]
  (cond (empty? env) 'error
        (= (first (first env)) var) (reset! (second (first env)) val)
        :else (recur (rest env) var val)))

(defn interpret-set [expn env]
  (set-var env (second expn) (interpret (third expn) env)))

(defn apply-decl [decl env]
  (add-var env (first decl) (interpret (second decl) env)))

(defn apply-decls [decls env0]
  (reduce (fn [env decl]
            (apply-decl devl env))
          env0
          decls))

(defn interpret-for [expn env0]
  (let [env1 (apply-decls (second expn) env0)]
    (loop []
      (if (interpret (third expn) env1)
        (do (interpret (sixth expn) env1)
            (interpret (fourth expn) env1)
            (recur))
        nil))))

(defn interpret-seq [seq-expn env]
  (doseq [expn (rest seq-expn)]
    (interpret expn env)))

As you can see, Clojure prefers to be explicit about mutation. The reference primitive used here is the atom and the relevant functions are atom, deref, and reset!. Also, the (loop [] (if x (do a b c) nil)) part can be replaced with (while x a b c). I admitt that I have been a bit sloppy; I haven't tested all the code above. Please leave a comment if something does not work or if you want me to clarify something.

Answer 2

Note sure how helpful it is now, but I wrote a for-loop macro in Clojure that essentially does what you want. It's a nice example of using macros to add new constructs to the language.

You'll probably need to modify it to fit your interpreter:

(defmacro for-loop [[sym init check change :as params] & steps]
  (cond
    (not (vector? params)) 
      (throw (Error. "Binding form must be a vector for for-loop"))
    (not= 4 (count params)) 
      (throw (Error. "Binding form must have exactly 4 arguments in for-loop"))
    :default
      `(loop [~sym ~init value# nil]
         (if ~check
           (let [new-value# (do ~@steps)]
             (recur ~change new-value#))
           value#))))

Usage as follows:

(for-loop [i 0 (< i 10) (inc i)] 
  (println i))

Answer 3

Take a look at clj-iter: https://github.com/nathell/clj-iter

Answer 4

A loop is in Clojure usually written as a loop/recur form, e.g.:

(loop [variable binding]
  ;; do something
  (if end-test
      return-value
      (recur (step variable))))

Documentation.

Edit: Since this seems to dissatisfy at least one reader, I'll add a bit of what you need to do with this in keeping with the conventions laid out in your interpreter:

• define an is-for?, which checks your form
• define an interpret-for, which takes the corresponding parts of the expression and constructs a loop form of the kind shown above
• add a corresponding clause to the cond form in interpret