https://gist.github.com/digikar99/b76964faf17b3a86739c001dc1b14a39

Skip to content
 
[                    ]
All gists Back to GitHub Sign in Sign up
 
Sign in Sign up
You signed in with another tab or window. Reload to refresh your
session. You signed out in another tab or window. Reload to refresh
your session. You switched accounts on another tab or window. Reload
to refresh your session.
{{ message }}

Instantly share code, notes, and snippets.

@digikar99

digikar99/why-coalton-is-a-language.org

Last active August 26, 2023 19:34

  * Star 7 You must be signed in to star a gist
  * Fork 2 You must be signed in to fork a gist

Star You must be signed in to star a gist
Code Revisions 3 Stars 7 Forks 2
Embed
What would you like to do?
">Embed Embed this gist in your website.
Share Copy sharable link for this gist.
Clone via HTTPS Clone with Git or checkout with SVN using the
repository's web address.
 
Learn more about clone URLs
[<script src="https:/]
 
Download ZIP
An attempt at introducing Coalton to lispers without a background in
ML-like languages
Raw
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.

 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

Even then, there are reasons I have been reluctant to adopt Coalton:

  * I value portability across implementations. This ensures not only
    that the code can run on different versions of the same compiler
    (assuming there are only incompatible changes due to CLHS's
    ambiguities and not bugs), but also that it might be possible to
    keep using Coalton, and the libraries that depend on it, even
    when you write code for Android at some point in the future. Back
    when I was just starting to be pulled into the whirlpool of type
    systems and polymorphism, Coalton only seemed to support SBCL;
    thanks to the contributors, things seem to have improved more
    recently, and CCL also seems supported in 2023.
  * I have a wish to be able to call coalton functions without
    monomorphizing them. Perhaps, this is a core reason why I haven't
    been able to abandon polymorphic-functions. Calling coalton
    functions without monomorphizing can make them very similar to
    common lisp's own generic functions in terms of calling
    conventions and interactivity! Then again, I don't know what
    deeper issues this might lead to.
  * Error messages should be understandable by people without a
    background in ML-like languages. Using coalton for your project
    means that if the user of your project runs into type errors,
    they will be greeted by an error message that they can only
    decipher if they already have a background in ML-like languages.
    That makes the barrier to entry to your own project even higher!
    Let's not forget that Common Lisp and Emacs themselves have a
    high-enough barrier to entry, and add in ML-like language to the
    mix .

 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!

Sign up for free to join this conversation on GitHub. Already have an
account? Sign in to comment

Footer

 (c) 2023 GitHub, Inc.

Footer navigation

  * Terms
  * Privacy
  * Security
  * Status
  * Docs
  * Contact GitHub
  * Pricing
  * API
  * Training
  * Blog
  * About

You can't perform that action at this time.