## typo

2022-11-07

A portable type inference library for Common Lisp

# 1Notable Features

## 1.1Blazingly 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.

## 1.2Handles 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
```

## 1.3Extensible

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

# 2Bonus Features

## 2.1Function Specialization

The cool thing about Typo is that it can (portably!) convert s-expressionsto 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))))))))
```

## 2.2Automatic 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`

.

# 3FAQ

## 3.1What'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.