PELTADOT Extends Lisp's Types And Dispatches Over Them

peltadot

#+title: PELTADOT: PELTADOT Extends Lisp's Types And Dispatches Over Them

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

:CONTENTS:
- [[#issues-with-standard-common-lisp-we-wish-to-address][Issues with standard common lisp we wish to address]]
- [[#installation][Installation]]
  - [[#using-download-dependencies][Using download-dependencies]]
  - [[#using-quicklisp][Using quicklisp]]
  - [[#using-ultralisp][Using ultralisp]]
- [[#usage][Usage]]
- [[#why-a-shadowing-cl-package][Why a shadowing CL package?]]
- [[#contrasting-peltadot-with-other-systems][Contrasting peltadot with other systems]]
  - [[#dynamic-typing][Dynamic Typing]]
  - [[#polymorphically-typed-structures-vs-functions][Polymorphically typed structures vs functions]]
  - [[#parametrically-typed-structures][Parametrically typed structures]]
:END:

* Issues 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 [[http://clhs.lisp.se/Body/m_deftp.htm][CL:DEFTYPE]] are what CLHS calls [[http://clhs.lisp.se/Body/26_glo_d.htm#derived_type][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 [[https://github.com/digikar99/polymorphic-functions][polymorphic-functions]], [[https://github.com/digikar99/extensible-compound-types][extensible-compound-types]], [[https://github.com/digikar99/extensible-optimizing-coerce][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. 

* Installation

All the three methods ultimately depend on the quicklisp client. Install it by following the instructions [[https://www.quicklisp.org/beta/][here]].

** Using download-dependencies

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

#+begin_src sh
cd $QUICKLISP_HOME/quicklisp/local-projects/
#+end_src

#+begin_src sh
git clone https://github.com/digikar99/download-dependencies
#+end_src

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

#+begin_src lisp
(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/"))
#+end_src

Finally, the system can be loaded using quicklisp.

#+begin_src lisp
(ql:quickload "peltadot")
#+end_src

** Using quicklisp

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

#+begin_src lisp
(ql:quickload "peltadot")
#+end_src

** Using ultralisp

#+begin_src lisp
(ql-dist:install-dist "http://dist.ultralisp.org/" :prompt nil)
(ql:quickload "peltadot")
#+end_src

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.

* Usage

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

#+BEGIN_SRC lisp
(defpackage #:my-package
  (:use #:cl))
#+END_SRC

you can simply write

#+BEGIN_SRC lisp
(defpackage #:my-package
  (:use #:peltadot))
#+END_SRC

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. [[file:docs/introduction-extensible-types.org][Introduction to Extensible Types]]
2. [[file:docs/tutorial-polymorphic-functions.org][Tutorial on Polymorphic Functions]]
3. [[file:docs/ortho-types-polymorphic-functions.org][Orthogonally specializing types and Type templating in Polymorphic Functions]]
4. [[file:docs/traits.org][Tutorial on Traits]]
5. [[file:docs/extensible-coerce.org][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.

* Why 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:

#+begin_quote
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.)

– [[https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node102.html][8.5 Environments, Common Lisp the Language, 2nd Edition]]
#+end_quote

* Contrasting peltadot with other systems

[[https://github.com/coalton-lang/coalton/][Coalton]] addresses all concerns (and more). However, in doing so, it becomes a DSL in itself. And, in fact, it seems that [[https://gist.github.com/digikar99/b76964faf17b3a86739c001dc1b14a39][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      |

** Dynamic Typing

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

** Polymorphically 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.

** Parametrically 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.


peltadot

Upstream URL

Author

License

peltadot

License:

Authors:

Defsystem Dependencies:

Dependencies:

peltadot/cl

Dependencies:

peltadot/class-specializers

Dependencies:

peltadot/cl-cuda

Dependencies:

peltadot/cl-types

Dependencies:

peltadot/coerce

Dependencies:

peltadot/form-types

Dependencies:

peltadot/form-types-and-optim

Dependencies:

peltadot/magicl

Dependencies:

peltadot/polymorphic-functions

Dependencies:

peltadot/specializing

Dependencies:

peltadot/traits

Dependencies:

peltadot-traits-library

Dependencies:

peltadot/types-core

Dependencies:

peltadot/utils

Dependencies:

Dependencies (16)

Dependents (2)