ML

来自站长百科
跳转至: 导航、​ 搜索

ML 是一个通用的函数式编程语言,它是由爱丁堡大学Robin Milner及他人在二十世纪七十年代晚期开发的。它的语法是从ISWIM得到的灵感。作为元语言ML是为了帮助在LCF定理证明机中寻找证明策略而构想出来的。(之前的元语言是pplambda,它联合了一阶逻辑演算、多态及Λ演算)。它使用了Hindley-Milner类型推论算法来推测大多数值的类型,而不需要四处使用注解。

简介[ ]

ML一般被归为非纯函数式编程语言,因为它允许副作用和指令式编程。这一点和纯函数式编程语言??例如Haskell??很不一样。   

ML特性有惰性求值的求值策略,一阶类型函数, 带有垃圾收集的自动内存管理, 参数多态,静态数据类型,类型推断,代数数据类型,模式匹配和异常处理。   

不像Haskell,ML使用热情求值,也就是说所有的子表达式总是被求值。导致的一个结果是你不能使用无穷表。然而,惰性求值产生的无穷表可以通过使用匿名函数来模拟。   

今天在ML家族中有好几种语言:两种主要的方言是Standard ML和Caml,其他的包括F# - 针对Microsoft .NET平台的开放研究项目。 ML中的思想影响了众多的语言,例如Haskell,Cyclone和Nemerle。 ML的实力大多被用于语言设计和操作(编译器、分析器、定理证明机), 但是它作为通用语言也被用于生化,金融系统,和宗谱数据库,一个P2P的客户/服务器程序等等。   

ML可以算一种具备命令式语言特点的函数型语言,或者说面向函数的命令型语言。和Lisp一样,ML具有非常灵活的函数功能。例如一个表达式的值可能就是一个函数,这个函数可以被作为参数传递给另一个函数,或者函数的返回值就是一个函数。同时和Algol类的语言比较接近的是,ML的语法象命令型的,而且用起来象用Algol家族的很多比较新的后代们一样方便。而且ML有并行扩展,可以用来写并行系统;甚至还有面向对象扩展。   

John C. Mitchell在他的Concepts in Programming Langugaes一书中使用ML来展示Algol类语言、Lisp类语言、以及并行语言和面向对象语言中的概念。   

ML是Robin Milner主管LCF项目时设计的。LCF项目是受Dana Scott给出的一组逻辑原则启发而设立的,致力于开发一种“可计算函数逻辑”(Logic of Computable Functions)。Robin Milner的目标是构造一个方便实用的系统,来自动的或者半自动的证明函数程序中一些有趣的性质。他的LCF项目于1970年在Standford开始,并于1980年代在Edinburge继续进行。期间取得了很多重要进展,并且激发了相关领域的一系列研究工作。   

ML是作为LCF项目的元语言(Meta Language)设计的,这也是其名字的来历。它的最初用途是写一些可以生成数学证明的程序。今天,大多数著名的推理系统都是用ML写的。   

目前ML有两个发展分支:Standard MLCaml。   

大多数SML编译器的行为方式都是交互式的:用户一条一条输入语句,编译器一一给出反馈。看起来象Logo或者Basic解释器一样。但是其实用户输入的程序是被先编译再执行的(其中细节大家可以从SML/NJ编译器的相关文档和论文中找到)。

环境配置[ ]

在Windows环境下使用Emacs作为ML的集成开发环境。下面关于EmacsSMLWindows下的配置说明其实同样适合于各种Unix类操作系统)。这里有一副抓图:在左边的frame中编辑好SML源程序后,按下C-c C-b,程序就交付给运行在右边frame中的SML编译器了。你也可以直接在右边的frame中交互式的输入SML程序。   

为了配置这个环境我安装了GNU Emacs for Windows(你也可以用XEmacs for Windows)、SML编译器SML/NJ(你也可以用其他编译器,比如Moscow ML,Poly/ML)、Emacs的SML mode。安装和配置步骤如下:   

下载和安装GNU Emacs for Windows   

下载和安装SML New Jersey编译器   

下载和安装Emacs的SML major mode。具体的方法如下:   

在你的Emacs安装目录(例如F:\Program Files\emacs-21.3)下建一个子目录叫site-lisp。如果已经有了就不用建了。   

在其中建一个子目录叫sml-mode   

将你下载的SML major mode压缩包解开,将其中所有.el文件拷贝到site-lisp/sml-mode子目录下   

编辑site-lisp中的site-start.el,加入两行:   

(add-to-list 'load-path "F:/Program Files/emacs-21.3/site-lisp/sml-mode")   (load "sml-mode-startup")   

在PATH环境变量里包含SML编译器所在的目录。我的是f:\sml\bin。   

启动Emacs后,敲 M-x run-sml就可以在Emacs中启动一个SML交互环境。   

如果用 M-x sml-mode就将当前buffer的major mode设置为sml-mode,你会发现其中的SML代码被语法高亮显示了。如果没有语法高亮,你可以在Emacs的配置文件(对于Windows版本的GNU Emacs和XEmacs而言是C:\.emacs,对Unix版本的是~/.emacs)中加入一行:   

Syntax highlight   

(global-font-lock-mode t)

编程风格[ ]

通常大家学习编程都是从命令式语言开始的。和函数示语言不同,命令式语言以语句作为基本单位。Algol家族的所有语言都是命令式语言,ML也不例外。因此学习ML不像学习Scheme那样需要完全转换一套思路。但是ML继承了函数式语言的很多特征,而且也有自己的一些特点。


线性数据结构   

程序中总要定义数据结构。常用的定长线性结构包括:PascalrecordCstructC++Javaclass。在ML中我们通常用tuple,即用圆括号括起来的,用逗号分隔的若干项元素。   

Tuple是个线性结构,可以用整数索引。比如   #1(1, 2.0, "apple") = 1   #2(1, 2.0, "apple") = 2.0   #3(1, 2.0, "apple") = "apple"   

和Algol类语言的数组不同的是,tuple中各个元素的类型可以不一样。   

C++boost模板库中提供了一个模板tuple,模仿ML/Scheme的tuple,使C++程序员可以将不同类型的数据组织成一个便于访问的线性结构。


函数的嵌套定义   

ML和大多数Algol类语言一样支持函数的嵌套定义(包括Algol 60、Algol 68和Pascal,但是C是例外)。   如果函数A和函数B互相嵌套调用(indirect recursion),则源程序中可以将B的函数体定义在 A的函数体内,或者A的定义在B的函数体内。具体采用那一种,要看外界是调用A还是B。   函数addqueen和其内部函数try就是这样的例子。显然addqueen是要被外部调用的。


用尾部递归(tail recursion)代替循环   

如果用Algol类语言(例如 Pascal和C)来写函数addqueen,其中需要一个循环,从某行的第一个位置开始,判断如果在这个位置上放一个皇后是否可以使得其不和前面已经放上的皇后冲突,而且后面还可以继续放满皇后。而ML中这个循环用递归函数tryARow表示。


纯表达式(pure expression)风格   

大多数Algol类语言对机器的抽象是以内存为中心的,即变量对象(object)对应内存中的存储区域,赋值语句对应机器的访存操作,所以程序中有大量的赋值语句。ML也支持赋值,但是通常建议采取的风格是类似Lisp和Scheme的纯表达式风格,避免赋值操作。   例如如果用C来描述n皇后问题,通常我们会设计一个数据结构描述棋盘(和ML程序一样),然后定义这个数据结构的一个实例(可能是个全局变量)。算法的主要工作是通过赋值修改这个实例的内容。   而例子中的ML代码中经典的一段是函数place。这是修改棋盘数据结构的代码。但是并没有使用赋值,而是产生了一个新的数据结构实例,其内容和参数略有区别(放上了一个新的皇后)。   

纯表达式的使用要求程序员先对程序考虑得非常细致才能动笔(动手?),因此使得程序逻辑更加清晰。(这和literate programming的思想是一致的。)但是目前的硬件机器是以内存为中心设计的,所以纯表达式语言的实现(编译器解释器)的效率依靠于设计者多费心思。ML就是通过静态作用域statically scoping)和uniform data representation等特点结合起来达到高效的。


相关条目[ ]


参考资料[ ]