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

[schachte at cs.mu.OZ.AU]

On  8 Nov, Fergus Henderson wrote:

> 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'.

Take the base 2 log, and then shift 1 left that many places to get the
value to OR into the bitset?
That's a pretty long, inefficient way to compute an identity function.

So let me get this straight.  When I have an enumerated type all of
whose members are represented as a single bit so I can just OR the
values together to make a bitset, you're suggesting I take the log of
the value so I can shift 1 that many places to give me back the number
I started with, which I can then OR with other such values?  I thought
we were interested in efficiency.  Also, this doesn't handle
enumerated types where there are holes.

>> (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.
> 

-- 
Peter Schachte                     The use of COBOL cripples the mind; its
mailto:schachte at cs.mu.OZ.AU        teaching should, therefore, be regarded
http://www.cs.mu.oz.au/~schachte/  as a criminal offense.
PGP: finger schachte at 128.250.37.3      -- E. W. Dijkstra 

--------------------------------------------------------------------------
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
--------------------------------------------------------------------------