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
|
package subex
import (
"main/walk"
)
type Transducer struct {
storeSize int
initialState SubexState
}
type StoreItem struct {}
// Where slots are stored
type Store [][]walk.Atom
// Return a new store with all the data from this one
func (store Store) clone() Store {
newStore := make([][]walk.Atom, len(store))
copy(newStore, store)
return newStore
}
// Return a copy of this store but with an additional slot set
func (store Store) withValue(key int, value []walk.Atom) Store {
newStore := store.clone()
newStore[key] = value
return newStore
}
type SlotMap struct {
nextId int
ids map[rune]int
}
func (m *SlotMap) getId(slot rune) int {
id, exists := m.ids[slot]
if exists {
return id
}
id = m.nextId
m.nextId++
m.ids[slot] = id
return id
}
// Compile the SubexAST into a transducer SubexState that can be run
func CompileTransducer(transducerAst SubexAST) Transducer {
slotMap := SlotMap {
nextId: 0,
ids: make(map[rune]int),
}
initial := transducerAst.compileWith(&SubexNoneState{}, &slotMap)
return Transducer {
storeSize: slotMap.nextId,
initialState: initial,
}
}
// An immutable stack for outputting to
type OutputStack struct {
head []walk.Atom
tail *OutputStack
}
func (stack OutputStack) pop() ([]walk.Atom, OutputStack) {
return stack.head, *stack.tail
}
func (stack OutputStack) push(atoms []walk.Atom) OutputStack {
return OutputStack {
head: atoms,
tail: &stack,
}
}
func (stack OutputStack) replace(atoms []walk.Atom) OutputStack {
return OutputStack {
head: atoms,
tail: stack.tail,
}
}
func (stack OutputStack) peek() []walk.Atom {
return stack.head
}
func topAppend(outputStack OutputStack, atoms []walk.Atom) OutputStack {
head := outputStack.peek()
return outputStack.replace(walk.ConcatData(head, atoms))
}
// One branch of subex execution
type SubexBranch struct {
// Content of slots in this branch
store Store
// State in this branch
state SubexState
// The output stack. At the end of the program, whatever is on top of this will be output
// States may push or pop to the stack as they wish, creating sort of a call stack that allows states to capture the output of other states
outputStack OutputStack
}
// Read a single character and return all the branches resulting from this branch consuming it
func (pair SubexBranch) eat(char walk.Atom) []SubexBranch {
return pair.state.eat(pair.store, pair.outputStack, char)
}
func (pair SubexBranch) accepting() []OutputStack {
return pair.state.accepting(pair.store, pair.outputStack)
}
func equalStates(left SubexBranch, right SubexBranch) bool {
// Only care about if they are the same pointer
return left.state == right.state
}
// If two branches have the same state, only the first has a chance of being successful
// This function removes all of the pointless execution branches to save execution time
func pruneStates(states []SubexBranch) []SubexBranch {
uniqueStates := 0
outer: for _, state := range states {
for i := 0; i < uniqueStates; i++ {
if equalStates(state, states[i]) {
continue outer
}
}
states[uniqueStates] = state
uniqueStates++
}
return states[:uniqueStates]
}
// Run the subex transducer
func RunTransducer(transducer Transducer, input []walk.Atom) (output []walk.Atom, err bool) {
states := []SubexBranch{{
state: transducer.initialState,
outputStack: OutputStack {
head: nil,
tail: nil,
},
store: make([][]walk.Atom, transducer.storeSize),
}}
var tmp []SubexBranch
newStates := make([]SubexBranch, 0, 2)
for _, piece := range input {
for _, state := range states {
newStates = append(newStates, state.eat(piece)...)
}
tmp = states
states = pruneStates(newStates)
newStates = tmp[:0]
if len(states) == 0 {
return nil, true
}
}
for _, state := range states {
acceptingStacks := state.accepting()
for _, stack := range acceptingStacks {
output := stack.head
return output, false
}
}
return nil, true
}
|
