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