The most important idea in computer science


#1

Hi there!

I wrote a blog post called The Most Important Idea in Computer Science. In it, I challenged the reader to write a small Lisp interpreter in a TDD fashion.

I promised to give a solution, so here is mine. Please feel free to share your solution!

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

    (list? exp)
    (let [[op & args] exp]
      (cond
        (= 'if op)
        (let [[test then else] args]
          (if (nil? (my-eval env test))
            (my-eval env else)
            (my-eval env then)))

        (= 'do op)
        (when-not (empty? args)
          (loop [[f & rst] args]
            (if (empty? rst)
              (my-eval env f)
              (do
                (my-eval env f)
                (recur rst)))))

        (= 'let op)
        (let [[[var val] & body] args]
          (my-eval (assoc env var val) (cons 'do body)))

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

Rock on!
Eric


#2

Thanks, I really enjoyed this! Here’s what I came up with:

(defn my-eval [env exp]
  (cond
    (symbol? exp) (env exp)
    
    (list? exp)
    (let [[op & args] exp]
      (cond
        (= op 'if) (let [[a b c] args]
                     (if (my-eval env a) (my-eval env b) (my-eval env c)))
        
        (= op 'do) (let [args' (map (partial my-eval env) args)]
                     (last args'))

        (= op 'let) (let [[[a b] & body] args]
                      (my-eval (assoc env a b) (cons 'do body)))

        :else (let [[op' & args'] (map (partial my-eval env) exp)]
                (apply op' args'))))

    :else exp))

#3

Cool! I really like your refactorings.


#4

Not the nicest, maybe even wrong, some duplication around accessing the various elements of the expression, but passes all tests :smile:

(defn my-eval [env exp] 
  (if (get env exp)
    (get env exp) 
    (if (seq? exp)
      (case (first exp)
        if (if (= (second exp) nil)
             (my-eval env (nth exp 3))
             (my-eval env (nth exp 2)))
        do (if (= (second exp) nil)
             nil
             (my-eval env (last exp)))
        let (my-eval (conj env (second exp)) (last exp))
        (apply (my-eval env (first exp)) (map (partial my-eval env) (rest exp))))
      exp)))

#5

Awesome!

I guess it works for the tests.

Looking up every value in the env shouldn’t happen. I could add a test for that.

And do should eval all of the forms. I could do a test for that, too!

Congrats and thanks!
Eric

PS How does it feel having written an interpreter?


#6

This is really great, I enjoyed it very much. Need more, please!

And the solution:

(defn my-eval [env exp]
  (let [val (env exp)]
    (cond 
      (some? val) val
      (symbol? exp) val
      (list? exp) (let [[f & args] exp]
                    (cond
                      (= 'if f) (if (my-eval env (first args))
                                    (my-eval env (second args))
                                    (my-eval env (nth args 2)))
                      (= 'do f) (reduce (fn [acc x] (my-eval env x)) nil args)
                      (= 'let f) (my-eval
                                   (reduce (fn [acc x]
                                             (assoc acc (first x) (second x)))
                                           env
                                           (partition 2 (first args)))
                                   (cons 'do (rest args)))
                     :default (apply (my-eval env f)
                                     (map (partial my-eval env) args))))
      :default exp)))

UPD: updated to work with new tests. Thanks :smile:


#7

Hey! Really great. Thanks for this. You’re giving me more ideas for some unit tests.

Eric


#8

Hey everyone, I’ve updated the exercise with a few more tests. If you’d like to check your solutions, you can copy paste them back in.


#9

I LOVED this challenge :smiley: … having the tests in place was very cool. Here’s my version; it passes the tests and it’s brief, but I don’t think it’s fully correct:

(defn my-eval [env exp]
  (cond
    (seq? exp) (condp = (first exp)
                 'if (if (my-eval env (second exp))
                                       (my-eval env (nth exp 2))
                                       (my-eval env (nth exp 3)))
                 'do (last (map #(my-eval env %) (rest exp)))
                 'let (my-eval (into env (apply hash-map (second exp)))
                               (conj (drop 2 exp) 'do))
                 ;; function evaluation
                 (apply (my-eval env (first exp))
                        (map #(my-eval env %) (rest exp))))
    :else (or (env exp) exp)))

#10

It felt really good. I’ve never written a function like and I’ve found macros quite confusing previously, but they seem more within reach now. Having the tests already written made this a lot more accessible.

I have to admit that as I scanned through your previous “Let’s TDD” articles on my phone, I didn’t realise that the code blocks were actually editors and that the whole thing was interactive, and that more tests would appear. I’d suggest that you make the interactive nature (and the fact that we don’t have to write the tests ourselves!) really obvious either in the title or somewhere on the page. Unfortunately, It’s too easy to gloss over things like that in my information-overloaded life.

It might also be nice to indicate the number of hidden tests as it’s a bit of a mystery when I’m actually going to be finished and remember to have breakfast :smile:


#11

Hey Prash,

Thanks! This was very helpful!

Eric


#12

New to clojure, but still fun. I have some destructuring to learn I see.Thanks for the exercise. My attempt:

 (if (list? exp)
    (let [funct (first exp) args (rest exp)]
      (cond
        (= 'if funct) 
          (if 
            (not (= 'nil (my-eval env (first args))))
            (my-eval env (nth args 1)) 
            (my-eval env (nth args 2)))
        (= 'do funct) 
          (last (map my-eval (repeat env) args))
        (= 'let funct)
          (my-eval 
            (merge env (apply hash-map (first args))) 
            (conj (rest args) 'do))
        :else (let [targs (map my-eval (repeat env) exp)
                    efn (first targs)
                    eargs (rest targs)]
                (apply efn eargs)
                )))
    (get env exp exp)))

#13

Fun exercise, here’s what i got:

(defn my-eval [env exp]
  (cond
    (symbol? exp) (get env exp)
    (list? exp) (let [[op & args] exp]
                  (condp = op
                    'if (if (my-eval env (first args))
                          (my-eval env (second args))
                          (my-eval env (nth args 2)))
                    'do (last (map #(my-eval env %) args))
                    'let (my-eval (apply assoc env (first args))
                                  (conj (rest args) 'do))
                    (apply (my-eval env op)
                           (map #(my-eval env %) args))))
    :else exp))

#14

(deleted my own post by mistake…)

Fun exercise, here’s what i got:

(defn my-eval [env exp]
  (cond
    (symbol? exp) (get env exp)
    (list? exp) (let [[op & args] exp]
                  (condp = op
                    'if (if (my-eval env (first args))
                          (my-eval env (second args))
                          (my-eval env (nth args 2)))
                    'do (last (map #(my-eval env %) args))
                    'let (my-eval (apply assoc env (first args))
                                  (conj (rest args) 'do))
                    (apply (my-eval env op)
                           (map #(my-eval env %) args))))
    :else exp))

#15

This was really fun, thank you Eric!
I’m not too happy about the repetition in the fn eval, but here it is anyway:

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

    (list? exp)
    (let [[op & arguments] exp]
      (cond
        (= 'if op)
        (let [[test-exp then-exp else-exp] arguments]
          (if (nil? test-exp)
            (my-eval env else-exp)
            (my-eval env then-exp)))

        (= 'do op)
        (loop [[curr & rst] arguments]
          (my-eval env curr)
          (if (seq rst)
            (recur rst)
            (my-eval env curr)))
        
        (= 'let op)
        (let [[[bind value] & let-exps] arguments]
          (my-eval (assoc env bind value) (conj let-exps 'do)))
        
        (fn? (my-eval env op))
        (apply (my-eval env op) (map #(my-eval env %) arguments))))

    :else exp))

…and now I’ll go over the other solutions to learn from them.


#16

Very fun exercise. The way the tests update live is really cool and quite addictive.

One suggestion: in my first naive implementation, I just merged the let bindings like so:

(defn eval-let [env [_let forms & body]]
  (let [new-env (merge env (apply hash-map forms))]
    (eval-do new-env (cons 'do body))))

Perhaps you could add a test that shows that each binding changes the env e.g.

(my-eval {} '(let [x 1 y x] y)) is 1

Of course, I realize that you have to put some cap on the number of tests :smile: but I think this was an subtle detail of the let.

In any case, great post!


#17

Here is my solution:

(defn my-eval [env exp]
  (cond
   (seq? exp)
      (let [[op & args] exp]
        (cond
          (= op 'if) (let [[condition if-do else-do] args]
                (if (my-eval env condition)
                  (my-eval env if-do)
                  (my-eval env else-do)))
          (= op 'do) (last (map (partial my-eval env) args))
          (= op 'let) (let [[bindings & body] args
                           enriched-env (reduce (fn [res [k v]]
                                                  (assoc res k v))
                                                env
                                                (partition 2 bindings))]
                        (my-eval enriched-env (conj body 'do)))
          :else (apply (env op) (map (partial my-eval env) args))))
   (coll? exp) (into (empty exp) (map (partial my-eval env) exp))
   (symbol? exp) (env exp)
   :else exp))

#18

These are all really great! What do you think of these exercises? Was it educational to go through the exercise?


#19

This was a fun exercise:

(defn my-eval [env exp]
  (cond
    (symbol? exp)
    (get env exp)
    (list? exp)
    (let [[f & args] exp]
      (condp = f
        'if
        (let [[test truthy falsey] args]
          (my-eval env (if (my-eval env test) truthy falsey)))
        'do
        (last (mapv (partial my-eval env) args))
        'let
        (let [[[term exp] & body] args
              env' (assoc env term exp)]
          (my-eval env' (last body)))
        (apply (get env f) (map (partial my-eval env) args))))
    :else
    exp))

Really good use of tests to iteratively expand the range of features.


#20

Very fun! I don’t think this allows for multiple let bindings though. But I would like props for doing this on my iphone!

(defn my-eval [env exp]
  (cond (= nil exp) nil
        (number? exp) exp
        (string? exp) exp
        (fn? exp) exp
        (symbol? exp) (get env exp)       
        (list? exp) (let [[op & args] exp]
                      (cond 

                       (= op 'if)
                       (let [[test then else] args]
                         (cond
                          (= test nil) (my-eval env else)
                          (not= test nil) (my-eval env then)))

                       (= op 'do) 
                       (cond (not (first args)) nil
                             (= (first args) (last args)) (my-eval env (last args))
                             (not (contains? (set (map list? args)) true)) (my-eval env (last args))
                             :else
                             (last (map #(my-eval env %) args)))

                       (= op 'let)
                       (let [[[binding val] & exprs] args
                             new-env (assoc env binding (my-eval env val))]          
                         (my-eval new-env (cons 'do exprs)))

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