PELTADOT: PELTADOT Extends Lisp's Types And Dispatches Over Them

1Contents

:PROPERTIES::TOC: :include all :depth 3 :ignore this:END:

:CONTENTS:

• Issues with standard common lisp we wish to address
• Installation
  • Using download-dependencies
  • Using quicklisp
  • Using ultralisp
• Usage
• Why a shadowing CL package?
• Contrasting peltadot with other systems
  • Dynamic Typing
  • Polymorphically typed structures vs functions
  • Parametrically typed structures

:END:

2Issues with standard common lisp we wish to address

1. CLOS methods dispatch over common lisp classes but not types. There does not seem to be any trivial way to adapt MOP to dispatch on types instead of classes. Thus, there is no way for ANSI common lisp to dispatch over specialized array types.
2. ANSI common lisp does not allow defining user-defined compound types similar to the builtin (vector &optional element-type) or (integer &optional lower-limit higher-limit). Types defined using CL:DEFTYPE are what CLHS calls derived type specifiers, that is, mere abbreviations and simple combinations of existing types.
3. CLOS-based multiple dispatch might not be the best way to implement adhoc polymorphism compared to traits.
4. cl:coerce is non-extensible.

These issues have previously been addressed using polymorphic-functions, extensible-compound-types, extensible-optimizing-coerce, coupled with a number of add-ons and supporting libraries. Even though modularity can be great at times, it seemed that the these projects had become more closely related than what was originally envisioned. Thus, the current project aims to bring all of them together. This would make the update process as well as the usage easier.

3Installation

All the three methods ultimately depend on the quicklisp client. Install it by following the instructions here.

3.1Using download-dependencies

Clone to somewhere asdf can find. If you have installed quicklisp, $QUICKLISP_HOME/quicklisp/local-projects/ is a usual location.

cd $QUICKLISP_HOME/quicklisp/local-projects/

git clone https://github.com/digikar99/download-dependencies

Running the following in lisp will download or update peltadot as well as some of its dependencies to *dependencies-home*.

(asdf:load-system "download-dependencies")
(let ((download-dependencies:*dependencies-home*
        (first ql:*local-project-directories*)))
  (download-dependencies:ensure-system
   "peltadot"
   :source-type :git
   :source "https://gitlab.com/digikar/peltadot.git/"))

Finally, the system can be loaded using quicklisp.

(ql:quickload "peltadot")

3.2Using quicklisp

As of March 2024, peltadot is yet to be added to the quicklisp dist. Once added, you can install it by

(ql:quickload "peltadot")

3.3Using ultralisp

(ql-dist:install-dist "http://dist.ultralisp.org/" :prompt nil)
(ql:quickload "peltadot")

Sometimes, ultralisp can take a long time to update systems, in that case, you might want to use download-dependencies to install or update peltadot and its dependencies.

4Usage

The goal is to make peltadot package a drop-in replacement to the common-lisp package. Thus, instead of

(defpackage #:my-package
  (:use #:cl))

you can simply write

(defpackage #:my-package
  (:use #:peltadot))

Peltadot package contains a number of additional as well as CL-shadowing symbols to help address the above issues. These may be introduced through the following pages.

1. Introduction to Extensible Types
2. Tutorial on Polymorphic Functions
3. Orthogonally specializing types and Type templating in Polymorphic Functions
4. Tutorial on Traits
5. Extensible Coerce

Amongst these, articles 1, 2, 4, 5 can be read independently of others. Article 3 however requires article 1 and 2 as a prerequisite.

5Why a shadowing CL package?

At the heart of peltadot (and earlier extensible-compound-types) is a user defined declaration peltadot:type or peltadot:extype. Unfortunately, declarations in ANSI common lisp are not macros - they are not subject to expansion and are taken verbatim.

However, for optimization, implementations require type information through cl:type declaration or the cl:the special form. Thus, the peltadot:type declarations need to expand into cl:type declarations. This necessitates the need for a shadowing CL package, in which all the special forms and macros that provide facilities for declaration are shadowed by equivalent macros that expand peltadot:type declarations into cl:type declarations.

It may be argued that the cl:type declarations may directly be modified through the define-declaration form of the peltadot:type, however:

The consequences are undefined if decl-name is a symbol that can appear as the car of any standard declaration specifier.

The consequences are also undefined if the return value from a declaration handler defined with define-declaration includes a key name that is used by the corresponding accessor to return information about any standard declaration specifier. (For example, if the first return value from the handler is :variable, the second return value may not use the symbols dynamic-extent, ignore, or type as key names.)

– 8.5 Environments, Common Lisp the Language, 2nd Edition

6Contrasting peltadot with other systems

Coalton addresses all concerns (and more). However, in doing so, it becomes a DSL in itself. And, in fact, it seems that solving these concerns (and beyond) is best done by a DSL.

However,

1. A DSL adds cognitive overhead for interop.
2. Common Lisp already has a steep learning curve. It doesn't seem wise to add standard-ML to the mix and steepen the learning curve even further.
3. Hindley-Milner (standrad ML) type system has its limitations.

The question then remain: what subset of common lisp issues solved by coalton are solvable without requiring a DSL? The necessity for coalton to be a DSL stems from atleast two issues:

1. A separate type system.
2. A compilation step involving constraint solving that requires two way transmission of information aka between callee/producers and callers/consumers.

Thus, any solution that wants to avoid becoming a DSL (i) has to be reasonably transparent with respect to the standard common lisp type system (ii) its compilation should not require two way information transmission, because standard common lisp only enables one way transmission of information through its macros and compilation macros.

Being transparent with respect to the standard common lisp type system means implementing the machinery of subtyping as well as lisp's myriad varieties of and, or, eql, satisfies types.

Foregoing two-way transmission of information means we cannot have expressions whose return type depend on the surrounding code. This means we cannot have polymorphically typed expressions. A polymorphic function cannot be made to dispatch on the return type. In contrast, ML-based coalton allows dispatching on the return type as well as allows expressions to be polymorphically typed.

The features are then summarized below:

Feature	common lisp	peltadot	coalton
Static typing	No	Yes	Yes
Dynamic typing	Yes	Yes	No
Polymorphically typed expressions	No	No	Yes
Return-type polymorphism	No	No	Yes
Polymorphically typed functions	No	Yes	Yes
Polymorphically typed structures	No	No	Yes
Parametrically typed structures	No	Yes	Yes
Zero run-time overhead structures	No	No	No

6.1Dynamic Typing

Handling run-time type uncertainty requires dynamic dispatch. Dynamic dispatch is incompatible with depending on return types, and therefore, on polymorphically typed expressions.

6.2Polymorphically typed structures vs functions

But we can always simulate a polymorphically typed expression by a polymorphically typed function, no? No, we can't. An expression does not have "input" parameters. What it does have are literals. The type of literals determines the type of expression. Thus, as long as literals are uniquely typed, we cannot have polymorphically typed expressions.

Polymorphically typed structures refer to the polymorphic typing of an expression such as (make-pair 2 3) - depending on the context this can be of type (pair fixnum) or (pair integer) or even (pair single-float) etc. Implementing this requires literals to be read as polymorphically typed and subsequent compile-time constraint solving for determining the type.

6.3Parametrically typed structures

In contrast, we can implement parametrically typed structures by storing the type parameter itself as a slot in the structure akin to how standard common lisp arrays work. This may be further augmented by having a type comparison function.