形式语义教材-Ch1 基本理论

形式语义

第一章 理论基础

§ 1.1 引 言

1941年Church创建了Lambda演算理论。它是一个形式系统,可作为计算模型,如同Turing机可作为计算模型一样。Lambda演算形式系统主要由两部分组成:其一是合法表达式的形式系统,其二是变换规则的形式系统.

Lambda演算系统可有多种。其主要区别在于构成Lambda演算形式系统的两个组成部分的具体定义上。不同的Lambda演算系统会得到一些不同的定理。Lambda演算系统如同Turing机系统一样,可描述任何一部分递归函数的计算过程。因此,Lambda演算系统也可视为一种算法语言系统。其中的Lambda表达式相当于语言的一个程序。程序如何执行,由Lambda演算系统的机制来确定。Lambda演算理论是函数式语言的基础,也是指称语义学的理论基础。

§1.2 Lambda 演算

纯Lambda表达式(以后简称λ表达式)是最小的一种表达式,主要由变量名和抽象符号λ以及括号等符号构成。若用X表示变量,用Exp表示纯Lambda表达式之集,则Exp集的定义如下。

■ 定义 1.2.1. λ表达式

若用BNF表示法,则可描述如下(x ∈Var, E ∈Exp ):

从上述定义可知纯 _表达式是非常小的表达式,以致于不能再小。但它将成为 _演算系统的基础。那么一个作为计算模型的形式系统应具备什么样的条件呢?很显然它起码应具备二个条件:其一是它有很强的功能,以致于能够描述复杂的计算过程;其二是它应

形式语义教材-Ch1 基本理论

形式语义教材-Ch1 基本理论

Word文档免费下载Word文档免费下载:形式语义教材-Ch1 基本理论 (共28页,当前第1页)

形式语义教材 Ch1 基本理论相关文档

最新文档

返回顶部