筆記與流年

沒有太多的話,這只是一個普通的Blog,想用它來記錄我的閱讀和學習筆記。

作者歸檔

links for 2008-02-21

By Mountain • Feb 22nd, 2008 • Category: 網路書簽


軟件搆造的復雜性

By Mountain • Feb 20th, 2008 • Category: 技術話題

今天在arXiv讀到一篇有趣的文章《軟件圖與程序員意識》(Software graphs and programmer awareness)。作者探討的是程序不同模塊間相互依賴搆成的圖的統計性質。作者試圖從微觀的程序員開發行為來闡釋程序的宏觀統計性質。

以前,我曾經做過一個統計,計量一些關鍵性系統模塊的復雜性。當時寫到:

硬件的飛速發展,網絡的出現,人機交互方式的變化正劇烈的改變着軟件產業的形態。那么影響軟件產業形態的因素有什么呢?從某一個視角來看,復雜性和經濟學是影響軟件產業形態的重要因素。

軟件搆造是一個非常復雜的過程。由于經濟學的原因,在攻克軟件搆造的復雜性過程中,發生了系統程序和應用程序的裂解,于是軟件產業也隨之分化成了不同的行業。在分化過程中值得注意的是一些關鍵性的系統,它們居于核心的,具有某種平台性質。比如操作系統內核、桌面系統、瀏覽器、Web服務器、數據庫服務器。

寫了一個小程序測試了一些系統的源程序行數,想看看現在的關鍵性系統究竟有多復雜。測試結果如下:

  • openoffice-1.0.2 3786802
  • linux-2.4.20 2964125
  • mozilla 2459987
  • sapdb 711151 (script for system tables not include)
  • j2sdk1.4.0 486376
  • amaya 7.2 452057
  • mysql 428500*
  • gcc-2.7.2.2 331209
  • lesstif-0.93.40 323526
  • httpd-2.0.44 297110
  • jfc 210022
  • HotSpot JVM 1.1 119093
  • javatool 101041 (estimated from bytecode)
  • hurd-0.2 97674
  • jigsaw 96061
  • berkleydb-3.2.9 86862
  • aspectj-1.0.6 84405
  • tomcat-4.1.10 64495
  • libwww 61347
  • zlib-1.1.4 9388

從上面的結果,我們可以看到:

  • 一個實用的基本的開發環境(編譯、調試、庫等)的代碼量應該在 100~500 kloc 附近,才有可能被廣泛使用。
  • 復雜的應用需要有 ~1 mloc 級別的代碼量。
  • 一台良好工作的 PC 所必須的支持軟件大致需要有 ~10 mloc 級別的代碼量。

今天再把當年的舊文翻出來,只是覺得這是一個可以繼續深究下去的課題。

從程序設計語言的角度看,一個程序設計語言可以通過其基礎的語言搆造來獲得普遍的計算能力,這解決了可計算性的問題,僅僅是第一步,后繼而來的是復雜性和經濟學的問題。在語言這個層次上,我們可以看到函數、類、模塊、包等分層,以及對分別編譯的支持,這是用抽象、分治、復用的手段解決復雜性。

除了這些手段,還有沒有其他的方法?我能想到的,還有meta-programming和combinator兩種途徑的DSL,以及generic programming。這些也是某種語言層次上的方法,但大的思路依然是抽象、分治、復用。



Git与Wikipedia:開放、分散和信任

By Mountain • Feb 18th, 2008 • Category: 互聯網

最近一直在關注分佈式的版本控制工具(DRCS),這其中最著名的莫過于gitmercurial。今天發現了一個用git實現的wiki系統git-wiki,讓我覺得有必要給大家說明一個前景—完全分散式的、基于信任關係管理的全新的Wikipedia。

先說一下git,它是由Linus Torvalds開發的一款分佈式的版本控制工具,計划開始于兩年多以前,最初用于Linux kernel的開發。git有以下的一些的特點:支援所謂非線性的開發;完全分佈式;支援多種發布協議;高效。

據說在Linux kernel的開發當中,Linus只接受來自少數信得過的開發人員的修改;而這些人員各自負責不同的領域,每個又有自己的團隊;這樣就形成了一個層級架構,而Linus居于層級架構的最頂端。

要注意的是,因為開源協議和git完全分散的特點,任何人都可以fork出來一個自己的分支,Linus也無法阻止這樣的事情發生。關鍵在于,fork出來的分支能否獲得足夠的資源來持久發展。大家的起點任何時候都是平等的,你的努力決定了你在一個開放社群裡的地位;Kernel的層級架構完全是基于信任關係建立起來的。

讓我們接着討論一下Wikipedia。在Wikipedia經常可以看到吵架和各種各樣的troll,Isaac Mao曾經評論說,這是因為Wikipedia集中式下的開放性使得信任關係無法良好的存在。設若我們有一個基于git的Wikipedia,情況就會完全改觀。

這樣一個前景是可以想象的。而且更有一點,完全分散的Wikipedia更難于被封鎖,最終必將是自由知識的勝利。

參考:



RSS導入后臺的實現

By Mountain • Jan 4th, 2008 • Category: 技術話題

來到Linkist的第一個項目就是RSS的自動導入,經過一個月的努力我們實現了這個功能。簡單記一下所得:

  • 空間的分散化:RSS的抓取本身是可以很容易分布到不同機器上去的,所以我們需要支持多臺機器分布工作。(勢必涉及分布算法,比如領導者選舉)
  • 時間的分散化:RSS源有不同的更新頻率,我們的抓取頻率必須可以根據更新頻率來調整。同樣頻率的抓取又可以在時間上隨機均勻分布于整個時段。
  • RSS源的特異性:RSS標準多,各個RSS源的實現不標準,特別是pubDate字段的實現更是千奇百怪。

這三點是我們RSS自動導入后臺實現的主要考慮。



尝试Cabal和Hackage

By Mountain • Jan 4th, 2008 • Category: 技術話題

现在的编程语言不少都有了打包、分发、共享代码的架构,如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語言的解釋器

By Mountain • Jan 2nd, 2008 • Category: 技術話題

假期抽了兩天時間,集中精力學習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)管理。這一點是我剛開始沒有意識到的。

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



複雜關係圖的可視化

By Mountain • Oct 18th, 2007 • Category: 技術話題

关系图

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

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

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

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



河蟹横行的中国互联网

By Mountain • Aug 30th, 2007 • Category: 互聯網

很好很河蟹几个星期没在Blog上说话了,今天看到一则新闻,面对如此河蟹横行的中国互联网,不由想说两句。

紧急通知,继”紫田”机房、广东汕头”蓝芒”机房,总数超过2000多台服务器被断网关闭处理后,今天我机房参加了浙江省公安厅召开的”十七大”前严打”交互性网站”(论坛/博客/留言板)通告会。会议精神明确要求,各IDC服务商在十七大之前,必须强制关闭所有论坛/博客/留言板等交互性网站,整个机房只要发现超过7例,采取关闭机房强制性措施,并处罚款5-100万元。

为了确保我司所有客户的网站不出现断网危机,所以我司在严打期间规定如下:

1、已有论坛的网站空间,强制关闭论坛功能(仅有论坛的关闭整个论坛);

2、尚未有论坛等交互性程序的空间,严打期间不得新开通论坛、博客、留言板等程序。我司24小时不间断检查,一旦发现,按恶意攻击机房处理,强制关闭此会员(或代理)名下所有网站并永不退款处理,造成严重损失的,将追究法律刑事责任。

3、完全靠论坛为生的大型论坛,要求开通的,必须安排专员每1小时向我司报到一次,24小时实时监管并交押金1万元,如因所登记的论坛缘故出现断网情况押金不退还。

4、政府禁令期间所有被关闭论坛/博客/留言板等功能的网站,一律作不可退款处理(属不可抗拒范围)。

5、要求更换网站内程序的网站,为防止出现意外上传原来程序的情况,须交押金1000元。

6、有反对意见或不满的,请直接致电公安部咨询相关情况。

注意:本次严打截至十七大会议结束,出现问题的网站主本人,都将公安部门追究直接刑事责任。

首先,我不知道这样的禁令从法律上讲是否合法,很明显它不但在侵犯大众言说的权力,还在侵犯站长的合法权益。互联网发展到今天,还有几多网站没有交互的能力呢?哪条法律说明不允许开设交互性网站了,你凭什么发布这样的禁令?很多话都无需再说,都是很明摆着的道理。我只能建议大家,向勇敢的yetaai学习,必要的时候站出来,用自己合理、合法的手段同不公正作抗争。



預祝Wikimania2007成功

By Mountain • Aug 3rd, 2007 • Category: 維基計划

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

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



技術筆記—零七之二

By Mountain • Jul 16th, 2007 • Category: 技術話題

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

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