作者 | Peter Norvig

译者 | Tianyu

修改 | Freesia

来历 | Python大本营(ID: pythonnews)

这篇文章有两个意图:一是展现怎么完成一个核算机言语的解说器,二是演示怎么运用 Python 3 结构 Lisp 的一种方言 Schema,作者把自己的这个言语解说器称作 Lispy。几年前,作者曾展现过怎么用 Java 和 Common Lisp 写 Schema 解说器。而本次的意图很朴实,作者会尽或许短小精悍为咱们进行介绍。

了解这些有多重要呢?正如 Steve Yegge 所说的,“假如你不知道编译器是怎么作业的,那么你也不会知道核算机是怎么作业的”。

Schema 程序的语法和语义

言语的语法是指组成正确的语句或表达式的次序;语义指那些表达式或语句的内涵意义。例如,在数学表达式言语中(以及许多编程言语中),一加二的语法是 “1 + 2”,而语义是指对两个数字履行相加操作,得到的成果为 3 。当咱们核算一个数值时,也能够说咱们在评价一种表达办法;咱们能够说 “1+2” 估值为 3,并写成 “1 + 2” ⇒ 3.

Schema 的语法不同于其他大多数编程言语。考虑如下状况:

Java 的语法规范十分冗杂(关键词、中缀运算符、三种括号、运算符优先级、点语法、引号、逗号、分号),但 Schema 的语法要简略得多:

  • Schema 程序仅由表达式组成。没有表达式和语句之分。

  • 数字(比方:1)和符号(比方:A)都能够称为原子表达式;它们无法再细分了。这和 Java 中的 counterpart 相似,但 Schema 不同,一些运算符号,如 + 和 > 也是标识符,和 A 及 fn 的位置是相等的。

  • 还有列表表达式:一个 "(" ,后边接零或多个表达式,后边再接一个 ")"。列表的第一个元素决议了其意义是什么:

    • 以关键词作为开始的列表,如 (if ...),是一种特别办法,意义取决于关键词是什么。

    • 以非关键词开始的列表,如 (fn ...),是函数的调用。

Schema 程序仅由表达式组成。没有表达式和语句之分。

数字(比方:1)和符号(比方:A)都能够称为原子表达式;它们无法再细分了。这和 Java 中的 counterpart 相似,但 Schema 不同,一些运算符号,如 + 和 > 也是标识符,和 A 及 fn 的位置是相等的。

还有列表表达式:一个 "(" ,后边接零或多个表达式,后边再接一个 ")"。列表的第一个元素决议了其意义是什么:

  • 以关键词作为开始的列表,如 (if ...),是一种特别办法,意义取决于关键词是什么。

  • 以非关键词开始的列表,如 (fn ...),是函数的调用。

以关键词作为开始的列表,如 (if ...),是一种特别办法,意义取决于关键词是什么。

以非关键词开始的列表,如 (fn ...),是函数的调用。

Schema 的妙处在于整个言语系统仅需 5 个关键词和 8 种语法办法。比照之下,Python 有 33 个关键词和 110 种语法办法,Java 有 50 个关键词和 133 种语法办法。那些括号或许看起来有些吓人,但 Schema 的语法具有着简略性与一致性。(有人恶作剧说 Lisp 便是“很多把人搞疯的括号”;而我以为 Lisp 标志着语法的朴实性。)

在本文中,咱们会介绍 Schema 言语及其解说器的一切特色,但中心要经过两个进程,先界说一个简略的言语,再界说 Schema 言语的悉数内容。

言语1:Lispy Calculator

Lispy Calculator 是 Schema 的一部分,仅运用了五种语法办法。因其依据 Lispy Calculator,只需你娴熟运用前缀表明法,就能够做任何典型核算机能够做的运算。你能够做两件典型核算机言语所不能做的两件事:"if" 表达式和界说新变量。下面是一个示例程序,依据公式 π r2,核算半径为10的圆形面积:

下面是一张有关悉数表达式的表格:

Expression(表达式) Syntax(语法) Semantics and Example(语义和比如)
variable reference symbol 一个标识符被解说为变量名;它的值是变量的值。比如:r ⇒ 10 (假定 r 已被界说为10)
constant literal number 核算成果为数字自身。比如:12 ⇒ 12 or -3.45e+6 ⇒ -3.45e+6
conditional (if test conseq alt) 履行 test;假如成果为 true,核算回来 conseq;不然回来 alt。比如:(if (> 10 20) (+ 1 1) (+ 3 3)) ⇒ 6
definition (define symbol exp) 界说一个新变量,并核算表达式 exp 赋值给它。比如:(define r 10)
procedure call (proc arg...) 假如表达式不是这些标识符 if, define 或 quote,那它便是一个进程。履行表达式及悉数参数,那么该进程就会被调用,而参数值列表也被调用。比如:(sqrt (* 2 8)) ⇒ 4.0

在该表的语法一栏,标识符有必要为符号,数字有必要为整数或小数,而其它斜体字能够为任何表达式,arg... 则表明零或多个 arg 的重复。

言语解说器到底是做什么的?

言语解说器包含两个部分:

Parsing:parsing 组件取得字符串办法的输入,并依据言语的语法规矩进行验证,然后将程序翻译成内部的表明办法。在一个简略的解说器中,内部的表明办法是一个树形结构(一般被称为笼统语法树),反响了程序语句和表达式的嵌套结构。在被称为编译器的言语翻译器中,常常有一系列内部的表明办法,以笼统语法树开始,然后紧接着一系列指令,能够直接被核算机履行。

Execution:内部的表明办法是依据言语的语义规矩进行处理的,因而才干履行核算。Lispy 的 execution 函数叫作 eval(留意这和 Python 的内置函数同名)。

下面是解说器作业进程的图片:

这儿举一个简略的小比如,看看 parse 和 eval 能做些什么:

>>> parse(program)['begin', ['define', 'r', 10], ['*', 'pi', ['*', 'r', 'r']]]

>>> eval(parse(program))314.1592653589793

类型界说

咱们来清晰一下 Scheme 目标的表明办法:

Parsing:parse, tokenize, read_from_tokens

传统上来看,parsing 一般分红两部分:词法剖析(lexical analysis),也便是将输入字符串分红一系列 token,以及语义剖析(syntactic analysis),也便是将 tokens 拼装成后向笼统语法树。Lispy 的 tokens 是括号、标识符和数字。有许多用于词法剖析的东西(如 Mike Lesk 和 Eric Schmidt 的 lex),但现在咱们挑选运用一个十分简略的东西:Python 的 str.split 函数。tokenize 函数以字符串作为输入,在每个括号两头加空格,然后调用 str.split 获取 tokens 列表:

下面咱们在程序示例中运用 tokenize:

函数 parse 以字符串的表达办法作为程序输入,调用 tokenize 获取 tokens 列表,然后调用 read_from_tokens 来拼装笼统语法树。read_from_tokens 会重视第一个 token,假如第一个是 ')',那么是一个语法过错。假如第一个是 '(',那么咱们就开端树立子表达式的列表,直到咱们遇到匹配的 ')'。任何没有括号的 token 一定是标识符或数字。咱们能够让 Python 对此做判别:关于每个不含括号的 token,首要测验将其解说为整数,然后是小数,假如哪个都不契合,那么它一定是个标识符。下面来看一下 parse 实例:

defread_from_tokens(tokens: list)-> Exp:"Read an expression from a sequence of tokens."iflen(tokens) == 0:raiseSyntaxError('unexpected EOF')token = tokens.pop(0)iftoken == '(':L = []whiletokens[0] != ')':L.append(read_from_tokens(tokens))tokens.pop(0) # pop off ')'returnLeliftoken == ')':raiseSyntaxError('unexpected )')else:returnatom(token)

defatom(token: str)-> Atom:"Numbers become numbers; every other token is a symbol."try: returnint(token)exceptValueError:try: returnfloat(token)exceptValueError:returnSymbol(token)

parse 的运转成果如下:

>>> parse(program)['begin', ['define', 'r', 10], ['*', 'pi', ['*', 'r', 'r']]]

咱们立刻就能够界说 eval 了,但在那之前,咱们还需求再看一个概念。

环境

环境是指变量名与值之间的映射。eval 默许运用大局环境,包含一组规范函数的称号(如 sqrt 和 max,以及操作符 *)。环境也能够由用户进行变量自界说:

defstandard_env-> Env:"An environment with some Scheme standard procedures."env = Envenv.update(vars(math)) # sin, cos, sqrt, pi, ...env.update({'+':op.add, '-':op.sub, '*':op.mul, '/':op.truediv, '>':op.gt, '<':op.lt, '>=':op.ge, '<=':op.le, '=':op.eq, 'abs': abs,'append': op.add, 'apply': lambdaproc, args: proc(*args),'begin': lambda*x: x[-1],'car': lambdax: x[0],'cdr': lambdax: x[1:], 'cons': lambdax,y: [x] + y,'eq?': op.is_, 'expt': pow,'equal?': op.eq, 'length': len, 'list': lambda*x: List(x), 'list?': lambdax: isinstance(x, List), 'map': map,'max': max,'min': min,'not': op.not_,'null?': lambdax: x == [], 'number?': lambdax: isinstance(x, Number), 'print': print,'procedure?': callable,'round': round,'symbol?': lambdax: isinstance(x, Symbol),})returnenv

global_env = standard_env

Evaluation:eval

咱们现已做好完成 eval 的预备了。作为初学者,来回忆一下之前的 Lispy Calculator 表:

Expression(表达式) Syntax(语法) Semantics and Example(语义和比如)
variable reference symbol 一个标识符被解说为变量名;它的值是变量的值。比如:r ⇒ 10 (假定 r 已被界说为10)
constant literal number 核算成果为数字自身。比如:12 ⇒ 12 or -3.45e+6 ⇒ -3.45e+6
conditional (if test conseq alt) 履行 test;假如成果为 true,核算回来 conseq;不然回来 alt。比如:(if (> 10 20) (+ 1 1) (+ 3 3)) ⇒ 6
definition (define symbol exp) 界说一个新变量,并核算表达式 exp 赋值给它。比如:(define r 10)
procedure call (proc arg...) 假如表达式不是这些标识符 if, define 或 quote,那它便是一个进程。履行表达式及悉数参数,那么该进程就会被调用,而参数值列表也被调用。比如:(sqrt (* 2 8)) ⇒ 4.0

下面是完成 eval 的代码,彻底遵从上面的表格:

这样就完成了!你能够运转看看成果:

Interaction:A REPL

一向输入 eval 当然很单调。Lisp 的一个巨大之处就在于交互式 read-eval-print 循环:为编程者供给了输入表达式,并当即读取,核算,然后输出的途径,而非冗长的构建/编译/运转进程。那么,咱们来界说一下 repl 函数,函数 schemestr 回来了一个代表 Schema 目标的字符串:

defschemestr(exp):"Convert a Python object back into a Scheme-readable string."ifisinstance(exp, List):return'('+ ' '.join(map(schemestr, exp)) + ')'else:returnstr(exp)

下面是 repl 的运转成果:

言语2:Full Lispy

现在咱们来拓宽一下,下面的表格展现了一个愈加完好的 Schema 子集:

Expression(表达式) Syntax(语法) Semantics and Example(语义和比如)
quotation (quote exp) 回来表达式 exp 的值,但不进行核算。比如:(quote (+ 1 2)) ⇒ (+ 1 2)
assignment (set! symbol exp) 履行 exp 并把值赋给 symbol,symbol 有必要被预先界说好。比如:(set! r2 (* r r))
procedure (lambda (symbol...)exp) 发明一个带参数 (symbol...) 的进程,exp 为其主体。比如:(lambda (r) (* pi (* r r)))

lambda 这种特别办法能够进行 procedure(进程)的创立。咱们期望 procedure 能这样运转:

此处包含两个进程。第一步,lambda 表达式用来创立 procedure,能够相关大局变量 pi 和 *,引进独自的参数 r。该 procedure 的作用是界说新变量 circle-area,并为其赋值。第二步,咱们刚刚界说的 procedure 包含 circle-area 的值,所以它被引证作值为10的参数。咱们想让 r 的取值为10,但它不会在大局环境下为 r 赋值为10。假如咱们将 r 用作其他意图呢?咱们无法经过调用 circle-area 来改动它的值。但咱们或许能够给名为 r 的部分变量赋值10,而无需忧虑影响到其他同名的大局变量。调用 procedure 的进程引进了新的部分变量,将其与函数的参数列表中的标识符逐个绑定,对应所调用函数的参数列表的值。

将 Env 重界说为 Class

为了便利操作部分变量,咱们将 Env 重界说为 dict 的子类。当咱们核算 (circle-area (+ 5 5)) 时,咱们会先获取 procedure 的主体 (* pi (* r r)),然后在 r 作为独自部分变量的环境下进行核算,但一同也存在大局环境作为“外部”环境;这样咱们就得到了 * 和 pi 的值。换句话说,咱们需求这样一个环境,将部分(蓝色框标示的)环境嵌在外部(赤色框标示的)环境内:

当咱们在这样一个嵌套环境中检查变量时,咱们首要看到的是最内层,假如没有找到变量名,再转移到外面一层。进程和环境是耦合的,接下来试着来一同界说它们:

classProcedure(object):"A user-defined Scheme procedure."def__init__(self, parms, body, env):self.parms, self.body, self.env = parms, body, envdef__call__(self, *args): returneval(self.body, Env(self.parms, args, self.env))

global_env = standard_env

咱们看到每个 procedure 都由三部分组成:参数名列表、主体表达式,以及环境。假如在最上层对 procedure 进行了界说,那么这是大局环境,但 procedure 也可相关到部分变量的环境,只需对其进行了预先界说。

环境是 dict 的子类,所以它具有悉数 dict 所具有的办法。别的还有两种办法:结构器 __init__ 结构了新环境,引进参数名列表和对应的参数值列表,并创立了内部包含 {variable: value} 的新环境,一同也可相关外部环境。办法 find 可用来为变量寻觅适宜的环境:内部环境或外部环境。

来看看怎么将这些东西整合在一同,下面是对 eval 的新界说。留意用于引证变量的语句变了:现在咱们有必要调用 env.find(x) 来查找变量 x 在哪一层;然后从该层取出 x 的值。(用于 define 的语句不变,由于 define 永久将新变量添加到最内层的环境。)此处有两个新的子句:set! 用来查找变量地点的环境层,并为其赋新值。lambda 用来依据给定的参数列表、主体和环境,来创立新的 procedure 目标。

为了搞清楚进程和环境是怎么协同作业的,试想这样一个程序,为核算 (account1 -20.00),咱们创立这个环境:

每个矩形框代表一个环境,框的色彩与环境中所界说的变量的色彩相对应。在程序的后两行,咱们界说了 account1,并调用了 (account1 -20.00);这表明创立了一个期初余额为100刀的银行账户,被取出了20刀。在核算 (account1 -20.00) 的进程中,咱们对 eval 表达式做了高亮处理。该表达式含三个变量,amt 在最内层(绿色)里。但 balance 不在这一层,咱们需求看绿色环境外面的 env,即蓝色层。最终,变量 + 不在这三层中,咱们需求找更外面的层,来到大局(赤色)环境。这个先看内环境再看外环境的进程叫作 lexical scoping。

下面来看看咱们能够做哪些事。

现在咱们具有了具有进程、变量、条件、次序履行的言语。假如你了解其他言语,你或许会想到 while 或 for 循环,但 Schema 并不包含这些。有关 Schema 的陈述表明,Schema 仅包含几条规矩,用来组成表达式,并不约束它们的组成办法,这样就足以构成一门有用且高效的编程言语了。在 Schema 中,你能够经过界说递归函数进行循环运算。

Lispy 评价

咱们从下面几个视点来评价 Lispy:

  • 轻量:Lispy 十分小:去掉注释和空格,共117行;源码巨细为4K。我用 Java 写的 Schema 最小版别有1664行,源码巨细为57K。Jscheme 开始名为 SILK (Scheme in Fifty Kilobytes),但我仅经过核算字节码来确保不超限,而非经过改动源码。Lispy 在这方面做得好多了;我以为它契合 Alan Kay 在1972年提出的,你能够经过一页代码来发明世界上最棒的言语。

轻量:Lispy 十分小:去掉注释和空格,共117行;源码巨细为4K。我用 Java 写的 Schema 最小版别有1664行,源码巨细为57K。Jscheme 开始名为 SILK (Scheme in Fifty Kilobytes),但我仅经过核算字节码来确保不超限,而非经过改动源码。Lispy 在这方面做得好多了;我以为它契合 Alan Kay 在1972年提出的,你能够经过一页代码来发明世界上最棒的言语。

  • 快速:Lispy 核算 (fact 100) 用时0.003秒。这对我来说,速度满足快了。

  • 完好:和规范版 Schema 比较,Lispy 不是很完好。首要包含以下几个缺点:

    • 语法:短少注释、quote/quasiquote 声明、# literals、派生表达式类型(如源自 if 的 cond,源自 lambda 的 let)和点表明法列表。

    • 语义:短少 call/cc 和 tail recursion。

    • 数据类型:短少字符串、字符、布尔、向量等。

    • 进程:短少100个原始 procedure。

    • 过错康复:Lispy 无法检测和陈述过错,也无法对其进行康复。Lispy 需求编程者操作无失误。

  • 功能:这就要由读者来判别了。在我看来,它能够到达我的意图,即充任 Lisp 的解说器。

快速:Lispy 核算 (fact 100) 用时0.003秒。这对我来说,速度满足快了。

完好:和规范版 Schema 比较,Lispy 不是很完好。首要包含以下几个缺点:

  • 语法:短少注释、quote/quasiquote 声明、# literals、派生表达式类型(如源自 if 的 cond,源自 lambda 的 let)和点表明法列表。

  • 语义:短少 call/cc 和 tail recursion。

  • 数据类型:短少字符串、字符、布尔、向量等。

  • 进程:短少100个原始 procedure。

  • 过错康复:Lispy 无法检测和陈述过错,也无法对其进行康复。Lispy 需求编程者操作无失误。

语法:短少注释、quote/quasiquote 声明、# literals、派生表达式类型(如源自 if 的 cond,源自 lambda 的 let)和点表明法列表。

语义:短少 call/cc 和 tail recursion。

数据类型:短少字符串、字符、布尔、向量等。

进程:短少100个原始 procedure。

过错康复:Lispy 无法检测和陈述过错,也无法对其进行康复。Lispy 需求编程者操作无失误。

功能:这就要由读者来判别了。在我看来,它能够到达我的意图,即充任 Lisp 的解说器。

实在的故事

追溯这个主意的来历有助于了解解说器的作业原理,下面给咱们共享一个实在的故事。

让咱们将时刻推回到1984年,其时作者正在写博士论文。那时还没有 LateX,也没有 Microsoft Word,作者用的是 troff。不幸的是,troff 没有向前引证符号标签:作者想写出 "As we will see on page @theorem-x",然后在适宜的当地写相似 "@(set theorem-x n%)" 的东西。而研究生同伴 Tony DeRose 也有相同的需求,所以他们一同勾勒出了一个简略的 Lisp 程序,可用作预处理器。但是,他们其时造出的 Lisp 尽管长于读取 Lisp 表达式,但读取非 Lisp 表达式时,慢得令人发指。

所以,作者和 Tony 各奔前程了。Tony 以为最难的部分是表达式的解说器;需求的是 Lisp,他知道怎么编写 C 程序来处理非 Lisp 字符,并将其链接到 Lisp 程序。但作者不知道怎么将其连在一同,但作者以为,为这个言语写一个解说器更简单,所以用 C 写了个解说器。风趣的是,Tony 用 C 写了个 Lisp 程序,由于他是个 C 程序员。而我写了个 C 程序,由于我是个 Lisp 程序员。

最终,他们都把作业搞定了。

原文链接:

https://norvig.com/lispy.html

(*本文为 AI科技大本营转载文章,转载请联络微信 1092722531)

推荐阅读