The path to Deriving

[gefjon]

---

author: phoebe goldman
title: the path to deriving

The recent implementation of Addressable serves as a proof-of-concept
for how we can implement a general derive (or deriving) mechanism,
akin to Rust's #[derive(...)] type .... annotations and Haskell's data ... deriving (...)
definitions.

In this document, my focus is strictly on semantics and implementation,
not on syntax. For illustration purposes, I'll adopt a Coalton-ified
version of Rust's annotations similar to what we use for repr (see
below). Do not treat this as a sytnax proposal; I just think it's an
obvious way to illustrate what I'm talking about.

(derive Eq Hash)
(define-type Foo
  (FooA UFix)
  (FooB String))

Semantically, that definition should, in addition to defining the type
Foo and its constructors FooA and FooB, define instances
(Eq Foo) and (Hash Foo). It might be treated as meaning something
like:

(define-type Foo
  (FooA UFix)
  (FooB String))

(define-instance (Eq Foo)
  (define (== x y)
    (match (Tuple x y)
      ((Tuple (FooA x) (FooA y)) (== x y))
      ((Tuple (FooB x) (FooB y)) (== x y))
      (_ False))))

(define-instance (Hash Foo)
  (define (hash x)
    (match x
      ((FooA x) (hash x))
      ((FooB x) (hash x)))))

Note that both of the generated instances do something obvious and
uninteresting, namely, they destructure the type and apply the relevant
method to its members.

As of Coalton commit 2a98108 (2022-06-17), here's how I think we
would implement that behavior in the Coalton compiler:

• Add a slot derived-instances to the defstruct type-definition
  defined in parse-type-definition.lisp, which holds a list of
  "derive specifiers." For a first implementation, these specifiers
  might be symbols naming classes, but if we want to support
  Haskell's deriving via, we might need to suppliment them with
  additional info.

• Keep a map from "derive specifiers" to "derive expanders," which
  are Common Lisp functions from type-definition to S-expressions,
  which should return a define-instance form.
  make-auto-addressable-instance, defined in
  toplevel-define-type.lisp, can serve as the prototypical "derive
  expander."

  • "derive expanders" should probably have some interface for
    signaling an error.

  • Should a "derive expander" have access to any other
    information? Should it take an environment as an additional
    argument? I'm inclined to say no, unless someone can point to a
    good reason otherwise.

  • It may one day become useful to allow users to define their own
    "derive expanders," ideally as Coalton functions. For now,
    I'll concern myself only with built-in expanders.

• During process-parsed-toplevel-type-definition (defined in
  toplevel-define-type.lisp), for each "derive specifier" in
  (derived-instances parsed-deftype), search the expander map for an
  appropriate expander. If one exists, call it to produce a
  define-instance form, and return a list of derived
  define-instance forms.

  • process-parsed-toplevel-type-definition currently returns
    either nil or exactly one define-instance form, but it could
    easily be adapted to return a list of zero or more
    define-instance forms.

• process-toplevel-type-definitions will then collect all the
  derived define-instance forms, and process-coalton-toplevel will
  pass them through the compiler pipeline as appropriate. This
  infrastructure already exists, except that
  process-toplevel-type-definitions will need to replace its
  when ... push with an append.

Note that, unlike Addressable, instances derived with an explicit
annotation will not necessitate the class being "early;" the class
just needs to be defined before compiling a type definition which
derives an instance on it.

In summary, the nontrivial work remaining is:

• Decide on a syntax for our derive mechanism.
• Define an internal representation for "derive expanders," and
  a procedure for searching the available expanders and invoking the
  appropriate one, erroring if none is found or if the invoked
  expander fails.
• Define built-in expanders for a whole bunch of library classes.

[eliaslfox]

I like (derive Eq Hash).

Having a dynamic system for registering derive expanders seems over engineered for builtin type classes. I think we could just use a case expression.

[gefjon]

I think a case expression (ecase, specifically), would count as the mapping I described, and seems like a great first implementation.