2.7.10 Assignment

In an imperative programming paradigm, a machine consists partly of an ensemble of addressable storage locations, whose contents are changed over time by assignment statements. An assignment statement includes some computable function of the global machine state, and the address of the location whose contents will be overwritten with the value computed from the function when it is evaluated.

Compiling a language containing assignment statements into virtual machine code suitable for avram might be facilitated by exploiting the following property.

P16

([[assign]] (p,f)) x = [[replace]] ((p,f x),x)

The identifier assign is used in silly to express a virtual code fragment having the form shown below, and replace corresponds to a further operation to be explained presently.

T18

[[assign]] (p,f) = (((p,f),nil),nil)

This feature simulates assignment statements in the following way. The variable x in P16 corresponds intuitively to the set of addressable locations in the machine. The variable f corresponds to the function whose value will be stored in the location addressed by p. The result of a function expressed using assign is a new store similar to the argument x, but with the part of it in location p replaced by f x. A source text with a sequence of assignment statements could therefore be translated directly into a functional composition of trees in this form.

The way storage locations are modeled in virtual code using this feature would be as nested pairs, and the address p of a location is a tree interpreted similarly to the trees used as operands to the field operator described in Field, to specify deconstructions. In fact, replace can be defined as a minimal solution to the following equation.

E0

([[field]] p) [[replace]] ((p,y),x) = y

This equation regrettably does not lend itself to inferring the silly source for replace using the isolate algorithm in Variable Freedom, so an explicit construction is given in Replace. This construction need not concern a reader who considers the equation a sufficiently precise specification in itself.

In view of the way addresses for deconstruction are represented as trees, it would be entirely correct to infer from this equation that a tuple of values computed together can be assigned to a tuple of locations. The locations don’t even have to be “contiguous”, but could be anywhere in the tree representing the store, and the function is computed from the contents of all of them prior to the update. Hence, this simulation of assignment fails to capture the full inconvenience of imperative programming except in the special case of a single value assigned to a single location, but fortunately this case is the only one most languages allow.

There is another benefit to this feature besides running languages with assignment statements in them, which is the support of abstract or opaque data structures. A function that takes an abstract data structure as an argument and returns something of the same type can be coded in a way that is independent of the fields it doesn’t use. For example, a data structure with three fields having the field identifiers foo, bar, and baz in some source language might be represented as a tuple ((foo contents,bar contents),baz contents) on the virtual code level. Compile time constants like bar = ((nil,(nil,nil)),nil) could be defined in an effort to hide the details of the representation, so that the virtual code field bar is used instead of compose(right,left). Using field identifiers appropriately, a function that transforms such a structure by operating on the bar field could have the virtual code couple(couple(field foo,compose(f,field bar)),field baz). However, this code does not avoid depending on the representation of the data structure, because it relies on the assumption of the foo field being on the left of the left, and the baz field being on the right. On the other hand, the code assign(bar,compose(f,field bar)) does the same job without depending on anything but the position of the bar field. Furthermore, if this position were to change relative to the others, the code maintenance would be limited to a recompilation.

This document was generated on December 10, 2012 using texi2html 1.82.