下面是该类的实现： Link class:

class Link:
    """A linked list is either a Link object or Link.empty

    >>> s = Link(3, Link(4, Link(5)))
    >>> s.rest
    Link(4, Link(5))
    >>> s.rest.rest.rest is Link.empty
    True
    >>> s.rest.first * 2
    8
    >>> print(s)
    (3 4 5)
    """
    empty = ()

    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

    def __repr__(self):
        if self.rest:
            rest_repr = ', ' + repr(self.rest)
        else:
            rest_repr = ''
        return 'Link(' + repr(self.first) + rest_repr + ')'

    def __str__(self):
        string = '('
        while self.rest is not Link.empty:
            string += str(self.first) + ' '
            self = self.rest
        return string + str(self.first) + ')'

>>> s = Link(1, Link(2, Link(3, Link(4))))
>>> s
Link(1, Link(2, Link(3, Link(4))))
>>> s.first = 9
>>> s
Link(9, Link(2, Link(3, Link(4))))

>>> s = link(1, link(2, link(3, link(4))))
>>> s
[1, [2, [3, [4, 'empty']]]]
>>> first(s) = 9
  File "", line 1
SyntaxError: can't assign to function call

本课程此前主要关注程序的 正确性 ——也就是程序能否产生正确输出。不过，计算机科学家也关心如何给问题设计 高效的 解法。量化效率的一种方法，是研究函数的 runtime 如何随输入变化。本课程以函数执行的操作次数衡量运行时间。

A function f(n) has...

• 具有常数运行时间，如果它的运行时间 f 不依赖于 n。其运行时间为 Θ(1).
• 具有对数运行时间，如果它的运行时间正比于 f log(n)。其运行时间为 Θ(log(n)).
• 具有线性运行时间，如果它的运行时间正比于 f n。其运行时间为 Θ(n).
• 具有二次运行时间，如果它的运行时间正比于 f n^2。其运行时间为 Θ(n^2).
• 具有指数运行时间，如果它的运行时间正比于 f b^n，其中某个量为常数 b。其运行时间为 Θ(b^n).

示例 1： 计算下面的表达式只需一次乘法： square(1)；计算另一个表达式也只需一次乘法： square(100)。一般来说，调用 square(n) 所需的操作次数是 常数 ，不会随输入变化 n。因此称 square 的运行时间复杂度为 Θ(1)。

示例 2： 计算下面的表达式只需一次乘法： factorial(1)，而另一个示例需要 100 次乘法。 factorial(100). As n 增大时，函数的运行时间也 factorial 增长 呈线性。因此称 factorial 的运行时间复杂度为 Θ(n).

示例 3： 考虑下面的函数：

def bar(n):
    for a in range(n):
        for b in range(n):
            print(a,b)

对 bar(1) 求值只会产生一次 print 调用，而对 bar(100) 求值会产生 10,000 次 print 调用。随着输入 n 增大时，函数的运行时间也 bar 增长 呈二次增长。因此称 bar 的运行时间复杂度为 Θ(n^2).

示例 4： 考虑下面的函数：

def rec(n):
    if n == 0:
        return 1
    else:
        return rec(n - 1) + rec(n - 1)

对 rec(1) 求值只需一次加法；对 rec(4) 求值会产生 2^4 - 1 = 15 次加法，如下图所示。

在求值过程中， rec(4)会有两次调用 rec(3)、四次调用 rec(2)、八次调用 rec(1)以及十六次调用 rec(0).

因此共有八个 rec(0) + rec(0)、四个 rec(1) + rec(1)、两个 rec(2) + rec(2)和一个 rec(3) + rec(3)，总计 1 + 2 + 4 + 8 = 15 次加法。

As n 增大时，函数的运行时间也 rec 增长 呈指数增长。具体来说，函数的运行时间在输入 rec 增加 1 时大约翻倍。 n 因此称其为指数复杂度。 rec 的运行时间复杂度为 Θ(2^n).

判断函数运行时间增长阶的提示：

• 如果函数是递归的，确定递归调用的次数以及每次递归调用的运行时间。
• 如果函数是迭代的，确定内层循环数量以及每个循环的运行时间。
• 忽略系数。执行某个线性次数操作的函数与执行另一个常数倍线性次数操作的函数都属于线性。 n 100 * n
• 选择最大的增长阶。如果函数第一部分为线性，第二部分为二次，那么整个函数的运行时间为二次。

• 本课程只考虑常数、对数、线性、二次和指数运行时间。

scm> (* 3 (+ 4 2))
18

与 Python 一样，调用表达式按以下步骤求值：

1. 对运算符求值；结果应当是一个过程。
2. 从左到右对各个操作数求值。
3. 把该过程应用于已经求值的操作数。

下面是几个使用内置过程的例子：

scm> (+ 1 2)
3
scm> (- 10 (/ 6 2))
7
scm> (modulo 35 4)
3
scm> (even? (quotient 45 2))
#t

(define <symbol> <expression>)

scm> (define pi (+ 3 0.14))
pi
scm> pi
3.14

对下面的表达式求值： define 表达式时：

1. 对最后一个子表达式（<expression>）求值；在本例中结果为 3.14.
2. 把该值绑定到符号（symbol）；在本例中符号为 pi.
3. 返回这个符号。

The define 形式还可以定义新过程，详见“定义函数”一节。

(cond
    (<p1> <e1>)
    (<p2> <e2>)
    ...
    (<pn> <en>)
    (else <else-expression>))

每个子句的第一个表达式是谓词，第二个表达式是与该谓词对应的返回表达式。 else 子句可以省略；其中的 <else-expression> 是在所有谓词都不为真时使用的返回表达式。

求值规则如下：

1. 按顺序对谓词 <p1>, <p2>, ..., <pn> 求值，直到某个谓词得到真值（除 #f).
2. 对第一个结果为真的谓词所对应的返回表达式求值，并返回其值。
3. 如果所有谓词都不为真且存在 else 子句，则对其返回表达式求值并返回。 <else-expression>.

例如，下面这个 cond 表达式会返回离给定数最近的 3 的倍数： x:

scm> (define x 5)
x
scm> (cond ((= (modulo x 3) 0) x)
            ((= (modulo x 3) 1) (- x 1))
            ((= (modulo x 3) 2) (+ x 1)))
6