Inconsistent semantics

You will note that a bunch of intermediate results are returned, before the final result, when computing a yesno program. In yesno, every program must return at least one value. Well, sort of...considering the short yesno program return x.. Since x is not bound, this program cannot return a value (when looking at intermediate results, this "value" is referred to as fail).

But, something must be returned by the execution of a yesno program. In this sense, yesno is complete. To be more precise, the program evaluates to multiple values at any point in time. These values are gleaned by considering, at each message passing state, that a message is sent or not sent. Since message passing is the foundation for iteration (and just about everything else), yesno can be trivially shown to be complete if we disallow message passing.

So, consider, during our course of executing a yesno program, we come across a message call. We consider two paths: where the message is not sent, and where the message is sent. In the path where the message is sent, it too will (probably) be faced with a similar divergence: where its messages are sent or not sent. Ultimately, in a terminating program, the recursion will stop—some atomic operation will be reached—and the stack of message calls will be retraced. Thus, ultimately, some "correct" value of an expression will be reached, if that expression terminates.

So for any expression, that expression can be in one of two states: it has finished computing, or it has not finished computing. If it has finished computing, there is only one value to consider. If it has not finished computing, there are any number of (inconsistent) values to consider, representing the possibility of that message being sent or not sent, and all of the subpossibilities there within.

So, it is prudent to write yesno programs in such a way that even if execution is not finished, some reasonable value is returned. This is commonly done by setting a variable to return to some initial value, and then updating that value as execution progresses.

As a sort of footnote, not that in order for the yesno interpreter to print out its results, it sends returned objects the show message. Thus, if the show method for that object does not terminate, we cannot absolutely say that yesno is "complete". This is more an issue of interface design than language design, and in any case we are guaranteed that show will terminate for primitive types (such as integers and booleans), and that is all we will consider from here on.

The halting problem

Recall that all code in yesno is actually an object of type Closure. Thus, we add a method to the Closure class to determine of an object will halt.

Closure addInstanceMessage: "halts" withMethod: [|
    z := false.
    self do.
    z := true.
    return z.
return [: 5 * 5 * 5 ] halts.

Execution of the program will yield an interesting property. Once the slough of fails is done with (setting up variable bindings and whatnot), we are returned a value of {false, true}. Semantically, this is saying "this computation either halts or doesn't halt; we don't know yet". After execution is completed, z takes on a value of just true, and our ultimate answer of {true} ("we know it halts") is returned.

If we replaced 5 * 5 * 5 with code which does not halt, the interpreter would again get to the point where it returns {false, true}, and then stay there, not being able to update its answer.

A trick to getting the correct values

Yesno does not guarantee that the correct answer will always be one of those returned (unless the program terminates). A design pattern (ick) that can be used to achieve this, though, is the idea of presetting. Often computation will be written like so:

some big long expensive computation computing a result.
return the result.

In yesno, you can rewrite this as:

returnValue := allPossibleValues.
some big long expensive computation computing a result.
returnValue := the result.
return returnValue.

When dealing with boolean values, the first step can be achieved via (returnValue := false. returnValue := true.). Immediately yesno will skip over the expensive computations and return a value of {false, true}. It's only when the big long expensive computation has finished that the correct answer, and only the correct answer, will be returned.