Algebraic effects, ownership, and borrowing | Hacker News Reader

Algebraic effects, ownership, and borrowing

antelang.org

109 pointsthunderbong22 comments

The author’s other blog post is also interesting, highlighting some of the complexity in Rust arising from tying together the concepts of shared references and immutability: https://antelang.org/blog/safe_shared_mutability/ (I.e. in Rust, mutability precludes shared references, even when it would be safe, such as when those references could not be shared across threads.)

Getting rid of explicit lifetime variables is also an interesting choice within this design space.

>such as when those references could not be shared across threads

Shared references can be problematic in a single threaded context too. (You may well be aware of this, but posting for the benefit of anyone who isn't.) This blog post has a good summary of the problematic cases: https://manishearth.github.io/blog/2015/05/17/the-problem-wi...

Rust chose to tie these together for a reason: https://manishearth.github.io/blog/2015/05/17/the-problem-wi...

Alias-xor-mutability is useful for interior pointers (referencing into an enum, referencing into a Vec) because modification may change the memory layout and invalidate the interior pointer. But when the memory layout does not change in singlethread case, alias-xor-mutability can reject safe programs.

I don't understand what "singlethread case" means here. If you mean that only a single reference is active at any given point of the program, Rust allows you to make that a mutable borrowing. If multiple aliased references are active, then you don't really have a "single thread" of control, and modifying one reference may invalidate assertions made by others (even something as simple as n != 0 prior to a division, or n < array_size after a bound check). Shared mutable state must be signaled very clearly if you want to keep a sensible semantics, and Rust does this with the Cell<>, RefCell<>, Atomic* etc. constructs.

Hi, author here!

If anyone's curious, here's how ante addresses these issues:

- It causes memory unsafety: Ante's `shared` references prevent memory unsafety by preventing projecting them into "shape-unstable" types like a vector's element

- Iterator invalidation: This is the previous point in disguise. Since iterating over a shared vector would grab references to its elements - this is prevented since it is shape-unstable. You'd need to clone the elements.

- It's effectively threaded: This is the same bug yet again! Once shared-ness is tracked this becomes a non-issue. Ante is still able to have the static guarantee that this can't happen but does not need to prevent sharing to do so.

- Safe Abstractions: This section is a bit general but it's worth noting Ante still has the ability to have `&own mut t` references if needed. The `swap` function there could use them for example.

Overall the claim that "Aliasing that doesn’t fit the RWLock pattern is dangerous" is fairly rust-centric. It would be dangerous if you had no other restrictions, but we could also adopt different restrictions that still permit aliasing but disallow projection into shape-unstable types instead.

That article gives an example of where mutable aliasing isn't always dangerous:

    let mut my_tuple = (1, 2);
    let first_elem = &my_tuple.0;

    // error[E0506]: cannot assign to `my_tuple` because it is borrowed
    my_tuple = (3, 4);

    println!("{first_elem}");

In that specific example it isn't a problem because the type being changed is just an integer. But if you tweak it slightly it creates a use-after-free:

    let mut my_tuple = (vec![1, 2, 3], 56);
    let first_elem = my_tuple.0.as_slice();

    my_tuple = (vec![4, 5, 6], 23);
    println!("{first_elem:?}");

In this case `first_elem` is a `&[i32]`, and when `my_tuple` is reassigned the allocation is freed while the reference still exists.

Rust does have something equivalent to what's described in the article you linked (and in fact the article even cites it): `&Cell<T>`. It does have some drawbacks compared to what's described in the article though (e.g. no built-in field projection, but it can technically be added in a future compiler version). It is also not completly free: it requires custom implementations of `Clone` to be `unsafe` (in Rust this is equivalent to the fact you cannot clone the `T` inside a `&Cell<T>`, this could also be fixed with an `unsafe trait`). Overall the idea is nice though and I'm curious to see how it will turn out in practice.

Ante has a similar unresolved problem with Clone- AIUI you can only safely Clone things you can project a `&shared` reference through.

To be clear, when I was talking about custom implementations of clone being `unsafe` I was referring to Ante. Ruat currently doesn't have the equivalent of Ante's `Clone` (but it could)

Ante is

> A low-level functional language for exploring algebraic effects, safe shared mutability, and other novel features

This has nothing to do with economics.

The "algebraic" qualifier should have tipped you off.

Why is that? I was intrigued by combination of words and found out it had nothing to do with what I thought.

Because an algebraic effect has no meaning in economics, as best I know, so the context must be something else.

The best bet to assume that it does, many econ majors have math backgrounds and many other want to pimp their work up and borrow terms.

Eg: (after a quick googgle) there is "Concordian economics" nominally an "integration of theory, policy, and practice" which borrows the algebraic rule terms commutative, distributive, and associative.

There's nothing wrong in principal (practice and|or reality are other things) with positing that concepts like transfers of ownership and goods should follow some set of rules .. that is what abstract algebra is all about, { groups of things, sets of rules }.

I have no knowledge of whether this is mainstream or very fringe .. but it's a thing <shrug>.

That is what I was expecting.

That is exactly what I thought was intriguing. Some people are attracted to what they don’t understand.

That’s true

I love this combination of ideas. I don’t love the Haskell inspired syntax though. I think Rust made the right call to go with more traditional syntax

I love ante's concept, I need to try actually using it sometime.

Ante is still mostly unusable unfortunately! Ownership & Borrowing were a relatively recent change and I've still yet to implement them. Algebraic effects are also still in progress in a dev branch and won't be merged for some time. You can use the language today but it will feel more like C with traits, generics, and bugs rather than a more featureful language.

The language does have a basic language server already though! It currently supports inline diagnostics and hover to show type.

Reply on news.ycombinator.com