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 int OPEN = 0, CLOSE = 1;
 40   // use signed integer for step index because we'll be doing arithmetic on it
 41   list<pair<int/*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<int,int>(OPEN, index));
 48     }
 49     if (inst.label == "}") {
 50       trace(9993, "transform") << "push (close, " << index << ")" << end();
 51       braces.push_back(pair<int,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;
117     target.type = new type_tree("offset");
118     target.set_value(0);
119     if (open_braces.empty())
120       raise << maybe(get(Recipe, r).name) << "'" << old_name << "' needs a '{' before\n" << end();
121     else if (old_name.find("loop") != string::npos)
122       target.set_value(open_braces.top()-index);
123     else  // break instruction
124       target.set_value(matching_brace(open_braces.top(), braces, r) - index - 1);
125     inst.ingredients.push_back(target);
126     // log computed target
127     if (inst.name == "jump")
128       trace(9992, "transform") << "jump " << no_scientific(target.value) << ":offset" << end();
129     else
130       trace(9992, "transform") << inst.name << ' ' << inst.ingredients.at(0).name << ", " << no_scientific(target.value) << ":offset" << end();
131   }
132 }
133 
134 // returns a signed integer not just so that we can return -1 but also to
135 // enable future signed arithmetic
136 int matching_brace(int index, const list<pair<int, int> >& braces, recipe_ordinal r) {
137   int stacksize = 0;
138   for (list<pair<int, int> >::const_iterator p = braces.begin();  p != braces.end();  ++p) {
139     if (p->second < index) continue;
140     stacksize += (p->first ? 1 : -1);
141     if (stacksize == 0) return p->second;
142   }
143   raise << maybe(get(Recipe, r).name) << "unbalanced '{'\n" << end();
144   return SIZE(get(Recipe, r).steps);  // exit current routine
145 }
146 
147 :(scenario loop)
148 def main [
149   1:num <- copy 0
150   2:num <- copy 0
151   {
152     3:num <- copy 0
153     loop
154   }
155 ]
156 +transform: --- transform braces for recipe main
157 +transform: copy ...
158 +transform: copy ...
159 +transform: copy ...
160 +transform: jump -2:offset
161 
162 :(scenario break_empty_block)
163 def main [
164   1:num <- copy 0
165   {
166     break
167   }
168 ]
169 +transform: --- transform braces for recipe main
170 +transform: copy ...
171 +transform: jump 0:offset
172 
173 :(scenario break_cascading)
174 def main [
175   1:num <- copy 0
176   {
177     break
178   }
179   {
180     break
181   }
182 ]
183 +transform: --- transform braces for recipe main
184 +transform: copy ...
185 +transform: jump 0:offset
186 +transform: jump 0:offset
187 
188 :(scenario break_cascading_2)
189 def main [
190   1:num <- copy 0
191   2:num <- copy 0
192   {
193     break
194     3:num <- copy 0
195   }
196   {
197     break
198   }
199 ]
200 +transform: --- transform braces for recipe main
201 +transform: copy ...
202 +transform: copy ...
203 +transform: jump 1:offset
204 +transform: copy ...
205 +transform: jump 0:offset
206 
207 :(scenario break_if)
208 def main [
209   1:num <- copy 0
210   2:num <- copy 0
211   {
212     break-if 2:num
213     3:num <- copy 0
214   }
215   {
216     break
217   }
218 ]
219 +transform: --- transform braces for recipe main
220 +transform: copy ...
221 +transform: copy ...
222 +transform: jump-if 2, 1:offset
223 +transform: copy ...
224 +transform: jump 0:offset
225 
226 :(scenario break_nested)
227 def main [
228   1:num <- copy 0
229   {
230     2:num <- copy 0
231     break
232     {
233       3:num <- copy 0
234     }
235     4:num <- copy 0
236   }
237 ]
238 +transform: jump 4:offset
239 
240 :(scenario break_nested_degenerate)
241 def main [
242   1:num <- copy 0
243   {
244     2:num <- copy 0
245     break
246     {
247     }
248     4:num <- copy 0
249   }
250 ]
251 +transform: jump 3:offset
252 
253 :(scenario break_nested_degenerate_2)
254 def main [
255   1:num <- copy 0
256   {
257     2:num <- copy 0
258     break
259     {
260     }
261   }
262 ]
263 +transform: jump 2:offset
264 
265 :(scenario break_label)
266 % Hide_errors = true;
267 def main [
268   1:num <- copy 0
269   {
270     break +foo:offset
271   }
272 ]
273 +transform: jump +foo:offset
274 
275 :(scenario break_unless)
276 def main [
277   1:num <- copy 0
278   2:num <- copy 0
279   {
280     break-unless 2:num
281     3:num <- copy 0
282   }
283 ]
284 +transform: --- transform braces for recipe main
285 +transform: copy ...
286 +transform: copy ...
287 +transform: jump-unless 2, 1:offset
288 +transform: copy ...
289 
290 :(scenario loop_unless)
291 def main [
292   1:num <- copy 0
293   2:num <- copy 0
294   {
295     loop-unless 2:num
296     3:num <- copy 0
297   }
298 ]
299 +transform: --- transform braces for recipe main
300 +transform: copy ...
301 +transform: copy ...
302 +transform: jump-unless 2, -1:offset
303 +transform: copy ...
304 
305 :(scenario loop_nested)
306 def main [
307   1:num <- copy 0
308   {
309     2:num <- copy 0
310     {
311       3:num <- copy 0
312     }
313     loop-if 4:bool
314     5:num <- copy 0
315   }
316 ]
317 +transform: --- transform braces for recipe main
318 +transform: jump-if 4, -5:offset
319 
320 :(scenario loop_label)
321 def main [
322   1:num <- copy 0
323   +foo
324   2:num <- copy 0
325 ]
326 +transform: --- transform braces for recipe main
327 +transform: copy ...
328 +transform: copy ...
329 
330 //: test how things actually run
331 :(scenarios run)
332 :(scenario brace_conversion_and_run)
333 def test-factorial [
334   1:num <- copy 5
335   2:num <- copy 1
336   {
337     3:bool <- equal 1:num, 1
338     break-if 3:bool
339 #    $print 1:num
340     2:num <- multiply 2:num, 1:num
341     1:num <- subtract 1:num, 1
342     loop
343   }
344   4:num <- copy 2:num  # trigger a read
345 ]
346 +mem: location 2 is 120
347 
348 :(scenario break_outside_braces_fails)
349 % Hide_errors = true;
350 def main [
351   break
352 ]
353 +error: main: 'break' needs a '{' before
354 
355 :(scenario break_conditional_without_ingredient_fails)
356 % Hide_errors = true;
357 def main [
358   {
359     break-if
360   }
361 ]
362 +error: main: 'break-if' expects 1 or 2 ingredients, but got none
363 
364 //: Using break we can now implement conditional returns.
365 
366 :(scenario return_if)
367 def main [
368   1:num <- test1
369 ]
370 def test1 [
371   return-if 0, 34
372   return 35
373 ]
374 +mem: storing 35 in location 1
375 
376 :(scenario return_if_2)
377 def main [
378   1:num <- test1
379 ]
380 def test1 [
381   return-if 1, 34
382   return 35
383 ]
384 +mem: storing 34 in location 1
385 
386 :(before "End Rewrite Instruction(curr, recipe result)")
387 // rewrite 'return-if a, b, c, ...' to
388 //   ```
389 //   {
390 //     break-unless a
391 //     return b, c, ...
392 //   }
393 //   ```
394 if (curr.name == "return-if" || curr.name == "reply-if") {
395   if (curr.products.empty()) {
396     emit_return_block(result, "break-unless", curr);
397     curr.clear();
398   }
399   else {
400     raise << "'" << curr.name << "' never yields any products\n" << end();
401   }
402 }
403 // rewrite 'return-unless a, b, c, ...' to
404 //   ```
405 //   {
406 //     break-if a
407 //     return b, c, ...
408 //   }
409 //   ```
410 if (curr.name == "return-unless" || curr.name == "reply-unless") {
411   if (curr.products.empty()) {
412     emit_return_block(result, "break-if", curr);
413     curr.clear();
414   }
415   else {
416     raise << "'" << curr.name << "' never yields any products\n" << end();
417   }
418 }
419 
420 :(code)
421 void emit_return_block(recipe& out, const string& break_command, const instruction& inst) {
422   const vector<reagent>& ingredients = inst.ingredients;
423   reagent/*copy*/ condition = ingredients.at(0);
424   vector<reagent> return_ingredients;
425   copy(++ingredients.begin(), ingredients.end(), inserter(return_ingredients, return_ingredients.end()));
426 
427   // {
428   instruction open_label;  open_label.is_label=true;  open_label.label = "{";
429   out.steps.push_back(open_label);
430 
431   // <break command> <condition>
432   instruction break_inst;
433   break_inst.operation = get(Recipe_ordinal, break_command);
434   break_inst.name = break_command;
435   break_inst.ingredients.push_back(condition);
436   out.steps.push_back(break_inst);
437 
438   // return <return ingredients>
439   instruction return_inst;
440   return_inst.operation = get(Recipe_ordinal, "return");
441   return_inst.name = "return";
442   return_inst.ingredients.swap(return_ingredients);
443   return_inst.original_string = inst.original_string;
444   out.steps.push_back(return_inst);
445 
446   // }
447   instruction close_label;  close_label.is_label=true;  close_label.label = "}";
448   out.steps.push_back(close_label);
449 }
450 
451 //: Make sure these pseudo recipes get consistent numbers in all tests, even
452 //: though they aren't implemented. Allows greater flexibility in ordering
453 //: transforms.
454 
455 :(before "End Primitive Recipe Declarations")
456 BREAK,
457 BREAK_IF,
458 BREAK_UNLESS,
459 LOOP,
460 LOOP_IF,
461 LOOP_UNLESS,
462 :(before "End Primitive Recipe Numbers")
463 put(Recipe_ordinal, "break", BREAK);
464 put(Recipe_ordinal, "break-if", BREAK_IF);
465 put(Recipe_ordinal, "break-unless", BREAK_UNLESS);
466 put(Recipe_ordinal, "loop", LOOP);
467 put(Recipe_ordinal, "loop-if", LOOP_IF);
468 put(Recipe_ordinal, "loop-unless", LOOP_UNLESS);
469 :(before "End Primitive Recipe Checks")
470 case BREAK: break;
471 case BREAK_IF: break;
472 case BREAK_UNLESS: break;
473 case LOOP: break;
474 case LOOP_IF: break;
475 case LOOP_UNLESS: break;