I'm looking for code that manipulates trees efficiently. In particular,
something like self-balancing binary trees, written in something like
Scheme.
Ideally, I'd like Scheme code for trees that are self-balancing, but which
don't rebalance too quickly. (That is, they allow a bounded amount of
unbalancedness, and rebalance now and then, to reduce amortized cost. I
would like something that would deal well with millions of insertions,
preferably even insertions in key order.)
Lisp code would be okay if it's written in some fairly generic dialect
of Lisp -- I'll have to translate it to Scheme.
In case you're wondering, I want to translate the SUN engineering
database benchmark into Scheme, so I can use it as a scalable GC
benchmark -- to see how well gc's deal with huge amounts of
long-lived data. (I want the tree routines for indexing large
collections of objects in the heap.)
-- Paul
Paul R. Wilson lab ph.: (312) 996-9216
Interactive Computing Environments (ICE) Lab. FAX no.: (312) 413-0024
U. of Ill. at Chicago EECS Dept. (M/C 154) ······@bert.eecs.uic.edu
P.O. Box 4348 Chicago,IL 60680
--
Paul R. Wilson lab ph.: (312) 996-9216
Interactive Computing Environments (ICE) Lab. FAX no.: (312) 413-0024
U. of Ill. at Chicago EECS Dept. (M/C 154) ······@bert.eecs.uic.edu
P.O. Box 4348 Chicago,IL 60680
I have just come to the conclusion, after trying for several hours,
that it is not possible to write a SETF method for LET using
DEFINE-SETF-METHOD. In case it's not obvious what that means, here's
one not-quite-right way to do it:
(define-setf-method let (clauses &rest body)
(let ((storevar (gensym)))
(values '() '() (list storevar)
`(let ,clauses
,@(butlast body)
(setf ,(car (last body)) ,storevar)
(car (last body))))))
So, roughly speaking, (setf (let ((x ...)) (car x)) 'foo) turns into
(let ((x ...)) (setf (car x) 'foo)).
The problem with the definition above is that it potentially evaluates
the subforms of the last form in the body more than once; so
(incf (let ((x ...)) (car (pop x))) 3)
turns into (effectively)
(let ((x ...)) (setf (car (pop x)) (+ 3 (car (pop x)))))
I can fix this problem, but then I get a version that doesn't
correctly handle DECLARE forms immediately inside the LET being
SETFed.
The point is not that it can't be done -- as far as I know, it is not
hard to specify what the expansion of SETF of LET should be -- but
that it can't be done with the DEFINE-SETF-METHOD interface.
Why would anyone want this to work? It's not unusual for macros to
expand into LET forms. It's true, I could write SETF methods for each
such macro individually, but I don't see why I should have to.
So I'm surprised that CLtL2 doesn't specify (at least not that I've
been able to find) that SETF of LET should work. Is this perhaps
simply an oversight, that should be brought to the attention of X3J13?
-- Scott
····@Reasoning.COM
In article <······················@kestrel.edu> ····@kestrel.edu (Scott Layson Burson) writes:
>I have just come to the conclusion, after trying for several hours,
>that it is not possible to write a SETF method for LET using
>DEFINE-SETF-METHOD.
You might want to check with the Master Macrologist, Alan Bawden. If it
can be done, he can probably figure out how to do it. If it can't, he can
probably prove it.
> (define-setf-method let (clauses &rest body)
> (let ((storevar (gensym)))
> (values '() '() (list storevar)
> `(let ,clauses
> ,@(butlast body)
> (setf ,(car (last body)) ,storevar)
> (car (last body))))))
>
>So, roughly speaking, (setf (let ((x ...)) (car x)) 'foo) turns into
>(let ((x ...)) (setf (car x) 'foo)).
>
>The problem with the definition above is that it potentially evaluates
>the subforms of the last form in the body more than once; so
Could the problem be that you're expanding into another SETF, rather than
using GET-SETF-METHOD-MULTIPLE-VALUE on (car (last body))? If the last
form in the body needs special attention like this, its SETF expansion
should take care of it.
>So I'm surprised that CLtL2 doesn't specify (at least not that I've
>been able to find) that SETF of LET should work. Is this perhaps
>simply an oversight, that should be brought to the attention of X3J13?
I think it's just an oversight by the original SETF designers in MacLisp,
which the CL SETF is basically a clone of. You can bring it to our
attention, but I don't think anything will come of it in the near future,
as it's too late to add something significant like this to the language.
--
Barry Margolin, Thinking Machines Corp.
······@think.com
{uunet,harvard}!think!barmar
In article <·····················@Think.COM> ······@think.com writes:
>In article <······················@kestrel.edu> ····@kestrel.edu (Scott Layson Burson) writes:
>>I have just come to the conclusion, after trying for several hours,
>>that it is not possible to write a SETF method for LET using
>>DEFINE-SETF-METHOD.
>
...
>> (define-setf-method let (clauses &rest body)
>> (let ((storevar (gensym)))
>> (values '() '() (list storevar)
>> `(let ,clauses
>> ,@(butlast body)
>> (setf ,(car (last body)) ,storevar)
>> (car (last body))))))
>>
>>So, roughly speaking, (setf (let ((x ...)) (car x)) 'foo) turns into
>>(let ((x ...)) (setf (car x) 'foo)).
>>
>>The problem with the definition above is that it potentially evaluates
>>the subforms of the last form in the body more than once; so
>
>Could the problem be that you're expanding into another SETF, rather than
>using GET-SETF-METHOD-MULTIPLE-VALUE on (car (last body))? If the last
>form in the body needs special attention like this, its SETF expansion
>should take care of it.
I fooled around a bit with this problem this morning. The bindings of
the let probably need to be bound around the accessor form too, so you
want to move the let bindings into the vars and vals returned by
define-setf-method. BUT define-setf-method has to return gensyms (or
gentemps) for its bindings. So you need to augment the environment
passed to the inner GET-SETF-METHOD-MULTIPLE-VALUE with symbol-macro
bindings that substitute references to the variables of the LET with
refs to temporaries. For good measure, you should add new declaration
info (with reference to the temporaries) to the environment too. Then
wrap LOCALLY around the store and accessor forms, and you're set.
Unfortunately, there won't be a portable way to do this in ANSI Common
Lisp because the environment functions from Chapter 8 of CLtL2 were
booted at the last meeting. You basically need to do a codewalk to do
this right.
>
>>So I'm surprised that CLtL2 doesn't specify (at least not that I've
>>been able to find) that SETF of LET should work. Is this perhaps
>>simply an oversight, that should be brought to the attention of X3J13?
>
>I think it's just an oversight by the original SETF designers in MacLisp,
>which the CL SETF is basically a clone of. You can bring it to our
>attention, but I don't think anything will come of it in the near future,
>as it's too late to add something significant like this to the language.
I can't see that SETF of LET would really be that useful. Unless you
make restrict the last form the LET to be a generalized location,
which seems very restrictive, you would have to write setf methods for
every special form in the language to make this work in the general
case.
--
Tim Moore ·····@cs.utah.edu {bellcore,hplabs}!utah-cs!moore
"Ah, youth. Ah, statute of limitations."
-John Waters