Reverse Polish Scheme

Reverse Polish Scheme

Paradigm(s)	Imperative, Stack-Based, Functional
Designed by	User:McGoron
Appeared in	2025
Computational class	Turing Complete
Major implementations	R4RS
Influenced by	Scheme, FORTH

Reverse Polish Scheme (RPS) is a homoiconic, stack-based programming language with reified continuations. Its syntax is a subset of Scheme. RPS can only use call/cc to manipulate the stack and instruction pointer. Stack operations, returns from calls, closures, delimited continuations, and all sorts of other fun things can be created using RPS's call/cc.

Core

RPS syntax is a subset of Scheme.

Line comments start with ;. Nested block comments start with #| and end with |#. Writing a number, string, #t, or #f will push that literal value onto the stack. Writing an identifier will execute that identifier.

A literal vector is introduced with #( and ends with ). A literal list (a linked list where each list cell is a vector of two elements) starts with ( and ends with ). The empty list (nil) is represented by (). A literal identifier is introduced with '. (Note that lists and vectors are not quoted.)

A procedure is a linked list whose first element can be used for data storage, and whose tail is a linked list of instructions to execute. By convention, procedures that do not have any data to save in their first element have their first element be #f.

If the interpreter hits the end of a procedure, it will halt.

The following are the built in instructions. Instructions will execute and continue at the next instruction (exceptions are call/cc and jump). They will consume all specified arguments to them.

Command	Description
proc to from call/cc	The fundamental stack manipulator. Jump to proc with the continuation cc pushed to the stack. When m cc jump is called, control returns to the instruction after call/cc, except that the stack is the m values on the stack before the jump appended to the values on the stack from from inclusive to to exclusive at the site of call/cc's invocation. If from is #f, then it will capture the entire stack starting from to exclusive.
bool on-false on-true if	If bool is #f, jump to the procedure on-false. Otherwise jump to the procedure on-true.
proc jump	The next executed instruction will be the first instruction of proc. Note that is no return stack.
n vector	Allocate a vector of n cells and push it to the stack.
vec vector-length	Push the length in cells of vec. Returns #f if vec is not a vector.
vec n ref	Push the nth cell of vec to the stack.
value n vec set!	Set the nth cell of vec to value.
x y eqv?	Pushes a boolean indicating if x and y are equivalent objects (i.e. the same vector or equal numbers).
x symbol?	Pushes a boolean indicating if x is a symbol.
x integer?	Pushes a boolean indicating if x is an exact integer.
x real?	Pushes a boolean indicating if x is a real.
x y +	Pushes x + y.
x y *	Pushes x * y.

Examples

The stack is notated as if it was a LISP list. The first element of the list is the top of the stack.

The following code will duplicate the top of the stack.

1 (#f jump) #f 1 call/cc

Explanation:

• 1, a procedure, #f, 1 are pushed to the stack. The stack looks like (1 #f <proc> 1 x values ...).
• call/cc is invoked. It will jump to <proc> with the stack (<cc> 1 x values ...).
• <cc> is jumped into with the argument 1. It will return to the position after the invocation of call/cc, pushing x onto a stack that was the stack at the invocation of call/cc, sans one element (the first 1 pushed). Hence the stack is (x x values ...).

This code is normally inlined and used as a macro. A Lisp interpreter can be used as a value-level macro processor for RPS. Since there is no lexical scope, there is no need for hygienic macros. Quasiquote works well to splice in code.