基于C语言实现的SML简单程序设计【100013046】

# 1 目标与选题动机 ## 1.1 目标 课程中总共安排了三次实验，实验目标和具体验证的知识点如下： ### 1.1.1 第一次实验 实验的总体目标是： （1）熟悉SML/NJ开发环境及使用； （2）掌握SML基本语法和书写规则； （3）SML简单程序设计和程序编写 具体的，实验中验证的知识点包括： （1）SML是强类型语言，不同数据类型不可以进行运算； （2）字符串类型没有+操作符，要用^操作符拼接； （3）形如x = 1的表达式不是给x赋值，而是一个布尔值； （4）要使用变量前需先进行绑定； （5）元组中元素数据类型可以不同，列表中元素数据类型必须相同； （6）掌握函数的递归写法和对列表的处理； （7）掌握基本的模式匹配和临界情况处理； （8）函数之间可以相互调用。 ### 1.1.2 第二次实验 实验的总体目标是： （1）掌握list结构的ML编程方法和程序性能分析方法； （2）掌握基于树结构的ML编程方法和程序性能分析方法。 具体的，实验中验证的知识点包括： （1）与list相关的运算符的使用，比如::符号是取表中元素，@符号是表的拼接； （2）作用域限定let-in-end的使用，在let之后in之前赋值的变量只在in之后end之前有效； （3）掌握递归函数结构的分析，并能够通过判断运行次数来确定时间复杂度； （4）掌握list结构的遍历、插入排序和归并排序算法； （5）掌握tree结构的遍历、插入排序和归并排序算法； （6）掌握使用datatype进行树结点类型定义； （7）掌握包含并行递归过程的函数的性能分析，从work和span两个角度分析； （8）掌握二分搜索算法的实现。 ### 1.1.3 第三次实验 实验的总体目标是： （1）掌握多态类型、option类型和高阶函数的编程方法； （2）用ML语言求解实际问题。 具体的，实验中验证的知识点包括： （1）高阶函数，将函数作为参数传递； （2）对列表中所有元素使用同一函数进行作用的mapList函数； （3）掌握用高阶函数实现mapList的方法； （4）掌握用柯里化函数实现mapList的方法； （5）掌握将数据包装为option类型的方法； （6）掌握找零问题的解决方法，并利用找零问题的思路求解类似问题。 ## 1.2 选题动机 本次报告选取的两个主题方向分别是： （1）函数式编程语言的家族成员及其简介； （2）函数式编程的特点。 首先，选择调查和总结函数式编程语言的家族成员体系的原因是，我认为一种编程思想要代入实践就必须有这种思想的载体，而函数式编程语言恰恰就是将函数式编程引入实践的载体。因为语言是用来描述思想的工具，所以通过语言的发展可以看到函数式编程的发展，通过语言的特性也可以看到函数式编程的特性。此外，语言的发展是多元化的，除了在课程中学习的Standard ML之外，还有许多不同的函数式编程语言。例如函数式编程语言的理论基础基本都是λ演算，而后出现了以Lisp为代表的动态类型的函数式编程语言，以及以ML为代表的静态类型的函数式编程语言，以Lisp和ML为源头又各有许多方言，形成各自的家族体系。这么多的函数式编程语言的关系错综复杂，从这个角度来说，我也认为有必要对它们进行梳理。 然后，选择调查和总结函数式编程的特点的原因是，我在课程学习的过程中，一开始非常不习惯和不理解函数式编程的一些特性，一直使用命令式的思维去理解，感觉很多特性是“反人类”的，比如无法对list进行下标操作、没有循环结构、不能随意使用变量保存状态等。但随着学习的深入，逐渐可以理解这些特性在函数式编程中发挥的作用。在整个课程学习完之后，我认为有必要对这些有趣的特性进行一个总结，巩固自己对函数式编程思想的理解。 下面的第二章将围绕函数式编程语言的家族成员及其简介这一主题展开，主要根据静态类型和动态类型对函数式编程语言进行划分，并对一些较为主流的函数式编程语言的诞生、特点以及和其他语言之间的联系进行简要介绍。 下面的第三章将围绕函数式编程语言的特点展开，主要包括函数是第一等公民、多态类型、高阶函数、柯里化、无副作用、“无状态”和递归这些特点的介绍和举例。在介绍特点时会以课程中所学习的Standard ML语言为例，结合具体代码进行特点的分析，并会介绍这些特点所带来的一些好处。 # 2 函数式编程语言的家族成员及其简介 本章主要探讨函数式编程语言的分类，以及介绍各类型函数式编程语言中具有代表性的家族成员。 按照一般思路，可以从强类型/弱类型，静态类型/动态类型这两个维度来对函数式编程语言进行分类。但是我经过了解之后发现绝大多数的主流函数式编程语言均采用强类型的设计。弱类型的函数式编程语言不具有主流地位，例如法国数学家David Madore于1999年设计的Unlambda语言，由s、k、i三个符号（组合子）完成基本操作，语言形式非常有趣，但实际应用中很少使用。 因此下文所描述的较为主流的函数式编程语言均为强类型语言，下面主要按照静态类型和动态类型对它们进行分类介绍。同一类型中按照诞生年份的前后进行排序。 ## 2.1 静态类型的函数式编程语言 静态类型的语言指的是在运行之前的编译阶段就进行类型检查，并确定变量的数据类型的一类语言。静态类型的较为主流的函数式编程语言如下。 ### 2.1.1 ML ML(Meta Language)由爱丁堡大学的Robin Milner等人在二十世纪七十年代晚期开发。ML并非纯函数式编程语言，因为它在一定程度上允许副作用和进行指令式的编程。同时ML具有函数式语言常有的惰性求值的策略，也具有多态、模式匹配、高阶、递归等特点。 ML具有非常好的灵活性，表达式的值可以是函数，这个值可以作为其他函数的参数，也可以作为其他函数的返回值。这个特点在本次课程学习Standard ML语言时，尤其在学习高阶、多态和柯里化等特性时体现非常明显。 目前ML语言家族具有两个较大的分支，一个是我们课程中所学的Standard ML（标准ML），另一个是Caml。本次课程中使用的是Standard ML最著名的编译器Standard ML New Jersey（SML/NJ）。Caml的具体实现是Ocaml语言，详见本节的第2.1.4小节的介绍。 ### 2.1.2 Miranda Miranda是由英国学者大卫·特纳（David Turner）所设计的纯函数式编程语言，其同样具有惰性求值特点，并遵循函数式编程语言的全部要求。 Miranda语言于1985年发表，配套发布了一个C语言编写的编译器，可以在Linux、Unix系统上运行，之后再1987年和1989年发布了更新。 这门语言部分采用了来自ML语言的设计，并为后续发展出的Haskell语言提供了很多新的理念。 ### 2.1.3 Haskell Haskell是于1990年在Miranda语言的基础上进行标准化的，它的理论基础也是λ演算。Haskell的命名来源于美国逻辑学家哈斯凯尔·加里，他在数理逻辑方面的工作很有造诣。  值得一提的是Haskell的标志，如下图所示： 图2.1 Haskell语言标志 图中的标志构成一个字母λ的样子，就是为了致敬λ演算这一套基于数学的形式系统。 Haskell和前面提到的Miranda�