An attempt at introducing Coalton to lispers without a background in ML-like languages

why-coalton-is-a-language.org

Coalton: Why is the interop not easier, and why might it be necessary for Coalton to be an entire language in itself?

If you came here searching for the context in which some reddit comments were written, you might want to check out this previous version of the article.

Several blog posts have been written about Coalton, about how it can be useful and what it brings to the table. However, to me, it hasn’t been clear why Coalton is the way to solve the problems that it does solve. Isn’t a simpler solution possible without making a full embedded language, and giving users the cognitive overhead of thinking about interop between normal lisp and coalton?

I have been thinking about this for a while as one of my pasttimes, and below I’ll summarize the better reasons why coalton might be the way it is. Perhaps, I couldn’t see it because I didn’t know the ML type system, but then, this article is directed at exactly those readers who do not know the ML type system.

The problems with ANSI Common Lisp

First, let’s summarize the problems with ANSI Common Lisp.

The obvious problems

No compile time type inferencing

While compile time type checks may not catch all the errors, and are definitely not a replacement for a test-suite, they are nonetheless helpful for quick feedback and keeping the debug-rewrite loop short. ANSI Common Lisp provides no guarantees about this; SBCL does try hard to attempt it, but there will be cases where it fails.

In recent years, there is also cl-form-types that tries to use the CLTL2 environment API to achieve portable type inferencing. But this has to be put to use through macros and compiler-macros.

Generics are an afterthought, and are dynamic

The Common Lisp Object System (CLOS) is fairly well-respected. However, perhaps to maintain compatibility with lisps existing at that time, the Common Lisp standardization process could not make all functions into generic functions.

Moreover, thanks to the lack of compile time type inferencing, and perhaps also due to their semantics, generic functions have to be necessarily dispatched dynamically. Again, there have been solutions proposed for this, albeit none of them portable beyond two to three implementations: fast-generic-functions, specialization-store, polymorphic-functions.

The non-obvious problems

The above problems are quite well-known and many of us might have come across them. But, as someone without a background in ML-like languages, finding the below problems required a fair bit of digging and thinking to see things for myself.

Let us start with history. In 1989, How to make ad-hoc polymorphism less ad hoc (it seems to be an easy read, but we will discuss the idea below) was published by Walder and Blott. In 1994, ANSI Common Lisp came into existence. And while Common Lisp existed even in 1984, the CLTL1 published by Guy Steele does not suggest the existence of CLOS or generic functions.

Nonetheless, ANSI CL does make some effort to integrate types and classes:

The purpose of specifying that many of the standard type specifiers have a corresponding class is to enable users to write methods that discriminate on these types. Method selection requires that a class precedence list can be determined for each class.

The hierarchical relationships among the type specifiers are mirrored by relationships among the classes corresponding to those types.

However, it seems like tying classes to types in this manner has been a bad decision* in two related parts:

1. Especially in the context of multiple inheritance, subtyping is not the same as subclassing.
2. If generic functions are the equivalent of interfaces, then as the Walder and Blott paper suggests they should be independent of the classes of the arguments.

*I don’t intend to criticize the committee, it did what it did, and perhaps the best it could have done given the finite time and resources. The decision looks bad only in retrospect, because now we know better.

Confuses subtyping with subclassing

For a long time, I had believed that subtyping is the same as subclassing. And, this notion doesn’t seem uncommon, given that people regularly request for extensible sequences and custom hash tables amongst other things.

What defines a sequence? A functional notion would suggest the intuition that if an object s provided a way to map from a given natural number to another object, then that object s seems good enough to qualify as a sequence - no matter what the actual class of the object! So, it seems like a “type” can be defined in terms of the functions, methods, or whatever-callable it requires - almost like an interface - rather than something else.

The lecture notes from here elaborate on this difference:

In the object-oriented framework, inheritance is usually presented as a feature that goes hand in hand with subtyping when one organizes abstract datatypes in a hierarchy of classes. However, the two are orthogonal ideas.

• Subtyping refers to compatibility of interfaces. A type B is a subtype of A if every function that can be invoked on an object of type A can also be invoked on an object of type B.
• Inheritance refers to reuse of implementations. A type B inherits from another type A if some functions for B are written in terms of functions of A.

In the object-oriented framework, if B is a subclass of A then it is clear that B is a subtype of A. Very often, B also inherits from A–for example, recall the way the implementation of bonus() for Manager called on the function bonus() defined in Employee.

However, subtyping and inheritance need not go hand in hand. Consider the data structure deque, a double-ended queue. A deque supports insertion and deletion at both ends, so it has four functions insert-front, delete-front, insert-rear and delete-rear. If we use just insert-rear and delete-front we get a normal queue. On the other hand, if we use just insert-front and delete-front, we get a stack. In other words, we can implement queues and stacks in terms of deques, so as datatypes, Stack and Queue inherit from Deque. On the other hand, neither Stack not Queue are subtypes of Deque since they do not support all the functions provided by Deque. In fact, in this case, Deque is a subtype of both Stack and Queue!

In general, therefore, subtyping and inheritance are orthogonal concepts. Since inheritance involves reuse of implementations, we could have an inheritance relationship between classes that are incomparable in the subtype relationship. In a more accurate sense, this is what holds between Stack, Queue and Deque. The type Stack supports functions push and pop that are implemented in terms of the Deque functions insert-front and delete-front. Similarly, Queue support functions insert and delete that are implemented in terms of the Deque functions insert-rear and delete-front. The function names are different, so none of these types is comparable in the subtype relation, but Stack and Queue do inherit from Deque.

Indeed, some lispers have noticed this before. Lisp Interface Library seems to be primarily built to separate these two notions of implementations and interfaces. Also see this article by Kent Pitman.

Above, the terms might be a fair bit overloaded. To clarify:

Used in \ Meaning	Refers to implementation	Refers to interface
ML-based languages	Type	Typeclass
The above lecture notes	Class	Type

Generics depend on the implementation details of their arguments, not their interface details

Once the difference between types/classes/implementation and typeclasses/types/interfaces is clear, it is possible to see that generics should depend on the interface details of their arguments and not their implementation details. Lisp Interface Library does exactly this!

However, given that these insights were discovered after 1994 ANSI Common Lisp came into existence, they are absent from the ANSI standard.

Parameterizing over argument types is a PITA

Parameterizing functions or data-structures over the types of its arguments requires an equivalence class for its arguments. Given an integer 5 or a float 5.0, ML-based languages can quite clearly state that their canonical type is int and float respectively. The compilers have sensible defaults for inferring the types; and in some cases, the language also provides users the option to override them.

Common Lisp has a hard time indicating if the canonical type of 5 is a type of integer or fixnum or (signed-byte 32) or (unsigned-byte 7) and so on and so forth. There are far too many possibilities. And even though CLHS might have some instructions about what should be done, the overspecified types pose an issue for parameterizing over them. Really,

• Does a (simple-array single-float (2 3)) have the same type as (simple-array single-float (4 3))?
• What about (simple-array single-float (12))?
• Or (simple-array double-float)?
• How about (array single-float (2 3))?

It’s not clear which of these should be considered equivalent! Indeed, the choice depends on the particular use at hand, but compromising with sensible defaults and lesser choices seems like a good option (?).

To understand the problem, let us assume that there was a way to define parametric types in ANSI CL, and that (pair <t1> <t2>) was one such type (structure) with slot accessors pair-x and pair-y. Similarly, assume that there was a way to define a parametric function as follows:

(define-parametric-function add-pair
    ((a (pair <t1> <t2>)) (b (pair <t1> <t2>)))
    (pair <t1> <t2>)
  (make-pair :x (add (pair-x a) (pair-x b))
             :y (add (pair-y a) (pair-y b))))

The above definition intends to say that add-pair is a function that takes two pairs of identical types, and returns another pair of identical type, with its slots formed by the sum of the correspondings slots of the two arguments.

Ignoring any other inconsistencies that the above requires, let us see the issues involved in determining what kinds of arguments that the add-pair function can actually take.

• Can it take #S(PAIR :X 5 :Y 6.0) and #S(PAIR :X 5 :Y 6.0)? The answer seems to be “yes” for all practical purposes.
• Can it take #S(PAIR :X 5 :Y 6.0) and #S(PAIR :X 10 :Y 6.0)? The answer is actually “no” if we treat 5 to have the type (eql 5); but the answer is “yes” if we treat 5 to have the type integer.
• Can it take #S(PAIR :X 5 :Y 6.0) and #S(PAIR :X 5.0 :Y 6.0)? The answer is no if we treat 5 to have the type integer; but the answer is yes if we take 5 to have the type number.
• Can it take #S(PAIR :X 5 :Y 6.0) and #S(PAIR :X "hello" :Y 6.0)? The answer is no if we treat 5 to have the type number; but the answer is yes if we take 5 to have the type cl:t. This gets as absurd as possible.

Which of these do we take as the canonical type of 5?

The problem does not disappear even if we try to establish the similarity in terms of classes. On SBCL,

• (class-name (class-of #(0 1))) returns SIMPLE-VECTOR
• (class-name (class-of (make-array 10 :element-type 'single-float))) returns SB-KERNEL::SIMPLE-ARRAY-SINGLE-FLOAT
• (class-name (class-of (make-array '(2 3) :element-type 'single-float))) returns SIMPLE-ARRAY

Resolving this requires nothing short of an entire type system with saner defaults. Which Coalton does provide.

PS: I have come across the term “Principal Type”, but after a careful reading, it seemed like the above problem is slightly different from Principal Types, since the latter talks about the types being instances of the principal type, while the former (and the above discussion) is concerned about values being instances of the… canonical… type.

PPS: Recently, I discovered a critical issue with the above understanding of parameterizing over argument types. The issue becomes apparant when one allows the typing system to have subtyping. In the presence of subtyping, all four of the argument pairs mentioned above are valid arguments for add-pair. This seeming insanity arises when one views the types and arguments of add-pair in isolation to the rest of the system - it disappears when one begins discussing the call sites of add-pair! See this comment for the resolution.

Generic numbers are prone to errors, but dispatching on return types makes non-generic numbers easy to deal with

Integers (bignums), rationals, floats are some of the different number types available in many programming languages. Unfortunately, none of them are a superset of the other with respect to all the operations, and each presents some difficulty.

To quote a page on the HaskellWiki:

Question: Can I have a generic numeric data type in Haskell which covers Integer, Rational, Double and so on, like it is done in scripting languages like Perl and MatLab?

Answer: In principle you can define a type like

data GenericNumber =
    Integer Integer
  | Rational Rational
  | Double Double

and define appropriate instances for Num class et. al. However you will find that it is difficult to implement these methods in a way that is appropriate for each use case. There is simply no type that can emulate the others. Floating point numbers are imprecise - a/b*b==a does not hold in general. Rationals are precise but pi and sqrt 2 are not rational. That is, when using GenericNumbers you will encounter exactly the problems that all scripting language users have encountered so far (or ignored :-).

A GenericNumber type would also negate the type safety that strongly typed numbers provide, putting the burden back on the programmer to make sure they are using numbers in a type-safe way. This can lead to subtle and hard-to-find bugs, for example, if some code ends up comparing two floating-point values for equality (usually a bad idea) without the programmer realizing it.

I’d highly recommend reading the HaskellWiki page for the examples.

So, non-generic numbers actually seem better, and requiring programmers to explicitly convert between them seems like a good way to do things. Indeed, they can get annoying at times. The wiki page lists the following example of implementing an average function:

You may find it cumbersome to manually convert integers to fractional number types like in

average :: Fractional a => [a] -> a
average xs = sum xs / fromIntegral (length xs)

and you may prefer

average :: [GenericNumber] -> GenericNumber
average xs = sum xs / genericNumberLength xs

with an appropriate implementation of genericNumberLength. However, there is already Data.List.genericLength and you can write

average :: Fractional a => [a] -> a
average xs = sum xs / genericLength xs

Here, the return type of genericLength depends on the surrounding context! If the surrounding context requires it to be a float, it will be a float. If the surrounding context requires it to be an integer, it will be an integer, and so on.

Such dependence of the return value on the return type is impossible in a dynamically typed language! There, you can only know the return type after the return value is computed at run time. Thus, a statically typed language can also be helpful in making non-generic numbers less annoying while helping maintain numeric type safety and avoid subtle bugs.

Coalton solves all of these!

Coalton is an efficient, statically typed functional programming language that supercharges Common Lisp.

No, that’s not the point!

Coalton is an efficient, statically typed functional programming language, that provides clean canonical types, and also a principled distinction between interface and implementation, and thus supercharges Common Lisp.

That is the point!

My coalton wishlist

In a previous version of this article, I had mentioned some wishes. But turns out that many of them have already been dealt with. The current wish is primarily about a coalton:inline declaration.

Conclusion: It’s hard (if possible at all!) to solve all of the problems without creating a separate language.

We have Common Lisp with its excellent compiler SBCL, that performs static-time type checks as well as many optimizations using declarations. Until now, some of us thought that all things are rosy, and with some effort it should be possible to put that to “good use”, and lo-and-behold we can have a proper generic common lisp with type inferencing, without it being an embedded language like coalton. It is only after running into the above non-obvious problems that that solutions that do not provide a complete language in itself have begun to feel like dead-ends.

Hopefully now, no more people run into the dead-ends we ran into and instead adopt and contribute to Coalton.

PS

I don’t have any specialized background in programming languages and I’m learning on the go. So, feel free to suggest any misconceptions or ambiguities I might be misleading the reader into!