Mu - 073wait.cc

  1 //: Routines can be put in a 'waiting' state, from which it will be ready to
  2 //: run again when a specific memory location changes its value. This is Mu's
  3 //: basic technique for orchestrating the order in which different routines
  4 //: operate.
  5 
  6 :(scenario wait_for_location)
  7 def f1 [
  8   10:num <- copy 34
  9   start-running f2
 10   20:location <- copy 10/unsafe
 11   wait-for-reset-then-set 20:location
 12   # wait for f2 to run and reset location 1
 13   30:num <- copy 10:num
 14 ]
 15 def f2 [
 16   10:location <- copy 0/unsafe
 17 ]
 18 +schedule: f1
 19 +run: waiting for location 10 to reset
 20 +schedule: f2
 21 +schedule: waking up routine 1
 22 +schedule: f1
 23 +mem: storing 1 in location 30
 24 
 25 //: define the new state that all routines can be in
 26 
 27 :(before "End routine States")
 28 WAITING,
 29 :(before "End routine Fields")
 30 // only if state == WAITING
 31 int waiting_on_location;
 32 :(before "End routine Constructor")
 33 waiting_on_location = 0;
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en">
	<head>
		<title>andrewyu.org Mailing List Guidelines</title>
		<link rel="stylesheet" href="/plain.css" />
		<link rel="shortcut icon" href="/favicon.ico" type="image/x-icon" />
		<meta charset="utf-8" />
	</head>
	<body class="indent">
		<h1><code>andrewyu.org</code> Mailing List Guidelines</h1>
		<p>The following guidelines apply to most <a href="https://mail.andrewyu.org/mailman/listinfo">public mailing lists on <code>andrewyu.org</code></a>.  Different lists may have different specific guidelines.</p>
		<ul>
			<li>
				Be considerate of other subscribers on the mailing lists.
			</li>
			<li>
				Plain text, preferrably 72 characters per line.
				<br />
				Many subscribers and maintainers read their mail on text-based mailers like mail(1), emacs, mutt, etc., and they often find HTML-formatted messages (or lines that stretch beyond 72 characters) unreadable. Many mailing lists strip messages of MIME content before sending them out to the rest of the list. If you don't use plain text, your messages will be reformatted. If they cannot be reformatted, they will be summarily rejected. Use attachments with care, they will be removed from messages on some lists.
			</li>
			<li>
				Include a useful Subject line.
				<br />
				Messages with an empty Subject will get bounced to the list manager and will take longer to show up. Including a relevant Subject in the message will ensure that more people actually read what you've written. Also, avoid Subject lines with excessive uppercase and exclamations. "Help!" or "I can't get it to work!" are not useful subject lines. Do not change the subject line while on the same topic. You may know what it is regarding, the rest of us who get several hundred messages a day will have no idea.
			</li>
			<li>
				Trim your signature.
				<br />
				Keep the signature lines at the bottom of your mail to a reasonable length.  PGP signatures should be attachments rather than inline.
			</li>
			<li>
				Stay on topic.
				<br />
				Please keep the subject of the post relevant to the topic of the mailing list.
			</li>
			<li>
				Include important information for questions.
				<br />
				Don't waste everyone's time with a hopelessly incomplete question. No one other than you has the information needed to resolve your problem, it is better to provide more information than needed than not enough detail.
			</li>
			<li>
				Respect differences in opinion and philosophy.
				<br />
				Intelligent people may look at the same set of facts and come to very different conclusions. Repeating the same points that didn't convince someone previously rarely changes their mind, and irritates all the other readers.
			</li>
			<li>
				No spam.
			</li>
			<li>
				Interweave quoted original messages with replies.
				<br />
				Post inline, and trim quotes. This means that your replies are interspersed with the original mail, and any irrelevant content is removed (trimmed):
				<pre>From: A
Subject: Re: S
To: B
CC: list

B wrote:
&gt; ...
&gt; Do you think that this is correct?

Yes, I believe so.

&gt; How about iterating through the items and applying the function to each of them?

Sounds good.</pre>
			</li>
			<li>
				Reply to the list.
				<br />
				For most discussions that are not going wildly off-topic and still may be of interest to those in the list, CC the list so others can follow up.  However, as it suggests, if things are going to be irrelevant to the list's topic, reply in private.
			</li>
		</ul>
		<div id="footer">
			<hr />
			<p><a href="/">Andrew Yu's Website</a></p>
		</div>
	</body>
</html>

c.html#L25'>maybe(get(Recipe, r).name) << "'reset' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end(); 113 break; 114 } 115 if (!is_mu_location(inst.ingredients.at(0))) { 116 raise << maybe(get(Recipe, r).name) << "'reset' requires a location ingredient, but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); 117 } 118 break; 119 } 120 :(before "End Primitive Recipe Implementations") 121 case RESET: { 122 int loc = static_cast<int>(ingredients.at(0).at(0)); 123 put(Memory, loc, 0); 124 trace(9998, "run") << "reset: *" << loc << " = " << get_or_insert(Memory, loc) << end(); 125 break; 126 } 127 128 //: scheduler tweak to get routines out of that state 129 130 :(before "End Scheduler State Transitions") 131 for (int i = 0; i < SIZE(Routines); ++i) { 132 if (Routines.at(i)->state != WAITING) continue; 133 int loc = Routines.at(i)->waiting_on_location; 134 if (loc && get_or_insert(Memory, loc) == 0) { 135 trace(9999, "schedule") << "waking up routine " << Routines.at(i)->id << end(); 136 put(Memory, loc, 1); 137 Routines.at(i)->state = RUNNING; 138 Routines.at(i)->waiting_on_location = 0; 139 } 140 } 141 142 //: Primitive to help compute locations to wait on. 143 //: Only supports elements immediately inside containers; no arrays or 144 //: containers within containers yet. 145 146 :(scenario get_location) 147 def main [ 148 12:num <- copy 34 149 13:num <- copy 35 150 15:location <- get-location 12:point, 1:offset 151 ] 152 +mem: storing 13 in location 15 153 154 :(before "End Primitive Recipe Declarations") 155 GET_LOCATION, 156 :(before "End Primitive Recipe Numbers") 157 put(Recipe_ordinal, "get-location", GET_LOCATION); 158 :(before "End Primitive Recipe Checks") 159 case GET_LOCATION: { 160 if (SIZE(inst.ingredients) != 2) { 161 raise << maybe(get(Recipe, r).name) << "'get-location' expects exactly 2 ingredients in '" << inst.original_string << "'\n" << end(); 162 break; 163 } 164 reagent/*copy*/ base = inst.ingredients.at(0); 165 if (!canonize_type(base)) break; 166 if (!base.type) { 167 raise << maybe(get(Recipe, r).name) << "first ingredient of 'get-location' should be a container, but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); 168 break; 169 } 170 const type_tree* base_root_type = base.type->atom ? base.type : base.type->left; 171 if (!base_root_type->atom || base_root_type->value == 0 || !contains_key(Type, base_root_type->value) || get(Type, base_root_type->value).kind != CONTAINER) { 172 raise << maybe(get(Recipe, r).name) << "first ingredient of 'get-location' should be a container, but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); 173 break; 174 } 175 type_ordinal base_type = base.type->value; 176 const reagent& offset = inst.ingredients.at(1); 177 if (!is_literal(offset) || !is_mu_scalar(offset)) { 178 raise << maybe(get(Recipe, r).name) << "second ingredient of 'get-location' should have type 'offset', but got '" << inst.ingredients.at(1).original_string << "'\n" << end(); 179 break; 180 } 181 int offset_value = 0; 182 //: later layers will permit non-integer offsets 183 if (is_integer(offset.name)) { 184 offset_value = to_integer(offset.name); 185 if (offset_value < 0 || offset_value >= SIZE(get(Type, base_type).elements)) { 186 raise << maybe(get(Recipe, r).name) << "invalid offset " << offset_value << " for '" << get(Type, base_type).name << "'\n" << end(); 187 break; 188 } 189 } 190 else { 191 offset_value = offset.value; 192 } 193 if (inst.products.empty()) break; 194 if (!is_mu_location(inst.products.at(0))) { 195 raise << maybe(get(Recipe, r).name) << "'get-location " << base.original_string << ", " << offset.original_string << "' should write to type location but '" << inst.products.at(0).name << "' has type '" << names_to_string_without_quotes(inst.products.at(0).type) << "'\n" << end(); 196 break; 197 } 198 break; 199 } 200 :(before "End Primitive Recipe Implementations") 201 case GET_LOCATION: { 202 reagent/*copy*/ base = current_instruction().ingredients.at(0); 203 canonize(base); 204 int base_address = base.value; 205 if (base_address == 0) { 206 raise << maybe(current_recipe_name()) << "tried to access location 0 in '" << to_original_string(current_instruction()) << "'\n" << end(); 207 break; 208 } 209 const type_tree* base_type = get_base_type(base.type); 210 int offset = ingredients.at(1).at(0); 211 if (offset < 0 || offset >= SIZE(get(Type, base_type->value).elements)) break; // copied from Check above 212 int result = base_address; 213 for (int i = 0; i < offset; ++i) 214 result += size_of(element_type(base.type, i)); 215 trace(9998, "run") << "address to copy is " << result << end(); 216 products.resize(1); 217 products.at(0).push_back(result); 218 break; 219 } 220 221 :(code) 222 bool is_mu_location(reagent/*copy*/ x) { 223 if (!canonize_type(x)) return false; 224 if (!x.type) return false; 225 if (!x.type->atom) return false; 226 return x.type->value == get(Type_ordinal, "location"); 227 } 228 229 :(scenario get_location_out_of_bounds) 230 % Hide_errors = true; 231 def main [ 232 12:num <- copy 34 233 13:num <- copy 35 234 14:num <- copy 36 235 get-location 12:point-number/raw, 2:offset # point-number occupies 3 locations but has only 2 fields; out of bounds 236 ] 237 +error: main: invalid offset 2 for 'point-number' 238 239 :(scenario get_location_out_of_bounds_2) 240 % Hide_errors = true; 241 def main [ 242 12:num <- copy 34 243 13:num <- copy 35 244 14:num <- copy 36 245 get-location 12:point-number/raw, -1:offset 246 ] 247 +error: main: invalid offset -1 for 'point-number' 248 249 :(scenario get_location_product_type_mismatch) 250 % Hide_errors = true; 251 container boolbool [ 252 x:bool 253 y:bool 254 ] 255 def main [ 256 12:bool <- copy 1 257 13:bool <- copy 0 258 15:bool <- get-location 12:boolbool, 1:offset 259 ] 260 +error: main: 'get-location 12:boolbool, 1:offset' should write to type location but '15' has type 'boolean' 261 262 :(scenario get_location_indirect) 263 # 'get-location' can read from container address 264 def main [ 265 1:num <- copy 10 266 # 10 reserved for refcount 267 11:num <- copy 34 268 12:num <- copy 35 269 4:location <- get-location 1:&:point/lookup, 0:offset 270 ] 271 +mem: storing 11 in location 4 272 273 :(scenario get_location_indirect_2) 274 def main [ 275 1:num <- copy 10 276 # 10 reserved for refcount 277 11:num <- copy 34 278 12:num <- copy 35 279 4:&:num <- copy 20/unsafe 280 4:&:location/lookup <- get-location 1:&:point/lookup, 0:offset 281 ] 282 +mem: storing 11 in location 21 283 284 //: allow waiting on a routine to complete 285 286 :(scenario wait_for_routine) 287 def f1 [ 288 # add a few routines to run 289 1:num/routine <- start-running f2 290 2:num/routine <- start-running f3 291 wait-for-routine 1:num/routine 292 # now wait for f2 to *complete* and modify location 13 before using its value 293 20:num <- copy 13:num 294 ] 295 def f2 [ 296 10:num <- copy 0 # just padding 297 switch # simulate a block; routine f1 shouldn't restart at this point 298 13:num <- copy 34 299 ] 300 def f3 [ 301 # padding routine just to help simulate the block in f2 using 'switch' 302 11:num <- copy 0 303 12:num <- copy 0 304 ] 305 +schedule: f1 306 +run: waiting for routine 2 307 +schedule: f2 308 +schedule: f3 309 +schedule: f2 310 +schedule: waking up routine 1 311 +schedule: f1 312 # if we got the synchronization wrong we'd be storing 0 in location 20 313 +mem: storing 34 in location 20 314 315 :(before "End routine Fields") 316 // only if state == WAITING 317 int waiting_on_routine; 318 :(before "End routine Constructor") 319 waiting_on_routine = 0; 320 321 :(before "End Primitive Recipe Declarations") 322 WAIT_FOR_ROUTINE, 323 :(before "End Primitive Recipe Numbers") 324 put(Recipe_ordinal, "wait-for-routine", WAIT_FOR_ROUTINE); 325 :(before "End Primitive Recipe Checks") 326 case WAIT_FOR_ROUTINE: { 327 if (SIZE(inst.ingredients) != 1) { 328 raise << maybe(get(Recipe, r).name) << "'wait-for-routine' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end(); 329 break; 330 } 331 if (!is_mu_number(inst.ingredients.at(0))) { 332 raise << maybe(get(Recipe, r).name) << "first ingredient of 'wait-for-routine' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); 333 break; 334 } 335 break; 336 } 337 :(before "End Primitive Recipe Implementations") 338 case WAIT_FOR_ROUTINE: { 339 if (ingredients.at(0).at(0) == Current_routine->id) { 340 raise << maybe(current_recipe_name()) << "routine can't wait for itself! '" << to_original_string(current_instruction()) << "'\n" << end(); 341 break; 342 } 343 Current_routine->state = WAITING; 344 Current_routine->waiting_on_routine = ingredients.at(0).at(0); 345 trace(9998, "run") << "waiting for routine " << ingredients.at(0).at(0) << end(); 346 break; 347 } 348 349 :(before "End Scheduler State Transitions") 350 // Wake up any routines waiting for other routines to complete. 351 // Important: this must come after the scheduler loop above giving routines 352 // waiting for locations to change a chance to wake up. 353 for (int i = 0; i < SIZE(Routines); ++i) { 354 if (Routines.at(i)->state != WAITING) continue; 355 routine* waiter = Routines.at(i); 356 if (!waiter->waiting_on_routine) continue; 357 int id = waiter->waiting_on_routine; 358 assert(id != waiter->id); // routine can't wait on itself 359 for (int j = 0; j < SIZE(Routines); ++j) { 360 const routine* waitee = Routines.at(j); 361 if (waitee->id == id && waitee->state != RUNNING && waitee->state != WAITING) { 362 // routine is COMPLETED or DISCONTINUED 363 trace(9999, "schedule") << "waking up routine " << waiter->id << end(); 364 waiter->state = RUNNING; 365 waiter->waiting_on_routine = 0; 366 } 367 } 368 } 369 370 //: yield voluntarily to let some other routine run 371 372 :(before "End Primitive Recipe Declarations") 373 SWITCH, 374 :(before "End Primitive Recipe Numbers") 375 put(Recipe_ordinal, "switch", SWITCH); 376 :(before "End Primitive Recipe Checks") 377 case SWITCH: { 378 break; 379 } 380 :(before "End Primitive Recipe Implementations") 381 case SWITCH: { 382 ++current_step_index(); 383 goto stop_running_current_routine; 384 } 385 386 :(scenario switch_preempts_current_routine) 387 def f1 [ 388 start-running f2 389 1:num <- copy 34 390 switch 391 3:num <- copy 36 392 ] 393 def f2 [ 394 2:num <- copy 35 395 ] 396 +mem: storing 34 in location 1 397 # context switch 398 +mem: storing 35 in location 2 399 # back to original thread 400 +mem: storing 36 in location 3 401 402 //:: helpers for manipulating routines in tests 403 //: 404 //: Managing arbitrary scenarios requires the ability to: 405 //: a) check if a routine is blocked 406 //: b) restart a blocked routine (`restart`) 407 //: 408 //: A routine is blocked either if it's waiting or if it explicitly signals 409 //: that it's blocked (even as it periodically wakes up and polls for some 410 //: event). 411 //: 412 //: Signalling blockedness might well be a huge hack. But Mu doesn't have Unix 413 //: signals to avoid polling with, because signals are also pretty hacky. 414 415 :(before "End routine Fields") 416 bool blocked; 417 :(before "End routine Constructor") 418 blocked = false; 419 420 :(before "End Primitive Recipe Declarations") 421 CURRENT_ROUTINE_IS_BLOCKED, 422 :(before "End Primitive Recipe Numbers") 423 put(Recipe_ordinal, "current-routine-is-blocked", CURRENT_ROUTINE_IS_BLOCKED); 424 :(before "End Primitive Recipe Checks") 425 case CURRENT_ROUTINE_IS_BLOCKED: { 426 if (!inst.ingredients.empty()) { 427 raise << maybe(get(Recipe, r).name) << "'current-routine-is-blocked' should have no ingredients, but got '" << inst.original_string << "'\n" << end(); 428 break; 429 } 430 break; 431 } 432 :(before "End Primitive Recipe Implementations") 433 case CURRENT_ROUTINE_IS_BLOCKED: { 434 Current_routine->blocked = true; 435 break; 436 } 437 438 :(before "End Primitive Recipe Declarations") 439 CURRENT_ROUTINE_IS_UNBLOCKED, 440 :(before "End Primitive Recipe Numbers") 441 put(Recipe_ordinal, "current-routine-is-unblocked", CURRENT_ROUTINE_IS_UNBLOCKED); 442 :(before "End Primitive Recipe Checks") 443 case CURRENT_ROUTINE_IS_UNBLOCKED: { 444 if (!inst.ingredients.empty()) { 445 raise << maybe(get(Recipe, r).name) << "'current-routine-is-unblocked' should have no ingredients, but got '" << inst.original_string << "'\n" << end(); 446 break; 447 } 448 break; 449 } 450 :(before "End Primitive Recipe Implementations") 451 case CURRENT_ROUTINE_IS_UNBLOCKED: { 452 Current_routine->blocked = false; 453 break; 454 } 455 456 //: also allow waiting on a routine to block 457 //: (just for tests; use wait_for_routine above wherever possible) 458 459 :(scenario wait_for_routine_to_block) 460 def f1 [ 461 1:num/routine <- start-running f2 462 wait-for-routine-to-block 1:num/routine 463 # now wait for f2 to run and modify location 10 before using its value 464 11:num <- copy 10:num 465 ] 466 def f2 [ 467 10:num <- copy 34 468 ] 469 +schedule: f1 470 +run: waiting for routine 2 to block 471 +schedule: f2 472 +schedule: waking up routine 1 because routine 2 is blocked 473 +schedule: f1 474 # if we got the synchronization wrong we'd be storing 0 in location 11 475 +mem: storing 34 in location 11 476 477 :(before "End routine Fields") 478 // only if state == WAITING 479 int waiting_on_routine_to_block; 480 :(before "End routine Constructor") 481 waiting_on_routine_to_block = 0; 482 483 :(before "End Primitive Recipe Declarations") 484 WAIT_FOR_ROUTINE_TO_BLOCK, 485 :(before "End Primitive Recipe Numbers") 486 put(Recipe_ordinal, "wait-for-routine-to-block", WAIT_FOR_ROUTINE_TO_BLOCK); 487 :(before "End Primitive Recipe Checks") 488 case WAIT_FOR_ROUTINE_TO_BLOCK: { 489 if (SIZE(inst.ingredients) != 1) { 490 raise << maybe(get(Recipe, r).name) << "'wait-for-routine-to-block' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end(); 491 break; 492 } 493 if (!is_mu_number(inst.ingredients.at(0))) { 494 raise << maybe(get(Recipe, r).name) << "first ingredient of 'wait-for-routine-to-block' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); 495 break; 496 } 497 break; 498 } 499 :(before "End Primitive Recipe Implementations") 500 case WAIT_FOR_ROUTINE_TO_BLOCK: { 501 if (ingredients.at(0).at(0) == Current_routine->id) { 502 raise << maybe(current_recipe_name()) << "routine can't wait for itself! '" << to_original_string(current_instruction()) << "'\n" << end(); 503 break; 504 } 505 Current_routine->state = WAITING; 506 Current_routine->waiting_on_routine_to_block = ingredients.at(0).at(0); 507 trace(9998, "run") << "waiting for routine " << ingredients.at(0).at(0) << " to block" << end(); 508 break; 509 } 510 511 :(before "End Scheduler State Transitions") 512 // Wake up any routines waiting for other routines to stop running. 513 for (int i = 0; i < SIZE(Routines); ++i) { 514 if (Routines.at(i)->state != WAITING) continue; 515 routine* waiter = Routines.at(i); 516 if (!waiter->waiting_on_routine_to_block) continue; 517 int id = waiter->waiting_on_routine_to_block; 518 assert(id != waiter->id); // routine can't wait on itself 519 for (int j = 0; j < SIZE(Routines); ++j) { 520 const routine* waitee = Routines.at(j); 521 if (waitee->id != id) continue; 522 if (waitee->state != RUNNING || waitee->blocked) { 523 trace(9999, "schedule") << "waking up routine " << waiter->id << " because routine " << waitee->id << " is blocked" << end(); 524 waiter->state = RUNNING; 525 waiter->waiting_on_routine_to_block = 0; 526 } 527 } 528 } 529 530 //: helper for restarting blocking routines in tests 531 532 :(before "End Primitive Recipe Declarations") 533 RESTART, 534 :(before "End Primitive Recipe Numbers") 535 put(Recipe_ordinal, "restart", RESTART); 536 :(before "End Primitive Recipe Checks") 537 case RESTART: { 538 if (SIZE(inst.ingredients) != 1) { 539 raise << maybe(get(Recipe, r).name) << "'restart' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end(); 540 break; 541 } 542 if (!is_mu_number(inst.ingredients.at(0))) { 543 raise << maybe(get(Recipe, r).name) << "first ingredient of 'restart' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); 544 break; 545 } 546 break; 547 } 548 :(before "End Primitive Recipe Implementations") 549 case RESTART: { 550 int id = ingredients.at(0).at(0); 551 for (int i = 0; i < SIZE(Routines); ++i) { 552 if (Routines.at(i)->id == id) { 553 if (Routines.at(i)->state == WAITING) 554 Routines.at(i)->state = RUNNING; 555 Routines.at(i)->blocked = false; 556 break; 557 } 558 } 559 break; 560 } 561 562 :(scenario cannot_restart_completed_routine) 563 % Scheduling_interval = 1; 564 def main [ 565 local-scope 566 r:num/routine-id <- start-running f 567 x:num <- copy 0 # wait for f to be scheduled 568 # r is COMPLETED by this point 569 restart r # should have no effect 570 x:num <- copy 0 # give f time to be scheduled (though it shouldn't be) 571 ] 572 def f [ 573 1:num/raw <- copy 1 574 ] 575 # shouldn't crash 576 577 :(scenario restart_blocked_routine) 578 % Scheduling_interval = 1; 579 def main [ 580 local-scope 581 r:num/routine-id <- start-running f 582 wait-for-routine-to-block r # get past the block in f below 583 restart r 584 wait-for-routine-to-block r # should run f to completion 585 ] 586 # function with one block 587 def f [ 588 current-routine-is-blocked 589 # 8 instructions of padding, many more than 'main' above 590 1:num <- add 1:num, 1 591 1:num <- add 1:num, 1 592 1:num <- add 1:num, 1 593 1:num <- add 1:num, 1 594 1:num <- add 1:num, 1 595 1:num <- add 1:num, 1 596 1:num <- add 1:num, 1 597 1:num <- add 1:num, 1 598 1:num <- add 1:num, 1 599 ] 600 # make sure all of f ran 601 +mem: storing 8 in location 1