tiny-lisp

これは Go による小さなコンカレント Lisp インタープリタである。
Go 1.0.3 と Go 1.1beta2 でコンパイルできる。

  $ go build tiny-lisp.go

とすると実行ファイル tiny-lisp ができる。
八女王問題の解の個数を求める

  $ ./tiny-lisp 8queens.l
  92
  $

ハイフンを与えるとスクリプト実行後に対話セッションに入る。

  $ ./tiny-lisp 8queens.l -
  92
  > (nqueens 4)
  (nqueens 4) => ((3 1 4 2) (2 4 1 3))
  >

セッションを終えるには Control-D または Control-C を打鍵する。
無引数で起動しても対話セッションに入る。

  $ ./tiny-lisp
  > (+ 5 6)
  (+ 5 6) => 11
  > (/ 12 10)
  (/ 12 10) => 6/5 /*=1.2*/
  >

今のところ数はすべて無限精度の有理数として扱う。

  $ go build tiny-lisp-prof.go

とするとプロファイルする tiny-lisp-prof ができる。
これを実行すると cpu-profile ファイルが作られる。
これを Go の pprof にかけて実行内容を分析できる。

  $ ./tiny-lisp-prof 8queens.l
  92
  $ /usr/local/go/misc/pprof tiny-lisp-prof cpu-profile
  Welcome to pprof!  For help, type 'help'.
  (pprof) top10
  Total: 233 samples
        94  40.3%  40.3%       94  40.3% runtime.nanotime
        22   9.4%  49.8%      229  98.3% lisp.(*Env).Eval
        15   6.4%  56.2%       22   9.4% hash_lookup
        10   4.3%  60.5%       59  25.3% lisp.(*Env).Get
         9   3.9%  64.4%        9   3.9% sync/atomic.AddUint32
         9   3.9%  68.2%        9   3.9% sync/atomic.CompareAndSwapUint32
         8   3.4%  71.7%        8   3.4% runtime.memhash
         4   1.7%  73.4%        5   2.1% copyout
         4   1.7%  75.1%        4   1.7% runtime.memclr
         3   1.3%  76.4%        4   1.7% MHeap_AllocLocked
  (pprof) 

コンカレントなプログラムの作例として qsort.l を用意した。
クイックソートのピボットによるリストの２分割の後，
右半分のソート処理を future フォームで別のゴルーチンに任せる。
再帰的な２分割のたびに次々とゴルーチンが作り出される。
結果は必要になったときに force 関数で取り出す。

  $ ./tiny-lisp qsort.l -
  > (qsort '(3 1 4 1 5 9 2 6 5))
  (qsort '(3 1 4 1 5 9 2 6 5)) => (1 1 2 3 4 5 5 6 9)
  >

コンカレント化の効果を見るため 5001 個の整数をソートする qsort-pi.l と，
その非コンカレント版である対照用の qsort-pi-seq.l を用意した。
最大スレッド数を環境変数 GOMAXPROCS で様々に指定して試行されたい。

  $ time GOMAXPROCS=5 ./tiny-lisp qsort-pi.l

--
H25.4/16 (鈴) suzuki611@oki.com, suzuki@acm.org