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
|
package subex
import (
"os"
"fmt"
"bufio"
"main/walk"
)
// Where slots are stored
type Store map[rune][]walk.Atom
// Return a new store with all the data from this one
func (store Store) clone() Store {
newStore := make(Store)
for key, val := range store {
newStore[key] = val
}
return newStore
}
// Return a copy of this store but with an additional slot set
func (store Store) withValue(key rune, value []walk.Atom) Store {
newStore := store.clone()
newStore[key] = value
return newStore
}
// Compile the SubexAST into a transducer SubexState that can be run
func CompileTransducer(transducerAst SubexAST) SubexState {
return transducerAst.compileWith(&SubexNoneState{})
}
// An immutable stack for outputting to
type OutputStack interface {
pop() ([]walk.Atom, OutputStack)
push(atoms []walk.Atom) OutputStack
}
type OutputStackNil struct {}
func (stack OutputStackNil) pop() ([]walk.Atom, OutputStack) {
panic("Tried to pop from an empty OutputStack")
}
func (stack OutputStackNil) push(atoms []walk.Atom) OutputStack {
return &OutputStackCons {
head: atoms,
tail: stack,
}
}
type OutputStackCons struct {
head []walk.Atom
tail OutputStack
}
func (stack OutputStackCons) pop() ([]walk.Atom, OutputStack) {
return stack.head, stack.tail
}
func (stack OutputStackCons) push(atoms []walk.Atom) OutputStack {
return &OutputStackCons {
head: atoms,
tail: stack,
}
}
func topAppend(outputStack OutputStack, atoms []walk.Atom) OutputStack {
head, tail := outputStack.pop()
return tail.push(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) (newStates []SubexBranch) {
outer: for _, state := range states {
for _, newState := range newStates {
if equalStates(state, newState) {
continue outer
}
}
newStates = append(newStates, state)
}
return newStates
}
// Run the subex transducer
func RunTransducer(transducer SubexState, input <-chan walk.Atom) (output []walk.Atom, err bool) {
states := []SubexBranch{{
state: transducer,
outputStack: OutputStackNil{}.push(nil),
store: make(Store),
}}
for piece := range input {
var newStates []SubexBranch
for _, state := range states {
newStates = append(newStates, state.eat(piece)...)
}
states = pruneStates(newStates)
}
for _, state := range states {
acceptingStacks := state.accepting()
for _, stack := range acceptingStacks {
output, _ := stack.pop()
return output, false
}
}
return nil, true
}
func Main() {
if len(os.Args) != 2 {
panic("Expected: program [subex]")
}
program := os.Args[1]
reader := &StringRuneReader {
input: program,
pos: 0,
width: 0,
}
ast := Parse(reader)
transducer := CompileTransducer(ast)
stdin := bufio.NewReader(os.Stdin);
jsonStream := walk.Json(stdin);
tokenStream := make(chan walk.WalkValue)
go func(in <-chan walk.WalkItem, out chan<- walk.WalkValue) {
for item := range in {
out<-item.Value
}
close(out)
}(jsonStream, tokenStream)
atoms := walk.Atomise(tokenStream)
output, err := RunTransducer(transducer, atoms)
if err {
fmt.Println("Error")
return
}
valueOut, error := walk.MemoryCompound(output)
if error != nil {
fmt.Println(error.Error())
return
}
for _, value := range valueOut {
fmt.Println(value)
}
}
|
