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.