1 //: Addresses help us spend less time copying data around.
  2 
  3 //: So far we've been operating on primitives like numbers and characters, and
  4 //: we've started combining these primitives together into larger logical
  5 //: units (containers or arrays) that may contain many different primitives at
  6 //: once. Containers and arrays can grow quite large in complex programs, and
  7 //: we'd like some way to efficiently share them between recipes without
  8 //: constantly having to make copies. Right now 'next-ingredient' and 'return'
  9 //: copy data across recipe boundaries. To avoid copying large quantities of
 10 //: data around, we'll use *addresses*. An address is a bookmark to some
 11 //: arbitrary quantity of data (the *payload*). It's a primitive, so it's as
 12 //: efficient to copy as a number. To read or modify the payload 'pointed to'
 13 //: by an address, we'll perform a *lookup*.
 14 //:
 15 //: The notion of 'lookup' isn't an instruction like 'add' or 'subtract'.
 16 //: Instead it's an operation that can be performed when reading any of the
 17 //: ingredients of an instruction, and when writing to any of the products. To
 18 //: write to the payload of an ingredient rather than its value, simply add
 19 //: the /lookup property to it. Modern computers provide efficient support for
 20 //: addresses and lookups, making this a realistic feature.
 21 
 22 //: todo: give 'new' a custodian ingredient. Following malloc/free is a temporary hack.
 23 
 24 :(scenario new)
 25 # call 'new' two times with identical types without modifying the results; you
 26 # should get back different results
 27 def main [
 28   1:address:num/raw <- new number:type
 29   2:address:num/raw <- new number:type
 30   3:bool/raw <- equal 1:address:num/raw, 2:address:num/raw
 31 ]
 32 +mem: storing 0 in location 3
 33 
 34 :(scenario new_array)
 35 # call 'new' with a second ingredient to allocate an array of some type rather than a single copy
 36 def main [
 37   1:address:array:num/raw <- new number:type, 5
 38   2:address:num/raw <- new number:type
 39   3:num/raw <- subtract 2:address:num/raw, 1:address:array:num/raw
 40 ]
 41 +run: {1: ("address" "array" "number"), "raw": ()} <- new {number: "type"}, {5: "literal"}
 42 +mem: array length is 5
 43 # don't forget the extra location for array length
 44 +mem: storing 6 in location 3
 45 
 46 :(scenario dilated_reagent_with_new)
 47 def main [
 48   1:address:address:num <- new {(address number): type}
 49 ]
 50 +new: size of '(address number)' is 1
 51 
 52 //: 'new' takes a weird 'type' as its first ingredient; don't error on it
 53 :(before "End Mu Types Initialization")
 54 put(Type_ordinal, "type", 0);
 55 :(code)
 56 bool is_mu_type_literal(const reagent& r) {
 57   return is_literal(r) && r.type && r.type->name == "type";
 58 }
 59 
 60 :(before "End Primitive Recipe Declarations")
 61 NEW,
 62 :(before "End Primitive Recipe Numbers")
 63 put(Recipe_ordinal, "new", NEW);
 64 :(before "End Primitive Recipe Checks")
 65 case NEW: {
 66   const recipe& caller = get(Recipe, r);
 67   if (inst.ingredients.empty() || SIZE(inst.ingredients) > 2) {
 68     raise << maybe(caller.name) << "'new' requires one or two ingredients, but got '" << to_original_string(inst) << "'\n" << end();
 69     break;
 70   }
 71   // End NEW Check Special-cases
 72   const reagent& type = inst.ingredients.at(0);
 73   if (!is_mu_type_literal(type)) {
 74     raise << maybe(caller.name) << "first ingredient of 'new' should be a type, but got '" << type.original_string << "'\n" << end();
 75     break;
 76   }
 77   if (SIZE(inst.ingredients) > 1 && !is_mu_number(inst.ingredients.at(1))) {
 78     raise << maybe(caller.name) << "second ingredient of 'new' should be a number (array length), but got '" << type.original_string << "'\n" << end();
 79     break;
 80   }
 81   if (inst.products.empty()) {
 82     raise << maybe(caller.name) << "result of 'new' should never be ignored\n" << end();
 83     break;
 84   }
 85   if (!product_of_new_is_valid(inst)) {
 86     raise << maybe(caller.name) << "product of 'new' has incorrect type: '" << to_original_string(inst) << "'\n" << end();
 87     break;
 88   }
 89   break;
 90 }
 91 :(code)
 92 bool product_of_new_is_valid(const instruction& inst) {
 93   reagent/*copy*/ product = inst.products.at(0);
 94   // Update NEW product in Check
 95   if (!product.type || product.type->atom || product.type->left->value != get(Type_ordinal, "address"))
 96     return false;
 97   drop_from_type(product, "address");
 98   if (SIZE(inst.ingredients) > 1) {
 99     // array allocation
100     if (!product.type || product.type->atom || product.type->left->value != get(Type_ordinal, "array"))
101       return false;
102     drop_from_type(product, "array");
103   }
104   reagent/*local*/ expected_product;
105   expected_product.type = new_type_tree(inst.ingredients.at(0).name);
106   return types_strictly_match(product, expected_product);
107 }
108 
109 void drop_from_type(reagent& r, string expected_type) {
110   assert(!r.type->atom);
111   if (r.type->left->name != expected_type) {
112     raise << "can't drop2 " << expected_type << " from '" << to_string(r) << "'\n" << end();
113     return;
114   }
115   // r.type = r.type->right
116   type_tree* tmp = r.type;
117   r.type = tmp->right;
118   tmp->right = NULL;
119   delete tmp;
120   // if (!r.type->right) r.type = r.type->left
121   assert(!r.type->atom);
122   if (r.type->right) return;
123   tmp = r.type;
124   r.type = tmp->left;
125   tmp->left = NULL;
126   delete tmp;
127 }
128 
129 :(scenario new_returns_incorrect_type)
130 % Hide_errors = true;
131 def main [
132   1:bool <- new num:type
133 ]
134 +error: main: product of 'new' has incorrect type: '1:bool <- new num:type'
135 
136 :(scenario new_discerns_singleton_list_from_atom_container)
137 % Hide_errors = true;
138 def main [
139   1:address:num/raw <- new {(num): type}  # should be '{num: type}'
140 ]
141 +error: main: product of 'new' has incorrect type: '1:address:num/raw <- new {(num): type}'
142 
143 :(scenario new_with_type_abbreviation)
144 def main [
145   1:address:num/raw <- new num:type
146 ]
147 $error: 0
148 
149 :(scenario new_with_type_abbreviation_inside_compound)
150 def main [
151   {1: (address address number), raw: ()} <- new {(& num): type}
152 ]
153 $error: 0
154 
155 //: To implement 'new', a Mu transform turns all 'new' instructions into
156 //: 'allocate' instructions that precompute the amount of memory they want to
157 //: allocate.
158 
159 //: Ensure that we never call 'allocate' directly, and that there's no 'new'
160 //: instructions left after the transforms have run.
161 :(before "End Primitive Recipe Checks")
162 case ALLOCATE: {
163   raise << "never call 'allocate' directly'; always use 'new'\n" << end();
164   break;
165 }
166 :(before "End Primitive Recipe Implementations")
167 case NEW: {
168   raise << "no implementation for 'new'; why wasn't it translated to 'allocate'? Please save a copy of your program and send it to Kartik.\n" << end();
169   break;
170 }
171 
172 :(after "Transform.push_back(check_instruction)")  // check_instruction will guard against direct 'allocate' instructions below
173 Transform.push_back(transform_new_to_allocate);  // idempotent
174 
175 :(code)
176 void transform_new_to_allocate(const recipe_ordinal r) {
177   trace(9991, "transform") << "--- convert 'new' to 'allocate' for recipe " << get(Recipe, r).name << end();
178   for (int i = 0;  i < SIZE(get(Recipe, r).steps);  ++i) {
179     instruction& inst = get(Recipe, r).steps.at(i);
180     // Convert 'new' To 'allocate'
181     if (inst.name == "new") {
182       if (inst.ingredients.empty()) return;  // error raised elsewhere
183       inst.operation = ALLOCATE;
184       type_tree* type = new_type_tree(inst.ingredients.at(0).name);
185       inst.ingredients.at(0).set_value(size_of(type));
186       trace(9992, "new") << "size of '" << inst.ingredients.at(0).name << "' is " << inst.ingredients.at(0).value << end();
187       delete type;
188     }
189   }
190 }
191 
192 //: implement 'allocate' based on size
193 
194 :(before "End Globals")
195 extern const int Reserved_for_tests = 1000;
196 int Memory_allocated_until = Reserved_for_tests;
197 int Initial_memory_per_routine = 100000;
198 :(before "End Reset")
199 Memory_allocated_until = Reserved_for_tests;
200 Initial_memory_per_routine = 100000;
201 :(before "End routine Fields")
202 int alloc, alloc_max;
203 :(before "End routine Constructor")
204 alloc = Memory_allocated_until;
205 Memory_allocated_until += Initial_memory_per_routine;
206 alloc_max = Memory_allocated_until;
207 trace("new") << "routine allocated memory from " << alloc << " to " << alloc_max << end();
208 
209 :(before "End Primitive Recipe Declarations")
210 ALLOCATE,
211 :(before "End Primitive Recipe Numbers")
212 put(Recipe_ordinal, "allocate", ALLOCATE);
213 :(before "End Primitive Recipe Implementations")
214 case ALLOCATE: {
215   // compute the space we need
216   int size = ingredients.at(0).at(0);
217   if (SIZE(ingredients) > 1) {
218     // array allocation
219     trace("mem") << "array length is " << ingredients.at(1).at(0) << end();
220     size = /*space for length*/1 + size*ingredients.at(1).at(0);
221   }
222   int result = allocate(size);
223   if (SIZE(current_instruction().ingredients) > 1) {
224     // initialize array length
225     trace("mem") << "storing " << ingredients.at(1).at(0) << " in location " << result << end();
226     put(Memory, result, ingredients.at(1).at(0));
227   }
228   products.resize(1);
229   products.at(0).push_back(result);
230   break;
231 }
232 :(code)
233 int allocate(int size) {
234   trace("mem") << "allocating size " << size << end();
235 //?   Total_alloc += size;
236 //?   ++Num_alloc;
237   // Allocate Special-cases
238   // compute the region of memory to return
239   // really crappy at the moment
240   ensure_space(size);
241   const int result = Current_routine->alloc;
242   trace("mem") << "new alloc: " << result << end();
243   // initialize allocated space
244   for (int address = result;  address < result+size;  ++address) {
245     trace("mem") << "storing 0 in location " << address << end();
246     put(Memory, address, 0);
247   }
248   Current_routine->alloc += size;
249   // no support yet for reclaiming memory between routines
250   assert(Current_routine->alloc <= Current_routine->alloc_max);
251   return result;
252 }
253 
254 //: statistics for debugging
255 //? :(before "End Globals")
256 //? int Total_alloc = 0;
257 //? int Num_alloc = 0;
258 //? int Total_free = 0;
259 //? int Num_free = 0;
260 //? :(before "End Reset")
261 //? if (!Memory.empty()) {
262 //?   cerr << Total_alloc << "/" << Num_alloc
263 //?        << " vs " << Total_free << "/" << Num_free << '\n';
264 //?   cerr << SIZE(Memory) << '\n';
265 //? }
266 //? Total_alloc = Num_alloc = Total_free = Num_free = 0;
267 
268 :(code)
269 void ensure_space(int size) {
270   if (size > Initial_memory_per_routine) {
271     cerr << "can't allocate " << size << " locations, that's too much compared to " << Initial_memory_per_routine << ".\n";
272     exit(1);
273   }
274   if (Current_routine->alloc + size > Current_routine->alloc_max) {
275     // waste the remaining space and create a new chunk
276     Current_routine->alloc = Memory_allocated_until;
277     Memory_allocated_until += Initial_memory_per_routine;
278     Current_routine->alloc_max = Memory_allocated_until;
279     trace("new") << "routine allocated memory from " << Current_routine->alloc << " to " << Current_routine->alloc_max << end();
280   }
281 }
282 
283 :(scenario new_initializes)
284 % Memory_allocated_until = 10;
285 % put(Memory, Memory_allocated_until, 1);
286 def main [
287   1:address:num <- new number:type
288 ]
289 +mem: storing 0 in location 10
290 
291 :(scenario new_size)
292 def main [
293   11:address:num/raw <- new number:type
294   12:address:num/raw <- new number:type
295   13:num/raw <- subtract 12:address:num/raw, 11:address:num/raw
296 ]
297 # size of number
298 +mem: storing 1 in location 13
299 
300 :(scenario new_array_size)
301 def main [
302   1:address:array:num/raw <- new number:type, 5
303   2:address:num/raw <- new number:type
304   3:num/raw <- subtract 2:address:num/raw, 1:address:array:num/raw
305 ]
306 # 5 locations for array contents + array length
307 +mem: storing 6 in location 3
308 
309 :(scenario new_empty_array)
310 def main [
311   1:address:array:num/raw <- new number:type, 0
312   2:address:num/raw <- new number:type
313   3:num/raw <- subtract 2:address:num/raw, 1:address:array:num/raw
314 ]
315 +run: {1: ("address" "array" "number"), "raw": ()} <- new {number: "type"}, {0: "literal"}
316 +mem: array length is 0
317 # one location for array length
318 +mem: storing 1 in location 3
319 
320 //: If a routine runs out of its initial allocation, it should allocate more.
321 :(scenario new_overflow)
322 % Initial_memory_per_routine = 2;  // barely enough room for point allocation below
323 def main [
324   1:address:num/raw <- new number:type
325   2:address:point/raw <- new point:type  # not enough room in initial page
326 ]
327 +new: routine allocated memory from 1000 to 1002
328 +new: routine allocated memory from 1002 to 1004
329 
330 :(scenario new_without_ingredient)
331 % Hide_errors = true;
332 def main [
333   1:address:number <- new  # missing ingredient
334 ]
335 +error: main: 'new' requires one or two ingredients, but got '1:address:number <- new'