How did UCSD Pascal exception mechanism work?

Question

In the UCSD PASCAL II.0 Manual, there is a description (document page 140, PDF page 153) of a peculiar language feature: instead of non-local GOTO statements, as in the Wirth's Pascal, there is

        EXIT is a UCSD extension which accepts as its single parameter
the identifier of a procedure to be exited. The use of an EXIT 
statement to exit a FUNCTION can result in the FUNCTION returning
undefined values if no assignment to the FUNCTION identifier is made
prior to the execution of the EXIT statement.

Then there is an example containing

PROCEDURE Q; FORWARD;

PROCEDURE P;
BEGIN
...
  IF some_condition THEN EXIT(Q);
...
END;

PROCEDURE Q;
BEGIN
  P;
...
END;

Regarding special cases, there is only one detail:

        If the procedure identifier passed to EXIT is a recursive
procedure, the most recent invocation of that procedure will be
exited.

However, somewhat surprisingly, there is no mention of the case when a procedure calls EXIT(name) when there is no name on the call stack. For example, if the procedure P was called directly from the main program, and some_condition was true, executing EXIT(Q) would be nonsensical.

Indeed, on the page 263 of the document (PDF page 276), the table of system errors contains

3       Procedure not present at exit time (XNOEXIT)

How was that feature implemented? Was it specific to P-code, or was there a Pascal implementation compiling to executable binaries which had the same feature?

Answer 1

Here is the part of the compiler that produces code for a call to exit (which is a normal procedure, rather than a kind of statement):

PROCEDURE EXIT;
  VAR LCP: CTP;
BEGIN
  IF SY = IDENT THEN
    BEGIN SEARCHID([PROC,FUNC],LCP); INSYMBOL END
  ELSE
    IF (SY = PROGSY) THEN
      BEGIN LCP := OUTERBLOCK; INSYMBOL END
    ELSE LCP := NIL;
  IF LCP <> NIL THEN
    IF LCP^.PFDECKIND = DECLARED THEN
      BEGIN GENLDC(LCP^.PFSEG); GENLDC(LCP^.PFNAME);
        IF INMODULE THEN
          BEGIN LINKERREF(PROC,LCP^.PFSEG,IC-2);
            IF SEPPROC THEN LINKERREF(PROC,-LCP^.PFNAME,IC-1);
          END
      END
    ELSE ERROR(125)
  ELSE ERROR(125);
  GEN1(30(*CSP*),4(*XIT*))
END (*EXIT*) ;

Thus the generated P-code for exit(f) is something like

LDCI ⟨segment of f⟩
LDCI ⟨procedure number of f⟩
CSP 4

The limited memory of many computers on which UCSD Pascal expected to run necessitated a way to divide a large program into smaller pieces, which USCD Pascal calls “segments”. If a routine declaration is preceded by the word SEGMENT, its code will be loaded into memory only when it is called.

Routines are assigned numbers (the value of pfname) beginning at 1; counting starts over in each segment, so to refer to a routine unambiguously a ⟨segment, pfname⟩ pair must be used.

Here is the assembly code for the exit procedure:*

 XIT:    ; EXIT PROCEDURE
         MOV     JTAB,IPC        ; FIRST SET IPC TO EXIT FROM CURRENT
         ADD     #EXITIC,IPC     ; PROC ... GET INFO FROM CUR JTAB
         SUB     @IPC,IPC        ; NOW IPC IS SET TO EXIT MY CALLER
         CMPB    @JTAB,@SP       ; IS IT THE PROC # TO EXIT ANYWAY?
         BNE     XCHAIN          ; IF NOT THEN CHAIN DYN LINKS TO FIND
         CMPB    @SEG,2(SP)      ; IF PROC OK, HOW ABOUT SEG#?
         BNE     XCHAIN          ; IF WRONG, THEN CHAIN DYN TOO
         CMP     (SP)+,(SP)+     ; ELSE CHUCK STACK STUFF
         MORE                    ; AND DO THE RETURN CODE
 XCHAIN: MOV     MP,R0           ; OK...START EXITING STACKED PROCS
 XLOOP:  CMP     R0,@BASE        ; ARE WE ABOUT TO EXIT SYSTEM BLOCK?
         BEQ     XBOMB           ; IF SO THEN BIG BOOBOO
         MOV     MSJTAB(R0),R1   ; ELSE OK...GRAB JTAB AND FUDGE MS IPC
         ADD     #EXITIC,R1      ; TO EXIT CODE RATHER THAN NORMAL REENTRY
         SUB     @R1,R1          ; R1 NOW HAS EXIT POINT IPC
         MOV     R1,MSIPC(R0)    ; SO PLACE IN STACK FRAME
         CMPB    @MSJTAB(R0),@SP ; IS THIS THE PROC# TO EXIT FROM?
         BNE     1$              ; IF NOT THEN GO TO NEXT CALLED PROC
         CMPB    @MSSEG(R0),2(SP)        ; AND RIGHT SEG#
         BNE     1$
         CMP     (SP)+,(SP)+     ; WELL, FOUND IT...CHUCK PARAMS
         MORE                    ; AND FALL OUT OF PROC
 1$:     MOV     MSDYN(R0),R0    ; CHAIN DOWN DYNAMIC LINKS!
         BR      XLOOP
 XBOMB:  TRAP    NOEXIT

I'll assume that you know how the P-system's “mark stack” works; if not, Pemberton and Daniels explain it in the book Pascal Implementation. The algorithm first sets the P-code instruction pointer to the epilogue of the caller of exit. Then we check whether we're exiting the current routine, to take care of a common case. (Note: MORE is a macro that transfers control to the next P-code instruction.) Otherwise, it searches up all the open activation records to find one corresponding to the routine number and segment that were pushed prior to the exit call. If one is found, the “return address” field of the record is changed to point to the routine's epilogue.

In any case, the epilogue of the caller of exit is executed, which causes control to transfer to the epilogue of the routine being exited from. By transferring to the epilogue, rather than just to the return address, an exited function will return a value.

However, if the search reaches the top of the stack, error trap 3 is signaled.

---

So that is how exit works. But a bigger mystery remains: Why didn't they just support nonlocal goto statements? The code for doing so would surely be no more complicated than for exit, and the feature is part of the standard language (while exit is not). Furthermore, nonlocal goto has lexical scope, making it easier to reason about than exit, which has indefinite scope.

Maybe exit was considered more structured than goto—but then why not add a return statement and keep it lexically scoped?

Its dynamic nature does make exit more powerful than goto. If UCSD Pascal supported routines as arguments, you could implement a condition system:

type signaltype = (endoffile, overflow, syntaxerror);

var ok: boolean;
    signaled: signaltype;
    handlers: set of signaltype;

procedure signal(s: signaltype);
  begin
    if not (s in handlers) then
      exit(defaulthandler);

    ok := false;
    signaled := s;

    case s of
    endoffile: exit(catchendoffile)
    overflow: exit(catchoverflow)
    syntaxerror: exit(catchsyntaxerror)
    end
  end;

procedure handle(s: signaltype; procedure p; procedure c);
  begin
    handlers := handlers + [s];
    p;
    handlers := handlers - [s];
    if (not ok) and signaled = s then
      c;
    ok := true
  end;

procedure endoffilehandler(procedure p; procedure c);
  procedure catchendoffile;
    begin
      p
    end;
  begin
    handle(endoffile, catchendoffile, c)
  end;

procedure overflowhandler(procedure p; procedure c);
  procedure catchoverflow;
    begin
      p
    end;
  begin
    handle(overflow, catchoverflow, c)
  end;

procedure syntaxerrorhandler(procedure p; procedure c);
  procedure catchsyntaxerror;
    begin
      p
    end;
  begin
    handle(syntaxerror, catchsyntaxerror, c)
  end;

Then you could say, e.g., overflowhandler(addtwonumbers, reportoverflow), where addtwonumbers attempts to add two numbers and does signal(overflow) if the result is too large, and reportoverflow prints a message like “number too big”. Only the most recently established handler will be invoked for any given condition, although you could change this by having the handlers call signal again.

This provides capabilities similar to Common Lisp's handler-case. If signaled held a record, you could convey even more information and support a fairly sophisticated exception handling mechanism.

---

* Unlike other P-system derivatives, the P-code generated by the compiler is interpreted by an assembly program akin to the Apollo AGC “interpreter”, rather than using the P-machine or generating native code directly. The code is taken from the I.5 sources (pdf, zip), in file USCD Pascal 1.5 ProcOp.txt, because it seems that the PDP-11 interpreter isn't included with the II.0 sources (pdf, zip). The II.0 distribution does, however, include an implementation of the P-code interpreter for the Z80 (the exit source is in the file z80_p-code_source/proc2.text), which uses the same algorithm as is described above.

Answer 2

PASCAL, like ALGOL before it, and unlike the entire C family of languages, has both static and dynamic scoping of activation records (i.e., frames, i.e., procedure calls).

☞ This is not the same as "dynamic scoping" as used in "dynamically scoped" languages like scripting languages, etc. This is about activation records of function/procedure calls.

Dynamic scoping of activation records is all that anyone is familiar these days since the C language family has long since completed its takeover of the entire procedural programming language space⁽¹⁾. That's where you have a stack of frames for procedure/function/method and each one is linked to its caller ("parent") - either explicitly with a link or more typically just implicitly by being placed adjacent to each other on the stack.

But ALGOL and PASCAL also had static scoping of activation records. Each record contained a link (conceptually) to its static - i.e., lexical - parent. These links had to be maintained at each procedure call.

Thus, this kind of exit in PASCAL required no search up the stack. There was an actual chain of links from the current procedure up through its lexical parents up to the outer scope. All you needed for this exit was the count of how many lexical scopes up the named procedure was - and that was available at compile time simply by looking at the parse tree (or AST).

(Remember, PASCAL doesn't have any new-fangled stuff like destructors that had to run as you exited procedure/function scopes. You could just pop the stack to the right place - you found the address to return to in the usual place in the desired parent's dynamically scoped callee (i.e., the frame below the desired parent).

There were three implementation techniques used, depending on your compiler.

1. The static parent link could actually be present in each stack frame. Referencing up-level variables required chaining up the required (compile-time known) number of levels and then going to the proper offset in that frame. This was reasonably straightforward to implement, was a small tax on each procedure call, and made up-level variable access somewhat slow (especially as you climbed higher up the lexical scopes).

2. You could keep a display of static parents. This was a separate area of memory (or actual registers in a Burroughs stack machine!) that was an array of pointers to the current set of static parents of the currently executed procedure. Maintaining this was also a small tax on each procedure call and return but had the advantage that up-level variable access was a direct index through this array plus an offset.

3. You could hedge by doing both: Each frame, when built, would contain the display of the current parents. This could potentially be a large tax on each procedure call but in fact there's a great optimization: The display for a particular frame only needed those parent frame pointers for which there was an actual reference to one of its variables⁽²⁾. Since most often a procedure didn't reference any of its up-level parent's variables - those procedure didn't need a display in their frame at all, thus didn't pay the tax. And the next most often case was a procedure that referenced up-level variables of only one of its parents: the tax then was no higher than full static linked frames. Only the really rare case of a procedure accessing up-level variables in more than one parent frame was more expensive at procedure call time. Meanwhile, an additional payback was that accessing those up-level variables no longer had to chain up the static frame links.

I don't know which technique the UCSC PASCAL interpreter used for its stack frames. It can probably be found somewhere⁽³⁾.

I found it surprising difficult to find any links to this subject, else I would have provided links. Maybe someone else can supply links. To me, that just indicates this is a dead end of computer language development. Well, with the exception of the LISP community and the entire functional programming community where it lives on in glory and usefulness. And it's also coming back as procedural-style languages begin to support closures ("lambdas") (I'm thinking of C++ and C#, not the cruddy fake "closures" of Java).

---

⁽¹⁾ But they haven't wiped out the functional programming language space, nor LISP, which still lives! But also see my comment in the last paragraph above.

⁽²⁾ Or when it called a procedure - necessarily a lexically nested procedure, that itself referenced variables in one of it's up-level parents not including this one. It's a bit tricky, and the tradeoffs aren't clear, and it's why it wasn't implemented very often. I do know it was in fact implemented at least once but sadly I can't remember which compiler it was ...

⁽³⁾ Oh, and BTW, you can also find it in the documented ABIs of some older systems. You'll see it as a space reserved in the stack frame/calling sequence - but unused by all languages today! - for the static link. I'm pretty sure I remember this coming up in at least one other answer here at retrocomputing, but in any event you'll probably find evidence for it on bitsavers or somewhere.