Deep Typing for Plain Old Lists – A new kind of LISP?

March 10, 2006

Genyris is an attempt to provide languages with dispatch on type
features and structural subtyping. The intent is to provide programmers with
a way to formally define the grammar of their list
structures, and to add ‘generic’ or polymorphic
functions on lists. The main difference between Genyris and
CLOS is that the you get dispatch on type for Plain Old Lists (POLs).

It is also designed to give you ambiguous data types.
So you can enter a list at the prompt and Genyris will
tell you what types it conforms to:

>- (types-of ‘(2134 . 986))

(complex point rational vector cons)

Here’s a familiar example:

Consider the following code fragment from Paul
Graham
‘s implementation of John McCarthy’s LISP:

(defun eval. (e a)
(cond
((atom e) (assoc. e a))
((atom (car e))
(cond
((eq (car e) ‘quote) (cadr e))
((eq (car e) ‘atom) (atom (eval. (cadr e) a)))
((eq (car e) ‘eq) (eq (eval. (cadr e) a)
(eval. (caddr e) a)))

To rewrite this using Genyris, first we need to define some list types:

(define-type atom symbol)

(define-type quote-form ‘quote thing) ; e.g. ‘(quote fred …)
(define-type atom-form ‘atom thing) ; e.g. ‘(atom z)
(define-type eq-form ‘eq thing) ; e.g. ‘(eq x y)

Then we write individual generic functions for eval.
which apply to the identified types:

(define-generic g-eval. ((atom e) (alist a)) (assoc. e a))

(define-generic g-eval. ((atom-form e) (alist a)) (atom (eval. (cadr e) a)))

(define-generic g-eval. ((quote-form e) (alist a)) (cadr e))

(define-generic g-eval. ((eq-form e) (alist a))
(eq (g-eval. (cadr e) a) (g-eval. (caddr e) a)))

With source code in this form we can add new evaluation rules to
g-eval. without needing to modify existing code. Whereas in the
traditional eval function there is a single cond expression which
must be maintained. We can also over-ride an existing definition
with a more specific data type. The dispatcher will always call the
most specific available function. For example we could add integers
to g-eval:

(define-generic g-eval. ((fixum e) a) e)

There’s more features than I can put in this post. An essay describing
the approach is available here.
Of course I will be grateful to anyone who reads it. A couple of Lisp people have reviewed it here in Australia (thanks guys) so it isn’t _too_ ordinary. I’m reasonably
confident that someone will point out a way to do this in CLOS or
Scheme. I looked but couldn’t see it.

Advertisements