Typo - A portable type inference library for Common Lisp

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:

(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

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

(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

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:

(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))))))

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

(cl:+ a b c)

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

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

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

(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))))))))

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.