by Darius Kazemi, July 13 2019

In 2019 I'm reading one RFC a day in chronological order starting from the very first one. More on this project here. There is a table of contents for all my RFC posts.

Stack machine

RFC-194 is titled “The Data Reconfiguration Service — Compiler/Interpreter Implementation Notes”. It's by Cerf, Harslem, Heafner, Metcalfe, and White, and undated but presumably was published in July 1971.

The technical content

This is more output from a subcommittee. This lays out technical changes to the Data Reconfiguration Service language/service, previously detailed in RFC-83 and RFC-138. Among these is a new assignment operator, .<=., which is essentially a “deep assignment” that fully assigns the attributes of one identifier to another. There's a concatenation operator, and some new data types for base 10 representation of EBCDIC and ASCII codes.

I love their description of the CPU as "a box full of miscellaneous parts, the most important being the Arithmetic Logic Unit and the instruction decoding unit". They provide a really nice box diagram of a generic CPU in Figure 2. The CPU for the DRS uses a reverse Polish notation instruction set, though they use the less common in 2019 terminology “Polish postfix”.

The CPU is a stack machine, which I had not heard of before looking it up just now. It's a computer that uses a stack (last-in, first-out) instead of a series of registers to store critical memory. So if you want to add two numbers, instead of putting one in register A and one in register B and then asking the ALU to do an “add”, you instead just tell the ALU “add” and it pops the two most recent values off the stack and adds them together.

There's a lot of detailed information in the document. The instruction format uses 16-bit instructions comprised of a 4-bit opcode and 12 bits for a literal or identifier reference, which is necessary because the architects expect more than 256 literals and identifiers combined. What's interesting to me is that the instruction has the 4-bit opcode, but one of the opcodes is the opcode for “operator”, at which point the 12 bits contain an identifier further specifying another opcode. The other “opcodes” are more like data type tags: this instruction contains an address, this contains a literal reference, this contains an integer constant, etc.

There's a lot of extremely detailed reference to how the stack machine works, and liberal usage of the acronym “TOS”, meaning “top of stack”. There's enough information here that someone could probably write a full emulator for the Data Reconfiguration Service as it existed in July 1971!


Broadly, this RFC is a great read if you are a nerd, and also I really, really want someone to write an emulator.

When I was checking the online records versus the paper originals, I noticed a transcription error in Figure 1, “Form Interpreter.” The arrows connecting “inputstream” and “outputstream” to “CPU” are in reverse direction. Here's the original and the online version.

Photo of a paper document held next a computer monitor, showing the discrepancy described above.

How to follow this blog

You can subscribe to this blog's RSS feed or if you're on a federated ActivityPub social network like Mastodon or Pleroma you can search for the user “@365-rfcs@write.as” and follow it there.

About me

I'm Darius Kazemi. I'm an independent technologist and artist. I do a lot of work on the decentralized web with ActivityPub, including a Node.js reference implementation, an RSS-to-ActivityPub converter, and a fork of Mastodon, called Hometown. You can support my work via my Patreon.