Post Reply 
The RPL inner loop explained
09-07-2018, 06:28 PM (This post was last modified: 09-14-2018 06:37 PM by Jonathan Busby.)
Post: #1
The RPL inner loop explained
The RPL inner loop explained

Draft 0.02b

Prologue

( It is assumed that the reader have 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 object pointers with 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.

For the purposes of this article, we need only define a few concepts :
  • The runstream
     
    This is a stream of 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 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.
     

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 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 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. Indirect execution occurs when I points to an object pointer whereas direct execution happens when I points to an embedded object.

To make it possible for the above to work, 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 :

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 )

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.

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.

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 Smile I also plan on adding some graphics which illustrate the concepts in this article when I have the time, probably started out with ASCII "graphics" Smile )
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 1 Guest(s)