1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
|
implementation module DTMC
import StdArray
import StdBool
import StdClass
import StdFile
from StdFunc import o
import StdInt
import StdList
from StdMisc import abort
import StdString
import StdTuple
import Data.Error
from Data.Func import $, mapSt, seqSt
import Data.List
import qualified Data.Map as M
from Data.Map import :: Map, alter
import Data.Maybe
import System.CommandLine
import System.File
import System.FilePath
import Text
import Expression
import Z3
paths :: !*DTMC -> *([[Int]], !*DTMC)
paths dtmc=:{nr_states,states}
# (inits,states) = getInitStates (nr_states-1) states
# (ps,states) = mapSt (paths` []) inits states
= (flatten ps, {dtmc & states=states})
where
getInitStates :: !Int !*{Maybe State} -> *(![Int], !*{Maybe State})
getInitStates i ss
| i < 0 = ([], ss)
# (s,ss) = ss![i]
| isNothing s = ([], ss)
# s = fromJust s
| s.init
# (inits,ss) = getInitStates (i-1) ss
= ([i:inits],ss)
= getInitStates (i-1) ss
paths` :: ![Int] !Int !*{Maybe State} -> *(![[Int]], !*{Maybe State})
paths` seen cur ss
| isMember cur seen = ([], ss)
# (s,ss) = ss![cur]
| isNothing s = ([], ss)
# s = fromJust s
| isAbsorbing s = ([[cur]], ss)
# succ = 'M'.keys s.transitions
# (pss,ss) = mapSt (paths` [cur:seen]) succ ss
= ([[cur:p] \\ ps <- pss, p <- ps], ss)
stateElimination :: !*DTMC -> *DTMC
stateElimination dtmc=:{nr_states}
# (ps,dtmc) = paths dtmc
= case [p \\ p=:[_:_:_:_] <- ps] of
[] -> {dtmc & states=prune (nr_states-1) dtmc.states}
[p:_] -> stateElimination {dtmc & states=uncurry elim (penultimate_trans p) dtmc.states}
with
penultimate_trans [x,y,_] = (x,y)
penultimate_trans [_:xs] = penultimate_trans xs
where
prune :: !Int !*{Maybe State} -> *{Maybe State}
prune i ss
| i < 0 = ss
# (Just s,ss) = ss![i]
| s.init || isAbsorbing s = prune (i-1) ss
| otherwise = prune (i-1) $ remove i (nr_states-1) ss
where
remove :: !Int !Int !*{Maybe State} -> *{Maybe State}
remove i j ss
| j < 0 = {ss & [i]=Nothing}
# (s,ss) = ss![j]
| isNothing s = remove i (j-1) ss
# s = fromJust s
= remove i (j-1) ss
elim :: !Int !Int !*{Maybe State} -> *{Maybe State}
elim s1 s ss
# (Just s1s,ss) = ss![s1]
# prob = 'M'.get s s1s.transitions
# (succ,ss) = ss![s]
| isNothing succ = ss
# succ = fromJust succ
| succ.init || isAbsorbing succ = ss
# succ = succ.transitions
# self_prob = fromMaybe "0" $ 'M'.get s succ
# succ = 'M'.toList succ
| s1 == s
# ss = seqSt (uncurry $ update_eq self_prob) succ ss
# (Just s1s,ss) = ss![s1]
# ss & [s1] = Just {s1s & transitions='M'.del s s1s.transitions}
= ss
| otherwise
# ss = seqSt (uncurry $ update_ne self_prob) succ ss
# (Just s1s,ss) = ss![s1]
# ss & [s1] = Just {s1s & transitions='M'.del s s1s.transitions}
= ss
where
update_eq :: !String !Int !String !*{Maybe State} -> *{Maybe State}
update_eq self_prob s2 prob2 ss
| s == s2 = ss
# (Just s1s,ss) = ss![s1]
# ss & [s1] = Just
{ s1s
& transitions = 'M'.put s2
("(" +++ prob2 +++ ")/(1-(" +++ self_prob +++ "))")
s1s.transitions
}
= ss
update_ne :: !String !Int !String !*{Maybe State} -> *{Maybe State}
update_ne self_prob s2 prob2 ss
| s == s2 = ss
# (Just s1s,ss) = ss![s1]
# ps1s2 = fromMaybe "0" $ 'M'.get s2 s1s.transitions
# ps1s = fromMaybe "0" $ 'M'.get s s1s.transitions
# ss & [s1] = Just
{ s1s
& transitions = 'M'.put s2
(ps1s2 +++ "+(" +++ ps1s +++ ")*(" +++ prob2 +++ ")/(1-(" +++ self_prob +++ "))")
s1s.transitions
}
= ss
isAbsorbing :: !State -> Bool
isAbsorbing s = all ((==) s.state_id) [to \\ (to,_) <- 'M'.toList s.transitions]
parseDTMC :: !FilePath !*World -> *(!DTMC, !*World)
parseDTMC fp w
# (lines,w) = readFileLines fp w
= (parseDTMCFromLines [s % (0,size s-2) \\ s <- fromOk lines], w)
parseDTMCFromLines :: ![String] -> DTMC
parseDTMCFromLines lines
# [nr_states:_:lines] = tl $ dropWhile ((<>) "@nr_states") lines
# states = map parseState $ groupLines "\t" [] lines
=
{ nr_states = toInt nr_states
, states = {Just s \\ s <- states}
}
where
parseState :: ![String] -> State
parseState [head:actions] =
{ state_id = toInt $ trim $ head % (5,size head-1)
, transitions = 'M'.unions $ map (snd o parseAction) $ groupLines "\t\t" [] actions
, init = endsWith "init" head
}
where
parseAction :: ![String] -> (!Int, !Map Int String)
parseAction [head:transitions] =
( toInt (head % (8, size head-1))
, 'M'.fromList $ map parseTransition transitions
)
where
parseTransition :: !String -> (!Int, !String)
parseTransition s = case split " : " (trim s) of
[id:prob:_] -> (toInt id, prob)
groupLines :: !String ![String] ![String] -> [[String]]
groupLines head current [] = [reverse current]
groupLines head current [line:lines]
| startsWith head line = groupLines head [line:current] lines
| isEmpty current = groupLines head [line] lines
| otherwise = [reverse current:groupLines head [line] lines]
printDTMC :: !*DTMC -> *(!String, !*DTMC)
printDTMC dtmc=:{nr_states,states}
# (state_strings,states) = printStates 0 states
# s = join "\n"
[ "@type: DTMC"
, "@parameters\n"
, "@reward_models\n"
, "@nr_states"
, toString nr_states
, "@model"
: state_strings
]
= (s, {dtmc & states=states})
where
printStates :: !Int !*{Maybe State} -> *(![String], !*{Maybe State})
printStates i ss
| i == nr_states = ([], ss)
# (s,ss) = ss![i]
| isNothing s = printStates (i+1) ss
# s = fromJust s
# repr =
[ "state " <+ s.state_id
, "\taction 0"
: ["\t\t" <+ to <+ " : " <+ prob \\ (to,prob) <- 'M'.toList s.transitions]
]
# (reprs,ss) = printStates (i+1) ss
= (repr ++ reprs,ss)
addVars :: *DTMC -> *DTMC
addVars dtmc = {DTMC | nr_states = dtmc.nr_states, states = addVarsS 0 dtmc.nr_states dtmc.states}
where
addVarsS :: !Int !Int !*{Maybe State} -> *{Maybe State}
addVarsS fi m ss
| fi >= m = ss
| otherwise = addVarsS (fi + 1) m (addVarsT fi 0 m ss)
addVarsT :: !Int !Int !Int !*{Maybe State} -> *{Maybe State}
addVarsT fi ti m ss
| ti >= m = ss
# (s, ss) = ss![fi]
= case s of
Nothing -> ss
(Just s) -> addVarsT fi (ti + 1) m {ss & [fi] = Just {s & transitions = alter (addVar fi ti) ti s.transitions}}
addVar :: Int Int (Maybe String) -> Maybe String
addVar _ _ Nothing = Nothing
addVar f t (Just fn) = Just ("((" <+ fn <+ ") + v" <+ f <+ "_" <+ t <+ ")")
findInitial :: !*DTMC -> (!State, !*DTMC)
findInitial dtmc=:{nr_states,states}
# (init,states) = findInitial` (nr_states-1) states
# dtmc & states = states
= (init, dtmc)
where
findInitial` :: !Int !*{Maybe State} -> *(!State, !*{Maybe State})
findInitial` i states
| i < 0 = abort "No initial state"
# (state, states) = states![i]
| isJust state && (fromJust state).init = (fromJust state, states)
| otherwise = findInitial` (i - 1) states
assertProperty :: !Property !*DTMC !Z3 !*World -> (*DTMC, *World)
assertProperty (prob, target) dtmc z3 w
# (init, dtmc) = findInitial dtmc
# formula = 'M'.get target init.transitions
| isNothing formula = abort "Cannot reach property target from initial state"
# formula = fromJust formula
# formula = "(= (" <+ prob <+ ") (" <+ parseInfix formula <+ "))"
# w = addAssert z3 formula w
= (dtmc, w)
Start w
# ([prog:args],w) = getCommandLine w
| length args <> 2
# (io,w) = stdio w
# io = io <<< "Usage: " <<< prog <<< " DRN_IN DRN_OUT\n"
# (_,w) = fclose io w
= w
# [drn_in,drn_out:_] = args
# (dtmc,w) = parseDTMC drn_in w
# dtmc = addVars dtmc
# dtmc = stateElimination dtmc
# (z3,w) = startZ3 w
# (dtmc,w) = assertProperty prop dtmc z3 w
//# (dtmcs,dtmc) = printDTMC dtmc
//# (_,w) = writeFile drn_out dtmcs w
= w
where
prop :: Property
prop = (0.5, 7) // Chance to reach state 7 is 0.5
|
