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

资源下载地址：https://download.csdn.net/download/sheziqiong/85896108
资源下载地址：https://download.csdn.net/download/sheziqiong/85896108
目录
1 目标与选题动机 3
1.1 目标 3
1.1.1 第一次实验 3
1.1.2 第二次实验 3
1.1.3 第三次实验 4
1.2 选题动机 4
2 函数式编程语言的家族成员及其简介 6
2.1 静态类型的函数式编程语言 6
2.1.1 ML 6
2.1.2 Miranda 7
2.1.3 Haskell 7
2.1.4 OCaml 8
2.1.5 Scala 9
2.1.6 F# 9
2.2 动态类型的函数式编程语言 10
2.2.1 Lisp 10
2.2.2 Scheme 11
2.2.3 Clojure 11
2.2.4 Erlang 12
3 函数式编程的特点 14
3.1 函数是第一等公民 14
3.2 多态类型 15
3.3 高阶函数 16
3.4 柯里化 17
3.5 无副作用 18
3.6 “无状态”和递归 19
4 心得收获与建议 21
4.1 课程收获 21
4.2 建议 21

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语言为例，结合具体代码进行特点的分析，并会介绍这些特点所带来的一些好处。
3函数式编程的特点
本章主要探讨函数式编程的一些突出特点，每个小节将讨论一个特点，并会以我们课程所学的Standard ML语言为例进行具体描述。
3.1函数是第一等公民
第一等公民（first-class values）指的是具有和其他数据类型一样的平等地位。不同等次（class）类型的地位如下表2.1所示：
表2.1 不同等次类型的地位
等次 地位
First Class 可作为函数参数、可返回，可赋值给其他变量
Second Class 可作为函数参数、不可返回、不可赋值给其他变量
Third Class 不可作为函数参数、不可返回、不可赋值给其他变量
函数作为第一等公民，可以赋值给其他变量，也可以作为参数传入另一个函数，或者作为别的函数的返回值。函数与其他数据类型一样，处于平等的地位，这就意味着函数与程序和过程之间没有区别，函数可以看作数据来进行使用。
下面使用standard ML语言的语法举三个例子来说明函数作为第一等公民的特性。
（1）作为函数参数
(* thenAddOne: ((int->int)*int)->int )
fun thenAddOne (f, x) = f x + 1;
上例中的thenAddOne函数的参数中就包含了另一个函数f，函数功能是将参数x使用函数f映射之后的值再加1。
（2）作为返回值
( mapList’: ('a->'b)->('a list->'b list) )
fun mapList’ f =
fn L => case L of
[] => []
| x::R => (f x)::(mapList’ f R);
上例中的mapList’函数接受一个函数f作为参数，返回一个将f作用到列表中每一个元素的函数。
（3）赋值给其他变量
( addOne: int->int )
fun addOne x = x + 1;
( 赋值给copyFun )
val copyFun = addOne;
上例中函数addOne的功能是将整型x的值加1之后返回。赋值语句”val copyFun = addOne;”将addOne函数的职能赋给了copyFun，此时copyFun x的函数功能与addOne x一致。
3.2多态类型
多态的含义是多种形态，指的是在类型推导过程中一些无约束的类型。多态类型是一个类型模式，用一个具体的类型去匹配这样一个类型模式，就可以将多态的类型模式实例化为一个具体的类型。
在standard ML语法中，多态类型在类型推导中使用单引号+小写字母的形式来代指。具体而言，在类型推导中出现的第一个多态类型为’a，第二个为’b，以此类推……如下图2.1所示：
图2.1 多态类型举例
在上例中，函数f的参数x、y、z在类型推导时无法确定，因此被认为是多态类型，但x、y、z的具体类型可以不同，因此使用不同的小写字母进行区分，类型分别为’a、’b、’c。
使用语句f( 1, 3.14, “hello”)对上例中的多态类型进行实例化，如下图2.2所示。
图2.2 多态类型实例化
在上例中，x值为1，类型为int；y值为3.14，类型为real；z值为”hello”，类型为string，这是将多态类型’a、’b、’c分别实例化得到的结果。
函数式编程中引入多态类型，可以避免写很多多余的代码，同时便于维护。因为不需要对每一种类型都编写一个对应的函数，只需要利用多态类型，在实际匹配时将多态类型实例化为所需的数据类型即可，需要维护的函数也就只有一个，不需要过多考虑类型问题。
3.3高阶函数
高阶函数可以使用另一个函数作为其输入参数，也可以返回一个函数。如果说上一节中的多态特性是为了简化多个类型的相同操作，那么高阶函数特性则是简化了多个参数的函数操作，也简化了同类型批量数据的不同函数操作。
具体来说，有了高阶函数之后，可以通过内部的一个函数把所有的参数处理完之后得到一个中间结果，再把这个中间结果作为变量传递给上一级函数。比如需要对一个整型列表中的全部元素进行递增、翻倍和平方这三种不同的操作，可以使用下面三个单独的函数：
( addList: int list->int list *)
fun addList [ ] = [ ]
| addList (x::L) = (x+1) :: addList L;

(* doubleList: int list->int list )
fun doubleList [ ] = [ ]
| doubleList (x::L) = (x2) :: doubleList L;

(* sqList: int list->int list )
fun sqList [ ] = [ ]
| sqList (x::L) = (xx) :: sqList L;
上例中的三个函数addList、doubleList、sqList分别实现了对列表中所有元素的加1、乘2和平方操作。但是经过观察可以发现上述三个函数的结构都是类似的，都是对每个元素的操作，只是操作的类型不同。根据这个思想可以使用高阶函数的概念，把这个不同类型的操作抽象成对单个元素的函数f，把f作为参数传递到高阶函数中，对列表中的每一个元素都使用函数f进行映射，如下例中mapList函数所示：
(* mapList: (('a->'b)*'a list)->'b list )
fun mapList(f, [ ]) = [ ]
| mapList(f, x::L) = (f x)::mapList(f, L);
有了mapList这个高阶函数之后，只需要实现int->int类型的加1、乘2和平方函数，然后再将对应的函数作为参数送入mapList函数中，对抽象的函数f进行具体化，就可以灵活实现对列表中所有元素进行同一操作。
3.4柯里化
当一个函数面临接收的参数数量不止一个时，对多个参数有两种处理方法，一种是把多个参数当成一个元组，第二种则是接收第一个参数，然后随即返回一个函数，这个函数可以接收第二个参数，以此类推直到所有参数被接收。第二种方式的函数就是柯里函数，柯里化也就是把接收多参数的函数转变为接收单一参数（第一个参数），并返回一个能够接收后续参数的函数的技术。
举例而言，一个2参数的函数使用第一种方式进行处理时定义为(a * b) -> t类型，它是一个作用于元组的单参数函数。而使用第二种方式进行处理时则定义为a -> (b -> t)，它是一个柯里函数，其接收第一个参数a，返回一个能够接收参数b的函数。
下面是一个代码示例：
( toBase: int -> int -> int list )
( REQUIRE: n为10进制，且n>=0,b>1 )
( ENSURE: toBase b n 将十进制数n转换为b进制数的int list形式 *)
fun toBase b 0 = []
| toBase b n =
let
val (r,q) = (n mod b, n div b)
in
r::(toBase b q)
end;
在这个例子中toBase函数接受一个参数b，返回一个接收参数n并将十进制数n转换为b进制数的int list形式的函数。
函数的柯里化有以下优点：首先可以提高函数的适用范围，其次由于是逐个接收参数逐个累积，最后才进行执行，具有延迟执行的特性，最后可以提前把易变因素确定下来，减少了后续生成函数的复杂程度，易于理解和设计函数。
3.5无副作用
副作用指的是函数内部和外部进行互动，产生了运算之外的其他结果。比如说，在函数内部修改了全局变量的值。副作用在命令式编程中非常常见，比如下面的C语言代码：
int a = 0;
int func(int b) {
a = a + b;
return a;
}
int main( ) {
int b = 1;
return func(b);;
}
在上面的例子中，main函数调用func函数。func函数接收整型参数b，功能是将全局变量a的值增加b，并返回修改后的a值。显然这个例子中的func函数是具有副作用的，它修改了全局变量a的值。调用func函数结束后a的值将变为1。
再看函数式编程的例子，以Standard ML语言为例，代码如下：
val a = 0;
fun func b = a + b;
func 1;
a;
上例中func函数的功能和C代码相同，将a的值增加b后返回，但区别是完全没有副作用。当调用func 1后函数正确返回1，但a的值仍然为0，如图2.3所示。

图2.3 调用函数func后a的值不变
无副作用的特点保持了函数的独立性，函数不依赖于外部的状态，也不会修改外部的状态。有了无副作用的特性，使得函数的单元测试和整个程序的调试都更加简单。
3.6“无状态”和递归
在命令式编程中，程序是具有状态的，程序的一个运行状态包括各个寄存器的值、所申请的内存空间的位置、大小和其中的数值等等信息。但在函数式编程中强调无状态，无需将状态保存在变量中，而是将状态锁定在函数内部，不依赖任何外部状态。也就是在函数式编程中是通过函数创建新的参数或者返回值，通过这些参数和返回值来保存状态的。在函数式编程中并非真正的无状态，而是将状态完全存放在栈中，对状态的读取和修改是通过一层层函数调用中，利用函数的参数和返回值进行传递。
这样的机制使得函数式编程天生就具有递归特性。函数式编程中没有循环语句，因为循环需要使用变量保存状态来进行控制，取而代之的形式就是递归。如果要遍历一个列表，在函数式编程中就是每次取用列表的首元素，然后对剩余列表使用该函数的递归调用，Standard ML描述的代码样例如下：
(* max: int list->int *)
fun max [ ] = 0
| max (x::L) =
let
val y = max L
in
if x > y then x else y
end;
函数max的功能是遍历一个元素均为自然数的整型列表中所有元素并找出最大值。可以看到整个函数结构是先用模式匹配取出列表的首元素，然后再递归调用max函数找到剩余列表元素中的最大值，与当前首元素进行比较，选取较大值作为返回值。这是一个典型的递归思路，递归求解问题可以将问题简单化，只需要完善地考虑问题的一个子问题。
由于在函数式编程中所有的计算都是静态的，所以在递归过程中并没有函数“调用”的概念，编译器会默认所有的递归函数是已知的，结合惰性求值的特点，使得中间开销并不大，程序的性能有所保证。
资源下载地址：https://download.csdn.net/download/sheziqiong/85896108
资源下载地址：https://download.csdn.net/download/sheziqiong/85896108