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