-
Notifications
You must be signed in to change notification settings - Fork 16
/
state.theory.txt
283 lines (239 loc) · 20.7 KB
/
state.theory.txt
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
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
STATE
/=+===============================+=\
/ : : \
)==: PARADIGMS :==(
\ :_______________________________: /
\=+===============================+=/
IMPERATIVE VS FUNCTIONAL ==> #Imperative programming emphasizes state manipulation
# - pros:
# - more flexible
# - more efficient
#Functional programming emphasizes referential transparency
# - pros:
# - easier to reason with:
# - for programmers
# - for static analysis, e.g. easier to test
# - easier to optimize
# - usually corrolated with declarative programming
REFERENTIAL TRANSPARENCY ==> #Also called "purity".
#Function that can be replaced by its return value, i.e.:
# - does not cause side effects
# - does not depend on state outside its arguments (i.e. local scope)
IDEMPOTENCY ==> #Function that can be called twice without state change, i.e.:
# - side effect always result in same state (including no side effects)
# - does not depend on state outside its arguments (i.e. local scope)
#Goal: duplicated calls (e.g. retries) are not a problem, i.e. no need to keep state about previous calls
SIDE EFFECT ==> #When state changes after a function has been fired, including:
# - changing caller state:
# - arguments passed by reference
# - global scope
# - changing closure state
# - changing control flow, e.g. jumping, including raising exception
#Usually execution time is not considered side effect
#Statement (causes side effects) vs expression (no side effects)
#Alternative to causing side effect (when flexibility is needed, e.g. I/O): returning state|action object to caller
/=+===============================+=\
/ : : \
)==: STRUCTURES :==(
\ :_______________________________: /
\=+===============================+=/
CLOSURE ==> #Function holding state accross executions thanks to lexical scope binding
COROUTINE ==> #Function that holds state accross executions, including where it left off:
# - run until explicit yield
# - jump to any function (instead of returning to caller)
# - when called again, restart at yield point
GENERATOR|SEMICOROUTINE ==> #Coroutine that only jumps back to caller when yielding, usually returning value
#Usually meant for iterators or streams
PERSISTENT DATA STRUCTURE ==> #Data structure that can be easily immutably updated, i.e. efficiently create a clone
#with new value while keeping old value as is.
#Can be:
# - "partially persistent": only newest version can be updated
# - "fully persistent": any version can be modified
# - "confluently persistent": can create value by merging two previous versions
# - "purely functional": when does not depend on global state
# - "retroactive": modifying an old version updates new ones
# - "partially" vs "fully retroactive": whether only newest version can be queried
#Opposite is "ephemeral data structure".
#Implementations (for any graph-based structure):
# - "fat node":
# - each node maintains its own version tree, i.e. list of old values
# - time complexity:
# - accessing old value: O(m * log n) (finding version in version tree, for each node)
# - adding new value: O(1) for partially persistent, O(log n) for fully persistent
# - space complexity: O(1) (no waste)
# - "path copying":
# - new values can point to old values, as long as it includes old values descendants
# - each new version must have its own root
# - all roots|versions are kept in an array
# - time complexity:
# - accessing old value: O(log n) (finding version in array, for all nodes)
# - adding new value: O(n) (figuring out which value to point to or copy)
# - space complexity: O(n) (some nodes might need to be copied)
#Examples:
# - easy to persist: linked lists, trees, stacks
# - harder to persist: queues, dequeues, hash maps, heap
ZIPPERS ==> #Way of making a tree a persistent data structure.
#It is conceptually similar to a gap buffer but for a tree:
# - a node and its descendants is marked as current "focus"
# - rest is the "context"
#Updating the focus subtree can be done by replacing it but re-using reference to the context subtree
#Also:
# - the context broken down into left|right context subtrees, according to whether it is a
# right|left child of its parent
# - breaking it down allows sharing references even if the tree gets updated
# - the path from root to focus node is kept, so that left|right context subtrees can be
# re-concatenated to focus subtree
#Idea can be also applied to other recursive data structures, such as lists,
#especially cons lists.
/=+===============================+=\
/ : : \
)==: SERIALIZATION :==(
\ :_______________________________: /
\=+===============================+=/
SERIALIZATION ==> #Representing state as data
MEMENTO ==> #Serialization allows retrieving full state while remaining minimal
#Does it by separating:
# - serialized object ("memento"), kept minimal, e.g. just an ID
# - object to serialize is "originator"
# - "caretaker" keeping track of full states, e.g. hash table with ID as key
#Goal: serializing while keeping information hiding, i.e. abstracting serialization away
BUILDER ==> #Initializing serialized objects:
# - a "reader" and "writer" deserialize|serialize an object
# - a "builder" initializes the deserialized object
# - it can be an abstract factory
#Can only read and build one part after another
#Goal: separating object representation from initialization
/=+===============================+=\
/ : : \
)==: CONTROL FLOW :==(
\ :_______________________________: /
\=+===============================+=/
BRANCH ==> #Instruction that jumps to another instruction
#Also called "goto" or "jump"
CONDITIONAL BRANCH ==> #Branch executed only if a test passes.
#Opposite is "unconditional branch"
PREDICATIONAL BRANCH ==> #Branch always evaluated, but only modifying state if a test passes
#Alternative to conditional branches.
#Uses to perform speculative execution.
MULTIWAY BRANCHING ==> #Conditional branching where one branch among several is picked using a key.
#Can be implemented:
# - imperatively:
# - sometimes developer-friendly
# - logical if/then/else statements
# - switch statement:
# - often has a default case
# - can be:
# - "structured": each case is isolated
# - "unstructured": "falls through" next cases
# - structured programming
# - declaratively:
# - more efficient
# - an associative map with the branch logic as values
# - pattern matching:
# - like an associative map with branch logic as values except:
# - keys can be FUNC(VAL)->BOOL or derived (e.g. regexps)
# - arithmetic if statement:
# - if (NUM) EXPR,EXPR2,EXPR3, where EXPR if NUM<0, EXPR2 if NUM == 0, EXPR3 if NUM>0
STRUCTURED PROGRAMMING ==> #Which control flows are used by imperative languages
#Non-structured programming:
# - use branching:
# - unconditional (goto, call, exit, etc.)
# - conditional (conditional jump, etc.)
# - includes:
# - early exit (return, break, continue, etc.)
# - exception|interrupt handling
# - async (coroutine, promise, etc.)
#Structured programming:
# - use structures:
# - blocks (if blocks, switch, etc.)
# - loops (for, while, etc.)
# - functions
#Structures are an abstraction of branching, aiming at grouping related code together, i.e. more cohesion
SPAGHETTI CODE ==> #Antipattern: code flow lacking linearity, i.e. jump from one part to another frequently
#Usually because of low cohesion but high granularity
CONTROL TABLE ==> #Associative map used for multiway branching, where values are functions, function pointers
#or jumps.
#Also called "decision table"
#Can be a multimap, i.e. values can be multiple functions.
#Branching using multiple indirection (as in control tables) is "indirect branching"
#Can use an index map, in which case it is called:
# - "branch table": when values are jumps
# - "dispatch table": when values are functions or function pointers
#Associative map can be single-dimensional or multiple-dimensional.
[FINITE-]STATE MACHINE/AUTOMATON #"FSM"/"FSA"
==> #Control flow where:
# - all state lies in one object
# - e.g. Turing machines are not state machines, since:
# - the array of values contains state (that can be read|written)
# - not only the current "state" variable and head position
# - each state variation triggers different branch
# - trigger can take input ("Mealy machine") or not ("Moore machine")
# - each state change ("transition") jumps back to initial point
# - when on a given state, state can change to:
# - only one other possible state ("deterministic"/DFA)
# - if acyclic, called DAFSA or "directed acycled word graph" (DAWG)
# - only 0-n possible states ("non-deterministic"/NFA)
#Types:
# - acceptors (also called "recognizers", "sequence detectors"):
# - goal is to check whether sequence of inputs ends up in a given state ("accepting|final" state)
# - i.e. modelling FUNC(...)->BOOL as a state machine
# - e.g. RegExp
# - classifier:
# - like acceptor, but there are several possible final state
# - i.e. modelling FUNC(...)->VAL (among ENUM) as a state machine
# - transducer (FST):
# - has a second state, which is output
STATE PATTERN ==> #Using polymorphism to implement a state machine:
# - a "context" has state-agnostic logic
# - a "state object" has several polymorphic implementations representing state-speicific
# logic of the same methods
# - it is called by, and switched, by the "context"
/=+===============================+=\
/ : : \
)==: TURING MACHINE :==(
\ :_______________________________: /
\=+===============================+=/
TURING MACHINE ==> #Theorical simplistic machine representing anything a computer (or any automated computation) can do.
#Input:
# - possible values ("symbols") are a finite set
# - input is array of symbols:
# - can be of infinite size, but only null ("blank" symbol) can appear infinitely
#State:
# - possible states are a finite set, which includes:
# - start state
# - end states (halt), which can include any not enumerated ones
# - current STATE is among possible ones
# - must include current position HEAD:
# - inside array of values, i.e. which one is current value
#Instruction:
# - FUNC(STATE, INPUT)->(WRITE_SYMBOL, MOVE_OFFSET, NEW_STATE)
# - WRITE_SYMBOL: write some value back
# - MOVE_OFFSET: adds -1|0|1 to HEAD
# - in 4-tuple model can either do WRITE or MOVE, in 5-tuple can do both
# - often represented as table of tuples, e.g. (STATE, INPUT, WRITE_SYMBOL, MOVE_OFFSET, NEW_STATE)
#Execution:
# - reads current value as current INPUT
# - using table of instructions:
# - performs INSTRUCTION
# - changes to NEW_STATE
UNIVERSAL TURING MACHINE ==> #Turing machine which gets its table of instructions as input:
# - e.g. code is data ("stored program computer")
# - architecture where code can be treated as data, and data can be treated as code:
# - Von Neumann architecture: same memory for both
# - Harvard architecture: different memory
ALTERNATE TURING MACHINES ==> #"Turing equivalent", i.e. not more powerful than normal Turing machine, i.e.:
# - cannot express more but can:
# - have more expressive instructions
# - use less memory
# - use less instructions
# - could be refactored as a normal Turing maching
/=+===============================+=\
/ : : \
)==: ARCHITECTURE :==(
\ :_______________________________: /
\=+===============================+=/
OBSERVER PATTERN ==> #When a module ("view|observer") must be kept in sync with another module ("model|subject") state
#Separate the two by using change events