知识库

From Mathematics to Generic Programming

Properties1
tags泛型编程, 抽象代数, 数论, c++, stl, 算法, 密码学, alexander-stepanov

16分钟阅读

From Mathematics to Generic Programming

“计算机科学与数学的分离极大地 impoverish 了两者。” —— Alexander Stepanov

核心观点

泛型编程（Generic Programming）不是一种语法特性，而是一种编程态度：将算法抽象到最通用的情境，同时不损失效率。这种态度直接源自抽象代数——数学家们两千年来不断推广定理适用范围的过程，与程序员泛化算法的过程本质相同。

本书由 C++ STL 设计者 Alexander Stepanov 与 Daniel Rose 合著，起源于 Stepanov 在亚马逊 A9.com 的 “Algorithmic Journeys” 课程。全书以历史叙事串联数学与编程：从埃及乘法到 RSA 密码学，从欧几里得到埃米·诺特，展示了一条清晰的脉络——数论 → 抽象代数 → 泛型编程。

全书结构（14章 + 3附录）

第一部分：古代数学基础（第1-5章）

章节主题核心内容
1本书简介泛型编程态度的来源；抽象代数与编程的关系；历史视角的学习方法
2第一个算法埃及乘法（俄罗斯农民乘法）：对数时间乘法，通过加倍和减半实现；算法改进的思维方式
3古希腊数论形数（多边形数）、埃拉托斯特尼筛法、完全数、毕达哥拉斯学派及其致命缺陷（无理数的发现）
4欧几里得算法最大公度量→最大公约数（GCD）；余数算法；零的历史；算法正确性证明（终止性 + 不变式）
5现代数论的兴起梅森素数、费马素数；费马小定理；欧拉定理与 φ 函数；模运算的应用

第5章核心洞察：古希腊人研究完全数等”无用”的纯数学问题，两千年后却催生了现代密码学中最实用的定理。这是纯数学与应用关系的经典案例。

第二部分：抽象代数与泛化（第6-9章）

章节主题核心内容
6数学中的抽象群（Group）：封闭性、结合律、单位元、逆元；幺半群、半群；子群与循环群；拉格朗日定理；理论与模型
7推导泛型算法从埃及乘法出发，逐步解耦算法对类型的要求：加法半群 A + 整数类型 N → 泛化的幂运算（power_semigroup）；斐波那契数计算作为应用
8更多代数结构环（Ring）、半环、欧几里得整环、域；矩阵乘法与半环；社交网络与最短路径应用；埃米·诺特与抽象代数的诞生
9组织数学知识证明的社会属性；泰勒斯定理；欧几里得公理系统；皮亚诺公理；公理解释而非定义

第6-7章是全书的核心：展示了如何从一个具体算法（埃及乘法）出发，通过识别操作所需的最少性质（仅需结合律 + 单位元 = 半群/幺半群），得到可应用于无数场景的泛型算法。

第三部分：泛型编程实践（第10-12章）

章节主题核心内容
10基本编程概念亚里士多德与抽象；概念（Concepts）：类型的需求规范；迭代器类别（输入/输出/前向/双向/随机访问）；值类型与正则类型
11置换与算法置换群；reverse、rotate 算法的多种实现；就地（in-place）vs 非就地；内存自适应算法
12GCD 的扩展Stein 算法（二进制GCD）及其泛化（多项式、高斯整数、艾森斯坦整数）；贝祖恒等式；扩展 GCD；乘法逆元

第10章核心：概念（Concepts）是泛型编程的核心工具——正如数学公理定义了”什么是群”，概念定义了”什么类型可以用于这个算法”。选择正确的概念至关重要：要求太多限制应用范围，要求太少则无法定义有用的算法。

第四部分：综合应用（第13-14章）

章节主题核心内容
13实际应用：密码学公钥密码系统原理；费马素性测试；卡迈克尔数；Miller-Rabin 素性测试；RSA 算法原理与实现（基于前12章所有成果）
14结论全书总结：泛型编程的态度、效率的重要性、接口设计、类型与概念的关系；数学传统的传承

关键概念详解

1. 泛型编程的定义

“泛型编程是一种编程态度，专注于将算法抽象到最通用的情境，同时不损失效率。”

  • 抽象来自抽象代数：数学家推广定理的过程 = 程序员泛化算法的过程
  • 效率是定义的一部分：比类型特化版本慢的泛型算法不会被使用
  • 从具体到抽象：抽象不是凭空产生的，必须从大量具体实例中发现正确的抽象

2. 代数结构层次（从弱到强）

半群 (Semigroup)     结合律 + 封闭性
  ↓
幺半群 (Monoid)       半群 + 单位元
  ↓
群 (Group)            幺半群 + 逆元
  ↓
阿贝尔群 (Abelian)     群 + 交换律
  ↓
环 (Ring)             加法阿贝尔群 + 乘法半群 + 分配律
  ↓
欧几里得整环 (Euclidean Domain)  环 + 欧几里得函数（可做GCD）
  ↓
域 (Field)            环 + 非零元乘法群（有除法）

对应编程中的概念：每一层代数结构都对应一个编程概念，算法只依赖它实际需要的最弱结构。

3. 幂算法的泛化路径（全书主线）

埃及乘法（正整数加法）
  → 乘法-加法半群（任意加法半群 + 整数倍乘）
    → 幂运算（任意半群运算 + 整数次幂）
      → 应用：
         · 斐波那契数（矩阵乘法半群）
         · 图最短路径（min-plus半群 / 热带半群）
         · RSA加密（模乘半群 + 快速幂）

这就是泛型编程的力量：一个算法，无数应用。

4. 概念（Concepts）

  • 定义：对类型的需求规范（语法需求 + 语义需求）
  • 作用：告诉编译器（和程序员）什么类型可以用于某个算法
  • 设计原则：
    • 需求越少 → 适用范围越广
    • 但需求不能太少，否则算法无法做有用的事
    • 正确的概念需要在实现和使用中反复探索

5. 几个重要的编程原则

原则含义
有用返回律（Law of Useful Return）函数应返回计算过程中得到的所有相关结果，避免调用方重复计算
类型分离不要假设多个参数必须是同一类型（如幂函数中底数类型和指数类型可以不同）
完备性接口应覆盖合理的使用场景（如 find 应返回位置而非布尔值）
接口精炼接口需要多次迭代才能正确，就像代码一样
内存自适应算法应适应可用内存量，而非假设固定的内存约束

重要算法整理

埃及乘法 / 快速幂（O(log n)）

核心思想：通过反复加倍运算对象和减半次数，将线性复杂度降为对数。

// 泛型版本：半群幂运算
template <Semigroup A, Integer N>
A power_semigroup(A a, N n) {
    // n > 0
    while (!odd(n)) { a = a * a; n = half(n); }
    if (n == 1) return a;
    return multiply_accumulate_semigroup(a, half(n-1), a*a);
}

欧几里得 GCD 算法

gcd(a, b) = gcd(b, a mod b)   // 直至 b == 0，返回 a
  • 正确性证明：每一步保持 GCD 不变 + 余数严格递减 → 有限步终止
  • 泛化路径：线段 → 整数 → 多项式 → 高斯整数 → 欧几里得整环

Miller-Rabin 素性测试

  • 概率性测试，随机 witness 有 75% 正确率
  • 100 个 witness → 错误概率 < 1/2
  • 基于费马小定理 + 自消去律（x² ≡ 1 mod p ⇒ x ≡ ±1 mod p）

Stein 算法（二进制 GCD）

  • 利用 2 是最小素数的性质，通过移位加速
  • 可泛化到多项式（x 对应 2 的角色）、高斯整数（1+i 对应 2）
  • 存在 Stein 算法工作但不是欧几里得整环的环——开放问题

RSA 密码学（全书数学的终极应用）

原理

  1. 密钥生成：

    • 选两个大素数 p₁, p₂（用 Miller-Rabin 测试）
    • 计算 n = p₁p₂，φ(n) = (p₁-1)(p₂-1)
    • 选公钥 pub 与 φ(n) 互素
    • 计算私钥 prv = pub⁻¹ mod φ(n)（用扩展 GCD）
    • 销毁 p₁, p₂

  2. 加密：c = m^pub mod n

  3. 解密：m = c^prv mod n

  4. 安全性：基于大整数分解的困难性

最实用的互联网安全技术，建立在最”无用”的纯数学（数论）之上——这是贯穿全书的主题。

历史人物脉络

本书特色之一是将数学思想与人的故事结合：

人物时代贡献
泰勒斯公元前6世纪第一个定理；西方哲学与科学之父
毕达哥拉斯学派公元前6-5世纪形数、完全数；发现无理数的危机
欧几里得公元前3世纪《几何原本》；公理方法；GCD算法
埃拉托斯特尼公元前3世纪素数筛法
费马17世纪费马小定理；数论奠基人
欧拉18世纪欧拉定理、φ函数；推广费马结果
高斯18-19世纪《算术研究》；高斯整数；素数分布猜想
伽罗瓦19世纪初群论创始人（20岁死于决斗）
埃米·诺特20世纪初抽象代数奠基人；环论；“诺特环”以她命名
Stevin16世纪多项式GCD；将GCD从整数推广到多项式

与其他知识的关联

个人收获与行动点

  1. 学习算法时问：这个算法可以在什么代数结构上工作？——找到最弱的前提条件
  2. 设计接口时遵守有用返回律——不要让调用者重复你已经算过的东西
  3. 概念设计是泛型编程的核心技能——类型需求要恰到好处，不多不少
  4. 纯数学不是没用的——今天的纯理论可能是明天的核心技术（如数论→密码学）
  5. 从具体到抽象，而不是反过来——好的抽象来自对大量实例的深刻理解，不是凭空设计的
  6. 读《Elements of Programming》——Stepanov & McJones 更正式的姊妹篇，适合深度学习

附录

  • 附录A：数学符号
  • 附录B：常见证明技巧（反证法、归纳法、鸽巢原理）
  • 附录C：非C++程序员的C++指南（模板、概念、函数对象、STL算法与迭代器、C++11新特性）
  • 参考文献 + 索引

“下次你写程序时，试着采用泛型编程的态度。从函数的具体实现开始，然后反复修改和提炼，让它们更高效、更通用……记住你是悠久数学算法思想传统的继承者。遵循泛型编程的原则，你已经在受益于前人的工作——从欧几里得到 Stevin 到诺特。通过设计优美、通用的算法，你也在为他们的工作添上自己的小小贡献。” —— 第14章结语

关系图谱

反向链接