(Strings) and arrays

This chapter is more technical. PostScript does also have to deal with strings and arrays, so we have to add support for them.

Strings are enclosed by paranthesises () and arrays by square brackets [], this is the easy part. But we also have to deal with an implementation detail of PostScript. Strings, arrays (and also procedures) are composite data types, and these data types are not stored by value, but by reference. If you assign (string) to foo, then you only add a reference to (string) to foo. If you assign foo to bar, there is no copy of (string), only the references is copied. So if you modify (string) itself with operators like put or putinterval, you modify both the value of foo and bar.

It's strange but we have to live with that. PostScript could have developed operators that combine strings and return new strings. This would have be a pure functional approach. But in the 1980s memory was expensive and they decided to go the reference way.

Our context needs therefore also to maintain a heap array to store the value. We implement the heap as a simple array. The position in the array is the reference.

We now have many datatypes: number, string, name, procedure and array. Many occasions to make type errors. We add to the context a function arguments context.pop() that gets all arguments for the operators, checks their types and returns them as an array.

Javascript

rpnArray = class {
   constructor(x, context) { 
     this.heap = context.heap;
     this.reference = this.heap.length;
     this.heap.push(x);
   }
   get type() { return "array"; }
   get dump() { return "[" + this.value.reduce((acc,x) => acc + x.dump + " ","").trim() + "]"; }
   get value() { return this.heap[this.reference] ; }
   replace(x) { 
   if (this.heap[this.reference].length != x.length)
      throw "array length mismatch " + x.length + "/" + this.heap[this.reference].length;
      this.heap[this.reference] = x;
   }
};
rpnMark = class {
   constructor(x) { this.value = x; }
   get type() { return "mark"; }
   get dump() { return "[" ; }
};
rpnName = class {
   constructor(x) { this.value = x; }
   get type() { return "name"; }
   get dump() { return "/" + this.value; }
};
rpnNumber = class { 
   constructor(x) { this.value = x;}
   get type() { return "number"; }
   get dump() { return this.value.toString(); }
};
rpnProcedure = class { 
   constructor(x) { this.value = x;}
   get type() { return "procedure"; }
   get dump() { return "{" + this.value + "}"; }
};
rpnString = class { 
   constructor(x, context) { 
     this.heap = context.heap;
     this.reference = this.heap.length;
     this.heap.push(x);
   }
   get type() { return "string"; }
   get dump() { return "(" + this.value + ")"; }
   get value() { return this.heap[this.reference] ; }
   replace(x) { 
   if (this.heap[this.reference].length != x.length)
      throw "string length mismatch " + x.length + "/" + this.heap[this.reference].length;
      this.heap[this.reference] = x;
   }
};

rpn = function(s, context = null ) {  
    if (!context) {
       context = {};
       context.stack = [];
       context.dict = {};
       context.heap = [];
       
       context.pop = function (...args) {
         if (this.stack.length < args.length) {
            throw "stackunderflow " + stack.length + "/" + args.length;
         }
         const result = [];
         for (var p of args) {
            const data = this.stack.pop(); 
            if (p == "any") {
              result.push(data);
            } else if (p.includes(data.type)) {
               result.push(data);   
            } else {
              throw "typeerror " + p + "/" + data.type;
            }
         }
         return result;
       }
       context.popArray = function() {
          var found = false;
          var arr = [];
          while (this.stack.length && ! found) {
             const value = this.stack.pop();
             if (value.type == "mark") {
               found = true;
             } else {
               arr.push(value);
             }   
          }
          if (! found) {
             throw "stackunderflow ]";
          }
          arr.reverse();
          this.stack.push(new rpnArray(arr, context)); 
       }
    }
    const list = s.concat(" ").split("");
    var state = "start";
    var current = "";
    var depth = 0;
    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 (elem == "/") {
                    state = "namestart";
                }  else if (elem == "{") {
                    state = "procedure";
                }  else if (elem == "(") {
                    state = "string";
                }  else if (elem == "[") {
                    context.stack.push(new rpnMark()); //mark
                }  else if (elem == "]") {
                    context.popArray();
                }  else if (elem == "%") {
                    state = "comment";
                }  else if (elem.trim() === '') {
                    // ignore whitespace
                }  else  {
                    throw new Error ("invalid character " + elem)
                } 
                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 (elem.trim() === "") {
                    context.stack.push(new rpnNumber(parseFloat(current)));
                    state = "start";
                    current = "";
                } else if (elem == "]") {
                    context.stack.push(new rpnNumber(parseFloat(current)));
                    state = "start";
                    current = "";
                    context.popArray();
                }  else {
                    throw new Error ("invalid character " + current + elem);
                }
                break;
            case "fraction":
                if (/[0-9]/.test(elem)) {
                    current += elem;
                } else if (elem.trim() === "") {
                    context.stack.push(new rpnNumber(parseFloat(current)));
                    state = "start";
                    current = "";
               } else if (elem == "]") {
                    context.stack.push(new rpnNumber(parseFloat(current)));
                    state = "start";
                    current = "";
                    context.popArray();
               } else {
                    throw new Error("invalid character " + current + elem);
               }
               break;
            case "operator":
                if (/[a-zA-Z0-9]/.test(elem)) {
                    current += elem;
                } else if (elem.trim() !== "" && elem != "]"){
                    throw new Error("invalid character " + current + elem);
                } else {
                    const data = context.dict[current];
                    const op = operators[current];
                    if (data) {
                       if (data.type == "procedure") {
                          context = rpn(data.value, context);
                       } else {
                          context.stack.push(data);
                       }
                    } else if (op) {
                       context = op(context);
                    } else {
                        throw new Error("invalid operator " + current);
                    }
                    state = "start";
                    current = "";
                    if (elem == "]") {
                       context.popArray();
                    }

}
                break;
           case "namestart":
                if (/[a-zA-Z]/.test(elem)) {
                    state = "name";
                    current = elem;
                } else {
                   throw new Error("invalid character /" +  current + elem);
                }
                break;
            case "name":
                if (/[a-zA-Z0-9]/.test(elem)) {
                    current += elem;
                } else if (elem.trim() === "") {
                    context.stack.push(new rpnName(current));
                    state = "start";
                    current = "";
               } else if (elem == "]") {
                    context.stack.push(new rpnName(current));
                    state = "start";
                    current = "";
                    context.popArray();
               } else  {
                    throw new Error("invalid character " + current + elem);
               }
                break;
            case "procedure":
               if (elem == "}") {
                   if (depth) {
                      depth--;
                      current += elem;
                   } else {
                        context.stack.push(new rpnProcedure(current));
                        state = "start";
                        current = "";
                   }
               } else if (elem == "{") {
                  depth++;
                  current += elem;
               } else {
                   current += elem;
               }
               break;
           case "string":
               if (elem == ")") {
                   if (depth) {
                      depth--;
                      current += elem;
                   } else {
                        context.stack.push(new rpnString(current, context));
                        state = "start";
                        current = "";
                   }
               } else if (elem == "(") {
                  depth++;
                  current += elem;
               } else {
                   current += elem;
               }
               break;
           case "comment":
             if (elem == endofline ) {
                state = "start";
             }
        } // switch state
    } // for
    if (state !== "start") {
         throw new Error("invalid state " + state + " " + current + elem);
    }
      return context;
};

The code for the operators becomes very cleaner.

operators.add = function(context) { const [b, a] = context.pop("number", "number"); if (!b) return context; context.stack.push(new rpnNumber(a.value + b.value)); return context; };

In the first line, we use the Javascript feature that allows you to assign array elements directly to constant. If there was any error, the first constant will be undefined and the operator stops.
In the following lines, the operator calculates the result and pushes it back to the stack.
The operator always returns the context to be reused.

Javascript

operators = {};

operators.add = function(context) {
    const [b, a] = context.pop("number", "number");
    if (!b) return context;
    context.stack.push(new rpnNumber(a.value + b.value));
    return context;
};

operators.sub = function(context) {
    const [b, a] = context.pop("number", "number");
    if (!b) return context;
    context.stack.push(new rpnNumber(a.value - b.value));
    return context;
};

operators.mul = function(context) {
    const [b, a] = context.pop("number", "number");
    if (!b) return context;
    context.stack.push(new rpnNumber(a.value * b.value));
    return context;
};

operators.div = function(context) {
    const [b, a] = context.pop("number", "number");
    if (!b) return context;
    context.stack.push(new rpnNumber(a.value / b.value));
    return context;
};

operators.sin = function(context) {
    const [a] = context.pop("number");
    if (!a) return context;
    context.stack.push(new rpnNumber(Math.sin(a.value * 3.1415926536 / 180)));
    return context;
};

operators.cos = function(context) {
    const [a] = context.pop("number");
    if (!a) return context;
    context.stack.push(new rpnNumber(Math.cos(a.value * 3.1415926536 / 180)));
    return context;
};

operators.def = function(context) {
    const [b, a] = context.pop("any", "name");
    if (!b) return context;
    context.dict[a.value] = b;
    return context; 
};

operators.dup = function(context) {
    const [a] = context.pop("any");
    if (!a) return context;
    context.stack.push(a);
    context.stack.push(a);
    return context;
};

operators.pop = function(context) {
    const [a] = context.pop("any");
    return context;
};

operators.exch = function(context) {
    const [b, a] = context.pop("any", "any");
    if (!b) return context;
    context.stack.push(b);
    context.stack.push(a);
    return context;
};

operators.true = function(context) {
    context.stack.push(new rpnNumber(1));
    return context;
};

operators.false = function(context) {
    context.stack.push(new rpnNumber(0));
    return context;
};

operators.not = function(context) {
    const [a] = context.pop("number");
    if (!a) return context;
    context.stack.push(new rpnNumber(a.value ? 0 : 1));
    return context;
};

operators.and = function(context) {
    const [b, a] = context.pop("number", "number");
    if (!b) return context;
    context.stack.push(new rpnNumber(a.value && b.value ? 1 : 0));
    return context;
};

operators.or = function(context) {
    const [b, a] = context.pop("number", "number");
    if (!b) return context;
    var result = 0;
    if (a.value) result = 1;
    if (b.value) result = 1;
    context.stack.push(new rpnNumber(result));
    return context;
};

operators.eq = function(context) {
    const [b, a] = context.pop("number,string", "number,string");
    if (!b) return context;
    if (a.type != b.type) {
       return context.error("typeerror");
    }
    context.stack.push(new rpnNumber(a.value == b.value ? 1 : 0));
    return context;
};

operators.ne = function(context) {
    const [b, a] = context.pop("number,string", "number,string");
    if (!b) return context;
    if (a.type != b.type) {
       return context.error("typeerror");
    }
    context.stack.push(new rpnNumber(a.value != b.value ? 1 : 0));
    return context;
};

operators.gt = function(context) {
    const [b, a] = context.pop("number,string", "number,string");
    if (!b) return context;
    if (a.type != b.type) {
       return context.error("typeerror");
    }
    context.stack.push(new rpnNumber(a.value > b.value ? 1 : 0));
    return context;
};

operators.ge = function(context) {
    const [b, a] = context.pop("number,string", "number,string");
    if (!b) return context;
    if (a.type != b.type) {
       return context.error("typeerror");
    }
    context.stack.push(new rpnNumber(a.value >= b.value ? 1 : 0));
    return context;
};

operators.lt = function(context) {
    const [b, a] = context.pop("number,string", "number,string");
    if (!b) return context;
    if (a.type != b.type) {
       return context.error("typeerror");
    }
    context.stack.push(new rpnNumber(a.value < b.value ? 1 : 0));
    return context;
};

operators.le = function(context) {
    const [b, a] = context.pop("number,string", "number,string");
    if (!b) return context;
    if (a.type != b.type) {
       return context.error("typeerror");
    }
    context.stack.push(new rpnNumber(a.value <= b.value ? 1 : 0));
    return context;
};

operators.if = function(context) {
    const [doif, condition] = context.pop("any", "number");
    if (!doif) return context;
    if (condition.value) { 
       context = rpn(doif.value, context);
    }
    return context;
};

operators.ifelse = function(context) {
    const [doelse, doif, condition] = context.pop("any", "any",  "number");
    if (!doelse) return context;
    if (condition.value) {
       context = rpn(doif.value, context);
    } else {
       context = rpn(doelse.value, context);
    }
    return context;
};

We adapt postScriptEditor to show the values correctly and to the heap

Javascript

postScriptEditor = function(code) {
    const id = Math.floor(Math.random() * 1000);  // create unique id for console.log
    const node = document.createElement("DIV");   // build the HTML nodes
    node.id = "id" & id;
    node.className = "psmain";
    const node2 = document.createElement("DIV");
    node2.className = "editzone";
    node.appendChild(node2);
    const node3 = document.createElement("DIV");
    node3.className = "editheader";
    node3.innerHTML = "PostScript";
    node2.appendChild(node3);
    const node4 = document.createElement("FORM");
    node2.appendChild(node4);
    const node5 = document.createElement("BUTTON");
    node5.type = "button";
    node5.id = "button" + id;
    node5.innerHTML = "Run";
    node4.appendChild(node5);
    const node6 = document.createElement("TEXTAREA"); 
    node6.id = "editor" + id; 
    node6.className = "pseditor"; 
    node6.innerHTML = code
    node4.appendChild(node6);
    const node7 = document.createElement("DIV");
    node7.id = "console" + id;
    node7.className = "jsconsole";
    node.appendChild(node7);
    console.log(node.outerHTML);  // add the node to the parent element

We try it out.

Javascript Editor

The main operators on strings and arrays are length, get, getinterval, put, putinterval. Get returns the character code of one character, getinterval returns an entire string. Put sets the character code at a position in the string and putinterval replaces a substring. Note that put and putinterval operate on the original string which keeps the same length.

Javascript

operators.length = function(context) {
    const [a] = context.pop("array,string");
    if (!a) return context;
    context.stack.push(new rpnNumber(a.value.length));
    return context;
};

operators.get = function(context) {
    const [b, a] = context.pop("number", "array,string");
    if (!b) return context;
    if (b.value < 0) return context.error("rangerror");
    if (b.value >= a.value.length) return context.error("rangerror");
    if (a.type == "array") {
       context.stack.push(a.value[b.value]);
    } else {
       context.stack.push(new rpnNumber(a.value.charCodeAt(b.value)));
    }
    return context;
};

operators.getinterval = function(context) {
    const [c, b, a] = context.pop("number", "number", "array,string");
    if (!c) return context;
    if (b.value < 0) return context.error("rangerror");
    if (c.value < 0) return context.error("rangerror");
    if (b.value + c.value > a.value.length) return context.error("rangerror");
    if (a.type == "array") {
       context.stack.push(new rpnArray(a.value.slice(b.value, b.value + c.value), context));
    } else {
       context.stack.push(new rpnString(a.value.substr(b.value, c.value), context));
    }
    return context;
};

operators.put = function(context) {
    const [c, b, a] = context.pop("any", "number", "array,string");
    if (!c) return context;
    if (b.value < 0) return context.error("rangerror");
    if (b.value >= a.value.length) return context.error("rangerror");
    if (a.type == "array") {
       const ch = [ c ];
       const s = a.value.slice(0, b.value).concat(ch).concat(a.value.slice(b.value+1, a.value.length));
       a.replace(s);
    } else {
       const ch = String.fromCharCode(c.value);
       const s = a.value.slice(0, b.value) + ch + a.value.slice(b.value + 1 , a.value.length);
       a.replace(s);
    }

return context;
};

operators.putinterval = function(context) {
    const [c, b, a] = context.pop("string,array", "number", "array,string");
    if (!c) return context;
    if (b.value < 0) return context.error("rangerror");
    if (b.value + c.value.length > a.value.length) return context.error("rangerror");
    if (a.type !== c.type) return context.error("typeerror");
    if (a.type == "array") {
       const s = a.value.slice(0, b.value).concat(c.value).concat(a.value.slice(b.value + c.value.length, a.value.length));
       a.replace(s);
    } else {
       const s = a.value.slice(0, b.value) + c.value + a.value.slice(b.value + c.value.length , a.value.length);
       a.replace(s);
    }
    return context;
};

We try it out.

Javascript Editor

The heap fills up with text which is not referenced any more so it should be freed. We will do that later.

And for put we see the change in heap affects also the original variable

Javascript Editor

code	stack	dict	heap
/a	/a
(foo)	/a (foo)		(foo)
def		a = (foo)	(foo)
/b	/b	a = (foo)	(foo)
a	/b (foo)	a = (foo)	(foo)
def		a = (foo) b = (foo)	(foo)
b	(foo)	a = (foo) b = (foo)	(foo)
1	(foo) 1	a = (foo) b = (foo)	(foo)
get	111	a = (foo) b = (foo)	(foo)
1	111 1	a = (foo) b = (foo)	(foo)
add	112	a = (foo) b = (foo)	(foo)
b	112 (foo)	a = (foo) b = (foo)	(foo)
exch	(foo) 112	a = (foo) b = (foo)	(foo)
1	(foo) 112 1	a = (foo) b = (foo)	(foo)
exch	(foo) 1 112	a = (foo) b = (foo)	(foo)
put		a = (fpo) b = (fpo)	(fpo)
a	(fpo)	a = (fpo) b = (fpo)	(fpo)

The new code is entirely rewritten and has 625 lines ps20240629.js

My Journey to PostScript