src/Pure/Concurrent/par_list.ML
author wenzelm
Thu, 11 Sep 2008 13:24:14 +0200
changeset 28199 e63d05ceec24
child 28304 4b0477452943
permissions -rw-r--r--
Parallel list combinators.
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
28199
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
     1
(*  Title:      Pure/Concurrent/par_list.ML
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
     2
    ID:         $Id$
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
     3
    Author:     Makarius
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
     4
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
     5
Parallel list combinators.
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
     6
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
     7
Notes:
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
     8
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
     9
  * These combinators only make sense if the operator (function or
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    10
    predicate) applied to the list of operands takes considerable
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    11
    time.  The overhead of scheduling is significantly higher than
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    12
    just traversing the list of operands sequentially.
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    13
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    14
  * The order of operator application is non-determined.  Watch out
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    15
    for operators that have side-effects or raise exceptions!
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    16
*)
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    17
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    18
signature PAR_LIST =
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    19
sig
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    20
  val map: ('a -> 'b) -> 'a list -> 'b list
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    21
  val get_some: ('a -> 'b option) -> 'a list -> 'b option
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    22
  val find_some: ('a -> bool) -> 'a list -> 'a option
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    23
  val exists: ('a -> bool) -> 'a list -> bool
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    24
  val forall: ('a -> bool) -> 'a list -> bool
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    25
end;
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    26
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    27
structure ParList: PAR_LIST =
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    28
struct
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    29
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    30
fun proper_exn (Exn.Result _) = NONE
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    31
  | proper_exn (Exn.Exn Interrupt) = NONE
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    32
  | proper_exn (Exn.Exn exn) = SOME exn;
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    33
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    34
fun raw_map f xs =
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    35
  let val group = TaskQueue.new_group ()
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    36
  in Future.join_results (List.map (fn x => Future.future (SOME group) [] (fn () => f x)) xs) end;
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    37
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    38
fun map f xs =
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    39
  let val results = raw_map f xs in
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    40
    (case get_first proper_exn results of
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    41
      SOME exn => raise exn
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    42
    | NONE => List.map Exn.release results)
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    43
  end;
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    44
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    45
fun get_some f xs =
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    46
  let
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    47
    exception FOUND of 'b option;
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    48
    fun found (Exn.Exn (FOUND some)) = some
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    49
      | found _ = NONE;
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    50
    val results = raw_map (fn x => (case f x of NONE => () | some => raise FOUND some)) xs;
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    51
  in
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    52
    (case get_first found results of
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    53
      SOME y => SOME y
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    54
    | NONE =>
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    55
        (case get_first proper_exn results of
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    56
          SOME exn => raise exn
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    57
        | NONE =>
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    58
            (case get_first Exn.get_exn results of
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    59
              SOME exn => raise exn
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    60
            | NONE => NONE)))
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    61
  end;
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    62
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    63
fun find_some P = get_some (fn x => if P x then SOME x else NONE);
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    64
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    65
fun exists P = is_some o get_some (fn x => if P x then SOME () else NONE);
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    66
fun forall P = not o exists (not o P);
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    67
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    68
end;