Where does this esoteric Pascal operator come from?

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

I want to address the “Has anyone seen this kind of proto-exceptions in any programming language?” part. In 1972, operators named CATCH and THROW were added to Maclisp (I've reformatted the original announcement for convenience):

There is a new pair of break-away functions: CATCH, a FSUBR [i.e. a “special operator”, in Common Lisp terminology] which merely evals the first item in its arglist, and THROW, a SUBR [i.e., a normal function implemented in machine code] of one argument which breaks away back to the most recent CATCH, causing CATCH to return as its value the argument to THROW. If no THROWs take place, the CATCH merely returns the evaluation which it commenced. This mechanism is independent of ERRSET, and should alleviate problems for those who have been using ERRSET and ERR to do the job that CATCH and THROW now do. However, more stuff must be saved up when a CATCH or ERRSET is EVAL'd and thus code compiled by compilers prior to number 240 will not have compiled ERRSET evaluations correctly.

According to the implementer of the feature, Jon L White, it originated because

Sussman's later development of CONNIVER [successor of PLANNER, predecessor of SCHEME] showed the need for a sort of non-local GOTO, as a means of quickly aborting a computation (such as a pattern-matching data-base search) that had gone down a wrong path.

(This is precisely the sort of backtracking behavior mentioned in the accepted answer.)

The operators were generalized later that year:

CATCH and THROW are both FSUBRs and have optional second args which are considered tags. (THROW FOO T1) will THROW back to the most recent setting of (CATCH (BAR) T1). (THROW FOO) will be caught by the most recent CATCH, regardless of any tag setting, and (CATCH (BAR)) will CATCH any THROW. However, (CATCH (BAR) T2) will never capture a (THROW FOO T1)—if there is no CATCH to match a given THROW (either one with the same tag name, or else a tag-less CATCH), then an UNSEEN-GO-TAG correctable error is done.

In contrast to branch, the “tag” in CATCH and THROW is not evaluated. A few years later, Lisp Machine Lisp changed the two operators so that

1. The tag argument comes first for both CATCH and THROW
2. The tag is evaluated
3. CATCH takes any number of forms to execute

And these semantics were inherited into Common Lisp's catch and throw.

---

Also, regarding Algol: Algol 68 doesn't have “formal labels”, but it does have anonymous functions routine-texts, and a kind of “syntactic sugar” where a label alone symbolizes a jump to that label, and another kind of syntactic sugar where a jump is treated as an anonymous function body a routine-text if it appears in a context where a procedure is expected (more precisely, “if the context expects the mode 'procedure yielding MOID'”).

Charles Lindsey was able to use these features, along with the language's unions and array literals row-displays in a slick way to add an exception handling construct to Algol 68 without actually changing the language's syntax at all. The method he describes is basically the same as is used to implement Common Lisp's conditions (see, e.g., Kent Pitman's sample implementation from 1988).