scheme解释器项目学习笔记

scheme解释器项目学习

尾递归

函数中递归的地方没有后续处理的东西了，此时是尾递归

参考：https://www.zhihu.com/question/20761771

尾递归优化

1. 是当我们的代码是尾递归格式的代码时，编译器或者解释器会对其优化，

2. 还是说当我们写了一个递归代码后，编译器或者解释器会自动把该代码转变为尾递归格式，然后再对其进行优化呢。

经过大致确认，是第一种情况

优化过程：

一个递归代码送进来，然后在计算一次后，返回的结果还是个函数，用一个变量保存下来，然后把这个变量再次送入到eval函数中。这样就是把递归变成了一个迭代的过程。

然后

就是把递归函数产生的结果保存下来，然后把这个结果作为参数再次传入递归函数中

参考：https://www.ruanyifeng.com/blog/2015/04/tail-call.html

https://zhuanlan.zhihu.com/p/36587160

https://zhuanlan.zhihu.com/p/350103441 蹦床优化

https://www.cnblogs.com/echoT/p/16175632.html#probelm-ec1

垃圾回收机制GC

lazy function definition

项目中的难点

eval函数和apply函数的相互递归

eval函数中遇到函数调用代码，需要使用apply函数处理这部分代码；

apply函数在处理代码时，需要获取操作数operand，这个时候又需要调用eval函数。

这两个函数的递归出口，就是原始语句，比如数字或字符串，关键字等

尾递归优化的实现

整体框架

Environments类

image-20230925004413496

用一个字典存储的当前环境下的所有变量的值，还有一个指向父环境的指针。

(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))