Let’s Write a PostScript Interpreter I think the most trustworthy programming languages are those which are human-scale: languages which a single user could reasonably write from scratch on some readily-available computational substrate. Knowing how to make your own tools provides a satisfying https://en.wikipedia.org/wiki/The_Feeling_of_Power. Today I’d like to take you on a brisk journey through the process of implementing an interesting subset of the https://en.wikipedia.org/wiki/PostScript programming language. We will ignore or simplify many features of the language, and we will elide most error-handling for simplicity, but every PostScript example we discuss will be a well-formed PostScript program which has the same behavior in our toy subset and a standard PostScript interpreter like https://en.wikipedia.org/wiki/Ghostscript.
The Elements of PostScript PostScript is primarily designed for describing printed documents: it has a rich vocabulary of features for creating and manipulating raster and vector graphics. For the purposes of this article I will narrowly focus on its mechanics as a general-purpose programming language. PostScript programs are composed of a series of whitespace-delimited tokens, plus a few special characters (% / ( ) < > [ ] { }) which immediately terminate the preceding token and begin a new one. The % character begins a line-comment.
The / character can prefix a literal name, which we’ll discuss in more detail momentarily. The ( ) and < > characters enclose PostScript strings, which we will omit from our interpreter for simplicity. The [, ], { and } characters are used to enclose PostScript arrays and procedures, respectively, but are ordinary self-delimiting tokens. Given a PostScript program fragment: % This is a line comment /double {2 mul} def 3 double The tokens are: ['/double','{','2','mul','}','def','3','double'] The PostScript execution model centers around several stacks: chiefly, an operand stack which is used to pass arguments between operators and a dictionary stack which is used to associate names with values.
The above program fragment is executed as follows: The name /double begins with a / prefix, so it is pushed onto the operand stack. The token { collects the tokens up to the matching } into a procedure without executing them, and the resulting procedure {2 mul} is pushed onto the operand stack. The name def does not begin with a / prefix, so it is looked up in the dictionary stack, starting with the topmost dictionary and searching deeper dictionaries until a match is found. This name is associated with an operator- a primitive provided by the language.
The def operator pops a procedure from the operand stack ({2 mul}) as well as a name (/double) and associates the name with the procedure in the topmost dictionary on the dictionary stack. The number 3 is pushed onto the operand stack. The name double does not begin with a / prefix, so it is looked up in the dictionary stack. This retrieves the procedure we previously associated with the name.
When a procedure is retrieved from the dictionary stack in this manner, its contents (2 mul) are executed in sequence. The number 2 is pushed onto the operand stack. The name mul does not begin with a / prefix, so it is looked up in the dictionary stack. The mul operator pops two values from the operand stack- 2 and 3- multiplies them, and then pushes the result- 6- onto the operand stack.
It’s also worth taking a moment to touch on PostScript arrays. The [ operator pushes a special value called mark onto the operand stack, and the ] operator pops all of the values of the operand stack down to the topmost mark and builds an array from them: [] % an empty array [1 2] % an array of two values [[1 2][3 4]] % an array of two values, each of which is an array [2 3 add] % equivalent to [5] We’ll discuss programming in PostScript in more detail later, but this is enough to get building. Code and Data Our PostScript interpreter will be written in a very concise style of JavaScript that is influenced by the philosophy of https://en.wikipedia.org/wiki/Forth_(programming_language), an influential ancestor of PostScript: We will factor our program apart into many short routines, generally single lines. We will prefer routines which are “pure” functions without side effects, but we will use global state when it simplifies our code.
Each routine should express a single idea, and contain no more than one control structure. Here are a few routines which illustrate this style: last = x=>x[x.length-1] iota = x=>Array.from(Array(x)).map((_,i)=>i) mod = (x,y)=>x-y*Math.floor(x/y) If you’re finding yourself struggling to “skim” code in this style, try to slow down and read each definition carefully, character-by-character. You may also find it useful to experiment with each definition in your browser’s JavaScript console as you go along. The first step in writing any interpreter is determining how we’ll represent data, in this case describing PostScript datatypes in terms of JavaScript datatypes: PostScript Example JavaScript Example number 37 Number 37 boolean true Boolean true name a String "a" literal /a String "/a" dictionary <</a 11>> Map new Map([['/a',11]]) array [11 22] Array [11,22] procedure {1 add} Object-wrapped Array {t:'proc',v:[1,'add']} operator add Function (x,y)=>x+y mark mark Singleton Object MARK Using primitive JavaScript values to represent most of these types will be particularly helpful for writing the definitions of all the operators.
Here are a set of definitions for constructing, accessing, and identifying various PostScript values: MARK = {} proc = x=>({t:'proc',v:x}) procval = x=>x.v isproc = x=>x&&x.t=='proc' isarray = x=>Array.isArray(x) isfunc = x=>'function'==typeof x isname = x=>'string'==typeof x&&`/`!=x[0] litval = x=>x.slice('/'==x[0]) Next, we need to translate PostScript syntax into the above data representations. We can use a JavaScript RegExp to split an input program into a sequence of tokens- line-comments (which can be discarded), special delimiters ([]{}), names, and numbers (which can be coerced into JavaScript numbers). While it is possible to implement { and } as PostScript operators, it is simpler for our purposes to cluster the tokens of procedures together as we parse the program: parse = x=>{ const t=x.trim().match(/(%[^\n]*\n)|(\[|\]|\{|\})|(\/?[^\[\]\{\}\/% \n]+)|(-?\d+)/gm).filter(x=>x[0]!='%') const next=()=>t.shift() const peek=()=>t[0] const isnum=x=>+x==+x const rec=()=>peek()=='{'?(next(),seq()): isnum(peek())?+next(): next() const seq=()=>{const r=[];while(peek()&&peek()!='}')r.push(rec());return next(),proc(r)} return seq() } Given a PostScript program like [10 20 30] {2 mul} forall The parse(x) routine will break it down into {t:'proc', v:['[', 10, 20, 30, ']', {t:'proc', v:[2, 'mul']}, 'forall']} The Interpreter The PostScript operand stack and dictionary stack can be represented as simple JavaScript global arrays- o and d, respectively: o=[] d=[] Some simple routines for manipulating these stacks: push = x=>o.push(x) pop = x=>o.pop() popn = x=>{const r=[];while(x-->0)r.unshift(pop());return r} popmark = ()=>{const r=[];while(o.length&&MARK!=last(o))r.unshift(pop());pop();return r} load = x=>{const v=litval(x);return d.findLast(s=>s.has(v)).get(v)} Executing pre-tokenized PostScript programs is very simple: we execute each token in sequence. Names are looked up in the dictionary stack and the corresponding operator or procedure is called; anything else is pushed onto the operand stack.
Since operators are JavaScript functions, when we execute them we’ll pop a number of values from the operand stack corresponding to their argument list count and apply() them to the function. If the function returns something other than undefined, we’ll push the result onto the stack: execfunc = x=>{const v=x.apply(null,popn(x.length));if(v!=undefined)push(v)} execproc = x=>{isproc(x)?procval(x).forEach(exec): exec(x)} exec = x=>{isfunc(x)?execfunc(x): isname(x)?execproc(load(x)): push(x)} The large bulk of the machinery of our interpreter lives in the primitive operator definitions, but each is individually fairly simple, with the possible exception of the for operator, which needs a few helper routines for generating stepped ranges. Many of these operators are pure JavaScript functions which do not directly access or modify either stack and can be tested and understood in isolation. countup = (x,y,z)=>{const r=[];while(x<=z)r.push(x),x+=y;return r} countdn = (x,y,z)=>{const r=[];while(x>=z)r.push(x),x+=y;return r} range = (x,y,z)=>x<z&&y>0?countup(x,y,z): y<0?countdn(x,y,z): [] prims={ true: true, false: false, exec: execproc, for: (x,y,z,w)=>range(x,y,z).forEach(v=>(push(v),execproc(w))), forall: (x,y)=>x.forEach(v=>(push(v),execproc(y))), repeat: (x,y)=>iota(x).forEach(v=>execproc(y)), ifelse: (x,y,z)=>execproc(x?y:z), load: load, def: (x,y)=>{last(d).set(litval(x),y)}, begin: x=>{d.push(x)}, end: ()=>{d.pop()}, dup: x=>(push(x),x), exch: (x,y)=>(push(y),x), pop: x=>{}, index: x=>o[o.length-(1+x)], copy: x=>o.slice(-x).forEach(push), roll: (x,y)=>popn(x).forEach((_,i,a)=>push(a[mod(i-y,x)])), floor: x=>Math.floor(x), sqrt: x=>Math.sqrt(x), not: x=>!x, add: (x,y)=>x+y, sub: (x,y)=>x-y, mul: (x,y)=>x*y, div: (x,y)=>x/y, mod: mod, eq: (x,y)=>x==y, ne: (x,y)=>x!=y, gt: (x,y)=>x>y, ge: (x,y)=>x>=y, lt: (x,y)=>x<y, le: (x,y)=>x<=y, '[': ()=>MARK, ']': popmark, length: x=>x.length, get: (x,y)=>x[y], dict: x=>new Map(), } To access the primitives from within exec() and execproc() we need to install them into the dictionary stack. Here’s a procedure to initialize both stacks: init = ()=>{o=[],d=[new Map(Object.entries(prims))]} We can now execute programs and observe their effects on the stacks: init() execproc(parse('2 3 add')) console.log(pop()) // 5 Making it Interactive For interactive use, we can wire everything up into a https://en.wikipedia.org/wiki/Read–eval–print_loop (REPL).
We’ll need at least some rudimentary output capabilities, so for starters we can install an extra primitive == which pops a value from the stack and displays it: format = x=>isarray(x)?`[${x.map(format).join(' ')}]`: isproc(x)?`{${format(procval(x))}}`: `${x}` prims['==']=x=>{console.log(format(x))} init() If we’re using https://nodejs.org we have to write our REPL in an event-driven style: // usage: node ps.js rl=require('readline').createInterface({input:process.stdin,output:process.stdout,prompt:' '}) rl.prompt() rl.on('line',x=>(execproc(parse(x)),rl.prompt())) rl.on('close',_=>(console.log(''),process.exit(0))) If we’re using https://bellard.org/quickjs/ we can write a more straightforward infinite loop instead: // usage: qjs --std ps.js while(1){std.out.printf(' '),execproc(parse(std.in.getline()))} Either way, we now have a fancy PostScript-style desk calculator: 2 3 add == 5 [[11 22 33] {10 mul} forall] == [110 220 330] postscript-figures/ps.js, for refe
Texto de beyondloom.com tal como lo publicó, leído de su página y mostrado aquí con el formato de El Autómata. El original, en beyondloom.com · Volver a la noticia de El Autómata