|
Vint Cerf - UCLA |
RFC 194 John Heafner - Rand
THE DATA RECONFIGURATION SERVICE --
COMPILER/INTERPRETER IMPLEMENTATION NOTES
T(X) = type of identifier X.
L(X) = length of contents of X.
V(X) = contents of X converted to binary
(decimal - binary is presently the only
transformation).
[Page 1]
[Page 2]
The interpreter is a simple minded machine having the virtue of
+-------------+ +--------------+
| inputstream | | outputstream |
+-------------+ +--------------+
/\ /
\ /
\ /
\ \/
+-----------------------+
| CPU |
+-----------------------+
| /\
| |
| |
\/ |
+-----------------------+
Storage: | Instruction |
| Sequence |
+-----------------------+
| Label Table |
+-----------------------+
| Literal/Identifier |
| Pool |
+-----------------------+
| Variable length |
| string area |
+-----------------------+
Fig. 1. Form Interpreter
[Page 3]
The CPU is a box full of miscellaneous parts, the most important
+-----------------+ +---------------+
| Instruction | | Instruction |
| Counter | | Register |
+-----------------+ +---------------+
|
|
V
+----------------+
| Operation Code |
| Decoding |
Run Time Stack +----------------+
+------------------+ / | \
| Operands | / | \
+------------------+ \/ V \/
| | +-----------------+
+------------------+ / Instruction \
| | | Interpreter |
+------------------+ | Routines |
| | \ /
+------------------+ +---------------+
| | | /\
+------------------+ | |
| | | |
+------------------+ V |
| | +---------------+
+------------------+ <------------- | Arithmetic |
| | -------------> | Logic Unit |
+------------------+ +---------------+
| |
+------------------+
| |
+------------------+
+------------------+ +------------------+
|Initial Input Ptr.| | Output pointer |
+------------------+ +------------------+
+------------------+ +------------------+
|Current Input Ptr.| | True/False Flag |
+------------------+ +------------------+
[Page 4]
The CPU is a stack machine driven by a Polish postfix instruction
16 bits
+--------/\---------+
/ \
+---------------------+
| length n in bytes |
+-- +---------------------+
| | |
| | compiled |
| | 16-bit |
n < | instructions |
| | |
| | |
| | |
+-- +---------------------+
Fig. 3. Compiled Instruction Sequence Format
[Page 5]
The format of the compiled Label Table is shown in Fig. 4.
16 bits
+-----/\-------+
/ \
+-----------------+
| length n |
| in bytes |
+-- +------------------+-----------------+
| | numeric value of | byte offset |
| | statement number | in inst. seq. |
| +------------------+-----------------+
| | : : |
n < | : : |
| | : : |
| | |
| | |
| | |
+-- +------------------------------------+
\_________________ _________________/
V
32 bits
Fig. 4. Compiled Label Table
[Page 6]
Literals and Identifiers are compiled as shown in fig. 5.
2 2
+----/\----+ +----/\----+
/ \ / \
+-------------+--------------+
1 1 | length n | length n |
___/\____ ___/\____ | in bytes | in bytes |
+---------+----------+-------------+--------------+
/ | |//////////| | |
| | Type |//////////| bit length | byte offset |
| | |//////////| | |
| +---------+----------+-------------+--------------+
5*n < | : |
| | : |
| | : | Identifiers
| | |
\ | |
+-------------------------------------------------+
/ | |
| | literals are |
| | byte-aligned | Literals
m < | |
| | |
| | |
\ +-------------------------------------------------+
Legend:
Type 0 = undefined
1 = B (binary)
2 = 0 (octal)
3 = X (hexadecimal)
4 = E (EBCDIC)
5 = A (ASCII)
6 = ED (EBCDIC encoded decimal)
7 = AD (ASCII encoded decimal)
8 = SB (signed binary, two's complement)
Fig. 5. Compiled Literals and Identifiers
[Page 7]
Types B, 0, X, AD, ED, and SB point to 32-bit word- aligned data shown below.
+---+---+-----+-------+ +-------------------+ word-aligned, | T |///| L | ---+-----> | | 32-bit right- +---+---+-----+-------+ +-------------------+ justified
Types E and A point to byte-aligned symbol streams
byte-aligned, L <= 256
+---+---+-----+-------+ +------------------------+ | T |///| L | ---+-----> | | +---+---+-----+-------+ +------------------------+
[Page 8]
Since literals and identifiers will be stored in the same data
+--------+------------------------+
| 4 | 12 |
+--------+------------------------+
|
/
/
/
|
V
LD = 0 literal or identifier reference (12-bit positive integer)
IC = 1 12-bit two's complement integer constant
OP = 2 operator
AD = 3 address (12-bit positive integer)
ARB = 4 indefinite replication factor
NULL = 5 missing attribute of term
The operation code decoder picks up types 0, 1, 3, 4,
The decoder examines OP elements further:
4 4 8
+--------+--------+----------------+
| 0010 | |////////////////|
+--------+--------+----------------+
OP |
+----------> 0 = binary operator
1 = unary operator
2 = special operator
[Page 9]
Let the TOS contain y and the next level, x. The binary operators
+---+ <-- TOS +-----+ <-- TOS
| y | | x-y |
e.g. x-y => +---+ ===> +-----+
| x | |/////|
+---+ +-----+
4 4 4 4
+--------+--------+--------+--------+
| 0010 | 0000 | |////////|
+--------+--------+--------+--------+
|
+--------------------------+
|
V
0 = integer +
1 = integer -
2 = integer x
3 = integer : (or /), no remainder
4 = concatenate ||
All binary operations except concatenate expect the top
-------
(*) As suggested above, the stack really contains instruction
[Page 10]
type L value T L V
+------+------+------+ +------+------+------+
TOS -> | B | 32 | 4 | | B | 32 | 12 | <- TOS
+------+------+------+ ==> +------+------+------+
| B | 8 | 16 | |//////|//////|//////|
+------+------+------+ +------+------+------+
Before-operation after-operation
+------+------+------+ +------+------+------+
TOS -> | A | 2 | DE | | A | 5 |ABCDE | <- TOS
+------+------+------+ ==> +------+------+------+
| A | 3 | ABC | |//////|//////|//////|
+------+------+------+ +------+------+------+
Before || operation after || operation
4 4 4 4
+--------+--------+--------+--------+
| 0010 | 0001 | | |
+--------+--------+--------+--------+
| |
+--------------+ |
| |
V |
0 = integer minus V
1 = load identifier 0 = evaluated contents
(after dec - binary
conversion)
1 = length field
2 = type field
2 = Label Table Reference
[Page 11]
For the unary minus operator the data described by the top of the
4 4 4 4
+--------+--------+--------+--------+
| 0010 | 0010 | | |
+--------+--------+--------+--------+
| |
+-----------------------+ /
| /
V /
0 = store TOS |
1 = return V
2 = branch 0 = true, 1 = false, 2 = unconditional
3 = compare 0 = .EQ. 2 = .LE. 4 = .GE.
1 = .NE. 3 = .LT. 5 = .GT.
4 = move input ptr 0 = store current into initial
1 = store initial into current
5 = input call 0 = no compare
1 = compare
6 = output call
[Page 12]
The TOS describes an index into the ID table and the next lower
The TOS describes a value to be returned to the routine which
The TOS describes an index into the instruction sequence to be used
The compare operator takes the two elements described by the two
This operator (no operands) replaces the Current Input Pointer with
This is the most complex operator thus far encountered. It requires
[Page 13]
| binary or null | length to find
+----------------------------+
| LD to literal or null | value (literal)
+----------------------------+
| binary code | input data type
+----------------------------+
| binary, arbitrary, or null | replication count
+----------------------------+
The input call operator can be invoked with the "no compare" flag
If the "compare" flag is set, the input stream must be searched for
If the input string matches, then the TRUE/FALSE flag is set true,
When a successful match is found the input subroutine always
[Page 14]
This routine utilizes the same parameters as the input call, but
(1,ED,X"FF",3) = E'255'
(1,ED,X"100",3) = E'256'
but (1,ED,SB"10000000",4) = E'-256'
If the output routine is able to perform the desired action, it
[Page 15]
INN = no compare )
current -> initial SCIP CIP -> IIP (store current input
ptr - initial IP)
initial -> current SICP IIP -> CIP (store initial input
ptr - CIP)
[Page 16]
ADDR. INSTR. COMMENTS
(NUMB.<=.1); 0 SICP RULE PRELUDE
1 IC 1
2 LD 0 REFERENCE TO NUMB
3 STO STORE IN NUMB
4 SCIP RULE POSTLUDE
1 CC(,E,,1:FR(99)), 5 SICP RULE PRELUDE
6 NULL NO REPLICATION EXPRESSION
7 IC 4 TYPE EBCDIC
8 NULL NO VALUE EXPRESSION
9 IC 1 LENGTH
10 INN INPUT CALL WITH NO COMPARE
11 AD 15
12 BT SKIP RETURN IF INN SUCCEEDS
13 IC 99 RETURN CODE
14 RET RETURN TO CALLER IF FAILED
15 LD 1 REFERENCE TO CC
16 STO STORE INPUT DATA IN CC
LINE(,E,,121: 17 NULL NO REPLICATION EXPRESSION
FR(99)), 18 IC 4 TYPE IS EBCDIC
19 NULL NO VALUE EXPRESSION
20 IC 121 LENGTH
21 INN INPUT WITH NO COMPARE
22 AD 26
23 BT SKIP RETURN IF OK
24 IC 98 RETURN CODE
25 RET RETURN TO CALLER IF FAILED
26 LD 2 REFERENCE TO LINE
27 STO STORE INPUT IN LINE
:CC, 28 SCIP SUCCESSFUL INPUT
29 NULL NO REPLICATION FACTOR
30 LD 1 REFERENCE TO CC
31 LIT TYPE OF CC
32 LD 1 REFERENCE TO VALUE OF CC
33 LD 1 CC AGAIN
34 LIL LENGTH OF CC
35 OUT OUTPUT CC
(,ED,NUMB,2), 36 NULL NO REPLICATION
37 IC 6 TYPE IS ED
38 LD 0 REFERENCE TO VALUE OF NUMB
39 IC 2 LENGTH OF OUTPUT FIELD
40 OUT OUTPUT NUMB AS EBCDIC DEC.
(,E,E".",1), 41 NULL NO REPLICATION
42 IC 4 TYPE IS EBCDIC
[Page 17]
43 LD 3 REFERENCE TO E"."
44 IC 1 LENGTH TO OUTPUT
45 OUT OUTPUT THE PERIOD
(,E,LINE,117), 46 NULL NO REPLICATION
47 IC 4 TYPE IS EBCDIC
48 LD 2 REFERENCE TO LINE
49 IC 117 LENGTH TO OUTPUT
50 OUT PUT OUT CONTENTS OF LINE
(NUMB.<=.NUMB+1: 51 LD 0 REFERENCE TO NUMB
U(1)); 52 IC 1 AMOUNT TO ADD
53 ADD ADD TO NUMB
54 LD 0 REFERENCE TO NUMB
55 STO STORE BACK INTO NUMB
56 AD 5 PLACE TO GO
57 B UNCONDITIONAL BRANCH BACK
LITERAL/IDENTIFIER TABLE
0 NUMB
1 CC
2 LINE
3 E"."
LABEL TABLE
LABEL OFFSET
1 5
[ This RFC was put into machine readable form for entry ] [ into the online RFC archives by Simone Demmel 6/97 ]
[Page 18]