The remedian is an approximation of the median that can be computed using only $O(\log{n})$ storage. The algorithm was originally presented in The Remedian: A Robust Averaging Method for Large Data Sets by Rousseeuw and Bassett (1990). The core of it is on the first page:

Let us assume that $n = b^k$, where $b$ and $k$ are integers (the case where $n$ is not of this form will be treated in Sec. 7. The remedian with base $b$ proceeds by computing medians of groups of $b$ observations, yielding $b^{k-1}$ estimates on which this procedure is iterated, and so on, until only a single estimate remains. When implemented properly, this method merely needs $k$ arrays of size $b$ that are continuously reused.

The implementation of this part in Clojure is so nice that I just had to share.

First, we need a vanilla implementation of the median function. We’re always going to be computing the median of sets of size $b$, where $b$ is relatively small, so there’s no need to get fancy with a linear time algorithm.

1
2
3
4
5
6
7
8

(defn median [coll]
  (let [size (count coll)
        sorted (sort coll)]
    (if (odd? size)
      (nth sorted (int (/ size 2)))
      (/ (+ (nth sorted (int (/ size 2)))
            (nth sorted (dec (int (/ size 2)))))
         2))))

Now we can implement the actual algorithm. We group, compute the median of each group, and recur, with the base case being when we’re left with a single element in the collection:

1
2
3
4
5
6
7

(defn remedian [b coll]
  (if (next coll)
    (->> coll
         (partition-all b)
         (map median)
         (recur b))
    (first coll)))

Because partition-all and map both operate on and return lazy sequences, we maintain the property of only using $O(b \log_{b}{n})$ memory at any point in time.

While this implementation is simple and elegant, it only works if the size of the collection is a power of $b$. If we don’t have $n = b^k$ where $b$ and $k$ are integers, we’ll over-weight the observations that get grouped into the last groups of size $< b$.

Section 7 of the original paper describes the weighting scheme you should use to compute the median if you’re left with incomplete groupings:

How should we proceed when the sample size $n$ is less than $b^k$? The remedian algorithm then ends up with $n_1$ numbers in the first array, $n_2$ numbers in the second array, and $n_k$ numbers in the last array, such that $n = n_1 + n_{2}b + … + n_k b^{k-1}$. For our final estimate we then compute a weighted median in which the $n_1$, numbers in the first array have weight 1, the $n_2$ numbers in the second array have weight $b$, and the $n_k$ numbers in the last array have weight $b^{k-1}$. This final computation does not need much storage because there are fewer than $bk$ numbers and they only have to be ranked in increasing order, after which their weights must be added until the sum is at least $n/2$.

It’s a bit difficult to directly translate this to the recursive solution I gave above because in the final step we’re going to do a computation on a mixture of values from the different recursive sequences. Let’s give it a shot.

We need some way of bubbling up the incomplete groups for the final weighted median computation. Instead of having each recursive sequence always compute the median of each group, we can add a check to see if the group is smaller than $b$ and, if so, just return the incomplete group:

1
2
3
4
5
6
7
8
9
10

(defn remedian-with-leftovers [b coll]
  (let [incomplete-group? #(or (< (count %) b)
                               (seq? (last %)))]
    (loop [coll coll]
      (if (next coll)
        (->> coll
             (partition-all b)
             (map #(if (incomplete-group? %) % (median %)))
             (recur))
        coll))))

For example, if we were using the mutable array implementation proposed in the original paper to compute the remedian of (range 26) with $b = 3$, the final state of the arrays would be:

In our sequence based solution, the final sequence will be ((4 13 (19 22 (24 25)))).

Now, we need to convert these nested sequences into [value weight] pairs that could be fed into a weighted median function:

1
2
3
4
5
6
7
8
9
10
11
12
13

(defn weight-leftovers [b nested-elements]
  (loop [vw-pairs []
         nested-elements nested-elements
         weight 1]
    (let [element (first nested-elements)]
      (cond
       (next nested-elements) (recur (conj vw-pairs [element weight])
                                     (next nested-elements)
                                     weight)
       (seq? element) (recur vw-pairs
                             element
                             (/ weight b))
       :else (conj vw-pairs [element weight])))))

Instead of weighting the values in array $j$ with weight $b^{j-1}$, we’re weighting it at $\frac{b^{j-1}}{b^{k}}$. Dividing all the weights by a constant will give us the same result and this is slightly easier to compute recursively, as we can just start at 1 and divide by $b$ as we descend into each nested sequence.

If we run this on the (range 26) with $b = 3$, we get:

1
2
3
4

user> (->> (range 26)
           (remedian-with-leftovers 3)
           (weight-leftovers 3))
[[4 1/3] [13 1/3] [19 1/9] [22 1/9] [24 1/27] [25 1/27]]

Finally, we’re going to need a weighted median function. This operates on a collection of [value weight] pairs:

1
2
3
4
5
6
7
8
9
10
11
12

(defn weighted-median [vw-pairs]
  (let [total-weight (->> vw-pairs
                          (map second)
                          (reduce +))
        middle-weight (/ total-weight 2)
        sorted-pairs (sort-by first vw-pairs)
        sorted-pairs-cum-weight (reductions (fn [[_ cum-weight] [v w]]
                                              [v (+ cum-weight w)])
                                            sorted-pairs)]
    (->> sorted-pairs-cum-weight
         (filter #(<= middle-weight (second %)))
         (ffirst))))

We can put it all together and redefine the remedian function to deal with the case where $n$ isn’t a power of $b$:

1
2
3
4
5

(defn remedian [b coll]
  (->> coll
       (remedian-with-leftovers b)
       (weight-leftovers b)
       (weighted-median)))

The remedian is fun, but in practice I prefer to use the approximate quantile methods that were invented a few years later and presented in Approximate Medians and other Quantiles in One Pass and with Limited Memory by Manku, Rajagopalan, and Lindsay (1998). There’s a high-quality implementation you can use in Clojure via Java interop in Parallel Colt’s DoubleQuantileFinderFactory.

@thattommyhall posted a fun question on Twitter:

If you type your name on a keyboard marked as qwerty but set to Dvorak and keep reinputting what comes out, will it ever say your name?

— !!!!!11111oneoneone (@thattommyhall) July 31, 2014

The best answer was “yes because group theory” and @AnnaPawlicka demonstrated it was true for her name:

@thattommyhall Yes. I can confirm that. :) pic.twitter.com/Vubkf1ltoK

— Anna Pawlicka (@AnnaPawlicka) July 31, 2014

But is it really true? And if so, how many iterations will it take to get the target string? I turned to Mathematica…

1
2
3
4
5
6
7
8
9
10

qwerty =
  {"-", "=",
   "q", "w", "e", "r", "t", "y", "u", "i", "o", "p", "[", "]", "\\",
   "a", "s", "d", "f", "g", "h", "j", "k", "l", ";", "'",
   "z", "x", "c", "v", "b", "n", "m", ",", ".", "/"};
dvorak =
  {"[", "]",
   "'", ",", ".", "p", "y", "f", "g", "c", "r", "l", "/", "=", "\\",
   "a", "o", "e", "u", "i", "d", "h", "t", "n", "s", "-",
   ";", "q", "j", "k", "x", "b", "m", "w", "v", "z"};

1
2
3
4

KeyGraph[from_, to_] :=
 Graph[
  MapThread[#1 -> #2 &, {from, to}],
  VertexLabels -> "Name", DirectedEdges -> True]

This allows us to visualize the mapping of keys from one layout to another:

1

KeyGraph[dvorak, qwerty]

There is a single directed edge going from each character to the one that will be displayed when you type it. There are 3 keys that remain unchanged, 2 pairs of swapped keys, and 2 large cycles of keys.

We can get these groups programmatically using the ConnectedComponents function:

1
2
3
4

TableForm @
 Sort @
  ConnectedComponents @
   KeyGraph[dvorak, qwerty]

1
2
3
4
5
6
7

\
a
m
] =
, w
. e y t f g u c i d h j k v
[ - ' q p r o l / s n ; z x b

It will take the length of the cycle the letter is in to get the letter we want. For a given word, we won’t get all the letters we want unless we’ve iterated some multiple of the length of the cycles each letter is in. Let’s apply the Least Common Multiple function to see the worst case where there is a letter from each cycle:

1
2
3
4

LCM @@
 Length /@
  ConnectedComponents @
   KeyGraph[dvorak, qwerty]

1

210

Looks like Anna got lucky that her name only consists of letters in a cycle of length 1 and 15.

For fun, here’s the graph we get if we use Colemak instead of Dvorak:

1
2
3
4
5
6
7

colemak =
  {"-", "=",
   "q", "w", "f", "p", "g", "j", "l", "u", "y", ";", "[", "]", "\\",
   "a", "r", "s", "t", "d", "h", "n", "e", "i", "o", "'",
   "z", "x", "c", "v", "b", "k", "m", ",", ".", "/"};

KeyGraph[colemak, qwerty]

One cycle of length 14, one cycle of length 3, and the rest are just letters that map back to themselves.

1
2
3
4

LCM @@
 Length /@
  ConnectedComponents @
   KeyGraph[colemak, qwerty]

1

42

I love REPL Driven Development. My style is to write expressions directly in the file that I’m working on and to use C-x C-e to view the value of the last command in the minibuffer.

Being able to move my cursor to a sub-expression and see the value of that expression immediately feels like a superpower. I love this ability and it’s one of the things that keeps me locked into Clojure+Emacs as my preferred enviroment.

This power can be taken to the next level by making custom evaluation commands that run whatever you want on the expression at your cursor.

The Basic Pattern

Let’s start by looking at the Elisp that defines cider-eval-last-sexp, which is what gets invoked when we press C-x C-e:

1
2
3
4
5
6
7

(defun cider-eval-last-sexp (&optional prefix)
  "Evaluate the expression preceding point.
If invoked with a PREFIX argument, print the result in the current buffer."
  (interactive "P")
  (if prefix
      (cider-interactive-eval-print (cider-last-sexp))
    (cider-interactive-eval (cider-last-sexp))))

The important part is that we can use cider-last-sexp to get the expression before the cursor as a string and we can evaluate a string by passing it to cider-interactive-eval. We’ll write some basic Elisp to make a new function that modifies the string before evaluation and then we’ll bind this function to a new key sequence.

The essential pattern we’ll use is:

1
2
3
4
5
6
7
8

(defun custom-eval-last-sexp ()
  (interactive)
  (cider-interactive-eval
    (format "(require 'some-namespace)
             (some-namespace/some-fn %s)"
            (cider-last-sexp))))

(define-key cider-mode-map (kbd "C-c c") 'custom-eval-last-sexp)

If you happen to still be using Swank or nrepl.el, you should use swank-interactive-eval and swank-last-sexp or swank-interactive-eval and nrepl-last-sexp.

Let’s look at some of the useful things we can do with this…

Collections

I frequently deal with collections that are too big to display nicely in the minibuffer. It’s nice to be able to explore them with a couple keystrokes. Here’s a simple application of the pattern that gives us the size of the collection by just hitting C-c c:

1
2
3
4
5
6
7

(defun count-last-expression ()
       (interactive)
       (cider-interactive-eval
         (format "(count %s)"
                 (cider-last-expression))))

(define-key cider-mode-map (kbd "C-c c") 'count-last-expression)

Another useful one is to just show the nth value. This one is a little more interesting because it requires a parameter:

1
2
3
4
5
6
7

(defun nth-from-last-expression (n)
       (interactive "p")
       (cider-interactive-eval
         (format "(nth %s %s)"
                 (cider-last-expression) n)))

(define-key cider-mode-map (kbd "C-c n") `nth-from-last-expression)

If you just use C-c n, Emacs defaults the parameter value to 1. You can pass an argument using Emacs’ universal argument functionality. For example, to get the 0^th element, you could either use C-u 0 C-c n or M-0 C-c n.

Write to File

Sometimes the best way to view a value is to look at it in an external program. I’ve used this pattern when working on Clojure code that generates SVG, HTML, and 3D models. Here’s what I use for 3D modeling:

1
2
3
4
5
6
7
8
9

(defun spit-scad-last-expression ()
  (interactive)
  (cider-interactive-eval
    (format    
      "(require 'scad-clj.scad)
       (spit \"eval.scad\" (scad-clj.scad/write-scad %s))"
      (cider-last-expression))))

(define-key cider-mode-map (kbd "C-c 3") 'spit-scad-last-expression)

This writes the eval.scad file to the root directory of the project. It’s great because OpenSCAD watches open files and automatically refreshes when they change. You can run this on an expression that defines a shape and immediately see the shape in another window. I used this technique in my recent presentation on 3D printing at the Clojure NYC meetup and I got feedback that this made the live demos easier to follow.

Here’s what it looks like when you C-c 3 on a nested expression that defines a cube:

View Swing Components

If you have to use Swing, your pain can be slightly mitigated by having a quick way to view components. This will give you a shortcut to pop up a new frame that contains what your expression evaluates to:

1
2
3
4
5
6
7
8
9
10
11

(defun frame-last-expression ()
  (interactive)
  (cider-interactive-eval
    (format    
     "(doto (javax.swing.JFrame. \"eval\")
        (.. (getContentPane) (add %s))
        (.pack)
        (.show))"
     (cider-last-expression))))

(define-key cider-mode-map (kbd "C-c f") 'frame-last-expression)

This plays nicely with Seesaw, but doesn’t presume that you have it on your classpath. Here’s what it looks like when you C-c f at the end of an expression that defines a Swing component:

Benchmarking with Criterium

In A Few Interesing Clojure Microbenchmarks, I mentioned Hugo Duncan’s Criterium library. It’s a reliable way of measuring the performance of an expression. We can bring it closer to our fingertips by making a function for benchmarking an expression instead of just evaluating it:

1
2
3
4
5
6
7
8

(defun benchmark-last-expression ()
  (interactive)
  (cider-interactive-eval
    (format "(require 'criterium.core)
             (criterium.core/quick-benchmark %s)"
            (cider-last-expression))))

(define-key cider-mode-map (kbd "C-c b") 'benchmark-last-expression)

Conclusion

I find this simple pattern to be quite handy. Also, when I’m showing off the power of nrepl to the uninitiated, being able to invoke arbitrary functions on whatever is at my cursor looks like pure magic.

I hope you find this useful and if you invent any useful bindings or alternative ways of implementing this pattern, please share!

I recently added text support to the scad-clj 3D modeling library and encountered an interesting bug:

See that 4? No hole! Why?!? All the other holes are there…

Shape Outlines

First, let’s look at how you get the outline of some text in a font in Java:

1
2
3
4
5
6
7
8
9
10

FontRenderContext frc = new FontRenderContext(
        null,
        RenderingHints.VALUE_TEXT_ANTIALIAS_DEFAULT,
        RenderingHints.VALUE_FRACTIONALMETRICS_DEFAULT);
Font font = new Font("Andale Mono", Font.PLAIN, 12);
String myText = "1234567890";
PathIterator path = font
       .createGlyphVector(frc, myText)
       .getOutline()
       .getPathIterator(null, 0.01d);

We end up with a PathIterator that traces along the outline of the character. This code uses the version of getPathIterator that specifies “flatness”, which means that we get back a path strictly made up of straight line segments that approximate the curves.

Characters that are made from a single filled polygon are relatively easy; there is a single path and the bounded area is what gets filled:

The complexity comes when the path crosses over itself or if it is discontinuous and contains multiple outlines:

The JavaDocs for PathIterator explain a bit about how to actually determine what is inside the path. All of the fill areas are determined using the WIND_EVEN_ODD rule: a point is in the fill area if it is contained by an odd number of paths.

For example, the dotted zero is made up of three paths:

1. The outline of the outside of the oval
2. The outline of the inside of the oval
3. The outline of the dot

The points inside #1 but outside #2 are in 1 area and the points inside #3 are inside 3 areas.

Counting Areas

For each path, we need to count how many other paths contain it. One way is to use java.awt.geom.Path2D.Double to make a Shape and then use the contains(double x, double y) method to see if any of the points from the other paths are in it.

I incorrectly assumed that each Shape contained at least one of the points that define it’s outline. It usually does, which is why all the other holes were properly rendered, but it doesn’t for some shapes, including triangles in certain orientations!

The JavaDoc for Shape says that a point is considered to lie inside a Shape if and only if:

1. It lies completely inside the Shape boundary or
2. It lies exactly on the Shape boundary and the space immediately adjacent to the point in the increasing X direction is entirely inside the boundary or
3. It lies exactly on a horizontal boundary segment and the space immediately adjacent to the point in the increasing Y direction is inside the boundary.

The three points defining the triangle that form the hole in 4 don’t meet any of these criteria, so instead of counting as being in 2 paths (itself and the outer outline), it was counted as being in 1. The fix was to explicitly define a path as containing itself.

I’ve been doing some 3D printing for my next keyboard project and I’ve got a workflow that I’m pretty happy with that I’d like to share.

When I first started trying to make models a month ago, I tried Blender. It’s an amazing beast, but after a few hours of tutorials it was clear that it would take a while to get proficient with it. Also, it is really designed for interactive modeling and I need something that I can programmatically tweak.

OpenSCAD

A couple of friends suggested OpenSCAD, which is touted as “the programmers’ solid 3D CAD modeler.” It provides a power set of primitive shapes and operations, but the language itself leaves a bit to be desired. This isn’t a beat-up-on-SCAD post, but a few of the things that irked me were:

• Strange function application syntax (parameters in parens after the function name with an expression or block following the closing paren)
• Unclear variable binding rules (multiple passes are made over the code and the results of changing a variable may affect things earlier in the code unexpectedly)
• No package/namespace management
• Multiple looping constructs that depend on what you are going to do with the results, not on how you want to loop

scad-clj

Fortunately, Matt Farrell has written scad-clj, an OpenSCAD DSL in Clojure. It addresses every issue I had with OpenSCAD and lends itself to a really nice workflow with the Clojure REPL.

To get started using it, add the dependency on [scad-clj "0.1.0"] to your project.clj and fire up your REPL.

All of the functions for creating 3D models live in the scad-clj.model namespace. There’s no documentation yet, so in the beginning you’ll have to look at the source for model.clj and occassionally the OpenSCAD documentation. Fortunately, there really isn’t much to learn and it’s quite a revelation to discover that almost everything you’ll want to do can be done with a handful of functions.

Here’s a simple model that showcases each of the primitive shapes:

1
2
3
4
5

(def primitives
  (union
   (cube 100 100 100)
   (sphere 110)
   (cylinder 10 150)))

Evaluating this gives us a data structure that can be converted into an .scad file using scad-clj.scad/write-scad to generate a string and spit.

1
2

(spit "post-demo.scad"
      (write-scad primitives))

We’re going to use OpenSCAD to view the results. One feature of OpenSCAD that is super useful for this workflow is that it watches opened files and automatically refreshes the rendering when the file is updated. This means that we can just re-evaluate our Clojure code and see the results immediately in another window:

scad-clj makes all new primitive shapes centered at the origin. We can use the shape operator functions to move them around and deform them:

1
2
3
4
5
6
7
8
9

(def primitives
  (union
   (->> (cube 100 100 100)
        (rotate (/ Math/PI 4) [1 1 1])
        (translate [150 0 0]))
   (->> (sphere 70)
        (scale [1/2 1/2 2])
        (translate [-150 0 0]))
   (cylinder 10 160)))

I snuck union into those examples. Shapes can also be combined using intersection, difference, and hull. It’s pretty incredible how much can be done with just these. For example, here’s the latest iteration of my keyboard design built using clj-scad:

3D Printing

Once your design is complete, you can use OpenSCAD to export it as an STL file which can then be imported to software like ReplicatorG or Makerware for processing into an .x3g file that can be printed:

I’ve been busy with a few other keyboard projects since my last post on my ErgoDox build. While working on those projects, I’ve gotten some parts and done a few more tweaks to the ErgoDox that I’d like to share.

PBT DSA Keycaps

The biggest improvement was switching the keycaps. Originally I had used keycaps from WASD Keyboards that were designed to be used with a normal keyboard. Typical keyboards use keycaps that are very similar to DCS profile caps, which have different profiles for different rows:

Source: Signature Plastics

In contrast, DSA keycaps have concave spherical tops and are uniform in profile:

I had ordered a set of DSA keycaps from Signature Plastics for another project and decided to try them out on the ErgoDox:

I was surprised with how much better these felt, particularly on the thumb cluster. I now realize that a lot of my discomfort reaching the upper keys on the the thumb cluster came from their relatively high profile.

The DSA keycaps are also made out of PBT plastic instead of ABS. They have a nice textured feel and the plastic is supposed to be much more robust. As I said in my last post, Pimp My Keyboard shop has PBT DCA blank sets for the ErgoDox for $43, which is a great deal and is definitely the way to go if you’re sourcing your own parts.

TRRS Connector

DigiKey finally got the TRRS connectors in stock and sent them to me. I was concerned that they wouldn’t fit in my lower profile case, but a little Dremel action made it work:

The keyboard didn’t work after I added the connector. It worked fine if I just had the right side plugged in, but as soon as I connected the left side, neither worked. I took the whole thing apart and used an ohmmeter to test the 4 connections between the two halves. It turned out that all of the connections were there, but there was a little resistance on one of them. I resoldered it more thoroughly and everything worked fine.

Sanding

Finally, I did a little experimentation with wet sanding the sides to remove some of the burn marks from the paper during the laser cutting and to give a more even finish. I used 400 grit sandpaper and made a little progress:

Acrylic dust is nasty stuff! It didn’t make as much of a difference as I hoped. I’m going to do a little more experimentation sanding with acetone to see if I can melt it smoothly and make the 5 layers of acrylic look like one piece.

Next Steps

My next project is going to involve a lot of acrylic bending, so I’m probably going to also take a stab at cutting and bending a stand for the ErgoDox that tents it at a better angle. Any suggestions are appreciated!

The ErgoDox is a split ergonomic keyboard project. One of the most notable things about it is that you can’t buy this keyboard — you have to build it yourself! The parts list is available on the site, along with the designs for the PCB and case.

I recently built one, sourcing the parts myself, and I’d like to share what I’ve learned.

Reference Build

The easiest way to build one is to get in on one of the group-buys of full kits organized by Massdrop. Their kits have become the most common build, with options for different style Cherry keyswitches and either a classic case or one with wrist rests.

After some investigation, I decided I could build something very similar without the kit.

Ordering the Parts

There are a few major things that you need to build an ErgoDox:

• Printed circuit boards (PCB)
• Teensy controller
• Keyswitches
• Key caps
• A bunch of little electronic components
• A case

I obtained the PCB, Teensy, and keyswitches from Mechanical Keyboards.

I managed to pick up all the little electronic components from DigiKey, except for the TRRS connectors which are currently unavailable. The TRRS connectors are the headphone-style jacks that are used to connect the two halves. I decided to not use TRRS and to just solder basic wires directly onto the board.

The PCBs were \$38, the keyswitches were \$49, the Teensy was \$22 (but can be bought for less), and the rest of the components came out to about \$20. This \$129 covers everything needed except for the case and the keycaps. For reference, the Massdrop group buy is \$199 for everything excluding the keycaps, so I had roughly $70 to spend on the case before it would have made financial sense to wait for another group buy opportunity.

Making the Case

There are really two options for making a case:

1. 3-D printing
2. Laser cut acrylic

The designs for the case are available on Shapeways, but it comes out to almost \$200, even when choosing the least expensive options for everything! I considered printing it myself on the Makerbots at my office, but I was skeptical that the older models we have would result in acceptable quality.

Laser cutting the acrylic seemed like the way to go, so I picked up 5 12”x12” sheets of 3mm opaque white acrylic from Canal Plastics for \$7 a sheet. They can be ordered from Amazon for basically the same price. The design used in Massdrop’s kit uses 3mm sheets for the top and bottom and 5mm sheets for the middle 3 layers, but I believed (hoped!) that I could make it all fit in a slimmer case.

I had never laser cut anything before, but my coworker Trammell has a ton of experience with it and helped me out. He’s a member at NYC Resistor and they have a laser! We used Inkscape to generate PDFs and then used his command line laser cutting tool to send them over to the Epilog laser cutter. We were able to get 2 layers out of each sheet, as you can see in these action shots:

And the final result:

It took just under 27 minutes of actual laser time, which at \$0.75/min came out to \$20. \$55 for the case was a lot more than I expected, but it still kept the cost below \$199. It seems like this is the part that would offer the most savings if done as part of a group buy.

Keycaps

Massdrop usually offers a separate group buy of PBT DCS keycaps when they offer the full kit. I decided to try using standard keycaps and to buy the missing ones separately. This was a big mistake. A proper set of keycaps for the ErgoDox requires 12 1.5x keycaps, which are way too expensive when bought separately. Only later did I discover that the Pimp My Keyboard shop has PBT DCA blank sets for the ErgoDox for $43.

I got my keycaps from WASD Keyboards. They have a pretty slick keycap designer. I used it with my kids and we came up with a design they were happy with (my 3 year-old is currently obsessed with rainbows):

I decided to take advantage of their ability to print whichever letters I want on each key to make this be the Colemak layout. I’ve got the layout commited to muscle memory, but sometimes my kids want to type on my keyboard and it’s annoying to switch to QWERTY so the keys match the letters printed on them.

Putting It Together

I did the actual soldering and assembly in the Hackerlab at my office:

To put it together, I mostly followed Massdrop’s assembly instructions. I did a decent job soldering (it’s almost 400 solder points), but I wish that I had watched the EEVblog videos on soldering beforehand. That guy knows what he’s talking about.

Because I used 3mm sheets instead of the recommended 5mm, there wasn’t a lot of clearance and I had to get creative. The keyswitches stuck out a little too far on the bottom of the PCBs, so I used flush cutters to trim the leads and the plastic nubs:

Originally, I used the recommended header pins to connect the Teensy to the PCB, but that brought the USB connector too high and prevented the top layer from fitting. Instead, Trammell suggested I mount it directly on the PCB. Desoldering the Teensy was really, really hard. The throughholes are tiny and there are so many of them! I ended up using the Dremel to clear some space around it and then used the cutting wheel to slice the header pins. Unfortunately, I got the angle wrong one time and took out a nice chunk of the Teensy’s bottom:

I got a replacement Teensy. With some electrical tape on the bottom, I put it directly on the PCB which got me the clearance I needed:

The mini-USB port on the back is about 5mm tall, so it also prevented the layers from fitting together nicely. I remedied that by dremeling a little into the 4th layer. It’s not beautiful, but it’s in the back and it’s good enough.

The Massdrop kit includes metal screws and nuts that are seriously sharp and will gouge the surface you put the ErgoDox on:

I decided to go with white nylon flat-head screws and nuts for both aesthetics and the safety of my desk:

The Dremel came in handy again for making countersinks and for shortening the screws:

The only other deviation from the original design was that I didn’t use the audio jack style connector. This was motivated by the fact that Digikey didn’t have it in stock and that the jack would be too tall for the 3mm sheets. I just soldered the wires directly onto the PCB:

Programming the Teensy

I used the most excellent ErgoDox Layout Configurator provided by Massdrop to make my own modified layout that matches what I use on my Kinesis Advantage. It was pretty straightforward. I made one of the inner 1.5x keys switch to a QWERTY layer as a courtesy to anyone else who wants to try it out.

Final Product

Here’s how it came out:

Side-by-side comparison with one of my coworkers’ build of Massdrop’s kit with the palm rest:

And here you can see just how much thinner the case is with all 3mm sheets:

The keycaps I used were taller than the PBT DCS ones sold by Massdrop, so it ended up being close to the same height.

Review and Next Steps

The design and build were fun, but the real test is actually typing on it. Like the Kinesis Advantage and Truly Ergonomic, the ErgoDox features a columnar layout with staggered keys, which is much more comfortable for me than the traditional layout. Unfortunately, the PCB is flat and I find it to be less comfortable than the Kinesis’s bowl shape. It’s hard to manufacture curved or flexible PCBs, so it’s understandable that this DIY project wouldn’t require it.

A common complaint about the ErgoDox is that the thumb clusters are too close to the other keys. This turned out to be a real problem for me as it requires a serious contortion for me to his the top keys of the thumb cluster. On the Kinesis, I have these mapped to the oft used Ctrl and Alt keys. It was so bad that I ended up having to remap the bottom corner keys to Ctrl and Alt and relegate the top 2 keys to less used ones. I’m not the only one who has struggled with this and the best solution I’ve seen so far is AcidFire’s Grand Piano design:

Another issue is that I chose the wrong keyswitches. My primary keyboard is the Kinesis Advantage LF, which uses Cherry MX reds. I love them, but they are really hard to find at a reasonable price. I wasn’t about to spend $160 on the keyswitches, so I opted for Cherry MX blacks. They are linear feel like the reds, but much stiffer, with an activation force of 60cN instead of 45cN. This didn’t seem like a big deal when I tried it out with individual switches from a sampler set, but it was a whole other experience when trying to type on a full set. It’s much harder to type on and I could feel my fingers straining very quickly.

The last issue is that the ErgoDox really need to be tented at an angle for maximum comfort. My plan was to use this as an ergonomic solution while traveling and I have some designs that would make it easy to attach to my laptop in a tented position. Something like this:

I decided to hold off on this until I have a solution for the other issues I listed.

Conclusion

Overall, this was an incredibly fun project and I learned a ton about how keyboards are made. For anyone who’s waiting for the next Massdrop group buy of a kit, you should know that it can be done by yourself for about the same price if you can get access to a laser cutter or CNC mill to make the case. I’m sure someone can be more creative and come up with an even more accessible solution.

Unfortunately, I’m not thrilled with the actual typing experience, so I can’t recommend it over the Kinesis Advantage. Some people love it, so try it out for yourself if you can or at least print out a stencil of it before committing.

My plan is to take what I’ve learned and to try and build something that’s an even better fit for my travel usage. Hopefully I can procure some Cherry reds for a reasonable price in the future…

There are a lot of great essays about the power and joy of LISP. I had read a bunch of them, but none convinced me to actually put the energy in to make it over those parentheses-shaped speed bumps. A part of me always wanted to, mostly because I’m convinced that our inevitable robot overlords will have to be programs that write programs and everything I had heard made me think that this would likely be done in a LISP. It just makes sense to be prepared.

Almost two years ago, a coworker showed me some gorgeous code that used Clojure’s thrush macro and I fell in love. I found myself jonesing for C-x C-e whenever I tried going back to Java. I devoured Programming Clojure, then The Joy of Clojure. In search of a purer hit, I turned to the source: McCarthy’s original paper on LISP. After reading it, I realized what someone could have told me that would have convinced me to invest the time 12 years earlier.

There’s a lot of interesting stuff in that paper, but what really struck me was that it felt like it fit into a theoretical framework that I thought I already knew reasonably well. This post isn’t about the power of LISP, which has been covered by others better than I could. Rather, it’s about where LISP fits in the world of computation.

None of what I’m about to say is novel or rigorous. I’m pretty sure that all the novel and rigorous stuff around this topic is 50 – 75 years old, but I just wasn’t exposed to it as directly as I’m going to try and lay out.

The Automaton Model of Computation

One of my favorite classes in school was 15-453: Formal Languages, Automata, and Computation, which used Sipser’s Introduction to the Theory of Computation:

One aspect that I really enjoyed was that there was a narrative; we started with Finite State Automata (FSA), analyzed the additional power of Pushdown Automata (PDA), and saw it culminate in Turing Machines (TM). Each of these models look very similar and have a natural connection: they are each just state machines with different types of external memory.

The tape in the Turing Machine can be viewed as two stacks, with one stack representing everything to the left of the current position and the other stack as the current position and everything to the right. With this model, we can view the computational hierarchy (FSA –> PDA –> TM) as just state machines with 0, 1, or 2 stacks. I think it’s quite an elegant representation and it makes the progression seem quite natural.

A key insight along the journey is that these machines are equivalent in power to other useful systems. A sizable section in the chapter on Finite State Automata is dedicated to their equivalence with Regular Expressions (RegEx). Context Free Grammars (CFG) are actually introduced before Pushdown Automata. But when we get to Turing Machines, there’s nothing but a couple paragraphs in a section called “Equivalence with Other Models”, which says:

Many [languages], such as Pascal and LISP, look quite different from one another in style and structure. Can some algorithm be programmed in one of them and not the others? Of course not — we can compile LISP into Pascal and Pascal into LISP, which means that the two languages describe exactly the same class of algorithms. So do all other reasonable programming languages.

The book and class leave it at that and proceed onto the limits of computability, which is the real point of the material. But there’s a natural question that isn’t presented in the book and which I never thought to ask:

While we know that there are many models that equal Turing Machines, we could also construct other models that equal FSAs or PDAs. Why are RegExs and CFGs used as the parallel models of computation? With the machine model, we were able to just add a stack to move up at each level – is there a natural connection between RegExs and CFGs that we extrapolate to find their next level that is Turing equivalent?

The Chomsky-Schützenberger Hierarchy

It turns out that the answers to these questions were well covered in the 1950’s by the Chomsky-Schützenberger Hierarchy of Formal Grammars.

The left-hand side of the relations above are the automaton-based models and the right-hand side are the language-based models. The language models are all implemented as production rules, where some symbols are converted to other symbols. The different levels of computation just have different restrictions on what kind of replacements rules are allowed.

For instance RegExs are all rules of the form $A \to a$ and $A \to aB$, where the uppercase letters are non-terminal symbols and the lowercase are terminal. In CFGs, some of the restrictions on the right-hand side are lifted. Allowing terminals to appear on the left-hand side lets us make rules that are conditional on what has already been replaced, which appropriately gets called “Context Sensitive Grammars.” Finally, when all the rules are lifted, we get Recursively Enumerable languages, which are Turing equivalent. The Wikipedia page for the hierarchy and the respective levels is a good source for learning more.

When you look at the definition of LISP in McCarthy’s paper, it’s much closer to being an applied version of Chomsky’s style than Turing’s. This isn’t surprising, given that they were contemporaries at MIT. In McCarthy’s History of Lisp, he expicitly states that making a usable version of this other side was his goal:

These simplifications made LISP into a way of describing computable functions much neater than the Turing machines or the general recursive definitions used in recursive function theory. The fact that Turing machines constitute an awkward programming language doesn’t much bother recursive function theorists, because they almost never have any reason to write particular recursive definitions, since the theory concerns recursive functions in general. They often have reason to prove that recursive functions with specific properties exist, but this can be done by an informal argument without having to write them down explicitly. In the early days of computing, some people developed programming languages based on Turing machines; perhaps it seemed more scientific. Anyway, I decided to write a paper describing LISP both as a programming language and as a formalism for doing recursive function theory.

Here we have it straight from the source. McCarthy was trying to capture the power of recursive definitions in a usable form. Just like the automata theorists, once the linguists theorist hit Turing completeness, they focused on the limits instead of the usage.

Theoreticians are more interested in the equality of the systems than the usability, but as practitioners we know that it matters that some problems are more readily solvable in different representations. Sometimes it’s more appropriate to use a RegEx and sometimes an FSA is better suited, even though you could apply either. While nobody is busting out the Turing Machine to tackle real-world problems, some of our languages are more influenced by one side or the other.

Turing Machines Considered Harmful

If you track back the imperative/functional divide to Turing Machines and Chomsky’s forms, some of the roots are showing. Turing Machines are conducive to a couple things that are considered harmful in larger systems: GOTO-based¹ and mutation-centric² thinking. In a lot of cases, we’re finding that the languages influenced by the language-side are better suited for our problems. Paul Graham argues that the popular languages have been steadily evolving towards the LISPy side.

Anyway, this is a connection that I wish I had been shown at the peak of my interest in automata theory because it would have gotten me a lot more excited about LISP sooner. I think it’s interesting to look at LISP as something that has the same theoretical underpinnings as these other tools (RegEx and CFG) that we already acknowledged as vital.

Thanks to Jason Liszka and my colleagues at Two Sigma for help with this post!

I was recently looking for an interesting relational dataset for another project and the idea of using the dependencies for every Clojure project on GitHub came up. It turns out that it’s possible to download almost every project.clj using Tentacles, so I decided to…

The most annoying part was dealing with GitHub’s rate limits, but after waiting a few hours I had them all on local disk and was able to play around. I haven’t gotten to dig into the data for the actual project I’m doing, but there were a couple simple queries that I thought were worth sharing.

Most frequently included packages

I was able to download 10770 project.clj files. Here are the 50 most frequently included packages listed in their :dependencies:

I think it makes a nice hit-list of projects to check out!

A couple interesting things jumped out at me:

1. 12.5% of Clojure projects on GitHub are using Compojure. Impressive.
2. congomongo, com.novemberain/monger, com.datomic/datomic-free, mysql/mysql-connector-java, and postgresql/postgresql are all clustered together in the low 100’s.

Most frequently applied licenses

Just over half of the project.clj’s don’t contain a :license. Here are the most popular:

The EPL’s dominance doesn’t come as a surprise, given Clojure’s use of it for the core libraries.

23 projects have “WTF” or “fuck” in their license string:

Conclusion

I’d like to share a mirror of just the project.clj files wrapped up in a single download, but I want to be conscientious of the variety of licenses. I’ll clean up the code for pulling and summarizing all this data soon so others can play with it. In the meantime, feel free to suggest other analyses that could be done on these…

A quine is a program which takes no input and outputs a copy of its own source code. There’s a history of making challenges out of variants on the idea (shortest quine, Ouroboros Programs, Multiquines). I’d like to propose a new variant for our modern social age: the Quine Tweet.

Inspiration

Last year I was working through 4Clojure and I had to reacquaint myself with how to implement one for Problem #125: Gus’s Quinundrum.

A few months later, I saw this tweet from Gary Trakhman:

So simple! (defn send-tweet [tweet] (api/statuses-update :oauth-creds my-creds :params {:status tweet}))

— Gary Trakhman (@gtrakGT) November 20, 2013

Seeing him tweet source code that tweets got me thinking about code that tweets its own source code. Could a Quine Tweet be written? I took a stab at adapting my Clojure code for Gus’s Quinundrum, but I just couldn’t make it fit in 140 characters.

Enter Wolfram

The next day, this came across my dash:

Hello world! – tweeting with #wolframlang on @Raspberry_Pi using Send["Twitter","Hello world!" …]

— Stephen Wolfram (@stephen_wolfram) November 21, 2013

Maybe this will enable my impossible dream of a Quine Tweet…

I finally got a Raspberry Pi running with the Wolfram Language and I made it happen:

\{o, c\} = FromCharacterCode\[\{\{92, 40\}, \{92, 41\}\}\] ; SendMessage\["Twitter", StringReplace\[InString\[$Line\], \{o -> "", c -> ""\}\]\]

— Matt Adereth (@adereth) January 8, 2014

If you paste it into a notebook and evaluate, you’ll get prompted for authorization and it’ll post itself. Here’s a brief explanation of what it does:

1. $Line is the count of input expressions that have been evaluated.
2. InString is a function that gets the input for the i^th input expression. It returns a string that has some extra escaped parentheses.
3. 92 is the ASCII code for \\. 40 and 41 are the codes for ( and ). FromCharacterCode can take a list of lists of ASCII codes and return a list of strings. The list is destructured into the variables o (open) and c (close).
4. StringReplace is then used to clean up the extra parentheses.
5. SendMessage is the new function in the Wolfram language that does all the hard work of posting.

I don’t think this is really in the true spirit of a quine, as having something like InString makes it a bit trivial, but you do what you must when you only have 140 characters!

The Challenge

So, can it be done in any other languages? Here’s what I think are fair restrictions:

1. Any standard Twitter client library for your language can be linked using the language’s normal methods (pom.xml, project.clj, etc.)
2. The authorization token can be supplied outside of source, either interactively or through a text file. I don’t imagine anyone wants to be sharing that…

Bonus points if you manage to make the tweet and source include #quine!