A good type system for prototype inheritance

[fare]

Summary

Prototype inheritance in the style of Jsonnet or Nix on top of a pure lazy functional language is exactly what the doctor ordered to assemble complex configurations in simple incremental touches. The pure and lazy aspect really work well with the fixed point computations, much more so than the effectful eager context of Self or JavaScript.

Your mission is to write a good implementation of such a language that includes a type system capable of dealing with what comes naturally in this style of object-oriented programming. Notably, you'll need some kind of row polymorphism with associative commutative row variables to represent the field identifiers and their types. Bonus points if you can deal well with identifier renaming and shadowing.

Basic Concept

Prototype inheritance can be implemented in 99 characters of Scheme, where the function make instantiates a prototype, and inhr composes two prototypes via inheritance:

(define (make p b) (letrec ((f (p (λ a (apply f a)) b))) f))
(define ((inhr p q) f s) (p f (q f s)))

With more details, the prototype for a (function) type R is a function from a R*R to R, of the form (λ (self super) …) where self is the recursively-defined fixed-point itself, and super the super-object it inherits from.

The first function makes an instance of the given prototype, i.e. a fixed-point, starting from a specified bottom object. Note how (λ a (apply self a)) is actually a self-reference to f, protected by the λ, and made necessary because Scheme is eager rather than lazy (and could be usefully replaced by a lazy reference, if available in your Scheme dialect, especially in presence of other side-effects).

(define (make-instance prototype bottom)
  (letrec ((self (prototype (λ a (apply self a)) bottom)))
    self))

The second function combines two prototypes, this one with a parent, to build a new prototype via inheritance. Below, this and parent are prototypes; self and super are objects instantiating the prototypes. Prototypes and objects are of very distinct types.

(define inherit (this parent)
  (λ (self super) (this self (parent self super))))

Here, prototypes and objects are just functions, but you can define usual fields trivially with

(define (bottom . x) (error "bottom"))
(define (((field k v) self super) x) (if (equal? x k) v (super x)))
(define my-object (instance (field 'x 1) (field 'y 2)))

Problem is, when you try to give a type to inhr, you'll find that unless your type system has some real advanced row polymorphism, your types will be oh too monomorphic. Incidentally, this monomorphism is enough to define the behavior of class-inheritance in terms of prototype-inheritance of class-descriptors at the meta-level. But then you need good reflection support in your language to express the passage to the meta-level and back.

Potential Approaches

• Use Jsonnet or Nix to get familiar with the kinds of cool advanced uses one can make of prototype inheritance.
• Use UrWeb or Ermine and see what types they give to non-trivial programs using inheritance in the style of Jsonnet or Nix.
• Start from Tix, and complete it if needs. be
• Experiment a new language in Racket.
• Start from hnix and add a type system to it.

Inspiration

• Tix an attempt to give a good type system for Nix.
• Jsonnet for a language that well documents the semantics of prototype inheritance.
• Nix — see the functions extends and composeExtensions in nixpkgs/lib/fixed-points.nix that implement Jsonnet-equivalent prototype inheritance in two functions totaling six lines of code.
• Self for initially introducing prototype inheritance.
• JavaScript for bringing it to the masses.
• Slate for combining prototype inheritance with multimethods.
• hnix, an implementation of Nix in Haskell.
• UrWeb, maybe the first functional language that had a type system strong enough to express prototype inheritance.
• Ermine, maybe the second such language.

[fare]

See also my prototype inheritance library in Gerbil Scheme at https://github.com/fare/gerbil-utils/tree/master/poo