[Cs254f11] Help me fix this loop

[Lee Spector]

> (def board
>  (atom
>    (zipmap
>      (reduce concat
>              (for [y (range 19)]
>                (map vector (repeat 19 y )
>                     (for [x (range 19)] x))))
>      (vec (repeat 361 0)))))
> 
> ;; defines a 19x19 board with all 361 entires set to 0.

Cool use of zipmap. Note that your board is a map that maps keys of the form [x y] -- for x and y ranging from 0 to 18 -- to values that are initially 0.

> (defn place-peice
>  [x y z]
>  (swap! board update-in [[x y]] (fn [j] z) ))
> 
> ;;Sets the value of the space with coordinates [x y] to z.

Looks fine. Minor stylistic point: a Clojure convention for naming an argument that you're never going to refer to is to name it "_" (without the quotes). So your function in the swap! could be (fn [_] z). The _ doesn't mean anything special to the system -- it's just a name like any other -- but it makes it clear to the reader that you won't actually be using it, so that it can be ignored.

> (loop [c 1 x (rand-int 19) y (rand-int 19)]
>  (if (and (< c 3) (zero? (get @board x y)))
>    (do (place-peice x y (if (even? x) 1 2))
>        (recur (inc c) (rand-int 19) (rand-int 19)))
>    (recur c (rand-int 19) (rand-int 19))))
> 
> This just crashes clooj, presumably because its going infinitely, since I set
> the number of iterations low enough that it shouldn't just be an efficiency
> issue.

One problem is that where you say (get @board x y) you mean to say (get @board [x y]). Remember that the keys in your map are [x y] pairs. What you were actually doing was calling the 3-argument version of get, where the 3rd argument is a default value to return if the second argument isn't found in the map. So you were looking up x, never finding it (because all of the keys in your map are pairs), and returning y from the call to "get".

Another problem is that your loop is indeed infinite, and not lazily so. So that's bad. If the condition is true then you place a piece (maybe) and then recur with increased c. After you've done that a couple of times c will be 3 and you'll always take the second branch. But the second branch also (always) recurs, with unchanged c. So no matter what you recur, and you never finish.

You need to have a branch without a recur, and you need to set up the loop so that you eventually take that branch. Since you don't care what this loop returns -- you're calling it for the side-effects that it has on the board atom -- the terminating branch could just be whatever. E.g. maybe make it just the keyword :done, just to make the intention clear -- and it'll be returned but you don't care.

An alternative to this :done branch is to use "when", which is like "if" but without an else branch (and also you can do as many things as you want in the body that gets executed upon a true condition, without using a "do", since there's no need to distinguish this stuff from the else branch). So you'd say something like:

(loop [....]
  (when (.... this should return true if we should keep going...)
    (... do some stuff that maybe changes the board ...)
    (recur ....)))

When the condition is false the body of the "when" won't be executed and therefore there will be no recur and therefore the loop will be done.

> The other setup I had which gave me a "Must recur from tail position" error. was
> this.
> 
> (loop [c 1 x (rand-int 19) y (rand-int 19)]
>  (if (and (< c 3) (zero? (get @board x y)))
>    (place-peice x y (if (even? x) 1 2))
>    (recur c (rand-int 19) (rand-int 19)))
>  (recur (inc c) (rand-int 19) (rand-int 19)))

This has some of the same problems (e.g. in the call to "get") but the new issue is that a Clojure loop can only have a recur in the tail position, which means as the last thing that would get executed in the body of the loop. Your loop here has two expressions in it -- the "if" expression and then the recur on the final line. It's fine to have two things in a loop body, but this means that the normal execution of this body of code would do the first and then the second. So while you're doing the first the second is waiting to be done. That means that the first is not in tail position. Which means that you can't recur from within the first. So you always want to structure the body of your loops in a way that only recurs from the last thing in the body of the loop -- possibly (actually usually) in branch of an "if" or a "cond", but this should only happen within the last thing in the loop and the recur should only occur as the last thing within a particular branch. There should never be anything left, waiting to be done, after the recur. For example, look at this loop for factorial from clojinc:

(defn factorial
  [n]
  (loop [i 1 result 1]
    (if (> i n)
      result
      (recur (inc i) (* result i)))))

In this case there's only one expression in the loop. There could be others, but if so then there should be a recur only in the last one. Here the recur occurs in one branch of the "if", but there's nothing after the recur in that branch. The inc gets done, the * gets done, and then you recur with those values, and there's nothing after the recur. If we replaced the recur with something like (do (recur ....) (... do something else)) then the recur wouldn't be in tail position and it wouldn't let us do it.

BTW you can do recursion from non-tail position with self-calling functions, as in:

(defn not-tail-recursive
  [n]
  (if (> n 0)
    (not-tail-recursive (dec n))
    (println "n isn't greater than 0"))
  (println "now n =" n))

(not-tail-recursive 4)

; n isn't greater than 0
; now n = 0
; now n = 1
; now n = 2
; now n = 3
; now n = 4

But this will consume and hold system resources for each nested call, since it has to keep the data for the outer call in place while it does the next inner-most one, so that it can do the remaining things in the outer call after the inner one is done. Which is usually fine, unless you do this really deeply with lots of recursions, in which case you run out of memory and trigger an exception. The loop/recur structure (and function definitions using recur to go back to the top of the function) requires that your recur calls are in tail position so that the compiler can throw away the state of the outer call before starting the inner one. So there's no memory use buildup, and you can go as deep as you want.

BTW some other Lisps allow you to write things that don't look tail recursive, and they'll automatically detect the possibility of reformulating it as a tail recursion and make the change automatically for you during compilation. Nifty, eh? Clojure is built on top of the JVM which apparently doesn't provide good support for this, and the decision was made to make recur valid only in tail position, so that tail recursion can always be used when you use recur.

 -Lee

PS you misspelled piece, but you did so consistently :-)