Hatena::ブログ(Diary)

映画は中劇 このページをアンテナに追加 RSSフィード

2017-03-23

[][] 限定継続 (delimited continuation) の動作を理解する

限定継続のオペレータであるshift/resetおよびcontrol/promptについて、その動作が腑に落ちたので、以下にまとめます。

継続とは

継続とは、呼び出されると「この後の計算」を実行する関数です。

Schemeにはcall/ccという関数が存在し、プログラムの任意の箇所で「この後の計算」が取り出せます。たとえば次のプログラムでは、gobackにcall/ccを呼び出した箇所の継続が束縛されます。gobackを呼び出すことで、call/cc呼び出しのところに制御が戻るため、1ずつ値を足しながら無限ループします。

(let ((pair (call/cc (lambda (cont) (list 0 cont)))))
  (let ((n (car pair)) (goback (cadr pair)))
    (print n)
    (newline)
    (goback (list (+ n 1) goback))))

; => 1 2 3 4 5 ....

仮にKinkで書くとこんな感じです。Kinkにcallccは無いけれど。

[:N :goback] = callcc{(:cont)
  [0 $cont]
}
print_line(N)
goback(N + 1 $goback)
# => 1 2 3 4 5 ...

call/ccによって取り出される継続は、呼び出されると、呼び出し元に戻ってくることがありません。「この後の計算」はその実行文脈(スレッドとか)が終わるまで続き、終わったらその実行文脈はおしまいです。つまり、returnのあるcallではなく、jumpです。

限定継続とは

限定継続とは、「この後の計算」の範囲に区切りをつけた (delimit) 継続です。限定継続は呼び出されると、区切りのところまで処理を進めて、呼び出し元に戻ります。

限定継続を扱うオペレータとしては、reset(区切りをつける)とshift(継続を取り出す)のペア、prompt(区切りをつける)とcontrol(継続を取り出す)のペアなど、いくつかの組み合わせが提唱されています。

shift/resetの使い方については、次の記事が分かりやすいです。

shit/resetの応用例として、ジェネレータ(イテレータ)を手続き的に生成する例を挙げます。実装言語はKinkです。

ジェネレータは2つの関数on_itemとon_endを引数に取って、要素が無ければon_endを呼び、要素があればon_item(現在の要素 次の要素以降のジェネレータ)を呼ぶ関数だ、ということにします。ジェネレータについて、eachやmapは次のように定義できます。

:map = {(:gen :trans)
  {(:on_item :on_end)
    gen(
      {(:V :next_gen)
        on_item(trans(V) map($next_gen $trans))
      }
      $on_end
    )
  }
}

:each = {(:gen :consume)
  gen(
    {(:V :next_gen)
      consume(V)
      each($next_gen $consume)
    }
    {}
  )
}

ベクタの要素を列挙するジェネレータは次のように定義できます。

:vec_gen = {(:Vec)
  {(:on_item :on_end)
    Vec.empty?.then(
      $on_end
      { on_item(Vec.first vec_gen(Vec.drop(1))) }
    )
  }
}

:nums = vec_gen([10 20 30])
:doubled_nums = map($nums {(:N) N * 2 })
each($doubled_nums $print_line)
# => 20 40 60

ベクタのような単純なデータ構造ならともかく、木やグラフのような複雑なデータ構造を扱う場合、上記のvec_genのように、ジェネレータを関数的に定義するのは困難です。ここで限定継続 (shift/reset) を使うと、Pythonのジェネレータのように、手続き的にジェネレータが定義できます。次のプログラムのcogenは、手続き的にジェネレータを作るための関数です。

:cogen = {(:fun)
  :yield = {(:V)
    shift{(:k) ['yielded' V $k] }
  }
  _make_cogen{
    reset{
      fun($yield)
      'returned'
    }
  }
}

:_make_cogen = {(:enter)
  {(:on_item :on_end)
    enter.switch(
      ['yielded' :V :k] {
        :reenter = { k 'returned' }
        on_item(V _make_cogen($reenter))
      }
      'returned' $on_end
    )
  }
}

10, 20, 30を列挙するジェネレータは次のように作れます。

:nums = cogen{(:yield)
  yield(10)
  yield(20)
  yield(30)
}

:doubled_nums = map($nums {(:N) N * 2 })
each($doubled_nums $print_line)
# => 20 40 60

Kinkには現在shift/resetがないので、上記のプログラムは動きません。入れるとしたら、下述するタグ付き限定継続を入れるので、どっちにしろ上記はそのままでは動かないはずです。

Oleg Kiselyov氏は An argument against call/cc という記事で、call/ccが扱いづらく危険であること、むしろ言語処理系は限定継続をプリミティブとして提供するべきであることを主張しています。確かに、call/ccによる継続はいわばgotoですから、危険であることは納得できます。

しかしながら限定継続のオペレータは、構成要素が多いだけに動作が微妙であり、直感的に把握しづらいという難点があります。微妙なところとは、たとえば、限定継続の処理自体がresetの中で実行されるのか、shiftのbody部の処理はresetの中で実行されるのか、などです。次の節で見るように、shift/resetとcontrol/promptは、このような微妙な動作が異ります。

各オペレータの動作

shift/reset, control/promptを、実装してみることで動作を理解します。

実装には、Schemeから派生した言語であるRacketを使います。Racketでは、プリミティブな継続オペレータとして、make-continuation-prompt-tag, call/prompt, call/comp, abort/ccという関数が提供されています。これらを組み合わせることで、shift/reset, control/prompt, それにcall/ccも実現できます。

  • (make-continuation-prompt-tag sym): Racketでは複数種類の継続区切りが区別できます。make-continuation-prompt-tagは、区切りを区別するためのタグを作ります。
  • (call/prompt thunk tag on-abort): tagで指定されたタグについて、継続を区切ってthunkを呼びます。thunkの中でabort/ccが呼ばれたときには、on-abortを呼びます。on-abortは継続区切りの外で呼ばれます。
  • (call/comp proc tag): tagで指定されたタグについて、一番内側の区切りまで計算する限定継続を引数としてprocを呼びます。
  • (abort/cc tag v ...): tagで指定されたタグについて、一番内側の区切りまで飛んで戻ります。v ...は、call/promptで指定したon-abortに渡す引数です。

Racketの継続まわりのリファレンスは次のページです。

これらのプリミティブであれば、それぞれ実装を想像するのはなんとか可能です。call/promptはスタックに区切りのフレームを積んでthunkを呼ぶのでしょう。call/compはスタックを最内の区切りまで切り取っておいて、呼び出されるとスタックの切れ端を現在のスタックに乗っけて評価をはじめるような関数を作るのでしょう。abort/ccは、最内の区切りまでのスタックを切り捨ててからon-abortを呼ぶのでしょう。

Racketの継続プリミティブを組み合わせて、私家版のshift/resetを作ってみます。

#lang racket
(require racket/control)

(define my-tag (make-continuation-prompt-tag 'my-tag))

(define (*my-reset thunk)
  (call/prompt
    thunk
    my-tag
    (lambda (abort-thunk) (abort-thunk))))

(define (*my-shift fun)
  (call/comp
    (lambda (k)
      (let ((kk (lambda (v) (*my-reset (lambda () (k v))))))
        (abort/cc my-tag (lambda () (*my-reset (lambda () (fun kk)))))))
    my-tag))

(define-syntax my-reset
  (syntax-rules ()
                ((_ body ...)
                 (*my-reset (lambda () body ...)))))

(define-syntax my-shift
  (syntax-rules ()
                ((_ k body ...)
                 (*my-shift (lambda (k) body ...)))))

promptはresetの別名ですが、shiftとcontrolの実装は異ります。具体的には、shiftに渡される限定継続の処理がresetの中で実行されるのに対して、controlに渡される限定継続の処理はpromptの外で実行されます。

#lang racket
(require racket/control)

(define *my-prompt *my-reset)

(define (*my-control fun)
  (call/comp
    (lambda (k)
      (abort/cc my-tag (lambda () (*my-prompt (lambda () (fun k))))))
    my-tag))

(define-syntax my-prompt
  (syntax-rules ()
                ((_ body ...)
                 (my-reset body ...))))

(define-syntax my-control
  (syntax-rules ()
                ((_ k body ...)
                 (*my-control (lambda (k) body ...)))))

Olivier Danvy's puzzleの理解

実装すれば理解できたと言えるのか。もちろんそんなことはない。

限定継続のパズルとして、Olivier Danvy's puzzleというコードがあるのだそうですが、このcontrol/prompt版がまるで分からない。

Racketで書き下すと次のとおりです。

#lang racket
(require racket/control)

(reset
  (shift k1 (cons 1 (k1 #f)))
  (shift k2 (cons 2 (k2 #f)))
  '())
; => '(1 2)

(prompt
  (control k1 (cons 1 (k1 #f)))
  (control k2 (cons 2 (k2 #f)))
  '())
; => '(2 1)

shift/resetの結果は直感的ですが、control/promptの結果は実行順序がテレコになっているように見えます。

なんでこんなことになるのか。段階的な項変換で理解してみます。まずはcontrol/promptから。

#lang racket
(require racket/control)

; (1) 初期状態
(prompt
  (control k1 (cons 1 (k1 #f)))
  (control k2 (cons 2 (k2 #f)))
  '())

; (2) 最初のcontrolに突入
(prompt
  (let ((k1 (lambda (ignored)
              ignored ; 元々最初のcontrolがあったところ
             (control k2 (cons 2 (k2 #f)))
             '())))
    (cons 1 (k1 #f))))

; (3) k1を簡約
(prompt
  (cons 1 (begin
            #f
            (control k2 (cons 2 (k2 #f)))
            '())))

; (4) beginの次の#fは不要なので消しとく
(prompt
  (cons 1 (begin
            (control k2 (cons 2 (k2 #f)))
            '())))

; (5) 二番目のcontrolに突入
(prompt
  (let ((k2 (lambda (ignored)
              (cons 1 (begin
                        ignored ; 元々二番目のcontrolがあったところ
                        '())))))
    (cons 2 (k2 #f))))

; (6) k2を簡約
(prompt
  (cons 2 (cons 1 (begin
                    #f
                    '()))))

; (7) beginの結果は単に'()である
(prompt (cons 2 (cons 1 '())))

; (8) promptの中身がリストのリテラルにできる
(prompt '(2 1))

; (9) controlのないpromptは単にbodyの結果を返す
'(2 1)

続いてshift/reset。

#lang racket
(require racket/control)

; (1) 初期状態
(reset
  (shift k1 (cons 1 (k1 #f)))
  (shift k2 (cons 2 (k2 #f)))
  '())

; (2) 最初のshiftに突入
(reset
  (let ((k1 (lambda (ignored)
              (reset
                ignored
                (shift k2 (cons 2 (k2 #f)))
                '()))))
    (cons 1 (k1 #f))))

; (3) k1を簡約
(reset
  (cons 1 (reset
            #f
            (shift k2 (cons 2 (k2 #f)))
            '())))

; (4) resetの次の#fは不要なので消しとく
(reset
  (cons 1 (reset
            (shift k2 (cons 2 (k2 #f)))
            '())))

; (5) 二番目のshiftに突入
(reset
  (cons 1 (reset
            (let ((k2 (lambda (ignored)
                        (reset
                          ignored
                          '()))))
              (cons 2 (k2 #f))))))

; (6) k2を簡約
(reset (cons 1 (reset (cons 2 (reset #f '())))))

; (7) shiftが無いので順々にresetを外していく
(reset (cons 1 (reset (cons 2 (reset '())))))
(reset (cons 1 (reset (cons 2 '()))))
(reset (cons 1 (reset '(2))))
(reset (cons 1 '(2)))
(reset '(1 2))
'(1 2)

これで違いが見て取れるようになりました。control/promptでは、k1, k2の呼び出しがpromptを作らないので、その中でcontrolが呼ばれると、k1, k2の外側のprompt内の処理が限定継続に束縛されてabortされるので、処理がテレコになって見えるわけです。一方shift/resetでは、k1, k2の呼び出し自体がresetを作るので、その中でshiftが呼ばれても、k1, k2の外側の処理がabortされることはありません。

どちらが良いかは難しいところです。shift/resetの方が分かりやすいのですが、余計にスタックフレームを積むので、末尾呼び出しの最適化が掛からなくて困ることがあるのかもしれません。ここらへんは使いこなしてみないと分からなそうです。

2015-04-19

[][] 渋谷JVM - JVM言語編でLTしました

渋谷JVMという集会の案内を見て、しばらく流していたのですが、実はJVM言語の集まりということが分かったので、Kinkの宣伝のためLT枠に滑り込みました。CCCの懇親会LTを使い回して、午前中には資料を完成させました。用意周到です。

本編はScala, Clojure, Groovy, Javaのセッションとパネルディスカッションでした。

途中、Clojureのcore.asyncという非同期処理ライブラリについて、2点質問しました。

この質問について、 id:ihcomega さんから、わけが分からないから解説しろ!という、もっともな突っ込みをいただきました。

ということで急遽LT資料を作って、コルーチンの実装方法を説明しました。

まとめると次のとおりです。

  1. コルーチンの実装にはスタックレスとスタックフルの二種類があって、Clojureのcore.asyncではスタックレスな実装を選択しているらしい。このため、コルーチンから処理を呼び出した先でコンテキストスイッチすることはできない。
  2. 通常のIOはブロックする。ブロックするとコンテキストスイッチできないため、コルーチンとの相性が悪い。このためコルーチンには、組み合わせて使える非同期IOが用意されることが多い。core.asyncでは専用のIO実装は用意されていないらしい。

また、無理を言って元のLTも喋らせていただきました。

2013-07-27

[] 多値と多重代入と Kink

多値と JVM の続き。

Kink という言語を作ってるんですけど、ここでは Ruby や Python と同様に、多値はサポートせず、多重代入を可能にしています。ただし、多重代入は特別な構文ではなく、単なる関数呼び出しです。

式の値の数という観点では、 Ruby や Python と同様に、 1 個に固定です。 C 系言語で void 型になるような式は、 Ruby では nil, Python では None という「値」になりますが、 Kink では base という「値」になります。値が無い = void 型ではなく、「なんもないよ」を表す値が 1 個あるわけです。で、多値はありません。多重代入ができれば、プログラムを書く上では充分だ、という判断に基づきます。

Ruby や Python では、多重代入は特別な構文ですが、 Kink の多重代入は単なる関数呼び出しです。というか、代入自体が単なる関数呼び出しです。

たとえば、単一代入は次のように書きます。

@NUM = 42

これは、変数参照に対する関数呼び出しであって、以下と同等です。

@NUM.op_set(42)

多重代入は次のように書きます。

[@ID @VALUE] = stdin.line / ','

これは、変数参照を要素として持つリストに対する関数呼び出しであって、以下と同等です。

[@ID @VALUE].op_set(stdin.line / ',')

同様に op_set を定義すれば、変数参照やリストに限らず、代入の左辺に置けるわけです。ただ、こういった柔軟性と引き換えに、プログラムの静的解析が困難を極め、最適化の手段が限られてしまうという難点があります。

2013-01-06

[][]Java のリフレクションで super.method(...) 相当の呼び出しはできない

下の例のように super.メソッド名(...) とすると親クラスのメソッドが呼べますが、リフレクション経由では同じようにできないことが分かりました。

class Parent {
    public void bang() {
        System.out.println("Parent.bang!");
    }
}

class Child extends Parent {
    @Override public void bang() {
        System.out.println("Child.bang!");
    }
    public void parentBang() {
        super.bang();
    }
}

public class Main {
    public static void main(String[] args) throws Exception {
        new Child().bang();  // => Child.bang!
        new Child().parentBang();  // => Parent.bang!
        Parent.class.getMethod("bang").invoke(new Child());  // => Child.bang!
        // ※ Parent.bang! であって欲しかったけどうまく行かなかった
    }
}

実際 Method#invoke の項には「Java 言語仕様にある通りに動的ルックアップするよ」 (invokevirtual / invokeinterface 相当) とあります。 super 呼び出しは invokespecial なので駄目です。

やりたかったことは次の通りです。 Kink というオレオレ言語を作っていて、 Java のクラスを動的プロキシっぽく拡張したクラスのインスタンスが作れます。で、今度 super 呼び出しができるようにしたのですが、 Java のリフレクションそのままではうまく行きませんでした。

結局どうしたかと言うと、実行時に生成する動的プロキシのクラスに、上例の Child#parentBang と同じように super 呼び出しするだけのブリッジメソッドを追加して、こいつを呼び出すようにしました。

useclass('java.util.ArrayList')
&LIST = ArrayList.newwith(
    'add' { > &L (&E)
        stderr.printline(E + ' is added!')
        L.super('add' E)
    }
)
LIST.add('voxxx') # => 'voxxx' is added!
LIST.add('twift') # => 'twift' is added!
printline(LIST) # => [voxxx, twift]

Java 7 で導入された MethodHandles.Lookup#findSpecial を使うことでも、 super 呼び出し相当のことができそうですが、 Kink 内部の仕組みと相性が悪いので、今回は使っていません。

2011-04-16

[] tak(13, 7, 0) 実行時間比較

shを除く各処理系で、tak(13, 7, 0) を走らせた。

処理系 実行時間
Groovy 1.6.4 (Server VM) 0m15s
Lua 5.1.4 0m20s
JRuby 1.4.0 (Server VM) 0m26s
Python 2.6.5 0m43s
SCM 5e5 (Scheme) 0m49s
Kink 8f30e3bcc17f (Server VM) 1m58s
CRuby 1.8.7 3m10s

Kink が CRuby より速い!ちょっと驚いた。

[][][][][][][]いろんな言葉で竹内関数

Kink

#!/usr/bin/env kink

&tak = { ( &X  &Y  &Z )
    ( X <= Y ).then {
        Y
    } {
        tak( tak( X - 1  Y  Z )  tak( Y - 1  Z  X )  tak( Z - 1  X  Y ) )
    }
}

[ &X  &Y  &Z ] = ARGS.map { __.int }
&TAK = tak( X  Y  Z )
print_line: format: 'tak( #X  #Y  #Z ) = #TAK'

Scheme

#!/usr/bin/scm -f

(require 'srfi-1)

(define (tak x y z)
  (if (<= x y)
    y
    (tak (tak (- x 1) y z) (tak (- y 1) z x) (tak (- z 1) x y))))

(write (apply tak (map string->number (drop *argv* *optind*))))
(newline)

Ruby

#!/usr/bin/env ruby

def tak( x , y , z )
  if x <= y
    y
  else
    tak( tak( x - 1 , y , z ) , tak( y - 1 , z , x ) , tak( z - 1 , x , y ) )
  end
end

x , y , z = ARGV.map { |arg| arg.to_i }
tak = tak( x , y , z )
puts "tak(#{x}, #{y}, #{z}) = #{tak}"

Python

#!/usr/bin/env python

import sys

def tak(x, y, z):
    if x <= y:
        return y
    else:
        return tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y))

x = int(sys.argv[1])
y = int(sys.argv[2])
z = int(sys.argv[3])
result = tak(x, y, z)
print "tak(%s, %s, %s) = %s" % (x, y, z, result)

Groovy

#!/usr/bin/env groovy

def tak(x, y, z) {
    if (x <= y) {
        return y
    } else {
        return tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y))
    }
}

x = Integer.decode(args[0])
y = Integer.decode(args[1])
z = Integer.decode(args[2])
result = tak(x, y, z)
println "tak($x, $y, $z) = $result"

Bourne Shell

#!/bin/sh

x=$1
y=$2
z=$3

if [ $x -le $y ]; then
  echo $y
else
  x1=`expr $x - 1`
  y1=`expr $y - 1`
  z1=`expr $z - 1`
  xx=`$0 $x1 $y $z`
  yy=`$0 $y1 $z $x`
  zz=`$0 $z1 $x $y`
  $0 $xx $yy $zz
fi

Lua

function tak(x, y, z)
  if x <= y then
    return y
  else
    return tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y))
  end
end

x = tonumber(arg[1])
y = tonumber(arg[2])
z = tonumber(arg[3])
result = tak(x, y, z)
print(result)

2010-11-20

[] 引数渡しの最適化について

メソッド呼び出し時の引数渡しの最適化について。次のようなメソッドがあったとします。

&half = { ( &N )
    N / 2
}

ここで、half関数への引数渡しは、仮引数リストに対するassignメソッドの呼び出しと同価です。

&half = {
    [ &N ].assign( _args )
    N / 2
}

assignメソッドを呼び出すためには、スロット「&N」、仮引数リスト「[ &N ]」、実引数リスト「_args」と、三つのオブジェクトを生成する必要があります。インスタンス生成を減らすため、上記のようなassignメソッドの呼び出しに対して、コンパイラは、オブジェクト群を生成せずに直接変数を定義するような評価器を生成します。 *1

*1:リストのassignメソッドが再定義された際には、処理をショートカットせず、普通にメソッドを呼び出しに行きます