継続渡しスタイルとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > ウィキペディア小見出し辞書 > 継続渡しスタイルの意味・解説 

継続渡しスタイル

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/06/22 04:18 UTC 版)

ナビゲーションに移動 検索に移動

継続渡しスタイル (CPS: Continuation-passing style) とは、プログラムの制御継続を用いて陽に表すプログラミングスタイルのことである。この用語は、ジェラルド・ジェイ・サスマンガイ・スティール・ジュニアにより、Scheme言語に関する初期の論文において導入された[1][2]

継続渡しスタイルで書かれた関数は、通常の直接スタイル (direct style) のように値を「返す」かわりに、「継続」を引数として陽に受け取り、その継続に計算結果を渡す。継続とは、関数の計算結果を受け取るための(一般には元の関数とは別の)1引数の関数のことである。継続渡しスタイルの関数を呼び出すときは、呼び出し側の関数が、呼び出される関数の「戻り値」を受け取るための継続を与える必要がある。この形でコードを書くと、直接スタイルにおいて暗黙に仮定されていた様々な動作が、陽に表される。例えば、手続きからの復帰が継続の呼び出しとして表される、計算の途中の値がすべて陽に名前を与えられる、引数の評価順序が陽に表される、末尾呼び出しは呼び出される手続きに呼び出し側と同じ継続を渡すことにあたる、等である。

直接スタイルのプログラムはCPSに自動変換することが可能である。関数型言語や論理型言語のコンパイラはCPSを中間表現として用いることがある。命令型言語ないし手続き型言語のコンパイラはしばしば静的単一代入(SSA)形式を用いるが、SSAとCPSはある意味で等価であることが知られている[3]。また、やはり関数型言語のコンパイラの中間表現として用いられることがあるA正規形(A-normal form)も、CPSとの対応関係が(当初から)知られている[4]

以下に直接スタイルと、それに対応するCPSで書かれたコードの例を示す。これらの例はSchemeで書かれている。継続を受け取る引数は慣習的にkで表される。

直接スタイル 継続渡しスタイル
(define (pyth x y)
  (sqrt (+ (* x x) (* y y))))
(define (pyth& x y k)
  (*& x x (lambda (x2)
    (*& y y (lambda (y2)
      (+& x2 y2 (lambda (x2py2)
        (sqrt& x2py2 k))))))))
(define (factorial n)
  (if (= n 0)
    1     ; 末尾再帰でない
    (* n (factorial (- n 1)))))
(define (factorial& n k)
  (=& n 0 (lambda (b)
    (if b   ; 再帰呼び出しにおいて
      (k 1) ; 継続が成長する
      (-& n 1 (lambda (nm1)
        (factorial& nm1 (lambda (f)
          (*& n f k)))))))))
(define (factorial n)
 (f-aux n 1))
(define (f-aux n a)
  (if (= n 0)
    a
    (f-aux (- n 1) (* n a)))) ; 末尾再帰
(define (factorial& n k) (f-aux& n 1 k))
(define (f-aux& n a k)
  (=& n 0 (lambda (b)
    (if b                    ; 再帰呼び出しにおいて
      (k a)                ; 継続が変わらない
      (-& n 1 (lambda (nm1) 
        (*& n a (lambda (nta)
          (f-aux& nm1 nta k)))))))))

CPS版では+&*&といったプリミティブも直接スタイルではなくCPSを仮定している。したがって、上の例を一般的なScheme処理系で動かすためには、それらのCPS版プリミティブも与える必要がある。例えば*&は以下のように定義できる。

(define (*& x y k)
 (k (* x y)))

これを一般に行うには、次のように変換ルーチンを書けばよい。

(define (cps-prim f)
  (lambda args
    (let ((r (reverse args)))
      ((car r) (apply f (reverse (cdr r)))))))
(define *& (cps-prim *))
(define +& (cps-prim +))

CPSで書かれた手続きを直接スタイルで書かれた手続きから呼び出すためには、CPSの手続きにより計算された結果を受け取るための継続を与える必要がある。上の例では(CPS版プリミティブが与えられたとして)(factorial& 10 (lambda (x) (display x) (newline)))のようになる。

他分野での応用例

計算機科学以外では、例えば自然言語意味論において、CPSを用いて文の表示を定義することにより、ある種の言語現象を説明できるとされている[1].

数理論理学カリー=ハワード同型対応において、CPS変換は、二重否定による古典論理直観主義論理への埋め込みにあたる。また、古典論理そのものは、Schemeの call-with-current-continuation 制御演算子のように、継続を直に扱うことができるプログラミング言語に対応する[5]

参考文献

  1. ^ Gerald Jay Sussman and Guy L. Steele, Jr. (December 1975). “Scheme: An interpreter for extended lambda calculus”. AI Memo 349: 19. "That is, in this continuation-passing programming style, a function always "returns" its result by "sending" it to another function. This is the key idea." 
  2. ^ Gerald Jay Sussman and Guy L. Steele, Jr. (December 1998). “Scheme: A Interpreter for Extended Lambda Calculus” (reprint). Higher-Order and Symbolic Computation 11 (4): 405--439. doi:10.1023/A:1010035624696. http://www.brics.dk/~hosc/local/HOSC-11-4-pp405-439.pdf. "We believe that this was the first occurrence of the term "continuation-passing style" in the literature. It has turned out to be an important concept in source code analysis and transformation for compilers and other metaprogramming tools. It has also inspired a set of other "styles" of program expression." 
  3. ^ * Richard A. Kelsey (March 1995). “A Correspondence between Continuation Passing Style and Static Single Assignment Form”. ACM SIGPLAN Notices 30 (3): 13--22. doi:10.1145/202530.202532. 
  4. ^ Flanagan, Cormac; Sabry, Amr; Duba, Bruce F.;Felleisen, Matthias. “The Essence of Compiling with Continuations”. Proceedings ACM SIGPLAN 1993 Conf. on Programming Language Design and Implementation, PLDI'93. Albuquerque, NM, USA. Flanagan93. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.8807 2007年6月5日閲覧。 
  5. ^ Timothy Griffin. (January 1990). “A formulae-as-type notion of control”. Proceedings of the Conference on the Principles of Programming Languages 17: 47–58. 

継続渡しスタイル

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/06/01 02:22 UTC 版)

継続」の記事における「継続渡しスタイル」の解説

詳細は「継続渡しスタイル」を参照 現在主流である、LIFO関数呼び出しではなく全ての関数呼び出しに、その関数終わった実行されるべき継続を、明示的に渡す、というプログラムスタイルがあり、プログラマが書くコードとしてだけではなくプログラミング言語処理系中間表現としても使われており研究されている。

※この「継続渡しスタイル」の解説は、「継続」の解説の一部です。
「継続渡しスタイル」を含む「継続」の記事については、「継続」の概要を参照ください。

ウィキペディア小見出し辞書の「継続渡しスタイル」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「継続渡しスタイル」の関連用語

継続渡しスタイルのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



継続渡しスタイルのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの継続渡しスタイル (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの継続 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS