Scalaの限定継続で四天王問題を解く例にprintlnを仕込んで解析してみた

Amb.scala

// papamitraさんの「Scalaの限定継続で四天王問題解いてみた」
// http://d.hatena.ne.jp/papamitra/20100912/continuations
//
// について、何が起こっているのかわからなかったので、println仕込んで解析してみた。
//
// 実行方法
// scalac -P:continuations:enable Amb.scala

import scala.util.continuations._

object Amb{

  def amb(lst:Int*):Int @ cpsParam[Unit,Unit] = shift { k:(Int=>Unit) => lst.foreach { x =>
    println("continue with " + x)
    k(x)
  }}
  def require(p:Boolean):Unit @ cpsParam[Unit,Unit] = shift { k:(Unit=>Unit) => if(p) {
    println("require:" + p)
    k()
  }}

  def distinct(lst:Int*)= {
    def proc(l:List[Int]):Boolean = l match{
      case Nil => true
      case x::xs => (xs.indexOf(x)<0) && proc(xs)
    }
    val result = proc(lst.toList)
    println("distinct: " + result)
    result
  }

  def main(args:Array[String]){
    reset{
      val a,b,c,d = amb(1,2,3,4)

      println("a=" + a + ", b=" + b + ", c=" + c + ", d=" + d)

      // 同順が無いことを仮定
      require(distinct(a,b,c,d))

      // A「Dがやられたようだな…」B「ククク…奴は我ら四天王の中でも最弱…」
      require(d==4)

      // C「私はBよりも弱い…」
      require(b < c)

      // A「そして私は最強ではない…」
      require(a != 1)

      // B「四天王の中に私よりも弱いものが最低でも二人いる…」
      require(b==1 || b==2)

      // C「私はAよりも強い…」
      require(c < a)

      // ※以上の条件から四天王を強い順に並べよ（5点）
      println(("abcd" zip List(a,b,c,d)).toList.sortWith(_._2 < _._2))
    }
  }
}

output.txt

continue with 1
continue with 1
continue with 1
continue with 1
a=1, b=1, c=1, d=1
distinct: false
continue with 2
a=1, b=1, c=1, d=2
distinct: false
continue with 3
a=1, b=1, c=1, d=3
distinct: false
continue with 4
a=1, b=1, c=1, d=4
distinct: false
continue with 2
continue with 1
a=1, b=1, c=2, d=1
distinct: false
continue with 2
a=1, b=1, c=2, d=2
distinct: false
continue with 3
a=1, b=1, c=2, d=3
distinct: false
continue with 4
a=1, b=1, c=2, d=4
distinct: false
continue with 3
continue with 1
a=1, b=1, c=3, d=1
distinct: false
continue with 2
a=1, b=1, c=3, d=2
distinct: false
continue with 3
a=1, b=1, c=3, d=3
distinct: false
continue with 4
a=1, b=1, c=3, d=4
distinct: false
continue with 4
continue with 1
a=1, b=1, c=4, d=1
distinct: false
continue with 2
a=1, b=1, c=4, d=2
distinct: false
continue with 3
a=1, b=1, c=4, d=3
distinct: false
continue with 4
a=1, b=1, c=4, d=4
distinct: false
continue with 2
continue with 1
continue with 1
a=1, b=2, c=1, d=1
distinct: false
continue with 2
a=1, b=2, c=1, d=2
distinct: false
continue with 3
a=1, b=2, c=1, d=3
distinct: false
continue with 4
a=1, b=2, c=1, d=4
distinct: false
continue with 2
continue with 1
a=1, b=2, c=2, d=1
distinct: false
continue with 2
a=1, b=2, c=2, d=2
distinct: false
continue with 3
a=1, b=2, c=2, d=3
distinct: false
continue with 4
a=1, b=2, c=2, d=4
distinct: false
continue with 3
continue with 1
a=1, b=2, c=3, d=1
distinct: false
continue with 2
a=1, b=2, c=3, d=2
distinct: false
continue with 3
a=1, b=2, c=3, d=3
distinct: false
continue with 4
a=1, b=2, c=3, d=4
distinct: true
require:true
require:true
require:true
continue with 4
continue with 1
a=1, b=2, c=4, d=1
distinct: false
continue with 2
a=1, b=2, c=4, d=2
distinct: false
continue with 3
a=1, b=2, c=4, d=3
distinct: true
require:true
continue with 4
a=1, b=2, c=4, d=4
distinct: false
continue with 3
continue with 1
continue with 1
a=1, b=3, c=1, d=1
distinct: false
continue with 2
a=1, b=3, c=1, d=2
distinct: false
continue with 3
a=1, b=3, c=1, d=3
distinct: false
continue with 4
a=1, b=3, c=1, d=4
distinct: false
continue with 2
continue with 1
a=1, b=3, c=2, d=1
distinct: false
continue with 2
a=1, b=3, c=2, d=2
distinct: false
continue with 3
a=1, b=3, c=2, d=3
distinct: false
continue with 4
a=1, b=3, c=2, d=4
distinct: true
require:true
require:true
continue with 3
continue with 1
a=1, b=3, c=3, d=1
distinct: false
continue with 2
a=1, b=3, c=3, d=2
distinct: false
continue with 3
a=1, b=3, c=3, d=3
distinct: false
continue with 4
a=1, b=3, c=3, d=4
distinct: false
continue with 4
continue with 1
a=1, b=3, c=4, d=1
distinct: false
continue with 2
a=1, b=3, c=4, d=2
distinct: true
require:true
continue with 3
a=1, b=3, c=4, d=3
distinct: false
continue with 4
a=1, b=3, c=4, d=4
distinct: false
continue with 4
continue with 1
continue with 1
a=1, b=4, c=1, d=1
distinct: false
continue with 2
a=1, b=4, c=1, d=2
distinct: false
continue with 3
a=1, b=4, c=1, d=3
distinct: false
continue with 4
a=1, b=4, c=1, d=4
distinct: false
continue with 2
continue with 1
a=1, b=4, c=2, d=1
distinct: false
continue with 2
a=1, b=4, c=2, d=2
distinct: false
continue with 3
a=1, b=4, c=2, d=3
distinct: true
require:true
continue with 4
a=1, b=4, c=2, d=4
distinct: false
continue with 3
continue with 1
a=1, b=4, c=3, d=1
distinct: false
continue with 2
a=1, b=4, c=3, d=2
distinct: true
require:true
continue with 3
a=1, b=4, c=3, d=3
distinct: false
continue with 4
a=1, b=4, c=3, d=4
distinct: false
continue with 4
continue with 1
a=1, b=4, c=4, d=1
distinct: false
continue with 2
a=1, b=4, c=4, d=2
distinct: false
continue with 3
a=1, b=4, c=4, d=3
distinct: false
continue with 4
a=1, b=4, c=4, d=4
distinct: false
continue with 2
continue with 1
continue with 1
continue with 1
a=2, b=1, c=1, d=1
distinct: false
continue with 2
a=2, b=1, c=1, d=2
distinct: false
continue with 3
a=2, b=1, c=1, d=3
distinct: false
continue with 4
a=2, b=1, c=1, d=4
distinct: false
continue with 2
continue with 1
a=2, b=1, c=2, d=1
distinct: false
continue with 2
a=2, b=1, c=2, d=2
distinct: false
continue with 3
a=2, b=1, c=2, d=3
distinct: false
continue with 4
a=2, b=1, c=2, d=4
distinct: false
continue with 3
continue with 1
a=2, b=1, c=3, d=1
distinct: false
continue with 2
a=2, b=1, c=3, d=2
distinct: false
continue with 3
a=2, b=1, c=3, d=3
distinct: false
continue with 4
a=2, b=1, c=3, d=4
distinct: true
require:true
require:true
require:true
require:true
require:true
continue with 4
continue with 1
a=2, b=1, c=4, d=1
distinct: false
continue with 2
a=2, b=1, c=4, d=2
distinct: false
continue with 3
a=2, b=1, c=4, d=3
distinct: true
require:true
continue with 4
a=2, b=1, c=4, d=4
distinct: false
continue with 2
continue with 1
continue with 1
a=2, b=2, c=1, d=1
distinct: false
continue with 2
a=2, b=2, c=1, d=2
distinct: false
continue with 3
a=2, b=2, c=1, d=3
distinct: false
continue with 4
a=2, b=2, c=1, d=4
distinct: false
continue with 2
continue with 1
a=2, b=2, c=2, d=1
distinct: false
continue with 2
a=2, b=2, c=2, d=2
distinct: false
continue with 3
a=2, b=2, c=2, d=3
distinct: false
continue with 4
a=2, b=2, c=2, d=4
distinct: false
continue with 3
continue with 1
a=2, b=2, c=3, d=1
distinct: false
continue with 2
a=2, b=2, c=3, d=2
distinct: false
continue with 3
a=2, b=2, c=3, d=3
distinct: false
continue with 4
a=2, b=2, c=3, d=4
distinct: false
continue with 4
continue with 1
a=2, b=2, c=4, d=1
distinct: false
continue with 2
a=2, b=2, c=4, d=2
distinct: false
continue with 3
a=2, b=2, c=4, d=3
distinct: false
continue with 4
a=2, b=2, c=4, d=4
distinct: false
continue with 3
continue with 1
continue with 1
a=2, b=3, c=1, d=1
distinct: false
continue with 2
a=2, b=3, c=1, d=2
distinct: false
continue with 3
a=2, b=3, c=1, d=3
distinct: false
continue with 4
a=2, b=3, c=1, d=4
distinct: true
require:true
require:true
continue with 2
continue with 1
a=2, b=3, c=2, d=1
distinct: false
continue with 2
a=2, b=3, c=2, d=2
distinct: false
continue with 3
a=2, b=3, c=2, d=3
distinct: false
continue with 4
a=2, b=3, c=2, d=4
distinct: false
continue with 3
continue with 1
a=2, b=3, c=3, d=1
distinct: false
continue with 2
a=2, b=3, c=3, d=2
distinct: false
continue with 3
a=2, b=3, c=3, d=3
distinct: false
continue with 4
a=2, b=3, c=3, d=4
distinct: false
continue with 4
continue with 1
a=2, b=3, c=4, d=1
distinct: true
require:true
continue with 2
a=2, b=3, c=4, d=2
distinct: false
continue with 3
a=2, b=3, c=4, d=3
distinct: false
continue with 4
a=2, b=3, c=4, d=4
distinct: false
continue with 4
continue with 1
continue with 1
a=2, b=4, c=1, d=1
distinct: false
continue with 2
a=2, b=4, c=1, d=2
distinct: false
continue with 3
a=2, b=4, c=1, d=3
distinct: true
require:true
continue with 4
a=2, b=4, c=1, d=4
distinct: false
continue with 2
continue with 1
a=2, b=4, c=2, d=1
distinct: false
continue with 2
a=2, b=4, c=2, d=2
distinct: false
continue with 3
a=2, b=4, c=2, d=3
distinct: false
continue with 4
a=2, b=4, c=2, d=4
distinct: false
continue with 3
continue with 1
a=2, b=4, c=3, d=1
distinct: true
require:true
continue with 2
a=2, b=4, c=3, d=2
distinct: false
continue with 3
a=2, b=4, c=3, d=3
distinct: false
continue with 4
a=2, b=4, c=3, d=4
distinct: false
continue with 4
continue with 1
a=2, b=4, c=4, d=1
distinct: false
continue with 2
a=2, b=4, c=4, d=2
distinct: false
continue with 3
a=2, b=4, c=4, d=3
distinct: false
continue with 4
a=2, b=4, c=4, d=4
distinct: false
continue with 3
continue with 1
continue with 1
continue with 1
a=3, b=1, c=1, d=1
distinct: false
continue with 2
a=3, b=1, c=1, d=2
distinct: false
continue with 3
a=3, b=1, c=1, d=3
distinct: false
continue with 4
a=3, b=1, c=1, d=4
distinct: false
continue with 2
continue with 1
a=3, b=1, c=2, d=1
distinct: false
continue with 2
a=3, b=1, c=2, d=2
distinct: false
continue with 3
a=3, b=1, c=2, d=3
distinct: false
continue with 4
a=3, b=1, c=2, d=4
distinct: true
require:true
require:true
require:true
require:true
require:true
require:true
List((b,1), (c,2), (a,3), (d,4))
continue with 3
continue with 1
a=3, b=1, c=3, d=1
distinct: false
continue with 2
a=3, b=1, c=3, d=2
distinct: false
continue with 3
a=3, b=1, c=3, d=3
distinct: false
continue with 4
a=3, b=1, c=3, d=4
distinct: false
continue with 4
continue with 1
a=3, b=1, c=4, d=1
distinct: false
continue with 2
a=3, b=1, c=4, d=2
distinct: true
require:true
continue with 3
a=3, b=1, c=4, d=3
distinct: false
continue with 4
a=3, b=1, c=4, d=4
distinct: false
continue with 2
continue with 1
continue with 1
a=3, b=2, c=1, d=1
distinct: false
continue with 2
a=3, b=2, c=1, d=2
distinct: false
continue with 3
a=3, b=2, c=1, d=3
distinct: false
continue with 4
a=3, b=2, c=1, d=4
distinct: true
require:true
require:true
continue with 2
continue with 1
a=3, b=2, c=2, d=1
distinct: false
continue with 2
a=3, b=2, c=2, d=2
distinct: false
continue with 3
a=3, b=2, c=2, d=3
distinct: false
continue with 4
a=3, b=2, c=2, d=4
distinct: false
continue with 3
continue with 1
a=3, b=2, c=3, d=1
distinct: false
continue with 2
a=3, b=2, c=3, d=2
distinct: false
continue with 3
a=3, b=2, c=3, d=3
distinct: false
continue with 4
a=3, b=2, c=3, d=4
distinct: false
continue with 4
continue with 1
a=3, b=2, c=4, d=1
distinct: true
require:true
continue with 2
a=3, b=2, c=4, d=2
distinct: false
continue with 3
a=3, b=2, c=4, d=3
distinct: false
continue with 4
a=3, b=2, c=4, d=4
distinct: false
continue with 3
continue with 1
continue with 1
a=3, b=3, c=1, d=1
distinct: false
continue with 2
a=3, b=3, c=1, d=2
distinct: false
continue with 3
a=3, b=3, c=1, d=3
distinct: false
continue with 4
a=3, b=3, c=1, d=4
distinct: false
continue with 2
continue with 1
a=3, b=3, c=2, d=1
distinct: false
continue with 2
a=3, b=3, c=2, d=2
distinct: false
continue with 3
a=3, b=3, c=2, d=3
distinct: false
continue with 4
a=3, b=3, c=2, d=4
distinct: false
continue with 3
continue with 1
a=3, b=3, c=3, d=1
distinct: false
continue with 2
a=3, b=3, c=3, d=2
distinct: false
continue with 3
a=3, b=3, c=3, d=3
distinct: false
continue with 4
a=3, b=3, c=3, d=4
distinct: false
continue with 4
continue with 1
a=3, b=3, c=4, d=1
distinct: false
continue with 2
a=3, b=3, c=4, d=2
distinct: false
continue with 3
a=3, b=3, c=4, d=3
distinct: false
continue with 4
a=3, b=3, c=4, d=4
distinct: false
continue with 4
continue with 1
continue with 1
a=3, b=4, c=1, d=1
distinct: false
continue with 2
a=3, b=4, c=1, d=2
distinct: true
require:true
continue with 3
a=3, b=4, c=1, d=3
distinct: false
continue with 4
a=3, b=4, c=1, d=4
distinct: false
continue with 2
continue with 1
a=3, b=4, c=2, d=1
distinct: true
require:true
continue with 2
a=3, b=4, c=2, d=2
distinct: false
continue with 3
a=3, b=4, c=2, d=3
distinct: false
continue with 4
a=3, b=4, c=2, d=4
distinct: false
continue with 3
continue with 1
a=3, b=4, c=3, d=1
distinct: false
continue with 2
a=3, b=4, c=3, d=2
distinct: false
continue with 3
a=3, b=4, c=3, d=3
distinct: false
continue with 4
a=3, b=4, c=3, d=4
distinct: false
continue with 4
continue with 1
a=3, b=4, c=4, d=1
distinct: false
continue with 2
a=3, b=4, c=4, d=2
distinct: false
continue with 3
a=3, b=4, c=4, d=3
distinct: false
continue with 4
a=3, b=4, c=4, d=4
distinct: false
continue with 4
continue with 1
continue with 1
continue with 1
a=4, b=1, c=1, d=1
distinct: false
continue with 2
a=4, b=1, c=1, d=2
distinct: false
continue with 3
a=4, b=1, c=1, d=3
distinct: false
continue with 4
a=4, b=1, c=1, d=4
distinct: false
continue with 2
continue with 1
a=4, b=1, c=2, d=1
distinct: false
continue with 2
a=4, b=1, c=2, d=2
distinct: false
continue with 3
a=4, b=1, c=2, d=3
distinct: true
require:true
continue with 4
a=4, b=1, c=2, d=4
distinct: false
continue with 3
continue with 1
a=4, b=1, c=3, d=1
distinct: false
continue with 2
a=4, b=1, c=3, d=2
distinct: true
require:true
continue with 3
a=4, b=1, c=3, d=3
distinct: false
continue with 4
a=4, b=1, c=3, d=4
distinct: false
continue with 4
continue with 1
a=4, b=1, c=4, d=1
distinct: false
continue with 2
a=4, b=1, c=4, d=2
distinct: false
continue with 3
a=4, b=1, c=4, d=3
distinct: false
continue with 4
a=4, b=1, c=4, d=4
distinct: false
continue with 2
continue with 1
continue with 1
a=4, b=2, c=1, d=1
distinct: false
continue with 2
a=4, b=2, c=1, d=2
distinct: false
continue with 3
a=4, b=2, c=1, d=3
distinct: true
require:true
continue with 4
a=4, b=2, c=1, d=4
distinct: false
continue with 2
continue with 1
a=4, b=2, c=2, d=1
distinct: false
continue with 2
a=4, b=2, c=2, d=2
distinct: false
continue with 3
a=4, b=2, c=2, d=3
distinct: false
continue with 4
a=4, b=2, c=2, d=4
distinct: false
continue with 3
continue with 1
a=4, b=2, c=3, d=1
distinct: true
require:true
continue with 2
a=4, b=2, c=3, d=2
distinct: false
continue with 3
a=4, b=2, c=3, d=3
distinct: false
continue with 4
a=4, b=2, c=3, d=4
distinct: false
continue with 4
continue with 1
a=4, b=2, c=4, d=1
distinct: false
continue with 2
a=4, b=2, c=4, d=2
distinct: false
continue with 3
a=4, b=2, c=4, d=3
distinct: false
continue with 4
a=4, b=2, c=4, d=4
distinct: false
continue with 3
continue with 1
continue with 1
a=4, b=3, c=1, d=1
distinct: false
continue with 2
a=4, b=3, c=1, d=2
distinct: true
require:true
continue with 3
a=4, b=3, c=1, d=3
distinct: false
continue with 4
a=4, b=3, c=1, d=4
distinct: false
continue with 2
continue with 1
a=4, b=3, c=2, d=1
distinct: true
require:true
continue with 2
a=4, b=3, c=2, d=2
distinct: false
continue with 3
a=4, b=3, c=2, d=3
distinct: false
continue with 4
a=4, b=3, c=2, d=4
distinct: false
continue with 3
continue with 1
a=4, b=3, c=3, d=1
distinct: false
continue with 2
a=4, b=3, c=3, d=2
distinct: false
continue with 3
a=4, b=3, c=3, d=3
distinct: false
continue with 4
a=4, b=3, c=3, d=4
distinct: false
continue with 4
continue with 1
a=4, b=3, c=4, d=1
distinct: false
continue with 2
a=4, b=3, c=4, d=2
distinct: false
continue with 3
a=4, b=3, c=4, d=3
distinct: false
continue with 4
a=4, b=3, c=4, d=4
distinct: false
continue with 4
continue with 1
continue with 1
a=4, b=4, c=1, d=1
distinct: false
continue with 2
a=4, b=4, c=1, d=2
distinct: false
continue with 3
a=4, b=4, c=1, d=3
distinct: false
continue with 4
a=4, b=4, c=1, d=4
distinct: false
continue with 2
continue with 1
a=4, b=4, c=2, d=1
distinct: false
continue with 2
a=4, b=4, c=2, d=2
distinct: false
continue with 3
a=4, b=4, c=2, d=3
distinct: false
continue with 4
a=4, b=4, c=2, d=4
distinct: false
continue with 3
continue with 1
a=4, b=4, c=3, d=1
distinct: false
continue with 2
a=4, b=4, c=3, d=2
distinct: false
continue with 3
a=4, b=4, c=3, d=3
distinct: false
continue with 4
a=4, b=4, c=3, d=4
distinct: false
continue with 4
continue with 1
a=4, b=4, c=4, d=1
distinct: false
continue with 2
a=4, b=4, c=4, d=2
distinct: false
continue with 3
a=4, b=4, c=4, d=3
distinct: false
continue with 4
a=4, b=4, c=4, d=4
distinct: false

run.sh

scala -P:continuations:enable Amb.scala > output.txt

理解のポイント

val a,b,c,d = amb(1,2,3,4)

により、a・ｂ・ｃ・ｄそれぞれについて、1・２・３・４の４値が順番に与えられて継続されるところがポイント。

つまり、Scala的には、
val a,b,c,d = amb(1,2,3,4)
においてまず
val a = amb(1,2,3,4)
が評価される。
ambは初回に1、次に2,3,4というように、1-4の値を順番に返して継続するので、
val a = amb(1,2,3,4)
は
a に 1を束縛して継続することになる。

aが決まったので、
val a,b,c,d = amb(1,2,3,4)
において次に評価されるのは、
val b = amb(1,2,3,4)
である。

これも、前述のa同様に、1から4について順番に継続される。
結局、初回の

val a,b,c,d = amb(1,2,3,4)

の評価は、
a, b, c, d すべてに1を束縛して継続することになる。

後は、distinctやrequireにより条件を満たさなかった場合、関数の実行がそこで終わるため、別の値について継続される。
(a,b,c,d) = (1,1,1,1) がいずれかのrequireやdistinctを満たさなければ、次は
(1,1,1,2)
(1,1,1,3)
(1,1,1,4)
(1,1,2,1)
(1,1,2,2)
(1,1,2,3)
中略
(4,4,4,4)
のように継続されて、すべてのdistinctやrequireを通った結果だけが解として出力される。

一見論理プログラミングをしているように見えるコードだが、
実際は継続を使って総当りで解を検索しているといえる。