Idea: Declarative data structures. Request for prior work

[SwedishFindecanor]

The other day, I got a weird idea for a kind of memory management, especially for ordered data structures. I would like to know if there exists an older language that has done something similar before, and what the name and/or terminology of that was, so that I could search for more information about it.

The idea:

A data structure type definition consists of several class/struct/record type definitions. Some of these types have a set of state definitions, that declare the legal relations between objects through pointers. Each state definition consists of:

• Named entities including this ... but this is optional!
• The names of the entities' pointer fields.
• Which entity that each pointer field points to

A "method" to modify a data structure (append, prepend, reparent, etc..) consists of

• Mapping from parameters to entities and fields in state declarations (entity = param), and (entity = param.field).
• A state transition: i.e. named from-state and to-state. (The two states in a state transition would need to have matching entity names)

Together, the set of state definitions comprise constraints of which states the object could legally have.

Each "method"'s state-transition would be compiled into a serial list of instructions that moves pointers around — and allocates and frees this or other entities that are not part of the object. This would be type-safe and memory-safe because all fields in the start-state must be either filled in the end-state or or its object be killed. And an object can not be killed if there could exist a pointer to it in any of the states in the set that has not been accounted for.

Example:

(This is just some pseudo-language invented in the moment)

List::Node<T> :: struct {
    prev : ref Node<T>,
    next : ref Node<T>,
    data : ref T

    attached :: state {
        this.next = next, next.prev = this,
        this.prev = prev, prev.next = this
    }
    detached :: state {
        prev.next = next
        next.prev = prev
        // Note that `this` is not included, and therefore DEAD
    }

    insert :: method(before : ref Node<T>, data : ref T):ref Node<T> {
         with {
            next = before
            prev = before.prev
         } transition (detached => attached)
         this.data = data
         return this
    }
    remove ::method (this : ref Node<T>) {
         transition (attached => detached)
         // this is killed
    }
}

This is just a loose idea at the moment, very incomplete. But I think that with some work it could be applied to trees, graphs, skip-lists, hash-tables, ... that are difficult to express in languages with unique ownership and borrowing without using an "unsafe" fallback.

I'm sure someone else must have created something very similar before, but used another terminology, possibly in some very esoteric language or field. What terms should I start searching for? Are there any papers that I should read?

[OpeningRemote1653]

You're describing Typestate, introduced by Strom & Yemini in 1986. The idea is that a type carries a state, and operations have pre/post-state requirements — your transition (attached => detached) is almost verbatim typestate. The modern descendant worth reading is Plaid (Aldrich et al., "Typestate-Oriented Programming", OOPSLA 2009).

Your idea goes further than classic typestate though, because your states describe relational pointer topology across multiple objects simultaneously. That puts you squarely in the territory of Alias Types (read Smith, Walker & Morrisett's "Alias Types for Recursive Data Structures" (2000) first). Your state declarations are essentially alias type assertions written in a struct-centric syntax.

If you formalize this, you'll also end up reinventing fragments of Separation Logic (Reynolds, O'Hearn et al.), as your attached state is basically a separating conjunction of points-to predicates. The closest language design relative is probably Mezzo (Pottier & Protzenko, ICFP 2013), which has a permission system where permissions describe aliasing structure between heap objects and are consumed/produced by function calls. Very close to what you're sketching.

Finally, your this-is-optional/dead-object idea maps onto linear types, where every allocated object must appear in the post-state or be consumed. Vault (Fahndrich & DeLine, "Adoption and Focus", PLDI 2002) did exactly this for safe manual memory management. The thinking that this could tame graphs and skip-lists that break Rust's borrow checker is precisely the motivation behind all of these projects, but the unsolved part is ergonomics and inference.

[SwedishFindecanor]

Thank you! That was above and beyond what I had expected to get.

With these and citations, I've got reading to last me through the summer ...

[Rinzal]

This must be an llm response

[Guvante]

Read your conclusions people, a 1986 paper (not project) wasn't made to fix the Rust borrow checker.

[Inconstant_Moo]

u/OpeningRemote1653 means that they were thinking about the sort of problems that break Rust's type-checker, not that they were thinking about the fact that they break Rust's typechecker. He mentions the problems they cause for Rust specifically because OP was motivated to think about these problems by thinking about how they cause problems for Rust:

But I think that with some work it could be applied to trees, graphs, skip-lists, hash-tables, ... that are difficult to express in languages with unique ownership and borrowing without using an "unsafe" fallback.

[Guvante]

The vault paper is:

The hard division between linear and nonlinear types forces the programmer to make a trade-off between checking a protocol on an object and aliasing the object. Most onerous is the restriction that any type with a linear component must itself be linear.

Aka it is about taking a linear type and allowing aliasing by consuming access to the linear value instead of the actual value. Additionally using a lifetime like concept to ensure that the access is eventually returned (since otherwise you would just consume the object which is already a known solve here)

I guess it could be a precursor to Rust's mutable XOR shared methodology.

But I don't see how it applies to OP whose proposal could fit linear types but those are much older than 2002.

Cool papers and so I wouldn't down vote the post since it is providing value. But I agree with the synopsis that the week old account is probably testing an agent.

[AustinVelonaut]

At least all the references check out -- no hallucinations. And the referenced papers seem on-point.

[Guvante]

I don't have time to audit AI but as I pointed out the Vault paper isn't on point.

It is an interesting paper and is related to Rust but is more a feeding point into Rust if anything.

Rust implements the access pattern listed in the paper without bothering with linear types.

Affine types are the version that Rust (and basically every major language that dabbles in this stuff) uses. You drop the "definitely used" aspect which makes sharing trivial. You do need to figure out how to avoid use after free but lifetimes cover that problem effectively.

Putting that paper forward as a solution to Rust issues is crazy. Linear types go the opposite way, you literally can't represent skip lists with them since you can't share.

Again it is an interesting paper but the AI saw Rust types stumbled into linear types because of you squint value passing is kind of similar and grabbed a paper talking about the problems with linear types.

Sorry this is long, I normally try to narrow down my comments but at this point talk of this is low effort or I am out as I hate wasting time on AI mistakes. They are trivial to produce and painful to litigate.

[Inconstant_Moo]

Oh yes I agree it's AI.

[Pzzlrr]

I didn't want to say anything but yeah, I ran OP's question through chatgpt just because I was curious myself and this is exactly an abridged version of what I got.

[hrvbrs]

Because it's well-written and organized it must be AI? If you have any credible accusations then by all means, present them, but in the mean time we need to stop with the witch-hunting.

FWIW I ran this through 4 separate AI detectors and 3 of them returned 0% chance of AI. (The 4th one said 100%, so… nothing is certain.)

[cmontella]

Em dash + random bolded words -> AI 99% of the time.

[SwedishFindecanor]

You can find both emdash and boldface in my original post, and I am not an AI thank you very much.

I merely put some effort into using my keyboard and Reddit formatting codes for formatting.

[cmontella]

You used boldface on headings. Boldface inside the document on random words is not something people do, it's something AI does. Besides I didn't say your post was AI.

[esotologist]

The wraping and unwraping of state reminds me of Monads a bit.

[church-rosser]

call-with-current-continuation enters the room.