I would argue that the comparison to goto is not completely apt — the two tradeoffs offer very different benefits. In the goto case you barely lose anything (almost every usage can be converted to structured control-flow), while your reasoning abilities are greatly increased. It is no accident Dijkstra’s paper became so widespread.

Not having a GC is a valid tradeoff in some (niche) use cases, as mentioned, but it is very far from a ubiquitous one. There is nothing fundamentally bad about self-referential data, in fact I think the vast majority of existing software would be vastly more complicated without them.

You’re falling into the trap of believing that there is a single path of progress towards some kind of ideal, which every language is moving towards or away from. Ideas in languages evolve the same way organisms do: In response to localised pressures, towards whatever gives them an advantage in that domain.

So to your point: goto has indeed mostly “evolved” out of most programmers workflow and languages. But it is still alive and well in certain contexts, for example kernel development.

I don’t think SSO is typically self-referential in the sense that is not allowed in rust. Typically SSO looks like (but more optimized to use every available byte and not hardcoded to 64 but platforms).

enum String {
  Inline([u8; 24])
  Allocated{
    ptr: *mut [u8],
    len: usize,
    capacity: usize,
  }
}

There is no explicit reference to the inline buffer (as that would waste a word of SSO space). Rust can handle this perfectly fine as a method like as_u8 can borrow a reference to the buffer.

In the past seven years I’ve been working with Rust, using the approach with indices described in the article has been an absolutely awesome API two times in quite large projects. It’s a very nice abstraction when you need to parse a file of code once and then refer it later. Eventually you’ll have one allocated string sitting in the bottom, tokenized in the next layer and then building a database of typed token IDs either in vectors or maps on top of the AST. The public API is built on top of the flat vectors of IDs which can then take a reference directly from the string which represents the code.

It is very efficient and extremely nice API to use. It has been causing almost zero crashes and has accelerated all development in the corresponding code bases. It’s not that I’m trying to evangelize Rust, but this way of modeling the data works very nicely for a few hard problems I’ve been needing to solve in my career.

‘Raw pointers’ in rust are not strong pointers—they can be forged. And the rules for when it is legal to do so are quite literally not specified (see e.g. tratt).

a graph of raw pointers is rarely the best approach

Why?

you can typically create a safe interface around the raw pointers derefs that enforces whatever invariants you’re using to ensure sound memory management

You advocate greenspinning. Green-spun subinterfaces tend to be difficult to use (since they are by definition and as a consequence of essential limitations incomplete), slow, and not modularly composable. Better that the language should grow to include such obviously and near-universally useful functionality.

Partly also responding to your other comment. And cc @oconnor663

A pointer is something that denotes an object. A strong pointer denotes an object directly; a weak pointer denotes an object indirectly. For eample, in java, if C is the name of a class or interface, then a variable of type C is a strong pointer. A memory address might be a strong pointer to a byte in memory, but it is not generally a strong pointer to an object conceived as a higher-level language-level abstraction. (In fact, a memory address is not even a strong pointer to a byte in any architecture with virtual memory.)

An array index, or a string to be looked up in a hash table—these are weak pointers. Weak pointers enable some forms of expressiveness and abstraction (for example, the index might not be into a single array, but into many of them; this allows to modularly and contextually add attributes to an object, like the transpose of stealth mixins), but are harder to reason about and, because they are essentially based on puns, amenable to misuse; hence, the most expressive languages, like lisp and self, encourage the use of strong pointers, in order to maintain local reasoning and to allow the encapsulated abstraction of representation (that object could still be represented using a single index and a collection of context arrays, apropos your performance considerations, but that detail will be hidden from the user of the object; similarly you could have, for example, an object encapsulating an entire graph, if you want one—but, if you have access to its nodes, you surely should be prevented from confusing the nodes of one graph with the nodes of another, should you not?). (See also, for example, explicit foreign key relationships in sql, though I am given to understand that these are not generally checked, unfortunately.)

There is one language which excels at the manipulation of indices: apl. I say this having written the better part of a j compiler in j (j is a dialect of apl), representing the program structure using an edge-list. I feel pretty good about that compiler and its ir. But other languages are not so oriented. They are oriented towards individual objects, encapsulation, and abstraction—scale and explicit interfaces. They lack facilities for expressively and concisely manipulating large arrays (no, the flavour-of-the-month pound of streamprocessing/numpy/whatnot being peddled does not count—rather than subordinate detail, it bows down before it, and the only thing it suggests is verbosity). I think the former represent a interesting ethos about what programming represents. I think it would do most people who program good to write a program in apl (not learn to use it as a calculator—that is rather different, and does not properly impart the values). But it is important to understand that this ethos is divorced from and in direct opposition to the values which underly the design of practically every other program and programming language today. There is a reason that, when apl programmers of the past few decades write c, they often write it like this; if you do not write your code like that, but still advocate the free use of weak pointers, you are committing a half measure and must think about why.

Weak pointers still make a great deal of sense, sometimes. But generally speaking they should not be the default.

The real world is built on weak pointers. The universe can’t tell one calcium atom from another. We go to a great deal of effort to create the illusion that computers underlied by strong pointers exist. Only to throw all that away and revert to weak pointers, stacked on top of the strong ones; why?

Adding generation numbers to indices reminds me of “Handles are the Better Pointers” which is roughly the same idea in C.

Previous discussion: https://lobste.rs/s/4xcla1/handles_are_better_pointers

Oh nice, Andrew commented about this on r/rust.

As another step, I wonder if some of the concerns raised here about safety w/r/t indexes vs pointers would be addressed by a “flyweight” API that encapsulates & hides the underlying arrays. I’m out of my depth with Rust, but maybe something like

struct PersonFlyweight {
   myself: PersonEntity,
   people: Arc<RwLock<PersonComponents>>
}

impl PersonFlyweight {
    fn add_friend(&self, other: PersonEntity) -> &Self {
        let mut w = self.people.write().unwrap();
        add_friend(&mut w.friends, self.myself, other);
        self
    }

    fn identify_as(&mut self, other: PersonEntity) -> &Self {
        self.myself = other;
        self
    }
}

fn main() {
    let mut people = PersonComponents{names: Vec::new(), friends: Vec::new()};

    let alice_id = new_person(&mut people, "Alice");
    let bob_id = new_person(&mut people, "Bob");

    let mut fly = PersonFlyweight{myself: alice_id, people: Arc::new(RwLock::new(people))};

    fly.add_friend(bob_id);
    fly.identify_as(bob_id).add_friend(alice_id);
    fly.identify_as(alice_id).add_friend(alice_id); // no-op
}

The simplest tool is a struct of arrays regardless of the implementation language ;)

I think it’s hard to go too much into this in a context-free way, since the use case is what matters, but with PersonIds you still have the issue of “is this ID still referencing a ‘live’ entity” (so you will need to unwrap just like with Weak). And if you are saying “no, actually everything is always live and we don’t GC” then memory leaks are a non-isuse (or you stick everything in a ’static and be done with it)

Making Ids explicit makes the Rust borrow checker happy, but I really think it doesn’t resolve the fundamental issues in entity systems, which is items no longer existing despite references to them still being somewhere else in the system. And you can handle that fine, if you have some unwrapping step. And if stuff can never be removed, then just “leak” memory (after all, if you stuff is immortal it’s not really a leak is it?). And Rc might not be the right solution for that, but some arena works fine.

I’m saying this, but I do think it’s interesting to explore stuff like your Walker structure anyways.

The literal rule for what you can’t express in Hylo is: any Rust function that, if you made its lifetimes explicit, has at most one lifetime parameter. If that lifetime parameter is used in the return type, you need a “subscript”, otherwise a regular function will do. Oh, and references can only appear at the top level, that is very important. Vice-versa is simpler: Rust is strictly more expressive.

But that doesn’t quite answer “what programs you can write” b.c. there’s the question of writing “the same thing” a different way.

I’ll consider writing this blog post.