Xonses progress report

I have rewritten my interpreter to use xonses throughout. As expected, Lisp code that doesn't use them is unaffected, and continues running as-is.

To recap: xonses are like conses, but in addition to car and cdr, they may have any number of other slots.

() == {} ;; nil is just an empty xons
(a) == { :car a :cdr {} }
(:foo 1) == { :foo 1 }
(:foo 1 2 3) == { :foo 1 :car 2 :cdr { :car 3 :cdr {} } }
(open-file "README" :mode "rw" :create-if-not-exists #t) ==
{ :mode "rw" :create-if-not-exists #t :car "open-file" :cdr { :car "README" :cdr {} } }

The differences between a Lisp/Kernel with conses and one with xonses are mostly:

• There is no longer a separate nil. A xons without car and cdr is treated as nil, even if it has other slots.
• The usual pair? predicate changes from (instance? obj Pair) to (and? (instance? obj Pair) (not? (null? obj)).
  
  (These previous two rules have to do with the fact that xonses are more expressive than conses, and so we lose some "sharpness".)
• Pattern matching is extended, so that not only car and cdr are matched recursively, but all slots.
• Evaluation of arguments is extended: like in Kernel, an applicative cdrs down its operands and evaluates each, building the arguments list. In addition we now also evaluate the other slots of the first xons (Open question: should we also evaluate the other slots of later xonses? Probably yes).

All in all, xonses fit into the usual Lisp framework.

One big problem remains, which is why my new interpreter doesn't work:

In the x-expression (open-file "README" :mode "rw"), the :mode slot gets attached to the first xons, the one whose car is open-file. Per the usual evaluation rule, a combiner uses the cdr -- ("README") -- of the form it appears in as operand, and so it doesn't see the :mode slot.

I think it boils down to this: once we have arbitrary slots and not just car and cdr, it may make sense to remove the usual Lisp rule that the car of a combination contains its combiner. Maybe we need an explicit combiner slot:

(:combiner open-file "README" :mode "rw")

which corresponds to

(:combiner open-file :mode "rw" :car "README" :cdr ())

or abbreviated, using \ for :combiner.

(\open-file "README" :mode "rw")

Mirroring the fact that there's no nil, this also has the nice symmetry that calling a combiner without arguments requires no car and cdr anymore:

(\foo) means simply (:combiner foo), without car and cdr.

Investigating!

First-class patterns

A good sign: xonses are already making me think previously impossible thoughts.

In my Kernel implementation Virtua, every object can potentially act as a left-hand side pattern.

A pattern responds to the message match(lhs, rhs, env) -- where the LHS is the pattern -- performs some computation, and possibly updates env with new bindings. The rules for Kernel's built-ins are:

• #ignore matches anything, and doesn't update the environment.
• Symbols match anything, and update the environment with a new binding from the symbol to the RHS.
• Nil matches only nil, and doesn't update the environment.
• Pairs match only pairs, and recursively match their car and cdr against the RHS's car and cdr, respectively.
• All other objects signal an error when used as a pattern.

With these simple rules one can write e.g. a lambda that destructures a list:
(apply (lambda (a b (c d)) (list a b c d))
       (list 1 2 (list 3 4)))
==> (1 2 3 4)

Now, why stop at these built-ins? Why not add first-class patterns? We only need some way to plug them into the parsing process...

An example: In Common Lisp, we use type declarations in method definitions:

(defmethod frobnicate ((a Foo) (b Bar)) ...)

(a Foo) means: match only instances of Foo, and bind them to the variable a.

Generalizing this, we could write:

(defmethod frobnicate ([<: a Foo] [<: b Bar]) ...)

The square brackets indicate first-class patterns, and in Lisp fashion, every first-class pattern has an operator, <: in this case. The parser simply calls <: with the operands list (a Foo), and this yields a first-class pattern, that performs a type check against Foo, and binds the variable a.

Another example would be an as pattern, like ML's alias patterns or Common Lisp's &whole, that lets us get a handle on a whole term, while also matching its subterms:

(lambda [as foo (a b c)] ...)

binds foo to the whole list of arguments, while binding a, b, and c to the first, second, and third element, respectively.

Another example would be destructuring of objects:
(lambda ([dest Person .name n .age a]) ...)
would be a function taking a single argument that must be an instance of Person, and binds n and a to its name and age, respectively.

With first-class patterns, all of these features can be added in luserland.

Xonses

I think I finally had the breakthrough regarding named parameters and conses: Xonses.

In short:

(open-file "README" :mode "rw" :create-if-not-exists #t)
===
{ :mode "rw" :create-if-not-exists #t :car "open-file" :cdr { :car "README" :cdr {} } }

A bit more here on the klisp group, and I'll keep you posted here, of course.