In Part I, we discussed the problem with using arrays in the functional paradigm. In Part II, we proposed using copy-on-write behavior as a possible solution. In this part, we will discuss the details of implementing copy-on-write, particularly in a purely-functional, lazy language.
The first thing we need to establish is the rules for how the copy-on-write flag (COW) should be set. We will choose to use a static analysis to decide where to insert instructions to enable COW. This allows us to isolate the COW logic to code that knows it’s working with arrays, which allows array code compiled by our compiler and non-array code compiled without knowledge of arrays to be linked together and work together. It also means we can reuse our static analysis to report errors to the user when what they expect to be O(1) or O(n) array code is compiled to be O(n) or O(n^2).
The COW flag prevents an array from being modified in-place; so the list of places we enable COW here is the photographic negative of the cases where in-place modification is allowed.
We enable COW on any array constant / literal which occurs at the top level of a program (statically allocated in the data segment), since we can’t see if it will be used in multiple places or not. On the other hand, we leave COW disabled on arrays allocated and returned from array functions at run time, until the caller decides to enable it.
Obviously, any function λ v. ... v ... v ... which uses an (unlifted) array parameter in multiple places should enable COW on the array before any of those uses. In addition, any function like λ v. ... for f = λ x. ... v ... . ... which allocates a closure over an array parameter should enable COW, since our analysis doesn’t track whether the closure will be called multiple times. Similar considerations apply to binding constructs like for v = ... . ... v ... v ... and for ⌊v⌋ ∝ ... . ... v ... v ..., where an array returned from a function we call is used multiple times (or used in a closure).
Note that, if we have a branching construct:
analyze e.
case c0 x0. ...,
case c1 x1. ...,
case c2 x2. ...,
, only multiple uses in the same branch, or one use outside the case branches and one use inside, count as ‘multiple uses’.
Before we place an array in a record or in a constructor, we need to enable COW on it, since our analysis doesn’t consider those data types. Similarly, we need to enable COW on any array variable which will be passed to a polymorphic function. If we call a polymorphic higher-order function, and pass it a function that returns an array, e.g. map f xn, where f returns an array, we need to wrap f in logic that enables COW on the result before returning it to map.
While we never enable COW on an array being returned (directly) from a function, we do need to wrap certain expressions in an extra evaluation context that will enable COW on the result before passing it further up the stack. We need to do this on any array expression being passed to a polymorphic function, on the right-hand side of any array thunk which is used multiple times, stored in a data structure, or passed as an argument to a function (since I don’t know how to have a function enable COW on a lifted array parameter).
None of the cases where we add this wrapper is a tail context, so they don’t interfere with tail recursion. In general, we enable COW on function parameters and on function arguments, but not on function results.
This strategy for copy-on-write is based on a static analysis just before the code generator actually runs. It’s possible to run this analysis throughout program optimization, and constrain optimizations to only increase, never decrease, the cases where COW is disabled; but, ultimately, the final decision whether an array will be built in-place or not is up to the code generator. In Part IV, I will consider what options there are for programmers to get automated errors when un-wanted array copies are inserted into their programs.
Global Script 