Common Lisp で streem みたいな書き方を実装してみた


この文章は、 [Lisp Advent Calendar 2014](http://qiita.com/advent-calendar/2014/lisp) の 12/18 担当分の記事として書かれました。

# 背景(順不同)<a id="sec-1" name="sec-1"></a>

## streem 言語<a id="sec-1-1" name="sec-1-1"></a>

Matz 氏により、 **streem** という、 stream based concurrent scripting language なるものの設計が進められています。

-   <https://github.com/matz/streem>

面白そうですね。

## streeem 言語<a id="sec-1-2" name="sec-1-2"></a>

streem 言語にインスパイヤされた mattn 氏により、 **streeem** という Go 言語での実装が行われました。

-   <https://github.com/mattn/streeem>
-   <http://qiita.com/mattn/items/20c7eb056ed8921547a8>

なんて素早いんでしょう。かっこいいですね。

## Common Lisp でのストリーム処理<a id="sec-1-3" name="sec-1-3"></a>

Common Lisp で、 UNIX シェルのようなパイプライン処理ってどう組むの？っていう問題提起があります。

-   <http://ja.stackoverflow.com/questions/1724/unix%E3%81%AE%E3%83%91%E3%82%A4%E3%83%97%E5%87%A6%E7%90%86%E3%81%AE%E3%82%88%E3%81%86%E3%81%AB%E3%82%B9%E3%83%88%E3%83%AA%E3%83%BC%E3%83%A0%E3%82%92%E6%89%B1%E3%81%84%E3%81%9F%E3%81%84>

どうも、あんまり「決定的」な方法がないなー、という気がしてました。

## 筆者の事情<a id="sec-1-4" name="sec-1-4"></a>

この日 (2014-12-18) の Lisp Advent Calender のために元々考えてたネタがあったんですが、脳内で放っておいたらどうでもよくなってきて…

なんかもっと面白いことないかな、と思ってきてました。

## 結果<a id="sec-1-5" name="sec-1-5"></a>

**[何かようわからんが、 Lisp に寄せて streem 実装してみるか](http://dic.nicovideo.jp/a/%E4%BD%95%E3%81%8B%E3%82%8F%E3%81%8B%E3%82%89%E3%82%93%E3%81%8C%E3%81%8F%E3%82%89%E3%81%88%E3%83%83!)**

コードを書きました。 <https://github.com/y2q-actionman/stleem>

名前は、 **stleem** にしました。これは、 僕が l と r の発音上の区別が付かない [Engrish](http://ja.wikipedia.org/wiki/Engrish) 野郎であることに由来しています。

# コード例<a id="sec-2" name="sec-2"></a>

本家 streem の例にある FizzBuzz から。

```cl
(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.  1 から 100 まで列挙。
2.  3 や 5 の倍数だった置きかえる。
3.  標準出力に書く
4.  結果のリストを得る。
ことが達成されます。

実行結果は以下です。

    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>

# 実装<a id="sec-3" name="sec-3"></a>

## 並列化<a id="sec-3-1" name="sec-3-1"></a>

### Threading<a id="sec-3-1-1" name="sec-3-1-1"></a>

Go 言語には [goroutine](https://gobyexample.com/goroutines) という、言語に密に結合された並列化機構があるそうです。Go 言語実装の streeem でも使われており、上記実装解説記事ではまるで空気のように使われています。いいなあ。

さて、 ANSI Common Lisp (1994年に標準化)には、並列化 API はありません。なんということでしょう。 C言語にも[2011年の規格](http://en.wikipedia.org/wiki/C11_(C_standard_revision))で並列化APIが加わったという、このご時世ににも関わらず、です。

(余談: 筆者が元々考えていた Lisp Advent Calender のネタというのは、この件について滔々と恨み節を述べる…というものでした。この辺の API が加わった Common Lisp 標準の制定を待っています。
いつまでも。)

とはいえ、各種 ANSI Common Lisp 準拠の Common Lisp 処理系は、大抵、独自拡張として並列化 API を持っています。それらを統一して使うための [Bordeaux Threads](http://common-lisp.net/project/bordeaux-threads/) というライブラリがあるので、それを使っています。

こんな感じでスレッドが立てられます:

```cl
;; "Hello, World" を吐くスレッドの作成
(make-thread #'(lambda () (print "Hello, World!")))

;; スレッドの終了を待つ
(join-thread *)
```

### Channel<a id="sec-3-1-2" name="sec-3-1-2"></a>

Go 言語には [channel](http://www.golang-book.com/10/index.htm) という、スレッド間通信機構があるそうです。同じく streeem で使われており、これもまた空気のように使われています。いいなあ。

さて、前述の [Bordeaux Threads の API](http://trac.common-lisp.net/bordeaux-threads/wiki/ApiDocumentation) には、そんな便利なインターフェイスはありません。普通のロックと条件変数しかなく、まあ頑張ればここから組むことも可能かもしれませんが、私めには無理でございました。

今回の用途では、「要素が投入されるまでブロックして待ってくれるキュー」があれば十分です。そのため、 [lparallel](http://lparallel.org/) ライブラリの [lparallel.queue](http://lparallel.org/api/queues/) パッケージを使いました。

### パイプライン化メインループの実装コード<a id="sec-3-1-3" name="sec-3-1-3"></a>

```cl
;;; 各スレッドがやること
(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)))))
```

## 構文解析<a id="sec-3-2" name="sec-3-2"></a>

### S式にしてさぼる<a id="sec-3-2-1" name="sec-3-2-1"></a>

streem や streeem では、構文解析に多くのコードが割かれています。構文解析器を作るというのは相当に手間どる作業であることは、皆々様ご存知だと思います。

一方 stleem では、思い切って、 **構文を全部S式で記述して下さい** とユーザの皆様にお願いすることにしました。これにより、構文解析から解放され、標準的なリスト操作関数だけで実装は完結します。

(余談: Lisper がS式に閉じこもってしまう一因は、こういう構文解析から解放されたいという願望だと思います。たぶん。)

コード

```cl
;;; 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))
```

### シンボルの処遇<a id="sec-3-2-2" name="sec-3-2-2"></a>

streem の例には、 `STDIN`, `STDOUT` という謎のシンボルがあります。これらはどう扱ったものでしょうか。

これらだけを stleem で特殊に扱ってあげるのは、妙な複雑度を増してしまいそうです。かといって `(STDIN)`, `(STDOUT)` なんて書かせると、 **「うわああ Lisper だあああ」** と言われるんじゃないかな…と筆者は被害妄想してしまいます。

結局、 `define-symbol-macro` で適当に置きかえるようにしました。

```cl
;; 任意 stream への出力用フィルタ
(defun stleem-write-driver (stream)
  #'(lambda (obj)
      (format stream "~&~A~%" obj)
      obj))

;; stdout というシンボルを、上の関数の呼び出しにおきかえる
(define-symbol-macro stdout
    (stleem-write-driver *standard-output*))
```

# 将来性<a id="sec-4" name="sec-4"></a>

こんな感じでストリーム指向っぽい書き方を実装してみたわけですが、僕自身はこれを使わない気がします。というのも、 Common Lisp の強力な反復処理記述用 DSL である [iterate](http://common-lisp.net/projects/iterate/index.html) との統合を考えたいためです。
前述の例を、それぞれ iterate で書いてみましょう:

```cl
(defun cat ()
  (iterate:iter
    (for l next (read-line *standard-input* nil nil))
    (while l)
    (write-line l *standard-output*)))
```

```cl
(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 に導入した方が、既存のコードともっと融和できるんじゃないかな…

と思いはじめたところで、この記事は終わりです。