Next: , Previous: Modes, Up: Top   [Contents]

6 Unique modes

Mode declarations can also specify so-called “unique modes”. Mercury’s unique modes are similar to “linear types” in some functional programming languages such as Clean. They allow you to specify when there is only one reference to a particular value, and when there will be no more references to that value. If the compiler knows there will be no more references to a value, it can perform “compile-time garbage collection” by automatically inserting code to deallocate the storage associated with that value. Even more importantly, the compiler can also simply reuse the storage immediately, for example by destructively updating one element of an array rather than making a new copy of the entire array in order to change one element. Unique modes are also the mechanism Mercury uses to provide declarative I/O.

We have not yet implemented unique modes fully, and the details are still in a state of flux. So the following should be considered tentative.

6.1 Destructive update

In addition to the insts mentioned above (free, ground, and bound(…)), Mercury also provides “unique” insts unique and unique(…) which are like ground and bound(…) respectively, except that they carry the additional constraint that there can only be one reference to the corresponding value. There is also an inst dead which means that there are no references to the corresponding value, so the compiler is free to generate code that reuses that value. There are three standard modes for manipulating unique values:

% unique output
:- mode uo == free >> unique.

% unique input
:- mode ui == unique >> unique.

% destructive input
:- mode di == unique >> dead.

Mode uo is used to create a unique value. Mode ui is used to inspect a unique value without losing its uniqueness. Mode di is used to deallocate or reuse the memory occupied by a value that will not be used.

Note that a value is not considered unique if it might be needed on backtracking. This means that unique modes are generally only useful for code whose determinism is det or cc_multi (see Determinism).

Unlike bound instantiatedness trees, there is no alternative syntax for unique instantiatedness trees.

6.2 Backtrackable destructive update

“Well it just so happens that your friend here is only mostly dead.
There’s a big difference between mostly dead and all dead…
Now, mostly dead is slightly alive.
Now, all dead — well, with all dead, there’s usually only one thing that you can do.”

“What’s that?”

“Go through his clothes and look for loose change!”

— from the movie “The Princess Bride”.

To allow for backtrackable destructive updates — that is, updates whose effect is undone on backtracking, perhaps by recording the overwritten values on a “trail” so that they can be restored after backtracking — Mercury also provides “mostly unique” modes. The insts mostly_unique and mostly_dead are equivalent to unique and dead, except that only references which will be encountered during forward execution are counted — it is OK for mostly_unique or mostly_dead values to be needed again on backtracking.

Mercury defines some standard modes for manipulating “mostly unique” values, just as it does for unique values:

% mostly unique output
:- mode muo == free >> mostly_unique.

% mostly unique input
:- mode mui == mostly_unique >> mostly_unique.

% mostly destructive input
:- mode mdi == mostly_unique >> mostly_dead.

6.3 Limitations of the current implementation

The implementation of the mode analysis algorithm is not quite complete; as a result, it is not possible to use nested unique modes, i.e. modes in which anything but the top level of a variable is unique. If you do, you will get unique mode errors when you try to get a unique field of a unique data structure. It is also not possible to use unique-input modes; only destructive-input and unique-output modes work.

The Mercury compiler does not (yet) reuse dead values. The only destructive update in the current implementation occurs in library modules, e.g. for I/O and arrays. We do however plan to implement structure reuse and compile-time garbage collection in the future.

Previous: Backtrackable destructive update, Up: Unique modes   [Contents]