38

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.

6
  • 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, 2017 at 9:40
  • Is it possible for you to post the original document in some form?
    – vzwick
    Jun 20, 2017 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, 2017 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, 2017 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, 2017 at 16:04

4 Answers 4

23

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.

4
  • 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, 2017 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, 2017 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, 2017 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, 2017 at 1:18
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.

5
  • 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, 2017 at 18:29
  • I've added more examples to the question.
    – Leo B.
    Jun 21, 2017 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, 2017 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, 2017 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, 2017 at 5:05
2

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).

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .