On Lisp in Clojure chapter 11 (section 11.1)

I am continuing to translate the examples from On Lisp by Paul Graham into Clojure. The examples and links to the rest of the series can be found on github.

Normally I would cover more than just 1 section in a post, but I thought material in this section could stand to be in its own discussion. In addition, the next section has so much in it that it will need its own post.

Section 11.1 Creating Context

The call to let is included for completeness. I thought the definition of our-let was pretty neat. I think it shows pretty clearly what Graham means when he talks about using a macro to create a context.

(let [x 'b] (list x))

(defmacro our-let [binds & body]
  `((fn [~@(take-nth 2 binds)]
       (do ~@body)) ~@(take-nth 2 (rest binds))))

(macroexpand-1 '(our-let [x 1 y 2] (+ x y)))
;; ((clojure.core/fn [x y] (do (+ x y))) 1 2)

(our-let [x 1 y 2] (+ x y))
;; 3

It seems like we get to see the when macro every chapter. It looked to me like the when-bind* was dropping all its variables, so clearly I don't understand it to translate it. In Clojure, gensym is done by appending # to any variable that you name in a macro.

(defmacro when-bind [[var expr] & body]
  `(let [~var ~expr]
     (when ~var
       ~@body)))

Graham showed us a cond-let function that accepted a sequence of pairs containing a boolean expression followed by a let binding. In Graham's implementation he had two helper functions and one macro. I wrote it with one helper function that recursively walks through the boolean expressions until it finds one that is true.

(defn condlet-bind [bindings]
  (loop [binds bindings]
    (cond (empty? binds) []
          (first binds) (first (rest binds))
          :default (recur (rest (rest binds))))))

(defmacro condlet [clauses & body]
  `(let ~(condlet-bind clauses)
     ~@body))

I want to point out the difference between this `condlet` function and Clojure.core's `if-let` function. condlet takes a list containing booleans and bindings, and will apply the first binding for which the boolean is true. if-let says if an expression is true, bind it to a symbol and execute one branch of code; if it is not true don't bind anything, and take a different branch.

In the following pseudo code, if some-expression returns a value other than false or nil, x gets bound to the result and do-something is called. If some-expression evaluates to false or nil, x does not get bound to anything and do-something-else gets called, just like a normal if.

#_(if-let [x (some-expression)]
  (do-something x)
  (do-something-else))

Functional Tic-Tac-Toe

Recently in the #Clojure channel on Freenode I heard someone say that you could write a tic-tac-toe game without any mutable variables. I had trouble conceiving how that could be possible. I decided to write one to find out.

The full running code is on github. This post will just look at a few of the functions that show how what seems like such an imperative problem can be solved in a functional way.

When I first created the project, I called it stateless-tic-tac-toe, but this was a misnomer. There is state everywhere. Each of the functions get passed the state they need to operate on, and usually the return is an updated version of the state.

Writing individual functions was pretty straight forward. I knew I was going to need a function that took no parameters and returned an empty board. It didn't take me long to realize that I would need to keep track of who's turn it was also.

(defn new-game [] 
  [(into [] (map str (range 1 10))) "X"])

The first big difference between a functional implementation and an imperative one is in the move function. In an imperative version, the board would be stored in a variable or property, and move would be a method that accepted a move as a parameter and modified the board variable.

In the functional version, move will not modify anything. The state of the game is passed in to move, along with the move to be applied. If the move legal, move returns a new version of the board. If the move was illegal then the calling function will get an unmodified board returned.

(defn move [[board player :as game] move]
  (if (legal-input? move)
    (let [board-index (- (Integer/parseInt move) 1)]
      (if (= (nth board board-index) move)
        [(assoc board board-index player)
         (if (= player "X") "O" "X")] 
        game)) game))

Functions like check-winner again show the different style of functional verses imperative. check-winner is passed in the current game state. It passes the current board configuration to functions that check for horizontal, vertical and diagonal lines. Finally, it returns the winner if there is one, or nil, which is evaluated to false, if there is no winner.

(defn check-winner [[board _]]
  (first (concat (check-horizontal board)
                 (check-vertical board) 
                 (check-diaganal board))))

I used a text based UI, which is pretty straight forward. Drawing the board is done with a function that takes in the board vector and returns strings that can be printed out to show the board. Everything was going great until I was ready for the actual event loop.

Using a while loop seemed like such a natural way to structure the game. While the game is not over, redraw the board and ask for a new move. I couldn't find a good way to write that without mutation. Instead of a while loop, I needed to use recursion.

Once I realized that I needed recursion, the function came pretty quickly. I have a function that takes in the game state and draws the board. After that, it checks to see if the game is over. If someone has won the game, or there are no more legal moves, the function prints out a message, and then exits. If the game is not over yet, the play-game function calls the move function and recursively calls itself with the result.

(defn play-game [the-game]
  (loop [game the-game]
    (println (render-board game))
    (if (game-over? game)
          (if-let [winner (check-winner game)]
            (println (str "Congrats to " winner))
            (println "tie game"))
          (recur (move game (get-move))))))

On Lisp in Clojure, chapter 10

I am continuing to translate the examples from On Lisp by Paul Graham into Clojure. The examples and links to the rest of the series can be found on github.

Chapter 10 presented some interesting problems. Some of them were the result of rampant mutability, and I have skipped those, but much of the rest applies to Clojure.

Stuart Halloway also has written a post on this chapter on his blog.

Section 10.1 Number of Evaluations

The difference between the correct version of the for loop and the multiple evaluation version is pretty straight forward. By binding ~stop to gstop#, stop only gets evaluated once.

;; correct version
(defmacro for' [[var start stop] & body]
  `(let [~var (atom ~start) gstop# ~stop]
     (while (< (deref ~var) gstop#)
         ~@body
         (swap! ~var inc))))

;; subject to multiple evaluations
(defmacro for' [[var start stop] & body]
  `(let [~var (atom ~start)]
     (while (< (deref ~var) ~stop)
       ~@body
       (swap! ~var inc))))

The the problem with the last version of the for loop really belongs in the next section.

;; incorrect order of evaluation
(defmacro for' [[var start stop] & body]
    `(let [gstop# ~stop ~var (atom ~start)]
       (while (< (deref ~var) ~stop)
         (swap! ~var inc)
         ~@body)))

Section 10.2 Incorrect Order of Evaluation

When I read the for macro labeled as having the incorrect order of evaluation, I thought Graham meant that the counter was being incremented at the top of the loop, and so I wrote my loop that way, and thought it was kind of a silly example. Then I tried the call to for in this section. First, Graham shows us an example where the order of evaluation gives an interesting result.

(def x (atom 10))
(+ (reset! x 3) @x)
;; => 6

In the version of the for loop with the incorrect order of evaluation, the stop variable appears first, so that gets evaluated, which sets x to 13. Then, start gets bound to the value of x, which is now 13, so the loop never actually runs. In the correct version of the for loop, in the let expression, the start is bound first, to 1, and then stop is bound to 13. I think Graham is right when he says that a caller has a right to expect start to be evaluated before stop because they appear left to right in the argument list. He is definitely right when he says this is a pathological way to call for'.

(let [x (atom 1)]
  (for' [i @x (reset! x 13)]
        (println @i)))

Section 10.3 Non-functional Expanders

This section shows a lot of awful things that can happen when you mix macros and mutation. But since we are in Clojure, we already avoid mutation when possible. Moving on...

Section 10.4 Recursion

Graham shows us how write a function with recursion and then shows us how to rewrite the same function in a more imperative manner. He does this because in this section he shows a potential pitfall of recursion in macros, and the imperative loop is an alternative.

The imperative version of our-length is a little extra painful in Clojure. Rather than mutating the list and the counter in a while loop, I am going to stick with the recursive function. We will just be careful when we recurse in macros.

(defn our-length [x]
  (loop [lst x acc 0]
    (if (empty? lst) acc
        (recur (rest lst) (inc acc)))))

Graham's ntha function works just fine. Rewriting it as the macro, nthb causes an infinite loop in the macro expansion.

 
(defn ntha [n lst]
  (if (= n 0)
    (first lst)
    (ntha (- n 1) (rest lst))))

(defmacro nthb [n lst]
  `(if (= ~n 0)
     (first ~lst)
     (nthb (- ~n 1) (rest ~lst))))

(macroexpand-1 '(nthb 2 [1 2 3 4 5]))

Graham shows a couple of ways to rewrite nth as a macro that doesn't lead to an infinite loop. I have just rewritten the version with the recursion in the macro.

(defmacro nthe [n lst]
  `(loop [n# ~n lst# ~lst]
     (if (= n# 0)
       (first lst#)
       (recur (dec n#) (rest lst#)))))

Graham also presents a pair of examples of writing a an `or` macro that sidestep the pitfalls of a recursive macro. In the first, the macro calls a recursive function. The second macro does its own recursion. This seems to be less difficult to do safely in Clojure, because recursion is done with `recur` rather than a function calling itself by name.

(defn or-expand [args]
  (if (empty? args)
    nil
    (let [sym (first args)]
       (if sym
         sym
         (or-expand (rest args))))))

(defmacro ora [& args]
  (or-expand args))

(defmacro orb [& args]
  (loop [lst args]
    (if (empty? lst) false
        (let [sym (first lst)]
          (if sym sym (recur (rest lst)))))))

On Lisp in Clojure chapter 9

I am continuing to translate the examples from On Lisp by Paul Graham into Clojure. The examples and links to the rest of the series can be found on github.

Chapter 9 is presented for the sake of completeness. Clojure's let bindings solve most of the problems Graham describes in this chapter. You can solve the rest of the problems by putting a # at the end of any variable name you don't want to be subject to capture. e.g. x#.

Stuart Halloway also has written a post on this chapter on his blog. He gives a good description of how these capture issues relate to Clojure.

Section 9.1 Macro Argument Capture

We can write Clojure macros that run into some the same argument capture problems.

(defmacro for' [[var start stop] & body]
  `(do
     (def ~var (atom ~start))
     (def limit ~stop)
     (while (< (deref ~var) limit)
       ~@body
       (swap! ~var inc))))

;; seems to work
(for' [ x 1 10] (println (str "current value is " @x)))

;; fails with error
(for' [ limit 1 10] (println (str "current value is" @limit)))

The version that is supposed to fail silently actually works just fine.

(let [limit 5]
  (for' [i 1 10]
        (when (> @i limit)
          (println (str @i) ) )))

Section 9.2 Free Symbol Capture

Translating the examples from this section does not lead to the same errors. The w referred to in simple-ratio is different from the w referred to in gripe. I don't know why the gripe macro doesn't get fooled by the parameter in simple-ratio, but it doesn't.

(def w (atom []))

(defmacro gripe [warning]
  `(do (swap! w #(conj % (list ~warning)))
       nil))

(defn simple-ratio [v w]
  (let [vn (count v) wn (count w)]
    (if (or (< vn 2) (< wn 2))
      (gripe "sample < 2")
      (/ vn wn))))

Section 9.3 When Capture Occurs

The first couple of code snippets just show let binding to describe the free variables. The first capture example is almost identical in Clojure.

(defmacro cap1 []
  `(+ x 1))

The next several capture examples don't apply in Clojure. Even if you do have an x defined in your environment, this macro won't compile:

(defmacro cap2 [var]
  `(let [x 2 ~var 3]
     (+ x ~var)))

When the macro expands, x gets expanded to a namespace qualified symbol, such as user/x, but you can't use let to bind a value to a namespace qualified symbol. In the first example from this chapter, the for loop, I used def to bind my variables, because I wanted to go out of my way to get the error.

The only way to define a cap2 macro in Clojure is like this:

(defmacro cap2 [var]
  `(let [x# 2 ~var 3]
     (+ x# ~var)))

The # symbol after the variable name causes the macro expansion to do a gensym, which will give a unique name to x#, which no doubt is how Graham will have us solve the problem, after he finishes warning us about it.

Section 9.4 Avoiding Capture with Better Names

This section doesn't give any examples.

Section 9.5 Avoiding Capture by Prior Evaluation

The failing call to before doesn't fail in Clojure. Even with the caller using def from within a do block. Probably this is because we can't bind to a namespace qualified symbol in a let. Oh, don't call my position function on a value that doesn't exist in the sequence.

(defn position [needle haystack]
  (loop [acc 0 lst haystack]
    (cond (empty? lst) nil
          (= needle (first lst)) acc
          :default (recur (inc acc) (rest lst)))))


(defmacro before [x y seq2]
  `(let [seq# ~seq2]
     (< (position ~x seq#)
        (position ~y seq#))))

(before (do (def seq2 '(b a)) 'a) 'b '(a b))

Here is the Clojure version of the new improved for loop. Graham defined the code to be executed as a lambda, and then looped over the invocation of that function. I am just going to bind my end value as limit# and move on.

(defmacro for' [[var start stop] & body]
  `(let [~var (atom ~start) limit# ~stop ]
     (while (< (deref ~var) limit#)
       ~@body
       (swap! ~var inc))))

Sections 9.6 and 9.7

We have seen the for loop several times, and we have already mentioned that gensym in CLISP is done with appending a # to the var name. Clojure is broken up into namespaces, not packages. Namespaces make name collisions less common, but not impossible, just as Graham describes for Lisp.

Section 9.8 Capture in Other Name Spaces

I wasn't able to reproduce the error in Clojure. What mac thinks is fun is different than what my let binding does for fun.

(defn fun [x] (+ x 1))

(defmacro mac [x] `(fun ~x))

(mac 10)

(let [fun  (fn [y] (- y 1))]
  (mac 10))

Section 9.9 Why Bother

Graham's answer to the question is a good one. And Rich Hickey's implementation of Lisp solves a lot of the problems for us.

On Lisp in Clojure chapter 8

I am continuing to translate the examples from On Lisp by Paul Graham into Clojure. The examples and links to the rest of the series can be found on github.

The first two sections of chapter 8 contain a lot of discussion and only a couple of small examples. Section 8.3 is a lot more involved, and I think we do get the first suggestion that maybe macros really are as powerful as those who already know Lisp would have us believe.

Section 8.1 When Nothing Else WIll Do

Graham describes 7 situations in which macros can do things that functions cannot. The text is very informative. The examples aren't significant, but for the sake of completeness:

(defn addf [x]
  (+ x 1))

(defmacro addm [x]
  `(+ 1 ~x))

(defmacro our-while [test & body]
  `(if ~test
     (do
       (swap! ~test not)
       ~@body)))

(defmacro foo [x]
  `(+ ~x y))

Section 8.2 Macro or Function

Graham has a list of 7 points in this section too. This time it is the pros and cons of using a macro instead of a function in a situation when either will do. Interestingly, there are 3 pros and 4 cons.

(defn avg [& args]
  (/ (apply + args) (count args)))

(defmacro avgm [& args]
  `(/ (+ ~@args) ~(count args)))

((fn [x y] (avgm x y)) 1 3)

Section 8.3 Applications for Macros

nil! is different in Clojure, because most values are immutable. Mutable values may be one of several types, each of which has its own semantics. Last chapter, we did one macro to set a ref to nil and another to set an atom to nil. There may indeed be situations where you want to have the same command to change either a ref or an atom.

(defmacro nil! [x]
  `(cond (instance? clojure.lang.Atom ~x ) (reset! ~x nil)
         (instance? clojure.lang.Ref ~x) (dosync (ref-set ~x nil))))

These two equivelent definitions of foo show how the defn macro works in Clojure.

(defn foo [x] (* x 2))
(def foo (fn [x] (* x 2)))

And of course, we can write a simplistic defn macro.

(defmacro our-defn [name params & body]
  `(def ~name
     (fn ~params  ~@body)))

The last set of examples is much more involved. Graham describe a CAD system and shows how a move function and a scale function might be written.

Graham did not provide an implementation for redraw or bounds, but we need both, if our code is going compile and run.

(defn redraw [from-x from-y to-x to-y]
  (println (str "Redrawing from: " from-x "," from-y " to "
                to-x "," to-y)))

(defn bounds [objs]
  (list
   (apply min (for  [o ( :objects objs)]
                (deref  (:obj-x o))))
   (apply min (for  [o ( :objects objs)]
                (deref  (:obj-y o))))
   (apply max (for  [o ( :objects objs)]
                (+  (deref  (:obj-x o)) (deref (:obj-dx o)))))
   (apply max (for  [o ( :objects objs)]
                (+  (deref  (:obj-y o)) (deref (:obj-dy o)))))))

The move-objs and scale-objs functions take in a collection of objects that contain their x and y coordinates and their sizes. Each of the objects keep their properties in a map, because I prefer named parameters to positional ones. Each of the functions walks through the objects and transforms them. Then the redraw function is called, to redraw the affected portion of the screen.

(defn move-objs [objs dx dy]
  (let [[x0 y0 x1 y1] (bounds objs)]
    (doseq [o (:objects objs)]
      (swap! (:obj-x o) + dx)
      (swap! (:obj-y o) + dy))
    (let [[xa ya xb yb] (bounds objs)]
      (redraw (min x0 xa) (min y0 ya)
               (max x1 xb) (max y1 yb)))))

(defn scale-objs [objs factor]
  (let [[x0 y0 x1 y1] (bounds objs)]
    (doseq [o (:objects objs)]
      (swap! (:obj-dx o) * factor)
      (swap! (:obj-dy o) * factor))
    (let [[xa ya xb yb] (bounds objs)]
      (redraw (min x0 xa) (min y0 ya)
              (max x1 xb) (max y1 yb)))))

I wrote a sample collection of objects that could be passed in as obis to either function. The collection is actually a map, with all of the objects mapped to :objects. Originally, I had a keyword :bounds that stored the starting bounds of the objects, but the bounds need to be recalculated after the transformation, so it didn't make sense to store it in the collection. In the real world, the collection may have other properties aside from just the objects it contains, so I decided to leave it as a map.

(def sample-object-collection
  {:objects [{:name "Object 1"
              :obj-x (atom 0) :obj-y (atom 0)
              :obj-dx (atom 5) :obj-dy (atom 5)}
             {:name "Object 2"
              :obj-x (atom 10) :obj-y (atom 20)
              :obj-dx (atom 20) :obj-dy (atom 20)}]})

(move-objs sample-object-collection 5 5)

Both functions apply their transformations and then call the redraw function in the same verbose way. If we added a flip method and a rotate method, again we would have a unique transformation followed by the same call to redraw. To battle this repetition, Graham provides the with-redraw macro.

(defmacro with-redraw [varname objs & body]
  `(let [[x0# y0# x1# y1#] (bounds ~objs)]
     (doseq [~varname (:objects ~objs)] ~@body)
    (let [[xa# ya# xb# yb#] (bounds ~objs)]
      (redraw (min x0# xa#) (min y0# ya#)
              (max x1# xb#) (max y1# yb#)))))

Because of this macro, the new versions of move-objs and scale-objs are much nicer. Each function has gone from 8 lines to 4, and all of the code that was taken out was noisy and distracting. Now it is easy to see how each function performs its transformation.

(defn move-objs [objs dx dy]
  (with-redraw o objs
    (swap! (:obj-x o) + dx)
    (swap! (:obj-y o) + dy)))

(defn scale-objs [objs factor]
  (with-redraw o objs
    (swap! (:obj-dx o) * factor)
    (swap! (:obj-dy o) * factor)))

On Lisp in Clojure chapter 7 (7.5 - 7.11)

I am continuing to translate the examples from On Lisp by Paul Graham into Clojure. The examples and links to the rest of the series can be found on github.

This post covers the second half of chapter 7. Stuart Halloway also has a post on this chapter on his blog.

Section 7.5 Destructuring in Parameter Lists

Clojure also has destructuring in the same form as Graham describes in Common Lisp. Clojure also supports destructuring with its map collection type. The book Clojure Programming shows how to combine vector destructuring and map destructuring in a parameter list or let binding. But back to the example...

(let [[x [y] & z] ['a ['b] 'c 'd ]]
  (list x y z))

In the next example, Graham shows a function called dolist which executes a particular function against each member of a list in succession. This may sound like map, but map builds a new list from the return values generated by applying a function to the members of a list. dolist executes a function against each member of a list and disregards the return values. It is used to execute a function for its side effects. Clojure's version is called doseq.

(doseq [x '(1 2 3)]
  (println x))

Graham then shows a way to implement a version of dolist. He builds a macro that takes in a list, a return value and the body of commands to be executed. I like the example, especially because it shows how to incorporate an optional parameter (return) and a variadic parameter (body) in the same parameter list.

The Clojure example doesn't work quite the same though. map in Clojure is lazy, the terms will only be evaluated when they are used. So if you don't pass a return value the map executes, because the reader wants to print out the return values. If you do pass a parameter, that becomes the only return value the repl needs to display, so the mapped function is never executed.

(defmacro our-dolist [[lst & result] & body]
  `(do  (map ~@body ~lst)
        ~@result))

(macroexpand-1 (our-dolist [[1 2 3] ] #(println %)))
(macroexpand-1 (our-dolist [[1 2 3] 4] #(println %)))

Section 7.6 A Model of Macros

Graham's our-defmacro, in addition to writing the desired function, also added a property called 'expander and attached it to the created function. I thought Clojure's metadata could serve the same purpose, but I was not able to make it work. Defmacro seems to work, and macroexpand-1 works the same with it.

(defmacro our-defmacro [name params & body]
  `(defn ~name [~@params]
     (do
       ~@body)))

(macroexpand-1 '(our-defmacro test [x] (println x)(+ x 2)))

Section 7.7 Macros as Programs

In this section, Graham shows how lists can be turned into programs by using macros. The expression we would want to use in Clojure though would have the parameters in a map, instead of a list where position matters.

While the named parameters are nicer than the Common Lisp version, at the same time I did cut a couple of corners. I wrote some of the values so that I didn't have to translate them, such as the let binding, which I wrote as one long vector and stated explicitly that z was nil.

;; our desired call
(our-looper {:initial-vals [w 3 x 1 y 2 z nil]
             :body ((println x) (println y))
             :loop-params [x x y y]
             :recursion-expr ((inc x) (inc y))
             :exit-cond (> x 10)
             :exit-code (println z)
             :return-val y})

;; our desired result
(let [w 3 x 1 y 2 z nil]
  (loop [x x y y]
    (if (> x 10)
      (do (println z) y )
       (do
         (println x)
         (println y)
         (recur (inc x) (inc y))))))

;; the macro
(defmacro our-looper [{:keys [initial-vals
                              body
                              loop-params
                              recursion-expr
                              exit-cond
                              exit-code
                              return-val]}]
  `(let [~@initial-vals]
     (loop [~@loop-params]
       (if ~exit-cond
         (do ~exit-code
             ~return-val)
         (do ~@body
             (recur ~@recursion-expr))
         ))))

Section 7.8 Macro Style

I just translated the first implementation of and; as Graham says, it is the more readable.

(defmacro our-and [& args]
  (loop [lst args]
    (cond
     (= (count lst) 0) true
     (= (count lst) 1) (first lst)
     :else (if (first lst) (recur (rest lst)) false))))

Section 7.9 Dependence on Macros

Just as Graham describes for Common Lisp, in Clojure if a function-b depends on function-a, when function-a is updated, function-b will reflect the change. If function-d depends on macro-c, function-d will not be updated when macro-c is updated.

(defn func-a [input]
  (+ input 1))
(defn func-b []
  (func-a 3))
(func-b)
;; 4
(defn func-a [input]
  (+ input 10))
(func-b)
;; 13

(defmacro macro-c [input]
  `(+ ~input 1))
(defn func-d []
  (macro-d 3))
(func-d)
;; 4
(defmacro macro-c [input]
  `(+ ~input 10))
(func-d)
;; 4

Section 7.10 Macros from Functions

The examples from this section are all pretty straight forward.

(defn second-f [x]
  (first (rest x)))

(defmacro second-m [x]
  `(first (rest ~x)))

(defn noisy-second-f [x]
  (println "Someone is taking a cadr")
  (first (rest x)))

(defmacro noisy-second-m [x]
  `(do
     (println "Someone is taking a cadr")
     (first (rest ~x))))

(defn sum-f [& args]
  (apply + args))

(defmacro sum-m [& args]
  `(apply + (list ~@args)))

(defmacro sum2-m [& args]
  `(+ ~@args))

(defn foo [x y z]
  (list x (let [x y]
            (list x z))))

(defmacro foo-m [x y z]
  `(list ~x
         (let [x# ~y]
           (list x# ~z))))

(macroexpand-1
 (foo-m 1 2 3) )

Section 7.11 Symbol Macros

Symbol macros do not exist in core clojure. Konrad Hinsen has a library that adds symbol macros and other useful macro functions.