dynamic-wind implementation

Asked by Denis Koreshkov on 2008-11-24

dynamic-wind implementation seem overly complex and inefficient. why not use Hanson-Lamping tree e.g. as in scheme-48?

Question information

Language:
English Edit question
Status:
Answered
For:
Ikarus Scheme Edit question
Assignee:
No assignee Edit question
Last query:
2008-11-25
Last reply:
2008-11-25
Abdulaziz Ghuloum (aghuloum) said : #1

On Nov 24, 2008, at 10:41 AM, Denis Koreshkov wrote:

> why not use Hanson-Lamping tree e.g. as in scheme-48?

I could not find any details about Hanson/Lamping's algorithm other
than that it exists in some "unpublished manuscript" that is no where
to be found. Do you have a link?

Also, the notes in:
   http://www-pu.informatik.uni-tuebingen.de/users/knauel/sw/scheme48-
gui/scheme/rts/wind.scm
says that this code (which I presume comes from scheme48) does not
use the Hanson/Lamping algorithm.
  (Hanson's work is in MIT scheme, is that what you meant?)

Abdulaziz Ghuloum (aghuloum) said : #2

And btw, the implementation in Ikarus is based on (pretty much a verbatim copy of it):
  http://scheme.com/tspl3/control.html#./control:s38

It's pretty straight forward to me, so, it strikes me that you think it's overly complex.

Denis Koreshkov (dkoreshkov) said : #3

>Abdulaziz Ghuloum proposed the following answer:
>I could not find any details about Hanson/Lamping's algorithm other than that it exists in some >"unpublished manuscript" that is no where to be found. Do you have a link?
No. Please consider the implementation included. It is enlightening :)
A description of a similar algorithm is on page 11 in
http://www.bitsavers.org/pdf/mit/cons/TheLispMachine_Nov74.pdf

>Also, the notes in:
>http://www-pu.informatik.uni-tuebingen.de/users/knauel/sw/scheme48-gui/scheme/rts/wind.scm
>says that this code (which I presume comes from scheme48) does not use the Hanson/Lamping algorithm.
Yes, it doesn't. It is something yet another! Thanks for correction.

Denis Koreshkov (dkoreshkov) said : #4

>Abdulaziz Ghuloum proposed the following answer:
>And btw, the implementation in Ikarus is based on (pretty much a verbatim copy of it):
> http://scheme.com/tspl3/control.html#./control:s38
>
>It's pretty straight forward to me, so, it strikes me that you think it's overly complex.

Btw, is this the one used in modern Chez? :)
It is inelegant compared to the "destructive state tree" solution I sent.

Abdulaziz Ghuloum (aghuloum) said : #5

On Nov 25, 2008, at 4:39 AM, Denis Koreshkov wrote:

> Btw, is this the one used in modern Chez? :)

I wouldn't know. I don't have access to its source. But I would
think it's a variant of the same approach. E.g., the common-tail
operation can be made faster by caching the length of the winders
each time you extend the list, thus saving on not having to compute
the length. In practice, this list is typically very short, so, I
don't think it matters much.

> It is inelegant compared to the "destructive state tree" solution I
> sent.

Yeah, right. :-)

Can you help with this problem?

Provide an answer of your own, or ask Denis Koreshkov for more information if necessary.

To post a message you must log in.