The RPL inner loop explained

[Jonathan Busby]

The RPL inner loop explained

Draft 0.2g

Prologue

( It is assumed that the reader has a basic understanding of computer architecture and programming )

What is RPL?

RPL ostensibly stands for "Reverse Polish LISP" and/or "ROM-based Procedural Language", depending on whom you ask. It is an RPN stack based threaded-interpreted language superficially similar to Forth. It was developed by HP starting at around 1983 to 1984 for their Saturn based calculators to make development easier because HP had previously used pure assembly language.

What is an RPL object?

An RPL object is a data structure, which can include executable code, that is stored in memory and which is prefixed by an address, called the "object prolog", which handles the specific execution of the class of objects of which the data structure is a part. The object body holds the object's data whereas the prolog tells the RPL interpreter how to execute the object.

How is RPL structured in memory?

RPL is a so-called "TIL" or "Threaded Interpreted Language". Most TILs, such as Forth, consist of a stream of pointers in memory called the "runstream" which, when dereferenced and executed in sequence, perform operations and manipulate the stack etc. RPL is structured similarly except that it is able to mix RPL words ( eg. executable operators that manipulate the stack ), object pointers and embedded objects directly in the runstream.

---

RPL, which is the threaded interpreted language used on HP's Saturn based calculators since the HP-18C, was developed by William C. Wickes back around 1983 to 1984. For a while, HP had a patent on it, but I think that is long since expired. ( see here ) Some of the information in this article is available from the journal article "RPL: A Mathematical Control Language" by William C. Wickes, published in "Programming Environments", Institute for Applied Forth Research, Inc., 1988., if you're lucky enough to find a copy of the specific 1988 journal issue. The full edition of the journal which contains the article might be hard to find, but thanks to David Hayden for a link to W.C. Wickes article which can be found here : http://hpgcc3.org/images/Documents/Wickes.pdf

For the purposes of this article, we need only define a few concepts :

• The runstream
   
  This is a stream of RPL words, object pointers or embedded objects which the RPL inner loop is executing
   
• Current object address
   
  This will be abbreviated "O" and it consists of a pointer to the current object being executed in the runstream
   
• Interpreter pointer
   
  This will be denoted by "I" and it points to the next object or RPL word in the runstream after the current object pointer, O.
   
• The program counter
   
  This will be represented by "PC" and it stands for the address of the next instruction to be executed by the CPU.
   
• Object prolog
   
  This is the address of the routine pointed to at the beginning of each object which handles direct and indirect execution of the object.
   
• Direct / indirect execution
  
  Indirect execution occurs when I points to an object pointer whereas direct execution happens when I points to an embedded object.
   
• RPL word
  
  This is a pointer to executable code which may eg. manipulate the stack or perform other operations. Note that an RPL word is almost always an object, usually a secondary or code object. There is an exception with so-called "primitive code objects" or PCOs which will be explained later. 
  
  

RPL was a great innovation because up until its invention, threaded-interpreted languages like Forth didn't have the ability to embed objects easily into the stream of instructions. The RPL inner loop was invented so that object pointers and *embedded objects* could be executed side by side seamlessly. The pseudocode for the generalized RPL inner loop is as follows :

Code:

    O  = [I]
    I  = I + Δ
    PC = [O] + Δ

where Δ is the length of an address ( eg. 5 nibbles )

For a verbal explanation of the above, the interpreter pointer is first dereferenced and then O is set to the dereferenced address. Next, the interpreter pointer, I, is updated to point to the next object or RPL word in the runstream. Finally, the current object pointer is dereferenced and the program counter, PC, is set to the dereferenced address plus the length of an address, which is represented by Δ. The length of an address, Δ, needs to be added to the PC as the object's prolog address points to itself and the actual code starts one Δ after the starting address of the prolog.

Since objects and object pointers can be intermixed in the runstream, then special care has to be taken with respect to direct and indirect execution. To make this possible, William C. Wickes invented an ingenious mechanism by which an object's prolog code can check for direct or indirect execution and take appropriate action. That mechanism is shown in the following pseudocode for the generalized RPL object prolog code :

Code:

    PROLOG -> PROLOG ( The prolog address at the start of the prolog code points to itself )
    IF O + Δ =/= PC
    THEN GOTO INDIRECT ( Test for direct execution )
        O = I - Δ ( Correct O to point to start of embedded object )
        I = I + α ( Correct I to point after embedded object where α is the length of the object )
    INDIRECT ( rest of prolog )

In the above, first, O + Δ is compared to the PC, and, if it is not equal to the PC, then this means that indirect execution is taking place. This is due to the fact that O points to the currently executing object but the PC points to that object's prolog code plus one Δ address word. If indirect execution is detected, then control is transferred to the object's indirect execution code. In the case of direct execution, O points to the embedded object's prolog code and the PC points Δ words past said object's prolog code. This means that O + Δ equals the PC since the address to which O points is its self-address. The prolog code has to correct for the fact that there is an embedded object in the runstream and correct O to point to the start of the embedded object and I to point past the object to the next pointer in the runstream.

Because the prolog address of every object points to itself, then when an object pointer is executed, the prolog code is executed, no matter how many times it's been dereferenced, so long as the length of an address is added to the address of the prolog pointer before execution.

In the Saturn specific case, object prologs *do not* need to point to themselves. To make this possible, an ingenious trick was invented by the developers of RPL which allows one to skip the direct/indirect object test :

Code:

    O  = [I]
    I  = I + Δ
    PC = [O] ( Do *NOT* advance the PC by the one 5-nibble address -- Instead execute object's prolog code )

The above pseudo-code corresponds to the Saturn specific RPL inner loop instructions which are :

Code:

    A=DAT0    A    * O  = [I]
    D0=D0+    5    * I  = I + Δ
    PC=(A)         * PC = [O]

When the above is executed, and I points to an object pointer, then the object's prolog code gets executed. The neat trick invented by the Saturn RPL developers is that every object's prolog code starts with what is essentially a "NOP" which when executed, corresponds to the following Saturn instruction sequence :

Code:

    D=D-1    A
    HS=      0

When I points to the start of an embedded object, then the above opcodes are dereferenced as an address and control is transferred to the RPL kernel's =PRLG routine which handles direct execution.

In HP calculators that use RPL, the code for each object prolog is prefixed by pointers to that object prolog's =SKIPOB code, and, more importantly, that object prolog's *direct execution code*. This can be represented as

Code:

        CON(5)  DIRECT
        CON(5)  SKIP
        ....Indirect object prolog execution code goes here...

in Saturn assembly.

The code for =PRLG follows :

Code:

    LC(2)    #A
    A=A-C    B
    PC=(A)

In the above, since register A points to the start of O's prolog code, the =PRLG routine subtracts 10 nibbles ( in the Saturn specific case, two 5-nibble address words ) from the address and transfers control to the address stored before the start of O's prolog code which points to the direct execution code for O ( the "CON(5) DIRECT" line in the Saturn assembly code ).

There is one special case in Saturn based specific RPL execution which restricts certain types of "objects" to *indirect execution only*. Specifically, if the object is a so-called PCO or "Primitive Code Object" then it can only be executed *indirectly*. This is because a PCO has no proper prolog pointer / address as its prefix, but instead has an address that points directly into the body of the "object" which is composed of machine code.

---

I hope this article serves as an understandable explanation of the RPL inner loop If you find any omissions, errors, or anything which I didn't explain clearly enough, then don't hesitate to contact me.

---

( I fixed most of the formatting errors ( Thanks to Dieter ). Note that this is a work in progress, at least with respect to the diagrams which I want to include If you have any suggestions about what I should include in the diagrams or what they should look like, then please don't hesitate to contact me )

( Also, Thanks to David Hayden for the link to W.C. Wickes journal article and his suggestions for changes I've made in this article )

( Updated to draft 0.2g on February 12th, 2021 )