洋葱菌的博客

著名的CS自学网站CS自学指南的首页就提到过这门传奇的编程入门课程——SICP。在该网页内提供的版本是加州伯克利大学的线上学习资源。

这门课程并不将重点放在某一个具体的编程语言上，而是更多关注编写程序本身的通用范式，从通用计算机处理语言的逻辑入手，帮助初学者快速上手，开启编程之旅。

笔者在新加坡国立大学举办的暑校中全程参与了SICP课程，NUS版本的SICP基于该校学生自主构建的JavaScript实验平台SourceAcademy，使用JS的子语言Source（由开发者创立），良好的前端性质赋予了这门课程更人性化的程序交互功能（比如逐步实现程序）。这里顺便贴出笔者完成的课程设计：一个2048小游戏的化学同位素版本，在此处可以直接体验（点击左上角Run按钮，在右侧切换到游戏窗口视图（第四个））。代码在上述链接和Github仓库都可以查看。这个游戏的灵感来源于Isotopic256。

对于至少接触过一个学期的CS专业课的同学而言，这门课程应该确实是略显基础了，极大部分内容，哪怕学校课程并没有明确指出，在实际编程的过程中也应该自主体会过了（比如内存模型和变量生存周期之类）。

基于以上原因，我利用参与这门课程的无聊时间整理了一些值得记忆或了解的知识点，供已经有一些编程基础，但是又对这门课程感兴趣的同学们快速补全。

Recursion：递归的进一步探讨

SICP指出，递归不仅仅是一个函数调用它自己，或者说在此基础上可以做出一种分类，即迭代过程和递归过程，这两种方式的关键区别在于是否产生函数栈堆积。

概念辨析：

递归函数：在函数体内部直接或者间接调用自身的函数。
递归过程（Recursive Process）：通过一系列延迟的运算操作实现的程序运行过程。
迭代过程（：不含有延迟的运算操作而实现的程序运行过程。

一个递归函数的实现可能是通过递归过程，也可能是通过迭代过程。

来看经典的递归例子——阶乘计算：

function factorial(n) {
  return n === 0
         ? 1
         : n * factorial(n - 1);
}

这个例子是一个递归过程，因为当前步骤需要在子步骤完成之后在进行计算，这就是“延迟的”运算操作。

再来看阶乘计算的另一种实现方式：

function factorial(n) {
    return fact_iter(1, 1, n);
}

function fact_iter(product, counter, max_count) {
  return counter > max_count
         ? product
         : fact_iter(counter * product, counter + 1, max_count);
}

我们发现在这段代码中，虽然函数调用了自己，但是当前的返回值没有任何需要在子步骤计算完成之后额外计算的内容（即先前的函数调用不需要堆积在栈内存里等待递归结束），因此这个过程是一个线性迭代过程。

将递归过程转换为迭代过程

一般来说，新建一个Helper function迭代函数，记录迭代状态和当前结果，然后将递归函数函数做成顶层函数，调用迭代函数的初态。可以将上例封装起来（注意迭代函数只需要记录两个参数）：

function factorial(n) {
  function iter(product, counter) {
    return counter > n
           ? product
           : iter(counter * product, counter + 1);
  }
    return iter(1, 1);
}

下面介绍一种更普适的编程思想（风格），可以将一般递归转化为尾递归（即迭代过程）。

Continuation Passing Style：递归的CPS风格

可以参考这篇博客。

简单来说，CPS也是通过实现一个迭代函数完成的，与之前的方法的区别在于以下两点：

CPS的迭代顺序是逆序的（从n到1），与普通递归顺序一致。
CPS通过一个匿名函数描述当前的迭代状态。具体地说，这个函数包括了从当前状态到最终结果需要进行的一切步骤。
CPS可以把任何递归函数变成尾递归（见下文），可以保证在一定程度上避免栈溢出（对于支持尾递归优化的编译器而言）。

从第二点可以看出，程序最终的返回值就是把最终的状态函数作用在初值上。

举个例子：

function factorial_cps(n, cont)
{
    return n === 1
           ? cont(1)
           : factorial_cps(n - 1, x => cont(n * x));
}

function factorial(n)
{
    return factorial_cps(n, x => x);
}

上例实现了阶乘函数，重点在于理解递归的传入参数x => cont(n * x)这一步骤。根据假设，此处的x代表的是之后的递归过程得到的结果，此处可以理解为已经计算好的n - 1的阶乘，那么在这一步我们要对这个结果做的事情就是乘上n，然后将其扔进现有的cont函数供后续处理。

从上例我们可以看出，CPS维护的参数函数的特征是：接入一个参数，返回一个参数。

对于较为复杂的递归方程，比如需要调用两次子递归得到现态的斐波那契数列： \[ f(n) = f(n - 1) + f(n - 2), f(0) = 0 \] 我们也可以把它转化成CPS风格，但需要进行一些转化以便维持cont函数的性质：

function fib_cps(n, cont)
{
    return n === 0
           ? cont(0)
           : n === 1
           ? cont(1)
           : fib_cps(n - 1, x => fib_cps(n - 2, y => cont(x + y)));
}

function fib(n)
{
    return fib_cps(n, x => x);
}

可以证明，对于任意的递归方程，我们都可以通过某种方式用CPS风格将其实现。这就是为什么CPS是一种风格而不是算法。它只是我们实现递归的众多方式之一。

Higher Order Functions：函数式编程基础

函数可以作为另一个函数的输入/返回值。外层函数成为Higher Order Function。

function sum(term, a, next, b)
{
    return a > b
                 ? 0
                 : term(a) + sum(term, next(a), next, b);
}

function cube(x)
{
  return x * x * x;
}

function add_one(x)
{
  return x + 1;
}

sum(cube, 3, add_one, 5); // Calculates 3^3 + 4^3 + 5^3

以上是一个简易的使用函数式思想的例子，实现了自定义处理方式和迭代方法的累加器。

函数嵌套定义

在代码块中（包括函数定义内部）可以定义其他函数，使其仅在该函数内部可见。

function sum(term, a, next, b)
{
  function cube(x)
  {
    return x * x * x;
  }

  function add_one(x)
  {
    return x + 1;
  }
    return a > b
                 ? 0
                 : term(a) + sum(term, next(a), next, b);
}

sum(cube, 3, add_one, 5); // Calculates 3^3 + 4^3 + 5^3

在封装功能时可以使用此特性。

匿名函数

出现了！是野生的lambda函数。

在Source语言中，匿名函数的定义方法如下：

列出参数（多参数使用小括号括起）
列出返回值（多条语句使用大括号括起）
使用=>连接

使用匿名函数改写上例：

function sum(term, a, next, b)
{
    return a > b
                 ? 0
                 : term(a) + sum(term, next(a), next, b);
}

sum(x => x * x * x, 3, x => x + 1, 5); // Calculates 3^3 + 4^3 + 5^3

多参数函数改写格式：

(x, y) => x + y

函数体包含多行：

x => {const y = x * x * x; return y;}

函数作为返回值

字面意思，返回一个函数即可。

下例创建一个自定义步长的迭代器：

function create_adder(n)
{
    function adder(x)
    {
        return x + n;
    }
    return adder;
}

使用匿名函数：

function create_adder(n)
{
    return x => x + n;
}

支持嵌套调用：

create_adder(4)(22); // Evaluate to 26

一个有趣的例子：重复应用n次函数，体现了函数式和递归的结合：

function repeat(f, n)
{
    return n === 1
           ? x => f(x)
           : x => f(repeat(f, n - 1)(x));
}

function add(x)
{
    return x + 1;
}

function square(x)
{
    return x * x;
}

repeat(add, 5)(1); // Gets 6 = 1+1+1+1+1+1

repeat(square, 3)(2); // Gets 256 = ((2^2)^2)^2

Data Abstaction

介绍了一些简单的数据封装概念，可以看成是数据结构的前置内容。由于大部分内容都比较基础，这里仅挑选了一些有趣的例子和知识点进行说明。

简单的例子：pair

给出一个基于函数式的数对结构（pair）的有趣实现方法：

function make_pair(x, y)
{
    return component => component === 0 ? x : y;
}

function head(p)
{
    return p(0);
}

function tail(p)
{
    return p(1);
}

const p = make_pair(3, 6);
display(head(p)); // Gets 3
display(tail(p)); // Gets 6

有区别于一般的思路（把数据结构封装成对象），这里把数据结构做成了一个函数，基于输入实现不同的功能，对于用户而言，效果是一样的。

另一种更抽象的实现方式：

const pair = (x, y) => f => f(x, y);

const head = p => p((x, y) => x);
const tail = p => p((x, y) => y);

const p = pair(3, 6);

display(head(p)); // Gets 3
display(tail(p)); // Gets 6

这里的数对依然是函数，但是这个函数接受一个函数作为输入，并把两个数据传入输入的函数中，因此要获得第一个数据或者第二个数据就需要通过传入不同的函数（比如接入两个参数返回第一个）实现。

这里也可以看出功能封装在编程中的体现：功能一致，实现方式可以不同。

用pair实现list：这就是链表

显然如果用pair去维护pair我们就可以维护更多数据了，列表定义如下：

一个列表（list）是空的（null），或者一个pair，它的tail是一个列表。

像这样：pair(1, pair(2, pair(3, pair(4, pair(5, null)))))

从内存模型上看，就是通过链表结构维护的线性表。显然，这种写法暗示了我们可以通过递归的方式遍历链表（而不是常用的for循环）。事实上，在Source语言的前两个章节，根本没有变量和循环可以使用（只能说确实是为编程基础教育设计出来的语言）。

（二叉）树

SICP接着介绍了如何使用pair维护tree。由于一个pair只能储存两个数据（抽象的或者不抽象的），基于这种方式实现的结构必然是二叉树（不考虑FirstChild-NextSibling方法表示的多叉树）。甚至，由于如果存了两个数据就没有多余的地方存放指向子节点的指针，这棵二叉树只能在度小于等于1的节点上存放数据。

叶子节点的tail指针指向null，因此这棵树满足：在所有度小于等于1的节点存有有且仅有一个相应类型的数据。

给出递归形式的定义：

一个树（tree）是空的（null），或者是一个pair，它的head是一个数据或者一棵树，tail是一棵树。

在这种语义下，树的结构事实上是一种嵌套链表。

注意根据定义，一个树只能维护一种固定的数据类型（而在多态语义下的链表，根据上述定义方式可以维护多种类型，有点像元组）。

处理树的基本算法此处也不多赘述，基本全部会在数据结构系列的课程中涵盖。

二分查找，二叉搜索树（BST）和其他

数据结构的基本内容，此处不多赘述。有需要的可以阅读鹤翔万里的笔记本或者OI Wiki，挑合适的内容看就行。

然后关于课程里提到的符号处理，浙大计算机系的同学应该会惊喜的发现这是FDS课程的一个经典Project“自动求导机”的简化版（只有加乘运算和单参数）。有需要的同学可以看一看我的实现。

SICP工具库

NUS的历代学生开发并维护了一堆用于SICP的工具库，文档可以在这里查看。

Curves：图形库

SICP提供了一个简单的用于实现曲线的图形库。

一个曲线是具有如下性质的函数：

接受一个范围在[0, 1]的浮点参数
返回一个点对象（实现决定）

实验环境预置了图形库，图形库接口的使用方法并不是课程关心的内容，细节可以参阅文档，这里不多赘述。

一个简单的绘制2D曲线的例子：

import {make_point, draw_connected_full_view, x_of, y_of} from "curve";

function circle(t)
{
    return make_point(math_cos(2 * math_PI * t), math_sin(2 * math_PI * t));
}

function spiral_rep(rep, t)
{
    const p = circle(t * rep % 1.0);
    const r = t;
    return make_point(r * x_of(p), r * y_of(p));
}

function get_spiral_rep(rep)
{
    return t => spiral_rep(rep, t);
}

draw_connected_full_view(200)(get_spiral_rep(3));

效果如下：

Sound：声音库

事实上，生成音符就是生成对应的波形。SICP提供了对应的解析工具用于播放，我们需要做的就是把想要播放的音符做成正弦函数，参数的变化范围就是对应的时长（秒），因此可以注意到正弦函数里的系数乘上了\(2\pi\)。

比如生成标准音：

const pitch_A_wave = t => math_sin(2 * math_PI * 440 * t); // A4
const pitch_A = make_sound(pitch_A_wave, 1.5);
play(pitch_A);

生成和弦（也就是正选波的叠加），注意通过振幅调整音量：

const C_maj_chord_wave =
    t => 0.33 * math_sin(2 * math_PI * 261.63 * t) + // C4
    0.33 * math_sin(2 * math_PI * 329.63 * t) + // E4
    0.33 * math_sin(2 * math_PI * 392.00 * t); // G4
const C_maj_chord = make_sound(C_maj_chord_wave, 1.5);
play(C_maj_chord);

拼接成旋律（也就是分段函数）：

const doremi_wave =
        t => t < 0.5
    ? math_sin(2 * math_PI * 261.63 * t) // C4
    : t < 1.0
    ? math_sin(2 * math_PI * 293.66 * t) // D4
    : math_sin(2 * math_PI * 329.63 * t); // E4
const doremi = make_sound(doremi_wave, 1.5);
play(doremi);

这里贴一个音名频率对照表：

音符	频率(hz)	音符	频率(hz)	音符	频率(hz)	音符	频率(hz)
C0	16.35	C2	65.41	C4	261.63	C6	1046.50
C#0	17.32	C#2	69.30	C#4	277.18	C#6	1108.73
D0	18.35	D2	73.42	D4	293.66	D6	1174.66
D#0	19.45	D#2	77.78	D#4	311.13	D#6	1244.51
E0	20.60	E2	82.41	E4	329.63	E6	1318.51
F0	21.83	F2	87.31	F4	349.23	F6	1396.91
F#0	23.12	F#2	92.50	F#4	369.99	F#6	1479.98
G0	24.50	G2	98.00	G4	392.00	G6	1567.98
G#0	25.96	G#2	103.83	G#4	415.30	G#6	1661.22
A0	27.50	A2	110.00	A4	440.00	A6	1760.00
A#0	29.14	A#2	116.54	A#4	466.16	A#6	1864.66
B0	30.87	B2	123.47	B4	493.88	B6	1975.53
C1	32.70	C3	130.81	C5	523.25	C7	2093.00
C#1	34.65	C#3	138.59	C#5	554.37
D1	36.71	D3	146.83	D5	587.33
D#1	38.89	D#3	155.56	D#5	622.25
E1	41.20	E3	164.81	E5	659.25
F1	43.65	F3	174.61	F5	698.46
F#1	46.25	F#3	185.00	F#5	739.99
G1	49.00	G3	196.00	G5	783.99
G#1	51.91	G#3	207.65	G#5	830.61
A1	55.00	A3	220.00	A5	880.00
A#1	58.27	A#3	233.08	A#5	932.33
B1	61.74	B3	246.94	B5	987.77

事实上，有从音符MIDI名称计算频率的公式： \[ f = 440 \cdot 2^{\frac{n - 69}{12}} \] 其中\(f\)是频率，单位是赫兹；\(n\)是MIDI音名，中央C的音名是60。

基于此，可以实现基于正弦波的编曲引擎。笔者写了一个简单的版本以供参考：

import {make_sound, play} from "sound";

// Use MIDI number to represent note
const get_freq = number => 440 * math_pow(2, (number - 69) / 12);

// Single note wave generator
function note_wave(number, loudness)
{
    const freq = get_freq(number);
    return t => loudness * math_sin(2 * math_PI * freq * t);
}

// Chord wave generator
function chord_wave(numbers, loudness)
{
    function iter(remains, cnt, cur_chord)
    {
        return is_null(remains)
               ? cur_chord
               : iter(tail(remains), cnt + 1,
                      t => (cnt / (cnt + 1)) * cur_chord(t) +
                            note_wave(head(remains),
                                 1 / (cnt + 1))(t));
    }
    const unit_chord = iter(numbers, 0, s => 0);
    return t => loudness * unit_chord(t);
}

function make_melody(waves, durations)
{
    // Helper function to write durations onto time axis 
    function get_timestamps(cur, acc)
    {
        return is_null(cur)
               ? null
               : pair(acc + head(cur), get_timestamps(tail(cur), acc + head(cur)));
    }
    
    // Whole duration of the melody
    // Use recursive progress to calculate everything again
    // Because loops are yet to be available
    function get_length(cur)
    {
        return is_null(cur)
               ? 0
               : head(cur) + get_length(tail(cur));
    }
    
    // Connect several waves together
    function wave_connect(waves, timestamps)
    {
        return is_null(waves)
               ? t => 0
               : t => t < head(timestamps)
               ? head(waves)(t)
               : wave_connect(tail(waves), tail(timestamps))(t);
    }
    
    const timestamps = get_timestamps(durations, 0);
    const length = get_length(durations);

    return make_sound(wave_connect(waves, timestamps), length);
}

以下这段使用示例代码生成了烂大街的4536251和弦进行：

const c1 = chord_wave(list(60, 65, 69), 1); // IV
const c2 = chord_wave(list(62, 67, 71), 1); // V
const c3 = chord_wave(list(64, 67, 71), 1); // iii
const c4 = chord_wave(list(64, 69, 72), 1); // vi
const c5 = chord_wave(list(62, 65, 69), 1); // ii
const c6 = chord_wave(list(62, 67, 71), 1); // V
const c7 = chord_wave(list(60, 64, 67, 72), 1); // I

const melody = make_melody(list(c1, c2, c3, c4, c5, c6, c7), list(1, 1, 1, 1, 1, 1, 2));
play(melody);

Arcade_2d：2D游戏引擎

一个简陋的2D游戏引擎。简陋是指这个引擎只实现了一些最基本的功能，其他的比如物理模拟全部需要自己写。

标签

分类

友链