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.
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!
Does the evaluator of combiners have access to the combiner itself, ie not just the operands?
ReplyDeleteIf that is the case, extending access to include additional "qualifiers" makes sense.
If this is not the case, then why not not permitting it? This would enable functions whose behaviour depends on the name used to invoke them...
Yes, good question. In Kernel, it's hardwired that a combiner is called with the cdr of the combination, i.e. the list without itself.
ReplyDelete"This would enable functions whose behaviour depends on the name used to invoke them..."
You probably don't want to do that. :-)
The blog post I'm most actively working on developing atm deals with the value of exploring alternative ideas, somewhat independent of whether or not they pan out. So I'm finding this exploration of the xons idea rather fascinating and fun.
ReplyDeleteSome miscellaneous questions, to maybe help stir your thinking as well as help me understand.
* What is car for, if it isn't for designating the combiner of a combination?
* What are car and cdr for, if not to provide a uniformly structured data representation of syntax?
* Is a xons subject to manipulation as data, in the sense that a traditional Lisp list would be, and if so, how?
"What is car for, if it isn't for designating the combiner of a combination?"
ReplyDeleteBy using the car as the combiner in lists meant to be evaluated, while allowing anything else as the car in other lists (e.g. the bindings in a LET), isn't Lisp wildly punning?
Rich Hickey makes the point that Lisp conflates these two cases, and Clojure thus uses () for calls and [] for grouping (e.g. LET's bindings).
My hunch is that using the car as combiner is one of the many deep "tricks" in Lisp. But it seems arbitrary, no?
"What are car and cdr for, if not to provide a uniformly structured data representation of syntax?"
With xonses, they are merely a pattern for expressing sequences. I'm deeply convinced that named arguments are a necessity - witness HTML attributes, shell command arguments, keyword arguments in many PLs. (In fact, one of my laws of software is: "It's all just a bunch of name/value pairs." :-))
"Is a xons subject to manipulation as data, in the sense that a traditional Lisp list would be, and if so, how?"
(cons a b) is expressible as (quote (:car a :cdr b)). Basically all cons-manipulation functions carry over. But xonses have more moving parts - e.g. consing a new xons onto another xons is troubling already: you probably always want to have keyword arguments attached as slots to the first xons in a cons-list.
Thanks for your interest! My hope would be that you put your exacting mind to the issue, and come up with a solution as perfect as Kernel! I feel too stupid. :-)
(I'm taking this slowly, not to miss important details in unexplored territory.)
ReplyDeleteMy third question seems to have gone astray. I get how to represent a pair as a xons. But, in the view of fexprs I've used for Kernel, it's key that source expressions can be fully analyzed and manipulated as data. We may be parting company with that assumption; best to be aware of that, if so.
The "theory of fexprs is trivial" result has two sides, what it does mean and what it doesn't. The myth I keep debunking is that fexprs trivialize all equational theory of a calculus; that's not so. What is true is that fexprs trivialize the equational theory of all terms that a fexpr can fully analyze. And in Lisp (based on conses, that is), all source expressions can be fully analyzed. A source expression being anything that can be read fro a source file.
But with xonses, it seems there'd be source expressions that can't be fully analyzed. If I've got
{:foo 1 :bar 2}
can I pass that to a fexpr that will be able to fully analyze it, determining what its slots are and what's stored in those slots?
Note that in Kernel, environments (which are a lot like xonses in some respects) are not fully analyzable. But unlike xonses, environments cannot be read from a source file; they can only result from evaluation.
Yes, I'm currently providing a (slot-names xons) function that returns the names of all slots in a xons, as well as (get-slot xons slotname) and (set-slot! xons slotname value).
ReplyDeleteI've now found a somewhat acceptable solution, that's not as radical as introducing a :combiner slot: a combiner is called with the whole form it appears in. This means that basically all combiners' parameter trees start with #ignore, to ignore the combiner itself:
ReplyDeleteKernel's ($vau (x) ...) is written as ($vau (#ignore x) ...) in order to ignore the combiner itself.
(In preview, this post has bizarrely no line wraparound. Posting anyway.)
ReplyDeleteThere's a quote about Lisp, I read it on Wikiquotes but later it got moved to the talk page because its author was non-notable (Paul Rubin). "No [programming] language feels more natural than Lisp. There's a real sense that ... Lisp is built into of the structure of the Universe."
Imho, the xonses idea wants that sense of inevitability. You've got primitives to allow full analysis of a xons; cool. Note, though, that Kernel doesn't have primitives for analyzing conses. car and cdr are conjured out of the primordial structural unification mechanism. So, something to ponder is, how can xonses settle into the deep infrastructure of the language?
Good points.
ReplyDeleteNote though, that in my current interpreter
($define car ($lambda ((a . #ignore)) a))
($define cdr ($lambda ((#ignore . b)) b))
is really just another syntax for
($define car ($lambda ((:car a)) a))
($define cdr ($lambda ((:cdr b)) b))
With xonses too, we can "conjure" these accessors.
Ah, to be really identical, we have to use these:
ReplyDelete($define car ($lambda ((:car a :cdr #ignore)) a))
($define cdr ($lambda ((:car #ignore :cdr b)) b))
The devil being in the details, what is the difference in meaning between
ReplyDelete($define car ($lambda ((:car a)) a))
and
($define car ($lambda ((:car a :cdr #ignore)) a))
?
Right, I've added these in my previous comment.
ReplyDeleteMy current approach is to signal an error if one of the slots in the LHS does not appear in the RHS.
Dear Manuel Simoni,
ReplyDeleteWhat you refer to as slots in this post are refered to as places in Common Lisp. Place forms provide an elegant means of handling places in Common Lisp. For example, here is how you can edit the value and function slots of a symbol:
(setf (symbol-value 'coll) '(1 2 3))
(setf (symbol-function 'coll) (lambda (&rest arg) (apply #'list arg))
There are a variety of representations of place based data structures available. I personally like this representation:
(% (first 1) (rest (first 2) (rest (first 3) (rest nil))))
S-expressions provide a standard, agreed upon, and fully sufficient syntax for representing place based data structures, so there is no need for any other textual syntactic forms. I developed the above representation back in January in this post http://lisp-ai.blogspot.com/2012/01/s-expression-syntax-for-maps.html