1 //: Structured programming
  2 //:
  3 //: Our jump recipes are quite inconvenient to use, so Mu provides a
  4 //: lightweight tool called 'transform_braces' to work in a slightly more
  5 //: convenient format with nested braces:
  6 //:
  7 //:   {
  8 //:     some instructions
  9 //:     {
 10 //:       more instructions
 11 //:     }
 12 //:   }
 13 //:
 14 //: Braces are just labels, they require no special parsing. The pseudo
 15 //: instructions 'loop' and 'break' jump to just after the enclosing '{' and
 16 //: '}' respectively.
 17 //:
 18 //: Conditional and unconditional 'loop' and 'break' should give us 80% of the
 19 //: benefits of the control-flow primitives we're used to in other languages,
 20 //: like 'if', 'while', 'for', etc.
 21 
 22 :(scenarios transform)
 23 :(scenario brace_conversion)
 24 def main [
 25   {
 26     break
 27     1:num <- copy 0
 28   }
 29 ]
 30 +transform: --- transform braces for recipe main
 31 +transform: jump 1:offset
 32 +transform: copy ...
 33 
 34 :(before "End Instruction Modifying Transforms")
 35 Transform.push_back(transform_braces);  // idempotent
 36 
 37 :(code)
 38 void transform_braces(const recipe_ordinal r) {
 39   const bool OPEN = false, CLOSE = true;
 40   // use signed integer for step index because we'll be doing arithmetic on it
 41   list<pair<bool/*OPEN/CLOSE*/, /*step*/int> > braces;
 42   trace(9991, "transform") << "--- transform braces for recipe " << get(Recipe, r).name << end();
 43   for (int index = 0;  index < SIZE(get(Recipe, r).steps);  ++index) {
 44     const instruction& inst = get(Recipe, r).steps.at(index);
 45     if (inst.label == "{") {
 46       trace(9993, "transform") << maybe(get(Recipe, r).name) << "push (open, " << index << ")" << end();
 47       braces.push_back(pair<bool,int>(OPEN, index));
 48     }
 49     if (inst.label == "}") {
 50       trace(9993, "transform") << "push (close, " << index << ")" << end();
 51       braces.push_back(pair<bool,int>(CLOSE, index));
 52     }
 53   }
 54   stack</*step*/int> open_braces;
 55   for (int index = 0;  index < SIZE(get(Recipe, r).steps);  ++index) {
 56     instruction& inst = get(Recipe, r).steps.at(index);
 57     if (inst.label == "{") {
 58       open_braces.push(index);
 59       continue;
 60     }
 61     if (inst.label == "}") {
 62       if (open_braces.empty()) {
 63         raise << maybe(get(Recipe, r).name) << "unbalanced '}'\n" << end();
 64         return;
 65       }
 66       open_braces.pop();
 67       continue;
 68     }
 69     if (inst.is_label) continue;
 70     if (inst.name != "loop"
 71          && inst.name != "loop-if"
 72          && inst.name != "loop-unless"
 73          && inst.name != "break"
 74          && inst.name != "break-if"
 75          && inst.name != "break-unless") {
 76       trace(9992, "transform") << inst.name << " ..." << end();
 77       continue;
 78     }
 79     // check for errors
 80     if (inst.name.find("-if") != string::npos || inst.name.find("-unless") != string::npos) {
 81       if (inst.ingredients.empty()) {
 82         raise << maybe(get(Recipe, r).name) << "'" << inst.name << "' expects 1 or 2 ingredients, but got none\n" << end();
 83         continue;
 84       }
 85     }
 86     // update instruction operation
 87     string old_name = inst.name;  // save a copy
 88     if (inst.name.find("-if") != string::npos) {
 89       inst.name = "jump-if";
 90       inst.operation = JUMP_IF;
 91     }
 92     else if (inst.name.find("-unless") != string::npos) {
 93       inst.name = "jump-unless";
 94       inst.operation = JUMP_UNLESS;
 95     }
 96     else {
 97       inst.name = "jump";
 98       inst.operation = JUMP;
 99     }
100     // check for explicitly provided targets
101     if (inst.name.find("-if") != string::npos || inst.name.find("-unless") != string::npos) {
102       // conditional branches check arg 1
103       if (SIZE(inst.ingredients) > 1 && is_literal(inst.ingredients.at(1))) {
104         trace(9992, "transform") << inst.name << ' ' << inst.ingredients.at(1).name << ":offset" << end();
105         continue;
106       }
107     }
108     else {
109       // unconditional branches check arg 0
110       if (!inst.ingredients.empty() && is_literal(inst.ingredients.at(0))) {
111         trace(9992, "transform") << "jump " << inst.ingredients.at(0).name << ":offset" << end();
112         continue;
113       }
114     }
115     // if implicit, compute target
116     reagent target(new type_tree("offset"));
117     target.set_value(0);
118     if (open_braces.empty())
119       raise << maybe(get(Recipe, r).name) << "'" << old_name << "' needs a '{' before\n" << end();
120     else if (old_name.find("loop") != string::npos)
121       target.set_value(open_braces.top()-index);
122     else  // break instruction
123       target.set_value(matching_brace(open_braces.top(), braces, r) - index - 1);
124     inst.ingredients.push_back(target);
125     // log computed target
126     if (inst.name == "jump")
127       trace(9992, "transform") << "jump " << no_scientific(target.value) << ":offset" << end();
128     else
129       trace(9992, "transform") << inst.name << ' ' << inst.ingredients.at(0).name << ", " << no_scientific(target.value) << ":offset" << end();
130   }
131 }
132 
133 // returns a signed integer not just so that we can return -1 but also to
134 // enable future signed arithmetic
135 int matching_brace(int index, const list<pair<bool, int> >& braces, recipe_ordinal r) {
136   int stacksize = 0;
137   for (list<pair<bool, int> >::const_iterator p = braces.begin();  p != braces.end();  ++p) {
138     if (p->second < index) continue;
139     stacksize += (p->first ? 1 : -1);
140     if (stacksize == 0) return p->second;
141   }
142   raise << maybe(get(Recipe, r).name) << "unbalanced '{'\n" << end();
143   return SIZE(get(Recipe, r).steps);  // exit current routine
144 }
145 
146 :(scenario loop)
147 def main [
148   1:num <- copy 0
149   2:num <- copy 0
150   {
151     3:num <- copy 0
152     loop
153   }
154 ]
155 +transform: --- transform braces for recipe main
156 +transform: copy ...
157 +transform: copy ...
158 +transform: copy ...
159 +transform: jump -2:offset
160 
161 :(scenario break_empty_block)
162 def main [
163   1:num <- copy 0
164   {
165     break
166   }
167 ]
168 +transform: --- transform braces for recipe main
169 +transform: copy ...
170 +transform: jump 0:offset
171 
172 :(scenario break_cascading)
173 def main [
174   1:num <- copy 0
175   {
176     break
177   }
178   {
179     break
180   }
181 ]
182 +transform: --- transform braces for recipe main
183 +transform: copy ...
184 +transform: jump 0:offset
185 +transform: jump 0:offset
186 
187 :(scenario break_cascading_2)
188 def main [
189   1:num <- copy 0
190   2:num <- copy 0
191   {
192     break
193     3:num <- copy 0
194   }
195   {
196     break
197   }
198 ]
199 +transform: --- transform braces for recipe main
200 +transform: copy ...
201 +transform: copy ...
202 +transform: jump 1:offset
203 +transform: copy ...
204 +transform: jump 0:offset
205 
206 :(scenario break_if)
207 def main [
208   1:num <- copy 0
209   2:num <- copy 0
210   {
211     break-if 2:num
212     3:num <- copy 0
213   }
214   {
215     break
216   }
217 ]
218 +transform: --- transform braces for recipe main
219 +transform: copy ...
220 +transform: copy ...
221 +transform: jump-if 2, 1:offset
222 +transform: copy ...
223 +transform: jump 0:offset
224 
225 :(scenario break_nested)
226 def main [
227   1:num <- copy 0
228   {
229     2:num <- copy 0
230     break
231     {
232       3:num <- copy 0
233     }
234     4:num <- copy 0
235   }
236 ]
237 +transform: jump 4:offset
238 
239 :(scenario break_nested_degenerate)
240 def main [
241   1:num <- copy 0
242   {
243     2:num <- copy 0
244     break
245     {
246     }
247     4:num <- copy 0
248   }
249 ]
250 +transform: jump 3:offset
251 
252 :(scenario break_nested_degenerate_2)
253 def main [
254   1:num <- copy 0
255   {
256     2:num <- copy 0
257     break
258     {
259     }
260   }
261 ]
262 +transform: jump 2:offset
263 
264 :(scenario break_label)
265 % Hide_errors = true;
266 def main [
267   1:num <- copy 0
268   {
269     break +foo:offset
270   }
271 ]
272 +transform: jump +foo:offset
273 
274 :(scenario break_unless)
275 def main [
276   1:num <- copy 0
277   2:num <- copy 0
278   {
279     break-unless 2:num
280     3:num <- copy 0
281   }
282 ]
283 +transform: --- transform braces for recipe main
284 +transform: copy ...
285 +transform: copy ...
286 +transform: jump-unless 2, 1:offset
287 +transform: copy ...
288 
289 :(scenario loop_unless)
290 def main [
291   1:num <- copy 0
292   2:num <- copy 0
293   {
294     loop-unless 2:num
295     3:num <- copy 0
296   }
297 ]
298 +transform: --- transform braces for recipe main
299 +transform: copy ...
300 +transform: copy ...
301 +transform: jump-unless 2, -1:offset
302 +transform: copy ...
303 
304 :(scenario loop_nested)
305 def main [
306   1:num <- copy 0
307   {
308     2:num <- copy 0
309     {
310       3:num <- copy 0
311     }
312     loop-if 4:bool
313     5:num <- copy 0
314   }
315 ]
316 +transform: --- transform braces for recipe main
317 +transform: jump-if 4, -5:offset
318 
319 :(scenario loop_label)
320 def main [
321   1:num <- copy 0
322   +foo
323   2:num <- copy 0
324 ]
325 +transform: --- transform braces for recipe main
326 +transform: copy ...
327 +transform: copy ...
328 
329 //: test how things actually run
330 :(scenarios run)
331 :(scenario brace_conversion_and_run)
332 def test-factorial [
333   1:num <- copy 5
334   2:num <- copy 1
335   {
336     3:bool <- equal 1:num, 1
337     break-if 3:bool
338 #    $print 1:num
339     2:num <- multiply 2:num, 1:num
340     1:num <- subtract 1:num, 1
341     loop
342   }
343   4:num <- copy 2:num  # trigger a read
344 ]
345 +mem: location 2 is 120
346 
347 :(scenario break_outside_braces_fails)
348 % Hide_errors = true;
349 def main [
350   break
351 ]
352 +error: main: 'break' needs a '{' before
353 
354 :(scenario break_conditional_without_ingredient_fails)
355 % Hide_errors = true;
356 def main [
357   {
358     break-if
359   }
360 ]
361 +error: main: 'break-if' expects 1 or 2 ingredients, but got none
362 
363 //: Using break we can now implement conditional returns.
364 
365 :(scenario return_if)
366 def main [
367   1:num <- test1
368 ]
369 def test1 [
370   return-if 0, 34
371   return 35
372 ]
373 +mem: storing 35 in location 1
374 
375 :(scenario return_if_2)
376 def main [
377   1:num <- test1
378 ]
379 def test1 [
380   return-if 1, 34
381   return 35
382 ]
383 +mem: storing 34 in location 1
384 
385 :(before "End Rewrite Instruction(curr, recipe result)")
386 // rewrite 'return-if a, b, c, ...' to
387 //   ```
388 //   {
389 //     break-unless a
390 //     return b, c, ...
391 //   }
392 //   ```
393 if (curr.name == "return-if" || curr.name == "reply-if") {
394   if (curr.products.empty()) {
395     emit_return_block(result, "break-unless", curr);
396     curr.clear();
397   }
398   else {
399     raise << "'" << curr.name << "' never yields any products\n" << end();
400   }
401 }
402 // rewrite 'return-unless a, b, c, ...' to
403 //   ```
404 //   {
405 //     break-if a
406 //     return b, c, ...
407 //   }
408 //   ```
409 if (curr.name == "return-unless" || curr.name == "reply-unless") {
410   if (curr.products.empty()) {
411     emit_return_block(result, "break-if", curr);
412     curr.clear();
413   }
414   else {
415     raise << "'" << curr.name << "' never yields any products\n" << end();
416   }
417 }
418 
419 :(code)
420 void emit_return_block(recipe& out, const string& break_command, const instruction& inst) {
421   const vector<reagent>& ingredients = inst.ingredients;
422   reagent/*copy*/ condition = ingredients.at(0);
423   vector<reagent> return_ingredients;
424   copy(++ingredients.begin(), ingredients.end(), inserter(return_ingredients, return_ingredients.end()));
425 
426   // {
427   instruction open_label;  open_label.is_label=true;  open_label.label = "{";
428   out.steps.push_back(open_label);
429 
430   // <break command> <condition>
431   instruction break_inst;
432   break_inst.operation = get(Recipe_ordinal, break_command);
433   break_inst.name = break_command;
434   break_inst.ingredients.push_back(condition);
435   out.steps.push_back(break_inst);
436 
437   // return <return ingredients>
438   instruction return_inst;
439   return_inst.operation = get(Recipe_ordinal, "return");
440   return_inst.name = "return";
441   return_inst.ingredients.swap(return_ingredients);
442   return_inst.original_string = inst.original_string;
443   out.steps.push_back(return_inst);
444 
445   // }
446   instruction close_label;  close_label.is_label=true;  close_label.label = "}";
447   out.steps.push_back(close_label);
448 }
449 
450 //: Make sure these pseudo recipes get consistent numbers in all tests, even
451 //: though they aren't implemented. Allows greater flexibility in ordering
452 //: transforms.
453 
454 :(before "End Primitive Recipe Declarations")
455 BREAK,
456 BREAK_IF,
457 BREAK_UNLESS,
458 LOOP,
459 LOOP_IF,
460 LOOP_UNLESS,
461 :(before "End Primitive Recipe Numbers")
462 put(Recipe_ordinal, "break", BREAK);
463 put(Recipe_ordinal, "break-if", BREAK_IF);
464 put(Recipe_ordinal, "break-unless", BREAK_UNLESS);
465 put(Recipe_ordinal, "loop", LOOP);
466 put(Recipe_ordinal, "loop-if", LOOP_IF);
467 put(Recipe_ordinal, "loop-unless", LOOP_UNLESS);
468 :(before "End Primitive Recipe Checks")
469 case BREAK: break;
470 case BREAK_IF: break;
471 case BREAK_UNLESS: break;
472 case LOOP: break;
473 case LOOP_IF: break;
474 case LOOP_UNLESS: break;