author | wenzelm |
Mon, 19 Feb 2018 10:35:53 +0100 | |
changeset 67658 | 67e5deb9e290 |
parent 62923 | 3a122e1e352a |
child 67659 | 11b390e971f6 |
permissions | -rw-r--r-- |
28199 | 1 |
(* Title: Pure/Concurrent/par_list.ML |
2 |
Author: Makarius |
|
3 |
||
4 |
Parallel list combinators. |
|
5 |
||
6 |
Notes: |
|
7 |
||
8 |
* These combinators only make sense if the operator (function or |
|
9 |
predicate) applied to the list of operands takes considerable |
|
10 |
time. The overhead of scheduling is significantly higher than |
|
11 |
just traversing the list of operands sequentially. |
|
12 |
||
28358 | 13 |
* The order of operator application is non-deterministic. Watch out |
28199 | 14 |
for operators that have side-effects or raise exceptions! |
15 |
*) |
|
16 |
||
17 |
signature PAR_LIST = |
|
18 |
sig |
|
41711 | 19 |
val map_name: string -> ('a -> 'b) -> 'a list -> 'b list |
58993
302104d8366b
prefer independent parallel map where user input is processed -- avoid non-deterministic feedback in error situations;
wenzelm
parents:
52945
diff
changeset
|
20 |
val map_independent: ('a -> 'b) -> 'a list -> 'b list |
28199 | 21 |
val map: ('a -> 'b) -> 'a list -> 'b list |
22 |
val get_some: ('a -> 'b option) -> 'a list -> 'b option |
|
23 |
val find_some: ('a -> bool) -> 'a list -> 'a option |
|
24 |
val exists: ('a -> bool) -> 'a list -> bool |
|
25 |
val forall: ('a -> bool) -> 'a list -> bool |
|
26 |
end; |
|
27 |
||
29368 | 28 |
structure Par_List: PAR_LIST = |
28199 | 29 |
struct |
30 |
||
67658 | 31 |
fun forked_results name f xs = |
59180
c0fa3b3bdabd
discontinued central critical sections: NAMED_CRITICAL / CRITICAL;
wenzelm
parents:
59137
diff
changeset
|
32 |
if null xs orelse null (tl xs) orelse not (Multithreading.enabled ()) |
41675 | 33 |
then map (Exn.capture f) xs |
67658 | 34 |
else Future.forked_results {name = name, deps = []} (map (fn x => fn () => f x) xs); |
28199 | 35 |
|
67658 | 36 |
fun map_name name f xs = Par_Exn.release_first (forked_results name f xs); |
41711 | 37 |
fun map f = map_name "Par_List.map" f; |
58993
302104d8366b
prefer independent parallel map where user input is processed -- avoid non-deterministic feedback in error situations;
wenzelm
parents:
52945
diff
changeset
|
38 |
fun map_independent f = map (Exn.interruptible_capture f) #> Par_Exn.release_all; |
28199 | 39 |
|
40 |
fun get_some f xs = |
|
41 |
let |
|
59136
c2b23cb8a677
added Par_List in Scala, in accordance to ML version;
wenzelm
parents:
58993
diff
changeset
|
42 |
exception FOUND of 'b; |
40700
4b4dfe05b5d7
clarified Par_List.managed_results, with explicit propagation of outermost physical interrupt to forked futures (e.g. to make timeout apply here as expected and prevent zombies);
wenzelm
parents:
37865
diff
changeset
|
43 |
val results = |
67658 | 44 |
forked_results "Par_List.get_some" |
59136
c2b23cb8a677
added Par_List in Scala, in accordance to ML version;
wenzelm
parents:
58993
diff
changeset
|
45 |
(fn x => (case f x of NONE => () | SOME y => raise FOUND y)) xs; |
28199 | 46 |
in |
59136
c2b23cb8a677
added Par_List in Scala, in accordance to ML version;
wenzelm
parents:
58993
diff
changeset
|
47 |
(case get_first (fn Exn.Exn (FOUND res) => SOME res | _ => NONE) results of |
c2b23cb8a677
added Par_List in Scala, in accordance to ML version;
wenzelm
parents:
58993
diff
changeset
|
48 |
NONE => (Par_Exn.release_first results; NONE) |
c2b23cb8a677
added Par_List in Scala, in accordance to ML version;
wenzelm
parents:
58993
diff
changeset
|
49 |
| some => some) |
28199 | 50 |
end; |
51 |
||
52 |
fun find_some P = get_some (fn x => if P x then SOME x else NONE); |
|
53 |
||
59137 | 54 |
fun exists P = is_some o find_some P; |
28199 | 55 |
fun forall P = not o exists (not o P); |
56 |
||
57 |
end; |