解析SICP-Proj4 EC

Photo by Florian Klauer on Unsplash|600

本文章请搭配NJU-SICP Project04 EC (Adopted from CS61A from Berkeley) 食用

Written By SweetGargamel

原问题

Why current interpreter cannot properly process tail call?

Consider such scheme code:

1
2
3
4
5
6


(define (factor n acc)
  (if (= n 0)
      acc
      (factor (- n 1) (* acc n))))

(factor 10 1)

The current evaluation process is:

1
2
3
4


     scheme_eval(`(factor 10 1))
===> return scheme_eval(`(factor 9 10))
===> return (return scheme_eval(`(factor 8 90)))
...

The problem is python interpreter does not properly perform tail call.

There’re mainly three way to solve this problem:

transform the scheme interpreter to an non-recursive interpreter, i.e., eliminate all recursive call to scheme_eval. That can be accomplished by
- rewrite this interpreter to an CEK interpreter. (‘C’ means control, ‘E’ means environment, ‘K’ means continuation). See here and Chap. 5 of ESSENTIALS OF PROGRAMMING LANGUAGES.
- rewrite this interpreter to an trampolined interpreter. We use this approach.
transform the source scheme code, e.g. Continuation-Passing Style transformation.

The trampoline technique is the simplest one. So we use this approach.

Trampoline

The trampoline technique is a simple technique to perform proper tail call in a “bad” language (e.g. Python, C, C++, Java, …).

For example, we can define a sum recursive function in python:

1
2
3
4
5


def sum(n, acc):
    if n == 0:
        return acc
    else:
        return sum(n - 1, acc + n)

And sum(10000, 0) will produce a StackOverflow error. Now we “trampoline” such function:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Unevaluated:
    def __init__(self, n, acc):
        self.n = n
        self.acc = acc

def sum_tram(n, acc):
    if n == 0:
        return acc
    else:
        return Unevaluated(n - 1, acc + n)

def sum(n, acc):
    # use do-while here is better, but Python does not support that
    res = sum_tram(n, acc)
    while isinstance(res, Unevaluated):
        res = sum_tram(res.n, res.acc)
    return res

Now sum(10000, 0) will properly works. This can be generalized to transform all recursive functions to loops, see here. But the above form is enough for our problem.

The Tasks

Complete the function optimize_tail_calls in scheme_eval_apply.py. It returns an alternative to scheme_eval that is properly tail recursive. That is, the interpreter will allow an unbounded number of active tail calls in constant space. It has a third argument tail that indicates whether the expression to be evaluated is in a tail context.

The Unevaluated class represents an expression that needs to be evaluated in an environment. When optimized_eval receives a non-atomic expression in a tail context, it returns an Unevaluated instance. Otherwise, it should repeatedly call original_scheme_eval until the result is a value, rather than an Unevaluated.

A successful implementation will require changes to several other functions, including some functions that we provided for you. All expressions throughout your interpreter that are in a tail context should be evaluated by calling scheme_eval with True as the third argument (now called tail). Your goal is to determine which expressions are in a tail context throughout your code and change calls to scheme_eval as needed.

Once you finish, uncomment the following line in scheme_eval_apply.py to use your implementation:

scheme_eval = optimize_tail_calls(scheme_eval)

疑惑引出

问题

1
2
3
4
5
6
7
8


def optimize_tail_calls(original_scheme_eval):
 def optimized_eval(expr, env, tail=False):
        if tail and not scheme_symbolp(expr) and not self_evaluating(expr):
            return Unevaluated(expr,env)
        # BEGIN PROBLEM EC

        # END PROBLEM EC
    return optimized_eval

是的，很显然你会不会觉得，开始在运行第一行代码的时候，如果是尾递归的话就会直接返回一个Unevaluated的玩意，这程序不就该崩了吗？

答案

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


def optimize_tail_calls(original_scheme_eval):
 def optimized_eval(expr, env, tail=False):
        if tail and not scheme_symbolp(expr) and not self_evaluating(expr):
            return Unevaluated(expr,env)
        # BEGIN PROBLEM EC
        res=original_scheme_eval(expr, env)
        while isinstance(res, Unevaluated):
            res = original_scheme_eval(res.expr, res.env)
        return res
        # END PROBLEM EC
    return optimized_eval

是的你看了答案会不会更觉得下面的代码根本就运行不到？
（当然除了该这些代码还应该按照助教的建议，把凡是尾递归的部分都给加一个tail=True的参数）

使用Vscode的Debug功能解析

怎么使用Debug

直接按照助教的提示修改.vscode/launch.json文件即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


{
    "version": "0.2.0",
    "configurations": [
        {
            "name": "Python: Current File",
            "type": "python",
            "request": "launch",
            "program": "scheme.py",
            "args":[
                "-i",
                "tests.scm"
            ],
            "console": "integratedTerminal",
            "justMyCode": true,

        }
    ]
}

你可以修改tests.scm里面的测试用例来测试，下面是我的例子

1
2
3
4
5
6


(define (factor n acc)
  (if (= n 0)
      acc
      (factor (- n 1) (* acc n))))

(factor 10 1)

当然别忘打断点了

Debug，启动！

点击Start Debugging
然后你会发现左边出来这些东西，分别是你的VARIABLES、WATCH、CALL_STACK
- VARIABLES是当前的变量
- WATCH可以添加自己想看的表达式或者变量的值
- CALL_STACK看调用的堆栈

我们发现他停到了if这个语句停下来了

现在解释器在干啥？

我们发现左上角的expr的第一个sym是define，说明他正在进行do_define_form

怎么让解释器往下走？

在最上面有几个按钮，分别是下面几个

Step Into 如果当前语句是一个call expression，他就会进入函数体让你看函数体内部是怎么执行的；否则和Step Over一样。
Step Over：不管是否是call expression直接当一条普通语句运行过去。
Step Out：跳出当前Frame（比如A里面调用了B函数，我现在通过Step Into进入了B所在的Frame,Step Out就直接回到A里面）