Functors in my Emacs?!

In Elsa we represent all types as EIEIO classes inheriting from elsa-type top level class. Primitive types, like integers, strings, symbols are represented by classes elsa-type-int, elsa-type-string, … Then there are more complex types which are rather type functions or type constructors, mapping simple types to more structured types. An example is a "list of something". For this, we have a type elsa-type-list which takes another type as an argument.

To make a list type, we invoke the constructor (elsa-type-list :item-type (elsa-type-string)). This would be a list of strings. Because this is kind of unwieldily, Elsa has a macro to make types: (elsa-make-type (list string)) would construct a list of strings. To express the types from now on, I will use the syntax accepted by elsa-make-type.

There are built-in types for many common types found in Emacs, such as:

• (cons int string) is a cons pair of integers and strings, like (1 . "foo")
• (function (int string) symbol) is a function taking an int and a string and returning a symbol
• (class elsa-type) is an EIEIO class elsa-type
• (struct trinary) is a cl-defstruct named trinary
• (or int marker) is a composite type which is either integer or a string, but we don't really know which one, because user can supply either. This is useful to annotate functions which can take more than one type as their argument, such as goto-char.
• (const :key) represents only the constant value :key and nothing else.
• more can be found in the Elsa manual or reading the code :grin:

Types naturally form a hierarchy. On the top is the type mixed which represents everything and on the bottom is type empty which has no values whatsoever. If you imagine types as sets of values you would be pretty close. One type accepts another if the other type is a subset of the accepting type. Some examples:

(elsa-type-accept mixed string) ;; t, mixed contains all the values
(elsa-type-accept string nil) ;; nil, string can not be nil
(elsa-type-accept symbol keyword) ;; t, every keyword is a symbol
(elsa-type-accept keyword symbol) ;; nil, some symbols are not keywords

;; t, or is a "union" of string and int, and all the strings are
;; included there
(elsa-type-accept (or string int) string)

;; nil, the other argument can be "foo" but that is not a number.
(elsa-type-accept int (or string int))

Notice in the last example that the second type could assume a value 4 which is an integer, so int could accept (or string int), but not always. This can actually be expressed by a three-valued logic and it is in fact what Elsa uses internally, but about that maybe some other time.

Generic types are super useful and basically any analyzer of Elisp would not work without them. The simplest example is the function car. car doesn't care what cons you give it, it will always politely give the value of the first cell back. So as a first attempt we can type it:

(car :: (function ((cons mixed mixed)) mixed))

Which means: it's a function taking a cons of two "anythings" returning an "anything". But that's not really what car does, is it? The car and cdr of a cons cell have concrete and very real types during runtime, we just don't know what they are beforehand. But this idea of "concrete but undetermined" is exactly what generics express.

So a second generic attempt to type this would be:

(car :: (function ((cons &a &b)) &a))

This says that whatever the type of the car cell is (here a type variable &a) is what the car function will return.

Now, this in itself is useless, because in a real program nothing has a "type &a". During the analysis we need to derive what is the actual type that &a represents. Consider the following example:

(car (cons 1 "hello")) ;; => 1

Here, the cons has a type (cons int string) and so by "overlapping" the types we can derive that &a is an int and &b is a string and the return type of the entire car form then must be an int. This process is called unification, because we unify the two type signatures:

(function ((cons &a  &b    )) &a )
           (cons int string)
;; -------
(function ((cons int &b    )) int) ;; &a -> int
           (cons int string)
;; -------
(function ((cons int string)) int) ;; &a -> int, &b -> string
           (cons int string)
;; done

The types were unified and the unifying substitution is &a -> int, &b -> string.

Now, trigger warning for mathematicians. I will be very loose about the terminology. I don't think it matters here very much.

Functor is a fancy word for "structure" and a functor map a more generic mapcar. We can imagine a functor as embedding a function into a structure. If we have a function:

(1+ :: (function (int) int))

we can embed it (somehow) into a list structure to produce a function

(1+-on-a-list :: (function ((list int)) (list int)))

Notice how the argument and return type int became (list int). We embedded the function into a richer structure, here, a list.

If you think about it, that's exactly what mapcar does. A hypothetical syntax (mapcar '1+) without the second list argument is a "function" which expects one more argument, a (list int) and it outputs a (list int).²

         (1+  :: (function (      int)        int))
((mapcar '1+) :: (function ((list int)) (list int)))

A functor map generalizes the lists's mapcar to arbitrary structures. The defining characteristic of a functor map is that the input and output structure is the same and only the "contents" are changed. Using a mapcar on a list we get out a list with updated elements.

Let's try some examples of functors.

First, let's take a cons. A cons is a structure with two "cells", the car and the cdr. To "map" over a cons is to apply a function over the car and the cdr. So an implementation of a functor map (or fmap) might be:

;; (fmap fun (cons      a       b))
;; =>        (cons (fun a) (fun b))

(defun fmap (fun cons-cell)
  (cons (funcall fun (car cons-cell))
        (funcall fun (cdr cons-cell))))

(fmap '1+ (cons 1 2)) ;; => (cons 2 3)
(fmap 'number-to-string (cons 1 2)) ;; => (cons "1" "2")

Another example might be an optional value. Let's define a structure "optional" which is either a value or "nothing". Nothing is distinct from a nil which still is a valid Elisp value. Nothing is an abstraction outside of Elisp type system really meaning absence of anything meaningful (say result of division by zero).

(defclass optional () () :abstract t)
(defclass has-value (optional) ((value :initarg :value)))
(defclass nothing (optional) ())

(has-value :value 7) ;; has value 7
(nothing)            ;; => has no value

We can write a "safe" division by zero using this class like so:

(defun division (a b)
  (if (= b 0)
      (nothing)
    (has-value (/ a b))))

How would we map over this optional structure? It consists of two… options: nothing or has-value. We can treat them one by one:

1. Mapping over nothing must produce nothing because fmap must preserve the structure and there's no structure in "nothing" (well, philosophically, even nothing is a structure of some sort).
2. Mapping over a has-value must also produce a has-value but with the updated content. So the implementation is:

;; (fmap fun nothing)
;; =>        nothing
;; (fmap fun (has-value :value      7))
;; =>        (has-value :value (fun 7))

(defun fmap (fun optional)
  (cond
   ((nothing-p optional)
    ;; nothing in, nothing out.
    (nothing))
   ((has-value-p optional)
    ;; get the value out of the optional, call the function and wrap
    ;; it back into a new has-value.
    (has-value :value (funcall fun (oref optional value))))))

(fmap '1+ (nothing))      ;; => (nothing)
(fmap '1+ (has-value 1))  ;; => (has-value 2)

(fmap 'number-to-string (division 1 0)) ;; => (nothing)
(fmap 'number-to-string (division 1 2)) ;; => (has-value "0.5")

The interesting thing about this example is that we can have a structure composed of multiple substructures and we can treat them on a case by case basis.

If we go back to the list embedding of the 1+ function producing a (list int) to a (list int) function, the embeddings for the cons and optional would look very similar:

;; fmap on cons
((fmap '1+) :: (function ((cons int int)) (cons int int)))
;; fmap on optional
((fmap 'number-to-string) ::
 (function ((class (optional int))) (class (optional string))))

To generalize this further, we can replace the concrete type constructors (such as cons) and type parameters (such as int or string) with type variables:

(fmap :: (function ((function (&a) &b) (&f &a)) (&f &b)))

This rather cryptic line says that a fmap takes a function from &a to &b and a structure (functor) &f holding things of type &a, and it produces the same structure &f holding things of type &b.

Functors on their own do not seem very useful. We have mapcar or the specialized fmap and then what? The real power of these abstractions come when we implement other operations in terms of the generic ones. So let's jump into that to close this one out.

Finally, I should not omit the fact that there are some actual mathematical laws the fmap function must satisfy to be a functor. This blog post article being dense as it is, I leave this to the reader to expand upon. It's not very important when implementing real-world functors as you almost always "have to" do it the right way.

Imagine now that we solved some unification, such as (unify (cons &a int) (cons string &b)) and we got out the unifying substitution &a -> string, &b -> int. How do we actually get the resulting unified type? We perform variable substitution!

To perform substitution on a simple type like int makes no sense, because there is no possible structure to be represented as a variable. This is the trivial case of a thing with no structure. It is only itself and that's it.

More interesting case is that of a list type, which has one type argument. A substitution would dive into the item type argument, try to substitute that, and then construct a new list type with the substituted item type.

Even more interesting is the cons type, which has two type arguments. We first substitute both of them and then construct a new cons type with the substituted type arguments.

In code, it would look something like this:

(cl-defgeneric substitute (this subs))

(cl-defmethod substitute ((this elsa-simple-type) subs)
  ;; Simple type can not substitute anything.
  this)

(cl-defmethod substitute ((this elsa-type-variable) subs)
  ;; Get the substitution from the hash table or return this if there
  ;; is no substitution available.
  (or (gethash (oref this name) subs)
      this))

(cl-defmethod substitute ((this elsa-type-list) subs)
  ;; Substitute the item-type and construct a new list type.
  (elsa-type-list :item-type (substitute (oref this item-type) subs)))

(cl-defmethod substitute ((this elsa-type-cons) subs)
  ;; Substitute the car-type and cdr-type and construct a new cons
  ;; type.
  (elsa-type-cons :car-type (substitute (oref this car-type) subs)
                  :cdr-type (substitute (oref this cdr-type) subs)))

If you squint at the last example really hard, it actually looks a lot like:

(defun fmap (fun cons-cell)
  (cons (funcall fun (car cons-cell))
        (funcall fun (cdr cons-cell))))

How could we implement a fmap for elsa-type-cons?

(cl-defmethod substitute ((this elsa-type-cons) subs)
  ;; Substitute the car-type and cdr-type and construct a new cons type.
  (elsa-type-cons :car-type (substitute (oref this car-type) subs)
                  :cdr-type (substitute (oref this cdr-type) subs)))

;; => substitute "substitute" with "funcall fun" and drop the second
;; argument

(cl-defmethod fmap (fun (this elsa-type-cons))
  ;; Substitute the car-type and cdr-type and construct a new cons type.
  (elsa-type-cons :car-type (funcall fun (oref this car-type))
                  :cdr-type (funcall fun (oref this cdr-type))))

It's the same thing! And this is the power of having generic operations such as functor maps. Once we define fmap for all the "structure-ful" Elsa types, we can write a single unification method in terms of fmap instead of one per each specific type.

-- (cl-defmethod substitute ((this elsa-type-list) subs)
--   ;; Substitute the item-type and construct a new list type.
--   (elsa-type-list :item-type (substitute (oref this item-type) subs)))
--
-- (cl-defmethod substitute ((this elsa-type-cons) subs)
--   ;; Substitute the car-type and cdr-type and construct a new cons
--   ;; type.
--   (elsa-type-cons :car-type (substitute (oref this car-type) subs)
--                   :cdr-type (substitute (oref this cdr-type) subs)))

++ (cl-defmethod substitute ((this elsa-type) subs)
++   (fmap (lambda (x) (substitute x subs) this)))

We can read this as "please, whatever structure this is, substitute every type argument it has recursively and give me back the same structure". Armed with the fmap instances for all the different types, we can implement plethora of other operations which work on the internal elements of these structures while preserving their shapes without ever actually having to be exposed to the structures—it is abstracted away in the functor map. This also frees you from thinking too much about the concrete and rather express the problem in the abstract way leading to (maybe?) increased clarity.

I think here is a good time to stop for now. If you have any questions, hit me up on twitter or on the GitHub repo for this blog (both are in the header).

Next time we will talk about extending functor maps to "zips", which instead of one structure and a function take two structures (of the same shape) and a function to "zip" them into a new structure of the same shape while combining the elements at the same "place" (teaser follows)

(??something?? '+
               (cons 1 2)
               (cons 3 4))
;; =>          (cons 4 6)