uniqueness and strictness unified?

Erik Zuurbier F.S.A.Zuurbier@inter.nl.net
Wed, 11 Mar 1998 23:15:32 +0100


Sjaak Smetsers wrote:

"Uniqueness is NOT a property of objects but of a function's argument."

Is that so? What I meant to say is that an object's TYPE can have the
uniqueness property, and a function cannot just have unique arguments,
but also unique results. What else would the following valid lines of
Clean mean:

:: *State = {gen::Generation, size::CellSize} // from the LifeGame
openfiles :: !*World -> (!*Files,!*World) // from StdFile

My idea was to go away from the concept that uniqueness be a property
of just any object's TYPE as in the lines above, but that an asterisk
(destruction sign) should only occur on the left side of an function-arrow.
Nowhere else. It says something about the FUNCTION, namely that the
function might destroy the argument. I also think the concept of
destructiveness is easier to explain than the uniqueness-idea (for instance
after years I honestly still don't understand why the State type above should
be marked as unique, just because some FUNCTIONs on it might do in-place
updates).

A simple example to support my idea that maybe uniqueness should not be viewed
as a typing issue:

Upd1 :: *a -> *a
Upd1 a = a

Upd2 :: a -> a
Upd2 a = a

Start :: (Int,Real)
Start = Upd1 (Upd2 a)
where a = (1,1.0)

This gives a type error:
Type error [Test.icl,11,Start]: "argument 1 of Upd1" * attribute required
but not
offered at the indicated position: ^ (Int,Real)
while we can easily check that there is only one reference to (Upd2 a).

The following gives a hint at what might be possible with my view.
(It is NOT about things that are ESSENTIALLY UNIQUE, such as many IO-objects.
I will say some words about that at the end.)

Observe the following piece of code, with destruction signs (*) as I propose:

UpdArray :: *{a} -> {a}       // a function to create an array
                              // from another array, possibly destroying
                              // its input
UpdArray arr1
 # arr = Destr1 arr1          // see below
   arr = Destr2 arr
   arr = Destr3 arr
   arr = Destr4 arr
   arr = Destr5 arr
 | BoolFun arr = arr          // so either choose the result of all
                              // destructive updates
 | otherwise   = arr1         // or revert to the original input

Destr1 :: *{a} -> {a}         // etc: all destructive functions

Clean would certainly not allow anything like the above, not even with strict
lets, because of uniqueness problems. But operationally, one can imagine the
following to happen.
1) UpdArray first creates a spare copy of (the spine of) the array. Call the
original x and the spare copy y. It does that BECAUSE Destr1 might destroy
its argument.
2) Destr1 does a fast destructive update on y, which is possible
because Destr1 is the only reference to y.
3) Destr2 does a fast destructive update on the result of that.
etc. Call the result of Destr5 z.
4) BoolFun does a test on z.
5) If it is true, output z and throw x away.
6) If it is false, output x and throw z away.

Say that there are non-destructive variants of Destr1 u/i Destr5.
Then the whole chain of updates could also have been done
the orthodox functional way: non-destructively. What is faster:
making ONE copy and doing a chain of destructive updates or doing
a chain of non-destructive updates, EACH creating a copy and driving
the garbage collector mad?

The good thing in the described operational behaviour is that the speed of
MANY destructive updates is possible by making just ONE copy, and thus to
gain the freedom of multiple references to arr1.
The down side seems to be that things may become less lazy in
places that are hard to spot, such as in the following example.

ReadOnly :: {a} -> R    // NOT strict in its argument
Destr :: R *{a} -> {a}  // NOT strict in its arguments, may destroy second arg.

UpdArray :: *{a} -> {a}
UpdArray arr = Destr r arr
where r = ReadOnly arr

Normally, evaluation of r would be postponed until it were really, really
needed by Destr. But if we did that here, Destr would be underway destroying
arr, and only then find out that it needs r, which in turn might need the
original arr. Too late!

How do we fix this? As in the above example, we could leave it up to the
compiler to be clever enough to make a spare copy of arr for ReadOnly,
or to evaluate r before entering Destr. In the latter case, the function
would become less lazy than it was supposed to be. So the laziness of a
program would depend on some optimization that the compiler did or did not
decide to do. Unacceptable!

The alternative is that we direct the compiler by an annotation, for 
example with the exclamation mark in the following:

UpdArray :: *{a} -> {a}
UpdArray arr = Destr !r arr
where r = ReadOnly arr

Call it a strict let if you will. If the exclamation mark would be absent,
the compiler would know to produce lazy code, so to make a spare copy of arr,
BUT NOT TO REJECT THE CODE!

Naturally, in case of ESSENTIALLY UNIQUE objects, making a spare copy is
no option, so the version without the exclamation mark WOULD be unacceptable
to the compiler.

Sjaak, you also wrote "So I do not see the diffence between your idea and
uniqueness typing."

I hope this helps.

Erik Zuurbier