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
|
:(after "Types")
// A program is a book of 'recipes' (functions)
typedef int recipe_number;
:(before "End Globals")
map<string, recipe_number> Recipe_number;
map<recipe_number, recipe> Recipe;
int Next_recipe_number = 1;
:(before "End Types")
// Recipes are lists of instructions. To run a recipe, the computer runs its
// instructions.
struct recipe {
string name;
vector<instruction> steps;
// End recipe Fields
};
:(before "struct recipe")
// Each instruction is either of the form:
// product1, product2, product3, ... <- operation ingredient1, ingredient2, ingredient3, ...
// or just a single 'label' starting with a non-alphanumeric character
// +label
// Labels don't do anything, they're just waypoints.
struct instruction {
bool is_label;
string label; // only if is_label
string name; // only if !is_label
recipe_number operation; // Recipe_number[name]
vector<reagent> ingredients; // only if !is_label
vector<reagent> products; // only if !is_label
instruction();
void clear();
string to_string() const;
};
:(before "struct instruction")
// Ingredients and products are a single species -- a reagent. Reagents refer
// either to numbers or to locations in memory along with 'type' tags telling
// us how to interpret them. They also can contain arbitrary other lists of
// properties besides types, but we're getting ahead of ourselves.
struct reagent {
vector<pair<string, vector<string> > > properties;
string name;
int value;
bool initialized;
vector<type_number> types;
reagent(string s);
reagent();
void set_value(int v) { value = v; initialized = true; }
string to_string() const;
};
:(before "struct reagent")
struct property {
vector<string> values;
};
:(before "End Globals")
// Locations refer to a common 'memory'. Each location can store a number.
map<index_t, int> Memory;
:(before "End Setup")
Memory.clear();
:(after "Types")
// Mu types encode how the numbers stored in different parts of memory are
// interpreted. A location tagged as a 'character' type will interpret the
// number 97 as the letter 'a', while a different location of type 'integer'
// would not.
//
// Unlike most computers today, mu stores types in a single big table, shared
// by all the mu programs on the computer. This is useful in providing a
// seamless experience to help understand arbitrary mu programs.
typedef int type_number;
:(before "End Globals")
map<string, type_number> Type_number;
map<type_number, type_info> Type;
int Next_type_number = 1;
:(code)
void setup_types() {
Type.clear(); Type_number.clear();
Type_number["literal"] = 0;
Next_type_number = 1;
// Mu Types Initialization
int integer = Type_number["integer"] = Next_type_number++;
Type_number["location"] = Type_number["integer"]; // wildcard type: either a pointer or a scalar
Type[integer].name = "integer";
int address = Type_number["address"] = Next_type_number++;
Type[address].name = "address";
int boolean = Type_number["boolean"] = Next_type_number++;
Type[boolean].name = "boolean";
int character = Type_number["character"] = Next_type_number++;
Type[character].name = "character";
// Array types are a special modifier to any other type. For example,
// array:integer or array:address:boolean.
int array = Type_number["array"] = Next_type_number++;
Type[array].name = "array";
// End Mu Types Initialization
}
:(before "End One-time Setup")
setup_types();
:(before "End Types")
// You can construct arbitrary new types. New types are either 'containers'
// with multiple 'elements' of other types, or 'exclusive containers' containing
// one of multiple 'variants'. (These are similar to C structs and unions,
// respectively, though exclusive containers implicitly include a tag element
// recording which variant they should be interpreted as.)
//
// For example, storing bank balance and name for an account might require a
// container, but if bank accounts may be either for individuals or groups,
// with different properties for each, that may require an exclusive container
// whose variants are individual-account and joint-account containers.
enum kind_of_type {
primitive,
container,
exclusive_container
};
struct type_info {
string name;
kind_of_type kind;
size_t size; // only if type is not primitive; primitives and addresses have size 1 (except arrays are dynamic)
vector<vector<type_number> > elements;
vector<string> element_names;
// End type_info Fields
type_info() :kind(primitive), size(0) {}
};
enum primitive_recipes {
IDLE = 0,
COPY,
// End Primitive Recipe Declarations
MAX_PRIMITIVE_RECIPES,
};
:(code)
//: It's all very well to construct recipes out of other recipes, but we need
//: to know how to do *something* out of the box. For the following
//: recipes there are only codes, no entries in the book, because mu just knows
//: what to do for them.
void setup_recipes() {
Recipe.clear(); Recipe_number.clear();
Recipe_number["idle"] = IDLE;
// Primitive Recipe Numbers
Recipe_number["copy"] = COPY;
// End Primitive Recipe Numbers
}
//: We could just reset the recipe table after every test, but that gets slow
//: all too quickly. Instead, initialize the common stuff just once at
//: startup. Later layers will carefully undo each test's additions after
//: itself.
:(before "End One-time Setup")
setup_recipes();
assert(MAX_PRIMITIVE_RECIPES < 100); // level 0 is primitives; until 99
Next_recipe_number = 100;
// End Load Recipes
:(before "End Test Run Initialization")
assert(Next_recipe_number < 1000); // functions being tested didn't overflow into test space
:(before "End Setup")
Next_recipe_number = 1000; // consistent new numbers for each test
//:: Helpers
:(code)
instruction::instruction() :is_label(false), operation(IDLE) {}
void instruction::clear() { is_label=false; label.clear(); operation=IDLE; ingredients.clear(); products.clear(); }
// Reagents have the form <name>:<type>:<type>:.../<property>/<property>/...
reagent::reagent(string s) :value(0), initialized(false) {
istringstream in(s);
in >> std::noskipws;
// properties
while (!in.eof()) {
istringstream row(slurp_until(in, '/'));
row >> std::noskipws;
string name = slurp_until(row, ':');
vector<string> values;
while (!row.eof())
values.push_back(slurp_until(row, ':'));
properties.push_back(pair<string, vector<string> >(name, values));
}
// structures for the first row of properties
name = properties[0].first;
for (index_t i = 0; i < properties[0].second.size(); ++i) {
types.push_back(Type_number[properties[0].second[i]]);
}
if (name == "_" && types.empty()) {
types.push_back(0);
properties[0].second.push_back("dummy");
}
}
reagent::reagent() :value(0), initialized(false) {
// The first property is special, so ensure we always have it.
// Other properties can be pushed back, but the first must always be
// assigned to.
properties.push_back(pair<string, vector<string> >("", vector<string>()));
}
string reagent::to_string() const {
ostringstream out;
out << "{name: \"" << name << "\", value: " << value << ", type: ";
for (index_t i = 0; i < types.size(); ++i) {
out << types[i];
if (i < types.size()-1) out << "-";
}
if (!properties.empty()) {
out << ", properties: [";
for (index_t i = 0; i < properties.size(); ++i) {
out << "\"" << properties[i].first << "\": ";
for (index_t j = 0; j < properties[i].second.size(); ++j) {
out << "\"" << properties[i].second[j] << "\"";
if (j < properties[i].second.size()-1) out << ":";
}
if (i < properties.size()-1) out << ", ";
else out << "]";
}
}
out << "}";
return out.str();
}
string instruction::to_string() const {
if (is_label) return label;
ostringstream out;
for (index_t i = 0; i < products.size(); ++i) {
if (i > 0) out << ", ";
out << products[i].to_string();
}
if (!products.empty()) out << " <- ";
out << name << '/' << operation << ' ';
for (index_t i = 0; i < ingredients.size(); ++i) {
if (i > 0) out << ", ";
out << ingredients[i].to_string();
}
return out.str();
}
string slurp_until(istream& in, char delim) {
ostringstream out;
char c;
while (in >> c) {
if (c == delim) {
// drop the delim
break;
}
out << c;
}
return out.str();
}
void dump_memory() {
map<int, int> ordered(Memory.begin(), Memory.end());
for (map<int, int>::iterator p = ordered.begin(); p != ordered.end(); ++p) {
cout << p->first << ": " << p->second << '\n';
}
}
:(before "End Includes")
#include <map>
using std::map;
|