[m-dev.] for review: add a new pred to array.m

[Thomas Charles Conway]

On Tue, Mar 30, 1999 at 05:09:09PM EST, Fergus Henderson wrote:
> On 30-Mar-1999, Thomas Charles Conway <conway at hydra.cs.mu.oz.au> wrote:
> How about just
> 
> 	* We've added some new predicates to the Mercury standard library:
> 		bag__count_value/3,
> 		array__map/3.
> 
> ?

Done.

> If you want short names for type variables, I much prefer T1, T2, ...
> rather than T, U, ...

Done.

> 
> Any particular reason why this is a predicate, rather than a function?
> The old rationale for using predicates was for debugging with Prolog, 
> but that doesn't apply now.
> 

Well, it's more consistent with the rest of the array module.

> > +	% The current implementation of array__map converts to a list,
> > +	% invokes list__map, then converts back to an array representation.
> > +	% It would be nicer to be able to do the map on each element
> > +	% maintaining the same array skeleton. Unfortunately this is
> > +	% tricky since the intermediate arrays have some elements of
> > +	% one type, and some of the other.
> 
> Yes, that would be tricky -- particularly for the accurate garbage collector
> and the debugger.  I don't think it would be worthwhile to try to make them
> somehow cope with mixed arrays like this.

I had in mind something more like the array partitioning scheme you
and I once talked about. eg
	% :- type partition(T) more-or-less-== array(T)
	%  partition(Whole, Ind, Part1, Part2)
	% [Pmin, Ind-1] -> Part1
	% [Ind, Pmax] -> Part2
	% where Pmin and Pmax are the minimum and maximum indices of
	% the whole partition.
	:- pred partition(partition(T), int, partition(T), partition(T)).
	:- mode partition(array_di, in, array_uo, array_uo) is det.

which splits the array into two parts at the given index. Now, you
could make a version of array__map which only works on signleton
partitions then use a combine predicate:
	:- pred combine(parition(T), partition(T), partition(T)).
	:- mode combine(array_di, array_di, array_uo) is det.
(and make combine abort if you try to combine non-adjacent partitions).

Now map can be written something like:
	
array__map(Closure, OldArray, NewArray) :-
	array__size(OldArray, Size),
	array__to_partition(OldArray, Part0),
	partition(Part0, 0, DonePart0, RemainingPart), % DonePart0 is empty
		% It's safe to coerce the type since there
		% are no elements
	coerce(DonePart0, DonePart1),
	array__map2(0, Size, Closure, RemainingPart, DonePart1, DonePart),
	array__from_partition(DonePart, NewArray).

array__map2(Ind, Size, Closure, RemainingPart0, DonePart0, DonePart) :-
	( Ind >= Size ->
		DonePart = DonePart0
	;
		partition(RemainingPart0, Ind + 1, PartToDo, RemainingPart),
		map_singleton_partition(Closure, PartToDo, PartDone),
		combine(DonePart0, PartDone, DonePart1),
		array__map2(Ind + 1, Size, Closure, RemainingPart,
			DonePart1, DonePart)
	).

Now, given an appropriate C representation for partitions, it shouldn't
be too hard to convince accurate GC to do the right job.

> 
> So a zero-copy implementation is tricky, in general.
> However, it's certainly quite possible to do better than your two-copy
> implementation.  A one-copy implementation should be straight-forward, no?
> 

Yes, you're right.
See the revised diff.

> 
> If you want to get tricky, you could special-case this for the case
> where the two types are the same, using a dynamic type test:
> 

I haven't bothered with this.

Here's a revised diff.

-- 
Thomas Conway <conway at cs.mu.oz.au> )O+
To a killer whale, otters are like hairy popcorn -- Paul Dayton

cvs diff: Diffing .
Index: NEWS
===================================================================
RCS file: /home/staff/zs/imp/mercury/NEWS,v
retrieving revision 1.141
diff -u -r1.141 NEWS
--- NEWS	1999/03/30 05:45:17	1.141
+++ NEWS	1999/03/30 23:57:58
@@ -39,7 +39,8 @@
 Changes to the Mercury standard library:
 ****************************************
 
-* We've added a new predicate to the Mercury standard library:
+* We've added some new predicates to the Mercury standard library:
+	array__map/3,
 	bag__count_value/3.
 
 * The following predicates have been replaced by functions with
cvs diff: Diffing bindist
cvs diff: Diffing boehm_gc
cvs diff: Diffing boehm_gc/Mac_files
cvs diff: Diffing boehm_gc/cord
cvs diff: Diffing boehm_gc/cord/private
cvs diff: Diffing boehm_gc/include
cvs diff: Diffing boehm_gc/include/private
cvs diff: Diffing browser
cvs diff: Diffing bytecode
cvs diff: Diffing bytecode/test
cvs diff: Diffing compiler
cvs diff: Diffing compiler/notes
cvs diff: Diffing debian
cvs diff: Diffing doc
cvs diff: Diffing extras
cvs diff: Diffing extras/aditi
cvs diff: Diffing extras/cgi
cvs diff: Diffing extras/complex_numbers
cvs diff: Diffing extras/complex_numbers/samples
cvs diff: Diffing extras/complex_numbers/tests
cvs diff: Diffing extras/dynamic_linking
cvs diff: Diffing extras/exceptions
cvs diff: Diffing extras/graphics
cvs diff: Diffing extras/graphics/mercury_opengl
cvs diff: Diffing extras/graphics/mercury_tcltk
cvs diff: Diffing extras/graphics/samples
cvs diff: Diffing extras/graphics/samples/calc
cvs diff: Diffing extras/graphics/samples/maze
cvs diff: Diffing extras/graphics/samples/pent
cvs diff: Diffing extras/lazy_evaluation
cvs diff: Diffing extras/odbc
cvs diff: Diffing extras/references
cvs diff: Diffing extras/references/samples
cvs diff: Diffing extras/references/tests
cvs diff: Diffing extras/trailed_update
cvs diff: Diffing extras/trailed_update/samples
cvs diff: Diffing extras/trailed_update/tests
cvs diff: Diffing library
Index: library/array.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/library/array.m,v
retrieving revision 1.52
diff -u -r1.52 array.m
--- array.m	1999/03/22 08:08:40	1.52
+++ array.m	1999/03/30 23:50:27
@@ -209,6 +209,11 @@
 :- mode array__bsearch(array_ui, in, pred(in, in, out) is det, out) is det.
 :- mode array__bsearch(in, in, pred(in, in, out) is det, out) is det.
 
+	% array__map(Closure, OldArray, NewArray) applys `Closure' to
+	% each of the elements of `OldArray' to create `NewArray'.
+:- pred array__map(pred(T1, T2), array(T1), array(T2)).
+:- mode array__map(pred(in, out) is det, array_di, array_uo) is det.
+
 %-----------------------------------------------------------------------------%
 :- implementation.
 
@@ -719,6 +724,34 @@
 		    array__bsearch_2(Array, Lo, Mid1, El, Compare, Result)
 	        )
 	    )
+	).
+
+%-----------------------------------------------------------------------------%
+
+array__map(Closure, OldArray, NewArray) :-
+	( array__semidet_lookup(OldArray, 0, Elem0) ->
+		array__size(OldArray, Size),
+		call(Closure, Elem0, Elem),
+		array__init(Size, Elem, NewArray0),
+		array__map_2(0, Size, Closure, OldArray,
+		NewArray0, NewArray)
+	;
+		array__make_empty_array(NewArray)
+	).
+
+:- pred array__map_2(int, int, pred(T1, T2), array(T1), array(T2), array(T2)).
+:- mode array__map_2(in, in, pred(in, out) is det, in, array_di, array_uo)
+		is det.
+
+array__map_2(N, Size, Closure, OldArray, NewArray0, NewArray) :-
+	( N >= Size ->
+		NewArray = NewArray0
+	;
+		array__lookup(OldArray, N, OldElem),
+		Closure(OldElem, NewElem),
+		array__set(NewArray0, N, NewElem, NewArray1),
+		array__map_2(N + 1, Size, Closure, OldArray,
+		NewArray1, NewArray)
 	).
 
 %-----------------------------------------------------------------------------%
cvs diff: Diffing lp_solve
cvs diff: Diffing lp_solve/lp_examples
cvs diff: Diffing profiler
cvs diff: Diffing readline
cvs diff: Diffing readline/doc
cvs diff: Diffing readline/examples
cvs diff: Diffing readline/shlib
cvs diff: Diffing readline/support
cvs diff: Diffing runtime
cvs diff: Diffing runtime/GETOPT
cvs diff: Diffing runtime/machdeps
cvs diff: Diffing samples
cvs diff: Diffing samples/c_interface
cvs diff: Diffing samples/c_interface/c_calls_mercury
cvs diff: Diffing samples/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/c_interface/mercury_calls_c
cvs diff: Diffing samples/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/diff
cvs diff: Diffing samples/muz
cvs diff: Diffing samples/rot13
cvs diff: Diffing scripts
cvs diff: Diffing tools
cvs diff: Diffing trace
cvs diff: Diffing trial
cvs diff: Diffing util