マクロと限定継続

@halcat0x15a

型推論器の副産物

• typelogic <- 型推論
• clog <- 論理プログラミング
• cont <- 限定継続
• unapply <- パターンマッチ

限定継続(shift/reset)

shiftはresetまでの継続をとる

(reset (+ (shift k (k 1)) 2)) ; => 3

; k = (fn [x] (+ x 2))

実装

shiftは継続コンテキストを返す

resetはcallによる継続渡し形式に変換

callは継続を適用する

(macroexpand (quote (reset (+ (shift k (k 1)) 2))))

(cont.core/call +
  (fn* [G__3646]
    (cont.core/call (new cont.core.Context (fn* [k] (k 1)))
      (fn* [G__3647]
        (cont.core/call (G__3646 G__3647 2)
          (fn* [G__3645] G__3645))))))

例

非決定性計算

(defn amb [& xs]
  (shift k (mapcat k xs)))

(reset
  (let [x (amb 1 2 3)
        y (amb 2 4 6)]
    (if (zero? (mod (+ x y) 3))
      (list [x y]))))

; => ([1 2] [2 4] [3 6])

継続とモナド

ambの計算はListモナドと同じ

do
  x <- [1, 2, 3]
  y <- [2, 4, 6]
  guard $ mod (x + y) 3 == 0
  return (x, y)

-- => [(1,2),(2,4),(3,6)]

継続を>>=に渡すことでdo構文を表現できる

(defprotocol Monad
  (>>= [a f]))

(defn <- [a] (shift k (>>= a k)))

(extend-protocol Monad
  clojure.lang.PersistentVector
  (>>= [v f] (vec (mapcat f v))))

(reset
  (let [x (<- [1 3])
        y (<- [2 4])]
    [(* x y)]))

; => [2 4 6 12]

Scala

Scalaのマクロでも実現可能

def amb[A, B](xs: A*) =
  shift((k: A => List[B]) => xs.toList.flatMap(k))
 
val example1 =
  reset {
    val x = amb(1, 3)
    val y = amb(2, 4)
    List((x, y))
  }

// => List((1,2), (1,4), (3,2), (3,4))

型付け

• A: 継続に返る型
• B: 継続が返す型
• C: resetに返る型

case class Context[+A, -B, +C](cc: (A => B) => C)
  extends AnyVal

resetの型はBとCが一致するという条件の元で決定可能

def reset[A](expr: A)(implicit ans: Ans[A]): ans.Type =
  macro resetImpl

まとめ

• 限定継続実装でモナド構文実装可能
• マクロと抽象化機構があればshift/resetが実現可能

参考

函数プログラミングの集い 2012 in Tokyo で発表してきました。