计算理论计算理论3章 Lambda演算模型

VIP免费

2025-01-13 2 0 714.38KB 38 页 5.9玖币

侵权投诉

计算理论

第三章 Lambda 演算模型

Lambda 演算理论

Alonzo Church 1936 年给出 lambda 演算

Lambda 演算理论是一个形式系统，同 Turing

机一样可作为计算模型。

 Lambda 演算理论是函数式语言的基础，也是

指称语义学的理论基础。

主要内容：

纯Lambda 演算理论

纯Lambda 演算实例

纯Lambda 演算的扩展

Lambda 演算理论

 Lambda 演算形式系统主要有两部分：

 表达式的形式系统

 变换规则的形式系统

Lambda 演算理论

纯Lambda 表达式形式：主要由变量名和抽象符号

、“ .” 以及括号等符号构成。

用E表示表达式， Exp 表示表达式之

集， Exp 定义如下：

 xExp ，其中 x是变量名。

若E1Exp ，E2Exp ，则 E1 E2  Exp 。

若E Exp ，x是变量，则x.E  Exp 。

若E  Exp ，则（ E） Exp 。

其中， E1 E2型表达式称为应用型表达式，x.E

型

表达式称为抽象型表达式。

1 Lambda 演算理论

表达式的 BNF 表示（ x为变量， EExp ）：

E ::= x | E1 E2 | x.E | (E)

记法约定：

E1 E2 E3 … En  (…(((E1 E2)E3))…) En

x1. x2. … . xn. E  x1. (… (xn. E)…)

x1. x2. … . xn. E  x1x2 … xn. E

x1. x2. … . xn. E1 … En

 x1. x2. … . xn.(E1…En)

1 Lambda 演算理论

定义 1 作用域

设有表达式x.E ，则定义x中的 x的作

用域为其中的体表达式 E部分。

定义 2 约束出现自由出现

对变量 x，当它出现在表达式x.E 中时，则

称x在表达式x. E 中的出现是约束出现。若

它出现的位置不被表达式约束时，则称 x在表

达式中的出现是自由出现 .

1 Lambda 演算理论

定义 3 自由变量

若变量 x在表达式 E中是自由出现，则称变量

x为表达式 E中的自由变量。

fv(E) ：表示表达式 E中的所有自由变量集。

fv(x) ={x}

fv(E1 E2) = fv(E1)  fv(E2)

fv(x.E) = fv(E) – {x}

fv((E)) = fv(E)

1 Lambda 演算理论

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

计算理论第三章Lambda演算模型Lambda演算理论AlonzoChurch1936年给出lambda演算Lambda演算理论是一个形式系统，同Turing机一样可作为计算模型。Lambda演算理论是函数式语言的基础，也是指称语义学的理论基础。主要内容：纯Lambda演算理论纯Lambda演算实例纯Lambda演算的扩展Lambda演算理论Lambda演算形式系统主要有两部分：表达式的形式系统变换规则的形式系统Lambda演算理论纯Lambda表达式形式：主要由变量名和抽象符号、“.”以及括号等符号构成。用E表示表达式，Exp表示表达式之集，Exp定义如下：x...

展开>> 收起<<

计算理论计算理论3章 Lambda演算模型.pptx

共38页,预览8页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

计算理论计算理论3章 Lambda演算模型

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: