パラメータを用いたポリモーフィズムの実験

モナド的な何かに向かってにおいて、「false かそれ以外か」という二元論のみに基づいた (つまり、Haskell のように特殊なコンテナを用いない) Maybe モナドの実現可能性について考察しました (実装)。

一応それはうまくいったように思うんですが、今度は、別のモナドを新しくそこに導入することが可能だろうか、という疑問が生じました。

Haskell のような型とかクラスのシステムが無い世界において、複数のモナドで共通の関数 (>>=, return など) を使うことが出来るだろうか、という疑問です。

例えば、>>= (bind と読みます) という、値と演算を橋渡しするための関数があります:

(define (>>= x f)
  ...)

この場合、値 x の型を調べることで、関数 f と x とを繋ぐ仕方を適宜選択することができると思います (dispatch on type):

(define (>>= x f)
  (if (list? x)
      (apply append! (map f x))
      ...

ところが、大きな壁にぶつかりました。return という、モナドでない値をモナドにする関数では、この方法が使えないんです:

;; Maybe monad
(define (return x)
  (Just x))

;; List monad
(define (return x)
  (list x))

ここで x として与えられるのは普通の Scheme の値に過ぎず、それをどのモナドとして使いたいのかという文脈は、値からは全く推測できないんです。

第二引数でモナドのタイプを指定する方法も考えましたが、コードが汚くなりそうで嫌でした。

非常に悩んだんですが、逆転の発想で、「文脈」を外から設定してやるという方法を思いつきました。

つまり、リストモナドの処理をしている間は return 等にリストモナドとしての意味を持たせるようにするのです。

これにはパラメータという仕組みを用います。

(define poly-return (make-parameter #f))

(define (return x)
  ((poly-return) x))

(parameterize ((poly-return (lambda (x) (list x))))
  (return 'foo))
; => (foo)

poly-return というプレースホルダのようなものに依存させることで return 自体には意味を持たせず、文脈によって意味が変わるようにするわけです (ここで return をパラメータ化していないのは、呼び出すのに括弧が余計に要るという不都合を隠蔽するためです)。

ちなみに parameterize というマクロは Common Lisp 等のダイナミック変数と同様の働きをするもので、パラメータ (make-parameter で作られたオブジェクト) の値を、ブロックの実行の期間だけ変更する、というものです。

具体的にはこんな形で、後から新しいモナドを追加できるモナド・システムが作れるんじゃないかと考えました:

(define (ignore . _) #f)
(define poly-bind ignore)
(define poly-return (make-parameter #f))
(define poly-fail (make-parameter #f))

(define (return x)
  ((poly-return) x))
(define (fail x)
  ((poly-fail) x))

(define (install-monad type? bind return fail)
  (let ((poly-bound poly-bind))
    (set! poly-bind (lambda (x f)
                      (if (type? x)
                          (parameterize ((poly-return return)
                                         (poly-fail fail))
                            (bind x f))
                          (poly-bound x f))))))

(define (>>= x f . fs)
  (let ((x (poly-bind x f)))
    (and x
         (if (null? fs)
             x
             (apply >>= x fs)))))
...

poly-bind という関数に、インストールされるモナドの情報が、クロージャの重ね着状態として保持されます (効率の良い方法じゃないかも知れませんが)。

>>= 関数が呼び出されると、その中からデータ型に適合した bind 関数が選ばれ、値が算出されます。そしてその間 return, fail も適切な内容にセットされます。

さて、これでうまくいったかと思ったんですが、実際には問題の半分が解決したに過ぎませんでした。と言うのは

(>>= (return x) f)

のようなパターンでは、>>= によって文脈が設定される前に return が評価されてしまうからです。

Haskell だとこういう場合、関数 f の型を調べて return の型を推論する、ということが出来るんでしょうが、Scheme では無理です。

新たな無理難題を抱える結果となってしまいました…。

追記 [20070715]:

文脈が設定される前に return が呼ばれたときの対策ですが、こういうのを考えました。

(define (infer-return x) (delay x))
(define poly-return (make-parameter infer-return))

(define (install-monad type? bind return fail)
  (let ((poly-bound poly-bind))
    (set! poly-bind
          (lambda (x f)
            (if (promise? x)
                (or (bind-within-context
                     (delay (try-bind x f bind return))
                     return fail)
                    (poly-bound x f))
                (if (type? x)
                    (bind-within-context
                     (delay (bind x f))
                     return fail)
                    (poly-bound x f)))))))

(define (try-bind x f bind lift)
  (with-handlers ((exn:fail? ignore))
    (bind (lift (force x)) f)))

(define (bind-within-context bind return fail)
  (parameterize ((poly-return return)
                 (poly-fail fail))
    (force bind)))

まず、文脈が未定義の場合は infer-return という関数が呼ばれるようにします。そして、delay でなくても良いんですが、とにかくどのモナド型に変換するかを考慮中という印を値に付けておくわけです。

で、その値が poly-bind に渡って来たら、インストールされているモナド型に順に当てはめて演算していき、成功するまでそれを繰り返します。

とりあえずはそんな感じです。