admin管理员组文章数量:1531793
一般的源代码程序经过编译器解析生成解析树。Lisp的奇特之处就在于，你可以完全卸除程序，控制这种解析树，进行任意的存取操作，也就是可以用程序生成程序。
Python号称最接近Lisp的语言，但它终究不是。但是因为几乎所有语言都是图灵完备的，所以即使Python无法实现Lisp的某个功能，也可以通过在Python中写一个Lisp解释器来实现那个功能。很奇妙是不是？
我们来写一个简单的基于Scheme语法的Lisp解析器吧：
先导入库：
################ lis.py: Scheme Interpreter in Python 3.10
## (c) Peter Norvig, 2010-18; See http://norvig/lispy.html
## Type hints and minor additions by Luciano Ramalho
import math
import operator as op
from collections import ChainMap
from itertools import chain
from typing import Any, NoReturn
from typing import Union, List, MutableMapping, Optional, Iterator
Symbol = str
Atom = Union[float, int, Symbol]
Expression = Union[Atom, List]
Environment = MutableMapping[Symbol, object]
print(Atom, Expression)
print(Environment)创建Parse解析
def parse(program: str) -> Expression:
"Read a Scheme expression from a string."
return read_from_tokens(tokenize(program))
def tokenize(s: str) -> List[str]:
"Convert a string into a list of tokens."
return s.replace('(', ' ( ').replace(')', ' ) ').split()
def read_from_tokens(tokens: List[str]) -> Expression:
"Read an expression from a sequence of tokens."
if len(tokens) == 0:
raise SyntaxError('unexpected EOF while reading')
token = tokens.pop(0)
if '(' == token:
exp = []
while tokens[0] != ')':
exp.append(read_from_tokens(tokens))
tokens.pop(0) # discard ')'
return exp
elif ')' == token:
raise SyntaxError('unexpected )')
else:
return parse_atom(token)
def parse_atom(token: str) -> Atom:
"Numbers become numbers; every other token is a symbol."
try:
return int(token)
except ValueError:
try:
return float(token)
except ValueError:
return Symbol(token)创建环境
def standard_env() -> Environment:
"An environment with some Scheme standard procedures."
env: Environment = {}
env.update(vars(math)) # sin, cos, sqrt, pi, ...
env.update(
{
'+': op.add,
'-': op.sub,
'*': op.mul,
'/': op.truediv, # 小数除
'quotient': op.floordiv, # 商 地板除法 整数除
'>': op.gt,
'<': op.lt,
'>=': op.ge,
'<=': op.le,
'=': op.eq,
'abs': abs,
'append': lambda *args: list(chain(*args)),
'apply': lambda proc, args: proc(*args),
'begin': lambda *x: x[-1],
'起': lambda *x: x[-1],
'car': lambda x: x[0],
'cdr': lambda x: x[1:],
'cons': lambda x, y: [x] + y,
'eq?': op.is_,
'equal?': op.eq,
'filter': lambda *args: list(filter(*args)),
'length': len,
'list': lambda *x: list(x),
'list?': lambda x: isinstance(x, list),
'map': lambda *args: list(map(*args)),
'max': max,
'min': min,
'not': op.not_,
'null?': lambda x: x == [],
'number?': lambda x: isinstance(x, (int, float)),
'procedure?': callable,
'round': round,
'symbol?': lambda x: isinstance(x, Symbol),
'display': lambda x: print(lispstr(x), end=''),
'显': lambda x: print(lispstr(x), end=''),
'newline': lambda: print(),
}
)
return envprocedure过程
class Procedure:
"A user-defined Scheme procedure."
def __init__(self, parms: List[Symbol], body: Expression, env: Environment):
self.parms = parms # 一个由Symbol对象组成的列表，表示过程的参数
self.body = body # 一个表示过程体的表达式，即实际的执行代码
self.env = env # 一个表示该过程执行环境的对象，通常是一个Environment类的实例
def __call__(self, *args: Expression) -> Any: # 使用星号表示接受可变数量的参数，这些参数是表达式（Expression）类型
local_env = dict(zip(self.parms, args)) # 创建一个本地环境，将过程的参数和传递给过程的实际参数一一对应起来，形成一个字典。
env: Environment = ChainMap(local_env, self.env) # 创建一个新的环境，该环境是本地环境和外部环境（在初始化时传递的环境self.env）的链式映射（ChainMap）
return evaluate(self.body, env) # 使用新创建的环境调用evaluate函数，传递过程体和新环境，以执行实际的过程体并返回结果。执行函数
def evaluate(x: Expression, env: Environment) -> Any:
"Evaluate an expression in an environment."
if isinstance(x, str): # variable reference
return env[x]
elif not isinstance(x, list): # constant literal
return x
elif x[0] == 'define': # (define var exp)
_, var, exp = x
env[var] = evaluate(exp, env)
elif x[0] == 'lambda': # (lambda (var...) body)
_, parms, body = x
return Procedure(parms, body, env)
elif x[0] == 'quote': # (quote exp)
_, exp = x
return exp
elif x[0] == 'if': # (if test consequence alternative)
_, test, consequence, alternative = x
if evaluate(test, env):
return evaluate(consequence, env)
else:
return evaluate(alternative, env)
elif x[0] == '设': # (define var exp)
_, var, exp = x
env[var] = evaluate(exp, env)
elif x[0] == '函': # (lambda (var...) body)
_, parms, body = x
return Procedure(parms, body, env)
elif x[0] == '引': # (quote exp)
_, exp = x
return exp
elif x[0] == '若': # (if test consequence alternative)
_, test, consequence, alternative = x
if evaluate(test, env):
return evaluate(consequence, env)
else:
return evaluate(alternative, env)
else: # (proc arg...)
proc_exp, *args = x
proc = evaluate(proc_exp, env)
arg_values = [evaluate(exp, env) for exp in args]
return proc(*arg_values)交互执行函数
def run_lines(source: str, env: Optional[Environment] = None) -> Iterator[Any]:
global_env: Environment = ChainMap({}, standard_env())
if env is not None:
global_env.update(env)
tokens = tokenize(source)
while tokens:
exp = read_from_tokens(tokens)
yield evaluate(exp, global_env)
def run(source: str, env: Optional[Environment] = None) -> Any:
# 实际上，这个函数只是简单地迭代了run_lines的所有结果，并没有对其进行任何操作。
# 最后，返回run_lines的最后一个结果。
for result in run_lines(source, env):
pass
return result运行测试：
percent = """
(define a 126)
(define b (* 6 50))
(* (/ a b) 100)
"""
run(percent)输出：42
当然我们也可以用中文关键字：
percent = """
(设 a 126)
(设 b (* 6 50))
(* (/ a b) 100)
"""
run(percent)这样看起来是不是更亲切一些了呢？
以上代码节选自：https://github/fluentpython/lispyhttps://github/fluentpython/lispy
总结下：《黑客与画家》作者格雷厄姆说Lisp是最棒的编程语言，大家一起来感受下吧！
附：
scheme学习资料：The Scheme Programming Language, 4th Edition
2024.1.2日补充：增加 procedure过程定义
版权声明：本文标题：编程奇妙之旅：使用Python写一个Lisp语言的解释器 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/xitong/1726827006a1086184.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论