Musings of a mathematician and aspiring programmer

## Month: October, 2011

### A persistent command history in Emacs

If you run interactive interpreters (e.g., `python`, `irb`, `ghci` etc.) inside Emacs, you have probably observed that they lose command history between sessions. This is very annoying, and below I offer a way to fix it.

Emacs interpreter modes are derived from `comint` mode. The command history is called an input ring and is stored in the buffer-local variable `comint-input-ring`. Furthermore, `comint` offers some facilities for reading/writing the input ring from/to a history file. In particular, the name of the history file is given by the variable `comint-input-ring-file-name`, and the functions that read/write the input ring are `comint-read-input-ring` and `comint-write-input-ring`. The variable `comint-input-ring-file-name` is buffer-local, and can be `nil`, in which case the above functions are no-ops. We would like Emacs to behave as follows: whenever we run an interpreter, its input ring is read from a file associated with that interpreter and is written to that file when we quit the interpreter. The former is easy to achieve: this is what mode hooks are for. We can associate with each interpreter a file in which its history will be stored, for example `inferior-haskell-history` for `ghci` and `inferior-ruby-history` for `irb`, and in the corresponding mode hook we can set the variable `comint-input-ring-file-name` to the appropriate value and call `comint-read-input-ring`. The latter is slightly more involved. We want to write the input ring to the file when the interpreter process exits. This is achieved by changing the process sentinel. From the documentation:

A process sentinel is a function that is called whenever the associated process changes status for any reason, including signals (whether sent by Emacs or caused by the process’s own actions) that terminate, stop, or continue the process. The process sentinel is also called if the process exits. The sentinel receives two arguments: the process for which the event occurred, and a string describing the type of event.

So, the idea is to change (again, in the mode hook) the process sentinel to the function that will not only insert the event description into the process buffer, but will also write the input ring to the history file. Here is an implementation:

```(defun comint-write-history-on-exit (process event)
(comint-write-input-ring)
(let ((buf (process-buffer process)))
(when (buffer-live-p buf)
(with-current-buffer buf
(insert (format "\nProcess %s %s" process event))))))

(defun turn-on-comint-history ()
(let ((process (get-buffer-process (current-buffer))))
(when process
(setq comint-input-ring-file-name
(format "~/.emacs.d/inferior-%s-history"
(process-name process)))
(set-process-sentinel process
#'comint-write-history-on-exit))))
```

Now, to enable reading/writing of command history in, say, `inferior-haskell-mode` buffers, simply add `turn-on-comint-history` to `inferior-haskell-mode-hook`:

```(add-hook 'inferior-haskell-mode-hook 'turn-on-comint-history)
```

Unfortunately, the above solution doesn’t always work. For example, the input ring is not written to the file if the buffer associated with the process is killed, because the process sentinel is invoked when buffer-local variables (in particular, `comint-input-ring-file-name` and `comint-input-ring`) are gone. Therefore we also add `comint-write-input-ring` to `kill-buffer-hook`; this has no effect if the buffer is not associated with a process or doesn’t have `comint-input-ring-file-name` set:

```(add-hook 'kill-buffer-hook 'comint-write-input-ring)
```

However, even this is not enough. Apparently, when Emacs itself is killed, `kill-buffer-hook` is not run on individual buffers. We can circumvent this problem by adding a hook to `kill-emacs-hook` that traverses the list of all buffers and writes the input ring (if it is available) of each buffer to a file.

```(defun mapc-buffers (fn)
(mapc (lambda (buffer)
(with-current-buffer buffer
(funcall fn)))
(buffer-list)))

(defun comint-write-input-ring-all-buffers ()
(mapc-buffers 'comint-write-input-ring))

```

### The magic of fixed points

A few days ago my wife received the following through VKontakte, the Russian clone of Facebook:

Find out your phone number on the calculator!

1. Take the calculator.
2. Enter the first 3 digits of your phone number.
3. Multiply by 80.
5. Multiply by 250.
8. Subtract 250.
9. Divide by 2.
10. Enjoy!

I was amused to see my wife getting amazed by this, arguably trivial, arithmetic trick. I leave it to you as an easy exercise to figure out how it works. However, this trick has reminded me of the following, a lot more sophisticated trick, which I learned when I was a kid.

Select any 21 cards from a complete set of playing cards. Give the deck of cards to your spectator, let her pick one card, and ask her to remember it. Let your spectator shuffle the cards. Now deal the deck, opening the cards one by one from the top, in the following pattern: place the first card into the first, leftmost pile; place the second card into the second, middle pile; place the third card into the third, rightmost pile; place the fourth card into the first pile again, and so on. Ask your spectator to watch you deal the cards and to show you the pile containing her card. Collect the cards, sticking that pile between the other two piles, and repeat the whole procedure 2 more times. Then open the cards one by one. The card of your spectator is always going be the 11th card in the deck.

When I was a kid, I was fascinated by this trick. I still think it is pretty neat. I was very proud then to have figured out how it works. Although I don’t remember the proof anymore, I remember that it was terribly complicated, and included some lengthy case analysis. Today I would like to present a simple and elegant proof.

For brevity, let us call the card your spectator has chosen the secret card. Let $n$ be its position in the deck, counted from the top. Let us compute the new position of the secret card in the deck after the cards have been dealt and collected back. It is easy to convince yourself that relative to its pile the secret card is going to end up at position $\lceil n/3\rceil$ counted from the bottom of the pile, or equivalently at position $8-\lceil n/3\rceil$ counted from the top of the pile. Here $\lceil x\rceil$ denotes the ceiling function of $x$, i.e., the smallest integer not less than $x$. Because the pile containing the secret card is placed between the other two piles, each of which consists of 7 cards, it follows that relative to the whole deck the secret card is going to land at position

$\displaystyle f(n) = 7 + 8 - \lceil n/3\rceil=15-\lceil n/3\rceil$

from the top of the deck.

Let us summarize: if the secret card is the $n$-th card in the deck, counted from the top, then dealing the cards once will place the card at position $f(n)$ from the top in the deck. Dealing the cards the second time will place the secret card at position $f(f(n))$. Finally, dealing the cards the third time will place the secret card at position $f(f(f(n)))$. We have a function $f$ from the set $\{1, 2, \dots, 21\}$ to itself given by the formula $f(n)=15-\lceil n/3\rceil$, and in order to justify the trick we must prove that for any $1\le n\le 21$ holds $f(f(f(n))) = 11$.

What is special about 11? It is the middle of the deck, but it is also a (unique) fixed point of the function $f$:

$\displaystyle f(11) = 15 - \lceil 11/3\rceil = 15 - 4 = 11.$

Therefore, we have to show that for any $1\le n \le 21$, the sequence of iterations $f(n)$, $f(f(n))$, $f(f(f(n)))$, … converges to the fixed point 11, and in fact in at most 3 steps. Let us see why this is the case. The key observation here is that the function $f$ is clearly non-increasing, i.e., $f(n_1) \le f(n_2)$ if $n_1\ge n_2$. Because $n$ lies between 1 and 21, it follows that

$\displaystyle 8 = f(21)\le f(n)\le f(1) = 14.$

Iterating this argument, we find that

$\displaystyle 10 = f(14)\le f(f(n))\le f(8) = 12,$

and consequently

$\displaystyle 11 = f(12) \le f(f(f(n)))\le f(10) = 11,$

so that $f(f(f(n)))$ is necessarily equal to 11. Q.E.D.

Exercise. Use this technique to generalize the trick. For example, if you take 33 cards instead of 21, and deal the cards 4 times instead of 3, then the secret card will be the 17th card in the deck.

If you are familiar with the Banach fixed point theorem, you may be tempted to apply it here (I was). Unfortunately, it doesn’t work, as the map $f$ is not a contraction mapping; for example,

$\displaystyle |f(3)-f(4)| = |14 - 13| = 1 = |3 - 4|.$

Fortunately, this kind of heavy artillery is not necessary here.