5
$\begingroup$

I'm experimenting with a toy (functional) programming language. One of my ideas is to aggressively hash cons everything, thus representing any data structure as a single integer. In that context, data structures are only efficient if they are history independent so I would switch out traditional RB/AVL/weight balanced trees for PATRICIA trees. For example, any set S would then be represented by the same underlying integer regardless of how it had been made.

A modern editor for my language (e.g. with throwback of inferred types) could benefit from "free" incremental updates to lexing, parsing and even type checking in the event of insertions and deletions of characters in the input program provided I can use a history-independent data structure supporting efficient enumeration, insertion and deletion.

Therefore, I am wondering if there is a history-independent rope?

$\endgroup$

1 Answer 1

1
$\begingroup$

The chief advantages of a rope vs. a more 'traditional' string are:

  • Neither additions or deletions require you to actually move any data.
  • Additions never require reallocating the entirety of the the memory backing the string.
  • Operations are very easily implemented CoW, which makes for both very cheap copies, and, well, easily retaining an edit, uh, history at low cost (both in terms of memory and ease of maintenance/access), though of course this most literal history is completely optional to the structure.

These characteristics offer a bunch of potential advantages; the aforementioned copying and history, immutability lending itself to thread safety, good caching performance if its data is backed by e.g. arena/slab allocation techniques, etc. etc.

Fundamentally, though, the way it works is by managing a tree which points to sequences of raw character data. The tree is frequently split as insertions or deletions call for it (as remember, the point really is that the actual character data never moves), and so that sequence of actions determines the actual structure of the tree (abstracted as it may, and indeed should, be to anyone using it).

While the structure per se may not give away much of that edit history (past which fragments must have been added contiguously), it is advantageous to allocate character buffers in chunks suitable for the OS memory management system and the CPUs caches. This means that even a large series of small additions made to utterly different areas of the string over time are often going to be sitting in order within a larger section of slab allocated memory, thus potentially revealing the order they were actually made via their memory addresses.

None of which is to say that you may not be able to contrive a rope which is able to provide some degree of history independence, but the concepts are to a large degree fundamentally in opposition to the chief benefits of the structure, so you have to question what upsides would remain if you did.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.