The most important idea in computer science


#21

Congratulations! There should be a continuation coming up.


#22

Mine is slightly different, in that it handles an arbitrary number of bindings inside a let form, whereas yours only handles a single binding.

(defn my-eval [env exp]
  (cond
    (symbol? exp)
    (env exp)

    (list? exp)
    (let [[op & args] exp]
      (cond
        (= 'if op)
        (let [[t y n] args]
          (if (my-eval env t) (my-eval env y) (my-eval env n)))
    
        (= 'do op)
        (let [args' (map (partial my-eval env) args)]
          (last args'))
    
        (= 'let op)
        (let [bindings (partition 2 (first args))
              args' (rest args)
              env' (reduce #(assoc %1 (first %2) (second %2)) 
                           env bindings)]
          (my-eval env' (cons 'do args')))

        :else
        (apply (my-eval env op) 
               (map (partial my-eval env) args))))

    :else
    exp))

#23

Hey Matthew!

I like it.

Eric


#24

Thank you Eric for this enjoyable exercise and your great work!

I am intrigued by the need to provide explicit bindings for functions already referenced by the same symbol in the compile time environment, e.g.

(my-eval ['x 1 'y 2] '(+ x (* y 2))) 
;; => 2

but

(my-eval {'x 1 'y 2 '+ + '* *} '(+ x (* y 2)))
;; => 5

(My solution, edited from Eric’s suggestions below, see extra tests here below line 83

(defn my-eval [env exp]
    (letfn [(eval-list [env [op & args :as exp]]
                (if (= 'let op)
                    (eval-let env exp)
                    (let [ vargs (vec (map #(my-eval env %) args))]
                        (condp = op
                            'if (if (vargs 0) (vargs 1) (vargs 2))

                            'do (do (doall vargs) 
                                    (last vargs))

                            (let [op (my-eval env op)]
                                (if (fn? op) (apply op vargs)
                                    (cons op vargs)))))))

            (eval-let [env [_ bindings & body]]
              (->> (apply list 'do body)
                   (my-eval (letbind>env bindings env))))
              
            (letbind>env [letbind env]
                (->>(partition 2 letbind) 
                (reduce (fn [env [k v]] 
                            (assoc env k (my-eval env v))) env))) ]
  (cond 
     (symbol? exp) (get env exp exp)
     (seq? exp) (eval-list env exp)
     (map? exp) (into (empty exp) 
                      (map (fn [[k v]] 
                                [(my-eval env k),(my-eval env v)])) exp)
     (coll? exp) (into (empty exp) (map #(my-eval env %) exp))
     :else exp)))

#25

Hey! Great solution!

That looks like a bug for sure.

What I think is going on is that you’re applying a symbol to the arguments. Let’s take it one step at a time:

In this:

The inner form is (* y 2). * is not bound in the env map, so it’s going to pass through as a symbol. Then it’s applied to (2 2) (y is 2 and the literal 2). Symbols act like keywords do: they look themselves up in the first argument, and if they’re not found, they return the second argument. Since 2 (the first one) is not a map, the default is returned, hence it being 2.

A similar thing is happening for the outer expression, which will become (+ x 2).

Wow! Clojure is hard! I wish that were not possible to do.

I would suggest only evaluating the elements of the list in the case where there is no special form. So move the map into eval-list. You don’t really want to eval let or if.

Great work, though!
Eric


#26

That was fun, thanks Eric.

(defn my-eval [env exp]
  (if (list? exp)
    (let [op (first exp)
          args (rest exp)]
      (cond
        (fn? (get env op)) (apply (get env op) (map (partial my-eval env) args))
      	(= op 'if) (let [[test on-true on-else] args]
                     (my-eval env (if (my-eval env test) on-true on-else)))
        (= op 'do) (reduce (fn [acc v] (my-eval env v)) nil args)
        (= op 'let) (my-eval (apply assoc env (first args)) (cons 'do args))))
    (get env exp exp)))

#27

Thanks Eric - great insight regarding the symbol-as-a-lookup behavior, this made me realize why my code just yielded the wrong value instead of crashing :smile:

Also, I followed your advice and moved my-eval recursions for lists, inside eval-list itself…makes so much sense, plus fixed more bugs for the tests I was adding - I am stll sending back to my-eval all let binding values though, to handle e.g. (let [ x (* 2 y) …] …). (see the edit in my original post).

So now, I am close to having something that (hopefully) handles any arbitrary nesting of let/if/do/funcs.

My remaining concern is the inability to resolve symbols already mapped in the environment e.g. {’+ +} is required “to make + work” - I don’t think that part was a bug in my code, since it passes all tests so far - also, the tests always bind the symbols to the actual function in the input env map; and all the solutions I took from this page also required an explicit binding at the call site to apply the actual function.

After some googling it looks like clojure-script does not allow symbol resolution e.g. as does clojure’s resolve fn, which did work for me when I tried it.

So I have a suggestion to make your challenge even more fun: 1) add tests which expect a full result without resorting to {…’+ +, '/ /} etc; 2) and tests with nesting of arbitrary complexity. I suggest 1) because it seems that hacking is an option, e.g. on this stackoverflow post

Thanks again!


#28

Hey there.

I’m glad you liked the advice.

I will definitely add some tests to the app.

Thanks!
Eric


#29

Here’s my solution. Not the most elegant but passes tests. :smile:

(defn my-eval [env exp]
  (cond (nil? exp) nil
        (symbol? exp) (env exp)
        (list? exp) (cond (= 'if (first exp)) (if (second exp) (my-eval env (nth exp 2))
                                			                   (my-eval env (nth exp 3)))
                          (= 'do (first exp)) (my-do env (rest exp) nil)
                          (= 'let (first exp)) (my-do (my-let env (second exp)) (nthrest exp 2) nil)
                          :else (apply (my-eval env (first exp)) (map (fn [e] (my-eval env e)) (rest exp))))
        :else exp))

(defn my-do [env args val]
  (cond (nil? (first args)) val
        :else (my-do env (rest args) (my-eval env (first args)))))

(defn my-let [env args]
  (cond (nil? (first args)) env
        :else (my-let (assoc env (first args) (second args)) (nthrest args 2))))

#30

Wow, this was surprisingly addictive and fun. My solution doesn’t really add much compared to the others I have scanned, there have been a lot of variations explored already, and I would have been cleaner about destructuring and naming if I were not just powering through to a solution as each test turned green, but I wanted to share it anyway. And yes, so much easier than writing an interpreter in the many other languages in which I have done so! :smile:

(declare my-eval)

(defn my-eval-do [env exp]
  (loop [remainder (rest exp)
         result (my-eval env (first exp))]
    (if (empty? remainder)
      result
      (recur (rest remainder) (my-eval env (first remainder))))))

(defn my-eval-let [env bindings body]
  (my-eval-do (reduce (fn [env binding]
                        (let [[sym val] binding]
                          (assoc env sym val)))
                      env bindings)
              body))

(defn my-eval-list [env exp]
  (let [f (first exp)
        r (rest exp)]
    (case f
      if (if (my-eval env (first r))
           (my-eval env (second r))
           (my-eval env (second (rest r))))
      do (my-eval-do env r)
      let (my-eval-let env (partition 2 (first r)) (rest r))
      (apply (get env f) (map (partial my-eval env) r)))))

(defn my-eval [env exp]
  (cond (or (number? exp) (string? exp)) exp
        (symbol? exp) (get env exp)
        (fn? exp) exp
        (list? exp) (my-eval-list env exp)))

#31

This was a great exercise and excessively fun! Thanks for the post!

Here’s my solution (which includes extra credit — a 'let which handles multiple forms, eval’d and bound in order). I wasn’t going for the most concise solution but for something that was readable and showed the grammar clearly (hence the really extraneous 'let for 'do and function application). I also left this open to handle more syntax (such as Clojure-like map and vectors literals).

(defn my-eval [env exp]
  (cond
    (list? exp) (case (first exp)
                  if (let [[_if test-form true-form false-form] exp]
                           (my-eval env
		                 (if (my-eval env test-form)
                                   true-form
                                   false-form)))
                  do (let [[_do & body] exp]
                       (when-not (empty? body)
                         (last (map (partial my-eval env) body))))
                  let (let [[_let bindings & body] exp
                            env (reduce (fn [env [binding form]]
                                          (assoc env binding (my-eval env form)))
                                        env
                                        (partition 2 bindings))]
                        (my-eval env (apply list 'do body)))
                  (let [[f & args] exp]
                    (apply (my-eval env f)
                           (map (partial my-eval env) args))))
    :else (get env exp exp)))

Great also to see everyone else’s solutions. Interesting mix of similarities and differences!

Thanks again!

-Aaron


#32

Just found this. Here’s my interpreter:

(defn my-eval [env exp]
  (let [env (merge env
                   {'if #(if %1 %2 %3)
                    'do #(last %&)
                    'let #(last %&)})
        alter-env {'let #(let [[k v] (first %2)]
                           (assoc %1 k v))}]
  	(if (seq? exp)
   		(let [[f & args] exp
              env' ((get alter-env f identity) env args)]
   	   		(apply (my-eval env f) 
                   (map (partial my-eval env') args)))
    	(get env exp exp))))

I enjoyed the prebuilt TDD environment. There were a few times where later tests would pass, but then I’d do something that would cause some failures and the text editor would scroll off the page because the divs above changed too much.


#33

Wow, great implementations!


#34

Eric, Maybe you have a bug in your implementation?

(my-eval {'x false} (if 'x 1 2)) returns 1 instead of 2


#35

Hi @viebel,

The issue is that you are quoting x and not the whole expression. It is evaluated before being passed to my-eval.

Try this:

(my-eval {'x false} '(if x 1 2))

#36

Well, this was an absolute delight–thanks ericnormand!

(defn my-eval [env exp]
  (cond
    (and (seq? exp) (= (first exp) 'if))
      (my-eval env (if-not (nil? (my-eval env (second exp))) (nth exp 2) (nth exp 3)))
    (and (seq? exp) (= (first exp) 'do)) (reduce #(my-eval env %2) nil (rest exp))
    (and (seq? exp) (= (first exp) 'let)) (let [env (merge env (second exp))] (my-eval env (nth exp 2)))
    (seq? exp) (apply (env (first exp)) (map #(my-eval env %) (rest exp)))
    (symbol? exp) (env exp)
    :else exp))

#37

What a nice challenge! Here is my solution:

(defn apply-if [env [_ pred then else]]
      [env (if pred then else)])
 
(defn apply-let [env [_ binding expression]]
     [(conj env binding) expression])

(defn apply-do [env [_ & expressions]]
  [env (last (eval-many env expressions))])

(def lang {'if apply-if 'do apply-do 'let apply-let})
(def language-feature? (into #{} (keys lang)))

(defn apply-fn [env [f & params]]
  (apply (get env f) (eval-many env params)))

(defn eval-sxp [env sxp]
  (let [head (first sxp)]
        (if (language-feature? head) 
          (apply my-eval ((get lang head) env sxp))
          (apply-fn env sxp))))

(defn eval-token [env token]
  (if (symbol? token)  ; false for strings and numbers
       (get env token)
       token))

(defn eval-many [env expressions]
  (map (partial my-eval env) expressions))

(defn my-eval [env sxp] 
   (if (seq? sxp)
     (eval-sxp env sxp)
     (eval-token env sxp))) 

I wonder if implementing a real language like this would be feasible in clojure given the JVM’s limitations optimizing non-tail-recursions.