picrin:モナド的リストオペレータの Scheme への導入 (限定継続を用いて)

picrin:モナド的リストオペレータの Scheme への導入 (限定継続を用いて)

原文


何日か前に、 list-monad ブランチを Picrin Scheme のマスターへマージしました。 このブランチはモナド・マジックでとても効果的にリストやリスト上の関数を操作するツール群を含んでいます。 以下でリスト構築、選択、写像などのようなリストモナドオペレータの典型的な場合を説明します。 このチュートリアルがあなたのスキームライフをより良いものにすることを願っています!

私達のモナドオペレータの概観

Picrin Scheme は R7RS Scheme ですので、私達のモナドオペレータは R7RS スタイルライブラリに分離されており、これは (picrin control list) と呼ばれます。 このライブラリをインポートすれば準備は終わりです。 モナドライブラリは 4 つのオブジェクトをエクスポートします。

私達のオペレータがリスト操作のための単相であるのに対し、ハスケルの語彙では、これらはそれぞれ 4 つの多相構文 do, <-, return, mzero に対応します。 あなたが良いハスケルプログラマなら、私達のリストモナドオペレータでリスト操作を書くのはとても簡単なはずです。 ここで私はリストモナドの説明について Real World Haskell から例を取ります。 以下の例でcomprehensiveは xs と ys の要素から全ての可能なペアのリストを構築する関数です。

comprehensive xs ys =
  do x <- xs
     y <- ys
     return (x,y)

-- comprehensive [1,2] "bar" == [(1,'b'),(1,'a'),(1,'r'),(2,'b'),(2,'a'),(2,'r')]

私達のリストモナドオペレータを使用すると、このコードを素早く Scheme に変換することが出来ます。

(define (comprehensive xs ys)
  (for (let ((x (in xs))
             (y (in ys)))
         (yield (cons x y)))))

もうひとつの例は選択です。 実際には、最初の例はアプリカティブスタイルと呼ばれるもので、モナドを使わずに書くことが出来ます。 ペアの生成は実行時の引数の値の状態に応じて分岐しないため、より制限された形で書くことが出来ます。 しかし、私達のオペレータは分岐を行うことが出来ます。 以下の例はinによってピックアップされた値による条件分岐が正しく動作することと、私達のオペレータがモナドと同等に強力であることの実証です。

-- Haskell
filter pred xs =
  do x <- xs
     if pred x then
       return x
     else
       mzero
; Scheme
(define (filter pred xs)
  (for (let ((x (in xs)))
         (if (pred x)
             (yield x)
             (null)))))

このコードではリストが MonadPlus のインスタンスであるという事実を使用しているということに注意して下さい。 既に気付いているかもしれませんが、それがどんな式であっても for 構文の中に入れることが出来ます。これは私達のアプローチとハスケルの間の最大の違いで、その do ブロックは構文のどんな種類も起くことを許可されている「普通の」ブロックではありません。

以下、オペレータの詳細な使用方法。

もしあなたが Clojure 使いなら、私達の for オペレータは Clojure の for マクロと同じであることを期待するかもしれません。 私達の for オペレータは表現力で勝っています。 Clojure の for マクロでのフィルタリングは :when ステートメントなしでは実行することが出来ません。 私達の for オペレータでは、あなた自身のガード構文を書くことが出来ます。

(define (guard test)
  (unless test
    (in '())))   ; 空リストからひとつの値を選択すると、失敗を意味する

以下、使い方。

(for (let ((x (in (iota 10))))
       (guard (even? x))
       (yield x)))

;=> (0 2 4 6 8)

内部では何が?

内部的には、これらのオペレータは限定継続上に実装されています。 基本的に、モナドは連続的で構成可能な計算のための抽象化ですが、別の面から見ると、それが継続渡しスタイルの形態の一種であると考えられます。 実際、 継続モナドは存在しています。 ネイティブ継続をサポートしていないハスケルで call/cc を模倣するためにモナドと CPS の力を使用しています。

限定継続 (別名:部分継続) は最近研究されている継続の派生物です。 そして Picrin は限定継続 (shift/rest オペレータ) を一箇月にわたって実験的にサポートしてきました。 この段落で限定継続を説明するのは困難です。 インターネット上に限定継続についての良い記事はたくさんあるはずなので、あとで確認してみて下さい。

既に限定継続 とは何かを知っているなら、 for 構文のマジックを理解することは簡単です。

(define-syntax for
  (syntax-rules ()
    ((_ expr)
     (reset (lambda () expr)))))

(define (in m)
  (shift (lambda (k)
           (apply append (map k m)))))

(define (yield x)
  (list x))

in オペレータの定義とリストモナドの bind オペレータの定義がとてもよく似ていることに注意して下さい。

m >>= f = concat (map f m)   -- List Monad (simplified version)

また、リストモナドの yield と return は完全に同じように動作します。

return x = [x]

御想像の通り、ハスケルの do と私達の for マクロは実際にはよく似た動作をしますが、書き方の重視する点が異なっています。本体式の CPS 変換の動作のかわりに、関数内でダイレクトスタイル (DS) で書かれた文脈から限定継続を抽出します。 for マクロはマーカーの役割を単純に演じる一方、ハスケルの do 式は CPS 変換です。

他のシステムとの比較

私達のオペレータの利点のひとつは簡潔さです。 私達は 4 つのオペレータを提供し、全ての操作を行うために充分に強力です。 srfi-42 (別名: list-ec) と loop マクロは私達と同様の問題に取り組むが、その悪いことは彼等がオペレータの削減ではなく追加しようとしていていることです。

それらは内部に 2 ダース以上の構文を含んでおり、ユーザはマクロの全力を使うために全てを覚えておく必要があります。 それは支払うにはあまりにも高価です。 私達のアプローチは明らかに逆です。 4 つのオペレータを覚えるだけで、必要に応じて、通常の関数やマクロ (例えば上記のガード機能) を定義することで構文を拡張することが出来ます。 この簡潔さは Scheme の理念によく合います。

いくつかの巨大なリストにこのマクロを使用している場合は、私達のオペレータとハスケルのオペレータの違いを理解する必要があります。 ハスケルと異なり、私達のリストモナドよる操作は全て貪欲な戦略で行われることに注意しなければなりません。 コンシングはリスト構築関数を呼出すたびに行われます。 不注意なコードでは大量のメモリ消費と顕著な GC 性能低下の原因になります。

; generates the list of 10000 elements at first
; the large part of the tail will be just discarded
(car (for (let ((x (in (iota 10000))))
            (if (prime? x)
                (yield x)
                (null)))))

このモナドのシステムはリストモナドに制限されません。 モナドの他の種類に拡張することが出来ます。 しかし、ハスケルのモナドが存在する間は厳密な型システムによって安全ではない副作用の全ての実行を禁止するので、 Scheme ではコア言語にこれら安全ではないプリミティブを持ち、 Scheme の I/O や State 風のモナドは絶対的に意味がない。 かわりに、もっと現実的なユースケースは素のスキームで複雑なコードで記述されるものでなければならない。 パーサコンビネータやマルチタスクプログラミングのような。 マルチタスクプログラミングで、私は非同期 I/O の基礎的なサポートを Picrin に導入することを計画しています。 現在の計画では、単一の非同期タスクはひとつの非同期契約オブジェクトにマッピングされ、新しいオペレータが提供されます。 典型的なコードは以下のようになります。

; [async operators]
; async : entering async context
; await : Promise a -> a

; [promise monad]
; then : Promise a -> (a -> Promise b) -> Promise b
; resolve : a -> Promise a
; join : [Promise a] -> Promise [a]

; [preloaded function]
; http-get-url : String -> Promise String

(define (http-get-urls urls)
  (join (map http-get-url urls)))

(define (get-all-pages urls)
  (async
    (let ((pages (await (http-get-urls urls))))
      (resolve (apply string-append pages)))))

結論

限定継続を使用して、モナドオペレータを Scheme 上に作成しました。 今回作ったものはリスト操作のためのオペレータであり、容易にモナドの他の種類に拡張することが出来ます。 副作用で操作を表すためにしばしば使用された、モナドは計算のための抽象レイヤとしてとても有用です。 私達の for オペレータの簡潔さと力をモナドから得ました。

More ...