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;