Add write-tracking to Nim's func

[Araq]

Abstract

The goal of this RFC is to enhance Nim's way of expressing immutability.

Motivation

Nim's func is loved by many, yet it doesn't do what most people expect it would do since it allows for mutations via ref, var and ptr.

Ever since I came up with "write tracking" (see https://nim-lang.org/araq/writetracking.html for details) we can effectively prevent mutations at compile-time.

That refs and ptrs can be used to mutate state is especially harmful for generic code:

func add[T](s: var seq[T]; x: sink T) = ...
# the compiler knows that `x` cannot be mutated inside an add[string], but
# the compiler does not know that `x` cannot be mutated inside an add[ref O]!

Assuming the proposed language change, the compiler would know this.

Proposal

Change the language definition of func into:

A func is a .noSideEffect proc that can only mutate state for locations derived from var parameters. A func can call other funcs, but it cannot call procs.

As an escape hatch, a func can call into a proc if it happens inside a new {.func.}: body pragma.

Watch out: Expressing mutation through var ref T is lying if you do not need to change the pointer itself. Instead of func f(x: var ref T) you should use proc f(x: ref T) {.noSideEffet.}.

A .func annotation needs to be added so that method, iterator and converter can also become func-like in the sense that funcs can call into methods/iterators/converters. Arguably .func is the right default for almost every iterator though. So for iterator .func should be the new default.

Advantages

1. Code becomes easier to reason about both for humans and compilers.
2. func becomes more useful, right now it's only an alias for proc .noSideEffect and the .noSideEffect part is inferred for procs anyhow.
3. .noSideEffect inferrence cannot become a liability when code evolves. You need to decide explicitly whether you seek to fullfill the func's contract now and in the future.

Disadvantages

1. It's yet another addition to Nim's effect system. But this time it's not inferred so arguably it avoids the mistakes of the past.
2. It breaks existing code that uses func and yet performs mutations through ref or ptr.
3. It's an unproven design that should be tried on large code-bases before this RFC is accepted. It should be introduced via an --experimental switch.

Backward incompatibility

Code that uses mutation inside func is broken. In the first version of the implementation the compiler should produce warnings instead of errors so that no code is broken for the time being.

[bluenote10]

Watch out: Expressing mutation through var ref T is lying if you do not need to change the pointer itself. Instead of func f(x: var ref T) you should use proc f(x: ref T) {.noSideEffet.}.

What if f takes other arguments that are not mutated, but happen to be ref types, say a static lookup table? When using proc it is no longer possible to express which ref arguments are actually mutated. So using func and over-specifying the mutability of x becomes the better option?

[Araq]

Not in my opinion. Over-specifying the mutability via var ref T is much more problematic than it looks as there is no subtype relation between var ref T and var ref S even if S <: T.

[Clyybber]

We could also make modifying a dereferenced location that isn't annotated with var count as a sideeffect. func could then stay as sugar for {.noSideEffect.}
Maybe its a good idea too to make it possible to write ref var T instead of var ref T if you don't intend on actually modifying the reference pointer itself.
Generalizing, there could be seq[var T] as a param type, which could provide useful for optimization.

[Araq]

We could also make modifying a dereferenced location that isn't annotated with var count as a sideeffect

Brilliant.

[Araq]

@Clyybber's solution has been implemented in my araq-better-funcs branch. Enable it via {.experimental: "strictFuncs".}. There is a big compatibility problem though, Nim code does things like this:

proc `[]=`*(t: StringTableRef, key, val: string) {.
  rtlFunc, extern: "nstPut", noSideEffect.}

It does the mutation through the first StringTableRef parameter which is not var. Fixing this to remove the .noSideEffect annotation means that we lose the information that the proc doesn't access any global variables. Maybe we need a .noGlobals effect?

[bluenote10]

I thought with @Clyybber's idea this can be expressed via:

proc `[]=`*(t: ref var StringTableObj, key, val: string) {.
  rtlFunc, extern: "nstPut", noSideEffect.}

[Araq]

Well ref var hasn't been implemented.

[awr1]

IMO I like this idea and I don't want to be the one to bikeshed over this but this should have a separate keyword from func, and that func should kept as-is, or that func should get a qualifier before it to enable this.

Some suggestions:

• curb
• limited/limited func/limited proc
• restrict/restricted func/restricted proc
• semifunc/ semi func
• partial func/partial proc
• confined func/confined proc
• var func
• routine/rout
• modifier

[ghost]

@awr1 I disagree - I think that it'll actually be easier for people to understand what func really is after this RFC gets accepted. (Assuming more and more people will use the strictFuncs experimental feature)

[Araq]

This has been implemented and documented well.