[m-rev.] Version types for review

[Julien Fischer]

On Fri, 3 Sep 2004, Ralph Becket wrote:

> %-----------------------------------------------------------------------------%
> % version_store.m
> % Ralph Becket <rafe at cs.mu.oz.au>
> % Thu Jan 22 12:01:19 EST 2004
> % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
> %
> % (See the header comments in version_types.m for an explanation of version
> % types.)
> %
> % A version store - this operates with similar efficiency to an ordinary
> % store, but "older" versions of the store are still available, but work
> % less efficiently as more updates are made to the "latest" version of
> % the store.  Operations on the "latest" version are always O(1).

That paragraph could be expressed better.

> %
> % The advantage of version stores is that they are ordinary ground terms
> % and can therefore be nested and so forth without the need for complicated
> % insts.
> %
> %-----------------------------------------------------------------------------%
This is one of the benefits of version structures in general.  I think
you should probably mention that in version_types.m as well.

>
> :- module version_store.
>
> :- interface.
>
>
>
> :- type version_store(S).
>
> :- type mutvar(T, S).
>
>
>
>     % Construct a new version store.  This is distinguised from other
s/distinguised/distinguished/

>     % version stores by its existentially quantified type.  This means
>     % the compiler can automatically detect any attempt to use a
>     % mutvar with the wrong version store.
>     %
> :- some [S] func new = version_store(S).
>
...

>     % set(VS, Mutvar, X) = ( VS ^ elem(Mutvar) := X ).
>     %
> :- func set(version_store(S), mutvar(T, S), T) = version_store(S).
>
>     % A version of the above suitable for use with state variables.
>     %
> :- pred set_mutvar(mutvar(T, S)::in, T::in,
>             version_store(S)::in, version_store(S)::out) is det.

I don't think you need to keep saying that the predicate
versions are suitable for use with state variables.  State
variables work with both versions - the predicate version
is just a little more convenient.  Our current coding
standard suggest placing the declarations for both
the predicate and function versions of the same operation
under a common comment.

>
>     % unsafe_rewind(VS) produces a version of VS for which all accesses are
>     % O(1).  Invoking this predicate renders VS and all later versions
>     % undefined that were derived by performing individual updates.
That should probably say:

	Invoking this predicate renders VS and all later vsions that
	were derived by performing individual updates undefined.

> Only use
>     % this when you are absolutely certain there are no live references to VS
>     % or later versions of VS.
>     %
> :- func unsafe_rewind(version_store(T)) = version_store(T).
>
>     % VS version of the above suitable for use with state variables.
>     %
> :- pred unsafe_rewind(version_store(T)::in, version_store(T)::out) is det.
>
...
>
> %-----------------------------------------------------------------------------%
> % Copyright (C) 2001-2002 The University of Melbourne
> % This file may only be copied under the terms of the GNU Library General
> % Public License - see the file COPYING.LIB in the Mercury distribution.
> % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
> %-----------------------------------------------------------------------------%

2002?  Surely you've worked on it since then.

> % version_bitmap.m
> % Ralph Becket <rafe at cs.mu.oz.au>
> %
> % (See the header comments in version_types.m for an explanation of version
> % types.)
> %
> % Version bitmaps: an implementation of bitmaps using version arrays.
> %
> % The advantage of version bitmaps is that in the common, singly threaded,
> % case, they are almost as fast as unique bitmaps, but can be treated as
> % ordinary ground values rather than unique values.
> %
> %-----------------------------------------------------------------------------%
>
> :- module version_bitmap.
>
> :- interface.
>
> :- import_module int, bool.
>
>
>
> :- type version_bitmap.
>
>     % new(N, B) creates a version_bitmap of size N (indexed 0 .. N-1)
>     % setting each bit if B = yes and clearing each bit if B = no.
>     % An exception is thrown if N is negative.
>     %
> :- func new(int, bool) = version_bitmap.
>
>     % Returns the number of bits in a version_bitmap.
>     %
> :- func num_bits(version_bitmap) = int.
>
>     % set(BM, I), clear(BM, I) and flip(BM, I) set, clear and flip
>     % bit I in BM respectively.  An exception is thrown if I is out
>     % of range.
>     %
> :- func set(version_bitmap, int) = version_bitmap.
>
> :- func clear(version_bitmap, int) = version_bitmap.
>
> :- func flip(version_bitmap, int) = version_bitmap.
>
>     % Versions of the above suitable for use with state variables.
>     %
> :- pred set(int::in, version_bitmap::in, version_bitmap::out) is det.
>
> :- pred clear(int::in, version_bitmap::in, version_bitmap::out) is det.
>
> :- pred flip(int::in, version_bitmap::in, version_bitmap::out) is det.
>
As mentioned above it's probably better that the declarations for
the predicate versions are grouped together with the function versions.

>     % is_set(BM, I) and is_clear(BM, I) succeed iff bit I in BM
>     % is set or clear respectively.
>     %
> :- pred is_set(version_bitmap, int).
> :- mode is_set(in, in) is semidet.
>
> :- pred is_clear(version_bitmap, int).
> :- mode is_clear(in, in) is semidet.
>
Is there any reason you haven't used predmode syntax here?

...

> %-----------------------------------------------------------------------------%
>
> :- pred in_range(version_bitmap, int).
> :- mode in_range(in, in) is semidet.
>
Again, you should probably use predmode syntax here.

> %-----------------------------------------------------------------------------%
> % Copyright (C) 2001, 2003 The University of Melbourne
> % This file may only be copied under the terms of the GNU Library General
> % Public License - see the file COPYING.LIB in the Mercury distribution.
> % vim: ft=mercury ts=4 sw=4 et tw=0 wm=0
> %-----------------------------------------------------------------------------%
> %
> % File: version_hash_table.m
> % Main author: rafe
> % Stability: low
> %

...

> :- func search(version_hash_table(K, V), K) = V is semidet.
> :- pred search(version_hash_table(K, V)::in, K::in, V::out) is semidet.
>
>     % Convert a hash table into an association list.
>     %
> :- func to_assoc_list(version_hash_table(K, V)) = assoc_list(K, V).
>
It might also be worth providing a from_assoc_list function.


>     % Fold a function over the key-value bindings in a hash table.
>     %
> :- func fold(func(K, V, T) = T, version_hash_table(K, V), T) = T.
>
> %-----------------------------------------------------------------------------%
> %-----------------------------------------------------------------------------%
> :- implementation.
>
...

> %-----------------------------------------------------------------------------%
>
> set(HT0, K, V) = HT :-
>
>         % If this is the first entry in the hash table, then we use it to
> 	% set up the hash table (the version_arrays are currently empty because
> 	% we need values to initialise them with).
>         %

Fix the indentation there (assuming that it's not cvs or my mail reader
doing that).

More later.

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