4 3 add 2 mul - PostScript as a programming language

PostScript uses the Reversed Polish Notation (RPN) which in its purest form, is a string with values and operators that work on a stack.

A stack is an array of values with no limited length. At the beginning, the stack is empty. You can push values on the top of the stack and pop them to get them back. The current value of a stack is the top most item.

The first PostScript machine we build here in Javascript is a RPN calculator. The machine reads the program which is a string of tokens separated by space. A token is a word in the string separated by space.

En example program would be "4 3 add 2 mul"

If the token is a number, it is pushed on the stack
If the token is a word, we read the word as operator. The operator might pop some values, make some calculations and then push some values on the stack.

In detail for our example

token	stack
4	4
3	4 3
add	7
2	7 2
mul	14

This is all of it. There are no variables, no control structures, just linear execution of code, however, you still can make complex calculations.

We use a state machine to parse the program. A state machine reads each character at once and performs an action when it has identified a token.

A number starts with a digit or dash, and continues with digits and at most one period.
An operator starts with a letter and continues with letters or digits.
All other characters are treated as space.

This graphical representation was made with the postscript code on the right

% label x y
/state {
gsave
translate 0 0 30 0 360 arc stroke
dup stringwidth pop 2 div neg -3 moveto show
grestore
} def

/atartstate {
gsave
translate 0 0 30 0 360 arc stroke
0 0 25 0 360 arc stroke
dup stringwidth pop 2 div neg -3 moveto show
grestore
} def

% label x1 y1 x2 y2
/path {
gsave
/y2 exch def /x2 exch def /y1 exch def /x1 exch def /label exch def
/a y2 y1 sub x2 x1 sub atan def
% line
x1 a cos 30 mul add y1 a sin 30 mul add moveto
x2 a cos 30 mul sub y2 a sin 30 mul sub lineto stroke
% arrows
x2 a cos 30 mul sub y2 a sin 30 mul sub moveto
a 150 add cos 10 mul a 150 add sin 10 mul rlineto stroke
x2 a cos 30 mul sub y2 a sin 30 mul sub moveto
a -150 add cos 10 mul a -150 add sin 10 mul rlineto stroke
% label
x1 a cos 40 mul add 3 sub y1 a sin 40 mul add 2 sub moveto
label stringwidth pop 3 add 0 rlineto 0 12 rlineto
label stringwidth pop 3 add neg 0 rlineto 0 -12 rlineto
0.8 setgray fill
x1 a cos 40 mul add y1 a sin 40 mul add moveto
0 setgray label show
grestore
} def

% label x1 y1 x2 y2 x3 y3 x4 y4
/path2 {
gsave
/y4 exch def /x4 exch def /y3 exch def /x3 exch def
/y2 exch def /x2 exch def /y1 exch def /x1 exch def /label exch def
% line
/a1 y2 y1 sub x2 x1 sub atan def
/a4 y4 y3 sub x4 x3 sub atan def
x1 a1 cos 30 mul add y1 a1 sin 30 mul add moveto
x2 y2 lineto
x2 a1 cos 50 mul add y2 a1 sin 50 mul add
x3 a4 cos 50 mul sub y3 a4 sin 50 mul sub
x3 y3 curveto
x4 a4 cos 30 mul sub y4 a4 sin 30 mul sub lineto stroke
% arrows
x4 a4 cos 30 mul sub y4 a4 sin 30 mul sub moveto
a4 150 add cos 10 mul a4 150 add sin 10 mul rlineto stroke
x4 a4 cos 30 mul sub y4 a4 sin 30 mul sub moveto
a4 -150 add cos 10 mul a4 -150 add sin 10 mul rlineto stroke
% label
x1 a1 cos 50 mul add 3 sub y1 a1 sin 50 mul add 2 sub moveto
label stringwidth pop 3 add 0 rlineto 0 12 rlineto
label stringwidth pop 3 add neg 0 rlineto 0 -12 rlineto
0.8 setgray fill
x1 a1 cos 50 mul add y1 a1 sin 50 mul add moveto
0 setgray label show
grestore
} def

/Helvetica findfont 12 scalefont setfont

(start) 100 200 atartstate
(number) 200 300 state
(fraction) 200 400 state
(operator) 200 100 state

(0-9-) 100 200 200 300 path
(0-9) 200 300 255 275 250 325 200 300 path2
(.) 200 300 200 400 path
(space) 200 300 150 325 100 250 100 200 path2
(0-9) 200 400 255 375 250 425 200 400 path2
(space) 200 400 150 425 75 250 100 200 path2
(a-z) 100 200 200 100 path
(a-z0-9) 200 100 255 75 250 125 200 100 path2
(space) 200 100 150 75 100 150 100 200 path2
showpage

My Journey to PostScript

In detail for our example

character	action	stack	state	current
4	-	empty	number	4
space	stack.push(4)	4	start	empty
3	-	4	number	3
space	stack.push(3)	4 3	start	empty
a	-	4 3	operator	a
d	-	4 3	operator	ad
d	-	4 3	operator	add
space	add(stack)	7	start	empty
2	-	7	number	2
space	stack.push(2)	7 2	start	empty
m	-	7 2	operator	m
u	-	7 2	operator	mu
l	-	7 2	operator	mul
space	mul(stack)	14	start	empty

Javascript

rpn = function(s) {
    var stack = [];
    const list = s.concat(" ").split("");
    var state = "start";
    var current = "";
    for (elem of list) {
        switch (state) {
            case "start":
                if (/[0-9-]/.test(elem)) {
                    state = "number";
                    current = elem;
                } else if (/[a-zA-Z]/.test(elem)) {
                    state = "operator";
                    current = elem;
                }  else if (/[.]/.test(elem)) {
                    throw new Error ("invalid character " + elem)
                } 
                // ignore spaces and invalid characters
                break;
            case "number":
                if (/[0-9]/.test(elem)) {
                    current += elem;
                } else if (elem == ".") {
                    state = "fraction";
                    current += elem;
                } else if (/[a-zA-Z-]/.test(elem)) {
                    throw new Error ("invalid character " + current + elem);
                }  else if (/[-]/.test(elem)) {
                    throw new Error ("invalid character " + current + elem)
                } else {
                    stack.push(parseFloat(current));
                    state = "start";
                    current = "";
                }
                break;
            case "fraction":
                if (/[0-9]/.test(elem)) {
                    current += elem;
                } else if (/[a-zA-Z.-]/.test(elem)) {
                    throw new Error("invalid character " + current + elem);
                } else {
                    stack.push(parseFloat(current));
                    state = "start";
                    current = "";
                }
                break;
            case "operator":
                if (/[a-zA-Z0-9]/.test(elem)) {
                    current += elem;
                } else if (/[.-]/.test(elem)) {
                    throw new Erroe("invalid character " + current + elem);
                } else {
                    const op = operators[current];
                    if (op) {
                       stack = op(stack);
                    } else {
                        throw new Error("invalid operator " + current);
                    }
                    state = "start";
                    current = "";
                    break;
                }
        } // switch state

} // for
    return stack.pop();
};

Now we just need to define some operators. We define add, sub, mul and div.
We set 0 if the stack is empty.

Javascript

You can try it out. Change the value of program and rerun the script

Javascript Editor

During our journey, our code will evolve. We will add features, fix bugs and sometimes refactor our code. On each chapter, we will reuse the code of the last chapter and only redefine functions, classes and objets when needed. To be able to do that, we always user variables to declare functions and classes.

The 94 lines of source code from this chapter are ps20240624.js

My Journey to PostScript