Storing procedure in environment of evaluator leads to infinite loop

Question

I converted the Structure and Interpretation of Computer Programs (SICP) version of the meta-circular evaluator to Clojure. The main difference (besides syntax) is the handling of the environment structure. Since you cannot use set-car! and set-cdr! in Clojure, these are implemented via an atom holding a map (copied from the code of Greg Sexton's chapter 4 notes on GitHub, which I believe has the same problem with not being able to define a procedure).

The code of the two evaluators can be found here:

Unfortunately defining a procedure does not work properly. What I expect to happen is this:

;;; M-Eval input:
(defn (add1 x) (+ x 1))

;;; M-Eval value:
< Environment printed >

;;; M-Eval input:
(add1 10)

;;; M-Eval value:
11

_{Note: it is basically Scheme code that is entered except for define which is called defn.}

Here defining add1 stores a procedure in the environment structure and when it is called with (add1 10) the symbol add1 is looked up in the environment and the procedure created by the evaluator is applied to 10, resulting in 11.

What I see however is this:

;;; M-Eval input:
(defn (add1 x) (+ x 1))

;;; M-Eval value:
{add1 (procedure (x) (((+ x 1))) (#object[clojure.lang.Atom 0x7c197838 {:status :ready, :val {add1 (procedure (x) (((+ x 1))) (#object[clojure.lang.Atom 0x7c197838 {:status :ready, :val {add1 (procedure (x) (((+ x 1))) (#object[clojure.lang.Atom 0x7c197838 {:status :ready, :val {add1 (procedure (x) (((+ x 1))) (#object[clojure.lang.Atom 0x7c197838 {:status :ready, :val {add1 (procedure (x) (((+ x 1))) (... et cetera)

I get a very long environment output (it looks like the created procedure has an environment that contains the procedure itself) and then a StackOverflowError.

Unhandled clojure.lang.Compiler$CompilerException
Error compiling:
scheme-evaluator.clj:316:1
(...)

Caused by java.lang.StackOverflowError
(No message)

For clarity, I put the eval below. But I think the whole code needs to be run to properly see what is wrong.

(defn eval [exp env]
  (cond (self-evaluating? exp) exp
        (variable? exp) (lookup-variable-value exp env)
        (quoted? exp) (text-of-quotation exp)
        (assignment? exp) (eval-assignment exp env)
        (definition? exp) (eval-definition exp env)
        (if? exp) (eval-if exp env)
        (lambda? exp) (make-procedure (lambda-parameters exp) 
                                      (lambda-body exp)
                                      env)
        (begin? exp) (eval-sequence (begin-actions exp) env)
        (cond? exp) (eval (cond->if exp) env)
        (application? exp) (apply (eval (operator exp) env)
                                  (list-of-values (operands exp) env))
        :else (throw (Throwable. (str "Unknown expression type \"" exp "\" -- EVAL")))))

I hope someone can help me with this and perhaps shine some light on what is going wrong here.

Takashi Kato Takashi Kato · Accepted Answer · 2016-04-12T12:48:13

The problem is lambda-body procedure. The lambda list contains 3 elements; tag, parameters and its body. However retrieving the body by lambda-body uses cddr instead of caddr, thus the result get wrapped by extra list. So if you change the definition of lambda-body like this:

(defn lambda-body [exp] (third exp))

then you can get result computed.

NB: if you want to avoid stack overflow error, then you can change eval-definition or define-variable! to return something else such as name of the given exp.

Storing procedure in environment of evaluator leads to infinite loop

1 Answers