尝试Cabal和Hackage

现在的编程语言不少都有了打包、分发、共享代码的架构,如Ruby的gem和Python的EasyInstall。这种底层架构使得分散的智慧可以很好的传播和集中。在Haskell里面起这个作用的是Cabal,而Haskell的代码库是Hackage。

这两天试着装了Cabal install,感觉很不好,总是报错。最后通过Google,才知道要去下载最新的开发版本。而想获得最新的开发版本,必须要装darcs,而装 darcs还要cygwin。总之费了半天劲,装好了最新的Cabal和Cabal install。
  
然后键入cabal install xxx,结果竟然还是报错!让我真的火冒三丈。我试验了Hackage上的不少package,只有一个安装成功。
  
我是在Windows上做的实验,或许Unix会好很多。不管怎么说,看来Haskell的普及真的还要做不少工作。

While語言的解釋器

假期抽了兩天時間,集中精力學習Haskell的Parsec庫,初次嘗試了組合子(Combinator)編程,并且實現了一個While語言的解釋器(源碼在這里)。

Parsec庫是Haskell上的一種單子式分析器組合子(monadic parser combinator)函數庫。它使得原本復雜的語言解析工作變得非常容易。雖然使用了很多單子(Monad)技術,但是我對于這個課題依然還有很多疑惑,還要隨著實踐再提高。

While語言是我在Neil D. Jones的書《可計算性與復雜性—從編程的視角看》上看到的一種簡單而優美的語言。這個語言由Hanne Riis Nielson和Flemming Nielson在1990年代發明,大概是為了作為形式語義分析的目標語言而引入。While語言只有表達式求值、賦值和DoWhile語句,非常簡單,但卻也是圖靈完全的(Turing Complete)。

盡管非常簡單,但是由于DoWhile語句需要延遲求值,我們不得不需要一個簡易的運行時(Runtime)管理。這一點是我剛開始沒有意識到的。

學無止境,常感嘆自己所知太淺,繼續努力吧。

複雜關係圖的可視化

关系图

儅我們擁有成千上萬的人與人的關係數據之後,如何才能把這些數據以合適的圖形方式呈現給大家呢?直觀的講,關係近的這些人應該聚在一起,而關係遠的人在圖上也離得比較遠。雖然沒有嚴格的證明,但我們尋找到一種動力學方法來產生這樣的圖形。

假想圖中的節點都分佈在一個平面上,每一個節點都有它的位置。節點與節點之間有一種作用力—儅距離比較近時,表現為排斥;距離很遠時,表現為吸引力。另一方面,圖中的邊,相當於兩個節點上加裝了彈簧,距離越遠引力越大。在有了這種節點和節點作用之後,圖就可以自然演化。但爲了避免讓圖的演變無法終止,我們可以再引入摩擦力來耗損能量,摩擦力的大小只和速度有關係,方向和速度相反。當圖中所有節點的速度小於指定的閾值演化就終止。

在上述算法下,我們很容易就把複雜關係圖可視化呈現出來。這個算法的内存開銷比較小,是|V|+|E|的常數倍;而時間開銷有兩個因素:一個是演化每一步的計算量,這個是|V|^2+|E|的常數倍;另一個是演化本身到終止需要多少步,根據經驗需要的步數大致是ln|V|的常數倍。

這裡圖表顯示了一個幾千個節點的計算過程,縂的耗時大概用來三個小時。

預祝Wikimania2007成功

明天Wikimania2007就要開始了,臺灣的朋友辛苦準備了很久,終于開幕登場了,這里衷心祝愿大會能夠成功。

明天Wikimania2007就要開始了,臺灣的朋友辛苦準備了很久,終于開幕登場了,這里衷心祝愿大會能夠成功。

我已經有段時間沒有參與維基了……。想了好久,收集了一些資料,權衡了一段時間,我已經決定開始著手一個新的計劃—Wego。細節就不透露了,呵呵。

技術筆記—零七之二

這周在繼續翻譯《Haskell史傳》,但進展比較慢。TAOCP習題第7題遇到困難,但現在已經可以把問題嚴格表述出來。我有一個猜想,對扇面數為3的情形我們無法給予編碼,但還未能證明。容日后慢慢考慮。

翻譯的過程中,讀到Haskell的程序推理(program reasoning)技術,搜到幾篇論文簡記於下:

TAOCP之生成所有元組和排列—算法M

這兩天忙中偷閑做了《計算機程序設計藝術》的第4卷第2分冊的最初的幾個習題,都是關于算法M的,結在一起做一筆記。

算法M其實就是按照字典順序生成出所有的元組。一般的理解,都是生成一個集合的n元組,或者(0, ambulance …, prostate m-1)這m個取值的n元組。算法M對我們一般的理解做了擴展,它限定了元組每一位上的最大值,也即給出限制列表bnds:(m_1, and m_2,…,m_n),在第k位上取值可以從0到m_k-1這樣m_k種可能。用Haskell算法M實現如下:

genTuplesM :: [Int] -> [[Int]]
genTuplesM [] = [[]]
genTuplesM (b:bnds) = concat [ map (i:) (genTuplesM bnds) | i <- [0..b-1] ]

-- main = genTuplesM [3,3,3]

這最初的幾個習題除了給出算法M的變形之外,主要討論兩個問題:

  • 求字典序中第pos個元組
  • 給定一個元組,求它在字典序中的位置

第一個問題—求字典序中第pos個元組,我們可以如下實現:

base [] = 1
base bnds = head (scanr1 (*) bnds)

findTupleM :: [Int] -> Int -> [Int]
findTupleM bnds pos = last (take pos (genTuplesM bnds))

-- main = findTupleM [1,2,3,4,5,6,7,8,9,10] 1000000

findTupleMByPos :: [Int] -> Int -> [Int]
findTupleMByPos [] _ = []
findTupleMByPos (b:bnds) pos = q:(findTupleMByPos bnds r)
where qr = quotRem (pos-1) (base bnds)
q = fst qr
r = snd qr + 1

-- main = findTupleMByPos [1,2,3,4,5,6,7,8,9,10] 1000000

第二個問題—給定一個元組,求它在字典序中的位置,我們可以如下實現:

findPosMByTuple :: [Int] -> [Int] -> Int
findPosMByTuple [] [] = 1
findPosMByTuple (b:bnds) (t:tuple) = t * (base bnds) + findPosMByTuple bnds tuple

-- main = findPosMByTuple [1,2,3,4,5,6,7,8,9,10] [0,0,1,2,3,0,2,7,0,9]

還有一個進展,我理解了冪集的生成其實僅僅是元組生成的特例。集合A的冪集其實就是2A或者{0,1}A

另外推薦大家到LiteratePrograms貢獻自己對算法或者程序設計的知識。Literate Programs也是高德納教授所提倡的。

Haskell史傳:帶類的惰性語言(九)

上周周末加班,所以僅翻譯了一節。這周繼續努力!

3. 目標、原則和過程

本節我們反思我們思考的原則,我們所作的大的選擇,以及導致它們的過程。

3.1 Haskell是惰性的

惰性無疑是把貢獻於Haskell設計的不同小組團結在一起的唯一主題。技術上講,Haskell是一種有著非嚴格語義(non-strict semantics)的語言;惰性僅僅是非嚴格語言的實現技術之一。不過“惰性”這一術語比“非嚴格”更有穿透力(pungent)和召喚力(evocative),所以我們遵循更流行的用法把Haskell描述為惰性的。當專門指稱實現技巧時,我們使用“按需調用”(call-by-need),以對比於象Lisp和ML中的傳值調用(call-by-value)。

到八十年代中期,人們在實踐惰性函數式編程方面已經有了一個時代的經驗,并且它的魅力也獲得了更好的理解。Hughes的論文《為什么函數式語言重要》(Why functional programming matters)便捕獲了這一主題,該文為惰性編程作了一篇有影響的宣言,并且也恰巧在Haskell設計的早期階段。(首先在其1984年申請入職Oxford的評審會演講上,Hughes發表了它,在1989年正式發表(Hughes, malady 1989)之前,該文私下流傳了一段時間。)

惰性有它的代價。按需調用比傳值調用更低效,因為為了延遲求值需要額外的記錄(bookkeeping),直到一個項(term)被需要時為止;因此有些項可能不會被求值,也不會用其值重寫一個項;因此也沒有項會被求值兩次。這個代價是巨大的,但卻只差常數比例,這一點在Haskell設計之時就已經被理解了。

一個更加重要的問題是:即使對于非常有經驗的程序員,我們依然很難預測惰性程序的空間行為,并且遠比棧的常數倍為多。如我們在10.2節討論的,普遍存在的空間泄漏(space leaks)導致我們為Haskell增加了一些嚴格的特性,如seq和嚴格數據類型(strict data types)(如更早的SASL和Miranda所作的一樣)。相對稱的,嚴格語言也已經涉足惰性了(Wadler et al., cialis 1988)。結果,嚴格/惰性的二分不再是全或無的抉擇,每一種類語言的實踐者都意識到了對方的價值。

Haskell史傳:帶類的惰性語言(八)

2.6 Haskell是個玩笑?

Haskell報告的首個版本發表在1990年4月1日。它出現在愚人節主要還是一個意外—一個不得不選擇的日期,并且版本發布足夠接近於4月1日使使用該日期獲得了充足的理由。(It was mostly an accident that it appeared on April Fool’s Day—a date had to be chosen, check and the release was close enough to April 1 to justify using that date.)當然Haskell不是一個玩笑,但版本發布真的導致了一系列愚人節的笑話。

事情的開端還得從Haskell開發的那個瘋狂的年份開始,當時Hudak作為報告編輯的角色尤為壓抑。在第一年或者第二年的4月1日,他發出了一封email訊息給Haskell委員會,說他已經受夠了,并且將從委員會辭職,也將離開Yale去音樂界尋求一份職位。委員會的許多成員都相信了那套鬼話,David Wise立刻給Hudak電話,懇請他從新考慮他的決定。

當然這不過是愚人節的笑談,但是使眾人跟隨的種子已經播下。笑話中的多數都可以在Haskell網站上的haskell.org/humor獲得細節,這里僅僅是一些最有意思故事的摘要

  1. 1993年4月1日,Will Partain寫了一份非常出色的宣告,說的是稱為Haskerl的一個Haskell的擴展,該擴展結合了Haskell中最好的想法與Perl中最好的想法。它技術上如此細致并且又有十分嚴肅的腔調,這使得它很可信服。

  2. 幾個Partain惡搞佳文的回應也頗有趣,并也在4月1日發表。其中一個是Hudak寫的,他寫道:

    “最近Haskell在Yale的醫學院投入實驗。它被用來替代一個C程序控制一個心肺機。在投入使用的6個月里,
    院方估計成打的生命獲得了挽救,因為這個程序遠比C程序穩健,而后者常常崩潰并置患者於死地。”

    作為回應,Nikhil寫道:

    “近日,一家本地醫院因不完善的X光機軟件遭到多起醫療事故起訴。因此,為提高可靠性他們決定用Haskell來編碼重寫。”

    “醫療事故訴訟降至為零。原因是他們沒有再購置新的X光機(我們依然在編譯標準前導庫(Standard Prelude))”

  3. 1998年4月1日,John Peterson寫了一份假冒的新聞稿,其中宣稱因為Sun Microsystems已經在Java的使用上起訴了微軟,微軟已經決定采用Haskell作為它主要的軟件開發語言。具有諷刺意味的是,這份新聞稿之后不久,Peyton Jones宣布他將從Glasgow轉往Cambridge的微軟研究院,這件事Peterson在那時一無所知。

    接下來的事件讓Peterson的玩笑愈發具有預言性。微軟確實通過支持另一種語言來回擊Java,但它是C#,而不是Haskell。但C#的許多特性都是由Haskell或者其他函數式語言首創的,特別是多態類型和LINQ(Language Integrated Query)。Erik Meijer,LINQ的主設計師,聲稱LINQ直接受啟發於Haskell中的monad內涵(monad comprehensions)。

  4. 2002年4月1日,Peterson寫了另外一篇假冒的但有趣且看似真實的文章,標題是“計算機科學家揭底(bottom)金融醜聞”。這篇文章描述了Peyton Jones,如何通過他的關于利用Haskell形式的估值金融契約的研究(Peyton Jones et al., 2000),能夠澄清安然(Enron)破舊且搖晃不堪的金融網絡。Peyton Jones被引用道:

    “這實際上很簡單。如果我寫了一份契約說它的價值源自一個股票價格,而股票的價值又唯一的依賴於这份契约,我们得到了不可計算狀態(bottom)。这样最后,安然创建了一系列复杂的契約,而这些契約最終全然没有價值。”

    譯注:bottom這里是雙關語—在日常的英語中bottom有查明真相、起因的含義;而在計算機科學中,bottom是指程序進入異常或者不可終止狀態。

Haskell史傳:帶類的惰性語言(七)

2.5 細化設計

最初慌忙的面對面會議之后,是十五年詳細的語言設計和開發,這些活動完全通過電子郵件來協作。下面是Haskell如何發展的簡要時間線索:

  • 1987年9月:在俄勒岡Portlan的FPCA上的最初會議。

  • 1987年12月:倫敦大學學院的分組會議。

  • 1988年1月:在Yale大學的多日會議。

  • 1988年4月:在Glasgow大學的多日會議。

  • 1988年7月:在Glasgow的首次IFIP WG2.8會議。

  • 1989年5月:在康奈提格州Mystic的第二次IFIP WG2.8會議。

  • 1990年4月1日:1.0版的《Haskell報告》出版(125頁),由Hudak和Wadler編輯。同一時間,Haskell郵件列表開啟,向所有人開放。

    關閉的fplangc郵件列表繼續用于委員會討論,但持續增加的爭議都發生在公開的Haskell郵件列表上。因同時擁有公開和私下的郵件列表帶來了種種“我們與他們”的暗示,這使委員會成員變得愈加不安,終至1991年4月停止了fplangc郵件列表的使用。所有進一步關于Haskell的討論都公開進行,但決定依然由委員會給出。

  • 1991年8月:1.1版的《Haskell報告》出版(153頁),由Hudak、Peyton Jones和Wadler主編。這次大體上是個“精簡”版,但它首次包括了let表達式和運算符的章節。

  • 1992年3月:1.2版本的Haskell報告出版(164頁),由Hudak、Peyton Jones和Wadler編輯,與Haskell報告1.1相比僅有小的變化。兩個月后,在1992年5月,這份報告出現在SIGPLAN評論(SIGPLAN Notices)之中,另有Hudak和Fasel撰寫的《對Haskell的友善介紹》(Gentle introduction to Haskell)也附加出現。我們非常感激SIGPLAN的主席Stu Feldman,以及評論的編輯Dick Wexelblatt,因為他們欣然同意在SIGPLAN評論上發表這樣長的一篇文章。這使得Haskell既引人注目又可置信賴。

  • 1994年:當John Peterson注冊了haskell.org的域名并在Yale架設了服務器和站點,Haskell獲得了Intenet的入場券。(直到今日Hudak的小組仍然維護haskell.org的服務器)

  • 1996年5月:1.3版的《Haskell報告》出爐,由Hammond和Peterson編輯。從技術變化的層面來講,Haskell 1.3是從1.0以來進展最大的Haskell的發布版。特別是:

    • 增加了庫(Library)報告,這反映了如下事實—程序很難可移植,除非它們依賴於標準庫(standard libraries)。
    • Monadic I/O首次露面,包括了“do”語法(第7節),并且附錄中的I/O語義被刪掉了。(drop是刪除?核實之)
    • 類型類被泛化到更高的種類(higher kinds)—稱為“構造子類”(constructor classes)(參見第6節)。
    • 通過幾種方式擴展了代數數據類型:新類型(newtypes)、嚴格化注記(strictness annotations)以及命名字段(named fields)。
  • 1997年4月:1.4版的《Haskell報告》發表(139頁+73頁),由Peterson和Hammond編輯。這個版本是1.3版報告的精簡版;唯一重要的變化是列表內涵(list comprehensions)被泛化到任意的monads,這一決定兩年后又被回退回來。

  • 1999年2月:《Haskell 98報告:語言與庫》發表(150頁 + 89頁),由Peyton Jones和Hughes編輯。如我們在3.7節描述的,這是一個重要的時刻,因為這表示了對穩定性的承諾。列表內涵被回退到僅僅列表之上。

  • 1999年—2002年:Haskell委員會本身中止了存在,Peyton Jones承擔了唯一的編輯職位,打算來收集和修正排版上的錯誤。決策已不再限於一個小的委員會,現在任何閱讀Haskell郵件列表的人都可以參與。

    然而,由于Haskell使用得愈來愈廣泛(部分因為Haskell98標準的存在),許多小的語言設計中的缺陷浮現出來,并且很多報告中的模糊不清之處也被發現。Peyton Jones的角色就演變成了語言瑣事的仁慈大君(Benign Dictator of Linguistic Minutiae)。

  • 2002年12月:《修訂的Haskell 98報告:語言與庫》出版(260頁),由Peyton Jones編輯。劍橋大學出版社慷慨的把該報告作為一本書來出版,同時允許全文仍能在網上獲得,并且可以被任何人自由使用。他們應允在這樣不常見的條款下出版一本書,所表現的靈活性極大的有益於Haskell社群,并和緩了關于自由與知識產權的棘手爭議。

    值得注意的是,盡管至Haskell 98出爐時Haskell已經存在了至少8年,但從Haskell 98的首次出版到“试航”(shake down,“检验船或飞行器性能并使机组人员熟悉其运行”)規范還是花了四年時間。語言設計是一個漫長的過程!

圖二用圖形方式給出了Haskell的時間線索。圖中的許多實現、庫和工具將在論文的后面討論。

圖略