CookBook/Recipes/TimeLimit.thy
author Christian Urban <urbanc@in.tum.de>
Thu, 08 Jan 2009 22:46:06 +0000
changeset 63 83cea5dc6bac
parent 61 64c9540f2f84
child 67 5fbeeac2901b
permissions -rw-r--r--
tuned
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
61
64c9540f2f84 Added four recipes.
boehmes
parents:
diff changeset
     1
theory TimeLimit
63
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
     2
imports "../Base"
61
64c9540f2f84 Added four recipes.
boehmes
parents:
diff changeset
     3
begin
64c9540f2f84 Added four recipes.
boehmes
parents:
diff changeset
     4
64c9540f2f84 Added four recipes.
boehmes
parents:
diff changeset
     5
section {* Restricting the Runtime of a Function *} 
64c9540f2f84 Added four recipes.
boehmes
parents:
diff changeset
     6
64c9540f2f84 Added four recipes.
boehmes
parents:
diff changeset
     7
text {*
64c9540f2f84 Added four recipes.
boehmes
parents:
diff changeset
     8
  {\bf Problem:}
63
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
     9
  Your tool should run only a specified amount of time.\smallskip
61
64c9540f2f84 Added four recipes.
boehmes
parents:
diff changeset
    10
63
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    11
  {\bf Solution:} This can be achieved using the function 
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    12
  @{ML timeLimit in TimeLimit}.\smallskip
61
64c9540f2f84 Added four recipes.
boehmes
parents:
diff changeset
    13
63
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    14
  Assume the following well-known function:
61
64c9540f2f84 Added four recipes.
boehmes
parents:
diff changeset
    15
64c9540f2f84 Added four recipes.
boehmes
parents:
diff changeset
    16
  *}
64c9540f2f84 Added four recipes.
boehmes
parents:
diff changeset
    17
63
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    18
ML {* 
61
64c9540f2f84 Added four recipes.
boehmes
parents:
diff changeset
    19
fun ackermann (0, n) = n + 1
64c9540f2f84 Added four recipes.
boehmes
parents:
diff changeset
    20
  | ackermann (m, 0) = ackermann (m - 1, 1)
64c9540f2f84 Added four recipes.
boehmes
parents:
diff changeset
    21
  | ackermann (m, n) = ackermann (m - 1, ackermann (m, n - 1))
64c9540f2f84 Added four recipes.
boehmes
parents:
diff changeset
    22
*}
64c9540f2f84 Added four recipes.
boehmes
parents:
diff changeset
    23
63
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    24
text {*
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    25
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    26
  Now the call 
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    27
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    28
  @{ML_response_fake [display] "ackermann (4, 12)" "\<dots>"}
61
64c9540f2f84 Added four recipes.
boehmes
parents:
diff changeset
    29
63
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    30
  takes a bit long. To avoid this, the call can be encapsulated 
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    31
  in a time limit of five seconds. For this you have to write:
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    32
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    33
@{ML_response [display]
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    34
"TimeLimit.timeLimit (Time.fromSeconds 5) ackermann (4, 12) 
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    35
  handle TimeOut => ~1"
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    36
"~1"}
61
64c9540f2f84 Added four recipes.
boehmes
parents:
diff changeset
    37
63
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    38
  where @{ML_text TimeOut} is the exception raised when the time limit
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    39
  is reached.
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    40
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    41
  Note that @{ML  "timeLimit" in TimeLimit} is only meaningful when you use PolyML, 
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    42
  because PolyML has a rich infrastructure for multithreading programming on 
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    43
  which @{ML "timeLimit" in TimeLimit} relies.
61
64c9540f2f84 Added four recipes.
boehmes
parents:
diff changeset
    44
63
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    45
\begin{readmore}
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    46
   The function @{ML "timeLimit" in TimeLimit} is defined in the structure
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    47
  @{ML_struct TimeLimit} which can be found in the file 
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    48
  @{ML_file "Pure/ML-Systems/multithreading_polyml.ML"}.
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    49
\end{readmore}
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    50
Christian Urban <urbanc@in.tum.de>
parents: 61
diff changeset
    51
 
61
64c9540f2f84 Added four recipes.
boehmes
parents:
diff changeset
    52
*}
64c9540f2f84 Added four recipes.
boehmes
parents:
diff changeset
    53
64c9540f2f84 Added four recipes.
boehmes
parents:
diff changeset
    54
end