src/Tools/Metis/metis.ML
changeset 39503 b7ff4b15be13
parent 39449 fbc1ab44b5f1
child 39672 a89040dd6416
equal deleted inserted replaced
39502:cffceed8e7fa 39503:b7ff4b15be13
   965         if m < n then hcf m n else hcf n m
   965         if m < n then hcf m n else hcf n m
   966       end;
   966       end;
   967 end;
   967 end;
   968 
   968 
   969 local
   969 local
   970   fun calcPrimes ps n i =
   970   fun calcPrimes mode ps i n =
   971       if List.exists (fn p => divides p i) ps then calcPrimes ps n (i + 1)
   971       if n = 0 then ps
       
   972       else if List.exists (fn p => divides p i) ps then
       
   973         let
       
   974           val i = i + 1
       
   975           and n = if mode then n else n - 1
       
   976         in
       
   977           calcPrimes mode ps i n
       
   978         end
   972       else
   979       else
   973         let
   980         let
   974           val ps = ps @ [i]
   981           val ps = ps @ [i]
       
   982           and i = i + 1
   975           and n = n - 1
   983           and n = n - 1
   976         in
   984         in
   977           if n = 0 then ps else calcPrimes ps n (i + 1)
   985           calcPrimes mode ps i n
   978         end;
   986         end;
   979 
       
   980   val primesList = Unsynchronized.ref [2];
       
   981 in
   987 in
   982   fun primes n = Metis_Portable.critical (fn () =>
   988   fun primes n =
   983       let
   989       if n <= 0 then []
   984         val Unsynchronized.ref ps = primesList
   990       else calcPrimes true [2] 3 (n - 1);
   985 
   991 
   986         val k = n - length ps
   992   fun primesUpTo n =
   987       in
   993       if n < 2 then []
   988         if k <= 0 then List.take (ps,n)
   994       else calcPrimes false [2] 3 (n - 2);
   989         else
       
   990           let
       
   991             val ps = calcPrimes ps k (List.last ps + 1)
       
   992 
       
   993             val () = primesList := ps
       
   994           in
       
   995             ps
       
   996           end
       
   997       end) ();
       
   998 end;
   995 end;
   999 
       
  1000 fun primesUpTo n = Metis_Portable.critical (fn () =>
       
  1001     let
       
  1002       fun f k =
       
  1003           let
       
  1004             val l = primes k
       
  1005 
       
  1006             val p = List.last l
       
  1007           in
       
  1008             if p < n then f (2 * k) else takeWhile (fn j => j <= n) l
       
  1009           end
       
  1010     in
       
  1011       f 8
       
  1012     end) ();
       
  1013 
   996 
  1014 (* ------------------------------------------------------------------------- *)
   997 (* ------------------------------------------------------------------------- *)
  1015 (* Strings.                                                                  *)
   998 (* Strings.                                                                  *)
  1016 (* ------------------------------------------------------------------------- *)
   999 (* ------------------------------------------------------------------------- *)
  1017 
  1000 
  1226 (* Metis_Useful impure features.                                                   *)
  1209 (* Metis_Useful impure features.                                                   *)
  1227 (* ------------------------------------------------------------------------- *)
  1210 (* ------------------------------------------------------------------------- *)
  1228 
  1211 
  1229 local
  1212 local
  1230   val generator = Unsynchronized.ref 0
  1213   val generator = Unsynchronized.ref 0
  1231 in
  1214 
  1232   fun newInt () = Metis_Portable.critical (fn () =>
  1215   fun newIntThunk () =
  1233       let
  1216       let
  1234         val n = !generator
  1217         val n = !generator
       
  1218 
  1235         val () = generator := n + 1
  1219         val () = generator := n + 1
  1236       in
  1220       in
  1237         n
  1221         n
  1238       end) ();
  1222       end;
  1239 
  1223 
  1240   fun newInts 0 = []
  1224   fun newIntsThunk k () =
  1241     | newInts k = Metis_Portable.critical (fn () =>
       
  1242       let
  1225       let
  1243         val n = !generator
  1226         val n = !generator
       
  1227 
  1244         val () = generator := n + k
  1228         val () = generator := n + k
  1245       in
  1229       in
  1246         interval n k
  1230         interval n k
  1247       end) ();
  1231       end;
       
  1232 in
       
  1233   fun newInt () = Metis_Portable.critical newIntThunk ();
       
  1234 
       
  1235   fun newInts k =
       
  1236       if k <= 0 then []
       
  1237       else Metis_Portable.critical (newIntsThunk k) ();
  1248 end;
  1238 end;
  1249 
  1239 
  1250 fun withRef (r,new) f x =
  1240 fun withRef (r,new) f x =
  1251   let
  1241   let
  1252     val old = !r
  1242     val old = !r
 14195 
 14185 
 14196 (* ------------------------------------------------------------------------- *)
 14186 (* ------------------------------------------------------------------------- *)
 14197 (* Basic conjunctive normal form.                                            *)
 14187 (* Basic conjunctive normal form.                                            *)
 14198 (* ------------------------------------------------------------------------- *)
 14188 (* ------------------------------------------------------------------------- *)
 14199 
 14189 
 14200 val newSkolemFunction =
 14190 local
 14201     let
 14191   val counter : int Metis_StringMap.map Unsynchronized.ref = Unsynchronized.ref (Metis_StringMap.new ());
 14202       val counter : int Metis_StringMap.map Unsynchronized.ref = Unsynchronized.ref (Metis_StringMap.new ())
 14192 
 14203 
 14193   fun new n () =
 14204       fun new n () =
 14194       let
 14205           let
 14195         val Unsynchronized.ref m = counter
 14206             val Unsynchronized.ref m = counter
 14196         val s = Metis_Name.toString n
 14207             val s = Metis_Name.toString n
 14197         val i = Option.getOpt (Metis_StringMap.peek m s, 0)
 14208             val i = Option.getOpt (Metis_StringMap.peek m s, 0)
 14198         val () = counter := Metis_StringMap.insert m (s, i + 1)
 14209             val () = counter := Metis_StringMap.insert m (s, i + 1)
 14199         val i = if i = 0 then "" else "_" ^ Int.toString i
 14210             val i = if i = 0 then "" else "_" ^ Int.toString i
 14200         val s = skolemPrefix ^ "_" ^ s ^ i
 14211             val s = skolemPrefix ^ "_" ^ s ^ i
 14201       in
 14212           in
 14202         Metis_Name.fromString s
 14213             Metis_Name.fromString s
 14203       end;
 14214           end
 14204 in
 14215     in
 14205   fun newSkolemFunction n = Metis_Portable.critical (new n) ();
 14216       fn n => Metis_Portable.critical (new n) ()
 14206 end;
 14217     end;
       
 14218 
 14207 
 14219 fun skolemize fv bv fm =
 14208 fun skolemize fv bv fm =
 14220     let
 14209     let
 14221       val fv = Metis_NameSet.transform Metis_Term.Var fv
 14210       val fv = Metis_NameSet.transform Metis_Term.Var fv
 14222 
 14211 
 14751 
 14740 
 14752 (* ------------------------------------------------------------------------- *)
 14741 (* ------------------------------------------------------------------------- *)
 14753 (* Definitions.                                                              *)
 14742 (* Definitions.                                                              *)
 14754 (* ------------------------------------------------------------------------- *)
 14743 (* ------------------------------------------------------------------------- *)
 14755 
 14744 
 14756 val newDefinitionRelation =
 14745 local
 14757     let
 14746   val counter : int Unsynchronized.ref = Unsynchronized.ref 0;
 14758       val counter : int Unsynchronized.ref = Unsynchronized.ref 0
 14747 
 14759     in
 14748   fun new () =
 14760       fn () => Metis_Portable.critical (fn () =>
 14749       let
 14761          let
 14750         val Unsynchronized.ref i = counter
 14762            val Unsynchronized.ref i = counter
 14751         val () = counter := i + 1
 14763            val () = counter := i + 1
 14752       in
 14764          in
 14753         definitionPrefix ^ "_" ^ Int.toString i
 14765            definitionPrefix ^ "_" ^ Int.toString i
 14754       end;
 14766          end) ()
 14755 in
 14767     end;
 14756   fun newDefinitionRelation () = Metis_Portable.critical new ();
       
 14757 end;
 14768 
 14758 
 14769 fun newDefinition def =
 14759 fun newDefinition def =
 14770     let
 14760     let
 14771       val fv = freeVars def
 14761       val fv = freeVars def
 14772       val rel = newDefinitionRelation ()
 14762       val rel = newDefinitionRelation ()