A portable type inference library for Common Lisp

typo

#+TITLE: Typo - A portable type inference library for Common Lisp
#+AUTHOR: Marco Heisig

* Notable Features

** Blazingly fast (approximate) handling of types

Typo has its own representation of types, called ntypes.  Conversion of
type specifiers is fast and mostly non-consing:

#+BEGIN_SRC lisp
(dolist (type '((function)
                (cons * function)
                (eql 42)
                (array bit (1 2 3 * 4))))
  (time (loop repeat (expt 10 6) do (type-specifier-ntype type))))
;;; Evaluation took:
;;;   0.031 seconds of real time
;;;   0 bytes consed
;;;
;;; Evaluation took:
;;;   0.059 seconds of real time
;;;   0 bytes consed
;;;
;;; Evaluation took:
;;;   0.155 seconds of real time
;;;   0 bytes consed
;;;
;;; Evaluation took:
;;;  0.539 seconds of real time
;;;  0 bytes consed
#+END_SRC

Also, reasoning about ntypes is much faster than reasoning about type
specifiers.  The only downside is that both the conversion from type
specifiers to ntypes and most operations on ntypes aren't always precise.
Each function that may or may not be precise will return a second value
that is true when its result is precise, and false if it isn't.

** Handles almost all functions in the Common Lisp package

#+BEGIN_SRC lisp
(infer-ntypes '+ (list (type-specifier-ntype '(complex single-float))
                       (type-specifier-ntype 'integer)
                       (type-specifier-ntype 'double-float)))
;; => (#<TYPO.NTYPE::PRIMITIVE-NTYPE (COMPLEX DOUBLE-FLOAT)>)
;; => NIL
;; => NIL

(infer-ntypes 'apply (list (type-specifier-ntype '(eql coerce))
                           (type-specifier-ntype 'integer)
                           (type-specifier-ntype '(eql single-float))
                           (type-specifier-ntype 'null)))
;; => (#<TYPO.NTYPE::PRIMITIVE-NTYPE SINGLE-FLOAT>)
;; => NIL
;; => NIL
#+END_SRC

** Extensible

Typo uses a convenient syntax for specifying function information, by means
of the =define-fndb-record= macro.  This way, programmers can describe how
a particular function can be specialized or differentiated, or whether it
can be subjected to constant folding.  Fore example, here is the function
information for the function =cl:cos=:

#+BEGIN_SRC lisp
(define-fndb-record cos (x)
  (:properties :foldable :movable)
  (:differentiator _ (wrap (- (sin x))))
  (:specializer
   (ntype-subtypecase (wrapper-ntype x)
     ((not number) (abort-specialization))
     (short-float (wrap (short-float-cos x)))
     (single-float (wrap (single-float-cos x)))
     (double-float (wrap (double-float-cos x)))
     (long-float (wrap (long-float-cos x)))
     (complex-short-float (wrap (complex-short-float-cos x)))
     (complex-single-float (wrap (complex-single-float-cos x)))
     (complex-double-float (wrap (complex-double-float-cos x)))
     (complex-long-float (wrap (complex-long-float-cos x)))
     (t (wrap-default (type-specifier-ntype 'number))))))
#+END_SRC

* Bonus Features

** Function Specialization
The cool thing about Typo is that it can (portably!) convert s-expressions
to the most applicable specialized version applicable to its target types.
For example, it can replace

#+BEGIN_SRC lisp
(cl:+ a b c)
#+END_SRC

where a is an integer, b is a double-float, and c is a single-float with

#+BEGIN_SRC lisp
(typo:two-arg-double-float+
 (typo:coerce-to-double-float a)
 (typo:two-arg-double-float+
  b
  (typo:double-float-from-short-float
   c)))
#+END_SRC

The inferface for this machinery is the function =typo:specialize=.  The
call to generate the example would be

#+BEGIN_SRC lisp
(typo:specialize
 #'cl:+
 (list
  (list 'a (list (typo:type-specifier-ntype 'integer)) nil nil)
  (list 'b (list (typo:type-specifier-ntype 'double-float)) nil nil)
  (list 'c (list (typo:type-specifier-ntype 'single-float)) nil nil))
 :wrap-constant (lambda (x) (list x (list (typo:ntype-of x)) nil nil))
 :wrap-function (lambda (fnrecord wrappers required optional rest)
                  (list `(,(typo:fnrecord-name fnrecord) ,@(mapcar #'first wrappers))
                        required optional rest))
 :wrapper-nth-value-ntype
 (lambda (index wrapper)
   (destructuring-bind (form required optional rest) wrapper
     (declare (ignore form))
     (let ((n-required (length required)))
       (if (< index n-required)
           (nth index required)
           (let ((n-optional (length optional)))
             (if (< index (+ n-required n-optional))
                 (nth (- index n-required) optional)
                 (if (null rest)
                     (typo:type-specifier-ntype 'null)
                     rest))))))))
#+END_SRC

** Automatic Differentiation

Typo can also compute expressions for computing the derivative of a
supplied function with respect to a particular argument.  The inferface for
this machinery is the function =typo:differentiate=.

* FAQ
** What's the difference betwen NTYPE from this implementation and https://github.com/s-expressionists/ctype?

CTYPE is a full-fledged, precise implementation of CL types, with its own
versions of typep and subtypep. It requires some amount of implementation
specific hooks to be useful.

NTYPE is only does approximate reasoning about types, but is really fast
and doesn't cons. It relies on the host's versions of typep and subtypep to
do the heavy lifting. But it is faster (which matters for Petalisp), and
fully portable. The main goal of NTYPE is to narrow down the type of each
value in a program enough to choose a specialized representation.

So the main difference between NTYPE and CTYPE is that the former is mostly
about fast type inference and not so much about answering type queries.


typo

Upstream URL

Author

License

typo

License:

Authors:

Dependencies:

typo.test-suite

License:

Authors:

Dependencies:

Dependencies (6)

Dependents (1)