SPL : Stack Programming Language

By Jacques Bailhache ( jacques.bailhache@gmail.com ) February 2022

Data

SPL uses symbolic expressions like LISP. A symbolic expression is either an atom (number, string, symbol...), a pair of symbolic expressions, or a vector of symbolic expressions. A string is written between double quotes ("). A pair of symbolic expressions a and b is written (a . b). A list is represented by nested pairs, for example (a . (b . (c . (d . nil))) which may also be written (a b c). Writing of nested list can be simplified, for example (a b c (d e f)) may be written (a b c : d e f).

Program

A program is a list of instructions executed successively from left to right.

Context

A context represents the state of execution of the program at some time. A context contains the program, two stacks and an environment containing the values of variables.

Execution

Execution consists in repetitively taking the first instruction from the program and applying its effects on the context.

Example

This is an example of a program that pushes the symbol FOO on the main stack, then the symbol BAR, then makes a pair with them and prints the result :

(QUOTE FOO QUOTE BAR CONS PRINT)
(BAR . FOO)

Instructions

QUOTE

QUOTE pushes the next instruction to the main stack.

Combinators

Combinators are instructions acting on the program :

I ... -> ...
K a b -> a
S a b c -> a c (b c)

Stack manipulation instructions

DROP drops the top of the main stack
DUP duplicates the top of the main stack
SWAP swaps the tho items on top of the main stack

Conditional

If the top of the main stack is true, (THEN a b) drops b and only a is executed, otherwise it drops a and only b is executed.

Symbolic expressions manipulation

CAR replaces a pair at the top of the main stack by its first component
CDR replaces a pair at the top of the main stack by its second component
CONS pushes on the main stack a pair built with the two items at the top of the main stack
EQ pushes a true value at the top of the main stack if the two items at the top of the main stack are equal, otherwise it pushes a false value.