SML

ML语言

　　ML语言
　　ML (which stands for Meta-Language) is a functional language which, unlike conventional (procedural) languages, is mathematically "pure". Assignment to variables in the way that it is done in procedural languages is not possible; a variable is defined as in mathematics as being equal to a particular value, so a statement such as "X = X + 1" would make no sense, as there is no value of X which is equal to X + 1. There are also no explicit control flow operations (loops, goto statements and so on); recursive function definitions are used to achieve the same effect.
　　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简介
　　我是从翻译John C. Mitchell的著作Concepts in Programming Langugaes开始接触和学习ML语言的。很快就被它那和数学系统一样严谨的类型系统吸引。后来发现ML确实是为了解编程语言设计思想应当学习的一种 语言。作为一个ML初学者，我把自己学到的一点东西整理出来，作为阶段小节。如果对其他初学ML的朋友们能稍微有点帮助，就是意外收获了。如果有其他对 ML感兴趣的朋友，很希望和你联系。
　　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 ML和Caml。我不会Caml，本文专注于SML。
　　大多数SML编译器的行为方式都是交互式的：用户一条一条输入语句，编译器一一给出反馈。看起来象Logo或者Basic解释器一样。但是其实用户输入的程序是被先编译再执行的（其中细节大家可以从SML/NJ编译器的相关文档和论文中找到）。
　　ML的相关资源
　　这里是我找到的一些ML相关的资源：
　　SML New Jersey -->
　　最著名的SML编译器——Standard ML New Jersey的官方网站。其中还可以找到很多SML相关的内容
　　Programming in Standard ML -->
　　我喜欢的一本Carnegie Mellon University使用的ML教科书——Programming in Standard ML。你也可以从我这里下载。
　　将Emacs作为SML的开发环境
　　目前有两个常用的SML的Emacs mode。一个是 Stefan Monnier写的，功能强大一些。可以从这里下载。SML/NJ的网站上有它的文档。
　　一个在线教程
　　Programming in Standard ML '97: On-line Tutorial -->
　　SML的Basic Library文档
　　如果要用ML写能实际干点事情的程序，离了Standard ML Basic Library是不行的。SML/NJ编译器安装时已经包含了Basic Library，你可以直接使用。如果需要查文档（其实是必然需要的:-)），请看这里。
　　ML编程环境的配置
　　我在Windows环境下使用Emacs作为ML的集成开发环境。下面关于Emacs和SML 在Windows下的配置说明其实同样适合于各种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)
　　著作节选
　　John C. Mitchell在他的Concepts in Programming Langugaes一书中使用ML来展示Algol类语言、Lisp类语言、以及并行语言和面向对象语言中的概念。应清华大学出版社的要求，我参与翻译了 此书中的部分内容，其中包括介绍ML语言（和其他Algol类语言）的第5章。没有经过校对的翻译结果可以从这里下载。请大家帮我多提意见。谢谢。
　　从例子看ML编程风格
　　通常大家学习编程都是从命令式语言开始的。和函数示语言不同，命令式语言以语句作为基 本单位。Algol家族的所有语言都是命令式语言，ML也不例外。因此学习ML不像学习Scheme那样需要完全转换一套思路。但是ML继承了函数式语言 的很多特征，而且也有自己的一些特点。
　　我修改了网上找到的一个求解n皇后问题的程序，用来展示ML编程的一些基本手段:
　　查看源程序
　　上面程序中使用了option。如果要改用exception可以将其中addqueen函数的定义改成这样。
　　程序注解和说明
　　线性数据结构
　　程序中总要定义数据结构。常用的定长线性结构包括：Pascal的record，C的struct，C++和Java的class。在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）风格，避免副作用（side effect）
　　大多数Algol类语言对机器的抽象是以内存为中心的，即变量和对象（object）对应内存 中的存储区域，赋值语句对应机器的访存操作，所以程序中有大量的赋值语句。ML也支持赋值，但是通常建议采取的风格是类似Lisp和Scheme的纯表达 式风格，避免赋值操作。
　　例如如果用C来描述n皇后问题，通常我们会设计一个数据结构描述棋盘（和ML程序一样），然后定义这个数据结构的一个实例（可能是个全局变量）。算法的主要工作是通过赋值修改这个实例的内容。
　　而例子中的ML代码中经典的一段是函数place。这是修改棋盘数据结构的代码。但是并没有使用赋值，而是产生了一个新的数据结构实例，其内容和参数略有区别（放上了一个新的皇后）。
　　纯表达式的使用要求程序员先对程序考虑得非常细致才能动笔（动手？），因此使得程序逻辑更加清 晰。（这和literate programming的思想是一致的。）但是目前的硬件机器是以内存为中心设计的，所以纯表达式语言的实现（编译器和解释器）的效率依靠于设计者多费心 思。ML就是通过静态作用域（statically scoping）和uniform data representation等特点结合起来达到高效的。