2277 - reagents now have a tree of types

22 files changed, 337 insertions, 237 deletions

diff --git a/010vm.cc b/010vm.cc
index cf54d65a..f264f752 100644
--- a/010vm.cc
+++ b/010vm.cc
@@ -52,9 +52,12 @@ struct reagent {
   string name;
   double value;
   bool initialized;
-  vector<type_ordinal> types;
+  type_tree* type;
   reagent(string s);
   reagent();
+  ~reagent();
+  reagent(const reagent& old);
+  reagent& operator=(const reagent& old);
   void set_value(double v) { value = v; initialized = true; }
   string to_string() const;
 };
@@ -64,6 +67,22 @@ struct property {
   vector<string> values;
 };
 
+// Types can range from a simple type ordinal, to arbitrarily complex trees of
+// type ordinals.
+struct type_tree {
+  type_ordinal value;
+  type_tree* left;
+  type_tree* right;
+  ~type_tree();
+  type_tree(const type_tree& old);
+  // simple: type ordinal
+  type_tree(type_ordinal v) :value(v), left(NULL), right(NULL) {}
+  // intermediate: list of type ordinals
+  type_tree(type_ordinal v, type_tree* r) :value(v), left(NULL), right(r) {}
+  // advanced: tree containing type ordinals in the leaves
+  type_tree(type_tree* l, type_tree* r) :value(0), left(l), right(r) {}
+};
+
 :(before "End Globals")
 // Locations refer to a common 'memory'. Each location can store a number.
 map<long long int, double> Memory;
@@ -105,8 +124,20 @@ void setup_types() {
   Type[array].name = "array";
   // End Mu Types Initialization
 }
+void teardown_types() {
+  // todo: why can't I just Type.clear()?
+  for (map<type_ordinal, type_info>::iterator p = Type.begin(); p != Type.end(); ++p) {
+    if (!p->second.name.empty()) {
+      for (long long int i = 0; i < SIZE(p->second.elements); ++i) {
+        delete p->second.elements.at(i);
+      }
+    }
+  }
+  Type_ordinal.clear();
+}
 :(before "End One-time Setup")
 setup_types();
+atexit(teardown_types);
 
 :(before "End Types")
 // You can construct arbitrary new types. New types are either 'containers'
@@ -129,7 +160,7 @@ struct type_info {
   string name;
   kind_of_type kind;
   long long int size;  // only if type is not primitive; primitives and addresses have size 1 (except arrays are dynamic)
-  vector<vector<type_ordinal> > elements;
+  vector<type_tree*> elements;
   vector<string> element_names;
   // End type_info Fields
   type_info() :kind(primitive), size(0) {}
@@ -179,7 +210,7 @@ instruction::instruction() :is_label(false), operation(IDLE) {
 void instruction::clear() { is_label=false; label.clear(); operation=IDLE; ingredients.clear(); products.clear(); }
 
 // Reagents have the form <name>:<type>:<type>:.../<property>/<property>/...
-reagent::reagent(string s) :original_string(s), value(0), initialized(false) {
+reagent::reagent(string s) :original_string(s), value(0), initialized(false), type(NULL) {
   // Parsing reagent(string s)
   istringstream in(s);
   in >> std::noskipws;
@@ -193,8 +224,9 @@ reagent::reagent(string s) :original_string(s), value(0), initialized(false) {
       values.push_back(slurp_until(row, ':'));
     properties.push_back(pair<string, vector<string> >(name, values));
   }
-  // structures for the first row of properties
+  // structures for the first row of properties: name and list of types
   name = properties.at(0).first;
+  type_tree** curr_type = &type;
   for (long long int i = 0; i < SIZE(properties.at(0).second); ++i) {
     string type = properties.at(0).second.at(i);
     if (Type_ordinal.find(type) == Type_ordinal.end()
@@ -202,20 +234,50 @@ reagent::reagent(string s) :original_string(s), value(0), initialized(false) {
         && !is_integer(type)) {
       Type_ordinal[type] = Next_type_ordinal++;
     }
-    types.push_back(Type_ordinal[type]);
+    *curr_type = new type_tree(Type_ordinal[type]);
+    curr_type = &(*curr_type)->right;
   }
-  if (is_integer(name) && types.empty()) {
-    types.push_back(0);
+  if (is_integer(name) && type == NULL) {
+    type = new type_tree(0);
     properties.at(0).second.push_back("literal");
   }
-  if (name == "_" && types.empty()) {
-    types.push_back(0);
+  if (name == "_" && type == NULL) {
+    type = new type_tree(0);
     properties.at(0).second.push_back("dummy");
   }
   // End Parsing reagent
 }
 
-reagent::reagent() :value(0), initialized(false) {
+//: avoid memory leaks for the type tree
+
+reagent::reagent(const reagent& old) :original_string(old.original_string), properties(old.properties), name(old.name), value(old.value), initialized(old.initialized) {
+  type = old.type ? new type_tree(*old.type) : NULL;
+}
+
+type_tree::type_tree(const type_tree& old) :value(old.value) {
+  left = old.left ? new type_tree(*old.left) : NULL;
+  right = old.right ? new type_tree(*old.right) : NULL;
+}
+
+reagent& reagent::operator=(const reagent& old) {
+  original_string = old.original_string;
+  properties = old.properties;
+  name = old.name;
+  value = old.value;
+  initialized = old.initialized;
+  type = old.type? new type_tree(*old.type) : NULL;
+  return *this;
+}
+
+reagent::~reagent() {
+  delete type;
+}
+type_tree::~type_tree() {
+  delete left;
+  delete right;
+}
+
+reagent::reagent() :value(0), initialized(false), type(NULL) {
   // The first property is special, so ensure we always have it.
   // Other properties can be pushed back, but the first must always be
   // assigned to.
diff --git a/011load.cc b/011load.cc
index d06476b0..44d906a3 100644
--- a/011load.cc
+++ b/011load.cc
@@ -47,9 +47,10 @@ long long int slurp_recipe(istream& in) {
   if (Recipe_ordinal.find(recipe_name) == Recipe_ordinal.end()) {
     Recipe_ordinal[recipe_name] = Next_recipe_ordinal++;
   }
-  if (warn_on_redefine(recipe_name)
-      && Recipe.find(Recipe_ordinal[recipe_name]) != Recipe.end()) {
-    raise << "redefining recipe " << Recipe[Recipe_ordinal[recipe_name]].name << "\n" << end();
+  if (Recipe.find(Recipe_ordinal[recipe_name]) != Recipe.end()) {
+    if (warn_on_redefine(recipe_name))
+      raise << "redefining recipe " << Recipe[Recipe_ordinal[recipe_name]].name << "\n" << end();
+    Recipe.erase(Recipe_ordinal[recipe_name]);
   }
   // todo: save user-defined recipes to mu's memory
   Recipe[Recipe_ordinal[recipe_name]] = slurp_body(in);
diff --git a/013literal_string.cc b/013literal_string.cc
index 78b15f18..569c8613 100644
--- a/013literal_string.cc
+++ b/013literal_string.cc
@@ -111,7 +111,7 @@ if (s.at(0) == '[') {
   s.erase(0, 1);
   strip_last(s);
   name = s;
-  types.push_back(0);
+  type = new type_tree(0);
   properties.push_back(pair<string, vector<string> >(name, vector<string>()));
   properties.back().second.push_back("literal-string");
   return;
diff --git a/014literal_noninteger.cc b/014literal_noninteger.cc
index c609171e..19966d9a 100644
--- a/014literal_noninteger.cc
+++ b/014literal_noninteger.cc
@@ -10,7 +10,7 @@ recipe main [
 :(after "Parsing reagent(string s)")
 if (is_noninteger(s)) {
   name = s;
-  types.push_back(0);
+  type = new type_tree(0);
   properties.push_back(pair<string, vector<string> >(name, vector<string>()));
   properties.back().second.push_back("literal-number");
   set_value(to_double(s));
diff --git a/020run.cc b/020run.cc
index 5ca093e7..d135e4b5 100644
--- a/020run.cc
+++ b/020run.cc
@@ -266,7 +266,7 @@ void write_memory(reagent x, vector<double> data) {
   if (is_literal(x)) return;
   long long int base = x.value;
   if (size_mismatch(x, data)) {
-    raise_error << maybe(current_recipe_name()) << "size mismatch in storing to " << x.original_string << " (" << size_of(x.types) << " vs " << SIZE(data) << ") at '" << current_instruction().to_string() << "'\n" << end();
+    raise_error << maybe(current_recipe_name()) << "size mismatch in storing to " << x.original_string << " (" << size_of(x.type) << " vs " << SIZE(data) << ") at '" << current_instruction().to_string() << "'\n" << end();
     return;
   }
   for (long long int offset = 0; offset < SIZE(data); ++offset) {
@@ -278,18 +278,18 @@ void write_memory(reagent x, vector<double> data) {
 
 :(code)
 long long int size_of(const reagent& r) {
-  if (r.types.empty()) return 0;
+  if (r.type == NULL) return 0;
   // End size_of(reagent) Cases
-  return size_of(r.types);
+  return size_of(r.type);
 }
-long long int size_of(const vector<type_ordinal>& types) {
-  if (types.empty()) return 0;
-  // End size_of(types) Cases
+long long int size_of(const type_tree* type) {
+  if (type == NULL) return 0;
+  // End size_of(type) Cases
   return 1;
 }
 
 bool size_mismatch(const reagent& x, const vector<double>& data) {
-  if (x.types.empty()) return true;
+  if (x.type == NULL) return true;
   // End size_mismatch(x) Cases
 //?   if (size_of(x) != SIZE(data)) cerr << size_of(x) << " vs " << SIZE(data) << '\n';
   return size_of(x) != SIZE(data);
@@ -300,7 +300,10 @@ bool is_dummy(const reagent& x) {
 }
 
 bool is_literal(const reagent& r) {
-  return SIZE(r.types) == 1 && r.types.at(0) == 0;
+  if (!r.type) return false;
+  if (r.type->value == 0)
+    assert(!r.type->left && !r.type->right);
+  return r.type->value == 0;
 }
 
 // hook to suppress inserting recipe name into errors and warnings (for later layers)
diff --git a/021check_instruction.cc b/021check_instruction.cc
index fcd861da..e51424f2 100644
--- a/021check_instruction.cc
+++ b/021check_instruction.cc
@@ -80,11 +80,16 @@ bool types_match(reagent lhs, reagent rhs) {
   // allow writing 0 to any address
   if (rhs.name == "0" && is_mu_address(lhs)) return true;
   if (is_literal(rhs)) return !is_mu_array(lhs) && !is_mu_address(lhs) && size_of(rhs) == size_of(lhs);
-  // more refined types can always be copied to less refined ones
-  if (SIZE(lhs.types) > SIZE(rhs.types)) return false;
-  if (SIZE(lhs.types) == SIZE(rhs.types)) return lhs.types == rhs.types;
-  rhs.types.resize(SIZE(lhs.types));
-  return lhs.types == rhs.types;
+  if (!lhs.type) return !rhs.type;
+  return types_match(lhs.type, rhs.type);
+}
+
+// two types match if the second begins like the first
+// (trees perform the same check recursively on each subtree)
+bool types_match(type_tree* lhs, type_tree* rhs) {
+  if (!lhs) return true;
+  if (lhs->value != rhs->value) return false;
+  return types_match(lhs->left, rhs->left) && types_match(lhs->right, rhs->right);
 }
 
 bool is_raw(const reagent& r) {
@@ -92,25 +97,28 @@ bool is_raw(const reagent& r) {
 }
 
 bool is_mu_array(reagent r) {
+  if (!r.type) return false;
   if (is_literal(r)) return false;
-  return !r.types.empty() && r.types.at(0) == Type_ordinal["array"];
+  return r.type->value == Type_ordinal["array"];
 }
 
 bool is_mu_address(reagent r) {
+  if (!r.type) return false;
   if (is_literal(r)) return false;
-  return !r.types.empty() && r.types.at(0) == Type_ordinal["address"];
+  return r.type->value == Type_ordinal["address"];
 }
 
 bool is_mu_number(reagent r) {
+  if (!r.type) return false;
   if (is_literal(r))
     return r.properties.at(0).second.at(0) == "literal-number"
         || r.properties.at(0).second.at(0) == "literal";
-  if (r.types.empty()) return false;
-  if (r.types.at(0) == Type_ordinal["character"]) return true;  // permit arithmetic on unicode code points
-  return r.types.at(0) == Type_ordinal["number"];
+  if (r.type->value == Type_ordinal["character"]) return true;  // permit arithmetic on unicode code points
+  return r.type->value == Type_ordinal["number"];
 }
 
 bool is_mu_scalar(reagent r) {
+  if (!r.type) return false;
   if (is_literal(r))
     return r.properties.at(0).second.empty() || r.properties.at(0).second.at(0) != "literal-string";
   if (is_mu_array(r)) return false;
diff --git a/030container.cc b/030container.cc
index 0c893fbc..5bbef105 100644
--- a/030container.cc
+++ b/030container.cc
@@ -6,10 +6,10 @@ type_ordinal point = Type_ordinal["point"] = Next_type_ordinal++;
 Type[point].size = 2;
 Type[point].kind = container;
 Type[point].name = "point";
-vector<type_ordinal> i;
-i.push_back(number);
-Type[point].elements.push_back(i);
-Type[point].elements.push_back(i);
+Type[point].elements.push_back(new type_tree(number));
+Type[point].element_names.push_back("x");
+Type[point].elements.push_back(new type_tree(number));
+Type[point].element_names.push_back("y");
 
 //: Containers can be copied around with a single instruction just like
 //: numbers, no matter how large they are.
@@ -41,12 +41,10 @@ type_ordinal point_number = Type_ordinal["point-number"] = Next_type_ordinal++;
 Type[point_number].size = 2;
 Type[point_number].kind = container;
 Type[point_number].name = "point-number";
-vector<type_ordinal> p2;
-p2.push_back(point);
-Type[point_number].elements.push_back(p2);
-vector<type_ordinal> i2;
-i2.push_back(number);
-Type[point_number].elements.push_back(i2);
+Type[point_number].elements.push_back(new type_tree(point));
+Type[point_number].element_names.push_back("xy");
+Type[point_number].elements.push_back(new type_tree(number));
+Type[point_number].element_names.push_back("z");
 
 :(scenario copy_handles_nested_container_elements)
 recipe main [
@@ -84,14 +82,18 @@ recipe main [
 ]
 +mem: storing 0 in location 7
 
-:(before "End size_of(types) Cases")
-type_info t = Type[types.at(0)];
+:(before "End size_of(type) Cases")
+if (type->value == 0) {
+  assert(!type->left && !type->right);
+  return 1;
+}
+type_info t = Type[type->value];
 if (t.kind == container) {
   // size of a container is the sum of the sizes of its elements
   long long int result = 0;
   for (long long int i = 0; i < SIZE(t.elements); ++i) {
     // todo: strengthen assertion to disallow mutual type recursion
-    if (types.at(0) == t.elements.at(i).at(0)) {
+    if (t.elements.at(i)->value == type->value) {
       raise_error << "container " << t.name << " can't include itself as a member\n" << end();
       return 0;
     }
@@ -131,11 +133,11 @@ case GET: {
   }
   reagent base = inst.ingredients.at(0);
   // Update GET base in Check
-  if (base.types.empty() || Type[base.types.at(0)].kind != container) {
+  if (!base.type || !base.type->value || Type[base.type->value].kind != container) {
     raise_error << maybe(Recipe[r].name) << "first ingredient of 'get' should be a container, but got " << inst.ingredients.at(0).original_string << '\n' << end();
     break;
   }
-  type_ordinal base_type = base.types.at(0);
+  type_ordinal base_type = base.type->value;
   reagent offset = inst.ingredients.at(1);
   if (!is_literal(offset) || !is_mu_scalar(offset)) {
     raise_error << maybe(Recipe[r].name) << "second ingredient of 'get' should have type 'offset', but got " << inst.ingredients.at(1).original_string << '\n' << end();
@@ -155,7 +157,7 @@ case GET: {
   reagent product = inst.products.at(0);
   // Update GET product in Check
   reagent element;
-  element.types = Type[base_type].elements.at(offset_value);
+  element.type = new type_tree(*Type[base_type].elements.at(offset_value));
   if (!types_match(product, element)) {
     raise_error << maybe(Recipe[r].name) << "'get' " << offset.original_string << " (" << offset_value << ") on " << Type[base_type].name << " can't be saved in " << product.original_string << "; type should be " << dump_types(element) << '\n' << end();
     break;
@@ -171,7 +173,7 @@ case GET: {
     raise_error << maybe(current_recipe_name()) << "tried to access location 0 in '" << current_instruction().to_string() << "'\n" << end();
     break;
   }
-  type_ordinal base_type = base.types.at(0);
+  type_ordinal base_type = base.type->value;
   long long int offset = ingredients.at(1).at(0);
   if (offset < 0 || offset >= SIZE(Type[base_type].elements)) break;  // copied from Check above
   long long int src = base_address;
@@ -180,11 +182,11 @@ case GET: {
     src += size_of(Type[base_type].elements.at(i));
   }
   trace(Primitive_recipe_depth, "run") << "address to copy is " << src << end();
-  type_ordinal src_type = Type[base_type].elements.at(offset).at(0);
+  type_ordinal src_type = Type[base_type].elements.at(offset)->value;
   trace(Primitive_recipe_depth, "run") << "its type is " << Type[src_type].name << end();
   reagent tmp;
   tmp.set_value(src);
-  tmp.types.push_back(src_type);
+  tmp.type = new type_tree(src_type);
   products.push_back(read_memory(tmp));
   break;
 }
@@ -192,13 +194,28 @@ case GET: {
 :(code)
 string dump_types(const reagent& x) {
   ostringstream out;
-  for (long long int i = 0; i < SIZE(x.types); ++i) {
-    if (i > 0) out << ':';
-    out << Type[x.types.at(i)].name;
-  }
+  dump_types(x.type, out);
   return out.str();
 }
 
+void dump_types(type_tree* type, ostringstream& out) {
+  if (!type->left && !type->right) {
+    out << Type[type->value].name;
+    return;
+  }
+  out << "<";
+  if (type->left)
+    dump_types(type->left, out);
+  else
+    out << Type[type->value].name;
+  out << ":";
+  if (type->right)
+    dump_types(type->right, out);
+  else
+    out << ".<>";
+  out << ">";
+}
+
 :(scenario get_handles_nested_container_elements)
 recipe main [
   12:number <- copy 34
@@ -208,16 +225,6 @@ recipe main [
 ]
 +mem: storing 36 in location 15
 
-//:: To write to elements of containers, you need their address.
-
-:(scenario get_address)
-recipe main [
-  12:number <- copy 34
-  13:number <- copy 35
-  15:address:number <- get-address 12:point/raw, 1:offset  # unsafe
-]
-+mem: storing 13 in location 15
-
 :(scenario get_out_of_bounds)
 % Hide_errors = true;
 recipe main [
@@ -248,6 +255,16 @@ recipe main [
 ]
 +error: main: 'get' 1:offset (1) on point-number can't be saved in 15:address:number; type should be number
 
+//:: To write to elements of containers, you need their address.
+
+:(scenario get_address)
+recipe main [
+  12:number <- copy 34
+  13:number <- copy 35
+  15:address:number <- get-address 12:point/raw, 1:offset  # unsafe
+]
++mem: storing 13 in location 15
+
 :(before "End Primitive Recipe Declarations")
 GET_ADDRESS,
 :(before "End Primitive Recipe Numbers")
@@ -260,11 +277,11 @@ case GET_ADDRESS: {
   }
   reagent base = inst.ingredients.at(0);
   // Update GET_ADDRESS base in Check
-  if (base.types.empty() || Type[base.types.at(0)].kind != container) {
+  if (!base.type || Type[base.type->value].kind != container) {
     raise_error << maybe(Recipe[r].name) << "first ingredient of 'get-address' should be a container, but got " << inst.ingredients.at(0).original_string << '\n' << end();
     break;
   }
-  type_ordinal base_type = base.types.at(0);
+  type_ordinal base_type = base.type->value;
   reagent offset = inst.ingredients.at(1);
   if (!is_literal(offset) || !is_mu_scalar(offset)) {
     raise_error << maybe(Recipe[r].name) << "second ingredient of 'get' should have type 'offset', but got " << inst.ingredients.at(1).original_string << '\n' << end();
@@ -284,8 +301,10 @@ case GET_ADDRESS: {
   reagent product = inst.products.at(0);
   // Update GET_ADDRESS product in Check
   reagent element;
-  element.types = Type[base_type].elements.at(offset_value);
-  element.types.insert(element.types.begin(), Type_ordinal["address"]);
+  // same type as for GET..
+  element.type = new type_tree(*Type[base_type].elements.at(offset_value));
+  // ..except for an address at the start
+  element.type = new type_tree(Type_ordinal["address"], element.type);
   if (!types_match(product, element)) {
     raise_error << maybe(Recipe[r].name) << "'get-address' " << offset.original_string << " (" << offset_value << ") on " << Type[base_type].name << " can't be saved in " << product.original_string << "; type should be " << dump_types(element) << '\n' << end();
     break;
@@ -301,7 +320,7 @@ case GET_ADDRESS: {
     raise_error << maybe(current_recipe_name()) << "tried to access location 0 in '" << current_instruction().to_string() << "'\n" << end();
     break;
   }
-  type_ordinal base_type = base.types.at(0);
+  type_ordinal base_type = base.type->value;
   long long int offset = ingredients.at(1).at(0);
   if (offset < 0 || offset >= SIZE(Type[base_type].elements)) break;  // copied from Check above
   long long int result = base_address;
@@ -343,7 +362,7 @@ recipe main [
   14:number <- copy 36
   15:number <- get-address 12:point-number/raw, 1:offset
 ]
-+error: main: 'get-address' 1:offset (1) on point-number can't be saved in 15:number; type should be address:number
++error: main: 'get-address' 1:offset (1) on point-number can't be saved in 15:number; type should be <address:number>
 
 //:: Allow containers to be defined in mu code.
 
@@ -406,6 +425,8 @@ void insert_container(const string& command, kind_of_type kind, istream& in) {
     istringstream inner(element);
     info.element_names.push_back(slurp_until(inner, ':'));
     trace("parse") << "  element name: " << info.element_names.back() << end();
+    type_tree* new_type = NULL;
+    type_tree** curr_type = &new_type;
     vector<type_ordinal> types;
     while (!inner.eof()) {
       string type_name = slurp_until(inner, ':');
@@ -415,10 +436,11 @@ void insert_container(const string& command, kind_of_type kind, istream& in) {
           && !is_integer(type_name)) {
         Type_ordinal[type_name] = Next_type_ordinal++;
       }
-      types.push_back(Type_ordinal[type_name]);
-      trace("parse") << "  type: " << types.back() << end();
+      *curr_type = new type_tree(Type_ordinal[type_name]);
+      trace("parse") << "  type: " << Type_ordinal[type_name] << end();
+      curr_type = &(*curr_type)->right;
     }
-    info.elements.push_back(types);
+    info.elements.push_back(new_type);
   }
   assert(SIZE(info.elements) == SIZE(info.element_names));
   info.size = SIZE(info.elements);
@@ -457,6 +479,10 @@ recently_added_types.clear();
 :(before "End Setup")  //: for tests
 for (long long int i = 0; i < SIZE(recently_added_types); ++i) {
   Type_ordinal.erase(Type[recently_added_types.at(i)].name);
+  // todo: why do I explicitly need to provide this?
+  for (long long int j = 0; j < SIZE(Type.at(recently_added_types.at(i)).elements); ++j) {
+    delete Type.at(recently_added_types.at(i)).elements.at(j);
+  }
   Type.erase(recently_added_types.at(i));
 }
 recently_added_types.clear();
@@ -491,7 +517,7 @@ recipe main [
   # integer is not a type
   1:integer <- copy 0
 ]
-+error: unknown type: integer
++error: main: unknown type in '1:integer <- copy 0'
 
 :(scenario run_allows_type_definition_after_use)
 % Hide_errors = true;
@@ -513,20 +539,21 @@ void check_invalid_types(const recipe_ordinal r) {
   for (long long int index = 0; index < SIZE(Recipe[r].steps); ++index) {
     const instruction& inst = Recipe[r].steps.at(index);
     for (long long int i = 0; i < SIZE(inst.ingredients); ++i) {
-      check_invalid_types(inst.ingredients.at(i));
+      check_invalid_types(inst.ingredients.at(i).type, maybe(Recipe[r].name), "'"+inst.to_string()+"'");
     }
     for (long long int i = 0; i < SIZE(inst.products); ++i) {
-      check_invalid_types(inst.products.at(i));
+      check_invalid_types(inst.products.at(i).type, maybe(Recipe[r].name), "'"+inst.to_string()+"'");
     }
   }
 }
 
-void check_invalid_types(const reagent& r) {
-  for (long long int i = 0; i < SIZE(r.types); ++i) {
-    if (r.types.at(i) == 0) continue;
-    if (Type.find(r.types.at(i)) == Type.end())
-      raise_error << "unknown type: " << r.properties.at(0).second.at(i) << '\n' << end();
+void check_invalid_types(const type_tree* type, const string& block, const string& name) {
+  if (!type) return;  // will throw a more precise error elsewhere
+  if (type->value && Type.find(type->value) == Type.end()) {
+    raise_error << block << "unknown type in " << name << '\n' << end();
   }
+  if (type->left) check_invalid_types(type->left, block, name);
+  if (type->right) check_invalid_types(type->right, block, name);
 }
 
 :(scenario container_unknown_field)
@@ -535,7 +562,7 @@ container foo [
   x:number
   y:bar
 ]
-+error: unknown type for field y in foo
++error: foo: unknown type in y
 
 :(scenario read_container_with_bracket_in_comment)
 container foo [
@@ -557,12 +584,7 @@ void check_container_field_types() {
   for (map<type_ordinal, type_info>::iterator p = Type.begin(); p != Type.end(); ++p) {
     const type_info& info = p->second;
     for (long long int i = 0; i < SIZE(info.elements); ++i) {
-      for (long long int j = 0; j < SIZE(info.elements.at(i)); ++j) {
-        if (info.elements.at(i).at(j) == 0) continue;
-        if (Type.find(info.elements.at(i).at(j)) != Type.end()) continue;
-        // End Container Type Checks
-        raise_error << "unknown type for field " << info.element_names.at(i) << " in " << info.name << '\n' << end();
-      }
+      check_invalid_types(info.elements.at(i), maybe(info.name), info.element_names.at(i));
     }
   }
 }
diff --git a/031address.cc b/031address.cc
index fd7c61e0..7be3b54d 100644
--- a/031address.cc
+++ b/031address.cc
@@ -11,7 +11,7 @@ recipe main [
 +mem: storing 34 in location 3
 
 :(before "long long int base = x.value" following "vector<double> read_memory(reagent x)")
-x = canonize(x);
+canonize(x);
 
 //: similarly, write to addresses pointing at other locations using the
 //: 'lookup' property
@@ -23,7 +23,7 @@ recipe main [
 +mem: storing 34 in location 2
 
 :(before "long long int base = x.value" following "void write_memory(reagent x, vector<double> data)")
-x = canonize(x);
+canonize(x);
 if (x.value == 0) {
   raise_error << "can't write to location 0 in '" << current_instruction().to_string() << "'\n" << end();
   return;
@@ -40,44 +40,25 @@ recipe main [
 +error: can't write to location 0 in '1:address:number/lookup <- copy 34'
 
 :(code)
-reagent canonize(reagent x) {
-  if (is_literal(x)) return x;
-  reagent r = x;
-  while (has_property(r, "lookup"))
-    r = lookup_memory(r);
-  return r;
+void canonize(reagent& x) {
+  if (is_literal(x)) return;
+  // End canonize(x) Special-cases
+  while (has_property(x, "lookup"))
+    lookup_memory(x);
 }
 
-reagent lookup_memory(reagent x) {
-  static const type_ordinal ADDRESS = Type_ordinal["address"];
-  reagent result;
-  if (x.types.empty() || x.types.at(0) != ADDRESS) {
+void lookup_memory(reagent& x) {
+  if (!x.type || x.type->value != Type_ordinal["address"]) {
     raise_error << maybe(current_recipe_name()) << "tried to /lookup " << x.original_string << " but it isn't an address\n" << end();
-    return result;
   }
   // compute value
   if (x.value == 0) {
     raise_error << maybe(current_recipe_name()) << "tried to /lookup 0\n" << end();
-    return result;
   }
-  result.set_value(Memory[x.value]);
-  trace(Primitive_recipe_depth, "mem") << "location " << x.value << " is " << no_scientific(result.value) << end();
-
-  // populate types
-  copy(++x.types.begin(), x.types.end(), inserter(result.types, result.types.begin()));
-
-  // drop one 'lookup'
-  long long int i = 0;
-  long long int len = SIZE(x.properties);
-  for (i = 0; i < len; ++i) {
-    if (x.properties.at(i).first == "lookup") break;
-    result.properties.push_back(x.properties.at(i));
-  }
-  ++i;  // skip first lookup
-  for (; i < len; ++i) {
-    result.properties.push_back(x.properties.at(i));
-  }
-  return result;
+  trace(Primitive_recipe_depth, "mem") << "location " << x.value << " is " << no_scientific(Memory[x.value]) << end();
+  x.set_value(Memory[x.value]);
+  drop_address_from_type(x);
+  drop_one_lookup(x);
 }
 
 :(after "bool types_match(reagent lhs, reagent rhs)")
@@ -96,20 +77,23 @@ reagent lookup_memory(reagent x) {
 :(code)
 bool canonize_type(reagent& r) {
   while (has_property(r, "lookup")) {
-    if (r.types.empty()) {
+    if (!r.type || r.type->value != Type_ordinal["address"]) {
       raise_error << "can't lookup non-address: " << r.original_string << '\n' << end();
       return false;
     }
-    if (r.types.at(0) != Type_ordinal["address"]) {
-      raise_error << "can't lookup non-address: " << r.original_string << '\n' << end();
-      return false;
-    }
-    r.types.erase(r.types.begin());
+    drop_address_from_type(r);
     drop_one_lookup(r);
   }
   return true;
 }
 
+void drop_address_from_type(reagent& r) {
+  type_tree* tmp = r.type;
+  r.type = tmp->right;
+  tmp->right = NULL;
+  delete tmp;
+}
+
 void drop_one_lookup(reagent& r) {
   for (vector<pair<string, vector<string> > >::iterator p = r.properties.begin(); p != r.properties.end(); ++p) {
     if (p->first == "lookup") {
@@ -144,7 +128,7 @@ if (!canonize_type(base)) break;
 :(after "Update GET product in Check")
 if (!canonize_type(product)) break;
 :(after "Update GET base in Run")
-base = canonize(base);
+canonize(base);
 
 :(scenario get_address_indirect)
 # 'get' can read from container address
@@ -161,7 +145,7 @@ if (!canonize_type(base)) break;
 :(after "Update GET_ADDRESS product in Check")
 if (!canonize_type(base)) break;
 :(after "Update GET_ADDRESS base in Run")
-base = canonize(base);
+canonize(base);
 
 //:: abbreviation for '/lookup': a prefix '*'
 
@@ -191,7 +175,8 @@ _DUMP,
 Recipe_ordinal["$dump"] = _DUMP;
 :(before "End Primitive Recipe Implementations")
 case _DUMP: {
-  reagent after_canonize = canonize(current_instruction().ingredients.at(0));
+  reagent after_canonize = current_instruction().ingredients.at(0);
+  canonize(after_canonize);
   cerr << maybe(current_recipe_name()) << current_instruction().ingredients.at(0).name << ' ' << no_scientific(current_instruction().ingredients.at(0).value) << " => " << no_scientific(after_canonize.value) << " => " << no_scientific(Memory[after_canonize.value]) << '\n';
   break;
 }
@@ -211,7 +196,9 @@ case _FOO: {
     else cerr << '\n';
   }
   else {
-    foo = canonize(current_instruction().ingredients.at(0)).value;
+    reagent tmp = current_instruction().ingredients.at(0);
+    canonize(tmp);
+    foo = tmp.value;
   }
   break;
 }
diff --git a/032array.cc b/032array.cc
index 1d64ff90..5cc34c1d 100644
--- a/032array.cc
+++ b/032array.cc
@@ -29,7 +29,7 @@ case CREATE_ARRAY: {
     raise_error << maybe(Recipe[r].name) << "'create-array' cannot create non-array " << product.original_string << '\n' << end();
     break;
   }
-  if (SIZE(product.types) == 1) {
+  if (!product.type->right) {
     raise_error << maybe(Recipe[r].name) << "create array of what? " << inst.to_string() << '\n' << end();
     break;
   }
@@ -46,7 +46,8 @@ case CREATE_ARRAY: {
 }
 :(before "End Primitive Recipe Implementations")
 case CREATE_ARRAY: {
-  reagent product = canonize(current_instruction().products.at(0));
+  reagent product = current_instruction().products.at(0);
+  canonize(product);
   long long int base_address = product.value;
   long long int array_size= to_integer(product.properties.at(0).second.at(2));
   // initialize array size, so that size_of will work
@@ -104,15 +105,15 @@ recipe main [
 
 //: disable the size mismatch check since the destination array need not be initialized
 :(before "End size_mismatch(x) Cases")
-if (x.types.at(0) == Type_ordinal["array"]) return false;
+if (x.type && x.type->value == Type_ordinal["array"]) return false;
 :(before "End size_of(reagent) Cases")
-if (r.types.at(0) == Type_ordinal["array"]) {
-  if (SIZE(r.types) == 1) {
+if (r.type && r.type->value == Type_ordinal["array"]) {
+  if (!r.type->right) {
     raise_error << maybe(current_recipe_name()) << "'" << r.original_string << "' is an array of what?\n" << end();
     return 1;
   }
   // skip the 'array' type to get at the element type
-  return 1 + Memory[r.value]*size_of(array_element(r.types));
+  return 1 + Memory[r.value]*size_of(array_element(r.type));
 }
 
 //:: To access elements of an array, use 'index'
@@ -158,7 +159,7 @@ case INDEX: {
   reagent product = inst.products.at(0);
   canonize_type(product);
   reagent element;
-  element.types = array_element(base.types);
+  element.type = new type_tree(*array_element(base.type));
   if (!types_match(product, element)) {
     raise_error << maybe(Recipe[r].name) << "'index' on " << base.original_string << " can't be saved in " << product.original_string << "; type should be " << dump_types(element) << '\n' << end();
     break;
@@ -167,32 +168,34 @@ case INDEX: {
 }
 :(before "End Primitive Recipe Implementations")
 case INDEX: {
-  reagent base = canonize(current_instruction().ingredients.at(0));
+  reagent base = current_instruction().ingredients.at(0);
+  canonize(base);
   long long int base_address = base.value;
   if (base_address == 0) {
     raise_error << maybe(current_recipe_name()) << "tried to access location 0 in '" << current_instruction().to_string() << "'\n" << end();
     break;
   }
-  reagent offset = canonize(current_instruction().ingredients.at(1));
+  reagent offset = current_instruction().ingredients.at(1);
+  canonize(offset);
   vector<double> offset_val(read_memory(offset));
-  vector<type_ordinal> element_type = array_element(base.types);
+  type_tree* element_type = array_element(base.type);
   if (offset_val.at(0) < 0 || offset_val.at(0) >= Memory[base_address]) {
     raise_error << maybe(current_recipe_name()) << "invalid index " << no_scientific(offset_val.at(0)) << '\n' << end();
     break;
   }
   long long int src = base_address + 1 + offset_val.at(0)*size_of(element_type);
   trace(Primitive_recipe_depth, "run") << "address to copy is " << src << end();
-  trace(Primitive_recipe_depth, "run") << "its type is " << Type[element_type.at(0)].name << end();
+  trace(Primitive_recipe_depth, "run") << "its type is " << Type[element_type->value].name << end();
   reagent tmp;
   tmp.set_value(src);
-  copy(element_type.begin(), element_type.end(), inserter(tmp.types, tmp.types.begin()));
+  tmp.type = new type_tree(*element_type);
   products.push_back(read_memory(tmp));
   break;
 }
 
 :(code)
-vector<type_ordinal> array_element(const vector<type_ordinal>& types) {
-  return vector<type_ordinal>(++types.begin(), types.end());
+type_tree* array_element(const type_tree* type) {
+  return type->right;
 }
 
 :(scenario index_indirect)
@@ -283,8 +286,8 @@ case INDEX_ADDRESS: {
   reagent product = inst.products.at(0);
   canonize_type(product);
   reagent element;
-  element.types = array_element(base.types);
-  element.types.insert(element.types.begin(), Type_ordinal["address"]);
+  element.type = new type_tree(*array_element(base.type));
+  element.type = new type_tree(Type_ordinal["address"], element.type);
   if (!types_match(product, element)) {
     raise_error << maybe(Recipe[r].name) << "'index' on " << base.original_string << " can't be saved in " << product.original_string << "; type should be " << dump_types(element) << '\n' << end();
     break;
@@ -293,15 +296,17 @@ case INDEX_ADDRESS: {
 }
 :(before "End Primitive Recipe Implementations")
 case INDEX_ADDRESS: {
-  reagent base = canonize(current_instruction().ingredients.at(0));
+  reagent base = current_instruction().ingredients.at(0);
+  canonize(base);
   long long int base_address = base.value;
   if (base_address == 0) {
     raise_error << maybe(current_recipe_name()) << "tried to access location 0 in '" << current_instruction().to_string() << "'\n" << end();
     break;
   }
-  reagent offset = canonize(current_instruction().ingredients.at(1));
+  reagent offset = current_instruction().ingredients.at(1);
+  canonize(offset);
   vector<double> offset_val(read_memory(offset));
-  vector<type_ordinal> element_type = array_element(base.types);
+  type_tree* element_type = array_element(base.type);
   if (offset_val.at(0) < 0 || offset_val.at(0) >= Memory[base_address]) {
     raise_error << maybe(current_recipe_name()) << "invalid index " << no_scientific(offset_val.at(0)) << '\n' << end();
     break;
@@ -355,7 +360,7 @@ recipe main [
   8:address:array:point <- copy 1/raw
   9:address:number <- index-address *8:address:array:point, 0
 ]
-+error: main: 'index' on *8:address:array:point can't be saved in 9:address:number; type should be address:point
++error: main: 'index' on *8:address:array:point can't be saved in 9:address:number; type should be <address:point>
 
 //:: compute the length of an array
 
@@ -389,7 +394,8 @@ case LENGTH: {
 }
 :(before "End Primitive Recipe Implementations")
 case LENGTH: {
-  reagent x = canonize(current_instruction().ingredients.at(0));
+  reagent x = current_instruction().ingredients.at(0);
+  canonize(x);
   if (x.value == 0) {
     raise_error << maybe(current_recipe_name()) << "tried to access location 0 in '" << current_instruction().to_string() << "'\n" << end();
     break;
diff --git a/033exclusive_container.cc b/033exclusive_container.cc
index 1f591acd..5376e058 100644
--- a/033exclusive_container.cc
+++ b/033exclusive_container.cc
@@ -11,13 +11,9 @@ type_ordinal tmp = Type_ordinal["number-or-point"] = Next_type_ordinal++;
 Type[tmp].size = 2;
 Type[tmp].kind = exclusive_container;
 Type[tmp].name = "number-or-point";
-vector<type_ordinal> t1;
-t1.push_back(number);
-Type[tmp].elements.push_back(t1);
-vector<type_ordinal> t2;
-t2.push_back(point);
-Type[tmp].elements.push_back(t2);
+Type[tmp].elements.push_back(new type_tree(number));
 Type[tmp].element_names.push_back("i");
+Type[tmp].elements.push_back(new type_tree(point));
 Type[tmp].element_names.push_back("p");
 }
 
@@ -36,7 +32,7 @@ recipe main [
 +mem: storing 34 in location 5
 +mem: storing 35 in location 6
 
-:(before "End size_of(types) Cases")
+:(before "End size_of(type) Cases")
 if (t.kind == exclusive_container) {
   // size of an exclusive container is the size of its largest variant
   // (So like containers, it can't contain arrays.)
@@ -89,7 +85,7 @@ case MAYBE_CONVERT: {
   }
   reagent base = inst.ingredients.at(0);
   canonize_type(base);
-  if (base.types.empty() || Type[base.types.at(0)].kind != exclusive_container) {
+  if (!base.type || !base.type->value || Type[base.type->value].kind != exclusive_container) {
     raise_error << maybe(Recipe[r].name) << "first ingredient of 'maybe-convert' should be an exclusive-container, but got " << base.original_string << '\n' << end();
     break;
   }
@@ -101,7 +97,8 @@ case MAYBE_CONVERT: {
 }
 :(before "End Primitive Recipe Implementations")
 case MAYBE_CONVERT: {
-  reagent base = canonize(current_instruction().ingredients.at(0));
+  reagent base = current_instruction().ingredients.at(0);
+  canonize(base);
   long long int base_address = base.value;
   if (base_address == 0) {
     raise_error << maybe(current_recipe_name()) << "tried to access location 0 in '" << current_instruction().to_string() << "'\n" << end();
@@ -160,9 +157,10 @@ recipe main [
 :(before "End size_mismatch(x) Cases")
 if (current_instruction().operation == MERGE
     && !current_instruction().products.empty()
-    && !current_instruction().products.at(0).types.empty()) {
-  reagent x = canonize(current_instruction().products.at(0));
-  if (Type[x.types.at(0)].kind == exclusive_container) {
+    && current_instruction().products.at(0).type) {
+  reagent x = current_instruction().products.at(0);
+  canonize(x);
+  if (Type[x.type->value].kind == exclusive_container) {
     return size_of(x) < SIZE(data);
   }
 }
diff --git a/037recipe.cc b/037recipe.cc
index 2c5d7d81..23cfb5b2 100644
--- a/037recipe.cc
+++ b/037recipe.cc
@@ -67,9 +67,9 @@ case CALL: {
 
 :(code)
 bool is_mu_recipe(reagent r) {
-  if (r.types.empty()) return false;
-  if (r.types.at(0) == Type_ordinal["recipe"]) return true;
-  if (r.types.at(0) == Type_ordinal["recipe-ordinal"]) return true;
+  if (!r.type) return false;
+  if (r.type->value == Type_ordinal["recipe"]) return true;
+  if (r.type->value == Type_ordinal["recipe-ordinal"]) return true;
   // End is_mu_recipe Cases
   return false;
 }
diff --git a/039wait.cc b/039wait.cc
index 314ab1cd..bdb81651 100644
--- a/039wait.cc
+++ b/039wait.cc
@@ -40,7 +40,8 @@ case WAIT_FOR_LOCATION: {
 }
 :(before "End Primitive Recipe Implementations")
 case WAIT_FOR_LOCATION: {
-  reagent loc = canonize(current_instruction().ingredients.at(0));
+  reagent loc = current_instruction().ingredients.at(0);
+  canonize(loc);
   Current_routine->state = WAITING;
   Current_routine->waiting_on_location = loc.value;
   Current_routine->old_value_of_waiting_location = Memory[loc.value];
diff --git a/040brace.cc b/040brace.cc
index ba8e9fd6..3a95e9f6 100644
--- a/040brace.cc
+++ b/040brace.cc
@@ -104,7 +104,7 @@ void transform_braces(const recipe_ordinal r) {
     }
     // if implicit, compute target
     reagent target;
-    target.types.push_back(Type_ordinal["offset"]);
+    target.type = new type_tree(Type_ordinal["offset"]);
     target.set_value(0);
     if (open_braces.empty())
       raise_error << inst.name << " needs a '{' before\n" << end();
diff --git a/042name.cc b/042name.cc
index 37544955..7850d57f 100644
--- a/042name.cc
+++ b/042name.cc
@@ -66,7 +66,7 @@ void transform_names(const recipe_ordinal r) {
 }
 
 bool disqualified(/*mutable*/ reagent& x, const instruction& inst, const string& recipe_name) {
-  if (x.types.empty()) {
+  if (!x.type) {
     raise_error << maybe(recipe_name) << "missing type for " << x.original_string << " in '" << inst.to_string() << "'\n" << end();
     return true;
   }
@@ -86,9 +86,10 @@ long long int lookup_name(const reagent& r, const recipe_ordinal default_recipe)
   return Name[default_recipe][r.name];
 }
 
-type_ordinal skip_addresses(const vector<type_ordinal>& types, const string& recipe_name) {
-  for (long long int i = 0; i < SIZE(types); ++i) {
-    if (types.at(i) != Type_ordinal["address"]) return types.at(i);
+type_ordinal skip_addresses(type_tree* type, const string& recipe_name) {
+  for (; type; type = type->right) {
+    if (type->value != Type_ordinal["address"])
+      return type->value;
   }
   raise_error << maybe(recipe_name) << "expected a container" << '\n' << end();
   return -1;
@@ -201,7 +202,7 @@ if (inst.operation == Recipe_ordinal["get"]
     raise_error << maybe(Recipe[r].name) << "expected ingredient 1 of " << (inst.operation == Recipe_ordinal["get"] ? "'get'" : "'get-address'") << " to have type 'offset'; got " << inst.ingredients.at(1).original_string << '\n' << end();
   if (inst.ingredients.at(1).name.find_first_not_of("0123456789") != string::npos) {
     // since first non-address in base type must be a container, we don't have to canonize
-    type_ordinal base_type = skip_addresses(inst.ingredients.at(0).types, Recipe[r].name);
+    type_ordinal base_type = skip_addresses(inst.ingredients.at(0).type, Recipe[r].name);
     inst.ingredients.at(1).set_value(find_element_name(base_type, inst.ingredients.at(1).name, Recipe[r].name));
     trace("name") << "element " << inst.ingredients.at(1).name << " of type " << Type[base_type].name << " is at offset " << no_scientific(inst.ingredients.at(1).value) << end();
   }
@@ -240,7 +241,7 @@ if (inst.operation == Recipe_ordinal["maybe-convert"]) {
   assert(is_literal(inst.ingredients.at(1)));
   if (inst.ingredients.at(1).name.find_first_not_of("0123456789") != string::npos) {
     // since first non-address in base type must be an exclusive container, we don't have to canonize
-    type_ordinal base_type = skip_addresses(inst.ingredients.at(0).types, Recipe[r].name);
+    type_ordinal base_type = skip_addresses(inst.ingredients.at(0).type, Recipe[r].name);
     inst.ingredients.at(1).set_value(find_element_name(base_type, inst.ingredients.at(1).name, Recipe[r].name));
     trace("name") << "variant " << inst.ingredients.at(1).name << " of type " << Type[base_type].name << " has tag " << no_scientific(inst.ingredients.at(1).value) << end();
   }
diff --git a/043new.cc b/043new.cc
index e28284ae..d33d685a 100644
--- a/043new.cc
+++ b/043new.cc
@@ -71,8 +71,7 @@ case NEW: {
   long long int size = 0;
   long long int array_length = 0;
   {
-    vector<type_ordinal> type;
-    type.push_back(current_instruction().ingredients.at(0).value);
+    type_tree* type = new type_tree(current_instruction().ingredients.at(0).value);
     if (SIZE(current_instruction().ingredients) > 1) {
       // array
       array_length = ingredients.at(1).at(0);
@@ -83,6 +82,7 @@ case NEW: {
       // scalar
       size = size_of(type);
     }
+    delete type;
   }
 //?   Total_alloc += size;
 //?   Num_alloc++;
@@ -225,7 +225,7 @@ case ABANDON: {
   }
   reagent types = inst.ingredients.at(0);
   canonize_type(types);
-  if (types.types.empty() || types.types.at(0) != Type_ordinal["address"]) {
+  if (!types.type || types.type->value != Type_ordinal["address"]) {
     raise_error << maybe(Recipe[r].name) << "first ingredient of 'abandon' should be an address, but got " << inst.ingredients.at(0).original_string << '\n' << end();
     break;
   }
@@ -234,9 +234,13 @@ case ABANDON: {
 :(before "End Primitive Recipe Implementations")
 case ABANDON: {
   long long int address = ingredients.at(0).at(0);
-  reagent types = canonize(current_instruction().ingredients.at(0));
-  reagent target_type = lookup_memory(types);
-  abandon(address, size_of(target_type));
+  reagent types = current_instruction().ingredients.at(0);
+  canonize(types);
+  // lookup_memory without drop_one_lookup {
+  types.set_value(Memory[types.value]);
+  drop_address_from_type(types);
+  // }
+  abandon(address, size_of(types));
   break;
 }
 
@@ -413,10 +417,13 @@ long long int unicode_length(const string& s) {
 }
 
 bool is_mu_string(const reagent& x) {
-  return SIZE(x.types) == 3
-      && x.types.at(0) == Type_ordinal["address"]
-      && x.types.at(1) == Type_ordinal["array"]
-      && x.types.at(2) == Type_ordinal["character"];
+  return x.type
+    && x.type->value == Type_ordinal["address"]
+    && x.type->right
+    && x.type->right->value == Type_ordinal["array"]
+    && x.type->right->right
+    && x.type->right->right->value == Type_ordinal["character"]
+    && x.type->right->right->right == NULL;
 }
 
 string read_mu_string(long long int address) {
diff --git a/044space.cc b/044space.cc
index fa71595f..53d9b802 100644
--- a/044space.cc
+++ b/044space.cc
@@ -46,24 +46,19 @@ long long int default_space;
 :(before "End call Constructor")
 default_space = 0;
 
-:(replace "reagent r = x" following "reagent canonize(reagent x)")
-reagent r = absolutize(x);
+:(before "End canonize(x) Special-cases")
+  absolutize(x);
 :(code)
-reagent absolutize(reagent x) {
-  if (is_raw(x) || is_dummy(x)) return x;
-  if (x.name == "default-space") return x;
+void absolutize(reagent& x) {
+  if (is_raw(x) || is_dummy(x)) return;
+  if (x.name == "default-space") return;
   if (!x.initialized) {
     raise_error << current_instruction().to_string() << ": reagent not initialized: " << x.original_string << '\n' << end();
-    return x;
   }
-  reagent r = x;
-  r.set_value(address(r.value, space_base(r)));
-  r.properties.push_back(pair<string, vector<string> >("raw", vector<string>()));
-  assert(is_raw(r));
-  return r;
+  x.set_value(address(x.value, space_base(x)));
+  x.properties.push_back(pair<string, vector<string> >("raw", vector<string>()));
+  assert(is_raw(x));
 }
-:(before "return result" following "reagent lookup_memory(reagent x)")
-result.properties.push_back(pair<string, vector<string> >("raw", vector<string>()));
 
 //:: fix 'get'
 
@@ -213,10 +208,13 @@ long long int address(long long int offset, long long int base) {
 :(after "void write_memory(reagent x, vector<double> data)")
   if (x.name == "default-space") {
     if (!scalar(data)
-        || SIZE(x.types) != 3
-        || x.types.at(0) != Type_ordinal["address"]
-        || x.types.at(1) != Type_ordinal["array"]
-        || x.types.at(2) != Type_ordinal["location"]) {
+        || !x.type
+        || x.type->value != Type_ordinal["address"]
+        || !x.type->right
+        || x.type->right->value != Type_ordinal["array"]
+        || !x.type->right->right
+        || x.type->right->right->value != Type_ordinal["location"]
+        || x.type->right->right->right) {
       raise_error << maybe(current_recipe_name()) << "'default-space' should be of type address:array:location, but tried to write " << to_string(data) << '\n' << end();
     }
     Current_routine->calls.front().default_space = data.at(0);
diff --git a/046closure_name.cc b/046closure_name.cc
index 82ba5db3..80ef44e8 100644
--- a/046closure_name.cc
+++ b/046closure_name.cc
@@ -46,10 +46,14 @@ void collect_surrounding_spaces(const recipe_ordinal r) {
     for (long long int j = 0; j < SIZE(inst.products); ++j) {
       if (is_literal(inst.products.at(j))) continue;
       if (inst.products.at(j).name != "0") continue;
-      if (SIZE(inst.products.at(j).types) != 3
-          || inst.products.at(j).types.at(0) != Type_ordinal["address"]
-          || inst.products.at(j).types.at(1) != Type_ordinal["array"]
-          || inst.products.at(j).types.at(2) != Type_ordinal["location"]) {
+      type_tree* type = inst.products.at(j).type;
+      if (!type
+          || type->value != Type_ordinal["address"]
+          || !type->right
+          || type->right->value != Type_ordinal["array"]
+          || !type->right->right
+          || type->right->right->value != Type_ordinal["location"]
+          || type->right->right->right) {
         raise_error << "slot 0 should always have type address:array:location, but is " << inst.products.at(j).to_string() << '\n' << end();
         continue;
       }
diff --git a/047global.cc b/047global.cc
index d0a3d47e..496a6f3e 100644
--- a/047global.cc
+++ b/047global.cc
@@ -32,10 +32,13 @@ global_space = 0;
 :(after "void write_memory(reagent x, vector<double> data)")
   if (x.name == "global-space") {
     if (!scalar(data)
-        || SIZE(x.types) != 3
-        || x.types.at(0) != Type_ordinal["address"]
-        || x.types.at(1) != Type_ordinal["array"]
-        || x.types.at(2) != Type_ordinal["location"]) {
+        || !x.type
+        || x.type->value != Type_ordinal["address"]
+        || !x.type->right
+        || x.type->right->value != Type_ordinal["array"]
+        || !x.type->right->right
+        || x.type->right->right->value != Type_ordinal["location"]
+        || x.type->right->right->right) {
       raise_error << maybe(current_recipe_name()) << "'global-space' should be of type address:array:location, but tried to write " << to_string(data) << '\n' << end();
     }
     if (Current_routine->global_space)
diff --git a/048check_type_by_name.cc b/048check_type_by_name.cc
index e96c54f2..7e5c478b 100644
--- a/048check_type_by_name.cc
+++ b/048check_type_by_name.cc
@@ -19,7 +19,7 @@ recipe main [
 
 :(code)
 void check_types_by_name(const recipe_ordinal r) {
-  map<string, vector<type_ordinal> > metadata;
+  map<string, type_tree*> metadata;
   for (long long int i = 0; i < SIZE(Recipe[r].steps); ++i) {
     instruction& inst = Recipe[r].steps.at(i);
     for (long long int in = 0; in < SIZE(inst.ingredients); ++in) {
@@ -33,15 +33,15 @@ void check_types_by_name(const recipe_ordinal r) {
   }
 }
 
-void check_metadata(map<string, vector<type_ordinal> >& metadata, const reagent& x, const recipe_ordinal r) {
+void check_metadata(map<string, type_tree*>& metadata, const reagent& x, const recipe_ordinal r) {
   if (is_literal(x)) return;
   if (is_raw(x)) return;
   // if you use raw locations you're probably doing something unsafe
   if (is_integer(x.name)) return;
-  if (x.types.empty()) return;  // will throw a more precise error elsewhere
+  if (!x.type) return;  // will throw a more precise error elsewhere
   if (metadata.find(x.name) == metadata.end())
-    metadata[x.name] = x.types;
-  if (metadata[x.name] != x.types)
+    metadata[x.name] = x.type;
+  if (!types_match(metadata[x.name], x.type))
     raise_error << maybe(Recipe[r].name) << x.name << " used with multiple types\n" << end();
 }
 
@@ -52,13 +52,12 @@ recipe main [
 ]
 
 :(code)
-void deduce_missing_type(map<string, vector<type_ordinal> >& metadata, reagent& x) {
-  if (!x.types.empty()) return;
+void deduce_missing_type(map<string, type_tree*>& metadata, reagent& x) {
+  if (x.type) return;
   if (metadata.find(x.name) == metadata.end()) return;
-  copy(metadata[x.name].begin(), metadata[x.name].end(), inserter(x.types, x.types.begin()));
+  x.type = new type_tree(*metadata[x.name]);
   assert(x.properties.at(0).second.empty());
-  x.properties.at(0).second.resize(metadata[x.name].size());
-  x.properties.push_back(pair<string, vector<string> >("as-before", vector<string>()));
+  x.properties.at(0).second.push_back("as-before");
 }
 
 :(scenario transform_fills_in_missing_types_in_product)
@@ -88,4 +87,4 @@ recipe main [
   y:address:charcter <- new character:type
   *y <- copy 67
 ]
-+error: unknown type: charcter
++error: main: unknown type in 'y:address:charcter <- new character:type'
diff --git a/053continuation.cc b/053continuation.cc
index 8de32f0f..a66e5401 100644
--- a/053continuation.cc
+++ b/053continuation.cc
@@ -64,8 +64,8 @@ case CONTINUE_FROM: {
 
 :(code)
 bool is_mu_continuation(const reagent& x) {
-  if (x.types.empty()) return false;
-  return x.types.at(0) == Type_ordinal["continuation"];
+  if (!x.type) return false;
+  return x.type->value == Type_ordinal["continuation"];
 }
 
 :(scenario continuation)
@@ -279,4 +279,4 @@ call_stack::iterator find_reset(call_stack& c) {
   }
 
 :(before "End is_mu_recipe Cases")
-if (r.types.at(0) == Type_ordinal["continuation"]) return true;
+if (r.type && r.type->value == Type_ordinal["continuation"]) return true;
diff --git a/054dilated_reagent.cc b/054dilated_reagent.cc
index 0487fe2b..a8cd6226 100644
--- a/054dilated_reagent.cc
+++ b/054dilated_reagent.cc
@@ -86,12 +86,12 @@ if (s.at(0) == '{') {
   }
   // structures for the first row of properties
   name = properties.at(0).first;
-  string type = properties.at(0).second.at(0);
-  if (Type_ordinal.find(type) == Type_ordinal.end()) {
+  string type_name = properties.at(0).second.at(0);
+  if (Type_ordinal.find(type_name) == Type_ordinal.end()) {
       // this type can't be an integer
-    Type_ordinal[type] = Next_type_ordinal++;
+    Type_ordinal[type_name] = Next_type_ordinal++;
   }
-  types.push_back(Type_ordinal[type]);
+  type = new type_tree(Type_ordinal[type_name]);
   return;
 }
 
diff --git a/075scenario_console.cc b/075scenario_console.cc
index ab6aba94..11438bf4 100644
--- a/075scenario_console.cc
+++ b/075scenario_console.cc
@@ -104,10 +104,10 @@ case ASSUME_CONSOLE: {
     }
   }
   assert(Current_routine->alloc == event_data_address+size);
-  // wrap the array of events in an event object
-  ensure_space(size_of_events());
+  // wrap the array of events in a console object
+  ensure_space(size_of_console());
   Memory[CONSOLE] = Current_routine->alloc;
-  Current_routine->alloc += size_of_events();
+  Current_routine->alloc += size_of_console();
   Memory[Memory[CONSOLE]+/*offset of 'data' in container 'events'*/1] = event_data_address;
   break;
 }
@@ -266,19 +266,19 @@ long long int size_of_event() {
   // memoize result if already computed
   static long long int result = 0;
   if (result) return result;
-  vector<type_ordinal> type;
-  type.push_back(Type_ordinal["event"]);
+  type_tree* type = new type_tree(Type_ordinal["event"]);
   result = size_of(type);
+  delete type;
   return result;
 }
 
-long long int size_of_events() {
+long long int size_of_console() {
   // memoize result if already computed
   static long long int result = 0;
   if (result) return result;
-  vector<type_ordinal> type;
   assert(Type_ordinal["console"]);
-  type.push_back(Type_ordinal["console"]);
+  type_tree* type = new type_tree(Type_ordinal["console"]);
   result = size_of(type);
+  delete type;
   return result;
 }