31

In the documentation for an implementation of Pascal for a Soviet computer, I've encountered a very weird language extension. I'll try to translate it:

Branching operator (branch)

Syntax

<Branching operator>::= branch <Expression> of <Operator> { ; <Operator> }* end

Semantics

When control reaches a branching operator, the Expression, which should be of a simple type, is evaluated, then control is passed to first Operator in the branch.
[Forall j ls likely missing here. - LB] If the j-th operator of the branch has concluded, the branch is exited, and control is passed beyond end. During the execution of the j-th Operator, the back operator can be called.

Syntax of the back operator

<back operator> ::= back <Expression>

During the execution of the back operator, the Expression is evaluated, and a search is performed for the closest dynamically preceding branch with a compatible value of its Expression. The values are compatible, when they are either equal, or one of them is equal to zero.

If such a branch is found, control is passed to the next operator in the branch, or, if the last operator in the branch was being executed, beyond the end of the branch.

If a branch with a compatible expression is not found, then it is deemed that the whole program is enclosed within

branch <Program>; begin <Printing "exit on ALT"> end end

TL;DR: The branch operator implements exceptions, allowing to represent concepts similar to C++ try, catch (including catch (...)), throw and re-throw, albeit using values of expressions rather than types to distinguish the exceptions.I notice two peculiarities: there are references to the "j-th operator" without explaining what "j" refers to (it turns out that in the context it simply means "any"); also the diagnostic "exit on ALT" — the equivalent of C++ terminate() — had ALT in Latin letters, and the turn of the phrase is somewhat unnatural in Russian.

(OK, three peculiarities: the last line is syntactically incorrect: the expression and the keyword of are missing. Should have been something like branch 0 of ...)

This leads me to think that this branch operator was not of an original design, and that part of the documentation is a direct translation from a foreign language.

Does it ring a bell? Has anyone seen this kind of proto-exceptions in any programming language?

An example (simplified from the example in the documentation):

program t;
procedure m(i: integer);
begin
  branch i of
    begin
      if i<20 then begin
        m(i+1);
        back i-2
      end
    end;
    writeln(i)
  end
end;
begin
  m(0)
end.

It prints

    17
    14
    11
     8
     5
     2
     0

The equivalent C++ code would be:

#include <iostream>
void m(int i) {
    try {
        if (i < 20) {
            m(i+1);
            throw i-2;
        }
    } catch (int k) {
        if (i && k && i != k)
            throw;
        std::cout << i << '\n';
    }
}
main() {
    m(0);
}

Additional examples:

branch expr of
    writeln(1);
    writeln(2);
    writeln(3)
end

will print 1 regardless of the value of expr, because the execution of the branch operator always starts from the first enclosed operator and finishes as soon as an operator concludes.

branch 0 of
    begin
        branch 1 of
            begin write(1); back 0 end;
            begin write(2); back 1 end;
            begin write(3); back 99 end
            write(4); 
        end;
        write(5)
    end;
    writeln(99)
end

will print 1 2 3 99: back 0 matches the closest enclosing branch with expression value 1 (because one of the expressions is 0), the first item of branch 1 has been executed; so control is passed to the next item of that branch; in the second item, back 1 matches branch 1, so control is passed to the third item. back 99 doesn't match branch 1 but it matches branch 0, so control is passed to the next item of branch 0 which prints 99. Without back 99, 1 2 3 5 would be printed. With back 1 instead of back 99, 1 2 3 4 5 would be printed.

The question of different types of expressions is not covered in the documentation. Experimentation shows that 1.0 doesn't match 1, but chr(1) does. This indicates that the type information was not saved, and that matching was done by bit pattern.

  • 4
    Nice find: A spaghetti enablement operator. Really weird. In your explanation I'm indeed missing what "j" refers to. The example complicates things even a bit more by being recursive (is this indeed needed). And the whole thing reminds me a bit of setjmp/longjmp in C – tofro Jun 20 '17 at 9:40
  • Is it possible for you to post the original document in some form? – vzwick Jun 20 '17 at 10:59
  • 1
    @vzwick Here it is, the relevant text starts from line 1649. The original example (line 1689) is unnecessarily complicated and uses another extension: so called "structural labels", allowing for "break" and continue"-like operators. – Leo B. Jun 20 '17 at 15:43
  • @tofro Exceptions per se are a good thing; the example is indeed too contrived, but it does demonstrate the dynamic mechanism of finding the matching branch for the back operator being executed. It is somewhat akin to setjmp/longjmp, but the devil's in the details. – Leo B. Jun 20 '17 at 15:56
  • @tofro Re "j-th": what it says that as soon as any operator within a branch concludes normally, the whole branch operator concludes, as if there was a "Forall j" quantifier. – Leo B. Jun 20 '17 at 16:04
11

From personal communication with Adam Sampson:

I think it's fairly likely that the designers of your 1979 dialect of Pascal were thinking of this as a feature to support (what was then called) "backtrack programming" for AI-like applications, rather than as an exception handling mechanism...

There were several programming languages experimenting with approaches to backtracking in the mid-late 70s, Prolog probably being the best-known result ("branch" is equivalent to a Prolog predicate with multiple rules, where failure inside one rule causes control flow to backtrack to the next rule). Your branch/back construct would be pretty handy if you were trying to write a tree search algorithm with pruning (e.g. a classic board game AI), or a backtracking parser.

Here's a 1974 survey which sketches the backtracking idea (p157) and describes some early implementations: http://dl.acm.org/citation.cfm?id=356632 (also http://www.ai.sri.com/pubs/files/1499.pdf - Leo B.)

This 1977 paper gives a denotational semantics for backtracking, and is fairly widely cited by later work: https://link.springer.com/article/10.1007/BF00289245

(Note in particular that it calls its equivalent of "branch" the "alternative" operator -- which might explain your "exit on ALT" message?)

This 1979 paper takes the idea and generalises it to work with coroutines (using Pascal for examples, although with different syntax): http://dl.acm.org/citation.cfm?id=357062.357063

As a matter of fact, similar program behavior and flow of control, except the "zero matches everything" part, could be expressed almost as succinctly in ALGOL-60 using formal parameters-labels:

       1.     ’BEGIN’
       2.         ’PROCEDURE’ M(I, X, Y);
       3.         ’VALUE’ I; ’INTEGER’ I; ’LABEL’ X, Y;
       4.         ’BEGIN’
       5.             ’IF’ I < 20 ’THEN’ ’BEGIN’
       6.                 M(I+1, Y, A);
       7.                 ’GOTO’ X;
       8.             ’END’ ’ELSE’ ’IF’ ’FALSE’ ’THEN’
       9.                 A: PRINT(I, NEWLINE);
      10.         ’END’;
      11.         M(0, T, T);
      12.         T:
      13.     ’END’ ’EOP’

LINE                                            ADDRESSES(OCTAL)
                1        2        3        4        5        6        7        8        9        0
 1 -  10      00001    00001             00003    00003    00004    00014    00015    00017    00022
11 -  13               00030    00031

 >>> PROGRAM <<<        LENGTH:    35 (00043)      TIME:   0,00 SEC. (CP:   0,00 SEC.)          ALGOL-COMPILER 16.IV.75

       *EXECUTE
         17
         14
         11
          8
          5
          2
8

They probably meant Landin's J operator, which is basically a precursor to the call-with-current-continuation function from Scheme. See the relevant part of Racket documentation.

  • Though it's a bit strange to implement the call/cc "numerically". I assume "j-th operator" in the translation should really be "J operator"? – dirkt Jun 20 '17 at 14:26
  • 2
    @dirkt I think you're giving the authors too much credit. The J operator is way more powerful than what's implemented. It is really nothing more but a non-local jump. – Leo B. Jun 20 '17 at 15:30
  • @LeoB. I'm not familiar with the J operator, but from the examples and the naming here, the main use case here seems to be implementing backtracking search algorithms, which is also a common application for call/cc, so I find it plausible that it was perhaps intended as a more restricted implementation that can achieve similar results. – Jules Aug 29 '17 at 1:07
  • @Jules That seems to be it; but I haven't seen that particular way of implementing it anywhere else. – Leo B. Aug 29 '17 at 1:18
1

Given the revised description, it appears that the intention was to provide an ability to exit inner blocks of code in a manner somewhat analogous to setjmp/longjmp. Basically, something like:

branch 6 of
  doX;
  doY;
  doZ;
End

would be somewhat analogous to the C code:

extern jmp_buff back_jmp_buff;
extern int jmp_cause;

jmp_buff volatile prev_jmp_buff = back_jmp_buff;
if (!setjmp(&back_jmp_buff))
  doX();
else if (jmp_cause != 6)
  longjmp(&prev_jmp_buff, 1);
else if (!setjmp(&back_jmp_buff))
  doY();
else if (jmp_cause != 6)
  longjmp(&prev_jmp_buff, 1);
else if (!setjmp(&back_jmp_buff))
  doZ();
else if (jmp_cause != 6)
  longjmp(&prev_jmp_buff, 1);
back_jmp_buff = prev_jmp_buff;

A back 6 would be equivalent to jmp_cause = 6; longjmp(&back_jmp_buff, 1); I don't understand the first example at all; the use of a variable and subtraction operators within the expressions seems weird.

For those unfamiliar with setjmp/longjmp, the expression setjmp(&buff) will take a snapshot of the current program counter and stack state and return 0; if code later does longjmp(&buff, n), execution will jump back to the previous setjmp(&buff), but it will return n. There are restrictions to the contexts in which setjmp can appear which make it hard to do anything with the return value beyond testing whether it is zero, so I used a separate jmp_cause variable.

  • I can share the frustration: when I first read the description, is seemed to me that the "branch" expression determines how many items to execute. As a matter of fact, the expression computed in "branch" doesn't select anything. The items are always executed sequentially; as soon as an item concludes, the whole branch statement concludes. The expression serves as a tag to match expressions thrown by nested "back" operators. – Leo B. Jun 21 '17 at 18:29
  • I've added more examples to the question. – Leo B. Jun 21 '17 at 18:59
  • This answer has been flagged as NAA. I don't think that all of this is NAA, but please remove the first sentence and possibly reorganise the answer so that the last sentence is nearer the beginning. – wizzwizz4 Jun 22 '17 at 16:28
  • @wizzwizz4: I rewrote the description to fit the new info. The first example seems rather horrible and I can't make head nor tail of it, but hopefully I figured out what's supposed to be going on. – supercat Jun 22 '17 at 16:52
  • That's right; but the functionality was clear to me; I'm asking what is the possible source of the language construct which internalizes comparing the jump cause and jumping further in case of a mismatch. Neither C setjmp/longjmp, nor C++ throw/catch do that automatically. The example from the article is indeed hard to understand but it demonstrates the unique feature of the construct. – Leo B. Jun 27 '17 at 5:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.