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
|
implementation module DTMC
import StdArray
import StdBool
import StdClass
import StdFile
from StdFunc import o
import StdInt
import StdList
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
import Data.Maybe
import System.File
import System.FilePath
import Text
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]
Start w
# (dtmc,w) = parseDTMC "die.drn" w
= [(s.state_id, 'M'.toList s.transitions, '\n') \\ Just s <-: (stateElimination dtmc).states]
|
