Saturday, October 13, 2012

Recursion is now permitted

I've started talking about recursion, and it's much more convenient to do when the recursion can actually be used. The recursive calls (when a label calls itself, directly or indirectly) have been forbidden in Triceps. Mind you, the recursive calling still can be done with the help of trays and forking, as the previous example has shown and more examples will show. And it's probably the best way too from the standpoint of correctness. However it's not the most straightforward way.

So I've decided to allow the recursion in its direct way. Especially that it doesn't have to be all-or-nothing, it can be done in a piecemeal and controlled fashion.

Now it's controlled per-unit. Each unit has two adjustable limits:

  • Maximal stack depth: Limits the total depth of the unit's call stack. That's the maximal length of the call chain, whether it goes straight or in loops.
  • Maximal recursion depth: Limits the number of times each particular label may appear on the call stack. So if you have a recursive code fragment (a streaming function, or now you can do it with a loop too), this is the limit on its recursive re-entrances.
Both these limits accept the 0 and negative values to mean "unlimited".

The default is as it has been before: unlimited stack depth, recursion depth of 1 (which means that each label may be called once but it may not call itself). But now you can change them with the calls:

$unit-> setMaxStackDepth($n);
$unit->setMaxRecursionDepth($n);

You can change them at any time, even when the unit is running (but they will be enforced only on the next attempt to execute a rowop).

You can also read the current values:

$n = $unit->maxStackDepth();
$n = $unit->maxRecursionDepth();

Another thing about the limits is that even if you set them to "unlimited" or to some very large values, thee still are the system limits. The calls use the C++ process (or thread) stack, and if you make too many of them, the stack will overflow and the whole process will crash and possibly dump core. Keeping the call depths within reason is still a good idea.

Now you can do the direct recursion. However as with the procedural code, not all the labels are re-entrant. Some of them may work with the static data structures that can't be modified in a nested fashion. Think for example of a table: when you modify a table, it sends rowops to its "pre" and "out" labels. You can connect the other labels there, and react to the table modifications. However these labels can't attempt to modify the same table, because the table is already in the middle of a modification, and it's not re-entrant.

The table still has a separate logic to check for non-re-entrance, and no matter what is the unit's general recursion depth limit, for the table it always stays at 1. Moreover, the table enforces it across both the input label interface and the procedural interface.

If you make your own non-re-entrant labels, Triceps can make this check for you. Just mark the first label of the non-re-entrant sequence with

$label->setNonReentrant();

And it will have its own private recursion limit of 1. Any time it's attempted to execute recursively, it will confess. There is no way to unset this flag: when a label is known to be non-re-entrant, it can not suddenly become re-entrant until its code is rewritten.

You can read this flag with

$val = $label->isNonReentrant();


The next installment will show some more examples.

No comments:

Post a Comment