. - mu - Soul of a tiny new machine. More thorough tests → More comprehensible and rewrite-friendly software → More resilient society.

diff options

author	Kartik Agaram <vc@akkartik.com>	2019-06-08 13:04:20 -0700
committer	Kartik Agaram <vc@akkartik.com>	2019-06-08 13:04:20 -0700
commit	28795052fe5579a37eb2df0fc5308268ad9c0bbf (patch)
tree	58f181d333d82a1e8f134fa1ca6ad8788c9cddd3 /factorial.mu
parent	eb75af079a102c2d7b1ec830297d049d40d858a8 (diff)
download	mu-28795052fe5579a37eb2df0fc5308268ad9c0bbf.tar.gz

Diffstat (limited to 'factorial.mu')

0 files changed, 0 insertions, 0 deletions

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> <meta http-equiv="content-type" content="text/html; charset=UTF-8"> <title>Mu - 040brace.cc</title> <meta name="Generator" content="Vim/8.0"> <meta name="plugin-version" content="vim7.4_v2"> <meta name="syntax" content="cpp"> <meta name="settings" content="number_lines,use_css,pre_wrap,no_foldcolumn,expand_tabs,line_ids,prevent_copy="> <meta name="colorscheme" content="minimal-light"> <style type="text/css">  </style> <script type='text/javascript'>  </script> </head> <body onload='JumpToLine();'> <a href='https://github.com/akkartik/mu/blob/master/040brace.cc'>https://github.com/akkartik/mu/blob/master/040brace.cc</a> <pre id='vimCodeElement'> 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 <a href='000organization.cc.html#L113'>main</a> [ 25 { 26 break 27 1:num <- copy 0 28 } 29 ] 30 +transform: --- <a href='012transform.cc.html#L99'>transform</a> braces for <a href='010vm.cc.html#L19'>recipe</a> <a href='000organization.cc.html#L113'>main</a> 31 +transform: jump 1:offset 32 +transform: copy ... 33 34 :(before "End Instruction Modifying Transforms") 35 Transform.push_back(<a href='040brace.cc.html#L38'>transform_braces</a>); // idempotent 36 37 :(code) 38 void <a href='040brace.cc.html#L38'>transform_braces</a>(const <a href='010vm.cc.html#L14'>recipe_ordinal</a> 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 <a href='003trace.cc.html#L189'>trace</a>(9991, "transform") << "--- <a href='012transform.cc.html#L99'>transform</a> braces for <a href='010vm.cc.html#L19'>recipe</a> " << get(Recipe, r).name << <a href='003trace.cc.html#L225'>end</a>(); 43 for (int index = 0; index < <a href='001help.cc.html#L141'>SIZE</a>(get(Recipe, r).steps); ++index) { 44 const instruction& inst = get(Recipe, r).steps.at(index); 45 if (inst.label == "{") { 46 <a href='003trace.cc.html#L189'>trace</a>(9993, "transform") << <a href='013update_operation.cc.html#L25'>maybe</a>(get(Recipe, r).name) << "push (open, " << index << ")" << <a href='003trace.cc.html#L225'>end</a>(); 47 braces.push_back(pair<bool,int>(OPEN, index)); 48 } 49 if (inst.label == "}") { 50 <a href='003trace.cc.html#L189'>trace</a>(9993, "transform") << "push (close, " << index << ")" << <a href='003trace.cc.html#L225'>end</a>(); 51 braces.push_back(pair<bool,int>(CLOSE, index)); 52 } 53 } 54 stack</*step*/int> open_braces; 55 for (int index = 0; index < <a href='001help.cc.html#L141'>SIZE</a>(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 <a href='003trace.cc.html#L196'>raise</a> << <a href='013update_operation.cc.html#L25'>maybe</a>(get(Recipe, r).name) << "unbalanced '}'\n" << <a href='003trace.cc.html#L225'>end</a>(); 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 <a href='003trace.cc.html#L189'>trace</a>(9992, "transform") << inst.name << " ..." << <a href='003trace.cc.html#L225'>end</a>(); 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 <a href='003trace.cc.html#L196'>raise</a> << <a href='013update_operation.cc.html#L25'>maybe</a>(get(Recipe, r).name) << "'" << inst.name << "' expects 1 or 2 ingredients, but got none\n" << <a href='003trace.cc.html#L225'>end</a>(); 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 (<a href='001help.cc.html#L141'>SIZE</a>(inst.ingredients) > 1 && is_literal(inst.ingredients.at(1))) { 104 <a href='003trace.cc.html#L189'>trace</a>(9992, "transform") << inst.name << ' ' << inst.ingredients.at(1).name << ":offset" << <a href='003trace.cc.html#L225'>end</a>(); 105 continue; 106 } 107 } 108 else { 109 // unconditional branches check arg 0 110 if (!inst.ingredients.empty() && is_literal(inst.ingredients.at(0))) { 111 <a href='003trace.cc.html#L189'>trace</a>(9992, "transform") << "jump " << inst.ingredients.at(0).name << ":offset" << <a href='003trace.cc.html#L225'>end</a>(); 112 continue; 113 } 114 } 115 // if implicit, compute target 116 reagent target(new type_tree("offset")); 117 target.<a href='010vm.cc.html#L67'>set_value</a>(0); 118 if (open_braces.empty()) 119 <a href='003trace.cc.html#L196'>raise</a> << <a href='013update_operation.cc.html#L25'>maybe</a>(get(Recipe, r).name) << "'" << old_name << "' needs a '{' before\n" << <a href='003trace.cc.html#L225'>end</a>(); 120 else if (old_name.find("loop") != string::npos) 121 target.<a href='010vm.cc.html#L67'>set_value</a>(open_braces.top()-index); 122 else // break instruction 123 target.<a href='010vm.cc.html#L67'>set_value</a>(<a href='040brace.cc.html#L135'>matching_brace</a>(open_braces.top(), braces, r) - index - 1); 124 inst.ingredients.push_back(target); 125 // log computed target 126 if (inst.name == "jump") 127 <a href='003trace.cc.html#L189'>trace</a>(9992, "transform") << "jump " << no_scientific(target.value) << ":offset" << <a href='003trace.cc.html#L225'>end</a>(); 128 else 129 <a href='003trace.cc.html#L189'>trace</a>(9992, "transform") << inst.name << ' ' << inst.ingredients.at(0).name << ", " << no_scientific(target.value) << ":offset" << <a href='003trace.cc.html#L225'>end</a>(); 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 <a href='040brace.cc.html#L135'>matching_brace</a>(int index, const list<pair<bool, int> >& braces, <a href='010vm.cc.html#L14'>recipe_ordinal</a> r) { 136 int stacksize = 0; 137 for (list<pair<bool, int> >::const_iterator p = braces.begin(); p != braces.<a href='003trace.cc.html#L225'>end</a>(); ++p) { 138 if (p->second < index) continue; 139 stacksize += (p->first ? 1 : -1); 140 if (stacksize == 0) return p->second; 141 } 142 <a href='003trace.cc.html#L196'>raise</a> << <a href='013update_operation.cc.html#L25'>maybe</a>(get(Recipe, r).name) << "unbalanced '{'\n" << <a href='003trace.cc.html#L225'>end</a>(); 143 return <a href='001help.cc.html#L141'>SIZE</a>(get(Recipe, r).steps); // exit current routine 144 } 145 146 :(scenario loop) 147 def <a href='000organization.cc.html#L113'>main</a> [ 148 1:num <- copy 0 149 2:num <- copy 0 150 { 151 3:num <- copy 0 152 loop 153 } 154 ] 155 +transform: --- <a href='012transform.cc.html#L99'>transform</a> braces for <a href='010vm.cc.html#L19'>recipe</a> <a href='000organization.cc.html#L113'>main</a> 156 +transform: copy ... 157 +transform: copy ... 158 +transform: copy ... 159 +transform: jump -2:offset 160 161 :(scenario break_empty_block) 162 def <a href='000organization.cc.html#L113'>main</a> [ 163 1:num <- copy 0 164 { 165 break 166 } 167 ] 168 +transform: --- <a href='012transform.cc.html#L99'>transform</a> braces for <a href='010vm.cc.html#L19'>recipe</a> <a href='000organization.cc.html#L113'>main</a> 169 +transform: copy ... 170 +transform: jump 0:offset 171 172 :(scenario break_cascading) 173 def <a href='000organization.cc.html#L113'>main</a> [ 174 1:num <- copy 0 175 { 176 break 177 } 178 { 179 break 180 } 181 ] 182 +transform: --- <a href='012transform.cc.html#L99'>transform</a> braces for <a href='010vm.cc.html#L19'>recipe</a> <a href='000organization.cc.html#L113'>main</a> 183 +transform: copy ... 184 +transform: jump 0:offset 185 +transform: jump 0:offset 186 187 :(scenario break_cascading_2) 188 def <a href='000organization.cc.html#L113'>main</a> [ 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: --- <a href='012transform.cc.html#L99'>transform</a> braces for <a href='010vm.cc.html#L19'>recipe</a> <a href='000organization.cc.html#L113'>main</a> 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 <a href='000organization.cc.html#L113'>main</a> [ 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: --- <a href='012transform.cc.html#L99'>transform</a> braces for <a href='010vm.cc.html#L19'>recipe</a> <a href='000organization.cc.html#L113'>main</a> 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 <a href='000organization.cc.html#L113'>main</a> [ 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 <a href='000organization.cc.html#L113'>main</a> [ 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 <a href='000organization.cc.html#L113'>main</a> [ 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 <a href='000organization.cc.html#L113'>main</a> [ 267 1:num <- copy 0 268 { 269 break +foo:offset 270 } 271 ] 272 +transform: jump +foo:offset 273 274 :(scenario break_unless) 275 def <a href='000organization.cc.html#L113'>main</a> [ 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: --- <a href='012transform.cc.html#L99'>transform</a> braces for <a href='010vm.cc.html#L19'>recipe</a> <a href='000organization.cc.html#L113'>main</a> 284 +transform: copy ... 285 +transform: copy ... 286 +transform: jump-unless 2, 1:offset 287 +transform: copy ... 288 289 :(scenario loop_unless) 290 def <a href='000organization.cc.html#L113'>main</a> [ 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: --- <a href='012transform.cc.html#L99'>transform</a> braces for <a href='010vm.cc.html#L19'>recipe</a> <a href='000organization.cc.html#L113'>main</a> 299 +transform: copy ... 300 +transform: copy ... 301 +transform: jump-unless 2, -1:offset 302 +transform: copy ... 303 304 :(scenario loop_nested) 305 def <a href='000organization.cc.html#L113'>main</a> [ 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: --- <a href='012transform.cc.html#L99'>transform</a> braces for <a href='010vm.cc.html#L19'>recipe</a> <a href='000organization.cc.html#L113'>main</a> 317 +transform: jump-if 4, -5:offset 318 319 :(scenario loop_label) 320 def <a href='000organization.cc.html#L113'>main</a> [ 321 1:num <- copy 0 322 +foo 323 2:num <- copy 0 324 ] 325 +transform: --- <a href='012transform.cc.html#L99'>transform</a> braces for <a href='010vm.cc.html#L19'>recipe</a> <a href='000organization.cc.html#L113'>main</a> 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 <a href='000organization.cc.html#L113'>main</a> [ 350 break 351 ] 352 +error: <a href='000organization.cc.html#L113'>main</a>: 'break' needs a '{' before 353 354 :(scenario break_conditional_without_ingredient_fails) 355 % Hide_errors = true; 356 def <a href='000organization.cc.html#L113'>main</a> [ 357 { 358 break-if 359 } 360 ] 361 +error: <a href='000organization.cc.html#L113'>main</a>: '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 <a href='000organization.cc.html#L113'>main</a> [ 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 <a href='000organization.cc.html#L113'>main</a> [ 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, <a href='010vm.cc.html#L19'>recipe</a> 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 <a href='040brace.cc.html#L420'>emit_return_block</a>(result, "break-unless", curr); 396 curr.<a href='050scenario.cc.html#L60'>clear</a>(); 397 } 398 else { 399 <a href='003trace.cc.html#L196'>raise</a> << "'" << curr.name << "' never yields any products\n" << <a href='003trace.cc.html#L225'>end</a>(); 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 <a href='040brace.cc.html#L420'>emit_return_block</a>(result, "break-if", curr); 412 curr.<a href='050scenario.cc.html#L60'>clear</a>(); 413 } 414 else { 415 <a href='003trace.cc.html#L196'>raise</a> << "'" << curr.name << "' never yields any products\n" << <a href='003trace.cc.html#L225'>end</a>(); 416 } 417 } 418 419 :(code) 420 void <a href='040brace.cc.html#L420'>emit_return_block</a>(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.<a href='003trace.cc.html#L225'>end</a>(), inserter(return_ingredients, return_ingredients.<a href='003trace.cc.html#L225'>end</a>())); 425 426 // { 427 <a href='010vm.cc.html#L33'>instruction</a> open_label; open_label.is_label=true; open_label.label = "{"; 428 out.steps.push_back(open_label); 429 430 // <break command> <condition> 431 <a href='010vm.cc.html#L33'>instruction</a> 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 <a href='010vm.cc.html#L33'>instruction</a> 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 <a href='010vm.cc.html#L33'>instruction</a> 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 <a href='001help.cc.html#L221'>put</a>(Recipe_ordinal, "break", BREAK); 463 <a href='001help.cc.html#L221'>put</a>(Recipe_ordinal, "break-if", BREAK_IF); 464 <a href='001help.cc.html#L221'>put</a>(Recipe_ordinal, "break-unless", BREAK_UNLESS); 465 <a href='001help.cc.html#L221'>put</a>(Recipe_ordinal, "loop", LOOP); 466 <a href='001help.cc.html#L221'>put</a>(Recipe_ordinal, "loop-if", LOOP_IF); 467 <a href='001help.cc.html#L221'>put</a>(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; </pre> </body> </html>


context:
space:
mode: