Skip to content

Berkeley CS61A

Basic Information

来源:UC Berkeley

课程名称:CS61A, Structure and Interpretation of Computer Programs (2020 Fall)

主题:Python, Scheme, SQL

主要内容:38 个 Lecture, 9 个 Homework, 15 个 Lab, 4 个 Project

课程网站:https://inst.eecs.berkeley.edu/~cs61a/fa20

个人实现:20Fa-CS61A-Berkeley(Private 仓库,依要求不公开)

起止时间:2023.11 - 2023.12

Content

Homeworks & Labs

该课程的 homework 和 lab 围绕 Python 的基本语法、简单数据结构(链表、树)、面向对象、Scheme 的基本语法、SQL 的基本语法等内容展开,并附带自动评分器。在完成过程中,主要遇到了以下问题:

Problem 1

Lab08 has_cycle_constant

As an extra challenge, implement has_cycle_constant with only constant space. (If you followed the hint above, you will use linear space.) The solution is short (less than 20 lines of code), but requires a clever idea. Try to discover the solution yourself before asking around:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def has_cycle_constant(link):
    """Return whether link contains a cycle.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.rest.rest.rest = s
    >>> has_cycle_constant(s)
    True
    >>> t = Link(1, Link(2, Link(3)))
    >>> has_cycle_constant(t)
    False
    """
    "*** YOUR CODE HERE ***"

Project 1-3

该课程的前三个 Projects 围绕 Python 展开,具体如下:

  • Hog: 模拟一个掷骰子游戏,主要练习 Python 基本语法

  • Cats: 实现一个带自动更正功能的打字速度测试器,主要练习 Python 基本语法

  • Ants: 实现一个类似植物大战僵尸的塔防游戏,主要练习面向对象编程

Project 4

该课程的第四个 Project 是用 Python 来写一个 Scheme 语言解释器。Scheme 语言作为 Lisp 的一种方言,是一种函数式编程语言。

为了实现该解释器,大致需要完成以下部分:

  • Reader: 从用户代码读取表达式(涉及括号配对)

  • Eval - Apply 循环: 通过 eval 和 apply 函数的互相调用来解析表达式

  • Special Forms: 处理 if, cond, lambda expression 等特殊函数

  • Quote: 实现 Scheme 中的 quote 和 unquote

  • Frame: 处理变量的生存周期

  • And & Or: 实现逻辑运算符的“短路”行为

  • Macro: 定义宏

  • Tail Call: 优化尾调用(即,不再需要创建 stack frame)

在完成过程中,主要遇到了以下问题:

Problem 1

Q: 如何实现尾调用优化?

A: 通过建立 Thunk 来延迟计算。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Thunk(object):
    """An expression EXPR to be evaluated in environment ENV."""
    def __init__(self, expr, env):
        self.expr = expr
        self.env = env

def complete_apply(procedure, args, env):
    """Apply procedure to args in env; ensure the result is not a Thunk."""
    validate_procedure(procedure)
    val = scheme_apply(procedure, args, env)
    if isinstance(val, Thunk):
        return scheme_eval(val.expr, val.env)
    else:
        return val

def optimize_tail_calls(original_scheme_eval):
    """Return a properly tail recursive version of an eval function."""
    def optimized_eval(expr, env, tail=False):
        """Evaluate Scheme expression EXPR in environment ENV. If TAIL,
        return a Thunk containing an expression for further evaluation.
        """
        if tail and not scheme_symbolp(expr) and not self_evaluating(expr):
            return Thunk(expr, env)
        result = Thunk(expr, env)
        while isinstance(result, Thunk):
            result = original_scheme_eval(result.expr, result.env)
        return result
    return optimized_eval