读《编程原本》

分类: 阅读

这本书,我在北师大图书馆和它有过一面之缘。当时随意翻了几页就被吸引到了,然而毕竟是讲算法相关的东西,上学的时候耐心不足,没能下定决心借去读。

终于又在苏州图书馆偶遇此书,看来有缘,不妨一读。

(注:后来发现这本书的英文版可以免费在线阅读,http://elementsofprogramming.com/


这本书的作者,是C++ STL的创始人。这本书涉及大量基础算法,很多都是C++ STL里面存在的。可是这本书并不是讲STL的书。

这本书讲的是Elements of Programming,这也是这本书的原书名;编程原本,即编程的本质。作者借助严密的数学工具来定义一系列算法和相关的数据结构。可以说,这本书也展现了STL的设计理念和思路。

书中算法并非用C++语言实现的,而是C++的一个变种,一个现实中并不存在的变种。但这个C++变种也是C++创始人操刀参与设计的!
加入了Concept的C++20与书中所采用的变种C++极为相似。而本书中也有Concept,虽然与C++20的Concept不尽相同,但也可以说是殊途同归。作者进行严密定义所借助的主要工具便是它了。


一上来,作者就教我们基础——第一章:基础。

虽说基础,却是令人耳目一新的基础。

他不讲编程的基本数据类型一般有哪些,也不讲基本的流程控制结构有什么。反而是通过一种分类的思想,介绍了编程中常常碰到的一些概念。

有些概念在中文版中实在难以区分,结合英文原版理解会好一些。

比如一开始介绍的,EntitySpeciesGenus,后俩我完全不记得中文版是怎么翻译的了,印象中是很容易混淆的。

实际上,上面三个词,分别对应的是实体(我个人的翻译),其中要比概念小一些。

实体又分为抽象实体具体实体抽象实体一般是永恒不变的,具体实体则是存在于时空中的独立的事物(但未必一定是物理存在的)。

属性(Attribute)具体实体抽象实体的一种关联,一般用于描述具体实体的特性、度量等。可以说,属性实体变得有血有肉。

标识(Identity)用于区分不同的个体,或者说指示某一个体。即使具体实体的属性发生变化,或者所处的时空发生变化,都不影响其拥有一致的“标识”。换句话说也就是“身份”。

快照(Snapshot)是具体实体在某时某刻的全部属性的集合。

作者举了一些现实的例子,比如“蓝色”、“13”是抽象实体,“苏格拉底”和“美国”是具体实体,“苏格拉底眼睛的颜色”和“美国州的数量”则是属性

抽象种,描述本质相同的抽象实体的共同特性。例如“人类”,“美国的州”都是抽象种

函数是关联一个或多个抽象实体的规则,这些实体分别是形参(Argument)结果(Result)

抽象属描述具有部分相似的不同。例如“数字”和“运算符”。
具体属描述具有部分相似的不同的具体种,例如哺乳动物和禽类动物。

一个实体只属于一个,决定了实体的产生和存在方式。一个实体可以属于多个,分别描述了一些实体的特性。


讲了这么多,和编程有什么关系呢?

简而言之,对象(Object)值(Value)就是实体类型(Type)就是概念(Concept)就是

那么什么是数据(Dataum)解释(Interpretation)在一起,就是
什么是数据不必多说,计算机里面的一部分0和1就是数据。
解释也好理解,同样一个1,可能是一个整数,也可能是一个小数。所以我们需要知道数据如何被解释,也就是数据对应的实体是什么。
对应于实体数据,可以称为数据表示(Representation)

除了,还有值类型(Value Type),表示和一系列数据的对应关系。

数据表示一个抽象实体时,数据良构(Well-Formed)的。例如,32位的二进制序列被解释成补码整数时是良构的,而NaN在解释为IEE 754浮点数时则是非良构(Ill-Formed)的。

同一值类型的两个,当表示同一个抽象实体时,称之为相等的;当其对应的数据是完全一致的序列时,则称为表示相等的。

举个例子,下面两个分数f1f2,应被视作相等而非表示相等。所以一般来说,我们应该为它写一个等号运算符重载。

struct 分数 {
    int 分子;
    int 分母;
};

分数 f1 = {1, 2};
分数 f2 = {2, 4};

对象是内存中用于表示具体实体的值,对象的状态是可变的。对象虽然也有,但它的可能在内存中不连续。

对象类型是描述该类型的对象的状态的一种值类型

……

好啦,摘抄(翻译)了这么多,大概能够体会出作者的良苦用心了吧!作者对编程中涉及的各个与数据、类型等相关的概念,全部进行了非常细化的分类抽象,看起来虽然复杂,但理清楚之后,实在对写出具有良好正确性的程序大有裨益!

可见,学好哲学对编程多么有帮助! 下面我们再接触一下贯穿全书的核心概念——“概念”!


概念(Concept)即一系列要求(Requirement)。C++20中的概念其实是由一系列约束(Constraint)构成的。其中思想可以说是一脉相承。

本书中的概念,需要一些与类型相关的概念定义:

类型属性:一个类型到一个的映射,用于描述类型的一些特性。例如sizeof(T),映射类型T到其所占内存空间大小的

类型函数:一个类型到另一个相关类型的映射。例如std::remove_pointer_t<T>映射某个指针类型T到其对应的原始类型,Arity(F)映射函数类型F到其参数个数。

类型构造器:通过已有的一个或多个类型创造一个新类型。例如std::add_pointer_t<T>可以通过类型T创造其指针类型。

哇,对象有构造器,类型还有构造器,是不是有一种Haskell的感觉。其实TypeScript也有类似的做法。

总之,这些泛型、模板做得相对高级的编程语言,都会有针对类型的计算,而不仅仅是传统编程中对对象或者的计算。

1

这是一个一元函数概念的例子。把上面形式化描述,用自然语言翻译一下就是:

一元函数(F) 定义为:

  • 函数(F) 即 F也是函数概念,
  • Arity(F) = 1,即参数个数(元)为1,
  • 且 定义Domain类型函数为符合一元函数概念的类型到符合常规概念的类型的映射,
    其实现为F -> InputType(F, 0),即将函数映射到其第一个参数的类型。

有了Concept的定义,作者就开始借助这些约束谓词、类型运算等进行算法和数据结构的设计了。比如:

template<typename Op>
    requires(BinaryOperation(Op))
Domain(Op) square(const Domain(Op)& x, Op op)
{
    return op(x, x);
}

这不是标准C++的写法,而是书中定义的变种C++的写法。

很好理解,square函数接受两个参数,第一个参数是二元运算Op定义域类型的一个值,第二个参数是一个二元运算Op类型的函数。它返回一个二元运算Op定义域类型的值。

具体实现就不必多说了。

很显然,这样的定义十分严谨,保证不会有不符合预期的参数传入。


如果是使用当下C++的模板来写这样一个程序,还是颇为费劲的,一般来说大家都不会去考虑这些约束,直接写成这样:

template <typename T, typename Op>
T square(const T& x, Op op)
{
    return op(x, x);
}

很显然,如果我们随意传一些参数,错误信息会深入模板内部实现,比较简单直接:

#include <concepts>
#include <functional>
#include <iostream>
#include <string>

int sum(int a, int b) { return a + b; }
int bad() { return 0; }

template <typename T, typename Op>
T square(const T& x, Op op) {
  return op(x, x);
}

int main() {
  int x = 3;
  // std::cout << square(3, bad); // <--- error
  std::cout << square(x, sum);
}
<source>: In instantiation of 'T square(const T&, Op) [with T = int; Op = int (*)()]':
<source>:16:29:   required from here
<source>:11:12: error: too many arguments to function
   11 |   return op(x, x);
      |          ~~^~~~~~

https://godbolt.org/z/id6Qgq

对于我们来说,square可能是个库函数,报错信息出在库函数内部,让人摸不着头脑,并不友好。

我们来试试C++20的Concept吧!

#include <concepts>
#include <functional>
#include <iostream>

template <class F>
concept BinaryOperation = requires(F&& f) {
  std::invoke(std::forward<F>(f), 0, 0);
};

template <BinaryOperation F>
struct _Domain;

template <class T>
struct _Domain<T(*)(T, T)> {
  using type = T;
};

template <class F>
using Domain = _Domain<F>::type;


int sum(int a, int b) { return a + b; }
int bad() { return 0; }

template <BinaryOperation Op>
Domain<Op> square(const Domain<Op>& x, Op op) {
    return op(x, x);
}

int main() {
  int x = 3;
  // std::cout << square(3, bad); // <--- error
  std::cout << square(x, sum);
}
<source>: In function 'int main()':
<source>:32:29: error: no matching function for call to 'square(int, int (&)())'
   32 |   std::cout << square(3, bad);
      |                             ^
<source>:26:12: note: candidate: 'template<class Op>  requires  BinaryOperation<Op> Domain<Op> square(Domain<Op>&, Op)'
   26 | Domain<Op> square(const Domain<Op>& x, Op op) {
      |            ^~~~~~
<source>:26:12: note:   template argument deduction/substitution failed:
<source>: In substitution of 'template<class F> using Domain = typename _Domain::type [with F = int (*)()]':
<source>:26:12:   required by substitution of 'template<class Op>  requires  BinaryOperation<Op> Domain<Op> square(Domain<Op>&, Op) [with Op = int (*)()]'
<source>:32:29:   required from here
<source>:19:7: error: template constraint failure for 'template<class F>  requires  BinaryOperation<F> struct _Domain'
   19 | using Domain = _Domain<F>::type;
      |       ^~~~~~
<source>:19:7: note: constraints not satisfied
<source>:6:9:   required for the satisfaction of 'BinaryOperation<F>' [with F = int (*)()]
<source>:6:27:   in requirements with 'F&& f' [with F = int (*)()]
<source>:7:14: note: the required expression 'std::invoke(forward<F>(f), 0, 0)' is invalid
    7 |   std::invoke(std::forward<F>(f), 0, 0);
      |   ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

尽管错误变得复杂,但从中可以清楚地看到,错误原因是约束条件没有满足。

比起刚才直接说square内部的函数调用传参过多,现在应用了Concept的程序会在我们使用square时告诉我们没有匹配到函数,这更容易帮助我们定位错误。毕竟square内部本没有错。

另外当函数调用层次变深、模板参数增多之后,就会知道有Concept在最外层帮我们阻挡是多么幸福!

https://godbolt.org/z/-fFYas


啊哈!这本十年前的书的思想,终于可以被今天的C++舒服地实践了!
(以前当然也可以写晦涩的模板来做约束,只是报错信息更不会友好…)

以上就是基础——基础基本上涵盖了分类思想,对类型运算做了一些定义,并引入Concept概念。

夹带一点私货,我感觉一般意义上的抽象实体对象具体实体值类型抽象种引用类型具体种概念抽象属接口具体属

再往后,本书涉及的算法和数据结构也是层层递进,从最简单的基本变换、运算做起,到线性序、顺序代数结构、迭代器、坐标结构、可变后继的坐标结构、复制重整、分区和合并、符合对象等等。每一次算法或者数据结构的定义,都伴随着严密周到的概念约束的定义。可以说几乎有些形式化验证的意味了。

如果你想要对算法和数据结构有一个全新的认识,尤其是想了解C++ STL的设计理念的话,一定不要错过这本书!