[mercury-users] Exceptions and unique modes

Ralph Becket rbeck at microsoft.com
Wed Mar 7 22:54:10 AEDT 2001


> From: Peter Schachte [mailto:schachte at cs.mu.OZ.AU]
> 
> On Tue, Mar 06, 2001 at 02:08:13AM -0800, Ralph Becket wrote:
> > Later on in that e-mail I suggested that the problem of recovering
unique
> > objects could be handled by periodically checkpointing the state of such
> > an object and keeping a log of all the transformations applied to it
> > thereafter.
> > Then, if you get an exception where you would otherwise lose the state
of
> > the
> > unique object, you can recreate its state from the checkpoint and the
log.
> 
> That's not the problem I'm talking about.  I mean how do you *find* the
> right object?  Say there are a dozen different unique objects being
> manipulated in various places in a computation that then throws an
> exception.  Even if you somehow have some structure that holds all of
them,
> how do you determine which of them is the current version of which
incoming
> object?

Every unique object that you wished to recover would have to have its own
checkpoint and log records.  When an exception is caught, you have to
recreate
all the unique objects you are interested in from the checkpoints and the
log.

> The cost of maintaining a redo log is too high for lightweight operations.

I contend that recovering persistent state after an exception is not going
to be a lightweight operation in general.

> For example, suppose I'm building up a unique list of unique things that I
> want to keep whether an exception happens or not.  Every time I create a
new
> list cell, you'll have to keep a record of the head and tail of the cell
so
> you can create it again.  That boils down to making another whole copy of
> the list, and at least doubles the time and space cost of creating the
list.

Yes, this is what databases have to do.  The problem is that when you catch
an exception you have no idea what state your unique object was in when the
exception was raised, so without some kind of sanity-checking mechanism it
may be impossible to restore it to a sensible state.  Moreover there's no 
guarantee that your handle on the object that you want to attach to the
io__state will still be valid when you catch the exception.  Keeping it up-
to-date may well be more expensive and prone to error than treating these 
things as pseudo-databases.

> It also raises the problem that the existence of the log itself makes the
> things it contains not unique; you'd have to introduce the concept of weak
> references.

Not necessarily: the log only has to record what needs to be done to update
the state of the object.

> It seems much easier to hang a hash map off of the io__state which
> associates a unique term with a name.  This solves the problem of finding
> the latest state of a particular unique object, too.  When you want to
> update one of these unique things, you look it up by name in the map,
create
> the new value, and put it back.  Of course, this can be made more
efficient
> by not actually storing the map in the io__state.  And we can optimize it
> further by analyzing the program to determine what names are used to store
> values in the hash map and allocating space for them statically.  This is
> what dynamically scoped variables are.

This is the same thing as Fergus' mutvars + try_store suggestion, surely.
The 
`variables' aren't dynamically scoped as they have to be accessed through a 
uniquely threaded object.  Of course, you still have a problem with storing
unique objects.

For example, assume the mode system is geared up to allow mutvars to contain
unique objects.  We then have

	store__get_mutvar(MutVar, Unique0, Store0, Store1),
		% The object referenced by the MutVar is now either no
longer unique,
		% hence it must be made invalid somehow, or Unique0 is a
copy of the
		% value in MutVar, which presumably defeats the object.
	Unique1 = process(Unique0),
		% If process/1 throws an exception then the object referred
to by
		% Unique0 may now be in an arbitrary state.
	store__set_mutvar(MutVar, Unique1, Store1, Store2)

If we wrap up the above in a try_store then we have no idea what the state
is of 
the object in MutVar.

The problem is just the same for imperative languages, it's just that many
imperative programmers don't seem to take it as seriously (i.e. often they
just 
hope for the best.  I can't see any honest way around the problem than
keeping
some kind of log or taking the monadic approach, which has its own
drawbacks.

Ralph
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------



More information about the users mailing list