第6章

UtilCont — 接続（ continuation ）の導入

この章では、goto や break, continue などのジャンプ命令に意味を与えるためにともいう）の概念を導入する。接続は直観的には
次のような C のプログラムでは :（ continuation・を表す。例えば 、

int main(int argc, char** argv) {printf("The result is %d.", 1+fact(10));}下線の部分の接続は、プログラムの残りの部分 — 1 を足してその結果を出力する、という操作である。
どのようなプログラム処理形でも、プログラムの実行中は何らかの形でこの接続の情報を保持しているはずである。機械語レベルでは、接続は（ program counter ）との組に相当する。ジャンプ命令を解釈するためには、この接続の概念を明示的に扱う必要がある。
また、やなど 一部の言語は、接続をプログラマが明示的に扱うことを可能にしている。これによってコルーチン（ coroutine ）など 、さまざまな自明でない制御構造を実現することができる。
この章では接続の概念を導入し 、そのさまざ まな応用を紹介する。

6.1

接続のモナドUtil に break, continue などを導入するために 、Expr の定義に次のように構成子を追加する。また、goto 文を導入するため、ラベルも導入する。

data Expr = Const Value | Let Decl Expr | Var String| Lambda String Expr | App Expr Expr | If Expr Expr Expr
| Letrec Decl Expr
| GetX | SetX Expr | GetY | SetY Expr | GetZ | SetZ Expr
| While Expr Expr ||||||

type LabeledExpr = (Maybe String, Expr);
これに対する具象構文としては、Expr → . . . | begin LabeledExprSeq|break | continue | abort|

goto Var | callcc Expr

LabeledExprSeq → LabeledExpr end | LabeledExpr ; LabeledExprSeq
LabeledExpr → Expr | Var : Expr
VI - 1;

を想定する。
次に abort, break, continue などを解釈するために接続の概念をインタプ リタに導入する。接続（ continuation ）のモナドは単独では次のような型になる。

type K r a =unitK :: a -> K r a;
unitK a =;;bindK :: K r a -> (a -> K r b) -> K r b;m ‘bindK‘ k =;abortK :: r -> K r a;abortK v =;直観的には a -> r が接続（ “以後実行すべき操作” ）の型になる。unitK a は、。m ‘bindK‘ k は、（ \ a -> k a c ）を mに渡す。m は最後にこの接続を呼び出すのが普通だが 、無視したり、他の接続を呼び出したりすることも可能である。これが 、ジャンプなどの命令に対応する。例えば 、abortK v は現在の接続を無視して v という値を全体の計算の結果としている。これは計算を途中で中止することに相当する。
実際に UtilCont で使用する計算の型 M では、接続とともに、状態を扱わなければいけないので、この r は状態の変化を表す State -> State とする。この State は状態の型である。いまのバージョン
では State は Value の三つ組であると定義しておく。
（ UtilST の時と同様、3 という数に特別の意味はない。）

type State = (Value, Value, Value);
type Result = State -> State;;type M a ={- = (a -> State -> State) -> State -> State -}unitM :: a -> M a;unitM a = unitK a;bindM :: M a -> (a -> M b) -> M b;m ‘bindM‘ k = m ‘bindK‘ k;
setX など 状態に関する関数も、この M の定義にあわせて書き直しておく。
failM :: String -> M a;
failM message = abortK (\ s -> (Str ("failure: "++message), Unit, Unit));setX :: Value -> M Value;
setX v =-- setY, setZ も同様に定義する。

;

getX :: M Value;
getX=-- getY, getZ も同様に定義する。

;

lookupM :: String -> Env -> M Value;VI - 2

lookupM x ((n,v):rest) = if n==x then unitM v else lookupM x rest;
lookupM x [] =("Variable: "++x++" is not found");failM はその時の環境・状態・接続はすべて無視して、 “failure: . . . ” というメッセージをプログラムの結果とする。
（ 便宜上、状態の第 1 要素にセットする。）setX v は状態の第 1 要素に v をセットし 、Unit と新しい状態を接続に渡す。
interp を書き換える前に、接続を値として扱えるように Value 型を拡張しておく。これは breakや continue や goto を実現するために、環境の中に接続を格納しておけると便利だからである。
data Value = . . .

|;Const, Var, Letrec などに対しては interp は変更する必要はない。
Break, Continue は環境の中の break, continue という識別子に束縛されている接続を lookup し 、現在の接続は無視して、その接続を起動する。これが “ジャンプ ” に相当する。Abort は、接続を無視して現在の状態をそのまま計算の最終結果として返す。
interp Breake = \ c0 -> lookupM "break" e;interp Continue e = \ c0 -> lookupM "continue" e;interp Aborte =;While に対しては、適切な接続を環境に格納する必要があるため、定義がやや複雑になる。
interp (While m1 m2) e =\ c1 ->let { e1 = (("break", Cont c1) : e) } ininterp m1 e (\ v ->case v of {Bool b -> if b thenlet { c2 = \ _ -> interp (While m1 m2) e c1 } in
let { e2 = (("continue", Cont c2) : e1) } ininterp m2 e2 c2else c1 (Bool True);_-> fairM "Boolean expected" c1});を表す接続で、c2 はを表す接続である。これらのここで、c1 は接続をそれぞれ 、break, continue という識別子に束縛した環境（ env ）のもとで m2 を評価する。
これまでと同じように run という関数をrun :: String -> String;
run str = showValue (fst3 (interp (myParse str) initEnv(\ v (_, y, z) -> (v, y, z)) (Unit, Unit, Unit)));fst3 (a, b, c) = a;と定義すると、例えば 、run ("let foo = \ n -> begin" setX 1; setY n;" while getY > 0 do begin"if getY==10 then break"++"++"++"++
VI - 3-- C の記法では-- int foo(int n) {-int r=1;-while (n>0) {"else if getY==3 then begin"
setY (getY-1); continue"end else 1;"
setX (getX*getY);"
setY (getY-1)" end;" getX"end in"foo 9"++"++"++"++"++"++"++"++")-if (n==10) break;-else if (n==3) {-n--; continue;-}-r=r*n; n--;-}-return r;-- }の結果は、に、最後の行の foo 9 を foo 11 に変えると結果はになる。
自由な飛躍命令である goto に対する意味を与えるために、まず、“ラベル ” を解釈する必要がある
が 、これに対する interp を定義をここに示すと長くなってしまうので、アイデアのみを示す。
例えば 、

begin
l1:
l2:
end

Exprs1 /*Exprs2 /*--- この中に goto l1; goto l2; を含むかもしれない */--- この中に goto l1; goto l2; を含むかもしれない */のような文の意味は、c1 , c2 を l1, l2 の接続とすると、

c1 = λ _ → interp Exprs1 e0 c2
c2 = λ _ → interp Exprs2 e0 ce0 = e + {l1 7→ Cont c1 , l2 7→ Cont c2 }のような式で意味を与えられる。そして、

interp (l1:Exprs1 l2:Exprs2 ) e c = c1 Unitと解釈する。この c, e はこの部分全体を解釈する時の接続と環境である。
goto はラベル名に対応する接続を環境から読み出して、現在の接続は無視して、単にその接続を起動する。

interp (Goto label) e = \ c0 -> lookupM label e
例えば 、run ("begin"++"set 1;"++" l1:"++"
if get > 100 then goto l2 else Unit; "++"set (get * 2);"++"
goto l1;"++" l2:"++"get"++"end")を評価すると、結果はになる。

VI - 4-- /* C の記法では */-- {-x = 1;-- l1:-if (x>100) goto l2;-x = x * 2;-goto l1;-- l2:-return x-- };6.2 Scheme 超入門
Scheme は、Lisp の一方言である。Scheme は関数型言語であるが 、Haskell と異なり、変数への代入など 命令的な特徴を残している。このため関数型言語と言える。また遅延評価ではなく、関数の引数を先に評価する、先行評価を採用している。
関数適用

関数適用 (function application) は次のような形である。

• (関数 引数 1 引数 2 . . . 引数 n ) のようなでくくった式の列

Scheme では + や × などの算術演算子に、通常の(infix notation) ではなく、(prefix notation) を用いることが特徴的である。例えば 、(+ 1 2) という式では、+が関数（ function ）,1 と 2 が引数である。
変数と代入

例えば 、(define x 5)という式で、5 という値の入った “x” という名前の変数を用意する。これ以降は x という変数は 5 に評価される。
Scheme の場合、変数名の中には、アルファベット、数字の他に+ - . * / < = > ! ? : $ % _ & ˜ ˆなどの記号を用いることができる。
（もちろん空白はダ メ）アルファベットの大文字と小文字は。
（つまり、Japan と japan は変数である。）
set!という命令によって、変数の値を変更する（ 代入するという）ことができる。
（ C 言語の 「 = 」演算子に対応する。）(set! x 4)

; 変数 x の値を 4 に変更する。
; それ以前に x を define しておく必要がある。

これは、Scheme がとしての側面を持つことを示す。

リスト リストを入力するためには、組み込み関数 list を用いる。list は任意の数の引数を取ることができる。

> (list 1997 5 6)(1997 5 6)
> (list "kagawa" "university")("kagawa" "university")
単に (1997 5 6) と入力すると、Scheme の処理系は、1997 という関数を 5 と 6 という引数に適用しているのだと判断する。
このように、Scheme（ 一般に Lisp ）では括弧「 ( 」、「 ) 」が 2 つの意味に使われる。ユーザが入力するときは「」の意味に、処理系が出力するときは「」の意味になる。もっと正確に言うとユーザが「 リスト 」を入力すると、処理系はそれを「関数適用」だと解釈するのである。
このような処理系の振舞いは Lisp の強力さの源であるが 、一方で混乱のもとでもある。
上記のデータは「 ’ 」（ クォート記号・引用記号）を用いて次のようにも入力できる。

VI - 5

> ’(1997 4 22)(1997 4 22)「 ’ 式」は、「 (quote 式) 」とも書く。
（ むしろ、後者が正式な書き方である。）> (quote (1997 5 6))(1997 5 6)quote は、だから、(1997 5 6) は関数適用ではな
くリストと解釈される。
空リスト（ 要素を 1 つも含まないリスト ）は ’() または (list) のように入力する。
> ’()()> (list)()cons（と読む）, car（と読む）, cdr（と読む）などが、リストを操作するための最も基本的な関数である。 cons はリストを組み立てるための関数、car と cdr はリストを分解するための関数である。
cons — リストの先頭に 1 つ新たに要素を付け加えたリストを返す関数
car — リストの先頭の要素を返す関数
cdr — リストの先頭を除いた残り（のリスト ）を返す関数
関数定義

関数の定義には次の形式の define を用いる。

(define (関数名 変数 1 . . .

変数 n ) 定義)

変数 1 . . . 変数 n はこの関数の仮引数である。

> (define (square x) (* x x))
square> (square 4)16
条件判断

条件判断は次のような形式で行なう。

(if 条件式 式 1 式 2 )を、を評価（ 計算）する。
（ C の if 文と異なり、値を返すことに条件式が注意する。むしろ、 C の?:オペレータに対応する。）
逐次実行(begin 式 1 式 2 . . .

式 n)VI - 6

式 1 から、式 n を順に評価し、最後の式 n の値を全体の値として返す。通常、C や JavaScript のブロック { 〜 }と意味は似ているが、C や JavaScriptのブロックは “文” の一種であるので値を持たないのに対し 、Scheme の begin 式は値を持つ。
なお、関数の定義の本体で、(define (hen_na_square x)(begin (set! x (* x x))x))のように順に式を評価するときは、上のように begin を使う必要はなく、(define (hen_na_square x)(set! x (* x x))x)のように単に式を並べて書くだけで良い。
（これを “暗黙” の begin という。）
局所変数（ let ） 関数の定義の他に let という構文で局所変数を導入することができる。

(let ((変数 1 式 1 )...
(変数 m 式 m ))式 0)
let 文では、式 1 から式 m を評価した結果が、変数 1 から変数 m に入れられ、最後に式 0 を評価する。
変数 1 , . . . , 変数 m のスコープは式 0 である。
ラムダ式（ 匿名関数）(lambda (変数 1 . . .

変数 n ) 定義)

これは 変数 1 . . . 変数 n を引数とする関数である。例えば 、(lambda (x) (* x x)) は 2 乗する関数である。((lambda (x) (* x x)) 2) は 4 になる。lambda はギリシャ文字の λ のことである。これらは define を用いて定義した名前付きの関数:(define (sq x) (* x x))の sq と同じ 関数になる。つまり、(define (sq x) (* x x)) は (define sq (lambda (x) (* xx))) と同じ意味なのである。

6.3 Scheme の call-with-current-continuation
Scheme では 、プログラマが接続を直接操作することができる。このことを Scheme はという言い方をする時もある。

(call-with-current-continuation thunk )(call/cc thunk )call-with-current-continuation という名前は長いので、省略形の call/cc がよく使われる1 。
Scheme は、-や/のような文字も変数の名前の中でに使用できるので、call-with-current-continuation や call/ccでひとつの名前である。ただし 、call/cc は Scheme の標準仕様には含まれていないので、処理形によっては、
1

VI - 7thunk は 1 引数の関数であり、(call/cc thunk ) はを引数として、thunk を呼び出す。thunk のなかで 、この接続を呼び出せば 、そのときの接続は無視されて（ = ジャンプして ）、call/cc が呼ばれた時の接続にその値が返される。thunk が接続を呼び出さなければ 、thunk 自身の戻り値が call/cc 式全体の戻り値になる。
例えば 、(define (foo x); let foo = \ x ->(call/cc (lambda (k);callcc (\ k ->(+ 100 (if (= x 0) 1 (k x)))))) ;100 + (if x==0 then 1 else k x))という関数を考える。
（ 右側には Util 風の書き方を示す。）(foo 0) を評価すると普通に足し算が計算になる。一方、(foo 1) の場合は、接続 k が 呼び出されるので 100 を足す部分はスされ 、値はキップされて、戻り値は となる。
call/cc のよくある使い方は、try〜catch と同じような大域脱出である。
（右側には Util 風の書き方を示す。）(define (multlist xs); let multlist = \ xs ->(call/cc (lambda (k);callcc (\ k ->(define (aux xs);
letrec aux = \ xs ->(if (null? xs)
1;
if null xs then 1(if (= 0 (car xs));
else if car xs == 0(k 0);then k 0(* (car xs) (aux (cdr xs))))));
else car xs * aux (cdr xs)(aux xs))));in aux xs)
この関数はリストの要素の掛け算を求める。要素の中に 0 が見つかると、大域脱出して multlist 全体の値は になる。
しかし 、このような大域脱出だけならば 、言語の仕様に call/cc のような大がかりな仕掛けをいれておく必要はない。call/cc の本当の価値はコルーチンなどの普通でない制御構造を実現できるところにある。

6.4 コルーチン（ coroutine ）コルーチンとは、2 つ以上のプログラムの実行単位が 、のことである。サブルーチン（ subroutine ）のように、実行単位の間に主と副といった従属関係はなく、コルーチンを構成する個々のルーチンは互いに対等な関係である。
例えば 、(define (increase n k)
; letrec increase = \ n -> \ k ->(if (> n 10) ’();
if n > 10 then Unit(begin (display " i:") (display n) ;else begin display " i:"; display n;(increase (+ n 1) (call/cc k))))) ;increase (n+1) (callcc k) end;
(define (decrease n k);
decrease = \ n -> \ k ->(if (< n 0) ’();
if n < 0 then Unit(begin (display " d:") (display n) ;else begin display " d:"; display n;(decrease (- n 1) (call/cc k)))));
decrease (n-1) (callcc k) end(define call/cc call-with-current-continuation)のように自分で定義しておく必要がある。

VI - 8という 2 つの関数を定義して(increase 0 (lambda (k) (decrease 10 k))); in increase 0 (\ k -> decrease 10 k)という式を実行すると、というように画面へ出力される。increase と decrease という 2 つの関数が交互に実行されていることがわかる。
call/cc はひじょうに強力なプ リミティブで 、コルーチンの他にこれまでに紹介したエラー処理（ try〜catch ）や非決定性などのプ リミティブも、call/cc を用いて定義できることがわかっている。
ある意味でオールマイティのプリミティブである。
しかし 、call/cc は効率的な実装の難しいプ リミティブでもある。素直な実装では call/cc を実現するためには、スタック全体のコピーを行なう必要がある。一方、はじめからスタックをヒープの中に取り、スタックのコピーを行なわないという方式もある。この方式では不要になったスタック領で回収する。
域も6.5

call/cc の表現

我々の言語 UtilCont に call/cc を導入するには、接続を関数として渡すためのコード を用意すれば良い。Callcc に対する interp の定義は次のようになる。

callccK :: ((a -> K r b) -> K r a) -> K r a;callccK h =;interp (Callcc m) e = interp m e ‘bindM‘ \ g ->case g of {Fun f ->;_-> failM ("Callcc: Function expected")};callccK の定義中で用いられている k は現在の接続（ d ）を捨て、キャプチャされた接続（ c ）を呼び出すという関数である。Callcc に対する interp の定義は、基本的に callccK を呼び出すだけである。
例えば 、run ("let mult = \ xs -> \ k -> begin" ++"setX 1; setY xs; setZ "";" ++"while isCons getY do begin" ++"let n = car getY in" ++"if n == 0 then k 0 else
" ++"begin setX (getX*n); setY (cdr getY); setZ (getZ ++ " " ++ n) end " ++
"
end;
" ++
"
getX
" ++
" end in" ++"let list= cons 1 (cons 2 (cons 3 (cons 0 (cons 4 (cons 5 nil))))) in" ++"let result = callcc (\ k -> mult list k) in" ++"pair result getZ")の結果は (Num 0.0, Str " 1.0 2.0 3.0") となる。

VI - 9

この章の参考文献[1] John C. Reynolds, 「 The Discoveries of Continuations 」
Lisp and Symbolic Computation, 6, (233–247). 1993 年
接続に関する文献は数多くあるが 、この論文は接続の「発見」について、振り返っている珍しいものである。
[2] Andrzej Filinski, 「 Representing Monads 」
21st ACM Symposium on Principles of Programming Languages. 1994 年
call/cc が「オールマイティ」であることについての説明を与えている。
[3] Richard Kelsey, William Clinger, and Jonathan Rees (Editors),「 Revised5 Report on the Algorithmic Language Scheme 」
http://www.schemers.org/Documents/Standards/R5RS/
Scheme の仕様書である。通常、略して R5RS と呼ばれる。call/cc の簡単な解説もある。
[4] T. Sekiguchi, T. Sakamoto, and A. Yonezawa,「 Portable Implementation of Continuation Operators in Imperative Languages by Exception Handling 」
Advances in Exception Handling Techniques. Springer-Verlag, LNCS 2022. 2001 年
http://www.yl.is.s.u-tokyo.ac.jp/amo/Java などの命令型言語に、call/cc のような接続を扱うオペレータを導入する方法を述べている。
[5] Levent Erkök, and John Launchbury, 「 Recursive Monadic Bindings 」
Proc. of the International Conference on Functional Programming. 2000 年
mfixU などの不動点演算子について解説している。

VI - 10