September 22, 2005
ACL Annotations

I'm surprised I have not yet linked to Chris Riesbeck's annotations on Paul Graham's ANSI Common Lisp.

This binary tree code is very inefficient. Inserting a new element, for example, copies the nodes above the point where the element is inserted. Exactly how much gets copied is left as an exercise for the reader, but such exercises should not be left for maintainers

Posted by jjwiseman at September 22, 2005 08:36 AM

Destructively modifying a tree as suggested comes at a price: no easy "undo" operation is possible any more, and sharing nodes in e.g., several versions of a tree is not possible anymore.

Depending on the situation, it might be better to rely on GC to get rid of the O(log(n)) copied nodes.

Posted by: michaelw on September 22, 2005 09:23 AM

At ILS, the smart Lisp-hackers thought Riesbeck was clueless about code-efficiency-- he judged based on lines-of-code instead of cpu-cycles, and he never figured out how expensive a CONS really is.

Posted by: Ex-ILS on September 22, 2005 09:54 AM

How expensive is a CONS, really?

Posted by: Luke Gorrie on September 22, 2005 11:22 AM

Now I know that CONS is what they teach the suckers.

Posted by: Tayssir John Gabbour on September 22, 2005 05:43 PM
Post a comment

Email Address:


Unless you answer this question, your comment will be classified as spam and will not be posted.
(I'll give you a hint: the answer is “lisp”.)


Remember info?