ML语言

维基百科,自由的百科全书
跳到导航 跳到搜索
ML
编程范型多范型函数式指令式
設計者罗宾·米尔纳爱丁堡大学其他人
发行时间1973年,​48年前​(1973
穩定版本
Standard ML '97
(1997年,​24年前​(1997
型態系統类型推论静态类型强类型
衍生副語言
Standard ML, OCaml
啟發語言
ISWIM[1]PAL[2]POP-2[1],GEDANKEN[1]
影響語言
ClojureCoqCyclone英语Cyclone (programming language)C++Elm[3]ErlangFuthark[4]F#F*HaskellIdris、Lazy ML[5]MirandaNemerle[6]OCamlOpa英语Opa (programming language)RustScalaStandard MLUr[7]

MLMeta Language:元语言),是一个函数式指令式通用编程语言,它著称于使用了多态Hindley–Milner类型推论[8]。ML能自动的指定多数表达式英语Expression (computer science)类型,不要求显式的类型标注,而且能够确保类型安全,已经正式证明了有良好类型的ML程序不会导致运行时间类型错误[8]

ML提供了对函数实际参数的模式匹配垃圾回收指令式编程传值调用柯里化。它被大量的用于编程语言研究之中,并且是全面规定了的和使用形式语义验证了的少数语言之一。它的类型和模式匹配使得它非常适合并且经常用于在其他形式语言上进行操作,比如在编译器构造自动化定理证明形式验证中。

历史[编辑]

1970年代早期,ML由爱丁堡大学罗宾·米尔纳及他人研制出来[1],用于在LCF英语Logic for Computable Functions定理证明器中开发证明策略[9],它语法从ISWIM及其扩展实现PAL得到了启发[2]。LCF的语言是“PPλ”,它是一阶逻辑演算与有类型的多态λ演算的结合,以ML作为元语言[2]

在1980年,Luca Cardelli英语Luca Cardelli于爱丁堡大学的VAX/VMS系统上开发了ML编译器,它被称为“VAX ML”[10],以区别于LCF版本的“DEC-10 ML”[11],它运行在DEC-10/TOPS-10主机Stanford LISP[12]。VAX ML的编译器和运行时间系统二者,都是用Pascal书写而建立在“函数抽象机器”(FAM)之上[13]。在1982年,爱丁堡大学的Kevin Mitchell,用VAX ML重写了VAX ML编译器,随即John Scott和Alan Mycroft英语Alan Mycroft加入了开发,在又进行一系列重写改进之后,新的编译器被称为“Edinburgh ML”[14]

在1981年,INRIAGérard Huet英语Gérard Huet,将最初的LCF ML适配到Multics系统的Maclisp下,并且增加了编译器[15]。这个实现被描述于INRIA内部文档“ML手册”之中[16],它被开发者自称为“Le_ML”[17]剑桥大学Lawrence Paulson英语Lawrence Paulson用它开发了Cambridge LCF,而剑桥大学Michael J. C. Gordon英语Michael J. C. Gordon用它开发了第一版的HOL英语HOL (proof assistant)[18]

在1983年,Robin Milner由两个动机驱使开始重新设计ML[19]。首先是爱丁堡大学Rod Burstall英语Rod Burstall及其小组,在规定语言CLEAR[20]和函数式语言HOPE[21]的规定和具体化上的工作。HOPE拥有优雅的编程特征,特别是模式匹配[22]和子句式函数定义[23];还有使用在接口中的签名,进行规定的模块化构造的想法。其次是Luca Cardelli英语Luca Cardelli,通过增加命名记录和可变类型,扩展了ML中数据类型的品目[24]

在1984年,贝尔实验室的David MacQueen提出了对Standard ML模块系统的设计[25]。在Standard ML的持续设计期间[26],Edinburgh ML被渐进的修改,充当了Standard ML的近似原型实现[27]。在1986年,普林斯顿大学Andrew Appel英语Andrew Appel贝尔实验室的David MacQueen,以Edinburgh Standard ML作为起步开发环境[28],开始了专注于生成高质量机器代码的Standard ML of New Jersey的活跃开发[29]

在1990年,Robin MilnerMads Tofte英语Mads TofteRobert Harper英语Robert Harper (computer scientist)制定的Standard ML的正式规定最终完成[30],并于1997年进行了修订[31]。在1989年,Mads Tofte英语Mads Tofte、Nick Rothwell和David N. Turner于爱丁堡大学开始开发ML Kit编译器,为了强调清晰性而非高效,将标准定义直接转译成一组Standard ML模块;在1992年和1993年期间,主要通过爱丁堡大学的Nick Rothwell和哥本哈根大学DIKU英语UCPH Department of Computer Science的Lars Birkedal的工作[32],ML Kit版本1完成并开源发行[33]

在1987年,INRIA的Ascánder Suárez,基于巴黎第七大学Guy Cousineau法语Guy Cousineau的“范畴抽象机器英语Categorical abstract machine”(CAM)[34],利用Le Lisp英语Le Lisp的运行时间系统重新实现了Le_ML,并正式命名为Caml[15]。在1990年和1991年,INRIAXavier Leroy英语Xavier Leroy基于用C实现的字节码解释器[35],利用Damien Doligez英语Damien Doligez提供的内存管理系统重新实现了Caml,并称其为Caml Light[36]。在1995年,Xavier Leroy又增加了机器代码编译器和高层模块系统[37],这个版本也称为“Caml Special Light”。在1996年,INRIA的Didier Rémy和Jérôme Vouillon,向Caml Special Light增加了面向对象特征[38],从而形成了OCaml[39]

今天ML家族的两个主要的方言是Standard MLOCaml。ML的实力大多被用于语言设计和操作,比如建构编译器、分析器、定理证明器,但是它作为通用语言也被用于生物信息和财务系统等领域。ML确立了静态类型函数式编程范型,从而在编程语言历史上占有显要地位,它的思想在影响了众多的语言,例如HaskellNemerle[6]ATS英语ATS (programming language)Elm[3]

解释与编译[编辑]

SML的代码片段很容易通过将其录入到“顶层”来研习,它也叫作读取﹣求值﹣输出循环或REPL。这是打印结果或定义的表达式的推论类型的交互式会话。很多SML实现提供交互式REPL,比如SML/NJ

$ sml
Standard ML of New Jersey v110.79 [built: Sat Oct 26 12:27:04 2019]
-

可以在提示符-后键入代码。例如计算1 + 2 * 3:

- 1 + 2 * 3;
val it = 7 : int

顶层推论这个表达式的类型为int并给出结果7。如果输入不完全则打印第二提示符=,这时经常可以用;终结输入。it是给未指定变量的表达式的标准变量。输入control-C可返回解释器顶层,输入control-D可退出解释器。

下面是hello, world!的程序代码在SML/NJ解释器下执行的结果:

- val _ = print "Hello, world!\n";
Hello, world!

和使用MLton英语MLton编译器进行编译执行的例子:

$ echo 'print "Hello, world!\n";' > hello-world.sml
$ mlton hello-world.sml
$ ./hello-world
Hello, world!

核心语言[编辑]

不同于纯函数式编程语言,ML是兼具一些指令式特征的函数式编程语言。ML的特征包括:传值调用的求值策略头等函数,带有垃圾收集的自动内存管理参数多态静态类型类型推论代数数据类型英语Algebraic data type模式匹配异常处理。不同于Haskell,ML与大多数编程语言一样使用及早求值

用ML书写的程序构成自要被求值的表达式英语Expression (computer science),而非语句或命令,尽管一些表达式返回一个平凡的unit值并且只为其副作用而求值。以下章节介绍采用Standard ML的语法和语义。

函数[编辑]

就像所有的函数式语言一样,ML的关键特征是函数,它被用于进行抽象。例如阶乘函数用纯ML可表达为:

fun fac 0 = 1
  | fac n = n * fac (n - 1)

这里将阶乘描述为递归函数,具有一个单一的终止基础情况。它类似于在数学教科书见到的阶乘描述。多数ML代码在设施和语法上类似于数学。

凭借类型推论编译器能推导出,fac接受整数0作为实际参数,则形式参数n也是整数类型int,而fac 0的结果是整数1,则函数fac的结果也是整数类型。函数fac接受一个整数的形式参数并返回一个整数结果,它作为一个整体从而有着“从整数到整数的函数”类型int -> int。函数及其形式参数的"类型"还可以用类型标注(annotation)来描述,使用E : t表示法,它可以被读作表达式E有类型t,它是可选也可忽略的。使用类型标注,这个例子可重写为如下:

fun fac 0 = 1
  | fac (n : int) : int = n * fac (n - 1)

这个函数还依赖于模式匹配,这是ML语言的重要部份。注意函数形式参数不必须在圆括号内但要用空格分隔。当一个函数的实际参数是0,它将返回整数1。对于所有其他情况,尝试第二行。这是一个递归,并且再次执行这个函数直到达到基础情况。它可以使用case表达式重写为:

fun fac n = case n 
     of 0 => 1
      | n => n * fac (n - 1)

这里case介入了模式和对应表达式的序列。它还可以重写为将标识符绑定到lambda函数

val rec fac =
     fn 0 => 1
      | n => n * fac (n - 1)

这里的关键字val介入了标识符到值的绑定,fn介入了匿名函数的定义,它可以用在fun的位置上,但使用=>算符而非=。绑定到递归的匿名函数需要使用rec关键字来指示。

通过将主要工作写入尾递归风格的内部迭代函数,借助于语言编译或解释系统进行的尾调用优化,这个函数可以得以增进性能,它的调用栈不需要随函数调用数目而成比例的增长。对这个函数可以采用向内部函数增加额外的“累加器”形式参数acc来实现:

fun fact n = let
    fun fac (0, acc) = acc
      | fac (n, acc) = fac (n - 1, n * acc)
    in
        fac (n, 1)
    end

let表达式的值是在inend之间表达式的值。这个递归函数的实现不保证能够终止,因为负数实际参数会导致递归调用的无穷降链条件。更健壮的实现会在递归前检查实际参数为非负数,并在有问题的情况,即n是负数的时候,启用异常处理

fun fact n = let
    fun fac (0, acc) = acc
      | fac (n, acc) = fac (n - 1, n * acc)
    in
        if (n < 0) 
        then raise Fail "negative argument"
        else fac (n, 1)
    end

类型[编辑]

有一些基本类型可以当作是“内建”的,因为它们是在Standard ML Basis库中预先定义的,并且语言为它们提供文字英语Literal (computer programming)表示法,比如34是整数,而"34"是字符串。一些最常用的基本类型是:

  • int 整数,比如3~12。注意波浪号~表示负号。
  • real浮点数,比如4.2~6.4。Standard ML不隐含的提升整数为浮点数,因此表达式2 + 5.67 是无效的。
  • string字符串,比如"this is a string"""(空串)。
  • char字符,比如#"y"#"\n"(换行符)。
  • bool布尔值,它是要么true要么false。产生bool值的有比较算符=<>>>=<<=,逻辑函数not短路求值的中缀算符andalsoorelse

包括上述基本类型的各种类型可以用多种方式组合。一种方式是元组,它是值的有序集合,比如表达式(1, 2)的类型是int * int,而("foo", false)的类型是string * bool。可以使用#1 ("foo", false)这样的语法来提取元组的指定次序的成员。

有0元组(),它的类型指示为unit。但是没有1元组,或者说在例子(1)1之间没有区别,都有类型int。元组可以嵌套,(1, 2, 3)不同于((1, 2), 3)(1, (2, 3))二者。前者的类型是int * int * int,其他两个的类型分别是(int * int) * intint * (int * int)

组合值的另一种方式是记录。记录很像元组,除了它的成员是有名字的而非有次序的,例如{a = 5.0, b = "five"}有类型{a : real, b : string},这同于类型{b : string, a : real}。可以使用#a {a = 5.0, b = "five"}这样的语法来选取记录的指定名字的字段。

Standard ML中的函数只接受一个值作为参数,而不是参数的一个列表,可以使用上述元组模式匹配来实际上传递多个参数。函数还可以返回一个元组。例如:

fun sum (a, b) = a + b
fun average pair = sum pair div 2

infix averaged_with
fun a averaged_with b = average (a, b)
val c = 3 averaged_with 7

fun int_pair (n : int) = (n, n)

这里第一段创建了两个类型是int * int -> int的函数sumaverage。第二段创建中缀算子averaged_with,接着定义它为类型int * int -> int的函数。最后的int_pair函数的类型是int -> int * int

下列函数是多态类型的一个例子:

fun pair x = (x, x)

编译器无法推论出的pair的特殊化了的类型,它可以是int -> int * intreal -> real * real甚至是(int * real -> string) -> (int * real -> string) * (int * real -> string)。在Standard ML中,它可以简单指定为多态类型'a -> 'a * 'a,这里的'a(读作“alpha”)是一个类型变量,指示任何可能的类型。在上述定义下,pair 3pair "x"都是有良好定义的,分别产生(3, 3)("x", "x")

算符=被定义为多态等式,它确定两个值是否相等,有着类型''a * ''a -> bool。这意味着它的两个运算数必须有相同的类型,这个类型必须是等式类型(eqtype)。上述基本类型中除了real之外,intrealstringcharbool都是等式类型。

例如:3 = 3"3" = "3"#"3" = #"3"true = true,都是有效的表达式并求值为true;而3 = 4是有效表达式并求值为false3.0 = 3.0是无效表达式而被编译器拒绝。这是因为IEEE浮点数等式打破了ML中对等式的一些要求。特别是nan不等于自身,所以关系不是自反的。

元组和记录类型是等式类型,当时且仅当它的每个成员类型是等式类型;例如int * string{b : bool, c : char}unit是等式类型,而int * real{x : real}不是。函数类型永远不是等式类型,因为一般情况下不可能确定两个函数是否等价。

数据类型[编辑]

Standard ML提供了对代数数据类型英语Algebraic data type(ADT)的强力支持。一个ML数据类型可以被当作是元组不交并英语Product type)。数据类型使用datatype关键字来定义,比如:

datatype int_or_string
  = INT of int
  | STRING of string
  | NEITHER

这个数据类型声明建立一个全新的数据类型int_or_string,还有一起的新构造子(一种特殊函数或值)INTSTRINGNEITHER;每个这种类型的值都是要么INT具有一个整数,要么STRING具有一个字符串,要么NEITHER。写为如下这样:

val i = INT 3
val s = STRING "qq"
val n = NEITHER
val INT j = i

这里最后的一个声明通过模式匹配,将变量j绑定到变量i所绑定的整数3val 模式 = 表达式是绑定的一般形式,它是良好定义的,当且仅当模式和表达式有相同的类型。

数据类型可以是多态的:

datatype 'a pair
  = PAIR of 'a * 'a

这个数据类型声明建立一个新的类型'a pair家族,比如int pairstring pair等等。

数据类型可以是递归的:

datatype int_list
  = EMPTY
  | INT_LIST of int * int_list

这个数据类型声明建立一个新类型int_list,这个类型的每个值是要么EMPTY(空列表),要么是一个整数和另一个int_list的接合。

通过datatype创建的类型是等式类型,如果它的所有变体,要么是没有参数的空构造子,要么是有等式类型参数的构造子,并且在多态类型情况下所有类型参数也都是等式类型。递归类型在有可能情况下是等式类型,否则就不是。

列表[编辑]

基础库提供的复杂数据类型之一是列表list。它是一个递归的、多态的数据类型,可以等价的定义为:

datatype 'a list
  = nil 
  | :: of 'a * 'a list

这里的::是中缀算符,例如3 :: 4 :: 5 :: nil是三个整数的列表。列表是ML程序中最常用的数据类型之一,语言还为生成列表提供了特殊表示法[3, 4, 5]

real list当然不是等式类型。但是没有int list不能是等式类型的理由,所以它就是等式类型。注意类型变量不同就是不同的列表类型,比如(nil : int list) = (nil : char list)是无效的,因为两个表达式有不同的类型,即使它们有相同的值。但是nil = nil(nil : int list) = nil都是有效的。

基本库rev函数“反转”一个列表中的元素。它的类型是'a list -> 'a list,就是说它可以接受其元素有任何类型的列表,并返回相同类型的列表。更准确的说,它返回其元素相较于给定列表是反转次序的一个新列表,比如将[ "a", "b", "c" ]映射成[ "c", "b", "a" ]。中缀算符@表示两个列表的串接。

rev@一般被实现为基本库函数revAppend的简单应用:

fun revAppend ([], l) = l
  | revAppend (x :: r, l) = revAppend(r, x :: l)

fun rev l = revAppend(l, [])

fun l1 @ l2 = revAppend(rev l1, l2)

类型声明[编辑]

类型声明或同义词(synonym)使用type关键字来定义。下面是给在平面中的点的类型声明,计算两点间距离,和通过海伦公式计算给定角点的三角形的面积的函数。

type loc = real * real

fun heron (a: loc, b: loc, c: loc) = let
    fun dist ((x0, y0), (x1, y1)) = let
        val dx = x1 - x0
        val dy = y1 - y0
        in
            Math.sqrt (dx * dx + dy * dy)
        end
    val ab = dist (a, b)
    val bc = dist (b, c)
    val ac = dist (a, c)
    val s = (ab + bc + ac) / 2.0
    in
        Math.sqrt (s * (s - ab) * (s - bc) * (s - ac))
    end

模式匹配[编辑]

Standard ML的数据类型可以轻易的定义和用于编程,在很大程度上是由它的模式匹配,还有多数Standard ML实现的模式穷尽性检查和模式冗余检查。

模式匹配可以在语法上嵌入到变量绑定之中,比如:

val ((m: int, n: int), (r: real, s: real)) = ((2, 3), (2.0, 3.0))

type hyperlink = {protocol: string, address: string, title: string}

val url : hyperlink =
    {title="The Standard ML Basis Library", protocol="https",
     address="//smlfamily.github.io/Basis/overview.html"}
val {protocol=port, address=addr, title=name} = url

val x as (fst, snd) = (2, true)

第一个val绑定了四个变量mnrs;第二个val绑定了一个变量url;第三个val绑定了三个变量portaddrname,第四个叫分层模式,绑定了三个变量xfstsnd

模式匹配可以在语法上嵌入到函数定义中,比如:

datatype shape
  = Circle of loc * real    (* 中心和弧度 *)
  | Square of loc * real    (* 左上角和边长,坐标轴对齐 *)
  | Triangle of loc * loc * loc     (* 角点 *)

fun area (Circle (_, r)) = 3.14 * r * r
  | area (Square (_, s)) = s * s
  | area (Triangle (a, b, c)) = heron (a, b, c)

次序在模式匹配中是紧要的:模式按文本次序来依次进行匹配。在特定计算中,使用下划线_,来省略不需要它的值的子成员,这也叫做通配符(wildcard)模式。所谓的“子句形式”风格的函数定义,这里的模式紧随在函数名字之后出现,只是如下形式的一种语法糖

fun area shape = case shape
      of Circle (_, r) => 3.14 * r * r
       | Square (_, s) => s * s
       | Triangle (a, b, c) => heron (a, b, c)

模式穷尽性检查将确保数据类型的每个情况都已经顾及到。[a] 如果有遗漏,则产生警告。[b] 如果模式存在冗余,也会导致一个编译时间警告。[c]

高阶函数[编辑]

函数可以接受函数作为实际参数,比如:

fun applyToBoth f x y = (f x, f y)

函数可以产生函数作为返回值,比如:

fun constantFn k = (fn anything => k)

函数可以同时接受和产生函数,比如复合函数英语Function composition (computer science)

fun compose (f, g) = (fn x => f (g x))

基本库的函数List.map,是在Standard ML中最常用的Curry化高阶函数,它在概念上可定义为:

fun map _ [] = []
  | map f (x :: xs) = f x :: map f xs

在基本库中将函数复合定义为中缀算符(f o g)mapfold高阶函数有较高效率的实现。[d]

异常[编辑]

异常可以使用raise关键字发起,并通过模式匹配handle构造来处理:

exception Undefined;

fun max [x] = x
  | max (x :: xs) = let
    val m = max xs
    in
        if x > m then x else m 
    end
  | max [] =
      raise Undefined

fun main xs = let
    val msg = (Int.toString (max xs))
    handle Undefined => "empty list...there is no max!"
    in
        print (msg ^ "\n")
    end

这里的^是字符串串接算符。可以利用异常系统来实现非局部退出,例如这个函数所采用技术:

exception Zero;

fun listProd ns = let
    fun p [] = 1
      | p (0 :: _) = raise Zero
      | p (h :: t) = h * p t
    in
        (p ns)
        handle Zero => 0
    end

异常Zero0情况下发起,控制从函数p中一起出离。

引用[编辑]

初始化基础库还以引用的形式提供了可变的存储。引用ref可以在某种意义上被认为是如下这样定义的:

datatype 'a ref = ref of 'a

还定义了内建的:=函数来修改引用的内容,和!函数来检索引用的内容。阶乘函数可以使用引用定义为指令式风格:

fun factImperative n = let
    val i = ref n and acc = ref 1
    in
        while !i > 0 do
            (acc := !acc * !i;
             i := !i - 1);
        !acc
    end

这里使用圆括号对以;分隔的表达式进行了顺序复合。

可变类型'a ref是等式类型,即使它的成员类型不是。两个引用被称为是相等的,如果它们标识相同的“ref单元”,就是说相同的对ref构造子调用生成的同一个指针。因此(ref 1) = (ref 1)(ref 1.0) = (ref 1.0)都是有效的,并且都求值为false,因为即使两个引用碰巧指向了相同的值,引用自身是分立的,每个都可以独立于其他而改变。

模块语言[编辑]

模块是ML用于构造大型项目和库的系统。

模块[编辑]

一个模块构成自一个签名(signature)文件和一个或多个结构文件。签名文件指定要实现的API(就像C语言头文件或Java接口文件)。结构实现这个签名(就像C语言源文件或Java文件)。解释器通过use命令导入它们。ML的标准库被实现为这种方式的模块。

例如,下列定义一个算术签名:

signature ARITH =
sig
    type t
    val zero : t
    val one : t
    val fromInt: int -> t  
    val fromIntPair : int * int -> t
    val fromReal : real -> t
    val succ : t -> t
    val pred : t -> t
    val ~ : t -> t
    val + : t * t -> t
    val - : t * t -> t
    val * : t * t -> t
    val / : t * t -> t
    val == : t * t -> bool
    val <> : t * t -> bool
    val > : t * t -> bool
    val >= : t * t -> bool
    val < : t * t -> bool
    val <= : t * t -> bool
end

和这个签名使用有理数的实现:

structure Rational : ARITH =
struct
    datatype t = Rat of int * int
    val zero = Rat (0, 1)
    val one = Rat (1, 1)
    fun fromInt n = Rat (n, 1)
    fun ineg (a, b) = (~a, b)
    fun fromIntPair (num, den) = let
        fun reduced_fraction (numerator, denominator) = let
            fun gcd (n, 0) = n
              | gcd (n, d) = gcd (d, n mod d)
            val d = gcd (numerator, denominator)
            in 
                if d > 1 then (numerator div d, denominator div d) 
                else (numerator, denominator)
            end
        in  
            if num < 0 andalso den < 0
            then Rat (reduced_fraction (~num, ~den))
            else if num < 0 
            then Rat (ineg (reduced_fraction (~num, den)))
            else if den < 0
            then Rat (ineg (reduced_fraction (num, ~den)))
            else Rat (reduced_fraction (num, den))
        end
    val SOME maxInt = Int.maxInt
    val minPos = 1.0 / (real maxInt)
    fun fromReal r = let
        fun convergent (i, f, h_1, k_1, h_2, k_2) = 
              if i <> 0 andalso ((h_1 > (maxInt - h_2) div i)
                  orelse (k_1 > (maxInt - k_2) div i))
              then (h_1, k_1)
              else if f < minPos 
              then (i * h_1 + h_2, i * k_1 + k_2)
              else convergent (trunc (1.0 / f), Real.realMod (1.0 / f),
                               i * h_1 + h_2, i * k_1 + k_2, h_1, k_1)
        in 
            if r < 0.0
            then Rat (ineg (convergent (trunc (~ r), 
                      Real.realMod (~ r), 1, 0, 0, 1))) 
            else Rat (convergent (trunc r, Real.realMod r, 1, 0, 0, 1))
        end
    fun succ (Rat (a, b)) = fromIntPair (a + b, b)
    fun pred (Rat (a, b)) = fromIntPair (a - b, b)
    fun add (Rat (a, b), Rat (c, d)) = 
          if b = d then fromIntPair(a + c, b) 
          else fromIntPair (a * d + c * b, b * d)
    fun sub (Rat (a, b), Rat (c, d)) = 
          if b = d then fromIntPair(a - c, b) 
          else fromIntPair (a * d - c * b, b * d)
    fun mul (Rat (a, b), Rat (c, d)) = fromIntPair (a * c, b * d)
    fun div_ (Rat (a, b), Rat (c, d)) = fromIntPair (a * d, b * c)
    fun gt (Rat (a, b), Rat (c, d)) =
          if b = d then (a > c) else (a * d) > (b * c)
    fun lt (Rat (a, b), Rat (c, d)) =
          if b = d then (a < c) else (a * d) < (b * c)
    fun neg (Rat (a, b)) = Rat (~a, b)
    fun eq (Rat (a, b), Rat (c, d)) = ((b = d) andalso (a = c))
    fun ~ a = neg a
    fun a + b = add (a, b)
    fun a - b = sub (a, b)
    fun a * b = mul (a, b)
    fun a / b = div_ (a, b)
    fun op == (a, b) = eq (a, b)
    fun a <> b = not (eq (a, b))
    fun a > b = gt (a, b)
    fun a >= b = (gt (a, b) orelse eq (a, b))
    fun a < b = lt (a, b)
    fun a <= b = (lt (a, b) orelse eq (a, b))
end

下面是这个结构的简单用例:

infix ==
local open Rational
in  
    val c = let 
    val a = fromIntPair(2, 3)
    val b = fromIntPair(4, 6)
    in
        a + b
    end
end
structure R = Rational
R.fromReal(3.245)

Standard ML只允许通过签名函数同实现进行交互,例如不可以直接通过这个代码中的Rat来建立数据对象。结构块对外部隐藏所有实现细节。这里的:叫做透明归属(ascription),可以通过所绑定的变量见到此结构的数据内容,与之相对的是:>,它叫做不透明归属,此结构的数据内容对外完全不可见。

要用有理数进行实际上的数值计算,需要处理分数形式中分母快速增大导致溢出整数类型大小范围等问题。[e]

函子[编辑]

函子接受指定签名的一个结构作为参数,并返回一个结构作为结果,下面示例的函子能在ARITH签名的结构上计算移动平均

functor MovingList (S : ARITH) = 
struct
    type t = S.t list * int * S.t
    fun size (ml : t) = #2 ml
    fun average (ml : t) = #3 ml
    fun fromList (l : S.t list) = let
        val n = length l
        val sum = foldl S.+ S.zero l
        local open S in
          val m = sum / (fromInt n) end 
        in
            if (null l) then raise Empty
            else (l, n, m) 
        end
    fun move ((l, n, m) : t, new : S.t) = let
        val old = List.nth (l, n - 1) 
        local open S in
          val m' = m + (new - old) / (fromInt n) end    
        in
            (new :: l, n, m')
        end     
    fun expand ((l, n, m) : t, new : S.t) = let
        val n' = n + 1; 
        local open S in
          val m' = m + (new - m) / (fromInt n') end
        in
            (new :: l, n', m')
        end
    fun shrink ((l, n, m) : t) = let
        val old = List.nth (l, n - 1) 
        val n' = if (n > 2) then n - 1 else 1 
        local open S in 
          val m' = m + (m - old) / (fromInt n') end
        in
            (l, n', m')
        end
    fun trunc ((l, n, m) : t) =
          (List.take (l, n), n, m)
end

和这个函子的简单用例:

structure R = Rational
structure MLR = MovingList (Rational)
val d = MLR.fromList [R.fromIntPair (4, 5), R.fromIntPair (2, 3)]
val d = MLR.expand (d, R.fromIntPair (5, 6))
val d = MLR.move (d, R.fromIntPair (7, 8))
val d = MLR.shrink d
val d = MLR.trunc d

示例代码[编辑]

下列例子使用了Standard ML的语法和语义。

素数[编辑]

下面是求素数试除法实现:

fun prime n = let
    fun isPrime (l, i) = let
        fun findDivisor [] = NONE 
          | findDivisor (x :: xs) = 
              if (i mod x) = 0 then SOME x
              else if (x * x) > i then NONE 
              else findDivisor xs
        in  
            case findDivisor l
              of SOME _ => false 
               | NONE => true
        end
    fun iterate (acc, i) =
          if i > n then acc
          else if isPrime (acc, i)
          then iterate (acc @ [i], i + 2)
          else iterate (acc, i + 2)
    in 
        if n < 2 then []
        else iterate ([2], 3)
    end

埃拉托斯特尼筛法实现[40]

fun prime n = let
    fun dropComposite (acc, [], _, _) = rev acc
      | dropComposite (acc, l as x :: xs, j, i) = 
          if j > n then List.revAppend (acc, l) 
          else if x < j  
          then dropComposite (x :: acc, xs, j, i)
          else if x > j 
          then dropComposite (acc, l, j + i, i)
          else dropComposite (acc, xs, j + i, i)
    fun generate i = let
        fun loop (l, i) = 
              if i <= 2 then l
              else loop (i :: l, i - 2)
        in
            loop ([], i - (i + 1) mod 2)
        end
    fun iterate (acc, []) = rev acc     
      | iterate (acc, l as x :: xs) = 
          if x * x > n then 2 :: List.revAppend (acc, l)
          else iterate (x :: acc,
                   dropComposite ([], xs, x * x, x * 2))
    in 
        if n < 2 then [] 
        else iterate ([], generate n)
    end

筛法还有基于数组的直观实现。[f] 下面是其解释器下命令行运行实例:

- fun printIntList (l: int list) =
=     print ((String.concatWith " " (map Int.toString l)) ^ "\n");
val printIntList = fn : int list -> unit
- val _ = printIntList (prime 100);
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

汉明数[编辑]

正规数是形如整数,对于非负整数,它是可以整除的数。计算升序的正规数的算法经由戴克斯特拉得以流行[41]理查德·汉明最初提出了这个问题,故而这个问题被称为“汉明问题”,这个数列也因而被称为汉明数。Dijkstra计算这些数的想法如下:

  • 汉明数的序列开始于数1
  • 要加入序列中的数有下述形式:2h, 3h, 5h,这里的h是序列已有的任意的汉明数。
  • 因此,可以生成最初只有一个1的序列H,并接着归并英语Merge algorithm序列2H, 3H, 5H,并以此类推。
fun Hamming_number n = let
    fun merge (p, q) = let
        fun revMerge (acc, p, q) =
              if not (null p) andalso not (null q) then
                  if hd p < hd q
                  then revMerge ((hd p) :: acc, tl p, q)
                  else if hd p > hd q
                  then revMerge ((hd q) :: acc, p, tl q)
                  else revMerge ((hd p) :: acc, tl p, tl q)
              else if null p 
              then List.revAppend (q, acc)
              else List.revAppend (p, acc)
        in
            if (null p) then q
            else if (null q) then p
            else rev (revMerge ([], p, q))
        end
    fun mul m x =
          if x <= (n div m) then SOME (x * m) else NONE
    fun mapShortCircuit pred l = let
        fun mapp ([], acc) = rev acc
          | mapp (x :: xs, acc) = (case (pred x)
              of SOME a => mapp (xs, a :: acc)
               | NONE => rev acc)
        in
            mapp (l, [])
        end
    fun generate l = let
        fun listMul m = mapShortCircuit (mul m) l
        fun mergeMul (m, i) = merge (listMul m, i)
        in
            foldl mergeMul [] [2, 3, 5]
        end
    fun iterate (acc, l) =
          if (hd l) > (n div 2) then merge (l, acc)
          else iterate (merge (l, acc), generate l)
    in
        if n > 0 then iterate ([], [1]) else []
    end

由于汉明数算法采用升序列表,这里将基本库mapPartial函数,[g] 改写为mapShortCircuit以便在认定后续元素都不满足条件时尽早结束,下面是汉明数程序在解释器下命令行运行实例:

- fun printIntList (l: int list) =
=     print ((String.concatWith " " (map Int.toString l)) ^ "\n");
val printIntList = fn : int list -> unit
- val _ = printIntList (Hamming_number 400);
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 60 64 72 75 80 81 90 96 100 108 120 125 128 135 144 150 160 162 180 192 200 216 225 240 243 250 256 270 288 300 320 324 360 375 384 400

示例汉明数程序代码一般用来展示纯函数式编程方式[42][h]

续体传递风格实例[编辑]

下面是续体传递风格英语Continuation-passing style(CPS)的合计整数列表的实现[43]

fun sum l = let
    fun sumCPS (k, []) = k 0
      | sumCPS (k, x :: xs) =
          sumCPS (fn a => k (x + a), xs)
    in
        sumCPS (fn x => x, l)
    end

对于输入[x1, x2, ..., xn]sumCPS函数等价于函数复合(fn x => x) o (fn a => x1 + a) o (fn a => x2 + a) o ... o (fn a => xn + a),它应用于0上得到(x1 + (x2 + (... + (xn + 0)...)))

排序算法[编辑]

排序算法关注计算复杂度,特别是时间复杂度,基本库函数的实现细节也要考虑在内,除非必需的情况避免使用遍历整个列表的length函数。[i] 通过比较于这些排序算法的周知过程式编程语言比如C语言的实现,可以体察到ML的函数式编程的相关限制和特色编码风格。

插入排序[编辑]

下面是简单的插入排序算法的实现:

fun insertSort l = let
    fun insert (acci, l, i) =
          if (null l) orelse i < (hd l)
          then List.revAppend (acci, i :: l)
          else insert ((hd l) :: acci, tl l, i)
    fun iterate (acc, l) =
          if (null l) then acc
          else iterate (insert ([], acc, hd l), tl l)
    in
        iterate ([], l)
    end

快速排序[编辑]

下面是快速排序算法的自顶向下实现:

fun quickSort [] = []
  | quickSort [x] = [x]
  | quickSort [x, y] =
      if x <= y then [x, y] else [y, x]
  | quickSort [x, y, z] = let
    val (x, y) = if x <= y then (x, y) else (y, x)
    val (y, z) = if y <= z then (y, z) else (z, y)
    val (x, y) = if x <= y then (x, y) else (y, x)
    in
        [x, y, z]
    end
  | quickSort (pivot :: xs) = let
    fun partition pred l = let
        fun loop ([], p, q) = (p, q)
          | loop (h :: t, p, q) =
              if (pred h) 
              then loop (t, h :: p, q)
              else loop (t, p, h :: q)
        in
            loop (l, [], [])
        end
    val (le, gt) = partition (fn x => (x <= pivot)) xs
    in  
        (quickSort le) @ (pivot :: (quickSort gt))
    end

基本库partition函数实现对快速排序而言有不必要的反转,[j] 这里采用了它的简化改写。由于fun l1 @ l2 = revAppend(rev l1, l2),在ML中快速排序应采用自底向上实现:

fun quickSort l = let 
    fun partition pred l = let
        fun loop ([], p, q) = (p, q)
          | loop (h :: t, p, q) =
              if (pred h) 
              then loop (t, h :: p, q)
              else loop (t, p, h :: q)
        in
            loop (l, [], [])
        end
    fun iterate (acc, []) = acc
      | iterate (acc, [] :: xs) = iterate (acc, xs)
      | iterate (acc, [x] :: xs) = iterate (x :: acc, xs)
      | iterate (acc, [x, y] :: xs) = let
        val (x, y) = if x <= y then (x, y) else (y, x) 
        in
            iterate (x :: y :: acc, xs)
        end
      | iterate (acc, [x, y, z] :: xs) = let
        val (x, y) = if x <= y then (x, y) else (y, x)
        val (x, y, z) =
              if y <= z then (x, y, z)
              else if x <= z then (x, z, y)
              else (z, x, y)
        in
            iterate (x :: y :: z :: acc, xs)
        end
      | iterate (acc, (pivot :: d) :: xs) = let
        val (le, gt) = partition (fn x => (x <= pivot)) d
        in
            iterate (acc, gt :: [pivot] :: le :: xs) 
        end       
    in
        iterate ([], [l])
    end

归并排序[编辑]

下面是归并排序算法的自底向上法实现:

fun mergeSort l = let
    fun generate (acc, []) = acc
      | generate (acc, [x]) = [x] :: acc
      | generate (acc, [x, y]) =
          if x <= y then [x, y] :: acc else [y, x] :: acc
      | generate (acc, x :: y :: z :: xs) = let
        val (x, y, z) =
              if x <= y then
                  if y <= z then (x, y, z)
                  else if x <= z then (x, z, y)
                  else (z, x, y)
              else 
                  if x <= z then (y, x, z)
                  else if y <= z then (y, z, x)
                  else (z, y, x)
        in
            generate ([x, y, z] :: acc, xs)
        end
    fun mergeWith _ (acc, [], []) = acc
      | mergeWith _ (acc, p, []) = List.revAppend (p, acc)  
      | mergeWith _ (acc, [], q) = List.revAppend (q, acc)
      | mergeWith cmp (acc, p :: ps, q :: qs) =
          if cmp (p, q)
          then mergeWith cmp (p :: acc, ps, q :: qs)
          else mergeWith cmp (q :: acc, p :: ps, qs)
    val mergeRev = mergeWith (fn (x, y) => (x > y))
    val revMerge = mergeWith (fn (x, y) => (x < y))
    fun iterate ([], _) = []
      | iterate ([x], isRev) =
          if isRev then rev x else x
      | iterate (acc, isRev) = let      
        val merge = if isRev then mergeRev else revMerge
        fun loop (acci, []) = acci
          | loop (acci, [x]) = (rev x) :: acci 
          | loop (acci, x :: y :: xs) = 
              loop (merge ([], x, y) :: acci, xs)
        in
            iterate (loop ([], acc), not isRev)
        end
    in
        iterate (generate ([], l), false)
    end

考虑输入列表[x1, ..., xi, a0, ..., a9, xj, ..., xn],这里在xixj之间的10a,具有相同的值并且需要保持其下标表示的次序,这里的xi > a并且xj < a,并且在这个区段前后的元素总数都能被3整除,则它被分解成子列表的列表[Xm, ..., [xj, a8, a9], [a5, a6, a7], [a2, a3, a4], [a0, a1, xi], ..., X1],这里有m = n div 3;假定这4个含有a的子列表两两归并,在归并正序子列表的归并条件x < y下,能得到[X1, ..., [xi, a4, ..., a0], [a9, ..., a5, xj], ..., Xk];继续推演下去,在归并反序子列表的归并条件x > y下,能得到[Xh, ..., [xj, a0, ..., a9, xi], ..., X1]。可以看出这种归并操作能够保证排序算法的稳定性,即具有相同值的元素之间的相对次序保持不变。

分解初始的子列表采用了插入排序,还可进一步增加其大小。[k] 归并排序也有自顶向下实现。[l]

堆排序[编辑]

下面是堆排序的基于数组的实现:

fun heapSort l = let
    val h = Array.fromList l
    val len = Array.length h
    fun get i = Array.sub (h, i)
    fun set i v = Array.update (h, i, v)
    fun siftdown (i, v, n) = let
        fun next p = let
            val l = p * 2 + 1
            val r = l + 1
            in 
                if (r < n) andalso
                   (get r) > (get l) then r
                else if (l < n) then l
                else p
            end
        fun loop i = let
            val j = next i
            in
                if j = i orelse (get j) <= v
                then set i v
                else (set i (get j); loop j)
            end
        in
            loop i    
        end
    fun heapify () = let
        fun loop i =
              if i < 0 then ()
              else (siftdown (i, get i, len);
                    loop (i - 1))
        in
            loop (len div 2 - 1)
        end
    fun generate () = let
        fun loop (acc, i) = let
            val t = get 0
            in
               if i <= 0 then t :: acc
               else (siftdown (0, get i, i);
                     loop (t :: acc, i - 1))
            end
        in
            loop ([], len - 1)
        end
    in
        heapify (); 
        generate ()
    end

在数组实现中,siftdown函数融合了筛选和插入功能,在提取堆顶元素生成结果列表时,先摘出最后的堆底元素而缩小堆的大小,然后的siftdown函数在逐级递降筛选出堆顶元素同时把它再插入回到堆中。这里建造堆的heapify函数也可以采用siftup函数来实现。[m] 排序算法也可以使用二叉树数据结构来实现二叉堆

fun heapSort l = let
    datatype 'a heap
      = Nil 
      | Leaf of 'a
      | Node of 'a * int * 'a heap * 'a heap
    fun key Nil = 
          let val SOME a = Int.minInt in a end
      | key (Leaf k) = k
      | key (Node (k, _, _, _)) = k
    fun count Nil = 0
      | count (Leaf _) = 1
      | count (Node (_, c, _, _)) = c    
    fun insert (Nil, x) = Leaf x
      | insert (Leaf k, l) = 
          if l >= k
          then Node (l, 2, Leaf k, Nil)
          else Node (k, 2, Leaf l, Nil)
      | insert (Node (k, _, Leaf l, Nil), r) = 
          if r >= k 
          then Node (r, 3, Leaf k, Leaf l)
          else if r >= l
          then Node (k, 3, Leaf r, Leaf l)
          else Node (k, 3, Leaf l, Leaf r)
      | insert (Node (k, c, l, r), x) = let
        val (k, x) = 
              if k >= x then (k, x) else (x, k) 
        in      
            if (count l) <= (count r)
            then Node (k, c + 1, insert (l, x), r) 
            else if x >= (key l)
            then Node (k, c + 1, insert (r, x), l)
            else Node (k, c + 1, l, insert (r, x))
        end
    fun extract Nil = Nil
      | extract (Leaf _) = Nil
      | extract (Node (_, _, l, Nil)) = l
      | extract (Node (_, c, l, r)) = let
        val k = key l
        val n = extract l
        in
            if n = Nil
            then Node (k, c - 1, r, Nil)
            else if (key n) >= (key r)
            then Node (k, c - 1, n, r)
            else Node (k, c - 1, r, n)
        end
    fun heapify () = let
        fun loop (acc, []) = acc
          | loop (acc, x :: xs) =
              loop (insert (acc, x), xs)  
        in
            loop (Nil, l)
        end
    fun generate h = let
        fun loop (acc, Nil) = acc
          | loop (acc, h) =
              loop ((key h) :: acc, extract h)
        in
            loop ([], h)
        end           
    in
        generate (heapify ())
    end

二叉树实现不便于直接访问堆底元素,故而使用insertextract函数分别承担独立的功能。

随机数生成[编辑]

编写排序算法进行测试除了使用简单的数列,[n] 还可以使用线性同余伪随机数函数来生成列表:

fun randList (n, seed) = let
    val randx = ref seed
    fun lcg () = (randx := (!randx * 1366 + 150889) mod 714025; !randx)
    fun iterate (acc, i) =
          if i <= 0 then acc
          else iterate (lcg () :: acc, i - 1)
    in
        iterate ([], n)
    end

语言解释器[编辑]

定义和处理一个小型表达式语言是相对容易的:

exception Err
 
datatype ty
  = IntTy
  | BoolTy
 
datatype exp
  = True
  | False
  | Int of int
  | Not of exp
  | Add of exp * exp
  | If of exp * exp * exp
 
fun typeOf (True) = BoolTy
  | typeOf (False) = BoolTy
  | typeOf (Int _) = IntTy
  | typeOf (Not e) = 
      if typeOf e = BoolTy
      then BoolTy
      else raise Err
  | typeOf (Add (e1, e2)) = 
      if (typeOf e1 = IntTy) andalso (typeOf e2 = IntTy)
      then IntTy
      else raise Err
  | typeOf (If (e1, e2, e3)) = 
      if typeOf e1 <> BoolTy
      then raise Err
      else if typeOf e2 <> typeOf e3 then raise Err
      else typeOf e2

fun eval (True) = True
  | eval (False) = False
  | eval (Int n) = Int n
  | eval (Not e) = (case eval e
      of True => False
       | False => True
       | _ => raise Fail "type-checking is broken")
  | eval (Add (e1, e2)) = let
    val (Int n1) = eval e1
    val (Int n2) = eval e2
    in
        Int (n1 + n2)
    end
  | eval (If (e1, e2, e3)) = 
      if eval e1 = True
      then eval e2
      else eval e3
 
fun exp_repr e = let
    val msg = case e
         of True  => "True"
          | False => "False"
          | Int n => Int.toString n
          | _ => ""     
    in
        msg ^ "\n"
    end
    
(* 忽略TypeOf的返回值,它在类型错误时发起Err *) 
fun evalPrint e = (ignore (typeOf e); print (exp_repr (eval e)));

将这段代码录入文件比如expr-lang.sml,并在命令行下执行sml expr-lang.sml,可以用如下在正确类型的和不正确类型上运行的例子,测试这个新语言:

- val e1 = Add (Int 1, Int 2);  (* 正确的类型 *)
val e1 = Add (Int 1,Int 2) : exp
- val _ = evalPrint e1;
3
- val e2 = Add (Int 1, True);   (* 不正确的类型 *)
val e2 = Add (Int 1,True) : exp
- val _ = evalPrint e2;

uncaught exception Err
  raised at: expr-lang.sml:25.20-25.23

注释和附录代码[编辑]

  1. ^ 子句集合是穷尽和不冗余的函数示例:
    fun hasCorners (Circle _) = false
      | hasCorners _ = true
    

    如果控制通过了第一个模式Circle,则这个值必定是要么Square要么Triangle。在任何这些情况下,这个形状都有角点,所以返回true而不用区分具体是那种情况。

  2. ^ 不详尽的模式示例:
    fun center (Circle (c, _)) = c
      | center (Square ((x, y), s)) = (x + s / 2.0, y + s / 2.0)
    

    这里在center函数中没有给Triangle的模式。 编译器发起模式不详尽的一个警告,并且如果在运行时间,Triangle被传递给这个函数,则发起异常Match

  3. ^ 存在模式冗余的(无意义)函数示例:
    fun f (Circle ((x, y), r)) = x+y
      | f (Circle _) = 1.0
      | f _ = 0.0
    

    匹配第二个子句的模式的任何值都也匹配第一个子句的模式,所以第二个子句是不可到达的。因此这个定义整体上是冗余的。

  4. ^ 映射函数的实际实现:
    fun map f = let
        fun m [] = []
    	  | m [a] = [f a]
    	  | m [a, b] = [f a, f b]
    	  | m [a, b, c] = [f a, f b, f c]
    	  | m (a :: b :: c :: d :: r) = f a :: f b :: f c :: f d :: m r
        in
    	    m
        end
    

    折叠函数的实际实现:

    fun foldl f b l = let
        fun f2 ([], b) = b
    	  | f2 (a :: r, b) = f2 (r, f (a, b))
        in
    	    f2 (l, b)
        end
    
    fun foldr f b l = foldl f b (rev l)
    

    过滤器函数的实际实现:

    fun filter pred [] = []
      | filter pred (a :: rest) =
          if pred a
    	  then a :: (filter pred rest)
    	  else (filter pred rest)
    
  5. ^ 对分数采取修约的有理数实现:
    signature ARITH =
    sig
        type t
        val zero : t
        val one : t
        val fromInt: int -> t  
        val fromIntPair : int * int -> t
        val repr : t -> unit
        val succ : t -> t
        val pred : t -> t
        val ~ : t -> t
        val + : t * t -> t
        val - : t * t -> t
        val * : t * t -> t
        val / : t * t -> t
    end
    
    structure Rational : ARITH =
    struct
        type t = int * int
        val zero = (0, 1)
        val one = (1, 1)
        val maxInt = (let val SOME a = Int.maxInt in Int.toLarge a end)
        fun fromInt n = (n, 1)
        fun neg (a, b) = (~a, b)
        fun fromLargePair (a, b) = (Int.fromLarge a, Int.fromLarge b)
        fun fromIntPair (num, den) = let
            fun reduced_fraction (numerator, denominator) = let
                fun gcd (n, 0) = n
                  | gcd (n, d) = gcd (d, n mod d)
                val d = gcd (numerator, denominator)
                in 
                    if d > 1 then (numerator div d, denominator div d) 
                    else (numerator, denominator)
                end
            in
                if num < 0 andalso den < 0
                then reduced_fraction (~num, ~den)
                else if num < 0 
                then neg (reduced_fraction (~num, den))
                else if den < 0
                then neg (reduced_fraction (num, ~den))
                else reduced_fraction (num, den)
            end
        fun repr (a, b) = let
            val m = if (b = 0) then 0 else if (a >= 0) then a div b else ~a div b
            val n = if (b = 0) then 1 else if (a >= 0) then a mod b else ~a mod b
            val ms = Int.toString m and ns = Int.toString n and bs = Int.toString b
            in 
                if n <> 0 andalso m <> 0 andalso a < 0
                then print ("~" ^ ms ^ " - " ^ ns ^ "/" ^ bs ^ "\n")
                else if n <> 0 andalso m <> 0  
                then print (ms ^ " + " ^ ns ^ "/" ^ bs ^ "\n")
                else if n <> 0 andalso m = 0 andalso a < 0
                then print ("~" ^ ns ^ "/" ^ bs ^ "\n")
                else if n <> 0 andalso m = 0 
                then print (ns ^ "/" ^ bs ^ "\n")
                else if a < 0 
                then print ("~" ^ ms ^ "\n")
                else print (ms ^ "\n")
            end
        fun convergent (i, n, d, h_1, k_1, h_2, k_2) = 
              if i <> 0 andalso ((h_1 > (maxInt - h_2) div i)
                  orelse (k_1 > (maxInt - k_2) div i))
              then (h_1, k_1)  
              else if n = 0
              then (i * h_1 + h_2, i * k_1 + k_2) 
              else convergent (d div n, d mod n, n,
                               i * h_1 + h_2, i * k_1 + k_2, h_1, k_1) 
        fun add ((a, b), (c, d)) = let
            val la = Int.toLarge a and lb = Int.toLarge b
            val lc = Int.toLarge c and ld = Int.toLarge d 
            val m = la * ld + lb * lc and n = lb * ld 
            in 
                if b = d 
                then fromIntPair (a + c, b)
                else fromLargePair (convergent (m div n, m mod n, n, 1, 0, 0, 1))
            end 
        fun sub ((a, b), (c, d)) = let
            val la = Int.toLarge a and lb = Int.toLarge b
            val lc = Int.toLarge c and ld = Int.toLarge d  
            val m = la * ld - lb * lc and n = lb * ld
            in  
                if b = d
                then fromIntPair (a - c, b)
                else if m < 0 
                then neg (fromLargePair (convergent (~m div n, ~m mod n, n, 1, 0, 0, 1)))
                else if m > 0
                then fromLargePair (convergent (m div n, m mod n, n, 1, 0, 0, 1))
                else (0, 1)
            end
        fun mul ((a, b), (c, d)) = let
            val la = Int.toLarge a and lb = Int.toLarge b
            val lc = Int.toLarge c and ld = Int.toLarge d 
            val m = la * lc and n = lb * ld 
            in  
                fromLargePair (convergent (m div n, m mod n, n, 1, 0, 0, 1))
            end
        fun op + ((a, b), (c, d)) = 
              if a < 0 andalso c < 0 
              then neg (add ((~a, b), (~c, d)))
              else if a < 0
              then sub ((c, d), (~a, b))
              else if c < 0
              then sub ((a, b), (~c, d))
              else add ((a, b), (c, d))
        fun op - ((a, b), (c, d)) = 
              if a < 0 andalso c < 0 
              then sub ((~c, d), (~a, b))
              else if a < 0
              then neg (add ((~a, b), (c, d)))
              else if c < 0
              then add ((a, b), (~c, d))
              else sub ((a, b), (c, d))
        fun op * ((a, b), (c, d)) = 
              if a < 0 andalso c < 0  
              then mul ((~a, b), (~c, d))
              else if a < 0
              then neg (mul ((~a, b), (c, d)))
              else if c < 0
              then neg (mul ((a, b), (~c, d)))
              else mul ((a, b), (c, d))
        fun op / ((a, b), (c, d)) =
              if a < 0 andalso c < 0  
              then mul ((~a, b), (d, ~c))
              else if a < 0
              then neg (mul ((~a, b), (d, c)))
              else if c < 0
              then neg (mul ((a, b), (d, ~c)))
              else mul ((a, b), (d, c))
        fun succ a = add (a, one)
        fun pred a = sub (a, one)
        fun ~ a = neg a
    end
    
  6. ^ 筛法基于数组的实现:
    fun prime n = let
        val sieve = Array.array (n + 1, true);
        fun markComposite (j, i) =
              if j > n then () 
              else (Array.update (sieve, j, false); 
                    markComposite (j + i, i))
        fun iterate i =
              if i * i > n then ()
              else if Array.sub (sieve, i)
              then (markComposite (i * i, i);
                    iterate (i + 1))
              else iterate (i + 1)
        fun generate (acc, i) = 
              if i < 2 then acc
              else if Array.sub (sieve, i) 
              then generate (i :: acc, i - 1)
              else generate (acc, i - 1) 
        in 
            if n < 2 then [] 
            else (iterate 2;
                  generate ([], n))
        end
    
  7. ^ 部份映射函数的实际实现:
    fun mapPartial pred l = let
        fun mapp ([], l) = rev l
          | mapp (x :: r, l) = (case (pred x)
              of SOME y => mapp (r, y :: l)
               | NONE => mapp (r, l)
                 (* end case *))
        in
            mapp (l, [])
        end
    
  8. ^ 汉明数进一步性质演示代码:
    fun printIntList (l: int list) =
        print ((String.concatWith " " (map Int.toString l)) ^ "\n");
    
    fun diff (p, q) = let
        fun revDiff (acc, p, q) =
              if not (null p) andalso not (null q) then
                  if hd p < hd q
                  then revDiff ((hd p) :: acc, tl p, q)
                  else if hd p > hd q
                  then revDiff (acc, p, tl q)
                  else revDiff (acc, tl p, tl q)
              else if null q 
              then List.revAppend (p, acc)
              else acc
        in
            if (null p) then []
            else if (null q) then p
            else rev (revDiff ([], p, q))
        end;
    
    fun Hamming_number n = let
        fun merge (p, q) = let
            fun revMerge (acc, p, q) =
                  if not (null p) andalso not (null q) then
                      if hd p < hd q
                      then revMerge ((hd p) :: acc, tl p, q)
                      else if hd p > hd q
                      then revMerge ((hd q) :: acc, p, tl q)
                      else revMerge ((hd p) :: acc, tl p, tl q)
                  else if null p 
                  then List.revAppend (q, acc)
                  else List.revAppend (p, acc)
            in
                if (null p) then q
                else if (null q) then p
                else rev (revMerge ([], p, q))
            end
        fun mul m x = (x * m)             
        fun generate l = let
            fun listMul m = map (mul m) l
            fun mergeMul (m, i) = merge (listMul m, i)
            in
                printIntList (listMul 2);
                printIntList (diff (listMul 3, listMul 2));
                printIntList (diff (listMul 5, merge (listMul 2, listMul 3)));  
                foldl mergeMul [] [2, 3, 5]
            end
        val count = ref 1;
        fun iterate (acc, l) =
              if (hd l) > (n div 2) then merge (l, acc)
              else (print ("round " ^ (Int.toString (!count)) ^ " for " ^
                           (Int.toString(length l)) ^ " number(s)\n");
                    count := !count + 1;
                    iterate (merge (l, acc), generate l))
        in
            if n > 0 then iterate ([], [1]) else []
        end;
    
    - val l = Hamming_number 400;
    round 1 for 1 number(s)
    2
    3
    5
    round 2 for 3 number(s)
    4 6 10
    9 15
    25
    round 3 for 6 number(s)
    8 12 18 20 30 50
    27 45 75
    125
    round 4 for 10 number(s)
    16 24 36 40 54 60 90 100 150 250
    81 135 225 375
    625
    round 5 for 15 number(s)
    32 48 72 80 108 120 162 180 200 270 300 450 500 750 1250
    243 405 675 1125 1875
    3125
    round 6 for 21 number(s)
    64 96 144 160 216 240 324 360 400 486 540 600 810 900 1000 1350 1500 2250 2500 3750 6250
    729 1215 2025 3375 5625 9375
    15625
    round 7 for 28 number(s)
    128 192 288 320 432 480 648 720 800 972 1080 1200 1458 1620 1800 2000 2430 2700 3000 4050 4500 5000 6750 7500 11250 12500 18750 31250
    2187 3645 6075 10125 16875 28125 46875
    78125
    round 8 for 36 number(s)
    256 384 576 640 864 960 1296 1440 1600 1944 2160 2400 2916 3240 3600 4000 4374 4860 5400 6000 7290 8100 9000 10000 12150 13500 15000 20250 22500 25000 33750 37500 56250 62500 93750 156250
    6561 10935 18225 30375 50625 84375 140625 234375
    390625
    val l = [1,2,3,4,5,6,8,9,10,12,15,16,...] : int list
    - val h = List.filter (fn x => (x <= 400)) l;
    val h = [1,2,3,4,5,6,8,9,10,12,15,16,...] : int list
    - val _ = print ((Int.toString (length h)) ^ " numbers from " ^ 
                     (Int.toString (length l)) ^ " numbers\n");
    61 numbers from 165 numbers
    
  9. ^ 列表长度函数的实际实现:
    fun length l = let
        (* fast add that avoids the overflow test *)
        val op + = Int.fast_add
        fun loop (n, []) = n
    	  | loop (n, [_]) = n + 1
    	  | loop (n, _ :: _ :: l) = loop (n + 2, l)
        in
    	    loop (0, l)
        end
    
  10. ^ 划分函数的实际实现:
    fun partition pred l = let
        fun loop ([], trueList, falseList) =
              (rev trueList, rev falseList)
          | loop (h :: t, trueList, falseList) =
              if pred h then loop (t, h :: trueList, falseList)
              else loop (t, trueList, h :: falseList)
        in
    	    loop (l, [], [])
        end
    
  11. ^ 分解成4元素子列表的函数:
        fun generate (acc, []) = acc
          | generate (acc, [x]) = [x] :: acc
          | generate (acc, [x, y]) =
              if x <= y then [x, y] :: acc else [y, x] :: acc
          | generate (acc, [x, y, z]) = 
              if x <= y then
                  if y <= z then [x, y, z] :: acc
                  else if x <= z then [x, z, y] :: acc
                  else [z, x, y] :: acc
              else 
                  if x <= z then [y, x, z] :: acc
                  else if y <= z then [y, z, x] :: acc
                  else [z, y, x] :: acc
          | generate (acc, w :: x :: y :: z :: xs) = let
            val (w, x) = 
                  if w <= x then (w, x) else (x, w)
            val (w, x, y) =
                  if x <= y then (w, x, y)
                  else if w <= y then (w, y, x)
                  else (y, w, x)
            val (w, x, y, z) =
                  if y <= z then (w, x, y, z)
                  else if x <= z then (w, x, z, y)
                  else if w <= z then (w, z, x, y)
                  else (z, w, x, y)
            in
                generate ([w, x, y, z] :: acc, xs)
            end
    
  12. ^ 归并排序算法的自顶向下实现:
    fun mergeSort l = let
        fun sort ([], _) = []
          | sort ([x], _) = [x]
          | sort ([x, y], _) =
              if x <= y then [x, y] else [y, x]
          | sort ([x, y, z], _) =
              if x <= y then
                  if y <= z then [x, y, z]
                  else if x <= z then [x, z, y] 
                  else [z, x, y]
              else 
                  if x <= z then [y, x, z]
                  else if y <= z then [y, z, x]
                  else [z, y, x] 
          | sort (l, n) = let
            val m = n div 2
            fun split (l, acc, i) = 
                  if i = 0 then (rev acc, l)
                  else split (tl l, (hd l) :: acc, i - 1)
            fun merge (p, q) = let
                fun revMerge (acc, p, q) =
                      if not (null p) andalso not (null q) then
                          if (hd p) <= (hd q)
                          then revMerge ((hd p) :: acc, tl p, q)
                          else revMerge ((hd q) :: acc, p, tl q)
                      else if null p 
                      then List.revAppend (q, acc)
                      else List.revAppend (p, acc)
                in
                    rev (revMerge ([], p, q))
                end
            val (ls, rs) = split (l, [], m)
            in
                merge (sort (ls, m), sort (rs, n - m))
            end
        in
            sort (l, length l)
        end
    
  13. ^ 堆建造函数heapify使用siftup函数的实现:
        fun siftup i = let
            val v = get i
            fun loop i = let
                val j = (i - 1) div 2 
                in
                    if i <= 0 orelse (get j) >= v
                    then set i v
                    else (set i (get j); loop j)
                end
            in
                loop i    
            end  
        fun heapify () = let
            fun loop i =
                  if i > (len - 1) then ()
                  else (siftup i; loop (i + 1))
            in
                loop 1
            end
    
  14. ^ 排序算法的简单测试代码:
    fun printIntList (l: int list) =
        print ((String.concatWith " " (map Int.toString l)) ^ "\n")
    
    fun shuffle (l, n) = let
        fun split (l, acc, i) = 
              if i = 0 then (acc, l)
              else split (tl l, (hd l) :: acc, i - 1)
        fun zip (acc, p, q, b) =
              if null p then List.revAppend (q, acc)
              else if null q then List.revAppend (p, acc)
              else if b then zip ((hd p) :: acc, tl p, q, false)
              else zip ((hd q) :: acc, p, tl q, true)
        val (p, q) = split (l, [], n div 2)
        in
            if (null l) then tl [0]
            else zip ([], p, q, true)
        end
        
    fun testsort f n = let
        fun loop (acc, i) =
              if (i <= 0) then acc
              else loop (i :: acc, i - 1)
        val sl = shuffle (loop ([], n), n)
        val ssl = shuffle (sl, n) 
        in
            print ("source list is: ");
            printIntList ssl; 
            print ("result list is: ");
            printIntList (f ssl)
        end
    

参见[编辑]

延伸阅读[编辑]

引用[编辑]

  1. ^ 1.0 1.1 1.2 1.3 Michael J. Gordon, Arthur J. Milner, Christopher P. Wadsworth. Edinburgh LCF: A Mechanised Logic of Computation. Lecture Notes in Computer Science, Vol. 78. Springer-Verlag, New York, NY, USA. 1979. ML is a general purpose programming language. It is derived in different aspects from ISWIM, POP2 and GEDANKEN, and contains perhaps two new features. First, it has an escape and escape trapping mechanism, well-adapted to programming strategies which may be (in fact usually are) inapplicable to certain goals. Second, it has a polymorphic type discipline which combines the flexibility of programming in a typeless language with the security of compile-time type checking (as in other languages, you may also define your own types, which may be abstract and/or recursive); this is what ensures that a well-typed program cannot perform faulty proofs. 
  2. ^ 2.0 2.1 2.2 M. Gordon, R. Milner, L. Morris, M. Newey, C. Wadsworth. A Metalanguage for Interactive Proof in LCF (PDF). 1978. ML is a higher-order functional programming language in the tradition of ISWIM, PAL, POP2 and GEDANKEN, but differs principally in its handling of failure and, more so, of types. 
  3. ^ 3.0 3.1 Bruce A. Tate, Fred Daoud, Ian Dees, Jack Moffitt. 3. Elm. Seven More Languages in Seven Weeks (PDF) Book version: P1.0-November 2014. The Pragmatic Programmers, LLC. 2014: 97, 101. ISBN 978-1-941222-15-7. On page 101, Elm creator Evan Czaplicki says: 'I tend to say "Elm is an ML-family language" to get at the shared heritage of all these languages.' ["these languages" is referring to Haskell, OCaml, SML, and F#.] 
  4. ^ 4.0 4.1 Troels Henriksen, Niels G. W. Serup, Martin Elsman, Fritz Henglein, Cosmin Oancea. Futhark: Purely Functional GPU-Programming with Nested Parallelism and In-Place Array Updates (PDF). Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation. PLDI 2017. ACM. 2017. 
  5. ^ Lennart Augustsson英语Lennart Augustsson, Thomas Johnsson. The Chalmers Lazy-ML Compiler. 1989. 
  6. ^ 6.0 6.1 Programming language for "special forces" of developers., Russian Software Development Network: Nemerle Project Team, [January 24, 2021] 
  7. ^ 7.0 7.1 Adam Chlipala. Ur/Web: A Simple Model for Programming the Web (PDF). MIT / Association for Computing Machinery (ACM). January 2015. 
  8. ^ 8.0 8.1 Robin Milner. A theory of type polymorphism in programming. (PDF). 1978.  Journal of Computer and System Sciences, 17(3):348–375.
  9. ^ Robin Milner. How ML Evolved (PDF). Polymorphism—The ML/LCF/Hope Newsletter,Vol. 1, No. 1. 1982. 
  10. ^ Luca Cardelli英语Luca Cardelli. ML under VMS (PDF). 1982. 
  11. ^ Luca Cardelli. Differences between VAX and DEC-10 ML (PDF). 1982. 
  12. ^ Lynn H. Quam, Whitfield Diffle. Stanford LISP 1.6 Manual (PDF). 
  13. ^ Luca Cardelli英语Luca Cardelli. The Functional Abstract Machine. 1983.  Bell Labs Technical Report TR-107.
    Luca Cardelli. Compiling a functional language. 1984.  In Proceedings of the 1984 ACM Symposium on LISP and Functional Programming, pages 208–217, New York, NY, USA. ACM.
  14. ^ Kevin Mitchell, Alan Mycroft. The Edinburgh Standard ML Compiler (PDF). 1985. 
  15. ^ 15.0 15.1 Guy Cousineau, Gérard Huet英语Gérard Huet. The CAML primer Version 2.6.1. 1990.  RT-0122, INRIA. pp.78.
    Pierre Weis, Maria Virginia Aponte, Alain Laville, Michel Mauny, Ascander Suarez. The CAML reference manual Version 2.6.1. 1990.  [Research Report] RT-0121, INRIA. pp.491.
  16. ^ G. Cousineau, M. Gordon, G. Huet, R. Milner, L. C. Paulson, C. Wadsworth. The ML Handbook, Version 6.2. Internal document. Project Formel, INRIA. July 1985. 
    Christoph Kreitz, Vincent Rahli. Introduction to Classic ML (PDF). 2011. This handbook is a revised edition of Section 2 of ‘Edinburgh LCF’, by M. Gordon, R. Milner, and C. Wadsworth, published in 1979 as Springer Verlag Lecture Notes in Computer Science no 78. ……The language is somewhere in between the original ML from LCF and standard ML, since Guy Cousineau added the constructors and call by patterns. This is a LISP based implementation, compatible for Maclisp on Multics, Franzlisp on VAX under Unix, Zetalisp on Symbolics 3600, and Le Lisp on 68000, VAX, Multics, Perkin-Elmer, etc... Video interfaces have been implemented by Philippe Le Chenadec on Multics, and by Maurice Migeon on Symbolics 3600. The ML system is maintained and distributed jointly by INRIA and the University of Cambridge. 
  17. ^ 17.0 17.1 A History of Caml. The Formel team became interested in the ML language in 1980-81. ……Gérard Huet decided to make the ML implementation compatible with various Lisp compilers (MacLisp, FranzLisp, LeLisp, ZetaLisp). This work involved Guy Cousineau and Larry Paulson. ……Guy Cousineau also added algebraic data types and pattern-matching, following ideas from Robin Milner ……. At some point, this implementation was called Le_ML, a name that did not survive. It was used by Larry Paulson to develop Cambridge LCF and by Mike Gordon for the first version of HOL ……. ……
    Our main reason for developing Caml was to use it for sofware development inside Formel. Indeed, it was used for developing the Coq system ……. We were reluctant to adopt a standard that could later prevent us from adapting the language to our programming needs. ……We did incorporate into Caml most of the improvements brought by Standard ML over Edinburgh ML. ……The first implementation of Caml appeared in 1987 and was further developed until 1992. It was created mainly by Ascander Suarez. ……
    In 1990 and 1991, Xavier Leroy designed a completely new implementation of Caml, based on a bytecode interpreter written in C. Damien Doligez provided an excellent memory management system. ……In 1995, Xavier Leroy released Caml Special Light, which improved over Caml Light in several ways. In 1995, Xavier Leroy released Caml Special Light, which improved over Caml Light in several ways. First, an optimizing native-code compiler was added to the bytecode compiler. ……Second, Caml Special Light offered a high-level module system, designed by Xavier Leroy and inspired by the module system of Standard ML. ……Didier Rémy, later joined by Jérôme Vouillon, designed an elegant and highly expressive type system for objects and classes. This design was integrated and implemented within Caml Special Light, leading to the Objective Caml language and implementation, first released in 1996 and renamed to OCaml in 2011.
     
  18. ^ Michael J. C. Gordon英语Michael J. C. Gordon. From LCF to HOL: a short history. 1996 [2007-10-11]. 
  19. ^ Robin Milner. A Proposal for Standard ML (PDF). 1983. 
  20. ^ R. M. Burstall, J. A. Goguen. The semantics of CLEAR, a specification language. 1977. 
    Donald Sannella. Semantics, Implementation and Pragmatics of Clear, a Program Specification Language. 1982. 
  21. ^ Rod Burstall英语Rod Burstall, D.B. MacQueen, D.T. Sannella英语Don Sannella. Hope: An Experimental Applicative Language (PDF). 1980.  Conference Record of the 1980 LISP Conference, Stanford University, pp. 136-143.
  22. ^ R.M. Burstall. Proving properties of programs by structural induction (PDF). 1968. 
  23. ^ R.M. Burstall, J. Darlington. A transformation system for developing recursive programs. Journal of the Association for Computing Machinery: 24(1):44–67. 1977. 
  24. ^ Luca Cardelli. ML under Unix (PDF). 1983. 
    Luca Cardelli. ML under Unix, Pose 4 (PDF). 1984. 
  25. ^ David MacQueen. Modules for Standard ML. LFP '84 Proceedings of the 1984 ACM Symposium on LISP and functional programming. August 1984: 198–207. 
  26. ^
  27. ^ Edinburgh ML (Core Language) (SML '90), Version 4.1.02. 1991. 
    The Edinburgh Standard ML Library (SML '90). 1993. 
  28. ^ Andrew W. Appel英语Andrew Appel, David MacQueen. A Standard ML compiler. 1987. 
    David Macueen. An Implementation of Standard ML Modules. 1988. 
  29. ^ Andrew W. Appel英语Andrew Appel, David MacQueen. Standard ML of New Jersey. 1991. 
    Standard ML of New Jersey, Version 0.93. 1993. 
  30. ^ Robin Milner, Mads Tofte, Robert Harper. The Definition of Standard ML (PDF). The MIT Press, Cambridge, MA, USA. 1990. 
  31. ^ Robin Milner, Mads Tofte, Robert Harper, David MacQueen. The Definition of Standard ML (Revised) (PDF). The MIT Press, Cambridge, MA, USA. 1997. 
  32. ^ Lars Birkedal, Nick Rothwell, Mads Tofte, David N. Turner. The ML Kit, Version 1. 1993. 
  33. ^ The release of the ML Kit Version 1. 1993. 
  34. ^ G. Cousineau, P.-L. Curien, M. Mauny. The categorical abstract machine. 1985.  LNCS, 201, Functional programming languages computer architecture, pp.~50-64.
    Michel Mauny, Ascánder Suárez. Implementing functional languages in the Categorical Abstract Machine (PDF). 1986.  LFP '86: Proceedings of the 1986 ACM conference on LISP and functional programming, Pages 266–278.
  35. ^ Xavier Leroy. The ZINC experiment : an economical implementation of the ML language. 1990.  RT-0117, INRIA.
  36. ^ Xavier Leroy英语Xavier Leroy. The Caml Light system Release 0.74, documentation and user's guide. 1997. 
  37. ^ Xavier Leroy. Manifest types, modules, and separate compilation (PDF). Principles of Programming Languages. 1994. 
  38. ^ Didier Rémy. Type inference for records in a natural extension of ML. Research Report RR-1431, INRIA. 1991. 
    Didier Rémy, Jérôme Vouillon. Objective ML: a simple object-oriented extension of ML (PDF). 1997. 
    Didier Rémy, Jérôme Vouillon. Objective ML: An effective object-oriented extension to ML (PDF). 1998. 
  39. ^ Xavier Leroy. The Objective Caml system release 1.07, Documentation and user's manual. 1997. 
  40. ^ Samuel Horsley英语Samuel Horsley FRS, "Κόσκινον Ερατοσθένους or The Sieve of Eratosthenes." Being an account of his method of finding all the Prime Numbers, Philosophical Transactions (1683–1775), Vol. 62. (1772), pp. 327–347.
  41. ^ Edsger W. Dijkstra, 17. An exercise attributed to R. W. Hamming, A Discipline of Programming, Prentice-Hall: 129–134, 1976, ISBN 978-0132158718 
    Edsger W. Dijkstra, Hamming's exercise in SASL (PDF), 1981, Report EWD792. Originally a privately circulated handwritten note .
  42. ^ David Turner. Lazy evaluation and infinite lists. An Overview of Miranda. Computing Laboratory, University of Kent. 1986. 
    CS3110. Streams and Laziness. Cornell University. 2018. 
  43. ^ CS3110. Continuations and CPS Conversion. Cornell University. 2012. 
  44. ^ Stephen Weeks. Whole-Program Compilation in MLton (PDF). Workshop on ML. 2006. 
  45. ^ HaMLet. 
  46. ^ "OCaml is an industrial strength programming language supporting functional, imperative and object-oriented styles". Retrieved on January 2, 2018.
  47. ^ Alice. 
  48. ^ Karl Crary. CM-Lex and CM-Yacc. Carnegie Mellon University. 2017. 
  49. ^ Amulet. amulet.works. [2021-01-12]. 

外部链接[编辑]