src/HOL/UNITY/Simple/Lift.thy
changeset 36866 426d5781bb25
parent 32960 69916a850301
child 37936 1e4c5015a72e
equal deleted inserted replaced
36865:7330e4eefbd7 36866:426d5781bb25
    16   stop  :: "bool"           --{*whether the lift is stopped at floor*}
    16   stop  :: "bool"           --{*whether the lift is stopped at floor*}
    17   req   :: "int set"        --{*for each floor, whether the lift is requested*}
    17   req   :: "int set"        --{*for each floor, whether the lift is requested*}
    18   up    :: "bool"           --{*current direction of movement*}
    18   up    :: "bool"           --{*current direction of movement*}
    19   move  :: "bool"           --{*whether moving takes precedence over opening*}
    19   move  :: "bool"           --{*whether moving takes precedence over opening*}
    20 
    20 
    21 consts
    21 axiomatization
    22   Min :: "int"       --{*least and greatest floors*}
    22   Min :: "int" and   --{*least and greatest floors*}
    23   Max :: "int"       --{*least and greatest floors*}
    23   Max :: "int"       --{*least and greatest floors*}
    24 
    24 where
    25 axioms
       
    26   Min_le_Max [iff]: "Min \<le> Max"
    25   Min_le_Max [iff]: "Min \<le> Max"
    27   
    26   
    28 constdefs
       
    29   
    27   
    30   --{*Abbreviations: the "always" part*}
    28   --{*Abbreviations: the "always" part*}
    31   
    29   
       
    30 definition
    32   above :: "state set"
    31   above :: "state set"
    33     "above == {s. \<exists>i. floor s < i & i \<le> Max & i \<in> req s}"
    32   where "above = {s. \<exists>i. floor s < i & i \<le> Max & i \<in> req s}"
    34 
    33 
       
    34 definition
    35   below :: "state set"
    35   below :: "state set"
    36     "below == {s. \<exists>i. Min \<le> i & i < floor s & i \<in> req s}"
    36   where "below = {s. \<exists>i. Min \<le> i & i < floor s & i \<in> req s}"
    37 
    37 
       
    38 definition
    38   queueing :: "state set"
    39   queueing :: "state set"
    39     "queueing == above \<union> below"
    40   where "queueing = above \<union> below"
    40 
    41 
       
    42 definition
    41   goingup :: "state set"
    43   goingup :: "state set"
    42     "goingup   == above \<inter> ({s. up s}  \<union> -below)"
    44   where "goingup = above \<inter> ({s. up s}  \<union> -below)"
    43 
    45 
       
    46 definition
    44   goingdown :: "state set"
    47   goingdown :: "state set"
    45     "goingdown == below \<inter> ({s. ~ up s} \<union> -above)"
    48   where "goingdown = below \<inter> ({s. ~ up s} \<union> -above)"
    46 
    49 
       
    50 definition
    47   ready :: "state set"
    51   ready :: "state set"
    48     "ready == {s. stop s & ~ open s & move s}"
    52   where "ready = {s. stop s & ~ open s & move s}"
    49  
    53  
    50   --{*Further abbreviations*}
    54   --{*Further abbreviations*}
    51 
    55 
       
    56 definition
    52   moving :: "state set"
    57   moving :: "state set"
    53     "moving ==  {s. ~ stop s & ~ open s}"
    58   where "moving = {s. ~ stop s & ~ open s}"
    54 
    59 
       
    60 definition
    55   stopped :: "state set"
    61   stopped :: "state set"
    56     "stopped == {s. stop s  & ~ open s & ~ move s}"
    62   where "stopped = {s. stop s  & ~ open s & ~ move s}"
    57 
    63 
       
    64 definition
    58   opened :: "state set"
    65   opened :: "state set"
    59     "opened ==  {s. stop s  &  open s  &  move s}"
    66   where "opened = {s. stop s  &  open s  &  move s}"
    60 
    67 
       
    68 definition
    61   closed :: "state set"  --{*but this is the same as ready!!*}
    69   closed :: "state set"  --{*but this is the same as ready!!*}
    62     "closed ==  {s. stop s  & ~ open s &  move s}"
    70   where "closed = {s. stop s  & ~ open s &  move s}"
    63 
    71 
       
    72 definition
    64   atFloor :: "int => state set"
    73   atFloor :: "int => state set"
    65     "atFloor n ==  {s. floor s = n}"
    74   where "atFloor n = {s. floor s = n}"
    66 
    75 
       
    76 definition
    67   Req :: "int => state set"
    77   Req :: "int => state set"
    68     "Req n ==  {s. n \<in> req s}"
    78   where "Req n = {s. n \<in> req s}"
    69 
    79 
    70 
    80 
    71   
    81   
    72   --{*The program*}
    82   --{*The program*}
    73   
    83   
       
    84 definition
    74   request_act :: "(state*state) set"
    85   request_act :: "(state*state) set"
    75     "request_act == {(s,s'). s' = s (|stop:=True, move:=False|)
    86   where "request_act = {(s,s'). s' = s (|stop:=True, move:=False|)
    76                                   & ~ stop s & floor s \<in> req s}"
    87                                   & ~ stop s & floor s \<in> req s}"
    77 
    88 
       
    89 definition
    78   open_act :: "(state*state) set"
    90   open_act :: "(state*state) set"
    79     "open_act ==
    91   where "open_act =
    80          {(s,s'). s' = s (|open :=True,
    92          {(s,s'). s' = s (|open :=True,
    81                            req  := req s - {floor s},
    93                            req  := req s - {floor s},
    82                            move := True|)
    94                            move := True|)
    83                        & stop s & ~ open s & floor s \<in> req s
    95                        & stop s & ~ open s & floor s \<in> req s
    84                        & ~(move s & s \<in> queueing)}"
    96                        & ~(move s & s \<in> queueing)}"
    85 
    97 
       
    98 definition
    86   close_act :: "(state*state) set"
    99   close_act :: "(state*state) set"
    87     "close_act == {(s,s'). s' = s (|open := False|) & open s}"
   100   where "close_act = {(s,s'). s' = s (|open := False|) & open s}"
    88 
   101 
       
   102 definition
    89   req_up :: "(state*state) set"
   103   req_up :: "(state*state) set"
    90     "req_up ==
   104   where "req_up =
    91          {(s,s'). s' = s (|stop  :=False,
   105          {(s,s'). s' = s (|stop  :=False,
    92                            floor := floor s + 1,
   106                            floor := floor s + 1,
    93                            up    := True|)
   107                            up    := True|)
    94                        & s \<in> (ready \<inter> goingup)}"
   108                        & s \<in> (ready \<inter> goingup)}"
    95 
   109 
       
   110 definition
    96   req_down :: "(state*state) set"
   111   req_down :: "(state*state) set"
    97     "req_down ==
   112   where "req_down =
    98          {(s,s'). s' = s (|stop  :=False,
   113          {(s,s'). s' = s (|stop  :=False,
    99                            floor := floor s - 1,
   114                            floor := floor s - 1,
   100                            up    := False|)
   115                            up    := False|)
   101                        & s \<in> (ready \<inter> goingdown)}"
   116                        & s \<in> (ready \<inter> goingdown)}"
   102 
   117 
       
   118 definition
   103   move_up :: "(state*state) set"
   119   move_up :: "(state*state) set"
   104     "move_up ==
   120   where "move_up =
   105          {(s,s'). s' = s (|floor := floor s + 1|)
   121          {(s,s'). s' = s (|floor := floor s + 1|)
   106                        & ~ stop s & up s & floor s \<notin> req s}"
   122                        & ~ stop s & up s & floor s \<notin> req s}"
   107 
   123 
       
   124 definition
   108   move_down :: "(state*state) set"
   125   move_down :: "(state*state) set"
   109     "move_down ==
   126   where "move_down =
   110          {(s,s'). s' = s (|floor := floor s - 1|)
   127          {(s,s'). s' = s (|floor := floor s - 1|)
   111                        & ~ stop s & ~ up s & floor s \<notin> req s}"
   128                        & ~ stop s & ~ up s & floor s \<notin> req s}"
   112 
   129 
       
   130 definition
   113   button_press  :: "(state*state) set"
   131   button_press  :: "(state*state) set"
   114       --{*This action is omitted from prior treatments, which therefore are
   132       --{*This action is omitted from prior treatments, which therefore are
   115         unrealistic: nobody asks the lift to do anything!  But adding this
   133         unrealistic: nobody asks the lift to do anything!  But adding this
   116         action invalidates many of the existing progress arguments: various
   134         action invalidates many of the existing progress arguments: various
   117         "ensures" properties fail. Maybe it should be constrained to only
   135         "ensures" properties fail. Maybe it should be constrained to only
   118         allow button presses in the current direction of travel, like in a
   136         allow button presses in the current direction of travel, like in a
   119         real lift.*}
   137         real lift.*}
   120     "button_press ==
   138   where "button_press =
   121          {(s,s'). \<exists>n. s' = s (|req := insert n (req s)|)
   139          {(s,s'). \<exists>n. s' = s (|req := insert n (req s)|)
   122                         & Min \<le> n & n \<le> Max}"
   140                         & Min \<le> n & n \<le> Max}"
   123 
   141 
   124 
   142 
       
   143 definition
   125   Lift :: "state program"
   144   Lift :: "state program"
   126     --{*for the moment, we OMIT @{text button_press}*}
   145     --{*for the moment, we OMIT @{text button_press}*}
   127     "Lift == mk_total_program
   146   where "Lift = mk_total_program
   128                 ({s. floor s = Min & ~ up s & move s & stop s &
   147                 ({s. floor s = Min & ~ up s & move s & stop s &
   129                           ~ open s & req s = {}},
   148                           ~ open s & req s = {}},
   130                  {request_act, open_act, close_act,
   149                  {request_act, open_act, close_act,
   131                   req_up, req_down, move_up, move_down},
   150                   req_up, req_down, move_up, move_down},
   132                  UNIV)"
   151                  UNIV)"
   133 
   152 
   134 
   153 
   135   --{*Invariants*}
   154   --{*Invariants*}
   136 
   155 
       
   156 definition
   137   bounded :: "state set"
   157   bounded :: "state set"
   138     "bounded == {s. Min \<le> floor s & floor s \<le> Max}"
   158   where "bounded = {s. Min \<le> floor s & floor s \<le> Max}"
   139 
   159 
       
   160 definition
   140   open_stop :: "state set"
   161   open_stop :: "state set"
   141     "open_stop == {s. open s --> stop s}"
   162   where "open_stop = {s. open s --> stop s}"
   142   
   163   
       
   164 definition
   143   open_move :: "state set"
   165   open_move :: "state set"
   144     "open_move == {s. open s --> move s}"
   166   where "open_move = {s. open s --> move s}"
   145   
   167   
       
   168 definition
   146   stop_floor :: "state set"
   169   stop_floor :: "state set"
   147     "stop_floor == {s. stop s & ~ move s --> floor s \<in> req s}"
   170   where "stop_floor = {s. stop s & ~ move s --> floor s \<in> req s}"
   148   
   171   
       
   172 definition
   149   moving_up :: "state set"
   173   moving_up :: "state set"
   150     "moving_up == {s. ~ stop s & up s -->
   174   where "moving_up = {s. ~ stop s & up s -->
   151                    (\<exists>f. floor s \<le> f & f \<le> Max & f \<in> req s)}"
   175                    (\<exists>f. floor s \<le> f & f \<le> Max & f \<in> req s)}"
   152   
   176   
       
   177 definition
   153   moving_down :: "state set"
   178   moving_down :: "state set"
   154     "moving_down == {s. ~ stop s & ~ up s -->
   179   where "moving_down = {s. ~ stop s & ~ up s -->
   155                      (\<exists>f. Min \<le> f & f \<le> floor s & f \<in> req s)}"
   180                      (\<exists>f. Min \<le> f & f \<le> floor s & f \<in> req s)}"
   156   
   181   
       
   182 definition
   157   metric :: "[int,state] => int"
   183   metric :: "[int,state] => int"
   158     "metric ==
   184   where "metric =
   159        %n s. if floor s < n then (if up s then n - floor s
   185        (%n s. if floor s < n then (if up s then n - floor s
   160                                   else (floor s - Min) + (n-Min))
   186                                   else (floor s - Min) + (n-Min))
   161              else
   187              else
   162              if n < floor s then (if up s then (Max - floor s) + (Max-n)
   188              if n < floor s then (if up s then (Max - floor s) + (Max-n)
   163                                   else floor s - n)
   189                                   else floor s - n)
   164              else 0"
   190              else 0)"
   165 
   191 
   166 locale Floor =
   192 locale Floor =
   167   fixes n
   193   fixes n
   168   assumes Min_le_n [iff]: "Min \<le> n"
   194   assumes Min_le_n [iff]: "Min \<le> n"
   169       and n_le_Max [iff]: "n \<le> Max"
   195       and n_le_Max [iff]: "n \<le> Max"