The Wyn Language Specification

In-place Updates

In-place updates do not provide observable side effects, but they do provide a way to efficiently update an array in-place, with the guarantee that the cost is proportional to the size of the value(s) being written, not the size of the full array.

The a with [i] = v language construct, and derived forms, performs an in-place update. The compiler verifies that the original array (a) is not used on any execution path following the in-place update. This involves also checking that no alias of a is used. Generally, most language constructs produce new arrays, but some (slicing) create arrays that alias their input arrays.

When defining a function parameter we can mark it as consuming by prefixing it with an asterisk. For a return type, we can mark it as alias-free by prefixing it with an asterisk. For example:

def modify (a: *[]i32) (i: i32) (x: i32): *[]i32 =
  a with [i] = a[i] + x

A parameter that is not consuming is called observing. In the parameter declaration a: *[i32], the asterisk means that the function modify has been given “ownership” of the array a, meaning that any caller of modify will never reference array a after the call again. This allows the with expression to perform an in-place update. After a call modify a i x, neither a or any variable that aliases a may be used on any following execution path.

If an asterisk is present at any point inside a tuple parameter type, the parameter as a whole is considered consuming. For example:

def consumes_both ((a,b): (*[]i32,[]i32)) = ...

This is usually not desirable behaviour. Use multiple parameters instead:

def consumes_first_arg (a: *[]i32) (b: []i32) = ...

For bulk in-place updates with multiple values, use the scatter function from the prelude.

Alias Analysis

The rules used by the Wyn compiler to determine aliasing are intuitive in the intra-procedural case. Aliases are associated with entire arrays. Aliases of a record are tuple are tracked for each element, not for the record or tuple itself. Most constructs produce fresh arrays, with no aliases. The main exceptions are if, loop, function calls, and variable literals.

After a binding let a = b, that simply assigns a new name to an existing variable, the variable a aliases b. Similarly for record projections and patterns.

The result of an if aliases the union of the aliases of the components.

The result of a loop aliases the initial values, as well as any aliases that the merge parameters may assume at the end of an iteration, computed to a fixed point.

The aliases of a value returned from a function is the most interesting case, and depends on whether the return value is declared alias-free (with an asterisk *) or not. If it is declared alias-free, then it has no aliases. Otherwise, it aliases all arguments passed for non-consumed parameters.

In-place Updates and Higher-Order Functions

Consumption generally interacts inflexibly with higher-order functions. The issue is that we cannot control how many times a function argument is applied, or to what, so it is not safe to pass a function that consumes its argument. The following two conservative rules govern the interaction between consumption and higher-order functions:

• In the expression let p = e1 in ..., if any in-place update takes place in the expression e1, the value bound by p must not be or contain a function.

• A function that consumes one of its arguments may not be passed as a higher-order argument to another function.