[m-dev.] for review: use bitsets in quantification

Fergus Henderson fjh at cs.mu.OZ.AU
Wed Nov 8 15:31:43 AEDT 2000


On 08-Nov-2000, schachte at cs.mu.OZ.AU <schachte at cs.mu.OZ.AU> wrote:
> On  8 Nov, Fergus Henderson wrote:
> > Actually on second thoughts I disagree with the idea too:
> > sparse_bitset doesn't strictly require that `to_int' return contiguous
> > values, but I can't see any practical advantage in defining `to_int'
> > in a way that doesn't return contiguous values, and so I don't think
> > this extra flexibility would actually buy you anything.
> 
> I was thinking of cases where you're using a C enum type (or a
> psuedo-type defined with #defines) that has holes, and you want to use
> that type directly in Mercury to avoid translation.  I've seen some such
> types defined as powers of two specifically so you could make sets of
> them -- wouldn't it be ironic if you couldn't use Mercury bitsets for
> them?

For a case like that, you could define `to_int' to return the log to
the base 2 of the value (using int__log2).  And you could then use
`dense_bitset' (or perhaps even `int_bitset', for bit sets that fit
in a single int), rather than `sparse_bitset'.

> (To make such types efficiently usable in bitsets, it might be a
> good idea to make the predicate/function that maps between value and
> the various needed masks be a method of this class.)

Yep.  Something like this:

	typeclass enum where [
		...
		pred bitmask(T::in, int::out, int::out) is det,
		% This should have the following semantics:
		%	bitmask(Enum, IntNum, BitMask) <=> (
		% 		Val = to_int(Enum),
		% 		IntNum = Val `div` int__bits_per_int,
		% 		BitNum = Val `mod` int__bits_per_int,
		% 		BitMask = 1 << BitNum
		% 	).
	].


	:- pred default_bitmask(T::in, int::out, int::out) <= enum(T)
		is det.
	% implemented more efficiently than the spec, e.g. using
	% `unchecked_left_shift`, and pragma c_code to help gcc
	% optimize the `div` and `mod`.

> Let me turn the question around:  why do you want prev and next?

Because I want `enum's to be enumerable.  I'd like to move the `..`
function from library/int.m to library/enum.m and make it work on any
type which is an instance of `enum'.

> I agree with the goal of keeping things simple.  In the absence of default
> methods, having unneeded methods means having unneeded, distracting
> code for every instance.

The additional code need not be particularly complicated, e.g.

	:- instance enum(foo) where [
		...
		func(prev/1) is default_prev,
		func(next/1) is default_next,
		pred(bitmask/2) is default_bitmask
	].

but I agree that if you have a lot of methods with defaults then this
can be distracting.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- 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
--------------------------------------------------------------------------



More information about the developers mailing list