ML语言

维基百科,自由的百科全书
跳到导航 跳到搜索
ML
编程范型多范型函数式指令式
設計者Robin Milner & 爱丁堡大学其他人
发行时间1973年,​48年前​(1973
穩定版本
Standard ML '97
(1997年,​24年前​(1997
型態系統类型推论静态类型强类型
衍生副語言
Standard ML, OCaml, F#
啟發語言
ISWIM
影響語言
ClojureCoqCyclone英语Cyclone (programming language)C++ElmF#F*HaskellIdrisMirandaNemerleOCamlOpa英语Opa (programming language)ErlangRustScalaStandard MLUr

ML(Meta Language:元语言)是一个通用的函數式編程语言。ML是静态作用域的。ML知名于使用了多态Hindley-Milner类型系统,它自动的指定多数表达式英语Expression (computer science)类型,不要求显式的类型标注,而且能够确保类型安全,已经正式证明了有良好类型的ML程序不会导致运行时间类型错误[1]

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

概述[编辑]

ML特性包括:传值调用的求值策略头等函数,带有垃圾收集的自动内存管理参数多态静态类型类型推论代数数据类型英语Algebraic data type模式匹配英语Pattern matching异常处理

不同于Haskell,ML与大多数编程语言一样使用及早求值,也就是说所有的子表达式总是被求值,尽管可以通过使用闭包来完成惰性求值。因此可以像Haskell那样建立和使用无限串流,但是它们的表达是间接的。

ML是由爱丁堡大学Robin Milner及他人在二十世纪七十年代早期开发的[2],它的语法是从ISWIM得到的灵感。ML是为了帮助在LCF英语Logic for Computable Functions定理证明器中寻找证明策略而构想出来的,LCF的语言是“pplambda”,联合了一阶逻辑演算和有类型的多态λ演算,拥有ML作为元语言。

今天在ML家族中有好几种语言:两种主要的方言是Standard MLCaml,其他的包括F#,它是针对Microsoft .NET平台的开放研究项目。ML中的思想影响了众多的语言,例如HaskellCyclone英语Cyclone (programming language)NemerleATS英语ATS (programming language)[3]Elm[4]

ML的实力大多被用于语言设计和操作(编译器、分析器、定理证明器),但是它作为通用语言也被用于生物信息和财务系统等领域。

例子[编辑]

下列例子使用了Standard ML的语法。其他ML方言比如OCamlF#在细微方面有所不同。

阶乘[编辑]

阶乘函数用纯ML可表达为:

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

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

这里展示的定义中有的部份,是可选的对这个函数的“类型”的描述。E : t表示法可以被读作表达式E有类型t。例如,实际参数n被指定了整数类型(int),而fac (n : int),应用fac于整数n的结果,也是整数类型。函数fac作为一个整体从而有着“从整数到整数的函数”类型(int -> int),就是说,fac接受一个证书作为实际参数并返回一个整数结果。凭借类型推论,这些类型标注(annotation)可以省略而由编译器来推导出来。不用类型标这个例子可重写为如下:

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

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

这个递归函数的实现不保证能够终止,因为负数实际参数会导致递归调用的无限降链条件。更健壮的实现会在递归前检查实际参数为非负数,如下这样:

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

有问题的情况(在n是负数的时候)展示了ML的异常系统的使用。

这个函数通过将它的内部循环写为尾递归风格而进一步改进,使得调用栈不需要与函数调用的数目成比例的增长。这是通过向内部函数增加额外的“加速器”形式参数来实现的,最终得到:

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

列表反转[编辑]

下列函数“反转”一个列表中的元素。更准确的说,它返回其元素相较于给定列表是反转次序的一个新列表:

fun reverse [] = []
  | reverse (x::xs) = (reverse xs) @ [x]

这个反转的实现,尽管正确而清楚,确是低效的,执行要求二次时间。这个函数可以重写为下列更高效但不易读的风格,以线性时间执行:

fun reverse xs = let
  fun rev [] acc = acc
    | rev (hd::tl) acc = rev tl (hd::acc)
in
  rev xs []
end

值得注意的是,这个函数是参数多态的一个例子。就是说它可以接受其元素有任何类型的列表,并返回相同类型的列表。

模块[编辑]

模块是ML用于构造大型项目和库的系统。一个模块构成自一个签名(signature)文件和一个或多个结构文件。签名文件指定要实现的API(就像C语言头文件,或Java接口文件)。结构实现这个签名(就像C语言源文件或Java类文件)。例如,下列定义一个算术签名和它的使用有理数的实现:

signature ARITH =
sig
        type t;
        val zero : t;

        val succ : t -> t ;
        val sum : t * t -> t;
end
structure Rational : ARITH =
struct
        datatype t = Rat of int * int;
        val zero = Rat(0,1);
        fun succ(Rat(a,b)) = Rat( a+b , b  );
        fun sum (Rat(a,b),  Rat(c,d)) = Rat(a*d+ c*b  , b*d) : t ;
end

解释器通过use命令导入它们。只允许通过签名函数同实现进行交互,例如不可以直接通过这个代码建立Rat数据对象。结构块对外部隐藏所有实现细节。

ML的标准库被实现为这种方式的模块。

书写一个语言解释器[编辑]

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

  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 chkEval e = (ignore (typeOf e); eval e) (* 将在类型错误时发起Err *)

在正确类型的和无正确类型上运行的例子:

- val e1 = Add(Int(1), Int(2)); (* 正确的类型 *)
val e1 = Add (Int 1,Int 2) : exp
- chkEval e1;
val it = Int 3 : exp

- val e2 = Add(Int(1),True); (* 不正确的类型 *)
val e2 = Add (Int 1,True) : exp
- chkEval e2;

uncaught exception Err

参见[编辑]

引用[编辑]

  1. ^ Robin Milner. A theory of type polymorphism in programming. Journal of Computer and System Sciences, 17(3):348–375, 1978.
  2. ^ Gordon, Michael J. C. From LCF to HOL: a short history. 1996 [2007-10-11]. 
  3. ^ Programming language for "special forces" of developers., Russian Software Development Network: Nemerle Project Team, [January 24, 2021] 
  4. ^ Tate, Bruce A.; Daoud, Fred; Dees, Ian; Moffitt, Jack. 3. Elm. Seven More Languages in Seven Weeks 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#.] 
  5. ^ "OCaml is an industrial strength programming language supporting functional, imperative and object-oriented styles". Retrieved on January 2, 2018.

延伸阅读[编辑]

  • The Definition of Standard ML (PDF).  Robin Milner, Mads Tofte, Robert Harper, MIT Press 1990; (revised edition adds author David MacQueen), MIT Press 1997, ISBN 0-262-63181-4.
  • Commentary on Standard ML, Robin Milner, Mads Tofte, MIT Press 1997, ISBN 0-262-63137-7.
  • ML for the Working Programmer, Lawrence Paulson, Cambridge University Press 1991, 1996, ISBN 0-521-57050-6.
  • Harper, Robert. Programming in Standard ML (PDF). Carnegie Mellon University. 2011. 
  • Elements of ML Programming, Jeffrey D. Ullman, Prentice-Hall 1994, 1998, ISBN 0-13-790387-1.

外部链接[编辑]