freenode/#sicl - IRC Chatlog
Search
14:17:35
karlosz
lukego: if you are interested in the SBCL compiler internals, there is a ton of internals documentation in the cmucl tree that just never made it over to sbcl
14:18:33
karlosz
and the compiler did all fit in one persons head in one point of time. it was written by one person
14:19:43
karlosz
the IR is astoundingly ahead of its time for something started in 1985. it is essentially a form of CPS put in a flowgraph rather than put in a syntax tree
15:10:33
jcowan
lukego: You may find <https://scsh.net/docu/html/man.html> amusing (scroll down to "Acknowledgements")
15:28:12
Shinmera
I have a data structure/protocol issue I'd like to get some thoughts on: essentially I have an object that represents the root of a tree -- a tree composed out of 'containers', each of which have a set of other entities, that may themselves be containers. The containers are abstract and may contain their entities in predictable or unpredictable orders.
15:28:46
Shinmera
Now I need to flatten this tree into a single sequence of instructions on each entity (and container) in the tree. Where order is important for a container, the order must be preserved in the resulting 'instruction sequence'.
15:29:15
Shinmera
Initially building this sequence is easy, as I can just traverse the tree using a simple generic function protocol
15:29:21
jcowan
beach: I see how it could be. Still, Olin is nothing like the way he describes himself here; he may be a good ol' boy, but he doesn't correspond to the good ol' boy stereotype except superficially.
15:29:47
Shinmera
However, the problem now comes in when entities are dynamically added and removed from the tree, and I need to update the instruction sequence to reflect these dynamic changes.
15:30:03
Shinmera
Rebuilding the sequence from the entire tree is considered prohibitively expensive, so the change has to be incremental.
15:31:40
Shinmera
So, I now need a protocol and algorithm to efficiently insert and remove the respective instructions from the sequence when an entity is removed or inserted into a container.
15:31:51
jcowan
Then I'd keep for each container, in addition to the ordered/unordered flag, indices into where its contents appear in the instruction sequence, as a list (first last first last ...)
15:32:40
jcowan
Is it important that the instruction sequence be traversed sequentially fast, as in "lists are too slow"?
15:33:06
Shinmera
For now I'm tracking 'start' and 'end' pointers for each entity that show where it begins and ends in the sequence. However I don't know how to communicate the 'position' when inserting.
15:34:21
jcowan
Ahh. Then you need the Palimpsest protocol, of which I am one of the only two experts in the world. Maybe three. :-)
15:37:07
jcowan
The idea is that you give each insertion (not container) a unique ID and number the original components of that insertion from 0 to whatever. So the initial container has id 0 (or whatever) and its elements are numbered from 0 to 9. To insert one element after 5, you create a new ID for that insertion. then the inserted element has an id of 1 and an index of 0.
15:50:11
beach
Shinmera: You can have relative positions in the tree, or equivalently, the number of instructions occupied by a subtree. That way you don't have to update the positions in the entire tree when you edit it.
15:50:36
Shinmera
One problem I have on the protocol side is even communicating 'where' the new insertion is in the container. The container might have more complex restrictions on the position of insertion than 'append to the end'. It might insert it anywhere in its sequence.
15:52:42
Shinmera
beach: so you mean building a strong order when flattening by assigning children an index relative to their immediate parent?
15:58:05
beach
Or, equivalently, storing the size in each subtree and computing the index as you traverse the tree.
16:12:30
Shinmera
I'll write up a more comprehensive article with some illustrations some other day.