proposal: frozen slices / arrays / maps and derivatives (immutable subscript-able objects)

[Spriithy]

Disclaimer: I have knowledge of #20443 and the following proposes a different approach to the same problem

I would like Go to introduce three new builtin functions (as are new and make for instance). The idea behind those three functions is to provide Go's runtime with an efficient temporary immutable state for subscript-able objects (i.e. types that support indexing or key addressing t[...]). The concept is named object freezing and can be extended further to other types.

The functions

The first function is freeze(s Subscriptable) where Subscriptable is a documentation-purpose abstract type. It is used to freeze a subscript-able object.

t := make([]int, 10) // Create a slice of ints
t[0] = 10 // fine
freeze(t)
x := t[0] // fine, x = 10
t[1] = 2 // panics !
// optional
// unfreeze(t)

The second function is unfreeze(s Subscriptable) and is used to unfreeze a frozen object.

// using previously introduced slice t
unfreeze(t)
t[4] = 8 // fine

The third function is frozen(s Subscriptable) bool and returns whether an object is frozen.

t2 := make([]int, 10)
frozen(t2) // false
freeze(t2)
frozen(t2) // true
// optional
unfreeze(t2)

Freezing rules

Here is a set of rules of object freezing I can think of.

Any non-frozen object is said unfrozen.
A scope "owns the frost" of an object if it successfully froze it

• A frozen object cannot be used as a left value
  • this makes freezing recursive
  • subscript & assign operation panics the current goroutine
  • accessing members (or indices) as r-values is OK
• A frozen object cannot be assigned until it is unfrozen
• A frozen object can be copied without problem
• A frozen object can only be unfrozen within the scope that owns the frost
  • Unfreezing a non-scoped-frozen object panics the current goroutine
• Freezing a frozen object doesn't give the current scope ownership of the frost
  • But it won't panic the goroutine
• A frozen object is unfrozen before being garbage collected or when it falls out of scope

Rules Demonstration

Here I will demonstrate what it is possible (or not) using the above set of rules (using int slices).

func owns() {
    slice := make([]int, 10)
    freeze(slice)
    unfreeze(slice) // OK, slice was first frozen within this scope
}

func doesntOwn(slice []int) {
    unfreeze(slice) // panics if slice was frozen by call er
}

func wontBecomeOwner(slice []int) {
    freeze(slice) // won't give the ownership of the frost to this scope if 
                        // the slice was already frozen i.e. ... (won't panic either)
    unfreeze(slice) // ... will panic
}

func noLeftValue() {
    t := make([]int, 3)
    freeze(t)
    t[0] = 10 // Panic !
    unfreeze(t)
    
    // 3x3 matrix
    t2d := make([][]int, 3)
    t2d[0] = t 
    freeze(t2d)
    t2d[0][2] = 4 // Panic !
}

I know this is far from a complete / as accurate as possible proposal, but I hope it will give some insights into what I have been thinking about for a while. Feel free to point at possible loopholes I might have forgotten about !

Notes:

• Of course all I have demonstrated using slices is applicable to maps, arrays and derived types of these (string, and custom types)

[randall77]

To implement this proposal you'd need to store a frozen bit somewhere. And maybe a whole word where you can store the name of the goroutine that owns the frost. Where do you propose to store this bit/word?

What about

t := make([]int, 3)
freeze(t)
p := &t[0]
unfreeze(t)
*p = 5

Is that allowed? What if the last two statements are swapped?

t := make([]int, 3)
freeze(t)
f(t)
unfreeze(t)

Is f allowed to modify elements in t? How does it know?

I'm skeptical that this proposal is even implementable. Are you intending that freeze is a guarantee, or best effort? Possibly something could be done if you only want the second of those.

[mdempsky]

What's the motivation for this proposal?

I'm under the impression this is meant to parallel JavaScript's Object.freeze API, but I can't imagine the use cases for Object.freeze map very well to Go.

[davecheney]

I'd prefer if this information was recorded in the type system, as it is with byte[] and string. I'd also like it if once a value was frozen, it could not be unfrozen, as that seems to defeat the purpose of the exercise.

…

On 27 Sep 2017, at 01:20, Matthew Dempsky ***@***.***> wrote: What's the motivation for this proposal? I'm under the impression this is meant to parallel JavaScript's Object.freeze API, but I can't imagine the use cases for Object.freeze map very well to Go. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or mute the thread.

[Spriithy]

I think it is possible to make this feature a fully compiler implemented thing. Just like const variables are only a build time thing.

[randall77]

Ok, good data point. No runtime changes, all in the compiler.
So, how would a compiler enforce this?
In particular, see my second example. #20443 can handle it by adding const to the type system. I'm not sure how a freeze-based implementation would.

"I think it is possible..." is unfortunately not a proposal. It is a feature request. In order to make this a proposal that can be evaluated it needs to have more implementation detail.
I would suggest starting a thread on golang-nuts to flesh out what an implementation would look like.

[Spriithy]

For your second example, f obviously isn't allowed to modify elements of t. Now, it would require (and I don't know if golang's does) that the compiler can determine whether a function's (or closure's) body uses t as an lvalue. If the compiler has the possibility to do so, then a quick check (I would guess O(n) to circle through all the statements in the body) would do it.

If this is verified, then the compiler generates an error like function f modifies frozen slice.

[mdempsky]

@Spriithy FYI, I'd still appreciate if you address my question above about motivation and potential use cases.

As for the proposal, I have a few clarifying questions:

1. What is f's semantics under your proposal?

    func f() {
        s := make([]int, 10)
        g(s)
        freeze(s)
        g(s)
        unfreeze(s)
        g(s)
    }
   
    func g(s []int) {
        s[0] = 1
    }
   

Does it compile? If so, do any of the calls to g panic?

2. What does calling f here do?

    func f() {
        s := make([]int, 10)
        g(s, s)
    }
   
    func g(t0, t1 []int) {
        freeze(t0)
        println(frozen(t1))
    }
   

Does it print true or false?

[Spriithy]

Hi @mdempsky, sorry for not having answered your concern.

To address your question, I don't know JavaScript, so this proposal clearly isn't under cover of adding something similar to Object.freeze in Go.

1. Your snippet would not compile. Indeed the second call to g on frozen s will trigger the compiler to check whether g alters its argument or not. Since g modifies the first entry of the slice, the compiler would detect it and puke an error at you saying something like cannot call packname.g on t. packname.g modifies elements of frozen slice. Code doesn't compile

2. In your second snippet, should you print t0 and t1's addresses they would match. This means, that if t0 is frozen t1 is as well. Your snippet prints true

However, all this considered, here are some more examples that demonstrate the failure of my proposal.

1. This snippet demonstrates the limitation of only yielding freeze control to initial freezing scope.

type stuff []int

func (s *stuff) lock() {
    freeze(*s)
}

func (s *stuff) unlock() {
    unfreeze(*s) // Fails...
}

2. This snippet demonstrates the limitation of a compiler only implementation (thanks to @mdempsky)

func main() {
    s := make([]int, 10)
    g(s, s)
}

func g(t0, t1 []int) {
    freeze(t0)
    println(frozen(t1)) // No way this is compile time only, is it ?
}

Unless someone finds a working set of rules & implementation that would solve these cases (would be a runtime thing for sure) I think this proposal is quite born dead.

However, if we consider the fact that a slice can be frozen once and never unfrozen as suggested @davecheney, many things would come out way more clear and straightforward.

However, since this would become a runtime state; Go would need to allocate one extra byte in slice's header as a flag whether it is frozen or not. This would create a slight overhead in the runtime as with subscripting arrays (bounds check).

[mdempsky]

Okay, it sounds like this proposal in its current state is withdrawn, so I'm going to close the issue. If someone comes up with a solution to the limitation identified above, we can reopen. Thanks!