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

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

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

  1. Christopher C. Stacy

    2004-08-28, 8:56 pm

    Your proposed langauge suggests that lists are appropriate for representing
    general data structures, and you say that your language “gives programmers
    working with lists the well-known benefits of polymorphism”.

    If I understand you correctly, the underlying functional point of your
    proposal is to provide a way to re-program the built-in Lisp operators,
    and to promote lists are the representation of all abstract structures
    (To implement this, your language adds a user-defined type-tag to the
    implementation of every CONS cell.)

    You mention an example (in Arc) where CAR and CDR have been defined on
    character strings; but since your proposal talks about list structure,
    I’m not sure if you are proposing that all data objects in Lisp should
    be implemented as lists. You do seem to be suggesting that all user
    defined objects be lists, annotated with abstract type and grammar.

    Your idea is in contrast the Common Lisp philosophy that the built-in
    operators have unchangeable semantics, which is desirable so that programs
    can be more easily understood. When a person sees “CAR”, they never have
    to wonder what it means, because its meaning can not have been changed
    or extended in any way.

    (That’s is not strictly enforced in the face of packages, but it is
    considered very extraordinary to create a namespace in which the
    Common Lisp symbol names have changed meanings. Once you do that,
    one would say that you are no longer programming in Common Lisp!)

    Lisp eschews the conflation of abstract structures and lists,
    and has CLOS instead. We also don’t think that the “overloading”
    kind of polymorphism is a “well-known benefit”. (You also mention
    performance issues and seem to imply that this is the roadblack,
    but that’s not really the basis of our counter philosophy.)
    The Common Lisp stance is similar to that of Java in this regard.

    Not all Lisp-like languages share Common Lisp’s philosophy here.
    For a look at a Lisp-like language that provides an abstract structure
    and type system like CLOS, along with operator overloading like C++,
    take a look at Dylan. Scheme allows primitive operators to be redefined

  2. Jon L White says:

    International Lisp Conference 2005

    Dear Bill,

    The Program Committee has reviewed your submission, “List Processing with Latent Polymorphic Types,” and has decided not to accept it for this Conference.

    At the end of this letter, below my signature, we have attached some of the reviewers’ comments on your paper, which may be of help to you in understanding why we did not feel that it is not a good fit for our Conference.

    Still, we hope you will be able to attend the Conference, and look forward to seeing you in June at Stanford.

    Jon L White
    Program Chair

    PaperNo 07, LatentPolymorphic

    Reviewer#09:

    The paper is 17 pages longer than the submissions limit and cannot be accepted in its current form. Furthermore, it is unclear how the system described relates to any of the mainstream type systems, which seem to have similar capabilities, and in some cases Turing complete languages for describing types. These systems can express types as the author is interested, provide a formal means to reason about them in non-trivial ways, and their data structures can be manipulated as first class objects. A good portion of this paper includes a meandering dialog which does not contribute to the discussion of the type system, which needed a better description of its intended capabilities in more formal terms.

    [NO]

    Reviewer#03:

    I think it will be quite useful to do such type inference on ordinarily untyped conses. Seems like a reasonable suggestion for flexible extension of CL type system that offers more type checking and optimization opportunities.

    [YES]

    Reviewer#10:

    The greater part of this paper is a rambling, philisophical walk into ordinary instances of “ambiguity”, but has absolutely no results to show for the journey. It references ARC, Paul Graham’s “unfinished Lisp”; but unlike ARC, the purpose for GENYSIS is much less clear. Graham claims that ARC is a simpler Lisp from which standard definitions of more complex Lisps can be unambiguously expressed. I don’t see what this author is claiming as an end result, unless it is just the nicely written paper itself.

    There is a substantial content to the idea of different “splines” of a view over a given data object; such topics came up during the discussion phases of CLOS predecessors (LOOPS, FLAVORS, etc.) This paper has nothing substantial at all in it, and its presentation is below the technical level of the ALU audience.

    [NO]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: