Self Types
I had blogged previously about the type of the M combinator. This is “dup apply” in Cat or “dup i” in Joy. The issue is that the type is self-referential: it only accepts functions which accept themselves as input. I had previously planned on using labeled types (i.e. type variables with implicit constraints) to deal with such scenarios, however I am now considering just using “self” types. A “self” type is a reference to an enclosing function type. This will allow me to define the type of “M” as (’A (’A self -> ‘B) -> ‘B). In other words “M” accepts only functions that accept themselves as a parameter on the top of the stack. This is significantly less expressive than type labels, but should be sufficient to cover all Cat programs that are likely to occur in practice. I’d appreciate it if anyone can think of a Cat (or Joy) program which is useful but can’t be typed using this scheme.