ML語言

ML語言

ML (meta language)是一個通用的函式式程式語言,它是由愛丁堡大學的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 ML和Caml。

大多數SML編譯器的行為方式都是互動式的:用戶一條一條輸入語句,編譯器一一給出反饋。看起來象Logo或者Basic解釋器一樣。但是其實用戶輸入的程式是被先編譯再執行的(其中細節大家可以從SML/NJ編譯器的相關文檔和論文中找到)。

產生

ALGOL國際代數語言 LISP語言(全名ListProcessor,即表處理語言)。ML是一個通用的函式式程式語言,它是由愛丁堡大學的Robin Milner等人在二十世紀七十年代晚期開發的。 目前ML有兩個發展分支:StandardML和Caml。 StandardML是標準ML,簡稱為SML。 ML是一種強類型函式程式設計語言(強類型:變數有且只有一種類型)。它擁有自然的語法和較少的基本概念,其理論基礎是λ演。

相關資源

最著名的SML編譯器——Standard ML New Jersey的官方網站。其中還可以找到很多SML相關的內容

教科書——Programming in Standard ML。

將Emacs作為SML的開發環境

目前有兩個常用的SML的Emacs mode。一個是 Stefan Monnier寫的,功能強大一些。可以從這裡下 載。SML/NJ的網站上有它的文檔。

SML的Basic Library文檔

如果要用ML寫能實際乾點事情的程式,離了Standard ML Basic Library是不行的。SML/NJ編譯器安裝時已經包含了Basic Library,你可以直接使用。

編程環境配置

在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編譯器所在的目錄。

啟動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繼承了函式式語言的很多特徵,而且也有自己的一些特點。

線性數據結構

程式中總要定義數據結構。常用的定長線性結構包括: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是要被外部調用的。

尾部遞歸代替循環

如果用Algol類語言(例如 Pascal和C)來寫函式addqueen,其中需要一個循環,從某行的第一個位置開始,判斷如果在這個位置上放一個皇后是否可以使得其不和前面已經放上的皇后衝突,而且後面還可以繼續放滿皇后。而ML中這個循環用遞歸函式tryARow表示。

純表達式風格

大多數Algol類語言對機器的抽象是以記憶體為中心的,即變數和對象(object)對應記憶體中的存儲區域,賦值語句對應機器的訪存操作,所以程式中有大量的賦值語句。ML也支持賦值,但是通常建議採取的風格是類似Lisp和Scheme的純表達式風格,避免賦值操作。

例如如果用C來描述n皇后問題,通常我們會設計一個數據結構描述棋盤(和ML程式一樣),然後定義這個數據結構的一個實例(可能是個全局變數)。算法的主要工作是通過賦值修改這個實例的內容。

而例子中的ML代碼中經典的一段是函式place。這是修改棋盤數據結構的代碼。但是並沒有使用賦值,而是產生了一個新的數據結構實例,其內容和參數略有區別(放上了一個新的皇后)。

純表達式的使用要求程式設計師先對程式考慮得非常細緻才能動筆,因此使得程式邏輯更加清晰。(這和literate programming的思想是一致的。)但是目前的硬體機器是以記憶體為中心設計的,所以純表達式語言的實現(編譯器和解釋器)的效率依靠於設計者多費心思。ML就是通過靜態作用域(statically scoping)和uniform data representation等特點結合起來達到高效的。

相關詞條

相關搜尋

熱門詞條

聯絡我們