《计算机程序的构造和解释》阅读笔记：准备（3）【python3简单实现lisp解释器（3）】

╰半夏微凉° 2022-12-03 13:26 128阅读 0赞

下面是我在原基础上添加了一些功能的解释器代码（超详细的注释）

################ python3 实现 lisp 解释器
    '''
    语言的语法是指组成正确的语句或表达式的顺序，语义指那些表达式或语句的内在含义。
    
    解释器流程
    程序 => 解析 => 抽象语法树 => 执行(语义) => 结果
    
    
    1:解析语法
    2:添加环境
    3:执行
    4:添加交互式
    5: 将Env重定义为Class
    6:添加符合Schema的语法形式(quote，set!，lambda)
    其实还有一个begin，它是按从左到右的顺序对表达式进行求值，并返回最终的结果，但是已经在环境中定义了
    '''
    
    # from __future__ import division
    import math, readline, sys, re
    import operator as op
    
    ################ 类型
    
    Symbol = str  # 字符串
    List   = list  # 列表
    Number = (int, float)  # 数字
    # Env = dict  # 环境
    
    # ======= 第一步 解析语法 =======
    
    # ======== 解析语法 ========
    def parse(program):
        '''
        语法解析函数
        参数：语句字符串
        返回：抽象语法树，多维数组形式展示嵌套关系
        '''
        return read_from_tokens(tokenize(program))
    
    def tokenize(s):
        '''
        字符串转list
        词法分析：也就是将输入字符串分成一系列 token，返回一个语法列表
        参数：语句字符串
        返回：一个简单的语法列表，tokens
        '''
        # 默认空格分隔。所以需要将括号添加空格，以便分隔出来
        tokens = s.replace('(',' ( ').replace(')',' ) ').split()
        # 判断括号对
        if tokens.count('(') != tokens.count(')'):
            print('括号对不一致！')
            return
        return tokens
    
    def read_from_tokens(tokens):
        '''
        解析list
        语义分析：将tokens组装成抽象语法树
        参数：语法列表
        返回：抽象语法树列表
        如果tokens长度为零直接返回
        去掉tokens第一个字符
        如果第一个字符是（ ，定义一个空列表用来存放语法树，如果tokens第一个字符不是 ），循环将同级语法树存到列表，碰到 ）直接去掉，返回这一层语法树
        其它情况返回字符，如果是数字就返回数字，其它的返回字符串
        '''
        if not isinstance(tokens, List):
            return 
    
        if len(tokens) == 0:
            print('不能为空')
            return
    
        # list去掉第一位元素，如果不是（ 就将它转换类型后加入列表中
        token = tokens.pop(0)
        # 第一个字符是(，然后建立表达式列表，直到匹配到 ）
        if '(' == token:
            # 这里定义空list是为了抽象语法树的嵌套关系
            L = []
            # 语法树第一个字符是）一定是错误语法
            while tokens[0] != ')':
                # 将括号以外的字符加进list中
                # 这里的递归是为了用多维数组展示抽象语法树的嵌套关系，同级的字符放在一个list中
                token_key = read_from_tokens(tokens)
                L.append(token_key)
            # 删除括号结束符 ）,如果不删除的话，碰到 ）就无法循环下去，只能得到部分语法树
            tokens.pop(0)
            # 返回同级数据
            return L
        elif ')' == token:
            print('语法错误')
        else:
            # 返回字符，如果数字转成整数或者浮点类型，其它都是字符串
            return atom(token)
    
    def atom(token):
        '''
        字符串类型转换
        Lispy 的 tokens 是括号、标识符和数字
        '''
        try: return int(token)
        except ValueError:
            try: return float(token)
            except ValueError:
                return Symbol(token)
    
    # python3 不存在apply，所以这里自己定义一个
    def apply(func, *args, **kwargs):
        return func(*args, **kwargs)
    
    def _add(*datas):
        # 加法，支持多数字，多字符串 (+ 1 2 3 4)，(+ "a" "b" "c")
        if len(datas) > 0:
            if isinstance(datas[0], int) or isinstance(datas[0], float):
                sum_num = 0
                for data in datas:
                    sum_num = sum_num + data
                return sum_num
            if isinstance(datas[0], str):
                sum_num = ""
                for data in datas:
                    sum_num = sum_num + data.replace('\"', '')
                return '\"' + sum_num + '\"'
    
    def _sub(*datas):
        # 减法，支持多数字 (- 9 2 1)
        sub_num = 0
        for data in datas:
            if len(datas) > 1 and sub_num == 0:
                sub_num = data
            else:
                sub_num = sub_num - data
        return sub_num
    
    def _mul(*datas):
        # 乘法，支持多数字 (* 2 3 4)
        mul_num = 1
        for data in datas:
            mul_num = data * mul_num
        return mul_num
    
    def _truediv(*datas):
        # 除法，支持多数字 (/ 8 4 2)
        truediv_num = 1
        for data in datas:
            if truediv_num == 1:
                truediv_num = data
            else:
                truediv_num = truediv_num / data
        return truediv_num
    
    def _to_char(char_data):
        # char 转化 字符 #\a，字符 a，判断是否是char
        if isinstance(char_data, str):
            pattern = re.compile(r'(^#\\)([\S]{1})')
            match = pattern.search(char_data)
            if match:
                return char_data
    
    def _to_string(str_data):
        # string 转化 字符串 "aa"，判断是否是字符串
        # 字符串，为了显示区分添加"
        if isinstance(str_data, str):
            pattern = re.compile(r'(^\")(\S*)(\"$)')
            match = pattern.search(str_data)
            if match:
                return str_data
    
    def _map(fn, *datas):
        # python3的map返回一个迭代器，所以这里需要处理一下，返回list
        datas = map(fn, *datas)
        new_datas = []
        # for data in datas:
        #     new_datas.append(data)
        try:
            while True:
                line = next(datas)
                if line is None:
                    break
                new_datas.append(line)
        except StopIteration:
            pass
        return new_datas
    
    # ====== 第五步 重定义环境 =========
    
    # ====== 将Env环境定义成class =======
    class Env(dict):
        '''
        Env继承dict类
        '''
        def __init__(self, parms=(), args=(), outer=None):
            # 构造函数
            # 初始化环境，zip可以直接转化成dict
            self.update(zip(parms, args))
            # 全局环境
            self.outer = outer
        def find(self, var):
            # 查找环境，这个是为了后面的局部环境和全局环境
            # 如果存在在局部环境中返回局部环境，没有就去全局环境找
            return self if (var in self) else self.outer.find(var)
    
    class Procedure(object):
        '''
        这个可以看作一个创造局部环境和外部环境的函数
        '''
        def __init__(self, parms, body, env):
            # 构造函数
            '''
            parms 是参数名
            body 是表达式
            env 是外部环境
            '''
            self.parms = parms 
            self.body = body 
            self.env = env
        def __call__(self, *args):
            # 调用对象的时候执行
            '''
            执行表达式，但是将上层的环境当作外部环境，将这一层的参数名与实际值设置为局部环境
            '''
            return eval(self.body, Env(self.parms, args, self.env))
    
    # ======= 第二步 设置环境 =======
    
    # ====== 环境 =======
    '''
    环境是指变量名与值之间的映射。eval 默认使用全局环境，包括一组标准函数的名称（如 sqrt 和 max，以及操作符 *）
    '''
    def standard_env():
        '''
        简单的标准环境
        环境是一个字典形式，将环境中添加标准库，或者自己定义的函数
        '''
        env = Env()  # 环境是一个字典形式
        # vars函数是python自带函数 返回对象object的属性名和属性值的字典形式
        env.update(vars(math)) # sin, cos, sqrt, pi, ...
        # 添加一些符合Scheme标准的环境
        env.update({
            # '+':op.add, 
            # '-':op.sub, 
            # '*':op.mul, 
            # '/':op.truediv,
            '+': _add,
            '-': _sub,
            '*': _mul, 
            '/': _truediv, 
            '>':op.gt, 
            '<':op.lt, 
            '>=':op.ge, 
            '<=':op.le, 
            '=':op.eq, 
            '%': op.mod,
            # 'add': op.add,
            # 'sub': op.sub,
            # 'mul': op.mul,
            # 'truediv': op.truediv,
            # 'add': _add,
            # 'sub': _sub,
            # 'mul': _mul,
            # 'truediv': _truediv,
            'mod': op.mod,
            'abs':     abs,
            'append':  op.add,  
            'apply':   apply,
            'begin':   lambda *x: x[-1],
            'car':     lambda x: x[0],
            'cdr':     lambda x: x[1:], 
            'cons':    lambda x, y: [x] + y if isinstance(y, List) else [x] + [y],
            'eq?':     op.is_, 
            'equal?':  op.eq, 
            'length':  len, 
            'list':    lambda *x: List(x), 
            'list?':   lambda x: isinstance(x,List), 
            'map':     _map,
            'max':     max,
            'min':     min,
            'not':     op.not_,
            'null?':   lambda x: x == [], 
            'number?': lambda x: isinstance(x, Number),   
            'procedure?': callable,
            'round':   round,
            'symbol?': lambda x: isinstance(x, Symbol),
            '#t': True,
            '#f': False,
            # (vector 1 "2" 3 "4") 类似列表的，我就用列表表示了
            # 'vector': lambda *x: '#'+schemestr(list(x)), 
            'boolean?': lambda x: True if x else False,
            'string?': lambda x: True if _to_string(x) else False,
            'char?': lambda x: True if _to_char(x) else False,
            # 'display': print
    
        })
        # 返回这个环境
        return env
    
    # 作为全局环境      
    global_env = standard_env()
    
    # ======= 第三步 执行 ========
    
    # ======= 执行 ========
    def eval(x, env=global_env):
        '''
        执行语义
        如果是字符，去环境中查找变量值或者函数
        如果是数字直接输出
        如果第一个字符是if先递归计算判断条件的值，然后递归计算输出值
        如果第一个字符是define递归计算出值，然后加入环境中
        其它的情况先用第一个字符去环境中查找函数，然后递归将后面的字符存入列表，最后执行函数参数是之前列表
    
        if 语句：
            (if test conseq alt)
            test是判断条件，如果符合输出conseq，否则输出alt
            例子：
                (if (> 1 0) 1 0)
                (if (> 1 0) (+ 1 2) (- 9 3))
        define 语句：
            (define symbol exp)
            例子：
                (define x 1)
        quote 语句：
            (quote exp)
            例子：
                (quote (1 2 3))
        set! 语句：
            (set! var exp)
            例子：
                (set! x 1) 
                注意：set! 是修改已经定义的变量，没有定义就使用会报错
        lambda 语句：
            (lambda (var...) body)
            例子：
                (lambda (x) (+ x x))
                注意：lambda 匿名函数需要定义以后使用 (define xx (lambda (x) (+ x x)))，用(xx 4)方式调用
        let 语句：
            (let ((var val) ...) exp)
            例子：
                (let ((f +) (x 2)) (f x 3)) 其实就是把加法赋值给f，把3赋值给x，然后计算
                (let ((x 2) (y 3)) (+ x y)) x=2，y=3，x+y
                (let ((double (lambda (x) (+ x x))))(list (double (* 3 4))(double (/ 99 11))(double (- 2 7))))
        begin 语句：
            (degin exp....)
            例子：
                (define x 1)
                (begin (set! x 1) (set! x (+ x 1)) (* x 2))
        display 语句：
            例子：
                (display "a") 相当于python的print
        实现python的range函数：
            例子：
                (define range (lambda (a b) (if (= a b) (quote ()) (cons a (range (+ a 1) b)))))
                (range 0 10)
                注意：Scheme 没有for，whlie，所以循环用递归代替
        map 语句：
            例子：
                (define fib (lambda (n) (if (< n 2) 1 (+ (fib (- n 1)) (fib (- n 2))))))
                (define range (lambda (a b) (if (= a b) (quote ()) (cons a (range (+ a 1) b)))))
                (map fib (range 0 20))
        list ：
            例子 (list 1 2 3 4)
        实现python中list的count函数：
            例子：
                (define count (lambda (item L) (if L (+ (equal? item (car L)) (count item (cdr L)))
                (count 0 (list 0 1 2 3 0 0))
        '''
        if isinstance(x, Symbol):
            # 字符 #\a，字符 a
            char_data = _to_char(x)
            if char_data:
                # 返回字符
                return char_data
            # 字符串，为了显示区分添加"
            str_data = _to_string(x)
            if str_data:
                # 返回字符串
                return str_data
            # 如果是字符就去环境中找，返回变量值或者函数
            # 这样可以根据调用去局部环境或者外部环境查找
            data = env.find(x)[x]
            return data
        # 常量返回
        elif not isinstance(x, List):
            return x                
        elif x[0] == 'quote':
            # (quote exp)
            # (quote (1 2))
            (_, exp) = x
            # quote 就是原样输出表达式
            return exp
        # if 语句，形式(if test conseq alt),test是判断条件,符合条件输出conseq,不符合输出alt
        elif x[0] == 'if':
            # (if test conseq alt)
            # (if (> 1 2) 1 2)
            # 语句形式分别赋值
            (_, test, conseq, alt) = x
            # 用递归计算条件
            exp = (conseq if eval(test, env) else alt)
            # 判断后结果可能是表达式所以也用递归计算出值
            return eval(exp, env)
        # define 定义变量，形式(define symbol exp),sybol是变量，exp是值
        elif x[0] == 'define':
            # (define var exp)
            # (define x 1)
            (_, var, exp) = x
            # 用递归计算数据
            # 将定义的数据加进环境中
            # 用递归是因为如果exp是个表达式，就计算出它的值再加入环境
            env[var] = eval(exp, env)
        elif x[0] == 'set!':
            # (set! var exp)
            # (set! x 1)，注意这里的x必须先定义过，也就是环境中必须有
            (_, var, exp) = x
            # set! 其实是一个覆盖环境值的操作，用递归也是因为如果exp是个表达式，就计算出它的值再加入环境
            env.find(var)[var] = eval(exp, env)
        elif x[0] == 'lambda':
            # (lambda (var...) body)
            # (lambda (x) (+ x x))，这样其实无法调用，一般用(define xx (lambda (x) (+ x x))) 定义，(xx 3)调用
            (_, parms, body) = x
            '''
            这里就用到了Procedure类
            因为lambda匿名函数的参数都是局部的，外面是无法调用的，所以这里先保存参数名，表达式，将env当作外部环境(因为可能会用到外部环境的变量)
            当调用的时候将值传入，与参数名配对，当作局部环境
            '''
            return Procedure(parms, body, env)
        elif x[0] == 'let':
            # (let ((var val) ...) exp1 exp2 ...)
            (_, var, exp) = x
            # 将定义分别加进环境中
            for data in var:
                env[data[0]] = eval(data[1], env)
            # 最后执行
            return eval(exp, env)
        else:
            '''
            Schema 计算形式第一个元素是计算符号:(+ 1 2)
            '''
            # list第一个元素去环境里去找这个函数
            # (proc arg...)
            proc = eval(x[0], env)
            # list后面的元素是函数参数
            args = [eval(exp, env) for exp in x[1:]]
            # 将参数传入函数
            data = proc(*args)
            return data
    
    # ======== 交互式 ========
    def repl(prompt='lis.py> '):
        '''
        终端交互式，死循环读取终端输入字符串，执行，转换成字符串，打印到终端
        '''
        # 这里学习python的交互式加入提示
        sys.stderr.write('-*- lispy 0.01 -*- Quit using \'exit()\'\n')
        # 死循环读取终端输入
        while True:
            data_str = input(prompt)
            # 防止不输入程序报错
            if data_str:
                # python交互式一样，输入exit()结束程序
                if data_str == 'exit()':
                    sys.exit()
                # 执行
                val = eval(parse(data_str))
                if val is not None:
                    # 打印 
                    print(schemestr(val))
    
    def schemestr(exp):
        """
        将数据转位字符串
        """
        if isinstance(exp, List):
            # 将列表中所有元素转成字符串，用空格分隔，开始结束加上括号
            return '(' + ' '.join(map(schemestr, exp)) + ')'
        elif isinstance(exp, bool):
            # bool 转化 #t: true，#f: flase
            if exp:
                return '#t'
            else:
                return '#f' 
        else:
            # 转成字符串
            return Symbol(exp)
    
    repl()

以下是原文的测试，我自己跑过也是没有问题的，大家可以试试

lis.py> (define circle-area (lambda (r) (* pi (* r r))))
    lis.py> (circle-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> (circle-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
    lis.py> (define twice (lambda (x) (* 2 x)))
    lis.py> (twice 5)
    10
    lis.py> (define repeat (lambda (f) (lambda (x) (f (f x)))))
    lis.py> ((repeat twice) 10)
    40
    lis.py> ((repeat (repeat twice)) 10)
    160
    lis.py> ((repeat (repeat (repeat twice))) 10)
    2560
    lis.py> ((repeat (repeat (repeat (repeat twice)))) 10)
    655360
    lis.py> (pow 2 16)
    65536.0
    lis.py> (define fib (lambda (n) (if (< n 2) 1 (+ (fib (- n 1)) (fib (- n 2))))))
    lis.py> (define range (lambda (a b) (if (= a b) (quote ()) (cons a (range (+ a 1) b)))))
    lis.py> (range 0 10)
    (0 1 2 3 4 5 6 7 8 9)
    lis.py> (map fib (range 0 10))
    (1 1 2 3 5 8 13 21 34 55)
    lis.py> (map fib (range 0 20))
    (1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)

我在原有的基础上添加了一些函数，然后添加了字符串，因为布尔值的表示是\#t，\#f所以我也改变了显示方式，也增加了一些语法判断，然后是交互式的缓存和正常退出程序

最近几天一直学习这个教程，对于Scheme的语法大致有了一些了解，整个解释器其实很简单，也很简陋，只能算一个计算器

接下来就要开始学习《计算机程序的构造和解释》这本书了，加油！！！！

这里还有一个几十种语言实现lisp解释器的项目，有一步步实现解释器的步骤，也有别人实现的源码

[github地址][github]

[中文翻译github地址][github 1]

[github]: https://github.com/kanaka/mal/tree/8a19f603868e36b9af8eb705f01bb96297cb65d0
[github 1]: https://github.com/Windfarer/mal-zh