README.org

March 17, 2025 ยท View on GitHub

#+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

(dolist (t1 '(single-float double-float)) (dolist (t2 '(complex rational string)) (let ((nt1 (type-specifier-ntype t1)) (nt2 (type-specifier-ntype t2))) (time (loop repeat (expt 10 6) do (ntype-union nt1 nt2))) (time (loop repeat (expt 10 6) do (ntype-contagion nt1 nt2))) (time (loop repeat (expt 10 6) do (ntype-intersection nt1 nt2)))))) ;; => 15-33 nanoseconds per operation, 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=.

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.