我们来写一个 PostScript 解释器

让我们来写一个 PostScript 解释器

我认为最值得信赖的编程语言是那些人类规模的语言：即单个用户可以在一些 readily-available 的计算基底上从零开始合理编写的语言。知道如何制作自己的工具会带来一种令人满足的力量感。

今天，我想带你快速走过实现 PostScript 编程语言中一个有趣子集的过程。我们将忽略或简化该语言的许多特性，并且为了简单起见，我们将省略大部分错误处理，但我们讨论的每个 PostScript 示例都将是一个格式良好的 PostScript 程序，它在我们的玩具子集和像 Ghostscript 这样的标准 PostScript 解释器中具有相同的行为。

PostScript 的要素

PostScript 主要设计用于描述打印文档：它拥有丰富的词汇特性，用于创建和操作光栅和矢量图形。就本文而言，我将狭隘地聚焦于其作为通用编程语言的机制。

PostScript 程序由一系列以空白分隔的标记组成，外加一些特殊字符（% / ( ) < > [ ] { }），它们会立即终止前一个标记并开始一个新标记。% 字符开始行注释。/ 字符可以前缀一个字面名称，我们稍后将更详细地讨论。( ) 和 < > 字符括起 PostScript 字符串，为简单起见，我们将在解释器中省略它们。[、]、{ 和 } 字符分别用于括起 PostScript 数组和过程，但它们是普通的自定界标记。给定一个 PostScript 程序片段：

        % This is a line comment
/double {2 mul} def

3 double
      

标记为：

        ['/double','{','2','mul','}','def','3','double']
      

PostScript 执行模型围绕几个栈展开：主要是一个操作数栈，用于在操作符之间传递参数，以及一个字典栈，用于将名称与值关联起来。

上述程序片段执行如下：

• 名称 /double 以 / 前缀开头，因此它被压入操作数栈。

• 标记 { 收集直到匹配的 } 之前的标记为一个过程，而不执行它们，结果过程 {2 mul} 被压入操作数栈。

• 名称 def 不以 / 前缀开头，因此在字典栈中查找它，从最顶层的字典开始，并搜索更深的字典直到找到匹配。此名称与一个操作符——由语言提供的原语——相关联。def 操作符从操作数栈弹出一个过程（{2 mul}）以及一个名称（/double），并将该名称与过程关联到字典栈中最顶层的字典中。

• 数字 3 被压入操作数栈。

• 名称 double 不以 / 前缀开头，因此在字典栈中查找它。这会检索我们先前与该名称关联的过程。当以这种方式从字典栈中检索过程时，其内容（2 mul）按顺序执行。

• 数字 2 被压入操作数栈。

• 名称 mul 不以 / 前缀开头，因此在字典栈中查找它。mul 操作符从操作数栈弹出两个值——2 和 3——将它们相乘，然后将结果——6——压入操作数栈。

还值得花点时间谈谈 PostScript 数组。[ 操作符将一个称为 mark 的特殊值压入操作数栈，而 ] 操作符将操作数栈中的所有值弹出，直到最顶层的 mark，并从中构建一个数组：

        []             % 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]
      

我们稍后将更详细地讨论 PostScript 编程，但这足以开始构建。

代码与数据

我们的 PostScript 解释器将用一种非常简洁的 JavaScript 风格编写，这种风格受到 Forth 哲学的影响，而 Forth 是 PostScript 有影响力的前身：

• 我们会把程序分解成许多短例程，通常只有一行。

• 我们会优先选择没有副作用的“纯”函数例程，但当全局状态能简化代码时，我们会使用全局状态。

• 每个例程应表达单一想法，并且最多包含一个控制结构。

下面几个例程说明了这种风格：

        last = x=>x[x.length-1]
iota = x=>Array.from(Array(x)).map((_,i)=>i)
mod  = (x,y)=>x-y*Math.floor(x/y)
      

如果你发现自己很难“略读”这种风格的代码，试着慢下来，逐字符仔细阅读每个定义。你可能会发现，边读边在浏览器的 JavaScript 控制台中试验每个定义会很有用。

编写任何解释器的第一步都是确定如何表示数据，这里就是用 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：

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

        push     = x=>o.push(x)
pop      = x=>o.pop()
popn     = x=>{const r=[];while(x-->0)r.unshift

执行预分词的 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

文章标题：让我们写一个 PostScript 解释器

正文： 我们的解释器只提供了标准 PostScript 所附带原始操作符的一个非常小的子集。在我们已有的基础上充实更多操作符，是一些有趣的练手练习：

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

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

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

尝试一些经典的函数式编程练习也很有价值，比如递归计算斐波那契数列：

        /fib {dup 2 ge {1 sub dup 1 sub fib exch fib add} {} ifelse} def

[0 1 10 {fib} for] ==
% [0 1 1 2 3 5 8 13 21 34 55]
      

当然，也有更符合习惯的迭代写法：

        [0 1 9 {2 copy add} repeat] ==
% [0 1 1 2 3 5 8 13 21 34 55]
      

我很喜欢把 PostScript 表达式包在 [] 里的做法，它像是列表推导式的一种更具组合性的替代方案。

下面是一个实用例程，用于制作一个元素顺序相反的数组副本：

        /reverse {[exch dup length 1 sub -1 0 {1 index exch get exch} for pop]} def

[11 22 33] reverse ==
% [33 22 11]
      

在我们手头的这些原始操作符的基础上，你能想到多少种拼接一对数组的方法？

        [11 22 33] [44 55] concat ==
% [11 22 33 44 55]
      

一种方法：

我使用 PostScript 这类串接式编程语言的许多经验来自 Forth，它对大多数操作符使用了略有不同的名称和分解方式。幸运的是，PostScript 相当有可塑性：

        /swap  {exch} def
/drop  {pop} def
/over  {1 index} def
/2dup  {2 copy} def
/2drop {pop pop} def
/rot   {3 -1 roll} def
/-rot  {3 1 roll} def
/@     {load exec} def
/!     {exch def} def
      

PostScript 的 roll 和 index 操作符比常见的 Forth 栈操作词更容易深入栈中取用元素，但这也要求程序员在阅读时，在有限的工作记忆中保持对栈内容的更宏观把握。即便是 rot/-rot，对一些 Forth 老手来说也可能是有争议的“代码异味”。

在 Forth 中，我们可以自由地操作“返回栈”以及操作数栈，通常用 r> 和 >r 这类词把一个栈顶的值转移到另一个栈。Forth 的控制结构常常会在迭代之间把循环索引之类的东西存放在返回栈上，以免它们干扰循环体内的参数流。它也可以方便地临时存放中间结果，以保持操作数栈较浅。PostScript 有一个用于嵌套过程记录的“执行栈”，但它不受程序员的直接控制；因此我们无法使用这类惯用法。

字典栈提供了可嵌套的命名局部变量作用域：

        2 dict begin
 /b def
 /a def
 a a mul
 b b mul
 add sqrt
end
      

甚至可以围绕这个模式构建整洁的抽象：

        /local {1 dict begin 3 1 roll exch def exec end} def

25 /a {a a add} local
      

但由于这种做法产生的是动态作用域而非词法作用域，它对我们 exec 的过程并不透明。如果没有一个辅助栈来“隐藏”中间状态，编写高阶函数可能会出奇地困难。试着在 PostScript 中定义一个等价于 Lisp 式 (cond) 的条件表达式，你就会明白我的意思：

        [{p1} {e1} {p2} {e2} ... {e}] cond
      

PostScript 有一个诱人的 bind 操作符（我们的解释器未实现它），旨在通过在 bind 时急切地把过程中对操作符的引用替换为其值，来帮助避开动态作用域的陷阱。然而，由于 bind 只关心解析操作符，它并不适用于模拟通用的词法作用域；我们需要构建一个更通用的机制来在过程中执行命名替换。

接下来是什么？

我们来写一个 PostScript 解释器

撇开我前面那些语义上的吹毛求疵不谈，我认为 PostScript 相当优雅，也很值得学习。既然现在我们有了一个能排进一两页打印纸篇幅的解释器，就有了一个很适合动手实验的基础。我确信，在我们这些简短的探索过程中，你已经想到许多可以添加的新原语操作符——sin、cos、pi，也许还有更多用来操作数据的工具，比如 type、cvx 和 cvlit，或者一套更丰富的输入输出例程？

你可能会发现，增加更健壮的错误处理值得多占一些体积。例如，你可以让 load 容忍未定义的名字并返回一个占位符：

        load = x=>{const v=litval(x);return (d.findLast(s=>s.has(v))||new Map()).get(v)||null}
      

你也可以实现更完整的数据类型和语法范围，比如（字符串）、非整数，以及用于字典“字面量”的 <</a 11 /b 22>> 语法。

带着你初具雏形的新的人类尺度编程环境，朝任何你喜欢的方向发展吧。享受这种力量感。

延伸阅读

• 《PostScript 语言参考》第三版

• 串接语言 Wiki

• 如何用 Python 编写 Lisp 解释器