Just wondering, but couldn't hash tables be implemented as "clever" association lists ? I mean, the interpreter / compiler could switch by itself to a hash-table representation when the user call 'assoc or 'alref on something like
((a b) (c d) (e f) ...)
In other words, a list of lists-of-size-2. The new representation would of course have to share the same semantics as a-lists (possible to cons, to get the car, the cddadr, ...)but with performance as a bonus.
Of course, it would still have to be able to go back to a "regular" list : I could do
(push 3 (car l))
-> ((3 a b) (c d) ...)
There, the compiler would have to see I don't want an association list anymore and switch back to a more traditional representation. In a way, this is the same idea as almkglor's one about lists secretly implemented as arrays.
This way, we would have one less primitive with all the benefits of hash tables. I don't know if it is possible, but as for know I don't see why it wouldn't.
Hmm, right, but that's just a design issue. If pg wanted to simplify the axioms, he could remove hash tables, make alists behave the way I explained and make the syntax foo!x look for the 'x key in the alist 'foo.
Edit : There would be a problem however if we try foo!3 : do we mean the third element, or the element associated to the key 3 ?
