C++/Julia-like parametric types in CL, based on CLtL2 extensions
This library is part of NUMCL. It provides Julia-like runtime parametric type correctness in CL, based on CLtL2 extensions. The main target of this library is the runtime correctness, but it also adds the equivalent type declarations (statically checked by SBCL). It supports both SBCL and CCL, but CCL would not enjoy the the speed gain.
(defun fn (a b) (declare (gtype (array ?t 1) a)) (declare (gtype ?t b)) (resolve ... (values (length a) b ?t))) (fn (make-array 5 :element-type 'single-float) 0.0) ; -> 5, 0.0, 'single-float (fn (make-array 5 :element-type 'fixnum) 0 ) ; -> 5, 0, 'fixnum (fn (make-array 5 :element-type 'single-float) 0 ) ;; error -- type unification fails (fn (make-array 5 :element-type 'fixnum) 0.0) ;; error -- type unification fails ;; now the real fun starts here... (defun gemm (a b c) (resolve (declare (gtype (array ?t (?n1 ?n2)) a) (gtype (array ?t (?n2 ?n3)) b) (gtype (array ?t (?n1 ?n3)) c)) (dotimes (i ?n1) (dotimes (j ?n2) (dotimes (k ?n3) (setf (aref c i k) (* (aref a i j) (aref b j k)))))))) (let ((c (make-array '(2 2) :initial-element 0))) (gemm #2A((0 1) (2 3)) #2A((0 1) (2 3)) c) (print c)) ;; -> #2A((2 3) (6 9)) ;; see example.lisp for more usage.
It does not modify/overwrite the
defun macro or other special operators and
naturally blends into the existing common lisp code. The only requirement is to
gtype declarations instead of
type declarations, and the use of
resolve macro which enforces the type consistency.
There is also
resolving macro, which is just an alias.
1.1What it is not
Convenient optimization based on the type is not the purpose of this library. For that purpose, combine this library with specialized-function (to be published).
Defining a algebraic type system is not the purpose of this library. For that purpose, see cl-algebraic-data-type.
Currently this library does not have any instrument for defining a parametric structure. For that purpose, see cl-parametric-type at the moment. (but borrowing the idea is planned.)
gtype declarations also add its simplified versions as the standard
define-declaration. Type variables such as
automatically converted into
However, currently no Common Lisp implementations
respect the additional declarations added by
Should they do so, it will compile to the same
efficient code as those with the
CLtL2 specifically mentions that the consequences are undefined
when the secondary value of
define-declaration contains any standard declaration specifier, like
Maintainers of Lisp implementations (e.g. SBCL maintainers) could interpret it as a freedom of choice.
We also ultimately hope lisp implementations to propagate this
outside the function boundary, allowing Lisp to have a proper parametric compile-time checking.
Even though the outer
gtype declarations fail to make the compiler recognize the equivalent
the ones inside the
resolving macro are converted to the
Also, the outer
gtype declaration is inherited and recognized by the inner
In the example below, the
C is matched against the
(defun fn6 (a b fn) (resolving (declare (gtype (array ?t ?d) a)) (declare (gtype (array ?t ?d) b)) (print (list :first ?t ?d)) (let ((c (funcall fn a b))) (resolving (declare (gtype (array ?t ?d) c)) (print (list :second ?t ?d)) (list a b c))))) (print (fn6 (make-array 2 :element-type 'fixnum) (make-array 2 :element-type 'fixnum) (lambda (a b) (if (zerop (random 1)) a b)))) ;; => (:FIRST FIXNUM (2)) ;; => (:SECOND FIXNUM (2)) ;; -> (#(0 0) #(0 0) #(0 0)) (print (fn6 (make-array 2 :element-type 'fixnum) (make-array 2 :element-type 'fixnum) (lambda (a b) (declare (ignore a b)) (make-array 2 :element-type 'single-float)))) ;; => (:FIRST FIXNUM (2)) ;; -| error! type variable ?t fails to match, because fixnum and single-float are disjoint
gtype comes from generic-type.
There are several proof-of-concept libraries in CL that tries to address some aspects of types in CL --- however, they are all subject to the Lisp Curse of not being complete and practical. Everyone implements half the feature they need personally, then stops there. Importantly, none of them naturally fits into the existing code base of Common Lisp. (This library is different, because it has a clear purpose and motivation --- implementing NUMCL.)
The first one you might have heard (and never tried yourself) is cl-algebraic-data-type (or cl-adt in short). It does not support parametric types. From the documentation, it is also not clear if you can define a list that contains only some type (i.e. the arguments to the type specifier is evaluated lazily). It comes with its own pattern matcher, but it is not complete and its performance does not seem like the focus. As a result, the library is not widely adapted.
The second one is cl-parametric-type, which provides a C++-like templates. It can define functions/structures/classes:
(template (<t>) (defun less (a b) (declare (type <t> a b)) (< a b))) (template (&optional (<t1> 'real) (<t2> 'real)) (defun multiply (a b) (declare (type <t1> a) (type <t2> b)) (* a b))) (template (&optional (<t1> t) (<t2> t)) (defstruct pair (first nil :type <t1>) (second nil :type <t2>))) (template (&optional (<t1> t) (<t2> t)) (defclass pair2 () (first :type <t1>) (second :type <t2>)))
but unfortunately has a nonstandard calling rule that depends on macros:
;; i.e. instead of (MAKE-PAIR :FIRST 1 :SECOND 2) you must also specify ;; the concrete types to instantiate PAIR and MAKE-PAIR: ;; (make-pair (bit fixnum) :first 1 :second 2) ; instantiating template-type (PAIR BIT FIXNUM) as <PAIR.BIT.FIXNUM> #S(<PAIR.BIT.FIXNUM> :FIRST 1 :SECOND 2) (defvar *pair* *) ;; store last result into *pair* *PAIR* (pair-first (bit fixnum) *pair*) 1
cl-parametric-type works by instantiating the variant of the function/structs etc., and the reason for the nonstandard call syntax is that it has to instantiate those specialized types beforehand.
1.4DependenciesThis library is at least tested on implementation listed below:
- SBCL 1.5.2 on X86-64 Linux 4.4.0-146-generic (author's environment)
Also, it depends on the following libraries:
- trivialib.type-unify :
- trivial-cltl2 by Tomohiro Matsuyama :Compatibility package exporting CLtL2 functionality
- trivia by Masataro Asai :NON-optimized pattern matcher compatible with OPTIMA, with extensible optimizer interface and clean codebase
- alexandria by Nikodemus Siivola <email@example.com>, and others. :Alexandria is a collection of portable public domain utilities.
- iterate by ** :Jonathan Amsterdam's iterator/gatherer/accumulator facility
1.6Author, License, Copyright
Masataro Asai (firstname.lastname@example.org)
Licensed under LGPL v3.
Copyright (c) 2019 IBM Corporation