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