The Broken Weight Problem

Some elderly academics were sitting next to me at the cafe today and they were discussing some mathematical puzzle, "The Broken Weight Problem." I'm not the best eavesdropper so I gathered a few search terms and popped them into Google, and viola.

Basically the idea is this. A merchant accepts goods in 40 pound increments. He uses a simple balance scale and a 40 pound weight to weigh the goods. One day, he accidentally dropped the weight and it broke into four pieces. After a bit of consideration, the merchant realized that, quite amazingly, each piece was an integer number of pounds in weight and, using his broken pieces of the weight and his balance scale, he was able to measure out any integer value from 1 to 40. The question is, what are the weights of the pieces? Hints and solutions after the break

---

Okay, a hint in case you are really stuck. You do realize that with a balance scale, the merchant is able to place some pieces on the other side of the scale which will act as a counter balance? This means that a five pound and a three pound piece can also measure two pounds, for example.

---

Now for solutions. Since we probably have a Common Lisp REPL close by, the easiest thing to do in this day and age is to just plug it in and have a computer solve it. But how do we do this? Well, it is simple enough using Screamer.

I start by grabbing a few libraries I will use, Iterate and, as mentioned, Screamer.

(ql:quickload '(:screamer :iterate))
(use-package :iterate)

First we define a test to see if a given set of piece weights can build an integer:

(defun check-integer (i w x y z)
  (iter (for s1 from (- w) to w by w)
    (finding
     s1 such-that
     (iter (for s2 from (- x) to x by x)
       (finding
        s2 such-that 
        (iter (for s3 from (- y) to y by y)
          (finding
           s3 such-that 
           (iter (for s4 from (- z) to z by z)
             (finding s4 such-that (= i (+ s1 s2 s3 s4)))))))))))

This function is pretty self explanatory. Given a set of weights, each weight can be in one of three places, on the right side of the scale, on the left side of the scale, or not on the scale at all. When applied to the balance of the scale (where zero means we have a balance) these states correspond to a negative value of the weight, a positive value of the weight, and a zero value for the weight. This is exactly what we are doing with these loops. Since there are only three states for each, it is simple to see that this will only require checking $3^{4}$ different possibilities at worst case.

Then we delve into the magic world of nondeterminism.

(screamer::defun stone-split (total-weight)
  (let* ((w (screamer:an-integer-between 1 (1+ total-weight)))
         (x (screamer:an-integer-between w (1+ total-weight)))
         (y (screamer:an-integer-between x (1+ total-weight)))
         (z (- total-weight w x y)))
    (if (and (> z 0)
             (iter (for i from 1 to total-weight)
               (let ((works (check-integer i w x y z)))
                 (always works))))
        (list w x y z)
        (screamer:fail))))

Here we are defining our function that will find zero, one, or several solutions to this problem depending on how we call it and if solutions exist. I left a free parameter total-weight so we can play with it, though it proves a bit boring to play with only that value. Things to note:

1. We need to use the defun from within the screamer package. This version of defun is special as it allows for simulated nondeterministic computation (via CPS I believe, but I'm not the guy to ask about that). The library suggests that you use screamer:define-screamer-package to make a package with the proper defun interned, but I am lazy.
2. The forms using screamer:an-integer-between tell Screamer that the solutions to this problem are some integer in that range. Screamer will handle figuring out which.
3. The screamer:fail form informs Screamer that it has chosen the wrong value. This will force Screamer to backtrack to the last integer range with values left and pick a new one.

We need to execute this function from within a "Nondeterministic Environment," which is commonly either inside a screamer:one-value or screamer:all-values form. So we invoke it like this ( fixed package namespace thanks to Derrell):

(screamer:one-value (stone-split 40))

…and it finds the correct result. Admittedly, this could be solved very simply without the use of Screamer, but I would argue that it requires less mental overhead when and produces much more flexible code using the Screamer route. What is the correct result?

---

I looked at it this way. You have three values a piece of weight $w$ can take, $-w$, 0, or $+w$. Therefore it seems to me that we have a set of equations:

\[ \alpha_i w + \beta_i x + \gamma_i y + \delta_i z = i ~~~~~\forall i \in {\mathbb N}_{1}^{40} \]

Where I use ${\mathbb N}_{1}^{40}$ to denote the natural numbers (starting from 1) less than or equal to 40. We know from the problem description that $w,x,y,z, \in {\mathbb N}_{1}^{40}$ and that $(\alpha, \beta, \gamma, \delta)+1 \in {\mathbb N}_{0}^{2}$. You could go about trying to solve these very over determined equations (edit: Actually it's underdetermined, hence we get multiple solutions. Limiting the values to integers is what makes it hard), however, this all might start looking familiar. This looks very much how you would calculate the value of a number in some (possibly irregular) base where the Latin symbols denote the value of each digit and the Greek symbols denote the value in that digit place. In this case, we are limited to three different values in our digit places, so it seems prudent to use base three. Thus the values of each digit place should be powers of three. Thus the answer should be 1, 3, 9, and 27.

How do we know we will have a solution? We need our trinary representation at least reach 40. Since half of our numbers are negative, we actually need to reach 80 in the positive only encoding. The largest value for four digits of trinary is (+ (* 2 27) (* 2 9) (* 2 3) (* 2 1)) or exactly 80. Also, it is a happy coincidence that our numbers also add up to 40, everything works just fine. If we look at how many unique solutions exist for other total weights we see that it seems that 40 is the largest weight we can get to with four pieces. This is a direct consequence of 80 being the largest 4 digit trinary number.

Total Weight	Number of unique solutions
4	1
5	1
6	2
7	3
8	4
9	5
10	7
11	7
12	9
13	10
14	10
15	11
16	12
17	11
18	12
19	12
20	11
21	11
22	12
23	9
24	9
25	9
26	7
27	7
28	7
29	5
30	5
31	5
32	3
33	3
34	3
35	2
36	2
37	2
38	1
39	1
40	1
41	0
42	0
43	0
44	0
45	0

On LaTeX and Microsoft Word

Sorry, this is a ranty post. Adjust your desire to read appropriately.

I was busy writing my APS abstract this last week. When we got near the end I was having a heck of a time getting Bibtex to work with Latex and insert my references properly. Later on I realized that APS doesn't really allow for citation ala Latex and Bibtex, but whatever. I was struggling with this, and mentioned to my advisor, jokingly, "Man, I hate Latex." He says, also jokingly, "you could use Microsoft Word." I say sure, despite the fact that the APS website says they prefer Latex and that Latex is actually easier for the submitter, MS Word is no problem. In fact, that is kind of the point. I wrote my abstract using Org-Mode precisely because it made little to no assumptions on the end result. I can export to Latex or one of the many other formats or just grab my text and paste it into MS Word with no problems. I can also send it to any human being in the world with a computer and that person can open it and understand what they are seeing. Hell, in a handful of keystrokes I could post it to this blog.

Later, when printing, my advisor changes from his joking suggestion to insist that I use MS Word (presumably so that I can export to a Rich Text Format document that the APS accepts). This will make it easier, right… So, I copy/paste it over to a document and save it as an RTF file. Low and behold, of course, the equations are not interpreted by word. It would take at least 15 minutes and perhaps up to an hour to figure out how to get the proper symbols, fonts, and kerning into the document for submission. The last kick to the nuts is that the APS provides an RTF template, but in order to use it, you must actually type the document into it yourself, by hand. If you copy and paste it into the template something, apparently, will get screwed up. I will repeat that, the American Physical Society requires you to actually, physically, press the keys on your keyboard while their template is open in order to submit an abstract (though I imagine something like xdotool might serve me well here). This is what happens with you use things you don't understand people. You get black magic crap like this.

Point is, I miss my previous colleagues and advisor, nay entire department, nay entire institution where they held the opinion that any individual in the sciences should be using Latex as their format for correspondence. Also, bravo to the APS for encouraging people to use Latex for submitting abstracts.

Time Lapse Fun with FFMPEG and Mencoder

I was in the office early this morning and saw the sun rising. I captured some video of it (my phone can do 30 minutes of 720p, though it doesn't look that good). However, the thirty minutes of video is rather boring to watch in real time. So I decided to speed up the video.

Speeding up the video was actually much more difficult that I thought it would be (and I am somewhat acclimated to the troublesome nature of FFMPEG and Mencoder). Anyway, in order to perform the speed up I used the FFMPEG filter select to only pass every n^th frame. The large the n, the faster the speed up. At the same time I chose to convert to WebM (the phone puts out H.264+AAC and placed in an MPEG4 container format). This produces a video file with only every n^th frame, but the video just hangs for the time it would have been displaying the other frames. To fix this, I then passed it through another program, mencoder. This program fairly similar to ffmpeg in purpose. The mencoder program has a special option, -speed, that will speed up the video stream by a factor you specify. This means that if we use -speed n then we should get the desired video frame rate. Refer to the man pages and FFMPEG manual for more insight for what is happening here.

ffmpeg -i VID_20111025_071454.m4v -vf select='not(mod(n\,50))' -an temp.webm
mencoder -ovc copy -oac copy -speed 50 temp.webm -o faster.webm

This would have been all it would take, however, since I am using Maverick Meerkat, the version of FFMPEG included doesn't have support for filters. This means that, ugh, you can't use the first command. Not unless you install a newer version. I avoid compiling libraries from source like the plague. Instead I added this PPA to my software sources and updated my software. This actually gave a lot of scary errors and almost tricked me into a dist-upgrade to Natty, (shame on you apt, I wouldn't do that to my worst enemy). But in the end, those commands did work (as evidenced by the videos).

The end result, we have a video where only every 50th frame show up in the output. This resulted in a pretty good effect. I didn't actually point the camera at the sunrise as that would cause problems with the contrast and I couldn't balance the camera on the window sill pointing that direction from my office. So it's not as dramatic as an actual sunrise.

I also captured another 30 minutes later that morning as the clouds forming as the air passed off the flatirons was a pretty cool dynamic effect.

Of course, all of this is kind of stupid (neat, to me, but stupid), as time-lapse is usually done by taking individual frames spaced seconds to minutes (or more) apart. Also, there are several options available on the Android Market. Though I wouldn't install them without researching the application and developers.

Fixed Point Emacs Completion

One of those annoying things about GNU Emacs is that when a window is popped up containing completions, it derails what you were doing.

First, completion windows take up half the frame. I can't actually figure out how to change this easily. Think of how you use the completions window. One primary way I use it is: I try to complete a symbol, realize that it doesn't have enough information, then type more and try again. In this case, having so many options doesn't help at all. I only need to know if there the symbol can be completed or if there are multiple possibilities.

Second, the position of the cursor on the screen is almost always changed when a window is popped up, and interestingly enough, not even in a predictable way. This means that if I try to perform a completion which I expect to have only one completion, thus not popping up a window, but it actually has several possibilities, I have an annoying situation. This could happen as a result of a symbol I didn't know about making the completion ambiguous resulting in a pop-up and a partial completion or it could be due to a typo. In either case, I need to examine what is at the command prompt in order to find out the proper course of action. This is unavoidable. What is avoidable, however, is the need to move the command prompt around the screen forcing the user to go searching for the new location.

In addition to these pretty legitimate claims, I also just find the entire process to be jarring. I often find myself kicked out of my current train of thought as I search for where my cursor has gone. Here is an example of how completion tends to work in Emacs.

When these two effects combine, I got so frustrated I started leaving my frames split in half so that completions will show up in the other window without effecting the window I was editing in at all. In a recent Reddit conversation with Stassats, he states that he also always maintains a completion window. To me, this is a big waste of screen space, but at least the point doesn't jump.

There are other solutions to this problem. My guess is that many people struggle with this and each produce their own solution. For instance, here is a post of how to designate a particular window for completions in someones (rather complicated for my taste) completion window setup.

My solution

The code is here, though I can't vouch for it being bug free.

My solution is to have windows pop-up with completions but have those windows be smaller than half the screen. An important distinction is that when a completion window pops up, it will not alter the screen location of the point. In order for this to be the case, we need to pop-up a window in an area of the frame that the cursor isn't utilizing. So, we handle this by identifying where in the frame the point is, then popping up a smaller completion window in either the top or bottom of the frame depending on its location.

To be precise:

1. See if there already is a visible completions window. If one exists, use it.
2. See if the current frame has only one window (when not counting the minibuffer). If it does, we know that a popup is desired.
   1. If the current window is actually the minibuffer, create the popup at the bottom of the frame.
   2. If the point is above the halfway point in the frame, create the popup window at the bottom of the frame.
   3. If below the halfway point, create it at the top of the frame.
3. If it matches none of this, let Emacs do as it would have.

Here is the result:

This works pretty well for me, but I imagine that is just because I might use Emacs in a quirky way. For instance, I usually have one desktop where all of my Emacs windows are. If they are on different desktops, perhaps the "use completions window if 'visible'" won't work very well. I don't know how Emacs handles this. What about terminal emacsclient instances and how does completion there interact with open X windows. All of these things should be configurable.

Anyhow, if anybody else finds this useful and wants to push patches back to me, please do. If anybody wants to grab this code and take over the project, or include it in your project, again, please do.

Other completion extension libraries

While I haven't found anything out there that does exactly what Fixed-Point-Completions does, there are a few libraries that also tweak completion. Most notably, popwin and icicles extend the completions functionality. Icicles is a bit heavy handed for my taste, changing many things in how Emacs functions. Popwin does a lot towards fixing my completion issues, but not enough. The thing which is really missing from both of these is that they still shift the visual location of the point at times.

Modf support on ABCL

No posts in a long time, sorry for that.  Probably going to be dead around here until PhD is taken care of.    I take solace in the fact that nobody reads this blog ;)

One good piece of news that crossed my RSS feed today: ABCL 0.26.2 was released.  Normally this isn't something I would really care that much about, but the change log says they fixed the apply/setf problem, which is a current failing of Modf on ABCL.  This means that, while Modf will still fail the test suite (due to no MOP, which is needed to expand class accessors if the user didn't specify an expander), it will work much more closely to how it does on other Lisps.  I think it is correct to say that Modf will work as long as all expanders are actually specified (i.e. not expanded at run time).  This is great news for any ABCL+Modf users of which I'd bet there are approximately zero.  Maybe now there will be some.

This should just work without any changes to Modf, but I'll try to find time to test it sometime soon.

Emacs Pinky

Whelp, it has happened to me.  After switching to Emacs 2-3 years ago, I have finally developed a repetitive stress injury due to my programming.  I don't think this would have happened with Vim (my old editor), but I have been coding much more these days.  Whatever.

I am resistant to using Viper mode as I think it will mess with the key bindings in the 20 some odd major modes I use every day.  So I am going to try something else.  I am deleting the Ctrl and Shift modifier keys from the X key bindings on the left side of my keyboard and will force myself to use Shift and Ctrl on the right hand side for a while.  Spreading the wear out over both hands should help things a bit.  Of course things are complicated a bit by the fact that this Mac keyboard doesn't have a left control at all.  No biggie with xmodmap.  Just use xev to figure out what keys send what code and make a xmodmap input file like this.

clear control
clear mod1
clear mod4
clear shift

keycode 50 = Shift_L
keycode 62 = Shift_R
keycode 37 = Control_L
keycode 108 = Control_R
keycode 64 = Super_L
keycode 134 = Alt_R
keycode 133 = Alt_L

add shift = Shift_R
add control = Alt_R
add mod1 = Alt_L
add mod4 = Super_L

Oh yeah, if you are using Ubuntu or probably any mainstream distribution, changes to xmodmap are often times intercepted on startup and different key mapping utility is used. in short, make this file as xmodmap in your home space, apply it, then restart the X server. You will probably get a dialog asking you if you want to include these key mappings or not.

Just run xmodmap <input-file> to effect the changes.  Also, I am going to try and mimic the key placement of the older space cadet keyboards, which were made for Emacs.  The Wikipedia page states that a big difference was that the space cadet keyboards had modifier keys in a "thumbable" position.  So I am leaving my left Alt as Alt and setting my right Alt as a Ctrl.  This means that in a few weeks time I should be using thumbs for most Emacs work (and everything work, as xmodmap changes are X global).

Now, the only thing I use my left pinky for is typing and Tab, which seems fair.  I'll see if things get better.  Maybe I will end up in Viper mode.

Update: Things did get better, but just barely. I do believe that the numbness is caused primarily by just a few common Emacs commands, like C-c C-c, C-x C-s, or any command that uses the C-c or C-x prefixes. In fact, my opinion is that the left hand is way over used in Emacs. I had to re-enable the left shift key for the sake of my typing speed. This has also revealed that Apple cut a few corners when it came to their keyboard hardware (everybody does). The left and right alt keys, when pressed at the same time, will stop any keys on the "zxcv" row from even producing key codes, so that's a pain right now. As of testing just a few minutes ago, the numbness comes back with just a few minutes of typing on a normal keyboard layout.

Update (after a few months): This has basically been resolved.  A few thoughts: mapping to thumbs seemed like a good idea, but thumbs get worn out too.  After a few months, my thumbs were pretty ache-y.  In the end, the two things I found that really did make a difference were: 1. binding caps-lock as a control and 2. switching to a Dvorak layout, more specifically the Programmers Dvorak layout, which I think is pretty smart.  I can't say how much each of these contributed individually, as I changed them simultaneously.  I plan to write a post on Programmers Dvorak soon but suffice it to say, switching layouts isn't a decision to take lightly.  The caps-lock thing, on the other hand, is dead simple and helps tremendously; I very much suggest it.  I only wish I had another key right beside the caps-lock (or in the pinky position on the right hand) that I could bind to Meta/Alt.

Introducting Index-Mapped-Arrays

I was writing a blog post regarding my release of a library I have been using for a while now but have recently cleaned up, but it got too wordy. I will post it as well (perhaps already have), but I wanted to have a short post showing the capabilities of this library. That way people might actually be interested enough to download the library or read the other post. So without further ado, I present Index-Mapped-Arrays:

Index-Mapped-Arrays provides a generic interface, imref, to Common Lisp types.

(imref '(a b c d e f) 2)
;; C

(imref '(((a b) (c d)) ((e f) (g h))) 1 1 1)
;; H

(imref '((1 2 3) (4 5 6) (7 8 9)) 1 1)
;; 5

(imref #2A((1 2 3) (4 5 6) (7 8 9)) 1 1)
;; 5

;;; As well as setting

(let ((ima '((1 2 3) (4 5 6) (7 8 9))))
  (setf (imref ima 1 1) 'set)
  ima )
;; ((1 2 3) (4 SET 6) (7 8 9))

(let ((ima #2A((1 2 3) (4 5 6) (7 8 9))))
  (setf (imref ima 1 1) 'set)
  ima )
;; #2A((1 2 3) (4 SET 6) (7 8 9))

As the name implies, you can map indices. Mapping indices allows you to do things like pull vectors out of matrices and grab sub-regions of arrays.

(defparameter *arr* '((1 2 3) (4 5 6) (7 8 9)))

;; Note, it returns a list
(row-vector *arr* 1)
;; (4 5 6)

;; We can't easily get a column vector, so we return an IMA object.
(column-vector *arr* 1)
;; #1D-IMA(2 5 8)

;; Print readably
(let ((*print-readably* t))
  (print (column-vector *arr* 1)) )
;; #(2 5 8) ; Printed as a normal array
;; #1D-IMA(2 5 8)

;; Same sort of thing with a submatrix
(submatrix *arr* 0 1 3 2)
;; #2D-IMA((2 3) (5 6) (8 9))

(row-vector (submatrix *arr* 0 1 3 2) 1)
;; #1D-IMA(5 6)

Note that IMA tries its best to give you a native data structure back, but if it can't, it gives to an instance of class index-mapped-array which emulates the proper mapping.

But that's not all. Index maps are themselves setfable places.

(setf (column-vector *arr* 0) '(a b c))
;; (A B C)

*arr*
;; ((A 2 3) (B 5 6) (C 8 9))

(defparameter *subarr* (submatrix *arr* 1 1 2 2))
;; *SUBARR*

(setf (row-vector *subarr* 0) '(d e))
;; (D E)

*subarr*
;; #2D-IMA((D E) (8 9))

*arr*
;; ((A 2 3) (B D E) (C 8 9))

And to get all of this for any data structure that can be accessed via a list of integer indices, all you have to do is specialize the methods, ima-dimensions, ima-dimension, imref, and (setf imref) (or if your data structure is immutable immod). Do this, and everything above just works, and it's portable so it should work everywhere the spec is obeyed (I test on SBCL, CMUCL, CCL, CLISP, ECL, and ABCL. All but ABCL work).

And don't think that this is only useful for blocks of data. It's a bit more flexible than that. Observe:

(defclass point () ((x-value :initarg :x-value :initform 0 :accessor x-of)
                    (y-value :initarg :y-value :initform 0 :accessor y-of)
                    (z-value :initarg :z-value :initform 0 :accessor z-of) ))

(defmethod print-object ((point point) str)
  (format str
          "#<Point: x=~A y=~A z=~A>"
          (x-of point)
          (y-of point)
          (z-of point) ))

(make-instance 'point :x-value 1 :y-value 2 :z-value 3)
;; #<Point: x=1 y=2 z=3>

;; Define the IMA interface
(defmethod ima-dimensions ((ima point))
  (list 3) )
(defmethod ima-dimension ((ima point) n)
  3 )

(defmethod imref ((point point) &rest i)
  (case (first i)
    (0 (x-of point))
    (1 (y-of point))
    (2 (z-of point))
    (otherwise (error "Index ~S out of bounds" i)) ))
(defmethod (setf imref) (new-value (point point) &rest i)
  (case (first i)
    (0 (setf (x-of point) new-value))
    (1 (setf (y-of point) new-value))
    (2 (setf (z-of point) new-value))
    (otherwise (error "Index ~S out of bounds" i)) )
  new-value )

(let ((point (make-instance 'point :x-value 1 :y-value 2 :z-value 3)))
  (iter (for i below 3)
    (collect (imref point i)) ))
;; (1 2 3)

For extra functionality, and you do want it, you can use the def-unmapper macro and specialize the make-ima-like method which will tell IMA how to change other IMAs into this kind of IMA, and how to make an another IMA like this one so we can fill it with data, respectively.

(defmethod make-ima-like ((point point) &key &allow-other-keys)
  (make-instance 'point) )

(def-unmapper point (ima)
  (when (or (< 1 (length (ima-dimensions ima)))
            (< 3 (ima-dimension ima 0)) )
    (error "Can only map a vector with 3 or fewer elements to a point") )
  (let ((point (make-instance 'point)))
    (setf (a-of point) (imref ima 0)
          (b-of point) (imref ima 1)
          (c-of point) (imref ima 2) )
    point ))

;; Or, more interestingly
(let ((point1 (make-instance 'point :x-value 1 :y-value 2 :z-value 3))
      (point2 (make-instance 'point :x-value 3 :y-value 2 :z-value 1)) )
  (list (v:dot point1 point2)
        (v:cross point1 point2)
        (v:+ point1 point2)
        (v:- point1 point2) ))
(10 #<Point: x=-4 y=8 z=-4> #<Point: x=4 y=4 z=4> #<Point: x=-2 y=0 z=2>)

This works because my vector arithmetic library uses IMA to access the elements of its arguments, and uses make-ima-like to make the structures that it returns to the caller. The unmapper is used if you need to get some mapped data into a equivalent form but without any of the index mappings.

And if you thought that was all, I just added a new feature, a map simplifier. This means that in certain simple cases, multiple levels of mappings are reduced to a single map. For instance, taking a transpose of a transpose will return the original array. This means there is less to fear when it comes to using a mapping as part of long recursion or iteration.

(let ((ima '((1 2) (3 4))))
  (iter (for i below 1000)
    (setf ima (transpose ima)) )
  ima )
;; ((1 2) (3 4)) <- the original list

(let ((ima '((1 2) (3 4))))
  (iter (for i below 1001)
    (setf ima (transpose ima)) )
  ima )
;; #2D-IMA((1 3) (2 4)) <- Only one mapping here

;; Let's really test the simplifier
(defun count-items (item-to-count ima)
  (cond ((= 0 (ima-dimension ima 0))
         0 )
        ((eql item-to-count (imref ima 0))
         (+ 1 (count-items item-to-count (subvector ima 1))) )
        (t (count-items item-to-count (subvector ima 1)) )))

;; We have to make a kind of complicated vector structure because if the vector
;; is of type list or array, there are quick, native ways of getting at the
;; subvector we need, so the simplifier isn't used at all.
(let ((ima (column-vector
            (iter (for i below 10000)
              (collect (list 1 (alexandria:random-elt '(not-it it)))) )
            1 )))
  (time (count-items 'it ima)) )
;; Evaluation took:
;;   0.192 seconds of real time
;;   0.190000 seconds of total run time (0.190000 user, 0.000000 system)
;;   98.96% CPU
;;   458,864,121 processor cycles
;;   4,484,640 bytes consed
;; 4900

;; Compare to without the simplifier
(let ((ima (column-vector
            (iter (for i below 10000)
              (collect (list 1 (alexandria:random-elt '(not-it it)))))
            1 ))
      ;; *simplify* controls whether IMA attempts to simplify or not.  Don't try
      ;; *this at home.
      (ima::*simplify* nil) )
  (time (count-items 'it ima)) )
;; Evaluation took:
;;   20.112 seconds of real time
;;   20.030000 seconds of total run time (19.720000 user, 0.310000 system)
;;   [ Run times consist of 1.030 seconds GC time, and 19.0000 seconds non-GC time. ]
;;   99.59% CPU
;;   48,151,308,831 processor cycles
;;   8 page faults
;;   1,602,561,216 bytes consed
;; 5026

Also, if you want to exploit your data structures capabilities, you can by specializing the mapping methods. But you only need bother if you want to try and eke out some extra performance for your particular case.

It's even integrated with Iterate (although more can be done here).

;; One way to "flatten" an IMA
(iter (for el in-ima '((1 2) (3 4)))
  (collect el) )
;; (1 2 3 4)

;; These are pretty self explanatory
(iter
  (for col in-column-vectors-of '((1 2 3) (4 5 6) (7 8 9)))
  (for row in-row-vectors-of '((1 2 3) (4 5 6) (7 8 9)))
  (collect (v:dot col row)) )
;; (30 81 150)

Basically, I wanted to share this with the community. I've been using it for a couple years and I really like it. Maybe others out there will as well. The code is on my github page and is released under the Lesser Lisp GPL.

Versioned Arrays

I just learned of a method of creating functional data structures from mutable types called versioning. Basically, if you have mutable data like an array, you can implement functional changes of the data structure by storing the differences between multiple references. This is a might bit better than copying the data structure, particularly in the case of a large array. For an array of size $N$, versioned arrays can hold two arrays with $m$ changes between them using only $O(N+m)$ space. Further, while the access time for an element when the array is $m$ away from it's version is $O(m)$, many use cases require only accessing arrays a fixed number of changes away, making access time $O(1)$.

A Simple Implementation using Lists

This can be implemented simply enough using cons cells and lists. Implementing in Common Lisp, accessing an element is as follows:

1. A versioned array is list whose last element is an array
   
2. The values before the last element are a list of changes that need to occur
   to mutate the array into the one we are interested in.
   
3. Access to the array involves applying all changes to the array and inverting
   the changes as we a moving the array to the other side of them (I'll try to
   clarify later)
   
4. Leaving you with a list of length one, containing an array with the desired
   values in it, at which point you can access the data.
   

By moving the array to the version we are currently accessing from, we are betting that more accesses will happen from this, or a similar, version. This will mean the rest of the accesses will be faster than the first.

(defpackage :versioned-arrays
    (:use :cl :bt :iter :modf)
  (:export #:make-versioned-array
           #:varef ))

(in-package :versioned-arrays)

(defun make-versioned-array (dimensions
                             &rest args
                             &key (element-type t)
                             initial-element initial-contents
                             adjustable fill-pointer
                             displaced-to displaced-index-offset )
  "Make a versioned array."
  (when (or adjustable fill-pointer displaced-to displaced-index-offset)
    (error "The capabilities: adjustable, fill-pointer, displaced-to,
    displaced-index-offset are not implemented yet") )
  (list (apply #'make-array dimensions args)) )

(defun varef (v-arr &rest idx)
  (multiple-value-bind (array changes) (get-array v-arr)
    (invert-changes (cdr v-arr) changes v-arr)
    (setf (car v-arr) array
          (cdr v-arr) nil )
    (apply #'aref (car v-arr) idx) ))

(defun get-array (v-arr)
  (if (arrayp (car v-arr))
      (values (car v-arr) nil)
      (multiple-value-bind (array changes)
          (get-array (cdr v-arr))
        (destructuring-bind (new-val &rest idx) (car v-arr)
          (let ((old-val (apply #'aref array idx)))
            (setf (apply #'aref array idx) new-val)
            (values array
                    (cons (cons old-val idx) changes) ))))))

(defun invert-changes (old-v-arr changes last)
  (cond ((null changes) nil)
        (t (setf (cdr old-v-arr) last
                 (car old-v-arr) (car changes) )
         (invert-changes (cdr old-v-arr) (cdr changes) old-v-arr) )))

First, let's consider a simple linear version history. This would happen if you had an array and only modified the original or the latest versions of the array. Using the standard cons cell diagrams where red is the car and blue is the cdr, our linear versioned array would look something like this:

Accessing an element in a linear versioned array. This is the way the structure would change if the last access was via Ref 2 and the next was via Ref 1. Any cons cell is a valid version of this array before and after the "rebase"

Modification goes very similarly:

1. Given that we want to modify the value at indices idx to new-val
   
2. We first store the current value at idx. This has the side effect of
   moving our array to the current version.
   
3. We cons a new cell to store the array in, place the delta where the array
   currently is, and modify the cdr of that cell to point to the new one.
   

This can be simply coded using my Modf library:

(define-modf-function varef 1 (new-val v-arr &rest idx)
  (let ((old-value
         ;; This moves the array to our version
         (apply #'varef v-arr idx) ))
    (let ((arr (car v-arr)))
      (setf (apply #'aref (car v-arr) idx) new-val)
      (setf (cdr v-arr) (list arr)
            (car v-arr) (cons old-value idx) )))
  (cdr v-arr) )

When looking at what is above, it is important to note that this is a mutation filled computation. This does not involve building lists the normal way with cons. Instead we are modifying lists in place. This is necessary as we need any changes we make to be seen by any reference to the versioned array. This is what I meant by inverting the changes. Inverting means reversing the order of the deltas as well as swapping the values in the deltas with the values in the array. The issue here is that we may have any given number of references to this data structure floating about. We need to modify the values that might be referenced so that if we use those reference later, they will still work.

So things might be coming into focus, although a versioned array is a list of deltas with it's last element an array, many other versioned arrays (or versions of the array) might be sharing some structure with this array. If they truly are versions of the same array, they at the very least share the last element in the list, which contains the array they are versioning. In the following figures we see the structure of a more complicated array as elements are accessed and modified (edited).

Accessing an element in a versioned array. This array has several versions. As demonstrated here, the version history is in general a tree. Upon access, the array is moved to the access point and all deltas are adjusted to maintain the array.

Accessing an element on a different branch of the version tree. Notice that no version is invalidated by this operation, not even the versions on the branch that isn't considered at all.

Editing an element in the array is much like an access except that at the end it creates another delta with the specified edit.

Multithreading

The very fact that we are messing around with mutation should clue you in that we are probably going to have thread safety issues. In fact, even reading is a mutating operation for this structure, so it isn't even safe to read from multiple threads at the same time. Due to this, everything inside the internals of this data structure needs to be wrapped in a lock unique to the structure. I chose to switch from a list to a structure so I could hold the lock in a straight-forward manner (and so I can have a type to specialize print-object on).

There is a single lock on the array. This means that, unlike tree based implementations of functional arrays, working with one version will halt any work with another version.

Performance

Let's see how this performs on the well known N-Queens problem. This involves backtracking, which is one of those use cases where we are only interested in array versions a constant number of deltas away from the current. If we ignore how simple the queens problem is and explicitly build a chess board to check the other attacking squares, we would get something like what follows. Here I have a version based on versioned arrays, and one sketched out for standard arrays. I also implemented this for a functional array based on FSet, which uses some kind of trees.

(defun place-queen (board i j)
  "This complicated bit is to test if a queen can attack another."
  (if (and (iter (for k from 0 below (va-dimension board 0))
                 (never (and (/= i k) (varef board k j))) )
           (iter (for k from 0 below (va-dimension board 1))
                 (never (and (/= j k) (varef board i k))) )
           (iter (for k1 from i downto 0)
                 (for k2 from j downto 0)
                 (never (and (/= k1 i) (/= k2 j) (varef board k1 k2))) )
           (iter (for k1 from i below (va-dimension board 0))
                 (for k2 from j below (va-dimension board 1))
                 (never (and (/= k1 i) (/= k2 j) (varef board k1 k2))) )
           (iter (for k1 from i downto 0)
                 (for k2 from j below (va-dimension board 1))
                 (never (and (/= k1 i) (/= k2 j) (varef board k1 k2))) )
           (iter (for k1 from i below (va-dimension board 0))
                 (for k2 from j downto 0)
                 (never (and (/= k1 i) (/= k2 j) (varef board k1 k2))) ))
      (modf (varef board i j) t)
      nil ))

(defun n-queens (board n row)
  "Simple enough backtracking algorithm."
  (if (= row n)
      board
      (iter (for i below n)
            (let ((result (place-queen board i row)))
              (when result
                (thereis (n-queens result n (+ row 1))) )))))

(defun place-queen* (board i j)
  "This complicated bit is to test if a queen can attack another."
  (if (and ...similar-tests...)
      t
      nil ))

(defun n-queens* (board n row)
  "A bit more convoluted backtracking algorithm."
  (if (= row n)
      board
      (let (winning-board)
        (iter (for i below n)
              (let ((result (place-queen* board i row)))
                (when result
                  (setf (aref board i row) t)
                  (let ((try (n-queens* board n (+ row 1))))
                    (when try
                      (setf winning-board try)
                      (finish) )
                  (setf (aref board i row) nil) ))
              (finally (return winning-board)) )))))

Comparing the two, we naturally see that the functional form is more elegant and understandable. The speed is another matter though…

$N$	Array	Versioned Array	FSet Array	VA/Array	FSet/Array
11	1	4	4	4	4
12	2	24	41	12	20.5
13	1	12	12	12	12
14	17	255	277	15	16.294118
15	14	207	231	14.785714	16.5
16	116	1726	1937	14.879310	16.698276
17	68	1006	1167	14.794118	17.161765
18	595	8775	10073	14.747899	16.929412
19	40	584	694	14.6	17.35

The functional version is easier to understand, of course, though using something like screamer would hide most if not all of the side effect annoyances. Speed wise, though, the functional approaches seem to be around a factor of 15 slower. The FSet method is consistently slower, but not by enough to say definitively that versioned arrays are going to be faster for this problem. We do see a slow growth in the FSet implementation. We are probably seeing the $O(\log N)$ access time. There might be a completely different story to tell with proper optimization of the versioned arrays. Particularly if someone tried to get it closer to the metal, so to speak.

Conclusions

A little side note: since starting the post, I have found out that Haskell uses something similar to this in its Diff Array library with the notable exception that the version history is forced to be linear. This is done by forcing a copy if a version other than the most recent is changed. This seems like it could lead to mysterious poor performance for small changes in your algorithm and certainly doesn't seem appropriate for backtracking. Fortunately, the person who let me know about data structure in the first place is currently implementing a library for this for Haskell.

One thing to note is when this doesn't work well. It doesn't work well when you have references to versions of an array with very different deltas. For instance, if you saved some initial state of an array, made many changes, and used both arrays by, say, comparing them element by element, things could get pretty slow. To curb this, several people have developed schemes to split the versioning tree if too many deltas are in between two particular arrays. Typically this is done probabilistically, randomly splitting the delta tree with probability $\frac 1 N$. With this modification, we have an expected amortized edit time of $O(1)$ (worst case $O(N)$ which is a steep price) and an expected worst case access time to be $O(N)$. The true worst case access time is $O(m)$ for arbitrarily bad luck on the RNG, but the expected $O(N)$ is a much needed improvement over knowing it is $O(m)$ where $m$ can be arbitrarily large. Since all of the work is done in walking the deltas and rebasing the array, edits and accesses have the same time complexity.

This all sounds like gloom and doom, but really, there are a large class of problems that don't require access from very different arrays. Further, much of this trouble can be resolved by breaking the abstraction and allowing the user to explicitly force a copy.

I was thinking about it, and there is nothing here limiting you to arrays. I could, in principle, implement this kind of versioning for any mutable structure. Instead of storing indices, the arguments of the setter function, store the function and the arguments and the setter can be inverted the same way it is in Modf. It doesn't sound like too bad of an idea to have a generic functionality to stick any object into and get back an immutable object with reasonable asymptotic performance. Maybe this should be a future extension for Modf.

Syncing Emacs with Google Documents

Before anything, sorry for the long post. If I had more time, I would have made it shorter. I made a promise to myself that I would spend the time to write up things I do, mainly so I get practice doing so, and to have a record of things I've done.

Recently I had an interview with Google. At Google they try to weed out applicants with a quick technical phone interview before they fly you out for an actual interview. As part of this interview, a shared Google Document is set up as a kind of virtual white-board so you can show your programming ability. Never mind that I would rather be sharing a Screen session, VNC connection, or even a live screen cast of my desktop, this is the way they decided to do it. The problem is, Google Documents are not meant to be code editor, they are meant to be a tool for writing documents. As such, I would be left without the aid of auto-completion, argument lists, and (most importantly) the Emacs key bindings, that, by now, are etched into my spinal column. So, a few minutes after receiving an email stating a Google Document would be used, I started coding up a program that would allow me to program in Emacs, but have my work displayed in Google Documents. See the video for an idea of what I'm talking about.

I quickly found the hooks: before-change-functions and after-change-functions. Actually, they are not hooks, I believe, as Emacs has a strictly specified meaning and argument passing protocol for hooks, they are just a list of functions that are called before and after each change, respectively. These would allow me to find what changes are being made locally so I can send them to Google Docs.

Now came one hurdle: how do I interface with Google Docs? There is a Greasemonkey and Python script that allows you to download Google Documents from the command line. Unfortunately, I could not find a script made for uploading documents, which is really the main part of this. Further, while the script worked for downloading, it was far too slow for interactive editing. The time from hitting return to retrieved document was on order 5-10 seconds. I needed something that could be run extremely fast, like on the order of the time it takes to type a key.

I eventually decided that I should try to mirror the edits between the two document by sending keystrokes to the browser window. Next hurdle: in X, as far as I know, keystrokes are only sent to the focused window. And since I would be using Emacs, I couldn't rightly send keystrokes to Firefox at the same time. Or can I? I quickly decided to run a separate X server which would run an instance of Firefox which could be focused at the same time as Emacs on my normal X server. Now there are several ways to do this (e.g. actually run a new server on a different virtual terminal, or playing around with Xnest which runs an X server inside a window in your host X server) but in the end I decided to use the awesome programs xpra and Xvfb. Xpra is a program designed to be an alternative to X forwarding.

Xpra and Xvfb

As an aside, X forwarding allows you to run graphical applications on remote machines while having the graphics display locally. This is different from VNC and RDP in that you don't have access to the entire X session, just windows associated with applications you are running. X forwarding has become less used in the Unix world, mostly due to a lack of knowledge of its existence, I believe. This is not to say that there aren't good reasons for it not be used. It actually has a pretty severe problem on high latency network (a.k.a high ping time) connections.

Xpra was also designed to get around X forwarding poor performance as well as to add abilities like detaching GUI programs and re-attaching from a different point on the network, just like with screen. It truly is very neat. All of it's neatness aside, I just wanted to use it to handle Xvfb, which is a virtual X server, like Xnest, but one that doesn't have to be displayed at all. You can start programs under an Xvfb server and they will happily do their business thinking they are displaying windows, but no window is drawn to any screen. Xvfb sounds just like what I needed. First I started the Xvfb server on display ":1" by using the Xpra:

xpra :1

I started Firefox under the Xvfb server via:

DISPLAY=:1 firefox -no-remote -P some-other-profile

This is more complicated than normal because I leave Firefox running. The options -no-remote tells Firefox to not check for other, currently running instances of Firefox before starting it. If Firefox sees a running instance of itself, it will choose to just open a new window rather than start a new instance. The option -P tells Firefox to use a different profile (which you must create prior to this) for the session. This is necessary as a different running instance of Firefox will have a lock held on your normal profile. If you are willing to just close Firefox, you can omit both of those options.

At this point, nothing should be displayed. If you want to attach the Firefox window to the current X server via Xpra, just use xpra attach and it should appear. You can navigate this to your Google Document.

Sending input to the window

Up until now, we have not even discussed how you are going to send input to the window. Luckily, this can be accomplished by many tools. In fact, I ran into three without even looking really (Xnee which includes gnee and cnee, xte, and xdotool). I have even heard people describing directly inserting characters into the input devices in /dev. I ended up using xdotool because (1) it seemed more powerful than xte and (2) cnee crashed my (main ":0") X server. With xdotool you can send keys (with modifiers), strings, mouse motion and clicks, and manipulate windows, like bringing them into focus.

# Send an 'a', a 'B', and a 'C'
DISPLAY=:1 xdotool key a B shift+c

# This types "hello how are you"
DISPLAY=:1 xdotool type "hello how are you"

# This moves the mouse to 100,100 relative to the top-left corner of the window,
# then right click (presses and releases the 3rd button)
DISPLAY=:1 xdotool mousemove --window 41466948 100 100 click 3

# This brings window with id 41466948 into focus
DISPLAY=:1 xdotool focusWindow 41466948

This is fine and dandy, but what if we want to input large sections of text. Even if we use the type command, xdotool is still just typing every letter, albeit ~100 characters/second. Further, due to a bug/shortcoming/whatever in xdotool, I couldn't figure out how to make it send text that includes a newline character (or an ampersand or question mark for that matter). It seems worth our while to come up with other ways of interfacing with the Google Documents window. The other way I came up with is the clipboard.

X has a clipboard (actually it has three), and that clipboard can be accessed via the command line. Again, there are multiple tools that can do this including xclip and xsel. While the functionality of the two programs are near identical, I chose to use xsel as it seemed a little more robust. Using xsel, we can send large sections of text to the clipboard on display ":1" (remember, each X server has it's own clipboard), then send a "ctrl+v" using xdotool. More interestingly, however, is that copying in the ":1" server allows us to gain some information on what is in the other file and more importantly, as it turns out, the location of the point in the Google Document.

Putting it together

Most of this involves coding in Emacs Lisp. The point of everything here is to keep track of where the point in the Google Document while making alterations. If we ever lose track of where the point is in the document, we will corrupt the document with every edit. In the following, I use the word "document" to refer to the Google document and "document point" to refer to the cursor location in that document. The word "buffer" refers to things in Emacs, and "buffer point" refers to the point in the Emacs buffer, i.e. the cursor position. I use the word function here because that's what Emacs calls them. In reality these are all procedures called for their side effects.

We will need some basics:

1. A function that will send a key to the window
   
2. A function that will send a string to the window
   
3. A function to properly escape strings sent through the shell
   
4. Functions that move left and right
   
5. A function that moves the point by some relative amount
   

   (defvar gd-point 0 "A variable holding the document point")
   
   (defun gdmir-gdocify-string (str)
     "Escape every character.  This means that the shell shouldn't
   mess with any of this."
     (replace-regexp-in-string "\\(.\\)" "\\\\\\1" str))
   
   ;; The parameter INSTANT is used in the buffered input optimiztion, but not
   ;; here.
   (defun gdmir-send-key (keys &optional instant)
     (shell-command (concat "DISPLAY=:1 xdotool windowFocus 4194333 key "
                            keys )))
   
   (defun gdmir-send-string (string)
     (shell-command (concat "DISPLAY=:1 xdotool windowFocus 4194333 type "
                            string )))
   
   (defun gdmir-move-left (n)
     "Move the buffer N characters left, reducing GD-POINT by N.
   The buffer point doesn't change."
     (loop repeat n
           do (gdmir-send-key "Left")
              (decf gd-point)) )
   
   (defun gdmir-move-right (n)
     "Move the buffer N characters right, increasing GD-POINT by N.
   The buffer point doesn't change."
     (loop repeat n
           do (gdmir-send-key "Right")
              (incf gd-point) ))
   
   (defun gdmir-move-to-relative-point (point-difference)
     "Move the buffer point to \(+ GD-POINT POINT-DIFFERENCE).  The
   buffer point doesn't change."
     (if (< point-difference 0)
         (gdmir-move-left (abs point-difference))
         (gdmir-move-right (abs point-difference)) ))
   

Now for the meat and potatoes: the hook functions. We will define a function that sets the after and before change functions. The before function, gdmir-before-edit, which receives the start and end point of the forthcoming edit, moves the document point to the end of the edit range, then saves the original string, and finally deletes the original text¹. The after function, gdmir-after-edit, sends commands required to type the new text.

(defun split-for-xdotool (string)
  "This function runs through the input and replaces instances of
`?', `&', and newlines with symbols corresponding to these
characters.  We return a list containing strings and the special
symbols in the order they should be output.  We have to use the
special symbols due to the fact that xdotool, or bash, or
something cannot handle these symbols, even if they are quoted."
  (rest
   (let ((count 0))
     (loop for segment in (split-string string "[\n?&]")
           appending
        (list (when (> count 0)
                (cond ((eql (aref string (- count 1)) (aref "?" 0))
                       'question )
                      ((eql (aref string (- count 1)) (aref "&" 0)) 'amp)
                      ((eql (aref string (- count 1)) (aref "\n" 0))
                       'ret )))
              segment )
           do (incf count (1+ (length segment))) ))))

(defvar *prechange-text* nil "This holds the contents of the
edited region prior to the edit.  We don't use this, but I can
think of a few reasons we might want to save it." )

(defun gdmir-before-edit (start end)
  (gdmir-move-to-relative-point (- end gd-point))
  (setf *prechange-text* (list start end (buffer-substring start end)))
  ;; Delete the string in GD before in Emacs
  (loop for i below (- end start)
        do (decf gd-point)
           (gdmir-send-key "BackSpace") ))

(defun gdmir-after-edit (start end old-length)
  (when (< 0 (- end start))
    (loop for line in (split-for-xdotool (buffer-substring start end))
          do (cond ((eql line 'question)
                    (gdmir-send-key "shift+slash") )
                   ((eql line 'amp)
                    (gdmir-send-key "shift+7") )
                   ((eql line 'ret)
                    (gdmir-send-key "Return")
                    (gdmir-send-string "\\|") )
                   ((< 0 (length line))
                    (gdmir-send-string (gdmir-gdocify-string line)) )))
    (incf gd-point (length (buffer-substring start end))) ))

(defun insert-change-hook ()
  (setf *change-hook-in-effect* t)
  (push
   'gdmir-before-edit
   before-change-functions )
  (push
   'gdmir-after-edit
   after-change-functions ))

We also can use a few helper functions which we will implement as key-bindings.

1. A function that syncs the points in the buffers (C-x SPC when mirroring is on)
   
2. A function that turns the mirroring on and off (C-x SPC when off will turn
   it on, if it's on and the point is already synced, it will be turned off)
   
3. A set of functions that moves the point in the browser window (M-<direction
   keys>). These are really handy for a quick reposition of the document
   point.
   

   (defun sync-points ()
     "Set GD-POINT to the buffer point."
     (setf gd-point (point)) )
   
   (defvar *change-hook-in-effect* nil "Used to determine if our
   change hooks are already doing their thing.")
   
   (defun setup-mirror ()
     "Set up the mirroring environment.  This should really be a
   minor mode, but since this is basically a throw away hack, I'm
   not going to bother."
     (setf old-after-change-functions after-change-functions
           old-before-change-functions before-change-functions )
     (local-set-key (kbd "M-<left>")
                    (lambda () (interactive) (gdmir-send-key "Left" t)) )
     (local-set-key (kbd "M-<right>")
                    (lambda () (interactive) (gdmir-send-key "Right" t)) )
     (local-set-key (kbd "M-<up>")
                    (lambda () (interactive) (gdmir-send-key "Up" t)) )
     (local-set-key (kbd "M-<down>")
                    (lambda () (interactive) (gdmir-send-key "Down" t)) )
     (local-set-key (kbd "C-x SPC")
                    (lambda ()
                      (interactive)
                      (cond ((and after-change-functions
                                  *change-hook-in-effect*
                                  (= (point) gd-point) )
                             (message "Mirroring disabled")
                             (setf *change-hook-in-effect* nil
                                   after-change-functions old-after-change-functions
                                   before-change-functions old-before-change-functions ))
                            ((and after-change-functions
                                  *change-hook-in-effect* )
                             (message "Syncing points")
                             (sync-points) )
                            (t
                             (message "Mirroring enabled")
                             (setf *change-hook-in-effect* t)
                             (insert-change-hook)
                             (sync-points) )))))
   

Optimizations

While all of this works, it works quite slowly. Just moving from one point to another in the document can take a considerable time as it involves moving side to side perhaps thousands of times. Here we consider two areas where there can be considerable improvements.

Incorporating other moves than side to side

The first optimization I made was to allow for motion using the up and down keys. This is difficult as we don't know how the lines are wrapped on the Google Doc, so we don't know how far that moves in the file. This can be attacked by noting that if we hold down shift as we move, the region will be selected. We can copy that to the clipboard² and read it in Emacs, allowing us to find length of the string selected, and therefore the motion in the document. This almost works. However, it turns out that whitespace at the beginning and end of selections are often times elided when copied to the clipboard (not sure why). Another issue, if you make a selection of only whitespace, it may not be copied to the clipboard at all, leaving what was on there before.

This means that we may lose track of our document point if we start or end on white space in a vertical move. The way I chose to deal with this is to place a vertical bar, "|", at the beginning of each line. To move vertically, I move the point to the beginning of the line (before the vertical bar) and then move up or down selecting the difference. This method ensures that the selection includes no end whitespace (other than the newline at the end. The newline at the end of the selection is deleted but it is compensated for by the vertical bar. As long as we only move one line at a time, we can tell how far we've gone in the vertical direction.

To add this change, we must modify the gdmir-move-left and gdmir-move-right functions to take two steps when we pass a newline in order to skip over the vertical bar in the left hand column. We must also have our change hooks check to see if we are deleting a newline (we must delete an extra character) and if we are inserting a newline (we must add a new vertical bar).

(defun gdmir-move-left (n)
  (save-excursion
    (goto-char gd-point)
    (loop repeat n
          do (when (= 0 (current-column))
               (gdmir-send-key "Left") )
             (gdmir-send-key "Left")
             (decf gd-point)
             (backward-char) )))

(defun gdmir-move-right (n)
  (save-excursion
    (goto-char gd-point)
    (loop repeat n
          do (gdmir-send-key "Right")
             (incf gd-point)
             (forward-char)
             (when (= 0 (current-column))
               (gdmir-send-key "Right") ))))

(defun gdmir-before-edit (start end)
  (gdmir-move-to-relative-point (- end gd-point))
  (setf *prechange-text* (list start end (buffer-substring start end)))
  ;; Delete the string in GD before in Emacs
  (save-excursion
    (goto-char gd-point)
    (loop for i below (- end start)
          do (progn
               (when (= 0 (current-column))
                 ;; Clear out code marker
                 (gdmir-send-key "BackSpace") )
               (decf gd-point)
               (gdmir-send-key "BackSpace")
               (backward-char) ))))

(defun gdmir-after-edit (start end old-length)
  (when (< 0 (- end start))
    (loop for line in (split-for-xdotool (buffer-substring start end))
          do (cond ((eql line 'question)
                    (gdmir-send-key "shift+slash") )
                   ((eql line 'amp)
                    (gdmir-send-key "shift+7") )
                   ((eql line 'ret)
                    (gdmir-send-key "Return")
                    (gdmir-send-string "\\|") )
                   ((< 0 (length line))
                    (gdmir-send-string (gdmir-gdocify-string line)) )))
    (incf gd-point (length (buffer-substring start end))) ))

(defun insert-change-hook ()
  (setf *change-hook-in-effect* t)
  (push
   'gdmir-before-edit
   before-change-functions )
  (push
   'gdmir-after-edit
   after-change-functions ))

Then we can introduce gdmir-move-up, gdmir-move-down, and extend gdmir-move-to-relative-point so it makes use of this new ability.

;; *EMS-PER-LINE* will be used to guess at when a line might be wrapped.  if we
;; *over-estimate, vertical moves will be broken
(defvar *ems-per-line* 50
  "A conservative estimate for how many `m's are in a line in the google document." )

(defun gdmir-move-to-zero-column ()
  (flush-commands)
  (save-excursion
   (goto-char gd-point)
   (gdmir-move-left (max (- (current-column) (- *ems-per-line* 1)) 0))
   (goto-char (- gd-point (max (- (current-column) (- *ems-per-line* 1)) 0)))
   (cond ((< (current-column) *ems-per-line*)
          (gdmir-send-key "Home Right" t)
          (setf gd-point (line-beginning-position)) )
         (t (gdmir-move-left
             (current-column) )))))

(defun gdmir-grab-selection ()
  "To read from the clipboard"
  (gdmir-send-key "ctrl+c" t)
  (shell-command-to-string "xsel --display :1 -o -b") )

(defun gdmir-move-up ()
  (flush-commands)
  (save-excursion
    (goto-char gd-point)
    ;; More to the left most position on the screen
    (gdmir-move-to-zero-column)
    (goto-char gd-point)
    ;; Move to the left of the code delimiter
    (shell-command "DISPLAY=:1 xdotool windowFocus 4194333 key Left")
    ;; move up selecting the differnce
    (let ((orig-line (line-number-at-pos)))
      (loop until (/= (line-number-at-pos) orig-line)
            do (shell-command "DISPLAY=:1 xdotool windowFocus 4194333 key shift+Up")
               (let ((selection (gdmir-grab-selection)))
                 (backward-char (length selection)) )
               ;; This doesn't move the point, it just moves to the left of the
               ;; selection and unselects the text.
            (shell-command "DISPLAY=:1 xdotool windowFocus 4194333 key Left") ))
    (setf gd-point (point))
    ;; Move to the right of the code delimiter
    (shell-command "DISPLAY=:1 xdotool windowFocus 4194333 key Right") ))

(defun gdmir-move-down ()
  (flush-commands)
  (save-excursion
    (goto-char gd-point)
    ;; More to the left most position on the screen
    (gdmir-move-to-zero-column)
    (goto-char gd-point)
    ;; Move to the left of the code delimiter
    (shell-command "DISPLAY=:1 xdotool windowFocus 4194333 key Left")
    ;; move down selecting the differnce
    (let ((orig-line (line-number-at-pos)))
      (loop until (/= (line-number-at-pos) orig-line)
            do (shell-command "DISPLAY=:1 xdotool windowFocus 4194333 key shift+Down")
               (let ((selection (gdmir-grab-selection)))
                 (forward-char (length selection)) )
               ;; This doesn't move the point, it just moves to the left of the
               ;; selection and unselects the text.
            (shell-command "DISPLAY=:1 xdotool windowFocus 4194333 key Right") ))
    (setf gd-point (point))
    ;; Move to the right of the code delimiter
    (shell-command "DISPLAY=:1 xdotool windowFocus 4194333 key Right") ))

(defun gdmir-move-to-relative-point (point-difference)
  (let ((target (+ gd-point point-difference)))
    ;; 80 is a guess at how far we have to be going before moving vertically
    ;; might be of benefit
    (cond ((< point-difference -80)
           ;; Go until you have passed the point.
           (while (> gd-point target)
             (gdmir-move-up) ))
          ((> point-difference 80)
           ;; Go until you have passed the point.
           (while (< gd-point target)
             (gdmir-move-down) )))
    ;; Then we will finish off with side to side movement
    (let ((point-difference (- target gd-point)))
      (if (< point-difference 0)
          (gdmir-move-left (abs point-difference))
          (gdmir-move-right (abs point-difference)) ))))

The motion to the beginning of the line is still annoying but as you can see we sped that up slightly by using the "home" key. This moves the point to the beginning of the line. You don't even have to select in this move as we can calculate the point at the beginning of the line in Emacs. There is one problem with this, however, since lines can wrap, and pressing "home" in Google Docs brings you to the beginning of the visible line, this cannot be used if you are on a wrapped line. I have the program move horizontally until it is within a conservative estimate of the maximum line width, then us the "home" key. You might think it a good idea to use the "shift+home" key combo repeatedly interspersed with "left" key presses counting how far we've gone, but the same issue remains, if we happen to start on some whitespace, we may miss some characters at the end of the line.

Buffering Commands

Buffering the input commands speeds things up in general because it removes some overhead to the input sending process. The way we have it set up right now is to have each keystroke start a bash shell and run the xdotool command to send input to the document. Just starting bash contributes a pretty big overhead. By buffering the commands, we can collect several commands and send them all at once, defeating the overhead. All in all this seems to speed up input by a factor of two, or so. This is a pretty significant improvement³. In fact, this beats the above method of motion for all but very long yet unwrapped lines.

In order to incorporate this kind of buffering from within Emacs, we can just hold of list of pending commands that need to be sent to the document. We will modify the gdmir-send-key function to push onto that list rather than actually send it to via xdotool. If the buffer gets to a certain size, we flush the commands to the document. In addition, since sending a string via xdotool is the last thing one can do in an invocation to xdotool, we also must force a flush of all stored commands before we send the string.

(defvar *pending-keys* nil)

(defun flush-commands (&optional string)
  (let* ((cmd (if *pending-keys*
                  (apply #'concat "key " (mapcar (lambda (x) (concat " " x)) (reverse *pending-keys*)))
                  " " ))
         (cmd (if string
                  (concat cmd " type " string)
                  cmd )))
    (when (or *pending-keys* string)
      (shell-command (concat "DISPLAY=:1 xdotool windowFocus 4194333 " cmd)) )
    (setf *pending-keys* nil)
    (setf *last-flush* (float-time)) ))

(defun gdmir-send-key (keys &optional instant)
  (push keys *pending-keys*)
  (when (or instant (< 20 (length *pending-keys*)))
    (flush-commands) ))

(defun gdmir-send-string (string)
  (flush-commands string) )

In addition to all of this, we will also need to alter several other functions to force flushing as some of them require synchronous execution, like anything that involves the clipboard.

(defun gdmir-move-to-zero-column ()
  (flush-commands)
  (save-excursion
   (goto-char gd-point)
   (gdmir-move-left (max (- (current-column) (- *ems-per-line* 1)) 0))
   (goto-char (- gd-point (max (- (current-column) (- *ems-per-line* 1)) 0)))
   (cond ((< (current-column) *ems-per-line*)
          (gdmir-send-key "Home Right" t)
          (setf gd-point (line-beginning-position)) )
         (t (gdmir-move-left
             (current-column) )))))

(defun gdmir-move-up ()
  (flush-commands)
  (save-excursion
    (goto-char gd-point)
    ;; More to the left most position on the screen
    (gdmir-move-to-zero-column)
    (goto-char gd-point)
    ;; Move to the left of the code delimiter
    (shell-command "DISPLAY=:1 xdotool windowFocus 4194333 key Left")
    ;; move up selecting the differnce
    (let ((orig-line (line-number-at-pos)))
      (loop until (/= (line-number-at-pos) orig-line)
            do (shell-command "DISPLAY=:1 xdotool windowFocus 4194333 key shift+Up")
               (let ((selection (gdmir-grab-selection)))
                 (backward-char (length selection)) )
               ;; This doesn't move the point, it just moves to the left of the
               ;; selection and unselects the text.
            (shell-command "DISPLAY=:1 xdotool windowFocus 4194333 key Left") ))
    (setf gd-point (point))
    ;; Move to the right of the code delimiter
    (shell-command "DISPLAY=:1 xdotool windowFocus 4194333 key Right") ))

(defun gdmir-move-down ()
  (flush-commands)
  (save-excursion
    (goto-char gd-point)
    ;; More to the left most position on the screen
    (gdmir-move-to-zero-column)
    (goto-char gd-point)
    ;; Move to the left of the code delimiter
    (shell-command "DISPLAY=:1 xdotool windowFocus 4194333 key Left")
    ;; move down selecting the differnce
    (let ((orig-line (line-number-at-pos)))
      (loop until (/= (line-number-at-pos) orig-line)
            do (shell-command "DISPLAY=:1 xdotool windowFocus 4194333 key shift+Down")
               (let ((selection (gdmir-grab-selection)))
                 (forward-char (length selection)) )
               ;; This doesn't move the point, it just moves to the left of the
               ;; selection and unselects the text.
               (shell-command "DISPLAY=:1 xdotool windowFocus 4194333 key Right") ))
    (setf gd-point (point))
    ;; Move to the right of the code delimiter
    (shell-command "DISPLAY=:1 xdotool windowFocus 4194333 key Right") ))

(defun gdmir-before-edit (start end)
  (gdmir-move-to-relative-point (- end gd-point))
  (setf *prechange-text* (list start end (buffer-substring start end)))
  ;; Delete the string in GD before in Emacs
  (save-excursion
    (goto-char gd-point)
    (loop for i below (- end start)
          do (progn
               (when (= 0 (current-column))
                 ;; Clear out code marker
                 (gdmir-send-key "BackSpace") )
               (decf gd-point)
               (gdmir-send-key "BackSpace")
               (backward-char) ))))

(defun gdmir-after-edit (start end old-length)
  (when (< 0 (- end start))
    (loop for line in (split-for-xdotool (buffer-substring start end))
          do (cond ((eql line 'question)
                    (gdmir-send-key "shift+slash") )
                   ((eql line 'amp)
                    (gdmir-send-key "shift+7") )
                   ((eql line 'ret)
                    (gdmir-send-key "Return")
                    (gdmir-send-string "\\|") )
                   ((< 0 (length line))
                    (gdmir-send-string (gdmir-gdocify-string line)) )))
    (incf gd-point (length (buffer-substring start end))) )
  (flush-commands) )

(defun insert-change-hook ()
  (setf *change-hook-in-effect* t)
  (push
   'gdmir-before-edit
   before-change-functions )
  (push
   'gdmir-after-edit
   after-change-functions ))

And lastly we probably want to set an idle timer to run flush-commands when nothing is happening. This will make it so no changes will sit indefinitely in the key buffer. After waiting around a few seconds (four here) and pending keys are sent to the document.

(setf *idle-flusher*
  (run-with-idle-timer 4 t (lambda () (flush-commands))) )

Two other thoughts of speeding things up come to mind, though I did not attempt this for free time reasons.

1. Asynchonous Input: Buffering commands is also a good idea for a completely
   different reason if we can buffer them outside of Emacs. Emacs, as lovely
   as it is, doesn't allow for multiple threads. This means that we have to
   wait as the commands are processed. If we are able to buffer commands to a
   different process, we could have a concurrent execution. We only need to
   have to synchronize the input with Emacs when we want to get contents of the
   Google Doc, i.e. when we are examining the clipboard.
   
2. Command optimization: The commands can also be optimized. For instance,
   when you yank to an Emacs buffer (a.k.a. paste), Emacs apparently writes it,
   then deletes it, then writes it again. I'm not sure why this happens, nor
   did I ever notice until the mechanism of writing and deleting was slowed
   down by a factor of 1000 or so. In principle, before the buffer is flushed
   to output, it could pass the contents through an optimizer, that would
   reduce this particular delete-redraw cycle to no action.
   

Conclusions

Let me take a moment to relay a few observations I made while developing this interface with a "cloud" program. First, this was very hard and convoluted. I don't think that Google has any interest in stopping me from doing this, but at times I actually thought there was an antagonistic entity on the other end thwarting my attempts. If you copy and paste from a Google Doc, whitespace might get eaten (I think this is happening due to X), or indentation might get messed up (this is almost certainly happening on the Google side). I had weird cases where more than four spaces in a row were converted to tabs, and bizarre rules on what and how much whitespace was eaten at the beginning and end of the selection. You saw how we dealt with this in the code (adding an vertical bar before each line), but it is just the nature of the beast that this is a fragile set up. It would really be nice if Google made a true virtual white-board, or used an existing one (they must exist). They could put a public API on it and anyone trying to do this would be giddy.

Second, because it's a cloud application, Google can upgrade and make incompatible changes at any time. The compatibility doesn't matter much to humans as they are adaptable, but to a program, it really throws a wrench in the works. For instance, I swear that when I first started developing, copying a block of text and pasting it in a Google Doc preserved the indentation. A few days later I tried it and this was no longer the case. It seemed like a bug that would bother people, so I wouldn't be surprised if it is fixed by now. Many people are excited by how fast an application can move when the developer decides the upgrade schedule. I guess I often times prefer the stability of getting to decide that myself.

In the end this worked well enough to use, which is the most important thing. It is pretty basic functionality, but good enough to really help when programming in Google Docs⁴. I wouldn't be surprised at all, though, if I tried this in a few weeks and found that it didn't work anymore. In the very end, however, it was ultimately unused as the phone interview consisted only of pen and paper questions. Not to despair, however, the problem was a fun one to tackle. It included interesting things like pushing the X windowing system further than most users ever do, really exploiting the extensibility of Emacs, and playing with the flexibility of the GNU/Linux operative system in general. A few years ago I would have thought this too hard to actually do and over a decade ago in Windows I would have thought this impossible (this might be possible in OS X, I imagine fiddling with the clipboard and sending keys might be the hard bits). All in all, this was a fun little project during some of the development.

Footnotes:

¹ There is actually a bug here. Emacs sometimes specifies that the
change area before isn't the change area specified in after. For instance,
check the command M-x capitalize-word, which will delete the word, but only
write the first letter of the word. I'm not sure if this is my misunderstanding
of the arguments Emacs sends, or if it is a bug in Emacs itself. Luckily it
seems to be very rare.

² Yeah, I know, if it's selected it is already on the selection clipboard.
I use the ctrl+c/ctrl+v one as it gives a bit more control.

³ To go further, one could attempt to reduce the xdotool delay
between key presses (which defaults to 13 ms). I didn't attempt this as I
assumed that it might reduce the robustness of the method (i.e. keystrokes might
be missed).

⁴ I originally had visions of actually mirroring the buffers.
I.e. you tell Emacs which buffers you want displayed in the document and it will
grab them, insert the code marker, perhaps a simple frame marking the buffer you
are in, and send it to the clipboard to be pasted on the document. I actually
had Emacs sending entire buffers at one point. After I started hitting more and
more issues with clipboards and how Google Docs messes with indentation, or
whitespace, or other things, I decided that this was not worth the effort.