[m-dev.] for review: tuples [1]

[Fergus Henderson]

Here's a more fleshed-out proposal for tuples with support
for typeclass instance declaratios that cover tuples of all arities.
The basic idea is to add `{ X | Xs }' as a special constructor
and type constructor for tuples.  Declaratively, there would be
essentially no difference between tuples and nested pairs, but
there would be a significant operational difference: tuples would
be represented using a flat representation.  This would lead to
O(N) differences in the performance for various operations.
For a tuple of arity N, `{ X | Xs }' would take O(N),
while extracting the Nth element of the tuple would take O(1),
whereas for nested pairs, it would be the converse.

My proposal is based on Simon's original proposal, with the
following additions.

First, syntax: the expression

	{ X | Xs }

would be parsed as

	'{|}'(X, Xs)

Likewise, in a manner similar to that for lists,

	{ X1, X2 | Xs } and { X1, X2, ..., XN | Xs }

would be parsed as
	
	'{|}'(X1, '{|}'(X2, Xs)) and
	'{|}'(X1, '{|}'(X2, ..., '{|}'(XN, Xs)...))

respectively.

Next, typing.  For the expression `X = { Y | Ys }',
type inference would infer these constraints:

	Y :: T
	X :: { T | Ts }
	Ys :: Ts
	& tuple(Ts)

Here `tuple' would be a builtin type class, declared as
an abstract type class in the `builtin' module, with every
tuple type implicitly an instance.  (Making the type class
abstract prevents users from declaring new instances for it.)

The '{|}' type constructor would need to be handled
specially in the type unification algorithm.
In particular,

	- unifying {X1} and {Y1 | Y2} should succeed,
	  binding Y2 to {};
	- unifying {X1, X2} and {Y1 | Y2} should succeed,
	  binding Y2 to {X2};
	- unifying {X1, X2, ..., XN} and {Y1 | Y2} should succeed,
	  binding Y2 to {X2, ..., XN};
	- and likewise for vice versa.

For type class instances, only the `{}/0' and the `{|}/2'
type constructors should be allowed in instance declarations.
The `{}/N' (N > 0) constructors should not be allowed,
since allowing them could result in overlapping instance
declarations.  (This is similar to the other restrictions
designed to prevent overlapping instance declarations.
We can reconsider this rule if we decide to loosen those
other restrictions.  It would be nice to allow *either*
instance declarations for {|}/2 *or* {}/N where N > 1,
but not both, but I couldn't figure out how to make that
work -- I don't think there is any easy way to check
conditions like that at link time just using a standard
linker, especially in the case of multi-parameter type classes.)

The '{|}' constructor could be treated as a builtin or
standard library function:

	:- func '{|}'(T1, T2) = '{|}'(T1, T2) <= tuple(T2).
	% XXX ideally this would be polymorphically moded,
	%     but for the short term we could make do with
	%     the following finite set:
	:- mode '{|}'(in, in) = out is det.
	:- mode '{|}'(out, out) = in(bound({})) is failure.
	:- mode '{|}'(out, out) = in(bound({ground|ground})) is det.
					% XXX using {|} in insts, as above,
					% might need special treatment
	:- mode '{|}'(out, out) = in is semidet.

The function be implemented in several ways: in Mercury code
(e.g. using arg and functor), in C code, or we could generate calls to
it as inline code, like we do for calls to call/N.

If we were generating inline code, the code that we would generate
would be either

	(a) if it is a construction (mode (in, in) = out)

	arity of X := arity of Ys + 1
	allocate memory for X
	copy Y
	loop to copy Ys
	
	(b) if it is a deconstruction (mode (out, out) = in)

	check that arity of Xs > 0
	copy Y
	arity of Ys := arity of Xs - 1
	allocate memory for Ys
	loop to copy Ys

Note that the arity of a tuple is contained in the type_info for that tuple,
which will be included in the typeclass_info for the tuple type class;
that is how the '{|}' function can determine the arity.

We could implement tuple concatentation as an ordinary function:

	:- func T1 ++ T2 = T3 <= (tuple(T1), tuple(T2), tuple(T3)).
	{} ++ T = T.
	{X|Xs} ++ Ys = {X|(Xs ++ Ys)}.

Of course this is O(N*N); for efficiency we might want to implement
tuple concatenation differently, e.g. using C code.

We might also want to have functions tuple_arity/1 and tuple_arg/1,

	:- func tuple_arity(T) = int <= tuple(T).
	:- some [ArgT] func tuple_arg(T, int) = ArgT <= tuple(T).

which would be versions of std_util:functor/3 and std_util:arg/2
that were specialized for tuples:

	tuple_arity(Tuple) = Arity :-
		std_util__functor(Tuple, _Name, Arity).

	tuple_arg(Tuple, Arg) = std_util__arg(Tuple, Arg).

Hmm, maybe that doesn't buy you enough to be worthwhile.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------