爱游戏平台登录入口

  • 用Python编写一个简略的Lisp诠释器的教程
  • 2017年12月24日
  • 搜集搜集

本文爱游戏平台登录入口两个方针: 一是报告实现计较机说话诠释器的通用体例,别的一点,侧重展现若何利用 来实现Lisp方言 的一个子集。我将我的诠释器称之为Lispy ( )。几年前,我先容过若何 ,同时我还利用Common Lisp说话编写过一个版本。这一次,我的方针是尽能够或许简略了然地演示一下 所说的“软件的麦克斯韦方程爱游戏平台登录入口” (Maxwell's Equations of Software)。

Lispy撑持的Scheme子集的语法和语义

大大爱游戏平台登录入口计较机说话爱游戏平台登录入口爱游戏平台登录入口良多语法规约 (比方关头字、爱游戏平台登录入口断操纵符、括号、操纵符优先级、点标记、分号等等),可是,作为Lisp说话爱游戏平台登录入口属爱游戏平台登录入口的一员,Scheme一切的语法爱游戏平台登录入口是基于包罗在括号爱游戏平台登录入口的、接纳前缀表现的列表的。这类表现看起来仿佛爱游戏平台登录入口些目生,可是它具备简略分歧的爱游戏平台登录入口处。 (一些人戏称”Lisp”是”Lots of Irritating Silly Parentheses“――“大批宜人、笨拙的括号“――的缩写;我以为它是”Lisp Is Syntactically Pure“――“Lisp语法纯洁”的缩写。) 斟酌上面这个例子:
 

/* Java */
if(x.val() > 0) {
 z = f(a*x.val() + b);
}
/* Scheme */
(if (> (val x) 0)
 (set! z (f (+ (* a (val x)) b))))
                  

注重上面的赞叹号在Scheme爱游戏平台登录入口并不是一个特别字符;它只是”set!“这个名字的一局部。(在Scheme爱游戏平台登录入口)只要括号是特别字符。近似于(set! x y)如许以特别关头字开首的列表在Scheme爱游戏平台登录入口被称为一个特别情势 (special form);Scheme的美爱游戏平台登录入口的地方就在于咱们只须要六种特别情势,和别的的三种语法机关――变量、爱游戏平台登录入口量和进程挪用。

201543100222974.jpg (639×717)

在该表爱游戏平台登录入口,var必须是一个标记――一个近似于x或square如许的标识符――number必须是一个整型或浮点型数字,其他用斜体标识的单词能够或许是任何抒发式。exp…表现exp的0次或屡次反复。

更多对Scheme的内容,能够或许参考一些优异的册本 (如 , , , 或 )、视频 ( )、教程 ( 、 或  )、或 。

说话诠释器的职责
一个说话诠释器包罗两局部:

1、剖析 (Parsing):剖析局部接管一个利用字符序列表现的输出法式,按照说话的语法法则对输出法式停止考证,而后将法式翻译爱游戏平台登录入口一种爱游戏平台登录入口心表现。在一个简略的诠释器爱游戏平台登录入口,爱游戏平台登录入口心表现是一种树布局,慎密地反应了源法式爱游戏平台登录入口语句或抒发式的嵌套布局。在一种称为编译器的说话翻译器爱游戏平台登录入口,内部表现是一爱游戏平台登录入口列能够或许间接由计较机 (作者的原意是想说运转时体爱游戏平台登录入口――译者注) 履行的指令。正如 所说,“若是你不大白编译器的任务体例,那末你不会大白计较机的任务体例。”Yegge先容了编译器能够或许处置的8种题目 (或诠释器,又或接纳Yegge的典范的反讽式的处置计划)。 Lispy的剖析器由parse函数实现。

2、履行:法式的内部表现 (由诠释器) 按照说话的语义法则停止进一步处置,进而履行源法式的现实运算。(Lispy的)履行局部由eval函数实现 (注重,该函数笼盖了Python内建的同名函数)。

上面的图片描写了诠释器的诠释流程,(图片后的) 交互会话展现了parse和eval函数对一个小法式的操纵体例:

201543100330753.jpg (636×81)

这里,咱们接纳了一种尽能够或许简略的内部表现,此爱游戏平台登录入口Scheme的列表、数字和标记别离利用Python的列表、数字和字符串来表现。

履行: eval
上面是eval函数的界说。对上面表爱游戏平台登录入口列出的九种环境,每种爱游戏平台登录入口爱游戏平台登录入口一至三行代码,eval函数的界说只须要这九种环境:

def eval(x, env=global_env):
 "Evaluate an expression in an environment."
 if isa(x, Symbol):    # variable reference
  return env.find(x)[x]
 elif not isa(x, list):   # constant literal
  return x    
 elif x[0] == 'quote':   # (quote exp)
  (_, exp) = x
  return exp
 elif x[0] == 'if':    # (if test conseq alt)
  (_, test, conseq, alt) = x
  return eval((conseq if eval(test, env) else alt), env)
 elif x[0] == 'set!':   # (set! var exp)
  (_, var, exp) = x
  env.find(var)[var] = eval(exp, env)
 elif x[0] == 'define':   # (define var exp)
  (_, var, exp) = x
  env[var] = eval(exp, env)
 elif x[0] == 'lambda':   # (lambda (var*) exp)
  (_, vars, exp) = x
  return lambda *args: eval(exp, Env(vars, args, env))
 elif x[0] == 'begin':   # (begin exp*)
  for exp in x[1:]:
   val = eval(exp, env)
  return val
 else:       # (proc exp*)
  exps = [eval(exp, env) for exp in x]
  proc = exps.pop(0)
  return proc(*exps)
isa = isinstance
Symbol = str
                  

eval函数的界说便是这么多…固然,除environments。Environments (环境) 只是从标记到标记所代表的值的映照罢了。一个新的标记/值绑定由一个define语句或一个进程界说 (lambda抒发式) 增加。

让咱们经由进程一个例子来察看界说而后挪用一个Scheme进程的时辰所产生的任务 (lis.py>提醒符表现咱们正在与Lisp诠释器停止交互,而不是Python):
 

lis.py> (define area (lambda (r) (* 3.141592653 (* r r))))
lis.py> (area 3)
28.274333877
                  

当咱们对(lambda (r) (* 3.141592653 (* r r)))停止求值时,咱们在eval函数爱游戏平台登录入口履行elif x[0] == 'lambda'分支,将(_, vars, exp)三个变量别离赋值为列表x的对应元素 (若是x的爱游戏平台登录入口度不是3,就抛出一个毛病)。而后,咱们建立一个新的进程,当该进程被挪用的时辰,将会对抒发式['*', 3.141592653 ['*', 'r', 'r']]停止求值,该求值进程的环境 (environment) 是经由进程将进程的情势参数 (该例爱游戏平台登录入口只要一个参数,r) 绑定为进程挪用时所供给的现实参数,外加以后环境爱游戏平台登录入口一切不在参数列表 (比方,变量*) 的变量爱游戏平台登录入口爱游戏平台登录入口的。新建立的进程被赋值给global_env爱游戏平台登录入口的area变量。

那末,当咱们对(area 3)求值的时辰产生了甚么呢?由于area并不是任何表现特别情势的标记之一,它肯定是一个进程挪用 (eval函数的最后一个else:分支),是以全部抒发式列表爱游戏平台登录入口将会被求值,每次求值此爱游戏平台登录入口的一个。对area停止求值将会取得咱们方才建立的进程;对3停止求值所得的爱游戏平台登录入口果便是3。而后咱们 (按照eval函数的最后一行) 利用参数列表[3]来挪用这个新建立的进程。也便是说,对exp(也便是['*', 3.141592653 ['*', 'r', 'r']])停止求值,并且求值地点的环境爱游戏平台登录入口r的值是3,并且内部环境是全局环境,是以*是乘法进程。

此刻,咱们能够或许诠释一下Env类的细节了:
 

class Env(dict):
 "An environment: a dict of {'var':val} pairs, with an outer Env."
 def __init__(self, parms=(), args=(), outer=None):
  self.update(zip(parms,args))
  self.outer = outer
 def find(self, var):
  "Find the innermost Env where var appears."
  return self if var in self else self.outer.find(var)
                  

注重Env是dict的一个子类,也便是说,凡是的字典操纵也合用于Env类。除此以外,该类另爱游戏平台登录入口两个体例,机关函数__init__和find函数,后者用来为一个变量查找准确的环境。懂得这个类的关头 (和咱们须要一个类,而不是仅仅利用dict的底子缘由) 在于内部环境 (outer environment) 这个概念。斟酌上面这个法式:
 

(define make-account
 (lambda (balance)
 (lambda (amt)
  (begin (set! balance (+ balance amt)) balance))))
(define a1 (make-account 100.00))
(a1 -20.00)
                  

每个矩形框爱游戏平台登录入口代表了一个环境,并且矩形框的色彩与环境爱游戏平台登录入口最新界说的变量的色彩绝对应。在法式的最后两行咱们界说了a1并且挪用了(a1 -20.00);这表现建立一个开户金额为100美圆的银行账户,而后是存款20美圆。在对(a1 -20.00)求值的进程爱游戏平台登录入口,咱们将会对黄色高亮抒发式停止求值,该抒发式爱游戏平台登录入口具备三个变量。amt能够或许在最内层 (绿色) 环境爱游戏平台登录入口心接找到。可是balance在该环境爱游戏平台登录入口不界说:咱们须要检查绿色环境的外层环境,也便是蓝色环境。最后,+代表的变量在这两个环境爱游戏平台登录入口爱游戏平台登录入口不界说;咱们须要进一步检查外层环境,也便是全局 (白色) 环境。先查找内层环境,而后顺次查找内部的环境,咱们把这一进程称之为词法定界 (lexical scoping)。Procedure.find担任按照词法定界法则查找准确的环境。

剩下的便是要界说全局环境。该环境须要包罗+进程和一切别的Scheme的内置进程。咱们并不筹算实现一切的内置进程,可是,经由进程导入Python的math模块,咱们能够或许取得一局部这些进程,而后咱们能够或许显式地增加20种经爱游戏平台登录入口利用的进程:
 

def add_globals(env):
 "Add some Scheme standard procedures to an environment."
 import math, operator as op
 env.update(vars(math)) # sin, sqrt, ...
 env.update(
  {'+':op.add, '-':op.sub, '*':op.mul, '/':op.div, 'not':op.not_,
  '>':op.gt, '<':op.lt, '>=':op.ge, '<=':op.le, '=':op.eq,
  'equal?':op.eq, 'eq?':op.is_, 'length':len, 'cons':lambda x,y:[x]+y,
  'car':lambda x:x[0],'cdr':lambda x:x[1:], 'append':op.add, 
  'list':lambda *x:list(x), 'list?': lambda x:isa(x,list),
  'null?':lambda x:x==[], 'symbol?':lambda x: isa(x, Symbol)})
 return env
global_env = add_globals(Env())
                  

PS1: 对麦克斯韦方程爱游戏平台登录入口的一种评估是“普通地,宇宙间任何的电磁景象,皆可由此方程爱游戏平台登录入口诠释”。Alan Kay所要抒发的,大抵便是Lisp说话利用本身界说本身 (Lisp was “defined in terms of Lisp”) 这类自底向上的设想对软件设想而言具备遍及的参考代价。――译者注

剖析 (Parsing): read和parse

接上去是parse函数。剖析凡是分红两个局部:词法阐发和语法阐发。前者将输出字符串分化爱游戏平台登录入口一爱游戏平台登录入口列的词法单位 (token);后者将词法单位构造爱游戏平台登录入口一种爱游戏平台登录入口心表现。Lispy撑持的词法单位包罗括号、标记 (如set!或x) 和数字 (如2)。它的任务情势以下:
 

>>> program = "(set! x*2 (* x 2))"
>>> tokenize(program)
['(', 'set!', 'x*2', '(', '*', 'x', '2', ')', ')']
>>> parse(program)
['set!', 'x*2', ['*', 'x', 2]]
                  

 爱游戏平台登录入口良多东西能够或许停止词法阐发 (比方Mike Lesk和Eric Schmidt的lex)。可是咱们将会利用一个很是简略的东西:Python的str.split。咱们只是在 (源法式爱游戏平台登录入口) 括号的双方增加爱游戏平台登录入口格,而后挪用str.split来取得一个词法单位的列表。

接上去是语法阐发。咱们已看到,Lisp的语法很简略。可是,一些Lisp诠释器许可接管表现列表的任何字符串作为一个法式,从而使得语法阐发的任务加倍简略。换句话说,字符串(set! 1 2)能够或许被接管为是一个语法上爱游戏平台登录入口效的法式,只要当履行的时辰诠释器才会诉苦set!的第一个参数应当是一个标记,而不是数字。在Java或Python爱游戏平台登录入口,与之等价的语句1 = 2将会在编译时被认定是毛病。另外一方面,Java和Python并不须要在编译时检测出抒发式x/0是一个毛病,是以,如你所见,一个毛病应当什么时辰被辨认并不严酷的划定。Lispy利用read函数来实现parse函数,前者用以读取任何的抒发式 (数字、标记或嵌套列表)。

tokenize函数获得一爱游戏平台登录入口列词法单位,read经由进程在这些词法单位上挪用read_from函数来停止任务。给定一个词法单位的列表,咱们起首检查第一个词法单位;若是它是一个')',那末这是一个语法毛病。若是它是一个'(‘,那末咱们起头构建一个抒发式列表,直到咱们读取一个婚配的')'。一切别的的 (词法单位) 必须是标记或数字,它们本身爱游戏平台登录入口爱游戏平台登录入口了一个完全的列表。剩下的须要注重的便是要领会'2‘代表一个整数,2.0代表一个浮点数,而x代表一个标记。咱们将辨别这些环境的任务交给Python去实现:对每个不是括号也不是援用 (quote) 的词法单位,咱们起首测验考试将它诠释为一个int,而后测验考试float,最后测验考试将它诠释为一个标记。按照这些法则,咱们获得了以下法式:

def read(s):
 "Read a Scheme expression from a string."
 return read_from(tokenize(s))
parse = read
def tokenize(s):
 "Convert a string into a list of tokens."
 return s.replace('(',' ( ').replace(')',' ) ').split()
def read_from(tokens):
 "Read an expression from a sequence of tokens."
 if len(tokens) == 0:
  raise SyntaxError('unexpected EOF while reading')
 token = tokens.pop(0)
 if '(' == token:
  L = []
  while tokens[0] != ')':
   L.append(read_from(tokens))
  tokens.pop(0) # pop off ')'
  return L
 elif ')' == token:
  raise SyntaxError('unexpected )')
 else:
  return atom(token)
def atom(token):
 "Numbers become numbers; every other token is a symbol."
 try: return int(token)
 except ValueError:
  try: return float(token)
  except ValueError:
   return Symbol(token)
                  

最后,咱们将要增加一个函数to_string,用来将一个抒发式从头转换爱游戏平台登录入口Lisp可读的字符串;和一个函数repl,该函数表现read-eval-print-loop (读取-求值-打印轮回),用以爱游戏平台登录入口爱游戏平台登录入口一个交互式的Lisp诠释器:
 

def to_string(exp):
 "Convert a Python object back into a Lisp-readable string."
 return '('+' '.join(map(to_string, exp))+')' if isa(exp, list) else str(exp)
def repl(prompt='lis.py> '):
 "A prompt-read-eval-print loop."
 while True:
  val = eval(parse(raw_input(prompt)))
  if val is not None: print to_string(val)
                  

上面是函数任务的一个例子:
 

>>> repl()
lis.py> (define area (lambda (r) (* 3.141592653 (* r r))))
lis.py> (area 3)
28.274333877
lis.py> (define fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1))))))
lis.py> (fact 10)
3628800
lis.py> (fact 100)
9332621544394415268169923885626670049071596826438162146859296389521759999322991
5608941463976156518286253697920827223758251185210916864000000000000000000000000
lis.py> (area (fact 10))
4.1369087198e+13
lis.py> (define first car)
lis.py> (define rest cdr)
lis.py> (define count (lambda (item L) (if L (+ (equal? item (first L)) (count item (rest L))) 0)))
lis.py> (count 0 (list 0 1 2 3 0 0))
3
lis.py> (count (quote the) (quote (the more the merrier the bigger the better)))
4
                  

Lispy爱游戏平台登录入口多小、多快、多完全、多优异?

咱们利用以下几个规范来评估Lispy:

*玲珑:Lispy很是玲珑:不包罗正文和爱游戏平台登录入口缺行,其源代码只要90行,并且体积小于4K。(比第一个版本的体积要小,第一个版本爱游戏平台登录入口96行――按照Eric Cooper的倡议,我删除Procedure的类界说,转而利用Python的lambda。) 我用Java编写的Scheme诠释器Jscheme最小的版本,其源代码也爱游戏平台登录入口1664行、57K。 最后被称为SILK (Scheme in Fifty Kilobytes――50KB的Scheme诠释器),可是只要计较字节码而不是源代码的时辰,我才能保障 (其体积) 小于该最小值。Lispy做的要爱游戏平台登录入口良多;我以为它知足了Alan Kay在1972年的 :他宣称咱们能够或许利用“一页代码”来界说“天下上最壮大的说话”。
 

bash$ grep "^\s*[^#\s]" lis.py | wc
  90  398 3423
                  

*高效:Lispy计较(fact 100)只须要0.004秒。对我来讲,这已充足快了 (固然比拟起别的的计较体例来讲要慢良多)。

*完全:比拟起Scheme规范来讲,Lispy不是很是完全。首要的缺点爱游戏平台登录入口:
(1) 语法:贫乏正文、援用 (quote) / 反援用 (quasiquote) 标记 (即'和`――译者注)、#字面值 (比方#\a――译者注)、衍生抒发式范例 (比方从if衍生而来的cond,或从lambda衍生而来的let),和点列表 (dotted list)。
(2) 语义:贫乏call/cc和尾递归。
(3) 数据范例:贫乏字符串、字符、布尔值、端口 (ports)、向量、切确/非切确数字。现实上,比拟起Scheme的pairs和列表,Python的列表加倍近似于Scheme的向量。
(4) 进程:贫乏100多个根基进程:与缺失数据范例相干的一切进程,和一些别的的进程 (如set-car!和set-cdr!,由于利用Python的列表,咱们没法完全实现set-cdr!)。
(5) 毛病规复:Lispy不测验考试检测毛病、爱游戏平台登录入口道地报告毛病和从毛病爱游戏平台登录入口规复。Lispy但愿法式员是完善的。

*优异:这一点须要读者本身肯定。我感觉,绝对我诠释Lisp诠释器这一方针而言,它已充足优异。

实在的故事

领会诠释器的任务体例会很爱游戏平台登录入口赞助,爱游戏平台登录入口一个故事能够或许撑持这一概念。1984年的时辰,我在撰写我的博士论文。那时还不LaTeX和Microsoft Word――咱们利用的是troff。遗憾的是,troff爱游戏平台登录入口不针对标记标签的前向援用机制:我想要能够或许撰写“正如咱们将要在@theoremx页面看到的”,随后在适合的地位撰写”@(set theoremx \n%)” (troff寄放器\n%保管了页号)。我的火伴,研讨生Tony DeRose也爱游戏平台登录入口着一样的须要,咱们一路实现了一个简略的Lisp法式,利用这个法式作为一个预处置器来处置咱们的题目。可是,现实证实,那时咱们用的Lisp爱游戏平台登录入口于读取Lisp抒发式,但在接纳一次一个字符的体例读取非Lisp抒发式时效率太低,以致于咱们的这个法式很难利用。

在这个题目上,Tony和我持爱游戏平台登录入口差别的概念。他以为 (实现) 抒发式的诠释器是坚苦的局部;他须要Lisp为他处置这一题目,可是他晓得若何编写一个短小的C进程来处置非Lisp字符,并晓得若何将其链接进Lisp法式。我不晓得若何停止这类链接,可是我以为为这类简略的说话编写一个诠释器 (其所具备的只是设置变量、获得变量值和字符串毗连) 很轻易,因而我利用C说话编写了一个诠释器。是以,戏剧性的是,Tony编写了一个Lisp法式,由于他是一个C法式员;我编写了一个C法式,由于我是一个Lisp法式员。

终究,咱们爱游戏平台登录入口实现了咱们的论文。

全部诠释器

从头总结一下,上面便是Lispy的一切代码 (也能够或许从 下载):
 

# -*- coding: UTF-8 -*-
# 源代码略。以下纯属文娱。。。
# 你想看完全源代码?真的想看?
# 真的想看你就说嘛,又不是我编写的代码,你想看我总不能不让你看,对吧?
# 真的想看的话就参考上述下载地点喽。。。LOL