Control Flow in Avail


Conditionals Loops Iteration Exceptions Backtracking Currying

Conditionals

Consider conditional statements in Smalltalk. They have the form:

boolExpr ifTrue: trueBlock ifFalse: falseBlock

The equivalent in Avail is:

if boolExpr then trueBlock else falseBlock

Several attempts were made at implementing this operation:

  1. A näive polymorphic implementation in Smalltalk would cost two message sends per conditional. One would be needed to dispatch to the appropriate implementation of #ifTrue:ifFalse:. The other would be to actually invoke the trueBlock or the falseBlock, depending on which implementation of #ifTrue:ifFalse: was invoked.

  2. An alternative approach is to use a primitive for #ifTrue:ifFalse: in class Boolean. This still has the cost of a monomorphic lookup of the #ifTrue:ifFalse: method, plus the invocation of the block, but no intermediate context needs to be constructed. When tried initially, Boolean was a leaf class with two instances, rather than the abstract class it is now, with two subclasses.

  3. The third approach is to introduce two primitives for #ifTrue:ifFalse:, one in class True, the other in class False. This makes the lookup bimorphic (or trimorphic if you count the abstract definition in Boolean), but it allows the return types to be strengthened if the blocks return different types. For example, the expression "if x=y then [123;] else [456;]" has the type [123..456], but "if true then [123;] else [456;]" has the type [123..123]. By the way, [123..456] and [123..123] are integer types, not blocks.

I tried all three of the above schemes, but none was satisfactory. In the future, I plan to introduce syntactic types, which should allow a fairly clean framework for basic operations like "if_then_else_". Note that this is essentially the same scheme Smalltalk has chosen for its special selectors, but it's much more general in Avail. For now, I'm leaving it as the one-primitive scheme (#2), with special code in the returns clause to deal with having static knowledge of the condition boolean.


Loops

The basic looping constructs in Avail are as follows:

The first one loops forever (or until escaped in some other way), so that expression has the type "terminates". The others have a return type of void, because they might eventually continue running at the statement after the loop (by exiting the loop). Note the symmetry and completeness in these five forms.

Like conditionals, I expect loops to be statically inlined when I implement syntactic types.


Iteration

The simplest form of iteration is over a range of integers:

startValue to endValue do [arg : integer | ....];

The third argument of "_to_do_", the block, must accept all values in the range [startValue..endValue+1). I state it this way rather than [startValue..endValue], so that passing INF (infinity) as the second argument won't force the block into having to accept INF as a possible value. Remember, INF+1=INF. Actually, this is only the case if the exact values are known for the expressions "startValue" and "endValue" at compile time. This would not be the case, for example, if these were variables or expressions rather than simple constants. In this more complex case (i.e., the general one), the type for "arg" must be at least as general as [startType lower bound..endType upper bound + 1), where startType is the static type of the expression "startValue", and the same for endType and endValue. See extended integer.

Besides the looping operations above, and the iteration operation "_to_do_", also above, there are mechanisms for traversing built-in collection-like objects. The primary mechanism is "_do_", which takes a tuple on the left, and runs the block on the right once for each element of the tuple, passing it as the sole argument. A similar "_do_" exists for sets and maps, but in the case of maps, both the key and its value are passed to a two-argument block.

At the moment of writing, there are also "_collect_", "_any_", and "_all_" operations for tuples. "_collect_" constructs a new tuple out of the results of evaluating the block with elements of the original tuple (thus, it has the same length as the original). "_any_" answers true iff any of the block evaluations yield true, and "_all_" answers true iff all of the block results are true. There will be more operations later on as the library is developed further.


Exceptions

The exception model in Avail is similar to the Smalltalk model, but resumable (proceedable) exceptions are not (currently) supported. The mechanism is kind of neat. A method "catch_in_" (actually a helper method of this, but forget I told you) is implemented as a primitive (#200) that always fails. The backup code invokes the second block (the "body"). Whenever a "Raise_" method is invoked, the current stack of continuations is scanned until a "catch_in_" invocation is found (by noticing the primitive number is 200). If the first argument of this method (the "handler" block) accepts the exception being raised, the stack is popped down to this level, and the handler block is invoked with the exception as its argument. Otherwise, the stack scanning continues until an interested handler is found. The result of the "catch_in_" expression is either the result of the body block (the 2nd arg) if things went well, or else the result of the handler block (the 1st arg) if things didn't go well but the handler was able to intercept an exception without throwing another one of its own.

There is also a provision for passing a comma-separated list of handlers which can catch different exceptions. This helps keep the indentation level down. Note that exceptions are user-defined types under "Exception", which is under "object", and that a handler for some exception type also automatically handles all subtypes.


Backtracking

There are three core methods to the backtracking code:

In addition, an "each_" operation takes a tuple and answers the first element. If backtracking occurs later, it will answer the second element into the same continuation that the first element was answered into. This repeats until all elements have been answered, at which point backtracking propagates to the next most recent "maybe" or "each_". For example, the expression "all [each <1,2,3>;]" is <1,2,3>. Also, the expression "each <true,false>" has exactly the same effect as "maybe".

Backtracking is thread safe (but it is currently impossible to create other threads).


Currying

There are two kinds of currying supported. The first form is "_curry_", which takes a block and an argument X, and answers a new block that takes one fewer argument, but when invoked with those arguments will have the same effect as the original block invoked with X followed by this shortened list of arguments. An example should be helpful:

adder ::= [a : integer, b : integer | a + b;];
incrementer ::= adder curry 1;
Print incrementer(5);  /* prints the number 6 */

The other form, "_curried", takes a block and answers a block which, when passed argument A, answers a block which, when passed argument B, answers a block... which, when passed the final argument, answers what the original block would answer if passed <A,B,...>. An example:

adder ::= [a : integer, b : integer | a + b;];
curriedAdder ::= adder curried;
incrementer ::= curriedAdder(1);
Print incrementer(5);  /* prints the number 6 */

There is one more useful operation - "_taking arguments tupled", which takes a block accepting N arguments, and transforms it into a block taking one argument, a tuple of size N. I bet you can guess what those elements are, and what the new block does when invoked.

By the way, static type safety is preserved through all these transformations. Try that in Java.