arXiv:0804.3434 · 中英对照阅读
λ 演算讲义
Lecture Notes on the Lambda Calculus
中文速览
理解函数如何作为“可执行的规则”被表达、计算和分析,是这套讲义要带读者解决的核心问题。作者从最基础的 λ 演算讲起,逐步介绍不同类型系统、归约规则与数学语义,并用它们串起计算理论、程序语言和逻辑之间的联系。材料展示了 λ 演算既能刻画一般可计算过程,也能把程序的计算过程和构造性证明联系起来。它的重要性在于,这套极简的工具既帮助我们严谨地研究程序如何运行,也为函数式编程、编译器和程序正确性分析提供了共同基础。
摘要
This is a set of lecture notes that developed out of courses on the lambda calculus that I taught at the University of Ottawa in 2001 and at Dalhousie University in 2007 and 2013. Topics covered in these notes include the untyped lambda calculus, the Church-Rosser theorem, combinatory algebras, the simply-typed lambda calculus, the Curry-Howard isomorphism, weak and strong normalization, polymorphism, type inference, denotational semantics, complete partial orders, and the language PCF.
术语表
- lambda calculus
- λ 演算
- untyped lambda calculus
- 无类型 λ 演算
- simply-typed lambda calculus
- 简单类型 λ 演算
- polymorphically typed lambda calculus
- 多态类型 λ 演算
- Church-Rosser theorem
- Church-Rosser 定理
- combinatory algebra
- 组合代数
- Curry-Howard isomorphism
- Curry-Howard 同构
- weak normalization
- 弱正规化
- strong normalization
- 强正规化
- polymorphism
- 多态性
- type inference
- 类型推断
- denotational semantics
- 指称语义
- complete partial order
- 完全偏序
- PCF
- PCF
- extensional view of functions
- 函数的外延观点
- intensional view of functions
- 函数的内涵观点
- extensional equality
- 外延相等
- intensional equality
- 内涵相等
- higher-order function
- 高阶函数
- bound variable
- 约束变量
- type
- 类型
- computability
- 可计算性
- Turing machine
- 图灵机
- general recursive function
- 一般递归函数
- lambda term
- λ 项