1 //: A Mu program is a book of 'recipes' (functions)
  2 :(before "End Globals")
  3 //: Each recipe is stored at a specific page number, or ordinal.
  4 map<recipe_ordinal, recipe> Recipe;
  5 //: You can also refer to each recipe by its name.
  6 map<string, recipe_ordinal> Recipe_ordinal;
  7 recipe_ordinal Next_recipe_ordinal = 1;
  8 
  9 //: Ordinals are like numbers, except you can't do arithmetic on them. Ordinal
 10 //: 1 is not less than 2, it's just different. Phone numbers are ordinals;
 11 //: adding two phone numbers is meaningless. Here each recipe does something
 12 //: incommensurable with any other recipe.
 13 :(after "Types")
 14 typedef int recipe_ordinal;
 15 
 16 :(before "End Types")
 17 // Recipes are lists of instructions. To perform or 'run' a recipe, the
 18 // computer runs its instructions.
 19 struct recipe {
 20   recipe_ordinal ordinal;
 21   string name;
 22   vector<instruction> steps;
 23   // End recipe Fields
 24   recipe();
 25 };
 26 
 27 :(before "struct recipe")
 28 // Each instruction is either of the form:
 29 //   product1, product2, product3, ... <- operation ingredient1, ingredient2, ingredient3, ...
 30 // or just a single 'label' starting with a non-alphanumeric character
 31 //   +label
 32 // Labels don't do anything, they're just named locations in a recipe.
 33 struct instruction {
 34   bool is_label;
 35   string label;  // only if is_label
 36   string name;  // only if !is_label
 37   string original_string;  // for error messages
 38   recipe_ordinal operation;  // get(Recipe_ordinal, name)
 39   vector<reagent> ingredients;  // only if !is_label
 40   vector<reagent> products;  // only if !is_label
 41   // End instruction Fields
 42   instruction();
 43   void clear();
 44   bool is_empty();
 45 };
 46 
 47 :(before "struct instruction")
 48 // Ingredients and products are a single species -- a reagent. Reagents refer
 49 // either to numbers or to locations in memory along with 'type' tags telling
 50 // us how to interpret them. They also can contain arbitrary other lists of
 51 // properties besides types, but we're getting ahead of ourselves.
 52 struct reagent {
 53   string original_string;
 54   string name;
 55   type_tree* type;
 56   vector<pair<string, string_tree*> > properties;  // can't be a map because the string_tree sometimes needs to be NULL, which can be confusing
 57   double value;
 58   bool initialized;
 59   // End reagent Fields
 60   reagent(const string& s);
 61   reagent() :type(NULL), value(0), initialized(false) {}
 62   reagent(type_tree* t) :type(t), value(0), initialized(false) {}
 63   ~reagent();
 64   void clear();
 65   reagent(const reagent& original);
 66   reagent& operator=(const reagent& original);
 67   void set_value(double v) { value = v;  initialized = true; }
 68 };
 69 
 70 :(before "struct reagent")
 71 // Types can range from a simple type ordinal, to arbitrarily complex trees of
 72 // type parameters, like (map (address array character) (list number))
 73 struct type_tree {
 74   bool atom;
 75   string name;  // only if atom
 76   type_ordinal value;  // only if atom
 77   type_tree* left;  // only if !atom
 78   type_tree* right;  // only if !atom
 79   ~type_tree();
 80   type_tree(const type_tree& original);
 81   // atomic type ordinal
 82   explicit type_tree(string name);
 83   type_tree(string name, type_ordinal v) :atom(true), name(name), value(v), left(NULL), right(NULL) {}
 84   // tree of type ordinals
 85   type_tree(type_tree* l, type_tree* r) :atom(false), value(0), left(l), right(r) {}
 86   type_tree& operator=(const type_tree& original);
 87   bool operator==(const type_tree& other) const;
 88   bool operator!=(const type_tree& other) const { return !operator==(other); }
 89   bool operator<(const type_tree& other) const;
 90   bool operator>(const type_tree& other) const { return other.operator<(*this); }
 91 };
 92 
 93 struct string_tree {
 94   bool atom;
 95   string value;  // only if atom
 96   string_tree* left;  // only if !atom
 97   string_tree* right;  // only if !atom
 98   ~string_tree();
 99   string_tree(const string_tree& original);
100   // atomic string
101   explicit string_tree(string v) :atom(true), value(v), left(NULL), right(NULL) {}
102   // tree of strings
103   string_tree(string_tree* l, string_tree* r) :atom(false), left(l), right(r) {}
104 };
105 
106 // End type_tree Definition
107 :(code)
108 type_tree::type_tree(string name) :atom(true), name(name), value(get(Type_ordinal, name)), left(NULL), right(NULL) {}
109 
110 :(before "End Globals")
111 // Locations refer to a common 'memory'. Each location can store a number.
112 map<int, double> Memory;
113 :(before "End Reset")
114 Memory.clear();
115 
116 :(after "Types")
117 // Mu types encode how the numbers stored in different parts of memory are
118 // interpreted. A location tagged as a 'character' type will interpret the
119 // value 97 as the letter 'a', while a different location of type 'number'
120 // would not.
121 //
122 // Unlike most computers today, Mu stores types in a single big table, shared
123 // by all the Mu programs on the computer. This is useful in providing a
124 // seamless experience to help understand arbitrary Mu programs.
125 typedef int type_ordinal;
126 :(before "End Globals")
127 map<string, type_ordinal> Type_ordinal;
128 map<type_ordinal, type_info> Type;
129 type_ordinal Next_type_ordinal = 1;
130 type_ordinal Number_type_ordinal = 0;
131 type_ordinal Boolean_type_ordinal = 0;
132 type_ordinal Character_type_ordinal = 0;
133 type_ordinal Address_type_ordinal = 0;
134 type_ordinal Array_type_ordinal = 0;
135 :(code)
136 void setup_types() {
137   Type.clear();  Type_ordinal.clear();
138   put(Type_ordinal, "literal", 0);
139   Next_type_ordinal = 1;
140   // Mu Types Initialization
141   Number_type_ordinal = put(Type_ordinal, "number", Next_type_ordinal++);
142   get_or_insert(Type, Number_type_ordinal).name = "number";
143   put(Type_ordinal, "location", Number_type_ordinal);  // synonym of number for addresses we'll never look up
144   Address_type_ordinal = put(Type_ordinal, "address", Next_type_ordinal++);
145   get_or_insert(Type, Address_type_ordinal).name = "address";
146   Boolean_type_ordinal = put(Type_ordinal, "boolean", Next_type_ordinal++);
147   get_or_insert(Type, Boolean_type_ordinal).name = "boolean";
148   Character_type_ordinal = put(Type_ordinal, "character", Next_type_ordinal++);
149   get_or_insert(Type, Character_type_ordinal).name = "character";
150   // Array types are a special modifier to any other type. For example,
151   // array:number or array:address:boolean.
152   Array_type_ordinal = put(Type_ordinal, "array", Next_type_ordinal++);
153   get_or_insert(Type, Array_type_ordinal).name = "array";
154   // End Mu Types Initialization
155 }
156 void teardown_types() {
157   for (map<type_ordinal, type_info>::iterator p = Type.begin();  p != Type.end();  ++p) {
158     for (int i = 0;  i < SIZE(p->second.elements);  ++i)
159       p->second.elements.clear();
160   }
161   Type_ordinal.clear();
162 }
163 :(before "End One-time Setup")
164 setup_types();
165 atexit(teardown_types);
166 
167 :(before "End Types")
168 // You can construct arbitrary new types. New types are either 'containers'
169 // with multiple 'elements' of other types, or 'exclusive containers' containing
170 // one of multiple 'variants'. (These are similar to C structs and unions,
171 // respectively, though exclusive containers implicitly include a tag element
172 // recording which variant they should be interpreted as.)
173 //
174 // For example, storing bank balance and name for an account might require a
175 // container, but if bank accounts may be either for individuals or groups,
176 // with different properties for each, that may require an exclusive container
177 // whose variants are individual-account and joint-account containers.
178 enum kind_of_type {
179   PRIMITIVE,
180   CONTAINER,
181   EXCLUSIVE_CONTAINER
182 };
183 
184 struct type_info {
185   string name;
186   kind_of_type kind;
187   vector<reagent> elements;
188   // End type_info Fields
189   type_info() :kind(PRIMITIVE) {
190     // End type_info Constructor
191   }
192 };
193 
194 enum primitive_recipes {
195   IDLE = 0,
196   COPY,
197   // End Primitive Recipe Declarations
198   MAX_PRIMITIVE_RECIPES,
199 };
200 :(code)
201 //: It's all very well to construct recipes out of other recipes, but we need
202 //: to know how to do *something* out of the box. For the following
203 //: recipes there are only codes, no entries in the book, because Mu just knows
204 //: what to do for them.
205 void setup_recipes() {
206   Recipe.clear();  Recipe_ordinal.clear();
207   put(Recipe_ordinal, "idle", IDLE);
208   // Primitive Recipe Numbers
209   put(Recipe_ordinal, "copy", COPY);
210   // End Primitive Recipe Numbers
211 }
212 //: We could just reset the recipe table after every test, but that gets slow
213 //: all too quickly. Instead, initialize the common stuff just once at
214 //: startup. Later layers will carefully undo each test's additions after
215 //: itself.
216 :(before "End One-time Setup")
217 setup_recipes();
218 assert(MAX_PRIMITIVE_RECIPES < 200);  // level 0 is primitives; until 199
219 Next_recipe_ordinal = 200;
220 put(Recipe_ordinal, "main", Next_recipe_ordinal++);
221 // Load Mu Prelude
222 // End Mu Prelude
223 :(before "End Commandline Parsing")
224 assert(Next_recipe_ordinal < 1000);  // recipes being tested didn't overflow into test space
225 :(before "End Reset")
226 Next_recipe_ordinal = 1000;  // consistent new numbers for each test
227 
228 //: One final detail: tests can modify our global tables of recipes and types,
229 //: so we need some way to clean up after each test is done so it doesn't
230 //: influence later ones.
231 :(before "End Globals")
232 map<string, recipe_ordinal> Recipe_ordinal_snapshot;
233 map<recipe_ordinal, recipe> Recipe_snapshot;
234 map<string, type_ordinal> Type_ordinal_snapshot;
235 map<type_ordinal, type_info> Type_snapshot;
236 :(before "End One-time Setup")
237 save_snapshots();
238 :(before "End Reset")
239 restore_snapshots();
240 
241 :(code)
242 void save_snapshots() {
243   Recipe_ordinal_snapshot = Recipe_ordinal;
244   Recipe_snapshot = Recipe;
245   Type_ordinal_snapshot = Type_ordinal;
246   Type_snapshot = Type;
247   // End save_snapshots
248 }
249 
250 void restore_snapshots() {
251   Recipe = Recipe_snapshot;
252   Recipe_ordinal = Recipe_ordinal_snapshot;
253   restore_non_recipe_snapshots();
254 }
255 // when running sandboxes in the edit/ app we'll want to restore everything except recipes defined in the app
256 void restore_non_recipe_snapshots() {
257   Type_ordinal = Type_ordinal_snapshot;
258   Type = Type_snapshot;
259   // End restore_snapshots
260 }
261 
262 //:: Helpers
263 
264 :(code)
265 recipe::recipe() {
266   ordinal = -1;
267   // End recipe Constructor
268 }
269 
270 instruction::instruction() :is_label(false), operation(IDLE) {
271   // End instruction Constructor
272 }
273 void instruction::clear() {
274   is_label=false;
275   label.clear();
276   name.clear();
277   operation=IDLE;
278   ingredients.clear();
279   products.clear();
280   original_string.clear();
281   // End instruction Clear
282 }
283 bool instruction::is_empty() { return !is_label && name.empty(); }
284 
285 // Reagents have the form <name>:<type>:<type>:.../<property>/<property>/...
286 reagent::reagent(const string& s) :original_string(s), type(NULL), value(0), initialized(false) {
287   // Parsing reagent(string s)
288   istringstream in(s);
289   in >> std::noskipws;
290   // name and type
291   istringstream first_row(slurp_until(in, '/'));
292   first_row >> std::noskipws;
293   name = slurp_until(first_row, ':');
294   string_tree* type_names = parse_property_list(first_row);
295   // End Parsing Reagent Type Property(type_names)
296   type = new_type_tree(type_names);
297   delete type_names;
298   // special cases
299   if (is_integer(name) && type == NULL)
300     type = new type_tree("literal");
301   if (name == "_" && type == NULL)
302     type = new type_tree("literal");
303   // other properties
304   slurp_properties(in, properties);
305   // End Parsing reagent
306 }
307 
308 void slurp_properties(istream& in, vector<pair<string, string_tree*> >& out) {
309   while (has_data(in)) {
310     istringstream row(slurp_until(in, '/'));
311     row >> std::noskipws;
312     string key = slurp_until(row, ':');
313     string_tree* value = parse_property_list(row);
314     out.push_back(pair<string, string_tree*>(key, value));
315   }
316 }
317 
318 string_tree* parse_property_list(istream& in) {
319   skip_whitespace_but_not_newline(in);
320   if (!has_data(in)) return NULL;
321   string_tree* first = new string_tree(slurp_until(in, ':'));
322   if (!has_data(in)) return first;
323   string_tree* rest = parse_property_list(in);
324   if (!has_data(in) && rest->atom)
325     return new string_tree(first, new string_tree(rest, NULL));
326   return new string_tree(first, rest);
327 }
328 :(before "End Unit Tests")
329 void test_parse_property_list_atom() {
330   istringstream in("a");
331   string_tree* x = parse_property_list(in);
332   CHECK(x->atom);
333   delete x;
334 }
335 void test_parse_property_list_list() {
336   istringstream in("a:b");
337   string_tree* x = parse_property_list(in);
338   CHECK(!x->atom);
339   CHECK(x->left->atom);
340   CHECK_EQ(x->left->value, "a");
341   CHECK(!x->right->atom);
342   CHECK(x->right->left->atom);
343   CHECK_EQ(x->right->left->value, "b");
344   CHECK(x->right->right == NULL);
345   delete x;
346 }
347 
348 :(code)
349 type_tree* new_type_tree(const string_tree* properties) {
350   if (!properties) return NULL;
351   if (properties->atom) {
352     const string& type_name = properties->value;
353     int value = 0;
354     if (contains_key(Type_ordinal, type_name))
355       value = get(Type_ordinal, type_name);
356     else if (is_integer(type_name))  // sometimes types will contain literal integers, like for the size of an array
357       value = 0;
358     else if (properties->value == "->")  // used in recipe types
359       value = 0;
360     else
361       value = -1;  // should never happen; will trigger errors later
362     return new type_tree(type_name, value);
363   }
364   return new type_tree(new_type_tree(properties->left),
365                        new_type_tree(properties->right));
366 }
367 
368 //: avoid memory leaks for the type tree
369 
370 reagent::reagent(const reagent& other) {
371   original_string = other.original_string;
372   name = other.name;
373   value = other.value;
374   initialized = other.initialized;
375   for (int i = 0;  i < SIZE(other.properties);  ++i) {
376     properties.push_back(pair<string, string_tree*>(other.properties.at(i).first, copy(other.properties.at(i).second)));
377   }
378   type = copy(other.type);
379   // End reagent Copy Constructor
380 }
381 
382 type_tree::type_tree(const type_tree& original) {
383   atom = original.atom;
384   name = original.name;
385   value = original.value;
386   left = copy(original.left);
387   right = copy(original.right);
388 }
389 
390 type_tree& type_tree::operator=(const type_tree& original) {
391   atom = original.atom;
392   name = original.name;
393   value = original.value;
394   if (left) delete left;
395   left = copy(original.left);
396   if (right) delete right;
397   right = copy(original.right);
398   return *this;
399 }
400 
401 bool type_tree::operator==(const type_tree& other) const {
402   if (atom != other.atom) return false;
403   if (atom)
404     return name == other.name && value == other.value;
405   return (left == other.left || *left == *other.left)
406       && (right == other.right || *right == *other.right);
407 }
408 
409 // only constraint we care about: if a < b then !(b < a)
410 bool type_tree::operator<(const type_tree& other) const {
411   if (atom != other.atom) return atom > other.atom;  // atoms before non-atoms
412   if (atom) return value < other.value;
413   // first location in one that's missing in the other makes that side 'smaller'
414   if (left && !other.left) return false;
415   if (!left && other.left) return true;
416   if (right && !other.right) return false;
417   if (!right && other.right) return true;
418   // now if either pointer is unequal neither side can be null
419   // if one side is equal that's easy
420   if (left == other.left || *left == *other.left) return right && *right < *other.right;
421   if (right == other.right || *right == *other.right) return left && *left < *other.left;
422   // if the two sides criss-cross, pick the side with the smaller lhs
423   if ((left == other.right || *left == *other.right)
424       && (right == other.left || *right == *other.left))
425     return *left < *other.left;
426   // now the hard case: both sides are not equal
427   // make sure we stay consistent between (a < b) and (b < a)
428   // just return the side with the smallest of the 4 branches
429   if (*left < *other.left && *left < *other.right) return true;
430   if (*right < *other.left && *right < *other.right) return true;
431   return false;
432 }
433 :(before "End Unit Tests")
434 // These unit tests don't always use valid types.
435 void test_compare_atom_types() {
436   reagent a("a:address"), b("b:boolean");
437   CHECK(*a.type < *b.type);
438   CHECK(!(*b.type < *a.type));
439 }
440 void test_compare_equal_atom_types() {
441   reagent a("a:address"), b("b:address");
442   CHECK(!(*a.type < *b.type));
443   CHECK(!(*b.type < *a.type));
444 }
445 void test_compare_atom_with_non_atom() {
446   reagent a("a:address:number"), b("b:boolean");
447   CHECK(!(*a.type < *b.type));
448   CHECK(*b.type < *a.type);
449 }
450 void test_compare_lists_with_identical_structure() {
451   reagent a("a:address:address"), b("b:address:boolean");
452   CHECK(*a.type < *b.type);
453   CHECK(!(*b.type < *a.type));
454 }
455 void test_compare_identical_lists() {
456   reagent a("a:address:boolean"), b("b:address:boolean");
457   CHECK(!(*a.type < *b.type));
458   CHECK(!(*b.type < *a.type));
459 }
460 void test_compare_list_with_extra_element() {
461   reagent a("a:address:address"), b("b:address:address:number");
462   CHECK(*a.type < *b.type);
463   CHECK(!(*b.type < *a.type));
464 }
465 void test_compare_list_with_smaller_left_but_larger_right() {
466   reagent a("a:number:character"), b("b:boolean:array");
467   CHECK(*a.type < *b.type);
468   CHECK(!(*b.type < *a.type));
469 }
470 void test_compare_list_with_smaller_left_but_larger_right_identical_types() {
471   reagent a("a:address:boolean"), b("b:boolean:address");
472   CHECK(*a.type < *b.type);
473   CHECK(!(*b.type < *a.type));
474 }
475 
476 :(code)
477 string_tree::string_tree(const string_tree& original) {
478   atom = original.atom;
479   value = original.value;
480   left = copy(original.left);
481   right = copy(original.right);
482 }
483 
484 reagent& reagent::operator=(const reagent& other) {
485   original_string = other.original_string;
486   for (int i = 0;  i < SIZE(properties);  ++i)
487     if (properties.at(i).second) delete properties.at(i).second;
488   properties.clear();
489   for (int i = 0;  i < SIZE(other.properties);  ++i)
490     properties.push_back(pair<string, string_tree*>(other.properties.at(i).first, copy(other.properties.at(i).second)));
491   name = other.name;
492   value = other.value;
493   initialized = other.initialized;
494   if (type) delete type;
495   type = copy(other.type);
496   // End reagent Copy Operator
497   return *this;
498 }
499 
500 reagent::~reagent() {
501   clear();
502 }
503 
504 void reagent::clear() {
505   for (int i = 0;  i < SIZE(properties);  ++i) {
506     if (properties.at(i).second) {
507       delete properties.at(i).second;
508       properties.at(i).second = NULL;
509     }
510   }
511   delete type;
512   type = NULL;
513 }
514 type_tree::~type_tree() {
515   delete left;
516   delete right;
517 }
518 string_tree::~string_tree() {
519   delete left;
520   delete right;
521 }
522 
523 void append(type_tree*& base, type_tree* extra) {
524   if (!base) {
525     base = extra;
526     return;
527   }
528   type_tree* curr = base;
529   while (curr->right) curr = curr->right;
530   curr->right = extra;
531 }
532 
533 void append(string_tree*& base, string_tree* extra) {
534   if (!base) {
535     base = extra;
536     return;
537   }
538   string_tree* curr = base;
539   while (curr->right) curr = curr->right;
540   curr->right = extra;
541 }
542 
543 string slurp_until(istream& in, char delim) {
544   ostringstream out;
545   char c;
546   while (in >> c) {
547     if (c == delim) {
548       // drop the delim
549       break;
550     }
551     out << c;
552   }
553   return out.str();
554 }
555 
556 bool has_property(const reagent& x, const string& name) {
557   for (int i = 0;  i < SIZE(x.properties);  ++i) {
558     if (x.properties.at(i).first == name) return true;
559   }
560   return false;
561 }
562 
563 string_tree* property(const reagent& r, const string& name) {
564   for (int p = 0;  p != SIZE(r.properties);  ++p) {
565     if (r.properties.at(p).first == name)
566       return r.properties.at(p).second;
567   }
568   return NULL;
569 }
570 
571 string_tree* copy(const string_tree* x) {
572   if (x == NULL) return NULL;
573   return new string_tree(*x);
574 }
575 
576 type_tree* copy(const type_tree* x) {
577   if (x == NULL) return NULL;
578   return new type_tree(*x);
579 }
580 
581 :(before "End Globals")
582 extern const string Ignore(",");  // commas are ignored in Mu except within [] strings
583 :(code)
584 void skip_whitespace_but_not_newline(istream& in) {
585   while (true) {
586     if (!has_data(in)) break;
587     else if (in.peek() == '\n') break;
588     else if (isspace(in.peek())) in.get();
589     else if (Ignore.find(in.peek()) != string::npos) in.get();
590     else break;
591   }
592 }
593 
594 void dump_memory() {
595   for (map<int, double>::iterator p = Memory.begin();  p != Memory.end();  ++p) {
596     cerr << p->first << ": " << no_scientific(p->second) << '\n';
597   }
598 }
599 
600 //:: Helpers for converting various values to string
601 //: Use to_string() in trace(), and try to keep it stable from run to run.
602 //: Use debug_string() while debugging, and throw everything into it.
603 //: Use inspect() only for emitting a canonical format that can be parsed back
604 //: into the value.
605 
606 string to_string(const recipe& r) {
607   ostringstream out;
608   out << "recipe " << r.name << " [\n";
609   for (int i = 0;  i < SIZE(r.steps);  ++i)
610     out << "  " << to_string(r.steps.at(i)) << '\n';
611   out << "]\n";
612   return out.str();
613 }
614 
615 string to_original_string(const recipe& r) {
616   ostringstream out;
617   out << "recipe " << r.name << " [\n";
618   for (int i = 0;  i < SIZE(r.steps);  ++i)
619     out << "  " << to_original_string(r.steps.at(i)) << '\n';
620   out << "]\n";
621   return out.str();
622 }
623 
624 string debug_string(const recipe& x) {
625   ostringstream out;
626   out << "- recipe " << x.name << '\n';
627   // Begin debug_string(recipe x)
628   for (int index = 0;  index < SIZE(x.steps);  ++index) {
629     const instruction& inst = x.steps.at(index);
630     out << "inst: " << to_string(inst) << '\n';
631     out << "  ingredients\n";
632     for (int i = 0;  i < SIZE(inst.ingredients);  ++i)
633       out << "    " << debug_string(inst.ingredients.at(i)) << '\n';
634     out << "  products\n";
635     for (int i = 0;  i < SIZE(inst.products);  ++i)
636       out << "    " << debug_string(inst.products.at(i)) << '\n';
637   }
638   return out.str();
639 }
640 
641 string to_original_string(const instruction& inst) {
642   if (inst.is_label) return inst.label;
643   if (!inst.original_string.empty()) return inst.original_string;
644   ostringstream out;
645   for (int i = 0;  i < SIZE(inst.products);  ++i) {
646     if (i > 0) out << ", ";
647     out << inst.products.at(i).original_string;
648   }
649   if (!inst.products.empty()) out << " <- ";
650   out << inst.name;
651   if (!inst.ingredients.empty()) out << ' ';
652   for (int i = 0;  i < SIZE(inst.ingredients);  ++i) {
653     if (i > 0) out << ", ";
654     out << inst.ingredients.at(i).original_string;
655   }
656   return out.str();
657 }
658 
659 string to_string(const instruction& inst) {
660   if (inst.is_label) return inst.label;
661   ostringstream out;
662   for (int i = 0;  i < SIZE(inst.products);  ++i) {
663     if (i > 0) out << ", ";
664     out << to_string(inst.products.at(i));
665   }
666   if (!inst.products.empty()) out << " <- ";
667   out << inst.name << ' ';
668   for (int i = 0;  i < SIZE(inst.ingredients);  ++i) {
669     if (i > 0) out << ", ";
670     out << to_string(inst.ingredients.at(i));
671   }
672   return out.str();
673 }
674 
675 string to_string(const reagent& r) {
676   if (is_dummy(r)) return "_";
677   ostringstream out;
678   out << "{";
679   out << r.name << ": " << names_to_string(r.type);
680   if (!r.properties.empty()) {
681     for (int i = 0;  i < SIZE(r.properties);  ++i)
682       out << ", \"" << r.properties.at(i).first << "\": " << to_string(r.properties.at(i).second);
683   }
684   out << "}";
685   return out.str();
686 }
687 
688 // special name for ignoring some products
689 bool is_dummy(const reagent& x) {
690   return x.name == "_";
691 }
692 
693 string debug_string(const reagent& x) {
694   ostringstream out;
695   out << x.name << ": " << x.value << ' ' << to_string(x.type) << " -- " << to_string(x);
696   return out.str();
697 }
698 
699 string to_string(const string_tree* property) {
700   if (!property) return "()";
701   ostringstream out;
702   dump(property, out);
703   return out.str();
704 }
705 
706 void dump(const string_tree* x, ostream& out) {
707   if (!x) return;
708   if (x->atom) {
709     out << '"' << x->value << '"';
710     return;
711   }
712   out << '(';
713   const string_tree* curr = x;
714   while (curr && !curr->atom) {
715     dump(curr->left, out);
716     if (curr->right) out << ' ';
717     curr = curr->right;
718   }
719   // check for dotted list; should never happen
720   if (curr) {
721     out << ". ";
722     dump(curr, out);
723   }
724   out << ')';
725 }
726 
727 string to_string(const type_tree* type) {
728   if (type == NULL) return "()";
729   ostringstream out;
730   dump(type, out);
731   return out.str();
732 }
733 
734 void dump(const type_tree* x, ostream& out) {
735   if (!x) return;
736   if (x->atom) {
737     dump(x->value, out);
738     return;
739   }
740   out << '(';
741   const type_tree* curr = x;
742   while (curr && !curr->atom) {
743     dump(curr->left, out);
744     if (curr->right) out << ' ';
745     curr = curr->right;
746   }
747   // check for dotted list; should never happen
748   if (curr) {
749     out << ". ";
750     dump(curr, out);
751   }
752   out << ')';
753 }
754 
755 void dump(type_ordinal type, ostream& out) {
756   if (contains_key(Type, type))
757     out << get(Type, type).name;
758   else
759     out << "?" << type;
760 }
761 
762 string names_to_string(const type_tree* type) {
763   if (type == NULL) return "()";  // should never happen
764   ostringstream out;
765   dump_names(type, out);
766   return out.str();
767 }
768 
769 void dump_names(const type_tree* x, ostream& out) {
770   if (!x) return;
771   if (x->atom) {
772     out << '"' << x->name << '"';
773     return;
774   }
775   out << '(';
776   const type_tree* curr = x;
777   while (curr && !curr->atom) {
778     dump_names(curr->left, out);
779     if (curr->right) out << ' ';
780     curr = curr->right;
781   }
782   // check for dotted list; should never happen
783   if (curr) {
784     out << ". ";
785     dump_names(curr, out);
786   }
787   out << ')';
788 }
789 
790 string names_to_string_without_quotes(const type_tree* type) {
791   if (type == NULL) return "()";
792   ostringstream out;
793   dump_names_without_quotes(type, out);
794   return out.str();
795 }
796 
797 void dump_names_without_quotes(const type_tree* x, ostream& out) {
798   if (!x) return;
799   if (x->atom) {
800     out << x->name;
801     return;
802   }
803   out << '(';
804   const type_tree* curr = x;
805   while (curr && !curr->atom) {
806     dump_names_without_quotes(curr->left, out);
807     if (curr->right) out << ' ';
808     curr = curr->right;
809   }
810   // check for dotted list; should never happen
811   if (curr) {
812     out << ". ";
813     dump_names_without_quotes(curr, out);
814   }
815   out << ')';
816 }
817 
818 bool is_integer(const string& s) {
819   return s.find_first_not_of("0123456789-") == string::npos  // no other characters
820       && s.find_first_of("0123456789") != string::npos  // at least one digit
821       && s.find('-', 1) == string::npos;  // '-' only at first position
822 }
823 
824 int to_integer(string n) {
825   char* end = NULL;
826   // safe because string.c_str() is guaranteed to be null-terminated
827   int result = strtoll(n.c_str(), &end, /*any base*/0);
828   if (*end != '\0') cerr << "tried to convert " << n << " to number\n";
829   assert(*end == '\0');
830   return result;
831 }
832 
833 void test_is_integer() {
834   CHECK(is_integer("1234"));
835   CHECK(is_integer("-1"));
836   CHECK(!is_integer("234.0"));
837   CHECK(is_integer("-567"));
838   CHECK(!is_integer("89-0"));
839   CHECK(!is_integer("-"));
840   CHECK(!is_integer("1e3"));  // not supported
841 }
842 
843 //: helper to print numbers without excessive precision
844 
845 :(before "End Types")
846 struct no_scientific {
847   double x;
848   explicit no_scientific(double y) :x(y) {}
849 };
850 
851 :(code)
852 ostream& operator<<(ostream& os, no_scientific x) {
853   if (!isfinite(x.x)) {
854     // Infinity or NaN
855     os << x.x;
856     return os;
857   }
858   ostringstream tmp;
859   // more accurate, but too slow
860 //?   tmp.precision(308);  // for 64-bit numbers
861   tmp << std::fixed << x.x;
862   os << trim_floating_point(tmp.str());
863   return os;
864 }
865 
866 string trim_floating_point(const string& in) {
867   if (in.empty()) return "";
868   if (in.find('.') == string::npos) return in;
869   int length = SIZE(in);
870   while (length > 1) {
871     if (in.at(length-1) != '0') break;
872     --length;
873   }
874   if (in.at(length-1) == '.') --length;
875   if (length == 0) return "0";
876   return in.substr(0, length);
877 }
878 
879 void test_trim_floating_point() {
880   CHECK_EQ(trim_floating_point(""), "");
881   CHECK_EQ(trim_floating_point(".0"), "0");
882   CHECK_EQ(trim_floating_point("1.5000"), "1.5");
883   CHECK_EQ(trim_floating_point("1.000001"), "1.000001");
884   CHECK_EQ(trim_floating_point("23.000000"), "23");
885   CHECK_EQ(trim_floating_point("23.0"), "23");
886   CHECK_EQ(trim_floating_point("23."), "23");
887   CHECK_EQ(trim_floating_point("23"), "23");
888   CHECK_EQ(trim_floating_point("230"), "230");
889   CHECK_EQ(trim_floating_point("3.000000"), "3");
890   CHECK_EQ(trim_floating_point("3.0"), "3");
891   CHECK_EQ(trim_floating_point("3."), "3");
892   CHECK_EQ(trim_floating_point("3"), "3");
893 }
894 
895 :(before "End Includes")
896 #include <map>
897 using std::map;
898 #include <utility>
899 using std::pair;
900 #include <math.h>