[m-rev.] Version types for review
Julien Fischer
juliensf at cs.mu.OZ.AU
Fri Sep 3 16:08:54 AEST 2004
On Fri, 3 Sep 2004, Ralph Becket wrote:
> I've tidied up the version types and would like to include them in the
> upcoming release. I can either put them in the standard library or
> extras - any opinions?
extras for the moment - although it would be nice if they
were in the standard library eventually.
> Do things need to pass in Java, .NET and with
> agc to go in the library? If so, I can sort those details out.
>
You could just provided default Mercury clauses that throw an
exception for .NET and Java - I suspect the problems the
Java backend has with RTTI would probably stop versions structures
working properly even if you did provide Java implementations.
I'm not sure about the agc here.
> %-----------------------------------------------------------------------------%
> % version_types.m
> % Ralph Becket <rafe at cs.mu.oz.au>
> % Fri Jul 9 15:31:16 EST 2004
> % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
> %
> % (This module only provides documentation describing general properties
> % of version types.)
> %
> % Version types are efficient pure implementations of typically imperative
> % structures, subject to the following caveat: efficient access is only
> % guaranteed for the "latest" version of a given structure. An older version
> % incurrs an access cost proportional to the number of its descendants.
> %
> % For example, if A0 is a version array, and A1 is created by updating A0,
> % and A2 is created by updating A1, ..., and An is created by updating An-1,
> % then accesses to An cost O(1) (assuming no further versions of the array
> % have been created from An), but accesses to A0 cost O(n).
> %
> % Most of these data structures come with impure, unsafe means to "rewind"
> % to an earlier version, restoring that version's O(1) access times, but
> % leaving later versions undefined (i.e. only do this if you are discarding
> % all later versions of the structure.)
> %
> %-----------------------------------------------------------------------------%
>
> :- module version_types.
>
> :- interface.
>
> %-----------------------------------------------------------------------------%
> %-----------------------------------------------------------------------------%
>
>
>
> %-----------------------------------------------------------------------------%
> % Copyright (C) 2004 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
> %-----------------------------------------------------------------------------%
> % version_array.m
> % Ralph Becket <rafe at cs.mu.oz.au>
> % Wed Jan 21 15:44:04 EST 2004
> %
> % (See the header comments in version_types.m for an explanation of version
> % types.)
> %
> % This module implements version arrays. A version array provides O(1)
> % access and update for the "latest" version of the array. "Older"
> % versions of the array incurr an O(k) penalty on accesses where k is
> % the number of updates that have been made since.
> %
> % The advantage of version arrays is that in the common, singly threaded,
> % case, they are almost as fast as unique arrays, but can be treated as
> % ordinary ground values rather than unique values.
> %
> % Version arrays are zero based.
> %
> %-----------------------------------------------------------------------------%
>
> :- module version_array.
>
> :- interface.
>
> :- import_module int.
> :- import_module list.
>
>
>
> :- type version_array(T).
>
>
>
> % empty_array returns the empty array.
> %
> :- func empty = version_array(T).
>
> % new(N, X) returns an array of size N with each item initialised
> % to X.
> %
> :- func new(int, T) = version_array(T).
>
> % A synonym for new/2.
> %
> :- func init(int, T) = version_array(T).
>
> % version_array(Xs) returns an array constructed from the items in the list
> % Xs.
> %
> :- func version_array(list(T)) = version_array(T).
>
I think for consistency with the rest of the standard library
you should probably call this from_list or at least provide
a synonym called from_list.
> % A ^ elem(I) = X iff the Ith member of A is X (the first item has
> % index 0).
> %
> :- func version_array(T) ^ elem(int) = T.
>
> % lookup(A, I) = A ^ elem(I).
> %
> :- func lookup(version_array(T), int) = T.
>
> % (A ^ elem(I) := X) is a copy of array A with item I updated to be
> % X. An exception is thrown if I is out of bounds.
> %
> :- func (version_array(T) ^ elem(int) := T) = version_array(T).
>
> % Version of the above suitable for use with state variables.
> %
> :- pred set(int::in, T::in, version_array(T)::in, version_array(T)::out)
> is det.
>
> % size(A) = N if A contains N items (i.e. the valid indices for A
> % range from 0 to N - 1).
> %
> :- func size(version_array(T)) = int.
>
> % max(Z) = size(A) - 1.
> %
> :- func max(version_array(T)) = int.
>
> % resize(A, N, X) returns a new array whose items from
> % 0..min(size(A), N - 1) are taken from A and whose items
> % from min(size(A), N - 1)..(N - 1) (if any) are initialised
> % to X.
> %
> :- func resize(version_array(T), int, T) = version_array(T).
>
> % Version of the above suitable for use with state variables.
> %
> :- pred resize(int::in, T::in, version_array(T)::in, version_array(T)::out)
> is det.
>
> % list(A) = Xs where Xs is the list of items in A
> % (i.e. A = version_array(Xs)).
> %
> :- func list(version_array(T)) = list(T).
>
It would be more consistent with the standard library if this function
were called to_list.
> % foldl(F, A, X) is equivalent to list.foldl(F, list(A), Xs).
> %
> :- func foldl(func(T1, T2) = T2, version_array(T1), T2) = T2.
>
> % foldr(F, A, X) is equivalent to list.foldr(F, list(A), Xs).
> %
> :- func foldr(func(T1, T2) = T2, version_array(T1), T2) = T2.
Some predicate versions of foldl, foldr plus foldl2, foldl3
(the usual suspects) would be nice as well.
...
> %-----------------------------------------------------------------------------%
> %-----------------------------------------------------------------------------%
> % Sordid stuff below this point...
>
A comment describing the thread safety (or lack thereof) of the code
in this section would be nice for future maintainers.
> :- pragma foreign_type("C", version_array(T), "struct va *")
> where equality is eq_version_array,
> comparison is cmp_version_array.
>
>
> :- pred eq_version_array(version_array(T)::in, version_array(T)::in)
> is semidet.
>
> eq_version_array(VAa, VAb) :-
> N = max(VAa),
> N = max(VAb),
> eq_version_array_2(N, VAa, VAb).
>
>
> :- pred eq_version_array_2(int::in,
> version_array(T)::in, version_array(T)::in) is semidet.
>
> eq_version_array_2(I, VAa, VAb) :-
> ( if I >= 0 then
> VAa ^ elem(I) = VAb ^ elem(I),
> eq_version_array_2(I - 1, VAa, VAb)
> else
> true
> ).
>
>
> :- pred cmp_version_array(comparison_result::uo,
> version_array(T)::in, version_array(T)::in) is det.
>
> cmp_version_array(R, VAa, VAb) :-
> N = min(max(VAa), max(VAb)),
> cmp_version_array_2(N, VAa, VAb, R).
>
>
> :- pred cmp_version_array_2(int::in,
> version_array(T)::in, version_array(T)::in, comparison_result::uo)
> is det.
>
> cmp_version_array_2(I, VAa, VAb, R) :-
> ( if I >= 0 then
> compare(R0, VAa ^ elem(I), VAb ^ elem(I)),
> ( if R0 = (=)
> then cmp_version_array_2(I - 1, VAa, VAb, R)
> else R = R0
> )
> else
> R = (=)
> ).
>
>
> :- pragma foreign_proc("C", version_array.empty = (VA::out),
> [will_not_call_mercury, promise_pure],
> "
> VA = va_new_empty();
> ").
>
>
> :- pragma foreign_proc("C", version_array.new(N::in, X::in) = (VA::out),
> [will_not_call_mercury, promise_pure],
> "
> VA = va_new(N, X);
> ").
>
>
> :- pragma foreign_proc("C",
> resize(VA0::in, N::in, X::in) = (VA::out),
> [will_not_call_mercury, promise_pure],
> "
> VA = va_resize(VA0, N, X);
> ").
>
>
> resize(N, X, VA, resize(VA, N, X)).
>
>
> :- pragma foreign_proc("C", size(VA::in) = (N::out),
> [will_not_call_mercury, promise_pure],
> "
> N = va_size(VA);
> ").
>
>
> :- pred get_if_in_range(version_array(T)::in, int::in, T::out) is semidet.
>
> :- pragma foreign_proc("C", get_if_in_range(VA::in, I::in, X::out),
> [will_not_call_mercury, promise_pure],
> "
> SUCCESS_INDICATOR = va_get(VA, I, &X);
> ").
>
>
> :- pred set_if_in_range(version_array(T)::in, int::in, T::in,
> version_array(T)::out) is semidet.
>
> :- pragma foreign_proc("C", set_if_in_range(VA0::in, I::in, X::in, VA::out),
> [will_not_call_mercury, promise_pure],
> "
> SUCCESS_INDICATOR = va_set(VA0, I, X, &VA);
> ").
>
>
> :- pragma foreign_proc("C", unsafe_rewind(VA0::in) = (VA::out),
> [will_not_call_mercury, promise_pure],
> "
> VA = va_rewind(VA0);
> ").
>
>
> :- pragma foreign_decl("C", "
> /*
> ** If index is -1 then value is undefined and rest is the latest
> ** array value.
> **
> ** Otherwise value is the overwritten value at index and rest is
> ** a pointer to the next version in the chain.
> */
> struct va {
> MR_Integer index; /* -1 for latest, >= 0 for older */
> MR_Word value; /* Valid if index >= 0 */
> union {
> MR_ArrayPtr array;/* Valid if index == -1 */
> struct va *next; /* Valid if index >= 0 */
> } rest;
> };
>
> /*
> ** Constructs a new empty version array.
> */
> struct va *
> va_new_empty(void);
>
> /*
> ** Constructs a new populated version array.
> */
> struct va *
> va_new(MR_Integer, MR_Word);
>
> /*
> ** Resizes a version array, populating new items with the
> ** given default value. The result is always a `latest'
> ** version.
> */
> struct va *
> va_resize(struct va *, MR_Integer, MR_Word);
>
> /*
> ** Returns the number of items in a version array.
> */
> MR_Integer
> va_size(struct va *);
>
> /*
> ** If I is in range then va_get(VA, I, &X) sets X to the Ith item
> ** in VA (counting from zero) and returns MR_TRUE. Otherwise it
> ** returns MR_FALSE.
> */
> int
> va_get(struct va *, MR_Integer, MR_Word *);
>
> /*
> ** If I is in range then va_set(VA0, I, X, VA) sets VA to be VA0
> ** updated with the Ith item as X (counting from zero) and
> returns MR_TRUE. Otherwise it returns MR_FALSE.
> */
> int
> va_set(struct va *, MR_Integer, MR_Word, struct va **);
>
> /*
> ** `Rewinds' a version array, invalidating all extant successors
> ** including the argument.
> */
> struct va*
> va_rewind(struct va *);
>
> ").
>
> :- pragma foreign_code("C", "
>
> #define va_latest_version(VA) ((VA)->index == -1)
>
>
> struct va *
> va_new_empty(void) {
>
> struct va *VA = MR_GC_NEW(struct va);
>
> VA->index = -1;
> VA->value = (MR_Word) NULL;
> VA->rest.array = (MR_ArrayPtr) MR_GC_NEW_ARRAY(MR_Word, 1);
> VA->rest.array->size = 0;
>
> return VA;
> }
>
>
> struct va *
> va_new(MR_Integer N, MR_Word X) {
>
> MR_Integer i;
> struct va *VA = MR_GC_NEW(struct va);
>
> VA->index = -1;
> VA->value = (MR_Word) NULL;
> VA->rest.array = (MR_ArrayPtr) MR_GC_NEW_ARRAY(MR_Word, N + 1);
> VA->rest.array->size = N;
>
> for(i = 0; i < N; i++) {
> VA->rest.array->elements[i] = X;
> }
>
> return VA;
> }
Our C coding guidelines suggest putting a space between for and the
parentheses. Likewise for while loops, if statements etc.
More later.
Cheers,
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
--------------------------------------------------------------------------
More information about the reviews
mailing list