Imperfect Software

I recently used the emacs package manager to update smartparens, and in doing so broke it. I was greeted with an error message proclaiming that -fix was not defined. It turned out that I had installed dash.el by hand and so it was not updated by the package manager. The new version of smartparens used the newly introduced -fix function. Installing dash via the package manager resolved the problem, but I was intrigued as to what this new function was.

The function’s doc string was impenetrable to me:

Compute the (least) fixpoint of FN with initial input LIST.

FN is called at least once, results are compared with `equal’.

Searching the web for “function fixpoint” led me to the Wikipedia definition:

[…] an element of the function’s domain that is mapped to itself by the function.

which was similarly unhelpful in shedding light on the problem. Looking at where -fix was used in smartparens, there’s a lot going on in a few lines of code.

(defun sp--update-local-pairs ()
  
  (let ((parent-modes (-fix (lambda (x)
                              (--if-let (get (car x) 'derived-mode-parent)
                                  (cons it x)
                                x))
                            (list major-mode))))
    ;; Combine all the definitions from the most ancient parent to the
    ;; most recent parent
    (--each parent-modes (sp-update-local-pairs it))))

So taking further advantage of the fact that source code is available I looked at the definition of -fix

(defun -fix (fn list)
  (let ((re (funcall fn list)))
    (while (not (equal list re))
      (setq list re)
      (setq re (funcall fn re)))
    re))

This is a bit clearer and suddenly the previous explanations make sense. Call fn on list recursively, stopping only when further invocations no longer alter list. Looking back at its use in sp--update-local-pairs, we start with a list consisting only of the current major mode, and then expand that list with the parents of that mode, stopping when there are no more parents.

I was intrigued by this elegant way of writing a recursive statement without explicit recursion and surprised I hadn’t come across it before. Looking at other languages, Haskell, perhaps unsurprising, has an implementation in Data.Function defined as

fix :: (a -> a) -> a
fix f = let {x = f x} in x

Chris Smith provides a good descriptions of the use of Fix points in Haskell that gives some of the theoretical background to the value of fix without being too detailed. The Haskell wiki book also provides an introductory level explanation.