Sorry for sending this to the request address :(
Hi, trying to compile these two files:
(* BITSET.sml *)
signature BITSET = sig
exception Not_found; (* raised by [choose] *)
type ty;
(* type of bitsets*)
val make_bitset : int -> ty ;
(* [make_bitset size] creates a new empty bitset containing [size] bits.*)
val copy : ty -> ty ;
(* [copy v] returns a fresh exact copy of bitset [v].*)
val copy_negated : ty -> ty ;
(* [copy_negated v] returns a fresh bit vector that is the complement of [v].*)
val set : ty -> int -> unit ;
(* [set v i] sets the [i]th bit of vector [v].*)
val clear : ty -> int -> unit ;
(* [clear v i] clears the [i]th bit of vector [v].*)
val test : ty -> int -> bool ;
(* [test v i] tests the [i]th bit of vector [v].*)
val neg : ty -> unit ;
(* [neg v] complements the vector [v] in place.*)
val band : ty -> ty -> unit ;
(* [band v_to v_from] performs a [land] of [v_to] and [v_from],
changing [v_to] in place.*)
val bor : ty -> ty -> unit ;
(* [bor v_to v_from] performs a [lor] of [v_to] and [v_from],
changing [v_to] in place.*)
val bxor : ty -> ty -> unit ;
(* [bxor v_to v_from] performs a [lxor] of [v_to] and [v_from],
changing [v_to] in place.*)
val bsub : ty -> ty -> unit ;
(* [bsub v_to v_from] computes the set difference [v_to - v_from],
storing the result in [v_to].*)
val is_sub : ty -> ty -> bool ;
(* [is_sub v1 v2] tests if vector [v1] is a subset of [v2].*)
val is_equal : ty -> ty -> bool ;
(* [is_equal v1 v2] tests if vector [v1] is structurally equal to [v2].*)
val choose : ty -> int ;
(* [choose v] returns an arbitary integer [i] such that [v[i] = true],
if there is one, otherwise raises [Not_found]. Equal integers are returned
for structurally equal vectors.*)
end;
(* BITSET.sml ends here *)
(* Bitset.sml *)
structure Bitset :> BITSET = struct
exception Not_found; (* raised by [choose] *)
exception Size_mismatch;
(* import selected stuff from LargeWord and Array *)
val wordSize = LargeWord.wordSize;
type word = LargeWord.word;
val notb = LargeWord.notb;
val << = LargeWord.<< ;
val fromLargeInt = LargeWord.fromLargeInt;
val andb = LargeWord.andb;
val orb = LargeWord.orb;
val xorb = LargeWord.xorb;
val length = Array.length;
val sub = Array.sub;
val tabulate = Array.tabulate;
val update = Array.update;
val modifyi = Array.modifyi;
val foldli = Array.foldli;
val appi = Array.appi;
type ty = {
size : int ,
last_mask : word ,
bits : word Array.array
};
fun make_mask (i: int) = notb (<< (notb (fromLargeInt 0), Word.fromInt i));
fun word_size (s: int) = (s div wordSize) + 1;
fun make_bitset s =
if s < 0 then raise Size
else let val bits = Array.array (word_size s, fromLargeInt 0);
val mask = make_mask (s mod wordSize) in
{ size = size, last_mask = mask, bits = bits } end ;
fun copy v =
let val s = #size v ; val ws = word_size s ;
fun f i = sub (#bits v, i) in
{ size = s, last_mask = #last_mask v, bits = Array.tabulate (ws, f) } end ;
fun copy_negated v =
let val last = length (#bits v) - 1;
fun f i = if i <> last then notb (sub (#bits v, i))
else andb (#last_mask v, notb (sub (#bits v, i))) in
{ size = #size v, last_mask = #last_mask v, bits = Array.tabulate (last+1, f) } end ;
fun set v i =
let val idx = i div wordSize; val bit = i mod wordSize;
val mask = << (fromLargeInt 1, Word.fromInt bit) in
update (#bits v, idx, orb (sub (#bits v, idx), mask)) end;
fun clear v i =
let val idx = i div wordSize; val bit = i mod wordSize;
val mask = notb (<< (fromLargeInt 1, Word.fromInt bit)) in
update (#bits v, idx, andb (sub (#bits v, idx), mask)) end;
fun test v i =
let val idx = i div wordSize; val bit = i mod wordSize;
val mask = << (fromLargeInt 1, Word.fromInt bit) in
andb (sub (#bits v, idx), mask) <> fromLargeInt 0 end;
fun neg v =
let val last = length (#bits v) - 1;
fun f (i, x) =
if i <> last then notb x
else andb (#last_mask v, notb x) in
modifyi f (#bits v, 0, SOME(last+1)) end;
fun band to from =
if #size from <> #size to then raise Size_mismatch
else let fun f (i, x) = andb (sub (#bits from, i), x) in
modifyi f (#bits to, 0, SOME(length (#bits to))) end;
fun bor to from =
if #size from <> #size to then raise Size_mismatch
else let fun f (i, x) = orb (sub (#bits from, i), x) in
modifyi f (#bits to, 0, SOME(length (#bits to))) end;
fun bxor to from =
if #size from <> #size to then raise Size_mismatch
else let fun f (i, x) = xorb (sub (#bits from, i), x) in
modifyi f (#bits to, 0, SOME(length (#bits to))) end;
fun bsub to from =
if #size from <> #size to then raise Size_mismatch
else let fun f (i, x) = andb (notb (sub (#bits from, i)), x) in
modifyi f (#bits to, 0, SOME(length (#bits to))) end;
fun is_sub v1 v2 =
if #size v1 <> #size v2 then raise Size_mismatch
else let fun p (i, x, b) = b andalso andb (x, notb (sub (#bits v2, i))) = fromLargeInt 0 in
foldli p true (#bits v1, 0, SOME(length (#bits v1))) end;
fun is_equal v1 v2 =
if #size v1 <> #size v2 then raise Size_mismatch
else let fun p (i, x, b) = b andalso x = sub (#bits v2, i) in
foldli p true (#bits v1, 0, SOME(length (#bits v1))) end;
fun find_bit (w: word) =
let fun fb1 i mask = if andb (mask, w) <> fromLargeInt 0 then i
else fb1 (i+1) (<< (mask, Word.fromInt 1)) in
fb1 0 (fromLargeInt 1) end ;
fun choose v =
let val ridx = ref ~1;
fun f (i, x) = if !ridx = ~1 andalso x <> 0
then ridx := i else () in
(appi f (#bits v, 0, SOME(length (#bits v)));
if !ridx = ~1 then raise Not_found
else let val idx = !ridx;
val bit = find_bit (sub (#bits v, idx)) in
!ridx * wordSize + bit end)
end;
end;
(* Bitset.sml ends here *)
I am getting these errors:
> Making Bitset
Error: in 'Bitset.sml', line 133.
Can't unify Words.LargeWord.word with int (Different type constructors)
Found near find_bit(sub( (#bits)(v), idx))
Error: in 'Bitset.sml', line 20.
Can't match int to Words.LargeWord.word (Different type constructors)
While checking (choose) near
structure
Bitset :> BITSET =
struct
exception Not_found
exception Size_mismatch
val ... = ...
type ...
...
...
end
Error: in 'Bitset.sml', line 20.
Can't match int to string -> int (Incompatible types)
While checking (make_bitset) near
structure
Bitset :> BITSET =
struct
exception Not_found
exception Size_mismatch
val ... = ...
type ...
...
...
end
Bitset was not declared
Exception- Fail "Static errors (pass2)" raised
I look at the code forward and backward and really think it is correct.
Here's the typing as I see it:
bit = find_bit (sub (#bits v, idx))
^^^ ^^^^^^^^ ^^^ ^^^^^^^ ^^^
int word->int (word array, int)->word word array int
!ridx * wordSize + bit
^^^^^ ^^^^^^^^ ^^^
int int int
And what in the world has STRING to do with it ?!?
February 2002 release of PolyML.
--
Ian Zimmerman, Oakland, California, U.S.A.
GPG: 433BA087 9C0F 194F 203A 63F7 B1B8 6E5A 8CA3 27DB 433B A087
EngSoc adopts market economy: cheap is wasteful, efficient is expensive.
