If then else - control structures

Until now, all operations of our PostScript machine are strictly linear. All code is executed once and without conditions. But without conditional execution, the machine is not Turning complete.

This problem is very easy to solve. We do have to modify our interpreter only slightly. We have to build a counter for the depth of the sequence, because a sequence may have sub-sequences.

What we need, is values (true, false), operators that can compare (equal, bigger, lower) and reverse (not) and operators. There will not be a Boolean type: 1 is true and 0 is false. We create an utility function rpnComparator to compare values.

Javascript

endofline = String.fromCharCode(10);

rpn = function(s, context = null ) {
    if (!context) {
       context = {};
       context. stack = [];
       context.dict = {};
    }
    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 = "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(parseFloat(current));
                    state = "start";
                    current = "";
                }  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(parseFloat(current));
                    state = "start";
                    current = "";
               } else {
                    throw new Error("invalid character " + current + elem);
               }
               break;
            case "operator":
                if (/[a-zA-Z0-9]/.test(elem)) {
                    current += elem;
                } else if (elem.trim() === '') {
                    const name = context.dict[current];
                    const op = operators[current];
                    if (name) {
                       context = rpn(name, context);
                    } else if (op) {
                       context = op(context);
                    } else {
                        throw new Error("invalid operator " + current);
                    }
                    state = "start";
                    current = "";
                } else {
                    throw new Error("invalid character " + current + elem);
                }
                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(current);
                    state = "start";
                    current = "";
               } else  {
                    throw new Error("invalid character " + current + elem);
               }
                break;
            case "procedure":
               if (elem == "}") {
                   if (depth) {
                      depth--;
                      current += elem;
                   } else {
                        context.stack.push(current);
                        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;
};

Javascript Editor

operators = {};
operators.add = function(context) {
    const b = context.stack.pop() ?? 0;
    const a = context.stack.pop() ?? 0;
    context.stack.push(a + b);
    return context;
};
operators.sub = function(context) {
    const b = context.stack.pop() ?? 0;
    const a = context.stack.pop() ?? 0;
    context.stack.push(a - b);
    return context;
};
operators.mul = function(context) {
    const b = context.stack.pop() ?? 0;
    const a = context.stack.pop() ?? 0;
    context.stack.push(a * b);
    return context;
};
operators.div = function(context) {
    const b = context.stack.pop() ?? 0;
    const a = context.stack.pop() ?? 0;
    context.stack.push(a / b);
    return context;
};

operators.sin = function(context) {
    const a = context.stack.pop() ?? 0;
    context.stack.push(Math.sin(a * 3.1415926536 / 180));
    return context;
};

operators.cos = function(context) {
    const a = context.stack.pop() ?? 0;
    context.stack.push(Math.cos(a * 3.1415926536 / 180));
    return context;
};

operators.def = function(context) {
    const b = context.stack.pop().toString() ?? "";
    const a = context.stack.pop() ?? "undefined";
    context.dict[a] = b;
    return context; 
}

operators.dup = function(context) {
    const a = context.stack.pop() ?? 0;
    context.stack.push(a);
    context.stack.push(a);
    return context;
};
operators.pop = function(context) {
    const a = context.stack.pop() ?? 0;
    return context;
};
operators.exch = function(context) {
    const b = context.stack.pop() ?? 0;
    const a = context.stack.pop() ?? 0;
    context.stack.push(b);
    context.stack.push(a);
    return context;
};

Javascript

operators.true = function(context) {
    context.stack.push(1);
    return context;
};
operators.false = function(context) {
    context.stack.push(0);
    return context;
};
operators.not = function(context) {
    const a = context.stack.pop() ?? 0;
    context.stack.push(a ? 0 : 1);
    return context;
}

rpnComparator = function(a,b) {
// returns 1 for bigger, -1 for lower and 0 for equal
// strings are compared alphabetically lowercase, except when equal all case
// all non empty strings are higher than numbers
// empty strings are lower than numbers
// NaN is lowest
// undefined and null should not happen
   
   if(typeof a == "number" && typeof b == "number") {
     if (a > b) return 1;
     if (a < b) return -1; 
     return 0;
   } else if (typeof a == "number") {
     return -1;
   } else if (typeof b == "number") {
     return 1;
   } else {
     const alow = a.toLowerCase();
     const blow = b.toLowerCase();
     if (alow > blow) return 1;
     if (alow < blow) return -1;
     if (a > b) return 1;
     if (a < b) return -1;
     return 0;
    }
}

operators.eq = function(context) {
    const b = context.stack.pop() ?? 0;
    const a = context.stack.pop() ?? 0;
    context.stack.push(rpnComparator(a,b) == 0 ? 1 : 0);
    return context;
};

operators.ne = function(context) {
    const b = context.stack.pop() ?? 0;
    const a = context.stack.pop() ?? 0;
    context.stack.push(rpnComparator(a,b) != 0 ? 1 : 0);
    return context;
};

operators.gt = function(context) {
    const b = context.stack.pop() ?? 0;
    const a = context.stack.pop() ?? 0;
    context.stack.push(rpnComparator(a,b) == 1 ? 1 : 0);
    return context;
};

operators.ge = function(context) {
    const b = context.stack.pop() ?? 0;
    const a = context.stack.pop() ?? 0;
    context.stack.push(rpnComparator(a,b) >= 0 ? 1 : 0);
    return context;
};

operators.lt = function(context) {
    const b = context.stack.pop() ?? 0;
    const a = context.stack.pop() ?? 0;
    context.stack.push(rpnComparator(a,b) == -1 ? 1 : 0);
    return context;
};

operators.le = function(context) {
    const b = context.stack.pop() ?? 0;
    const a = context.stack.pop() ?? 0;
    context.stack.push(rpnComparator(a,b) <= 0 ? 1 : 0);
    return context;
};

We try it out.

Javascript Editor

We now are ready to construct the first conditional operator if.

Javascript

We try it out.

Javascript Editor

We can build a recursive function like factorial.

Javascript Editor

It is better to use the stack and not variables in recursion because of the variable scope. Note that there is no global scope on this page, so when you run just factorial here, you get an error.

Javascript Editor

We can also invent a mod operator.

Javascript Editor

Can we make also the greatest divisor? Stack hhandling is challenging, but gcd is quite similar to mod. Note that you can space and comment your code to make it readable.

Javascript Editor

The current code is now 359 lines ps20240628.js

My Journey to PostScript