I started working on a replacement for the existing clojure.zip library with a couple of enhancements to support navigation by index or key. I went down a rabbit hole, finding things I didn't like about the existing implementation. Of course the more I learned the more I came to appreciate that it reflected good compromises. Still, Clojure has evolved since Rich Hickey wrote the original implementation and at the end of the day, I still wanted to make some changes.

This is the first of a three-part series.

Part One: Zipper Primer
Part Two: Clojure Implementation
Part Three: Extensions

Zipper Primer

Like Hickey, my starting point was the Functional Pearl paper published by Gérard Huet in 1997. I pored over Huet's paper until my eyes hurt -I have a barely detectable ability to read OCaml which probably handicapped me more than I would have liked to admit. But after much experimenting at the REPL I think I finally understand the Zipper. To help others in their quest to understand the Zipper, I've generated some diagrams focusing on some critical concepts.

This diagram shows a simple tree along with a path from the Root to a terminal leaf "element" (I avoid the term "node" because, as we'll see below, it has a different meaning in the context of Huet's zipper).

An element can be both contained within its parent and contain other elements. The green in the diagram below is the same value: at the third level it is contained within its parent alongside its siblings. At the fourth level we see that it is also a collection containing sub-elements in its own right.

This next diagram gets to the crux of the zipper. It shows the hierarchy of Node structures corresponding to the path shown above. Each Node is a three-tuple comprised of a list of left (Huet calls them "elder") siblings, a pointer to its parent Node and a list of right ("younger") siblings. There are five Nodes in this diagram (the purple Node at the top has a nil value in place of a pointer to its parent). It's essential to understand that the Node does not track the value between the left siblings and the right siblings. There is essentially a gap between the left and right.

If you squint just right, the above image evokes a zipper. Imagine recursively pulling each arrow up to the gap between its parent's left and right siblings. If you had the missing "gap" element from the bottom-most (blue) node, you could reconstitute the corresponding element. You could in turn pull the reconstituted blue element up to the red node above it and thus reconstitute a red element, and with that element you could... and so on up to the root to reconstitute the entire tree.

The Zipper uses the Loc data structure to explicitly track this bottom-most missing gap element. A Loc is a tuple of the path to the root (a linked list of Nodes as depicted above) plus the single element missing from the bottom Node. Below in green are the two components of a Loc for the eighth sibling of the third descendant of the example tree. The dark green is the gap element itself (frequently named t for "tree" in Huet's paper) while the light green is the recursive Node (frequently named p for "path" in Huet's paper). Keep in mind that p is the entire path to the root -I've only shaded the first Node, but the arrow pointing up should remind you that the entire path to the root is available recursively through ancestor Nodes.

Why Zippers?

What advantages do Zippers represent compared to alternative data structures?

An obvious advantage, compared to the raw tree, is that the Zipper represents the entire (possibly updated) tree and a current position (or focus). Said another way, Zippers are a purely functional way of navigating, modifying and pointing within an arbitrary tree.

Another notable advantage is the efficient editing of immutable data structures^[1]. For immutable data, the Zipper's recursive Node structure tracks the minimal set of elements that need to be re-written to effect any change. With no loss in expressivness, the necessary re-writing is deferred until "zipping" up the data structure; multiple changes are thus effected all at once, potentially minimizing expensive write operations.

A good starting point for a bastion host image is: binlab/bastion:latest  But it requires a file volume that is my public key.  That works fine locally, but won't work when the container is deployed to AWS or some other docker host.  The solution is to build a new image with my public key baked in.  Here's the Dockerfile:

FROM binlab/bastion

LABEL maintainer="cch1@hapgood.com"

ARG USER=bastion
ARG GROUP=bastion
ARG HOME=/var/lib/bastion

COPY ./authorized_keys ${HOME}/authorized_keys

RUN chown ${USER}:${GROUP} ${HOME}/authorized_keys
RUN chmod 600 ${HOME}/authorized_keys

docker run --name bastion --hostname bastion -p 22222:22/tcp -v bastion:/usr/etc/ssh:rw -e "PUBKEY_AUTHENTICATION=true" -e "GATEWAY_PORTS=false" -e "PERMIT_TUNNEL=false" -e "X11_FORWARDING=false" -e "TCP_FORWARDING=true" -e "AGENT_FORWARDING=true" binlab/bastion:latest

Reference: https://www.techrepublic.com/article/how-to-create-your-own-docker-image/

My goal was to navigate a nested structure of maps, like this:

{:a0 {:b0 {:c0 1 :c1 {}} :b1 {:d0 2}} :a1 {:z {}}}

After a couple of iterations I settled on this for my zipper:

(defn map-zip
  [m]
  (let [root (clojure.lang.MapEntry. ::root m)]
    (z/zipper (comp map? val)
              (comp seq val)
              (fn [[k children] children'] (clojure.lang.MapEntry. k (into (empty children) children')))
              root)))

This zipper works perfectly for iteratively traversing and editing my data structure. For example, one task was to prune the empty sub-maps (like the entry at (get-in m [:a1 :z]). Here's a function that performs that task:

(defn prune
  "Recursively prune the empty submap leaves from the nested map structure `m`"
  [m]
  (let [z (map-zip m)]
    (val (loop [z z]
           (if (z/end? z)
             (z/root z)
             (recur (if (and (z/branch? z) (not (seq (z/children z))))
                      (z/remove z)
                      (z/next z))))))))

But despite the effectiveness, in several cases I found the implementation counter-intuitive -specifically when navigating.   The fundamental problem is that navigating using relative motion (left, right, leftmost, rightmost) work well for sequences (a common use case for zippers) but is inefficient when I already have an index associating keys to children for my maps.

I decided to create a new library inspired by the Clojure zipper implementation but leveraging the efficient and idiomatic navigation by sequences of keys (à la get-in , update-in, assoc-in).    Projected completion date: not now.

This article examines some of the issues involved in managing versions and describes an alternative to the default management offered by leiningen that we use at Room Key.  It assumes familiarity with Clojure, leiningen and git.

Some History

In 2010 Room Key^[1] started developing a web service using Clojure 1.2.0 and Leiningen 1.x.  By early 2011, we had decided that the version of our artifacts, particularly the primary web site application, needed to be something more flexible than commited text within project.clj.  In February, we wrote the first leingingen support code that slurped the version from git and supplied it to the project as it was being evaluated (and it was indeed evaluated back in the Leiningen 1.x days).  It wasn't much code -only a couple of dozen lines (and the author was allergic to line lengths beyond about 40 characters).  But it introduced a way of thinking that seems very natural and obvious.  Since 2011, we have expanded on the original work in several steps and today, in mid-2016 the evolution of that code is lein-v, a leiningen plugin that solves a lot of hairy issues surrounding versions.

Our Problem

A version identifies software artifacts as they evolve over time.  As such, versioning is a critical component of change management.

We find that leiningen's approach of having the version stored in the commited project.clj source requires either ambiguous versions (where many commits share the same version)^[2] or unweildy commit practices (changing the version in project.clj on every commit).

We believe:

1. Unique (and reproducible/committed) source should produce unique versions
2. Versioning should be painless in the simplest cases, but complex cases should still be manageable
3. Versions should reflect an ordering of source code where possible^[3]
4. Versioning information should live in the SCM repo -the source of source code truth
5. Version information is metadata and should not be stored within with the data it describes

A Solution

Lein-v uses git metadata to build a unique, reproducible and meaningful version for every commit.  Along the way, it adds useful metadata to your project and artifacts (jar and war files) to tie them back to a specific commit.  Consequently, it helps ensure that you never release an irreproduceable artifact.

Read git to generate a version

Instead of reading a static string in project.clj, lein-v reads git tag and commit data to construct a version that is unique to the current commit.  It then injects this git-derived version into all subsequent leiningen tasks.  The version is constructed from:

• Coded tags of the form v<version> (generated by the release process)
• SHA of the current commit
• Commit distance from most recent version tag to the current commit

The commit distance provides an ordering of commits and the SHA uniquely identifies commits.  Together, they can be used to produce versions that don't rely on manual editing of project.clj.

Update versions logically during release

By leveraging leiningen's built-in support for extending its release process, lein-v can close the loop on version management by updating the version stored in git tags.  Here is an example process that we use at Room Key:

    :release-tasks [["vcs" "assert-committed"]
                    ["v" "update"] ;; compute new version & tag it
                    ["vcs" "push"]
                    ["deploy"]]

The lein-v update task computes a new version from the current version and a command line bump parameter such as :major or :alpha^[4].  The new version is injected into the standard leiningen processing, which allows the leingingen vcs task to work as expected.

A note on version structure

Since the dawn of software management (in all its various guises), version structure has been a contentious subject.  Lein-v attempts to remain neutral on the subject of what a version should look like.  But because leiningen ultimately relies on maven to resolve dependencies, lein-v leans towards maven's (loose) view of versions.  Version structure is abstracted into two protocols (SCMHosted and Releasable), and implementations for maven 3 and semver 2.0.0 are provided.  It's not hard to write your own implementation and select it instead of the default MavenVersion.

Availability

Lein-v is available on Clojars and source is available on GitHub.  Pull requests are welcome and issues can be raised against our GitHub project as well.

Related Reading

• (http://maven.apache.org/ref/3.2.5/maven-artifact/apidocs/org/apache/maven/artifact/versioning/ComparableVersion.html)
• (http://www.sonatype.com/books/mvnref-book/reference/pom-relationships-sect-pom-syntax.html)
• (http://javamoods.blogspot.com/2010/10/world-of-versioning.html)
• (http://download.eclipse.org/aether/aether-core/1.0.1/apidocs/org/eclipse/aether/util/version/GenericVersionScheme.html)
• (http://git.eclipse.org/c/aether/aether-core.git/tree/aether-util/src/main/java/org/eclipse/aether/util/version/GenericVersion.java)
• (http://books.sonatype.com/mvnref-book/reference/pom-relationships-sect-pom-syntax.html#pom-reationships-sect-versions)
• (http://mojo.codehaus.org/versions-maven-plugin/version-rules.html)
• (http://maven.40175.n5.nabble.com/How-to-use-alternative-version-numbering-scheme-td123806.html)
• (http://maven.apache.org/ref/3.2.5/maven-artifact/index.html)
• (https://cwiki.apache.org/confluence/display/MAVENOLD/Versioning)
• (http://docs.codehaus.org/display/MAVEN/Dependency+Mediation+and+Conflict+Resolution)
• (http://dev.clojure.org/display/doc/Maven+Settings+and+Repositories)
• (http://maven.40175.n5.nabble.com/How-to-use-SNAPSHOT-feature-together-with-BETA-qualifier-td73263.html)

Notes

then known as Hotelicopter. ↩︎

SNAPSHOT versions are a prime example of ambiguous versions, and we do not use them at Room Key. ↩︎

branches in the source code repo make a total ordering impossible. ↩︎

The actual bump parameters supported depend on the specific versioning format you use.  The default maven format supports all the built-in leingingen bump levels (:major :minor :patch :alpha :beta and :rc) as well as :snapshot and :release to explicitly manage SNAPSHOT releases. ↩︎

"There have been N days with no workplace accident"

This article examines an initiative at Room Key to lower the latency between identifying a desired change to code and deploying code to production.  It assumes some familiarity with git, Jenkins and Amazon Web Services.

Some History

Room Key's primary product is a web site delivered as a single page Javascript application that queries an AWS-hosted Clojure web service.  We use two primary git repositories: one for the front-end app and one for the back-end webservice.  From our formation in 2010 until very recently we practiced a form of agile development with a three week sprint.  Once per sprint we would cycle through the same plan-code-stage-qa-deploy process.

Plan

During planning, desired features were broken down into feature stories and priority bug fixes were scheduled with bug stories.  The stories were written or adjusted in such a way as to be achievable within the upcoming sprint.  The team agreed to a three-week plan which was communicated to external stakeholders.

Code

Once the plan was laid out in the form of stories for the current sprint, developers coded the features and bug fixes.  Feature branches in our git repo were used to isolate complex stories from the master branch.  For commits to the master branch, a Jenkins continuous integration server ran unit tests for both of the primary repositories.

Stage

Towards the end of the second week of the sprint, developers would wrap up their development and merge their commits into the master branch.  A front-end release candidate was identified and staged into the back-end repository as an asset.  A back-end release candidate was then staged to a qa server.

QA

Once the release candidate was staged, the QA team had a budget of roughly four days to perform regression tests and feature tests.  Most of the feature tests were performed manually based on the acceptance criteria outlined in the feature stories.  Regression tests were partially automated and worked in the browser.

Deploy

Once QA signed off on the release candidate, we deployed the artifacts to AWS by adjusting a CloudFormation template.

Problems

Our approach was appealing in many ways: it was easy to explain; it provided regular feedback; compared to old-school waterfall planning methodologies, it was efficient;  it ticked a lot of the "agile" boxes; and it promised the ability to update to our product every three weeks.  But it had some painful failure modes that were exposed all too often because our reality is messy.

Our reality was that:

1. Bugs from the previous sprint ate up wildly varying amounts of our time each sprint.
2. Stories changed in scope, and new high-priority stories were added after the sprint started.
3. Available resources changed due to sickness or other personal reasons.
4. The QA team found bugs of wildly varying severity in the new features.
5. Deployment issues occasionally arose.

If these problems were encountered early in the sprint, we could usually recover.  Problems uncovered late in the sprint had more severe repercussions.  Obviously, there was less time to recover without missing the deployment schedule.  But we also found that the further into the development cycle a failure appeared, the more likely it was to prevent every in-progress story from progressing.  Why?  Because we coupled together all stories and commits in a sprint...  in essence, we willingly donned a straitjacket.

This coupling phenomenon where one story, or even one commit, can torpedo every story in a sprint can be explained by this observation:

Planning has as a primary goal the decomposition of high-level deliverables so that developers can work independently.  For QA testing of the deliverables, the independent pieces need to be reconstituted into a recognizable feature.  For deployment, all scheduled features need to be reconstituted into a single artifact.

This is where the original draft blog post ended.  Shortly after I drafted it, I became the CTO of Roomkey and addressed the issues above by adopting a continuous deployment model.  It was not easy to get from "here" to "there" but the payoff was worth it.  We parallelized and decoupled stories, invested in automated testing to find problem early and changed our processes fundamentally.  Our approach probably will not work for most companies.

The biggest challenge was getting developers to buy into their responsibility for finding bugs early.  Most developers accept responsibility for the bugs that they introduce.  Fewer, but still many, accept responsibility for proactively finding bugs in the code for which they are responsible.  Too few accept the collective responsibility of finding bugs (before delivery to QA) resulting from the integration of their code with the code of other developers.  At Roomkey, this last challenge was a struggle.  In a mature code base with many authors, I believe that a robust test suite is one of the best ways to reduce the number of regressions.