函数程序设计语言--计算机模型、编译技术、系统结构

出版者:清华大学出版社

作者:郑纬民

页数:261

出版时间:1997-11

价格:20.00

装帧:平装

isbn号码:9787302022343

具体描述

内容简介

本书详细论述了函数程序设计语言的计算模型、编译技术以及面向函数程序设计语言的系统结构。其

主要内容包括：函数程序设计语言，λ演算，函数语言的归约计算方法，函数语言的图重写计算模型，图重

写计算模型描述语言CIL，多态类型及类型检查，自由变量的清除与优化组合子，惰性模式匹配及编译方

法，严格性分析方法，编译时粒度分析及估算方法，存储管理及垃圾单元回收，多机并行图重写执行模型

HPGREM，并行抽象机PAM/TGR及体系结构等。

本书适合于从事计算机系统结构、信息处理、并行处理技术研究的科技人员阅读，也可作为计算机等

专业的研究生和高年级本科生的教材和教学参考书。

作者简介

郑纬民 男，1946年生，浙江宁波人。1970年毕业于清华大学自

动控制系并留校任教。1982年在清华大学计算机系获硕士学位。现为清

华大学计算机系教授、博士生导师。1985年至1986年曾在纽纸头州立大

学石溪分校从事分布操作系统研究。1989年至1991年曾在英国南安普

敦大学参加函数语言并行编译系统的研究。

郑纬民多年来一直从事并行处理与分布计算机系统、面向AI体系结构以及说明性语

言的编译方法和程序开发环境等教学和研究工作，取得了―系列成果。近几年来，参加或

负责的国家攻关、863计划和自然科学基金项目有“THUDS分布计算机”、“并行图归

纳智能工作站”、“军用软件开发新技术”、“可扩展并行机群系统”等10余项。研究成

果达到了国际先进水平或国内领先水平，多次获得国家教委科技进步奖。近几年来，在国

内外学术刊物和学术会议上发表论文80余篇。著作有《计算机系统结构）和《函数语言

及其实现技术》等

目录信息

目录
第1章 引论
1.1 函数式程序设计语言
1.1.1 APL语言
1.1.2 FP语言
1.1.3 ML语言
1.1.4 Lisp语言
1.1.5 SASL，KRC和Miranda语言
1.1.6 Haskel1语言
1.1.7 其它的函数语言
1.2 函数语言的基本特征和实现论题
1.2.1 函数语言的基本特征
1.2.2 程序的执行效率
1.2.3 主要实现论题
1.3 函数语言的图重写实现技术
1.4 本章小结
第2章 函数式程序设计语言
2.1 函数语言的特点
2.1.1 变量名和值
2.1.2 执行顺序
2.1.3 循环和递归
2.1.4 数据结构
2.1.5 函数作为值
2.2 ML语言简介
2.2.1 ML的特点
2.2.2 类型
2.2.3 几点说明
2.3 SML标准类型
2.3.1 基本类型
2.3.2 表类型
2.3.3 元组类型
2.3.4 函数的类型和表达式
2.4 sML标准函数
2.4.1 标准布尔型函数
2.4.2 标准算术运算函数和运算符的重载
2.4.3 标准字符串函数
2.4.4 标准表函数
2.4.5 字符、字符串和表
2.4.6 比较运算符
2.5 SML函数定义
2.5.1 函数
2.5.2 约束变量的类型
2.5.3 定义
2.5.4 条件表达式
2.5.5 递归和函数定义
2.5.6 访问元组约束变量中的元素
2.5.7 模式匹配
2.5.8 局部定义
2.6 SML类型
2.6.1 类型表达式和类型缩写（abbreviatedtypes）
2.6.2 类型变量和多态性
2.6.3 定义新类型
2.6.4 抽象数据类型
2.6.5 树
2.7 本章小结
第3章 λ演算
3.1 λ演算的基本概念和定义
3.2 λ演算的归约
3.3 递归定义
3.4 纯λ演算中的算术
3.5 本章小结
第4章 函数语言的归约计算方法
4.1 归约计算的语义
4.2 正规序归约的语用
4.2.1 串归约（stringreduction）
4.2.2 标准环境归约（standardenvironmentreduction）
4.2.3 图归约（graphreducti0n）
4.2.4 全惰性图归约（fulllazygraphreduction）
4.2.5 惰性图归约（1azygraphreduction）
4.2.6 图归约的特点
4.3 组合子图归约（c0mbinator－basedgraphreduction）
4.3.1 基本思想
4.3.2 组合子及其性质
4.3.3 超组合子性质
4.4 本章小结
第5章 函数语言的图重写计算模型
5.1 计算对象的描述形式
5.2 计算的操作方式
5.3 计算的控制方式
5.3.1 并行性开发策略
5.3.2 并行计算的控制管理方法
5.3.3 并行计算任务的粒度（granularity）
5.4 本章小结
第6章 编译中间语言
6.1 中间语言的基本概念
6.2 CIL程序的基本描述形式
6.3 CIL程序例子
6.4 CIL程序执行算法
6.5 CIL语言对函数式程序的支持
6.5.1 TermL模式结构的转换
6.5.2 非平坦TermL的转换
6.5.3 标记TermR
6.6 本章小结
第7章 多态类型及类型检查
7.1 多态类型
7.2 程序的表示
7.3 类型推导与类型合一
7.4 类型变量与环境
7.5 类型推导算法
7.5.1 类型推导算法中用到的函数
7.5.2 类型推导算法
7.6 本章小结
第8章 自由变量的消除与优化组合子
8.1 λ－提升
8.1.1 λ－提升方法
8.1.2 λ－提升方法的评价
8.2 最大自由表达式（mfe）抽取
8.2.1 mfe抽取算法
8.2.2 最大自由表达式抽取方法的分析
8.3 函数部分作用共享分析
8.3.1 部分作用的共享及其表示
8.3.2 共享分析方法
8.4 优化组合子生成方法
8.5 本章小结
第9章 惰性模式匹配及其编译方法
9.1 模式与模式匹配
9.2 最小扩展模式与模式匹配树
9.2.1 模式匹配谓词及其性质
9.2.2 惰性模式匹配算法的存在性与最小扩展模式
9.2.3 MEPⅡ的生成和匹配树的构造
9.3 模式的平坦化和参量一致化变换
9.3.1 两个简单的转换方法及其效率
9.3.2 重写规则的生成方法
9.4 本章小结
第10章 惰性函数语言程序严格性分析方法
10.1 抽象解释和严格性分析方法
10.1.1 基于抽象解释的严格性分析方法
10.1.2 严格性分析与函数程序的并行性开发
10.1.3 惰性计算方式和结构数据的计算
10.2 投影分析分析方法
10.2.1 投影和计算的描述
10.2.2 基于投影分析的严格性分析方法
10.2.3 举例
10.3 并行性开发方法的优化
10.3.1 算子
10.3.2 并行性开发方法
10.4 本章小结
第11章 编译时粒度分析及估算方法
11.1 现状与问题
11.2 K0zen语义与分布函数
11.3 分布函数与程序粒度的关系
11.4 程序粒度分析的系统化方法
11.5 细粒度任务的收拢（coalescing）原理
11.6 任务颗粒的分类及合并
11.7 引入启发因素的编译时粒度分析算法HCGA
11.8 实验及与相关工作的比较
11.9 本章小结
第12章 存储管理及垃圾单元回收
12.1 概述
12.2 Ash0ke的改进引用计数法
12.2.1 Ashoke算法
12.2.2 Ashoke算法的正确性证明
12.2.3 并行环境中的Ash0ke算法实现
12.3 基于引用计数的垃圾回收技术
12.3.1 经典的引用计数法
12.3.2 ARVIND/THOMAS的带权引用计数法
12.3.3 垃圾单元回收的惰性方法
12.3.4 带权的垃圾单元惰性回收方法
12.4 FL/TBD/TBC/CRC与CM分立的垃圾回收开销分析
12.5 FL/TBD/TBC/CRC与CM混合的垃圾回收开销分析
12.6 并行系统中的垃圾单元回收
12.7 本章小结
第13章 多相并行图重写执行模型HPGREM
13.1 并行执行模型的研究现状
13.2 HPGREM的形式化描述
13.2.1 基本定义
13.2.2 形式化描述
13.3 存储管理及执行环境组织
13.4 并行性开发策略
13.4.1 并行性开发
13.4.2 任务分布的Lazy－Eager原理
13.4.3 基于LEDT原理的任务分布算法
13.5 并行执行模型HPGREM的多相性质
13.6 本章小结
第14章 并行抽象机PAM/TGR及体系结构
14.1 概述
14.2 存储器组织及数据表示
14.2.1 存储器组织
14.2.2 图结点及数据表示
14.3 并行抽象机PAM/TGR的指令系统
14.3.1 并行抽象机指令集
14.3.2 抽象机的寻址方式
14.3.3 并行抽象机PAM/TGR的优化编译器
14.4 并行抽象机的指令执行算法
14.4.1 环境生成指令（push）执行算法
14.4.2 环境拷贝指令（copy）执行算法
14.4.3 重写指令（grew）执行算法
14.4.4 重写任务的管理指令（take，mask，sndt，recy）执行算法
14.4.5 调用基元操作与存储管理指令（call，flsh）执行算法
14.5 并行抽象机PAM/TGR的体系结构
14.6 并行抽象机PAM/TGR的性能评价
14.6.1 基于Benchmark的PAM/TGR性能测试
14.6.2 与相关系统的性能比较
14.7 本章小结
参考文献
· · · · · · (收起)

用户评价

这本书的内容深度着实令人惊叹，尤其是在“函数式语言的数学基础”这一章节，彻底刷新了我对编程语言底层逻辑的认知。我一直认为编程是一种“如何做”的艺术，而这本书则将我引向了“为何如此”的哲学思考。作者从集合论、范畴论等数学分支引入，详细阐述了函数式编程的理论根基，例如 Curry-Howard同构，它将逻辑命题与程序类型巧妙地联系起来，让我看到了程序不仅仅是指令的集合，更是数学证明的另一种形式。 书中对于“代数数据类型”的讲解更是让我耳目一新，它揭示了如何通过组合简单的基本类型来构建复杂的、具有强大表达能力的结构，这与我之前接触的面向对象语言中的类继承和多态有着截然不同的思路。作者还深入探讨了“类型系统”的强大之处，例如如何通过强大的类型约束来在编译时捕获大量的错误，从而提高程序的可靠性和健壮性。这种从数学层面理解编程的方式，让我受益匪浅，也让我对函数式编程语言的优雅和严谨性有了更深刻的理解。

接着，《函数程序设计语言》在“编译技术”部分展现了其强大的实用价值。我一直对编译器的工作原理感到好奇，特别是如何将高级语言转化为机器可执行的代码。这本书在这方面的内容可谓是淋漓尽致。它详细讲解了函数式语言编译过程中特有的挑战，例如如何处理惰性求值、如何进行函数柯里化和部分应用优化。书中对于抽象语法树（AST）的构建、中间代码生成、以及各种优化策略的介绍，都非常有条理。 我特别着迷于书中关于“图归约”（graph reduction）的讲解，这是一种在处理惰性求值函数式语言时非常重要的求值策略。作者通过生动的图示和代码示例，清晰地展示了计算的逐步展开过程，让我能直观地理解“按需计算”的精髓。此外，书中对于类型推导、垃圾回收机制的深入探讨，也让我对函数式语言的内存管理和安全性有了更深的认识。对于那些想要深入了解编译器内部运作，或者希望设计、实现自己的编程语言的读者来说，这部分的知识绝对是宝贵的财富，它不仅仅是理论的堆砌，更是实践的指导。

在阅读《函数程序设计语言》的过程中，我被书中对于“求值策略”的细致分析深深吸引。我一直习惯于命令式语言中的“即时求值”模式，而函数式语言中引入的“惰性求值”（lazy evaluation）和“严格求值”（strict evaluation）则为我打开了新的视角。作者用大量的实例和图示，将惰性求值的“按需计算”原理剖析得淋漓尽致，让我明白了它在处理无限数据结构、提高程序效率方面的重要作用。 书中还详细比较了不同求值策略的优缺点，以及它们对程序性能、内存消耗的影响。我尤其对书中关于“好悖论”（the paradox of the good）的讨论印象深刻，它解释了惰性求值在某些情况下如何导致意想不到的行为，以及如何通过理解求值策略来避免这些问题。此外，书中还深入探讨了“记忆化”（memoization）技术，以及它如何与惰性求值结合，进一步优化程序的性能。这种对程序执行细节的深入剖析，让我能够更精准地控制程序的行为，写出更高效、更优化的代码。

这本书的“类型系统”部分，绝对是其最令人瞩目的亮点之一。我之前接触的编程语言，其类型系统往往是相对简单的，而这本书则将类型系统提升到了一个前所未有的高度。作者深入探讨了“Hindley-Milner类型推导”等高级类型推导算法，让我明白了编译器是如何在无需显式类型注解的情况下，自动推导出程序的类型，从而保证程序的正确性。 我尤其对书中关于“多态性”（polymorphism）的深入讲解印象深刻，包括“参数多态”（parametric polymorphism）和“ ad hoc 多态”（ad hoc polymorphism）。作者通过丰富的例子，展示了多态性如何提高代码的复用性和灵活性，而又不牺牲类型安全。此外，书中还探讨了“依赖类型”（dependent types）等更高级的类型理论，虽然这部分内容相对更抽象，但它展示了类型系统在形式化验证程序正确性方面的巨大潜力。这种对类型系统的深刻理解，让我意识到类型不仅仅是为了防止编译错误，更是表达程序逻辑、保证程序健壮性的强大工具。

《函数程序设计语言》的“系统结构”部分，则将理论和编译技术提升到了一个新的高度，探讨了函数式语言在实际系统中的应用和影响。我一直对如何将函数式编程的优点（如并发性、可维护性）融入到大型复杂系统中感到兴趣，这本书恰好满足了我的这一需求。书中详细分析了函数式语言在并行计算、分布式系统中的优势，以及如何利用其不可变性和纯函数的特性来简化并发编程的难度，避免竞态条件和死锁等常见问题。 我尤其喜欢书中关于“并发模型”的讨论，例如 Actor模型、CSP（Communicating Sequential Processes）等，以及这些模型如何与函数式编程范式相结合。作者还探讨了函数式语言的内存模型和垃圾回收机制如何影响系统的性能和可伸缩性，以及如何设计高效的运行时环境。此外，书中还涉及了函数式语言在特定领域的应用，比如在人工智能、数据科学、Web开发等方面的实践案例，这让我看到了函数式编程不仅仅是一种理论上的优雅，更是一种在现实世界中解决复杂问题的强大工具。

《函数程序设计语言》在“函数式编程与软件工程”的结合，是让我倍感兴奋的部分。我一直认为，编程语言的选择对软件开发的效率、质量和可维护性有着至关重要的影响。这本书让我看到了函数式编程如何能够从根本上提升软件工程的实践水平。作者详细阐述了函数式语言的“纯函数”和“不可变性”如何能够极大地简化代码的理解和调试，以及如何降低引入bug的风险。 书中关于“函数组合”（function composition）和“高阶函数”（higher-order functions）的运用，为我展示了如何构建高度模块化、易于测试和复用的代码。我尤其对书中关于“函数式反应式编程”（Functional Reactive Programming, FRP）的介绍印象深刻，它提供了一种声明式的方式来处理随时间变化的数据流，这在处理用户界面、实时系统等场景下非常有价值。此外，书中还探讨了函数式编程如何促进“测试驱动开发”（Test-Driven Development, TDD）和“持续集成”（Continuous Integration, CI）等现代软件工程实践。这种将函数式编程的理论优势转化为实际工程效益的分析，让我对函数式编程在实际项目中的应用前景充满了信心。

《函数程序设计语言》对于“函数式编程的实现”的探讨，给了我非常深入的认识，它不仅仅是理论上的讲解，更是将抽象概念转化为实际可运行代码的过程。我一直对编译器是如何将高级函数式语言转换为低级机器码感到好奇，这本书在这方面的内容让我大开眼界。作者详细讲解了函数式语言编译过程中所面临的各种挑战，比如如何高效地处理“闭包”（closures）、如何进行“柯里化”（currying）和“部分应用”（partial application）的优化。 书中对于“图归约”（graph reduction）和“标记-清除式垃圾回收”（mark-and-sweep garbage collection）等关键技术的深入剖析，让我得以窥见函数式语言运行时环境的复杂性。我特别对书中关于“代码生成”的讲解印象深刻，作者如何将函数式语言的特性转化为高效的机器指令，以及如何进行各种“编译器优化”（compiler optimizations），比如“内联”（inlining）、“死代码消除”（dead code elimination）等。这种对实现细节的深入理解，不仅让我对函数式语言的性能有了更直观的认识，也让我对编译器设计本身产生了浓厚的兴趣。

这本书在“模式匹配”（pattern matching）和“代数数据类型”（algebraic data types）方面的讲解，为我打开了全新的编程思路。我之前习惯于使用大量的if-else语句和switch-case来处理不同的数据情况，而模式匹配提供了一种更加声明式、更加优雅的方式。作者详细阐述了如何通过模式匹配来解构复杂的数据结构，以及如何将不同的处理逻辑与特定的数据模式关联起来。 我尤其对书中关于“代数数据类型”的介绍印象深刻。它展示了如何通过组合简单的基本类型来构建复杂、具有丰富表达能力的类型，例如使用“代数和类型”（sum types）来表示枚举，使用“代数积类型”（product types）来表示记录。这种数据建模方式，与我之前习惯的面向对象语言中的类继承和组合有着显著的区别，它更加强调数据的结构和不变性。通过模式匹配和代数数据类型，我能够以一种更直观、更安全的方式来处理数据，大大降低了出错的可能性。

《函数程序设计语言》在“并发与并行编程”方面的论述，可以说是我近年来读到过的关于这一主题最深刻、最系统的讲解之一。我一直觉得并发编程是软件开发中最具挑战性的领域之一，充满了各种陷阱和难以调试的问题。而这本书则提供了一种全新的、更加优雅的解决思路。作者将函数式编程的“纯函数”和“不可变性”作为并发编程的基石，解释了它们如何能够天然地避免共享状态带来的竞争条件和死锁。 书中详细介绍了各种基于函数式范式的并发模型，例如“消息传递模型”（message passing）、“Actor模型”以及“软件事务内存”（Software Transactional Memory）。我尤其对书中关于“并发抽象”的讨论印象深刻，作者是如何通过高阶函数和组合子来构建强大而灵活的并发抽象，从而让开发者能够以更高级、更声明式的方式编写并发程序。书中还深入探讨了如何利用函数式语言的特点来处理并行计算中的数据划分、任务调度和结果聚合等问题。这种从根本上解决并发难题的方法，让我看到了函数式编程在构建大规模、高可靠性系统中的巨大潜力。

初次翻开这本书，就被其厚重与严谨的学术气息所吸引。这本书的封面设计相当朴实，没有花哨的插图，只有书名和作者姓名，这种极简风格反而传递出一种“内涵至上”的信号，让我对即将深入的知识领域充满了期待。我原本对函数式编程语言的认识仅限于一些零散的概念，比如不可变性、高阶函数等，但这本书就像一座巨大的知识宝库，系统地、深入地为我打开了函数式编程的世界。 首先，它在“计算机模型”部分就奠定了坚实的理论基础。我尤其对书中对lambda演算的详细阐述印象深刻，这不仅仅是理论上的探讨，更是对函数式编程语言底层数学逻辑的深刻剖析。作者用大量的篇幅解释了lambda演算如何能够表达一切可计算的函数，以及与之相关的Church-Rosser定理等，这些理论对于理解函数式语言的计算模型至关重要。书中关于递归、不动点理论的讲解也十分透彻，让我明白了函数式语言中循环是如何被优雅地替代的。更令我惊喜的是，作者并没有止步于理论，而是通过具体的例子，将抽象的数学概念与实际的编程实践联系起来，比如如何用lambda演算来模拟数据结构，如何构建基本的算术运算。这种从根本上理解计算本质的方式，彻底颠覆了我之前对编程的许多直观认识。