表达与实现的区别

引言

最近在读王垠的博客，借着辨析“表达”和“实现”这两个概念，总结一下收获。

表达

表达就是编写表达式，构造表达式树。表达式树也是一种数据结构。

标准表达式树

很多种数据都有一些标准格式，比如图片的png格式，表达式却没有。每种高级语言都可以看作这样一种格式，不过哪一个都不是标准，不像 Unicode 那样是字符串的统一编码（理想情况下）。

标准表达式树至少能简化：

• 代码解析
• 进程间通信

还没有这样的标准，所以我们先讨论一下它不是什么。

并非字节码

标准表达式树并非 python java 的字节码，而是完全基于抽象表达式树。不同的解释器可能对这树有不同的解释，但这是因为不同的解释器对树中函数、运算符的解释不同，树的拓扑结构是确定的。这和浏览器解析网页类似，区别是表达式树存储了过程信息。标准表达式树和 HTML 一样，其格式有国际标准。

并非 SQL

标准表达式树并非另一种 SQL。虽然 SQL 也是不涉及过程的声明式语言，但它等价于关系代数的表达式树（实际情况是只支持一部分关系代数操作）。

但有一点值得关注：SQL 语句不是数据，但能在数据库间通用（一定程度上），这一点和标准表达式树是类似的。SQL 的问题在于，因为关系代数仅能用在关系数据库的查询上，其表达范围有限。

实现

在我们的计算机中真正运行的只有机器指令。当谈到实现时，我们的思路集中在机器的一举一动上，想着内存和指针。比如，下面的 C 程序连接两个链表，省略了链表的定义：

link concatenate(link pointer1, link pointer2) {
    link tmp;
    tmp = pointer1;
    while (tmp->next) {
        tmp = tmp->next;
    }
    tmp->next = pointer2;
    return pointer1;
}

C 程序在手把手教机器怎么做：

• 创建临时变量
• 触及null之前迭代这个变量
• 修改变量所指向的内存区域的值
• 返回值

在 Scheme 中：

(define (extend seq1 seq2)
  (if (null? seq1)
      seq2
      (cons (car seq1)
            (extend (cdr seq1) seq2))))

• 我们知道把一个元素加在链表头部的方法(cons element items)
• 我们知道关系extend(s1, s2) = [s1[0]] + extend(s1[1:], s2)
• s1[1:]不断减小s1，最终变为空表。在 s1 是空表时，结果应为 s2

对比可见，Scheme 用表达式刻画参数与返回值之间的关系，解释器负责计算这个表达式。C 程序分配内存、修改内存、控制程序流程（体现在while和return），CPU 负责执行这些命令（编译后）。

只从语义的角度考虑，Scheme 抽象层级高于 C，因为计算的本质是表达式求值，而不是命令 CPU 在内存上做各种操作。lambda 演算早于冯诺依曼计算机出现，说明表达式求值是独立于计算机体系结构的。

使用 C 语言时，我们既要表达也要实现，先构建表达式，再用各种算法、数据结构计算它。

表达与实现

列方程与解方程

当我们习惯方程后，解题可以分成两部分：

• 把问题表达为方程
• 解方程

当我向不懂方程的人解释方程思想时，他们会本能地思考解方程过程是怎样映射到原问题的解决步骤的，试图将解方程中“移项”、“合并”等等操作在原问题中意味着什么想出来，好像只有这样才能确信方程的解就是原问题的答案。

但我们都知道，解方程的技术和获得方程的技术（比如数学建模）之间没有耦合，研究数值分析的数学家根本不必考虑他的方程求解技术会被用在什么问题上。

表达式树的构造和解释

理想情况下，编程序也应该和列方程类似。非计算机专业的人可能说不清算账的计算器和电脑有什么本质区别，我认为他们在这件事上的直觉恰是我们应该追求的目标。科学计算器可以看作一个算数表达式的解释器，而计算机与计算器的区别（对用户来说）应该仅仅在：

• 各类IO
• 函数
• 外存储
• 多进程

使用计算器时不需要考虑内存管理，计算机也不应该。

人构造表达式，计算机计算表达式的值。人只需要关心自己的表达式是否能解决问题，不必操心自己的表达式将怎样被计算，就像列方程的时候不考虑怎样解方程一样。解方程是数学家的事，如何（高效）计算表达式是解释器的事，是解释器设计者的事。

的值。人只需要关心自己的表达式是否能解决问题，不必操心自己的表达式将怎样被计算，就像列方程的时候不考虑怎样解方程一样。解方程是数学家的事，如何（高效）计算表达式是解释器的事，是解释器设计者的事。