用ML编写正确的程序MLProgrammingCorrectly

1、用ML编写正确的程序ML Programming Correctly汪旻51103790361函数式程序设计过程式语言面向命令，函数式语言面向表达式函数式语言避免繁琐的内存管理函数式语言要求写出可靠正确的程序函数式语言的几个概念函数，递归，模式匹配，多态类型检测，高阶函数，无穷数据结构，惰性求值2ML与纯函数式编程语言的区别ML是非纯函数式语言热情求值没有无穷数据结构模块多态类型检测异常处理简单的IO指令3ML的诞生ML(Meta-Language) 是一个通用的函数式编程语言，它是由爱丁堡大学的Robin Milner在二十世纪七十年代晚期开发的，现在流行的方言有Standard ML和Ca

2、ml.启发语言：ISWIM影响语言：Miranda, Haskell, Cyclone, C+, F#, Clojure, Felix, Opa, Erlang 设计初衷：LCF定理证明机中寻找证明策略ML大多被用于语言设计和操作（编译器、分析器、定理证明机）， 但是它作为通用语言也被用于生化，金融系统，和宗谱数据库，一个P2P的客户服务器程序等等。4Level 0Hello world“Hello world!”; (*make a string*)print it; (*output it*)阶乘函数fun fac 0 = 1 | fac n = n * fac (n - 1);LV.0M

3、L Programmer猿LV.1ML ProgrammerLevel Up!5Level 1值的声明命名常量val pi = 3.14159;声明函数fun circle_area (r) = pi*r*r;标识符字母开头，允许数字、下划线、撇号!%&$#+_*/:?|6Level 1基本类型数int, real + - * div mod 负号类型约束字符串连接符#”0”和“0”真值orelse, andalso, notif E then E1 else E2- fun square x = x*x;- fun square x = x*x :real;7Level 1序偶、元组、记录序

4、偶向量(2.5 , 1.2) : real*realtype vec = real * real;记录val ZS = name=“Zhang San”, age=20, major=“CS”;#age ZS; 20 : intLV.1ML Programmer猿LV.2ML ProgrammerLevel Up!8Level 2表达式中缀操作符(infix operator)及其优先级、结合方式传值调用(add.)局部声明let . in . endlocal . in . end支持嵌套9(* Example for infix operator *)infix xor;fun (p xo

5、r q) = (p orelse q) andalso not (p andalso q);(* 中缀优先级 *)infix 7 times;(* 传值调用 *)sqr(sqr(sqr(2)=sqr(sqr(2*2)=sqr(sqr(4)=sqr(4*4)=sqr(16)=16*16=256 .zero(sqr(sqr(sqr(2)=zero(sqr(sqr(2*2)=zero(sqr(sqr(4)=zero(sqr(4*4)=zero(sqr(16)=zero(16*16)=zero(256)=010(* Example for let . in . end *)fun fraction (

6、n,d) = let val com = gcd(n,d) in (n div com, d div com) end; val fraction = fn : int * int - int * int(* Example for local . in . end *)local fun itfib (n, prev, curr) : int = if n=1 then curr else itfib (n-1, curr, prev+curr)in fun fib (n) = itfib(n, 0, 1)end; val fib = fn ; int - intLV.2ML Program

7、mer猿LV.3ML ProgrammerLevel Up!11 Level 3模块系统结构通过Conplex.zero这样的形式来访问不同结构里的标识符可以相同签名12structure Complex : ARITH = struct type t = real*real; val zero = (0.0, 0.0); fun sum (x,y), (x,y) = (x+x, y+y) : t; fun diff (x,y), (x,y) = (x-x, y-y) : t; fun prod (x,y), (x,y) = (x*x - y*y, x*y + x*y) : t; fun re

8、cip (x,y) = let val t:real = x*x + y*y in (x/t, y/t) end fun quo (z,z) = prod(z, recip z); end;signature ARITH = sig type t val zero : t val sum : t * t - t val diff : t * t - t val prod : t * t - t val quo : t * t - t end;LV.3ML Programmer猿LV.4ML ProgrammerLevel Up!13Level 4多态类型检测多态类型的声明关于算法（Damas(

9、1985)的博士论文）- fun pairself x = (x,x); val pairself = fn : a - a * afun fst (x,y) = x; val fst = fn : a * b - afun snd (x,y) = y; val snd = fn : a * b - bLV.4ML Programmer猿LV.5ML ProgrammerLevel Up!14Level 5List顺序 3, 4可重复 3, 4, 3元素类型任意 (1,”one”),(2,”two”),(3,”three”) : (int*string) list: 右结合中缀操作符cons

10、在表前加入一个元素_通配符LV.5ML Programmer猿LV.6ML ProgrammerLevel Up!15Level 6数据类型声明datatype person = King | Peer of string*string*int | Knight of string | Peasant of string;fun title King = His Majesty the King“ | title (Peer(deg,terr,_) = The deg of terr | title (Knight name) = Sir name | title (Peasant name)

11、 = name;16Level 6树节点=节点+子树or叶子datatype a tree = Lf | Br of a tree * a tree;size(tree)应用17val tree2 = Br(2, Br(1,Lf,Lf), Br(3,Lf,Lf);val tree5 = Br(5, Br(6,Lf,Lf), Br(7,Lf,Lf);val tree4 = Br(4, tree2, tree5);421356718（* make a tree *）datatype a tree = Lf | Br of a * a tree * a tree;structure Tree = s

12、tructfun size Lf = 0 | size (Br(v,t1,t2) = 1 + size t1 + size t2;fun size Lf = 0 | size (Br(v,t1,t2) = 1 + size t1 + size t2;fun depth Lf = 0 | depth (Br(v,t1,t2) = 1 + Int.max (depth t1, depth t2); fun reflect Lf = Lf | reflect (Br(v,t1,t2) = Br(v, reflect t2, reflect t1);.end;19（* 二叉查找树 *）(* Dicti

13、onaries as Binary search trees *)signature DICTIONARY = sig type key(*type of keys*) type a t(*type of tables*) exception E of key(*errors in lookup, insert*) val empty: a t(*the empty dictionary*) val lookup: a t * key - a val insert: a t * key * a - a t val update: a t * key * a - a t end;(*Struct

14、ure Order can vary; Tree avoids referring to a free structure. *)structure Dict : DICTIONARY = struct type key = string; type a t = (key * a) tree; exception E of key; val empty = Lf; 20fun lookup (Lf, b) = raise E b | lookup (Br (a,x),t1,t2), b) =(case Spare(a,b) of GREATER = lookup(t1, b) | EQUAL

15、= x | LESS = lookup(t2, b); fun insert (Lf, b, y) = Br(b,y), Lf, Lf) | insert (Br(a,x),t1,t2), b, y) =(case Spare(a,b) of GREATER = Br (a,x), insert(t1,b,y), t2) | EQUAL = raise E b | LESS = Br (a,x), t1, insert(t2,b,y); fun update (Lf, b, y) = Br(b,y), Lf, Lf) | update (Br(a,x),t1,t2), b, y) =(case

16、 Spare(a,b) of GREATER = Br (a,x), update(t1,b,y), t2) | EQUAL = Br (a,y), t1, t2) | LESS = Br (a,x), t1, update(t2,b,y); end;LV.6ML Programmer猿LV.7ML ProgrammerLevel Up!21后期升级攻略函数与算子实现惰性求值实现搜索策略函数式程序正确性的证明抽象类型（用于建立大型系统）ML中的命令式程序设计应用：LAMBDA演算解释器22总结用ML可以很容易写出清晰、可靠的程序。值得作为函数式编程的入门语言。在牺牲部分效率的情况下，提升程序的安全性是十分必要的。因为在函数式编程里，正确性第一，清晰性次之，效率排在第三位。ML在运行前会检查所有的类型和接口以防止出错，让程序员将更多的精力放在丰富语言上，而不是冗长又无用的调试和测试。ML远没有这次所展示的这么少，它的强大之处还待继续去深入地了解。23参考资料ML for the Working