この文章は、 Lisp Advent Calendar 2014 の 12/18 担当分の記事として書かれました。
背景(順不同)
streem 言語
Matz 氏により、 streem という、 stream based concurrent scripting language なるものの設計が進められています。
面白そうですね。
streeem 言語
streem 言語にインスパイヤされた mattn 氏により、 streeem という Go 言語での実装が行われました。
なんて素早いんでしょう。かっこいいですね。
Common Lisp でのストリーム処理
Common Lisp で、 UNIX シェルのようなパイプライン処理ってどう組むの？っていう問題提起があります。
どうも、あんまり「決定的」な方法がないなー、という気がしてました。
筆者の事情
この日 (2014-12-18) の Lisp Advent Calender のために元々考えてたネタがあったんですが、脳内で放っておいたらどうでもよくなってきて…
なんかもっと面白いことないかな、と思ってきてました。
結果
何かようわからんが、 Lisp に寄せて streem 実装してみるか
コードを書きました。 https://github.com/y2q-actionman/stleem
名前は、 stleem にしました。これは、 僕が l と r の発音上の区別が付かない Engrish 野郎であることに由来しています。
コード例
本家 streem の例にある FizzBuzz から。
(defun fizzbuzz ()
(stleem ()
(seq 100)
(lambda (x)
(cond ((= (mod x 15) 0)
"FizzBuzz")
((= (mod x 3) 0)
"Fizz")
((= (mod x 5) 0)
"Buzz")
(t
x)))
stdout))
これにより、
- 1 から 100 まで列挙。
- 3 や 5 の倍数だった置きかえる。
- 標準出力に書く
- 結果のリストを得る。
ことが達成されます。
実行結果は以下です。
STLEEM-EXAMPLE> (fizzbuzz)
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
;; 中略
Fizz
Buzz
(1 2 "Fizz" 4 "Buzz" "Fizz" 7 8 "Fizz" "Buzz" 11 "Fizz" 13 14
"FizzBuzz" 16 17 "Fizz" 19 "Buzz" "Fizz" 22 23 "Fizz" "Buzz" 26 "Fizz"
28 29 "FizzBuzz" 31 32 "Fizz" 34 "Buzz" "Fizz" 37 38 "Fizz" "Buzz" 41
"Fizz" 43 44 "FizzBuzz" 46 47 "Fizz" 49 "Buzz" "Fizz" 52 53 "Fizz"
"Buzz" 56 "Fizz" 58 59 "FizzBuzz" 61 62 "Fizz" 64 "Buzz" "Fizz" 67 68
"Fizz" "Buzz" 71 "Fizz" 73 74 "FizzBuzz" 76 77 "Fizz" 79 "Buzz" "Fizz"
82 83 "Fizz" "Buzz" 86 "Fizz" 88 89 "FizzBuzz" 91 92 "Fizz" 94 "Buzz"
"Fizz" 97 98 "Fizz" "Buzz")
STLEEM-EXAMPLE>
実装
並列化
Threading
Go 言語には goroutine という、言語に密に結合された並列化機構があるそうです。Go 言語実装の streeem でも使われており、上記実装解説記事ではまるで空気のように使われています。いいなあ。
さて、 ANSI Common Lisp (1994年に標準化)には、並列化 API はありません。なんということでしょう。 C言語にも2011年の規格で並列化APIが加わったという、このご時世ににも関わらず、です。
(余談: 筆者が元々考えていた Lisp Advent Calender のネタというのは、この件について滔々と恨み節を述べる…というものでした。この辺の API が加わった Common Lisp 標準の制定を待っています。
いつまでも。)
とはいえ、各種 ANSI Common Lisp 準拠の Common Lisp 処理系は、大抵、独自拡張として並列化 API を持っています。それらを統一して使うための Bordeaux Threads というライブラリがあるので、それを使っています。
こんな感じでスレッドが立てられます:
;; "Hello, World" を吐くスレッドの作成
(make-thread #'(lambda () (print "Hello, World!")))
;; スレッドの終了を待つ
(join-thread *)
Channel
Go 言語には channel という、スレッド間通信機構があるそうです。同じく streeem で使われており、これもまた空気のように使われています。いいなあ。
さて、前述の Bordeaux Threads の API には、そんな便利なインターフェイスはありません。普通のロックと条件変数しかなく、まあ頑張ればここから組むことも可能かもしれませんが、私めには無理でございました。
今回の用途では、「要素が投入されるまでブロックして待ってくれるキュー」があれば十分です。そのため、 lparallel ライブラリの lparallel.queue パッケージを使いました。
パイプライン化メインループの実装コード
;;; 各スレッドがやること
(defun make-stleem-thread-function (pipeline-func from-pipe to-pipe end-symbol)
#'(lambda ()
(unwind-protect
(loop for in = (pipe-pop from-pipe end-symbol) ; 入力 pipe から要素を拾って
until (eq in end-symbol) ; EOF なら終了
as out = (funcall pipeline-func in) ; フィルタ関数を通して
until (eq out end-symbol) ; EOF なら終了
do (pipe-push to-pipe out)) ; 出力 pipe に吐く
(pipe-close to-pipe)))) ; エラーが起きても pipe を閉じることを保証 (unwind-protect)
;;; Main loop
(defun run-stleem (pipeline-funcs
&key (start-symbol t) (end-symbol nil) (extract-values t))
(let ((threads nil)
(last-pipe nil))
(unwind-protect
(loop for pipeline-func in pipeline-funcs ; 各 pipeline を構成する関数について・・
as from-pipe = (make-instance 'constant-pipe :value start-symbol) ; 入力 pipe
then to-pipe
as to-pipe = (make-instance 'tekitou-pipe) ; 出力 pipe
do (push (make-thread ; スレッド作成
(make-stleem-thread-function
pipeline-func from-pipe to-pipe end-symbol)
:name "streem worker thread")
threads)
finally
(setf last-pipe to-pipe)
(mapc #'join-thread threads)) ; 全スレッドの終了を待つ
(mapc #'destroy-thread threads)) ; エラーで中断してもスレッドを絶対殺す
(cond ((null last-pipe)
(values nil nil))
(extract-values
(values (pipe-extract last-pipe) t)) ; 最後の出力 pipe の中身を取り出して返す。
(t
(values last-pipe t)))))
構文解析
S式にしてさぼる
streem や streeem では、構文解析に多くのコードが割かれています。構文解析器を作るというのは相当に手間どる作業であることは、皆々様ご存知だと思います。
一方 stleem では、思い切って、 構文を全部S式で記述して下さい とユーザの皆様にお願いすることにしました。これにより、構文解析から解放され、標準的なリスト操作関数だけで実装は完結します。
(余談: Lisper がS式に閉じこもってしまう一因は、こういう構文解析から解放されたいという願望だと思います。たぶん。)
コード
;;; Entry point
(defmacro stleem ((&key (start-symbol t) (end-symbol nil) (extract-values t))
&body pipelines)
`(run-stleem
(list ,@pipelines) ; ユーザが渡したS式を詰め直しているだけ!
:start-symbol ,start-symbol
:end-symbol ,end-symbol
:extract-values ,extract-values))
シンボルの処遇
streem の例には、 STDIN, STDOUT という謎のシンボルがあります。これらはどう扱ったものでしょうか。
これらだけを stleem で特殊に扱ってあげるのは、妙な複雑度を増してしまいそうです。かといって (STDIN), (STDOUT) なんて書かせると、 「うわああ Lisper だあああ」 と言われるんじゃないかな…と筆者は被害妄想してしまいます。
結局、 define-symbol-macro で適当に置きかえるようにしました。
;; 任意 stream への出力用フィルタ
(defun stleem-write-driver (stream)
#'(lambda (obj)
(format stream "~&~A~%" obj)
obj))
;; stdout というシンボルを、上の関数の呼び出しにおきかえる
(define-symbol-macro stdout
(stleem-write-driver *standard-output*))
将来性
こんな感じでストリーム指向っぽい書き方を実装してみたわけですが、僕自身はこれを使わない気がします。というのも、 Common Lisp の強力な反復処理記述用 DSL である iterate との統合を考えたいためです。
前述の例を、それぞれ iterate で書いてみましょう:
(defun cat ()
(iterate:iter
(for l next (read-line *standard-input* nil nil))
(while l)
(write-line l *standard-output*)))
(defun fizzbuzz ()
(iterate:iter
(for x from 1 to 100)
(for y = (cond ((= (mod x 15) 0)
"FizzBuzz")
((= (mod x 3) 0)
"Fizz")
((= (mod x 5) 0)
"Buzz")
(t
x)))
(print y)))
これを見る限り、 iterate だけで、「もう十分それっぽい」記述が出来ているように感じられてしまっております。
なんか上手いことパイプラインっぽく見えるような項を iterate に導入した方が、既存のコードともっと融和できるんじゃないかな…
と思いはじめたところで、この記事は終わりです。