There is a certain level of recursion that may show in the data structures denoted by Algol 68 modes. A typical example are the nodes of linked lists, trees or graphs, in which each node must be able to somehow refer to the other nodes linked to themselves. This is great, but it was early recognized that this flexibility could be dangerous, for two reasons.
First, should a mode be built in a way the recursion never stops,
values of that mode would occupy infinite space, which makes no sense.
This would be the case of mode Node = struct (int data,
Node next) for example. The solution for this problem, a version
of which was later adopted by C, was to go through the indirection
implied by a name or reference. So we would write mode Node
= struct (int data, ref Node next) instead.
Second, recursion in mode definitions may lead to ambiguity in the
context of strong syntactic positions and their associated coercions.
Lindsey exemplifies this situation with a mode mode Itself =
ref Itself and the right hand side (which is a strong
position) in the assignation ref Itself = loc
Itself.
A mode declaration that doesn’t suffer from any of the above problems is said to be well formed. Otherwise, it is said to be ill formed.
On the face of these problems, the syntax of the mode declarers was carefully designed (like everything else in this language) so that, on one side, ill formed modes can always be detected at compile time and, on the other, the programmer can easily and consistently determine, without having to remember arbitrary rules, whether the mode she is writing is well formed. To this effect, both compiler and programmer use the same method: the so-called yin-yang algorithm, which is directly derived from the grammar of declarers (see below).
The method is as follows:
ref or proc is found, that’s a yin.
struct or a procedure’s parameter pack is found, that’s a yang.
Finding at least a yin guarantees that the problem of infinitely big data objects due to recursion cannot happen, and finding at least a yang guarantees that the mode is not strongly coercible to itself.
As a first example, consider the declaration of the mode
Node below:
mode Node = struct (int data, Node next)
Applying the yin-yang method, we start with Node, then we
get a yang due to the struct, thn we find Node
again: there is recursion. But since we didn’t get any yin, the mode
is not well formed because its values would occupy infinite space. To
fix this, we make sure to add a yang via either a name or a procedure:
mode Node = struct (int data, ref Node next)
As a second example, consider the declaration of the mode
Set below:
mode Set = ref[]Elem,
Elem = union (int,Set)
Applying the yin-yang method, we start with Set, then we
get a yin due to the ref, then we find Elem, in
which we find Set again: there is recursion. But since we
didn’t get any yang, the mode is not well formed because it is
strongly coercible to itself: a value of mode Set could be
dereferenced, then rowed, then united. To fix this, we make sure to
add a yang:
mode Set = struct (ref[]Elem elems),
Elem = union (int,Set);
Simplified [RR 7.4.1]:
a) WHETHER (NOTION) shields SAFE to SAFE:safe
where (NOTION) is (PLAIN)
or (NOTION) is (FLEXETY ROWS of)
or (NOTION) is (union of) or (NOTION) is (void),
WHETHER true.
b) WHETHER (PREF) shields SAFE to yin SAFE: WHETHER true.
c) WHETHER (structured with) shields SAFE to yang SAFE:
WHETHER true.
d) WHETHER (procedure with) shields SAFE to yin yang SAFE:
WHETHER true.