用JavaScript实现PostScript解释器

用原始 JavaScript 值来表示这些类型中的大多数，对编写所有运算符的定义特别有帮助。下面是一组用于构造、访问和识别各种 PostScript 值的定义：

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])

接下来，我们需要把 PostScript 语法翻译成上述数据表示。可以用 JavaScript 的 RegExp 把输入程序切分成一串 token——行注释（可以丢弃）、特殊分隔符（[]{}）、名字和数字（可以强制转换成 JavaScript 数字）。虽然把 { 和 } 实现成 PostScript 运算符也是可行的，但对我们来说，在解析程序时把过程（procedure）的 token 聚在一起更简单：

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() }

给定像这样的 PostScript 程序

[10 20 30] {2 mul} forall

parse(x) 例程会把它拆解成

{t:'proc', v:['[', 10, 20, 30, ']', {t:'proc', v:[2, 'mul']}, 'forall']}

解释器

PostScript 的操作数栈和字典栈可以分别用简单的 JavaScript 全局数组 o 和 d 来表示：

o=[] d=[]

一些用于操作这些栈的简单例程：

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)}

执行预先 token 化的 PostScript 程序非常简单：我们依次执行每个 token。名字会在字典栈中查找，并调用对应的运算符或过程；其他任何东西都压入操作数栈。由于运算符是 JavaScript 函数，执行它们时，我们会根据其参数列表长度从操作数栈弹出相应数量的值，并对该函数调用 apply()。如果函数返回的不是 undefined，我们就把结果压入栈：

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)}

我们解释器的大部分机制都存在于原始运算符定义中，但每个定义单独来看都相当简单，可能的例外是 for 运算符，它需要几个辅助例程来生成带步长的范围。这些运算符中有许多是纯 JavaScript 函数，既不直接访问也不修改任何一个栈，可以孤立地测试和理解。

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(),

要在 exec() 和 execproc() 中访问这些原始运算符，我们需要把它们安装到字典栈中。下面是一个初始化两个栈的过程：

init = ()=>{o=[],d=[new Map(Object.entries(prims))]}

现在我们可以执行程序并观察它们对栈的影响：

init() execproc(parse('2 3 add')) console.log(pop()) // 5

让它可交互

对于交互式使用，我们可以把一切接入一个 Read-Eval-Print-Loop（REPL）。我们至少需要一些基本的输出能力，所以作为起步，可以安装一个额外的原始运算符 ==，它从栈中弹出一个值并显示出来：

format = x=>isarray(x)?[${x.map(format).join(' ')}]: isproc(x)?{${format(procval(x))}}: ${x} prims['==']=x=>{console.log(format(x))} init()

如果使用 Node.js，我们得用事件驱动风格来写 REPL：

// 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)))

如果使用 QuickJS，我们可以改写成更直白的无限循环：

// usage: qjs --std ps.js while(1){std.out.printf(' '),execproc(parse(std.in.getline()))}

无论哪种方式，我们现在都有了一个花哨的 PostScript 风格桌面计算器：

2 3 add == 5 [[11 22 33] {10 mul} forall] == [110 220 330]

为方便参考，这里是完整一体的解释器。

我们的解释器只提供了标准 PostScript 所带原始运算符的一个很小的子集。用我们已有的东西来充实更多运算符，有一些有趣的指法练习：

/if {{} ifelse} def /neg {-1 mul} def

试试实现 abs——计算一个数的绝对值：

那 min 呢——找出栈上两个值中的最小值？

（原文较长，此处译出前 6000 字，完整内容请点「打开原文」。）