Aha.
正在载入中英对照阅读…

arXiv:0804.3434 · 中英对照阅读

λ 演算讲义

Lecture Notes on the Lambda Calculus

Peter Selinger

中文速览

理解函数如何作为“可执行的规则”被表达、计算和分析,是这套讲义要带读者解决的核心问题。作者从最基础的 λ 演算讲起,逐步介绍不同类型系统、归约规则与数学语义,并用它们串起计算理论、程序语言和逻辑之间的联系。材料展示了 λ 演算既能刻画一般可计算过程,也能把程序的计算过程和构造性证明联系起来。它的重要性在于,这套极简的工具既帮助我们严谨地研究程序如何运行,也为函数式编程、编译器和程序正确性分析提供了共同基础。

摘要

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
λ 项