clj.orcery

Language, Expression and Design

Tuesday

04

October 2016

why clojure.zip sucks

by Chris Zheng,

I have to say it. The clojure.zip implementation sucks.

I'll be completely upfront here. The real motive of course, is to trash-talk an existing library and then point to something that I just wrote. Let's get that clear right from the start.

Now back to trash-talking.

IMPOSSIBLE!! you say. This is outright heresy. How can anything witten by Rich be anything but a masterpiece? clojure.zip has been around since the very beginning of clojure. It's so popular that so many libraries are built on top of it and it's also optimized with a fast implementation. So if it sucks, then why didn't people say anything before?

Let me put it this way - We all have better things to do in our lives than nitpick over zipper implementations.

Well. I don't.

The reason why using clojure.zip sucks is because it lures us into a false sense of security. It obviously works. People have obviously built things with it but this is why it's even more sneaky and insidious. It's always when we get drawn in too close that the cracks begin to appear.

What is a zipper?

For those that don't know what a zipper is, here is a brief intro:

A zipper is a data structure representing an ordered tree and a position within the ordered tree. What is an ordered tree you ask? Well... if you write clojure, you will be writing ordered trees all day long. For example, we can create an ordered tree like this:

'(this is
  (an)
  (ordered (tree)))

or like this:

[:this :is [:an] [:ordered [:tree]]]

Really - clojure code is an ordered tree.

For a data structure to be of use, we have to know how to access and manipulate that structure. The zipper library is fundamental to being able to access and manipulate an ordered tree as it contains the two primary bits of information:

  • the entire datastructure
  • the position of a cursor that can move about within the tree.

So you can think of using the zipper library as telling a cursor where to go. Using clojure's representation, when we create a zipper, this is essentially what we are looking at, with the cursor being represented as a container surrounding a sexpr

(seq-zip 'stuff)

yields:

< stuff >  

The < and > represent the cursor around the object. So

(seq-zip '(this is
           (an)
           (ordered (tree))))

yields:

<(this is  
  (an)
  (ordered (tree)))>

Movement

So the basics and semantics have been established. Once we have a zipper, we can then tell it some instructions:

down

(<this> is
  (an)
  (ordered (tree)))

right

(this <is>
  (an)
  (ordered (tree)))

right

(this is
  <(an)>
  (ordered (tree)))

down

(this is
  (<an>)
  (ordered (tree)))

insert-right the value an

(this is
  (<an> an)
  (ordered (tree)))

right

(this is
  (an <an>)
  (ordered (tree)))

insert-left the value example

(this is
  (an example <an>)
  (ordered (tree)))

insert-left the value of

(this is
  (an example of <an>)
  (ordered (tree)))

up

(this is
  <(an example of an)>
  (ordered (tree)))

up

<(this is  
  (an example of an)
  (ordered (tree)))>

We can see that after these steps, the orginal structure has changed. So we use the same expressions to do it in code:

(-> (zip/seq-zip '(this is
                        (an)
                        (ordered (tree))))
    (zip/down)
    (zip/right)
    (zip/right)
    (zip/down)
    (zip/insert-right 'an)
    (zip/right)
    (zip/insert-left 'example)
    (zip/insert-left 'of)
    (zip/up)
    (zip/up)
    (zip/node))
=> '(this is 
          (an example of an) 
          (ordered (tree)))

So the API for a zipper has commands that allow it to move in a 2D-like fashion, It's very mechanical, it's not that pretty but it works and it allows for higher level abstractions to be built on top of it.

why clojure.zip sucks

We now know how zippers work. We can now address the title. clojure.zip sucks because of two main reasons:

  1. Lack of guard rails - nil punning for most movements out of the zipper as well as using :end as end.
  2. Viewing the cursor as 'on an object in the tree' as opposed to 'within the tree'.

Let's talk about the first point later because whether or not it is good or not sometimes can be purely based upon opinion. I want to focus on the second point first.

Let me show some simple situations where clojure.zip does not work as intuitively as expected:

Replace the last item on a nested list with a specified value:

(defn replace-last-nest [data elem]
  (->  (zip/vector-zip data)
       zip/down
       zip/down
       zip/rightmost
       zip/remove
       (zip/insert-right elem)
       zip/root))

Let's see it in action:

(replace-last-nest [[1 2 3 4]] 10)
=> [[1 2 3 10]]    ; good

(replace-last-nest [[1 2 3]] 10)
=> [[1 2 10]]         ; good

(replace-last-nest [[1 2]] 10)
=> [[1 10]]           ; still good

wait for it...

(replace-last-nest [[1]] 10)
=> [[] 10]            ; wtf?

Those clojure zipper experts might have already caught onto this little ditty already. Why remove then insert-right if you want to replace something? Just use replace - the code becomes shorter too:

(defn replace-last-nest-fix [data elem]
  (->  (zip/vector-zip data)
       zip/down
       zip/down
       zip/rightmost
       (zip/replace elem)
       zip/root))

and look, it's fixed.

(replace-last-nest-fix [[1]] 10)
=> [[10]]            ; you idiot Chris

Okay, fine. but what about this:

I want to insert :foo into the 3rd position of a nested list, and if the list contains less than 3 elements, fill it with :wah.

So the inputs/output combinations look something like:

(foo-foo [[1 2 3 4]])
=> [[1 2 :foo 4]]

(foo-foo [[1 2 3]])
=> [[1 2 :foo]]

(foo-foo [[1 2]])
=> [[1 2 :foo]]

(foo-foo [[1]])
=> [[1 :wah :foo]]

(foo-foo [[]])
=> [[:wah :wah :foo]]

What I really want to write is something like this:

(defn step-or-insert [z]
    (or (zip/right z)
        (-> z
            (zip/insert-right :wah)
            (zip/right))))

(defn foo-foo [data]
    (-> (zip/vector-zip data)
        (zip/down)
        (zip/down)
        (step-or-insert)
        (step-or-insert)
        (zip/replace :foo)))

Which works fine for all of the inputs:

(foo-foo [[1 2]])
=> [[1 2 :foo]]

(foo-foo [[1]])
=> [[1 :wah :foo]]

until we hit an empty vector:

(foo-foo [[]])
=> (throws "Insert at top")

Okay, so it craps out on an empty vector, so what's the answer?

I thought about leaving it as an exercise to the reader but it may be a little cruel. Here is the actual implementation:

(defn foo-foo [data]
    (let [start (-> (zip/vector-zip data)
                    (zip/down))
          start (if (= (zip/node start) [])
                  (zip/insert-child start :wah)
                  start)]
      (-> (zip/down start)
          (step-or-insert)
          (step-or-insert)
          (zip/replace :foo)
          (zip/root))))

Now, my question is... Why did I have to pollute my nice foo-foo function by putting a whole bunch of nasty code in the let form.

I'll let you in on a dirty little secret. clojure.zip has problems dealing with empty containers. Even though the list is clearly there, because it's empty, clojure.zip does not want to move down. It's is not built for representing TRUE EMPTINESS.

How very Zen indeed.

No, not really. It's quite easy to pinpoint the problem and this brings me back to point number 2 of why clojure.zip sucks:

Viewing the cursor as on an object in the tree as opposed to within the tree. Notice what happens when I start removing items one by one in a list:

'(1 2 <3>) ;; remove

'(1 <2>) ;; remove

'(<1>)  ;; remove

Now, the cursor faces an existential question on the next delete. The cursor by definition has to be attached to an object within the tree. When it is asked to remove 1, the cursor does so...

(<>)

And then it realises that there is NOTHING for it to attach to anymore.

This by anyone's definition is pretty freaky and so the cursor does just that: it freaks out (some people may even call it transcending) and jumps up to the parent level and then attaches itself to the empty list:

<()>  

This behavior is predictable, and it makes complete sense when explained to people. It reminds me of that needy ex-girlfriend who can't bear the thought of being alone. Some people may even consider this a feature - but for me, it is an incredibly annoying bug. To make matters worse is what can only be described as gold-digging behaviour.

(remove (1 2 <3>)) 
=> (1 <2>)  ;; expected

(remove (1 <2> 3)) 
=> (<1> 3)  ;; expected

And now:

(remove (<1> 2 3)) 
=> <(2 3)>  ;; ... expected.

Let me explain in my own head what just happened with the last call:

The cursor has now attached itself to the item at the top of the list. However, that top item is marked for removal. The cursor does just that. It removes the top item and then it looks for the next item to attach itself to. However, it looks around and it sees only the number 2 - which is now at the top of the list. The cursor thinks that it is too good to attach itself to number 2 and so it jumps out and just attaches itself to it whole list.

To be frank... I just don't like it. I know it's expected behavior but to me it's not right behaviour.

... and another thing ....

Let's now talk about point number 1 of why clojure.zip sucks:

  • Lack of guard rails, nil punning and :end

In general I'm a big advocate for nil punning because it simplifies expression. I think that the way clojure treats a sequence operation by treating movement out of that list as nil is the right thing to do:

(next [])
=> nil

and of course, there is also rest:

(rest [])
=> ()

However, an array/vector/sequence is like one big rail. There's really not too many things that can go wrong. You can move out of the array. Sometimes we get an exception, other times we get nil. We've learnt to just deal with it because you're either in or you're either out.

With zippers however, it's a very different story. The range of movement is much more rich than in an array. We have the following choices: up, down, left, right. However, it is much more complex than that. The structure is not a uniform 2D grid and so we have to check our movement at every step.

We have three choices when moving around with a zipper.

  • We can return nil - no guard rails
  • We can return the last valid spot - soft guard rail
  • We can throw an exception - angry guard rail

At any point we make a wrong move, we can expect those 3 types of feedback. Now, I'm not saying that returning nil is bad and throwing an exception is good. It's entirely dependent on what we want to achieve. The richness of movement and expression demands choice. And it's not about having guard rails or not having guard rails - it's about being able to CHOOSE.

For example:

  • When I'm building an application that mimics user behaviour as they move through a form on an editor, I don't want my application to segfault or throw an exception when the user presses the right arrow too many times (soft guard rail)

  • When I'm building a highly optimised tree walking algorithm, I might use nil to represent a short-circuit for search (no guard rail)

  • When I'm debugging a tree walking program and I'm not sure where it is going wrong, then I would like to have the program explicitly tell me in what places there is movement out of the structure. (angry guard rail)

By supporting only one type of choice - no guard rails, clojure.zip forces the developer to do the hard work. The hard work being re-implementing the movements to suit the needs of the application. This is wasteful and developers build on top of a cursor that can't handle TRUE EMPTINESS. This is why it sucks.

introducing hara.zip

Here it comes... the old bait and switch. Yes, it's another hara library. I'm ashamed that it's all come down to this.

I am jumping the gun a little bit as I haven't yet written up a user guide - but the list of commands are there. I think people that use zipper libraries should know that when I call up on a zipper, that I don't mean it to move left 2 places and insert PSYCHE!.

This implementation is based on two conversations, years apart. One was with xsc about the implementation of remove in rewrite-clj. You see, because rewrite-clj is built on top of clojure.zip - those quirks that remove has was considered expected behaviour. I was sold, didn't think much more and two years passed. Just last week, I had an interesting coding session with Tobias Steiner who gave me the insight that I needed:

The zipper cursor should represent gaps in the container, not the objects

Then it all made sense. Instead of representing an zipper cursor as an attachment to an element:

(<1> 2 3)

we represent it as an actual cursor:

(| 1 2 3)

that

(1 | 2 3)

can

(1 2 | 3)

move

(1 2 3 |)

around

(1 2 3)|

Independently of any element in the data-structure. This gives the ability for the cursor to move into an empty list and this will work as expected:

(require '[hara.zip :as z]]

(-> (z/vector-zip [[]])
    (z/down)
    (z/down)
    (z/insert 'HELLO)
    (z/top)
    (z/node))
=> [[HELLO]]

This solves the second point. How about the problem with choice?

conditional restarts

I built hara.zip entirely on top of hara.event. You can see from code examples that half of the lines of code are taken up by calls to event/raise.

This is super important because of a very special piece of magic called continue, allowing remarkable control over how the function behaves.

For example, the default behavior of move-left is to return the actual zipper:

So you can call as many times move-left as you want and it'll stay in the right spot:

(->> (z/vector-zip [1 2])
     (z/down)
     (z/move-left)
     (z/move-left)
     (z/move-left)
     (z/cursor-str))
=> "[| 1 2]"

However, we can hook in hara.event to get the behaviour that we want:

angry guard rail example:

(use 'hara.event)

(manage   
   (-> (z/vector-zip [1 2])
       (z/down)
       (z/move-left)
       (z/move-left)
       (z/move-left)
       (z/cursor-str))
   (on {:op  :move
        :tag :no-left}
       []
       (fail)))
=> (throws "No Left Node")

no guard rail example:

(manage   
   (-> (z/vector-zip [1 2])
       (z/down)
       (z/move-left)
       (z/move-left)
       (z/move-left)
       (z/cursor-str))
   (on {:op  :move
        :tag :no-left}
       []
       (continue nil))
=> (throws "NULL Exception")

Finally, the Rick James guard rail:

(manage   
   (-> (z/vector-zip [1 2])
       (z/down)
       (z/move-left)
       (z/move-left)
       (z/move-left)
       (z/cursor-str))
   (on {:op  :move
        :tag :no-left}
       [zip]
       (continue 
         (-> zip
             (z/move-right 2)
             (z/insert-right 'PSYCHE!)))))
  => "[| 1 2 PSYCHE!]")

Let's do a bit more just to make damn sure:

(manage   
   (-> (z/vector-zip [1 2])
       (z/down)
       (z/move-left)
       (z/move-left)
       (z/move-left)
       (z/move-left)
       (z/cursor-str))
   (on {:op  :move
        :tag :no-left}
       [zip]
       (continue 
         (-> zip
             (z/move-right 2)
             (z/insert-right 'PSYCHE!)))))
=> "[1 2 | PSYCHE! PSYCHE!]"

Oh Dave Chappelle, why did you leave us?

comments powered by Disqus