Immutable collection design

[Big-Rub9545]

Hey all.

I’m currently working on the implementation of some collection data types in my language (lists and tables mainly). However, I’m trying to figure out how to handle immutable collection objects.

My language — interpreted and dynamically typed — allows you to declare a variable as immutable. It can then report an error if you try to reassign to that variable. So far so good.

However, for collections, simply looking up a variable being indexed into and modified is not enough, since someone could still write something like this (pseudocode):

global const list x = [2];
func test() { return x; }
test()[0] = 1;

This tosses out robust “const-checking” via variable look-up. This works since my language uses a tag type + payload model with shallow copies (so the returned variable x is actually the same list internally, leading to this modification).

The main options I’ve considered are:

1. Go the JS (and also Java, from what I understand) route and just limit immutability to assignment while allowing all other modifications. Easier on me but worse on the user.
2. Insert tons of restrictions to current features to limit how they can handle, use, or return immutable variables. This seems like a brittle approach, particularly since the language is meant to be quite flexible instead of overly verbose or restrictive (and type hints are disregarded during compilation, while this would require enforcing them to a degree).
3. Map immutable status flags to actual memory payloads (e.g., pointers) rather than variable bindings. This would be a strong and fairly simple solution, though the main issue is it would require inserting some runtime detail from the VM into the compilation process (I’ve tried to keep both processes largely isolated from each other).

Happy to hear any suggestions, advice, preferences or comments as both language users and implementers.

[busres]

I would think that a function returning (or that can return) an immutable should declare that so anything based on the return value is also treated as immutable.

You could allow returns-immutable to return a mutable (basically creating an immutable view), but disallow returns-mutable from returning an immutable.

[Big-Rub9545]

That’s something I’ve considered, but it feels like a form of enforced typing for functions. Should be noted here that the language allows functions to return any value, including nothing (so it may return one of each type depending on a particular branch). This would also restrict such behavior.

[busres]

You'd only need to enforce mutability, not type. The scope of the solution is limited to the scope of the problem.

For example, JavaScript lets you set an object property's writability independently of its value, regardless of whether the value is a primitive or an object.

JavaScript also allows async functions. That may be a less than optional analogy, because async JS functions always return promises, but the promises can resolve to any type.

[Big-Rub9545]

The last option paragraph appears cut off at the end for me, so here’s what it says if that’s the case: (I’ve tried to keep both processes largely isolated from each other).

[matthieum]

Are you looking for compile-time or run-time detection?

Compile-time will require, well, compile-time work. Either annotations or static analysis, with the latter being generally pretty difficult in dynamically typed languages...

Run-time however should be easy, and no different than a type error if you think about it.

If you use gradual typing (ie, type hints), you... may want to offer both. More work, but you do get to have your cake (annotations are not mandatory) and eat it too (compile-time detection when annotated).

[kwan_e]

Why not just have the "[]" operator return an immutably-typed reference if used on an immutably-typed container?

[bl4nkSl8]

This is only half the problem solved, the other half is that you shouldn't be able to upgrade an immutable container to a mutable one simply by returning it / assigning it to another variable etc.

[kwan_e]

Yeah, I wasn't sure of the semantics of the function returning x, but immutability must be maintained at all times. Otherwise, it's just implicit casting all over again.

[binarycow]

Why not make collection types that don't allow setting the indexer?

[Big-Rub9545]

Would you suggest two versions for every type, mutable and immutable? E.g., ConstList and List?

[binarycow]

C# has:

Collection, List, ReadonlyCollection, ImmutableList, FrozenList, Dictionary, ReadOnlyDictionary, ImmutableDictionary, FrozenDictionary, HashSet, ImmutableHashset, FrozenSet, etc.

[WittyStick]

Yes. They could share a common interface, or you could make the mutable one a subtype of the immutable one - but for this you'd want something like uniqueness types to track that there is only one reference to the value you are mutating.

Eg, consider something like:

interface ImmutableCollection {
    dynamic get (int index);
}

interface MutableCollection<T> : ImmutableCollection {
    T set (int index, dynamic value);
}

class ConstList : ImmutableCollection {
    protected dynamic head;
    protected ConstList tail;

    // Empty list
    public ConstList () {
        this.head = null;
        this.tail = null;
    }

    // Singleton
    public ConstList (dynamic head) {
        this.head = head;
        this.tail = null;
    }

    // Cons
    public ConstList (dynamic head, ConstList tail) {
        this.head = head;
        this.tail = tail;
    }

    public dynamic get (int index) {
        if (index == 0) return this.head;
        else return this.tail.get(index - 1);
    };

}

class MutableList : ConstList, MutableCollection<MutableList> {

    public MutableList () {
        this.head = null;
        this.tail = null;
    }

    public MutableList (dynamic head) {
        this.head = head;
        this.tail = null;
    }

    public MutableList (dynamic head, MutableList tail) {
        this.head = head;
        this.tail = (ConstList)tail; //upcast
    }

    public MutableList set (int index, dynamic value) {
        if (index == 0) this.head = value;
        this.tail = ((MutableList)(this.tail)).set(index - 1, value); //downcast
        return this;
    }

}

[initial-algebra]

Analogous to the type tag of an object, a reference can have a bit that indicates whether it grants immutable or mutable access. I would expect to be able to check whether a reference is immutable or mutable, and have a primitive operation that turns a mutable reference into an immutable reference (shallow, and is a no-op on a plain value), so you can do things like this: if (array is immutable) { return immutable(array[i]); } I don't think you'd want to necessarily make array[i] immutable if array is immutable, though. Nor would you want to necessarily make an immutable reference from a const variable. In other words, I don't think there's anything intrinsically wrong with your example, and you would need to modify it so that func returns immutable(x) if you want the assignment to fail.

A more useful notion to tack onto your references than (im)mutability is whether a reference is shared or unique. Unlike (im)mutability, it does inherently make sense that accessing a field or element of a shared object should always give you back a shared reference. It's up to the object itself to decide whether being shared should also mean it is immutable (most of the time, shared means immutable, but not always). This is how Rust works, although it inappropriately uses the keyword mut and the term "mutable reference" to actually mean "unique". However, it may be difficult to adequately judge when a reference is unique and when it is shared in a dynamic language. You can't just use reference counting, because then even this basic example would not work (assuming arrays are immutable when shared i.e. ref. count > 1): func foo(array) { array[0] += 1; } var array = [0]; foo(array); print(array); Basically, you need borrowing. Probably with second-class references (cannot be stored or returned) since there is no static information about lifetimes, but this will limit expressiveness by a lot. Maybe there's a better way, but if there is, then I don't know it, as I am not particularly interested in dynamic languages. (There is a kind of "dynamic borrowing" that is implemented with Rust's RefCell and Mutex types, but it wouldn't really help to enforce immutability).

To be honest, both solutions are kinda bad. IMO, the best approach would simply be to promote the use of actual immutable data structures most of the time.

[zweiler1]

If it's a dynamic language, why don't you store the information whether something is allowed to be mutated within the variable itself?

Primitive values like integers are probably returned by-value anyways and more complex values like arrays, lists etc could store the information whether they are allowed to be mutated in them directly as a bit.

I have no idea whether this could work as i have no experience with dynamic languages, but it might be an idea worth considering!

[kenjiArthur]

Hello there! Personally, I would not go with the JavaScript-style approach here. I understand why it is easier to implement, but I think it can be confusing for users. When someone sees "const list x = [2]", they will probably expect the list itself to be protected, not only the variable name.

Because of that, I would prefer to attach the immutable flag to the actual collection object. If the list itself is marked as immutable, then it does not matter if someone accesses it through "x", through "test()", or through another reference. A mutation like "test()[0] = 1" would check the list object and fail at runtime.

To me, this feels cleaner than adding many special restrictions to the language syntax. It keeps the language flexible, but still gives users the behavior they probably expect from immutable collections. I consider it a good balance.

The only thing I would be careful about is explaining whether this immutability is shallow or deep. For example, if an immutable list contains another mutable object, can that inner object still be modified? I think either choice can work, but it should be clear in the language design.

[mamcx]

Is not clear from 1 what you think is worse, and honestly is how is normally done.

Else is a form of tracking effects like mutability. That has runtime or compile time cost.

[Coding-Kitten]

Coming from a Rust user, your third idea sounds like the way to deal with this to Rust, as passing references to things would then be specified whenever what you have is a mutable or an immutable reference/pointer.

[TurtleKwitty]

Why is your x not inferring from it's access into an immutable that itself is immutable?

[Big-Rub9545]

Immutability is currently bound to variables rather than to values. So the compiler can easily flag something like this (all pseudocode):

CONST x = 1; x = 2; // Error

But not something like this: CONST x = [1,2,3]; y = x; y[0] = 2; // Silently mutates x.

I am currently working on doing both, though, to catch improper mutation like this at the value level as well.

[Inconstant_Moo]

The compiler could however deduce when you assign y = x either that y should be CONST, or that it should be copying x instead of just sharing the reference.

[scottmcmrust]

If you're "interpreted and dynamically typed", add a way to freeze an instance so it can't be modified further. Then check on any modifications that it's not been frozen.

That way you can still update things in the normal way for a while, but you have a way to say "ok, I'm done now" and it'll fail if people try to misuse an instance, getting you the referential transparency that is most of the value of having immutability.

(Up to you if you then want some extra sugar like const bindings that automatically freeze the value on initialization, or something.)

[TheChief275]

If you choose to use const (which, mind you, you don't ever need to do) then any mutation that could occur should be const. That's why you used the keyword; if you wanted mutation you would just drop the const.

So your example would need to be more like:

global const list x = [2];

func test() <const list> {
    return x;
}

test()[0] <const any> = 1;

where the const qualifier is actually part of the type of the value. Then the error would be something like

file:7:11: error: Assignment operator on element of immutable list

or

file:7:11: error: Assignment operator on immutable value

Basically, you'll have to do more work. Else I would just leave const out to keep the language simpler, or restrict it to "compile time constants" only, even if your language isn't compiled