Continuation-passing style (original) (raw)
Στο συναρτησιακό προγραμματισμό, το στυλ περάσματος συνεχειών (continuation-passing style, CPS) είναι ένα στυλ προγραμματισμού στο οποίο η ροή του ελέγχου δίνεται ρητά από το πέρασμα συνεχειών.
| Property | Value |
|---|---|
| dbo:abstract | Στο συναρτησιακό προγραμματισμό, το στυλ περάσματος συνεχειών (continuation-passing style, CPS) είναι ένα στυλ προγραμματισμού στο οποίο η ροή του ελέγχου δίνεται ρητά από το πέρασμα συνεχειών. (el) In functional programming, continuation-passing style (CPS) is a style of programming in which control is passed explicitly in the form of a continuation. This is contrasted with direct style, which is the usual style of programming. Gerald Jay Sussman and Guy L. Steele, Jr. coined the phrase in AI Memo 349 (1975), which sets out the first version of the Scheme programming language.John C. Reynolds gives a detailed account of the numerous discoveries of continuations. A function written in continuation-passing style takes an extra argument: an explicit "continuation"; i.e., a function of one argument. When the CPS function has computed its result value, it "returns" it by calling the continuation function with this value as the argument. That means that when invoking a CPS function, the calling function is required to supply a procedure to be invoked with the subroutine's "return" value. Expressing code in this form makes a number of things explicit which are implicit in direct style. These include: procedure returns, which become apparent as calls to a continuation; intermediate values, which are all given names; order of argument evaluation, which is made explicit; and tail calls, which simply call a procedure with the same continuation, unmodified, that was passed to the caller. Programs can be automatically transformed from direct style to CPS. Functional and logic compilers often use CPS as an intermediate representation where a compiler for an imperative or procedural programming language would use static single assignment form (SSA). SSA is formally equivalent to a subset of CPS (excluding non-local control flow, which does not occur when CPS is used as intermediate representation). Functional compilers can also use A-normal form (ANF) (but only for languages requiring eager evaluation), rather than with 'thunks' (described in the examples below) in CPS. CPS is used more frequently by compilers than by programmers as a local or global style. (en) En la programación funcional, el Continuation-passing style (CPS) es un estilo de programación en el cual el Flujo de control se pasa explícitamente en forma de una Continuación, en oposición al estilo directo, que es el estilo habitual de programar. La notación CPS (abreviatura de continuation-passing style) es una forma de escribir el código de un programa en la que las Continuaciones se escriben y se pasan de forma explícita. Cuando se escribe un programa en notación CPS, cada función recibe un parámetro adicional, que representa la Continuación de la función. En lugar de retornar, la función invocará la continuación recibida pasando el valor de retorno. De esta forma, las funciones nunca regresan al código que las llamó, sino que la ejecución del programa transcurre “hacia adelante” sin retornar hasta que el programa finalice. Cuando desde una función A se desea invocar a una función B, se pasa como continuación de la función B el código que se desea ejecutar a continuación (incluyendo la invocación de la continuación de la función A). La notación CPS ocasiona que el tamaño de la pila crezca con cada llamada a función, con el peligro de desbordamiento que eso conlleva. Por ello, cualquier implementación que pretenda escribir el código en notación CPS para ser ejecutado emplea la optimización conocida como tail-call optimization (TCO) que en español se traduce como optimización de cola. Esta optimización consiste en aprovechar que el marco de pila de la función actual al realizar una llamada a función no va a volver a ser usado (ya que las funciones no retornan) y por tanto puede ser reutilizado como marco de pila para la función invocada, evitando por tanto el crecimiento desmedido de la pila. (es) Unter Continuation-Passing Style (kurz CPS) versteht man einen Programmierstil, bei dem der Kontrollfluss ausschließlich durch Continuations gesteuert wird. Continuations sind Funktionen, die die verbleibenden Berechnungen repräsentieren. An die Stelle der Funktionsrückkehr tritt bei Programmen im Continuation-Passing Style der Aufruf der übergebenen Continuation. In den meisten Programmiersprachen werden nach Beendigung einer Funktion ihr Ergebnis und der Kontrollfluss an den Aufrufer zurückgegeben. Zur Abgrenzung von CPS wird dies als direkter Stil, direct style, bezeichnet. Es ist aber auch möglich, der Funktion eine Nachfolgefunktion zu übergeben, die an Stelle des Aufrufers das Ergebnis erhalten soll. Anstatt zum Aufrufer zurückzukehren, übergibt die Funktion ihr Ergebnis dieser Nachfolgefunktion. Die Funktionen bilden gewissermaßen eine Kette. Statt von einer Nachfolgefunktion kann man auch von einer „Fortführung“ sprechen, dem deutschen Wort für Continuation. Der CPS ist ein Programmierstil, der dieser Vorgehensweise folgt. CPS macht den in vielen Sprachen notwendigen Stack zur Speicherung der Rücksprungadresse beim Aufruf einer Methode überflüssig. Damit ist es möglich, eine Programmiersprache ohne Stack (stackless) zu implementieren. Da auf vielen Systemen die Größe des Stacks begrenzt ist, ist ohne CPS auch die maximale Rekursionstiefe begrenzt, was unter Umständen zum Problem werden kann. Mit CPS ist es möglich, diese Begrenzung zu umgehen. Ein Beispiel hierfür ist Stackless Python. Viele Compiler logischer und funktionaler Programmiersprachen verwenden CPS als interne Repräsentation eines Programmes, da er es erleichtert, Schlüsse über das Programm zu ziehen, und damit Optimierungen vereinfacht. Eine direct-style-Sprache wie JavaScript in CPS zu transformieren, führt (sofern der Compiler keine Tail Call Optimization unterstützt) dazu, dass früher oder später der Stack überläuft, da eine durch Aufruf einer Continuation verlassene Funktion nicht über ihren „offiziellen“ Weg beendet wird und somit der Stackeintrag nicht abgeräumt wird. Wenn Exceptions verfügbar sind, ist es aber möglich, beim Erreichen einer bestimmten Rekursionstiefe die aktuelle Continuation in eine Exception zu packen und diese zu werfen. Das wickelt den Stack ab, und am oberen Ende der Kette von Funktionsaufrufen wartet ein Exceptionhandler, der die verpackte Continuation aufruft. Auf diese Weise implementiert beispielsweise flapjax eine CPS-Transformation von JavaScript-Code. (de) 継続渡しスタイル (CPS: Continuation-passing style) とは、プログラムの制御を継続を用いて陽に表すプログラミングスタイルのことである。この用語は、ジェラルド・ジェイ・サスマン とガイ・スティール・ジュニアにより、Scheme言語に関する初期の論文において導入された。 継続渡しスタイルで書かれた関数は、通常の直接スタイル (direct style) のように値を「返す」かわりに、「継続」を引数として陽に受け取り、その継続に計算結果を渡す。継続とは、関数の計算結果を受け取るための（一般には元の関数とは別の）1引数の関数のことである。継続渡しスタイルの関数を呼び出すときは、呼び出し側の関数が、呼び出される関数の「戻り値」を受け取るための継続を与える必要がある。この形でコードを書くと、直接スタイルにおいて暗黙に仮定されていた様々な動作が、陽に表される。例えば、手続きからの復帰が継続の呼び出しとして表される、計算の途中の値がすべて陽に名前を与えられる、引数の評価順序が陽に表される、末尾呼び出しは呼び出される手続きに呼び出し側と同じ継続を渡すことにあたる、等である。 直接スタイルのプログラムはCPSに自動変換することが可能である。関数型言語や論理型言語のコンパイラはCPSを中間表現として用いることがある。命令型言語ないし手続き型言語のコンパイラはしばしば静的単一代入(SSA)形式を用いるが、SSAとCPSはある意味で等価であることが知られている。また、やはり関数型言語のコンパイラの中間表現として用いられることがあるA正規形(A-normal form)も、CPSとの対応関係が（当初から）知られている。 (ja) |
| dbo:wikiPageExternalLink | http://scheme.com/tspl3/further.html%23./further:h4 http://www.scheme.com/tspl3/ http://www.cs.princeton.edu/~appel/papers/ssafun.ps http://www.pps.univ-paris-diderot.fr/~kerneis/software/ http://www.brics.dk/RS/07/6/ https://books.google.com/books%3Fid=0Uoecu9ju4AC https://github.com/kerneis/cpc |
| dbo:wikiPageID | 749852 (xsd:integer) |
| dbo:wikiPageLength | 22199 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1105224202 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Scheme_(programming_language) dbr:Tail_call dbr:Double-negation_translation dbr:Intermediate_representation dbr:Intuitionistic_logic dbr:ML_programming_language dbr:Thunk_(functional_programming) dbr:Compiler dbr:Mathematics dbr:Gerald_Jay_Sussman dbr:Glasgow_Haskell_Compiler dbr:Continuation dbr:Control_flow dbr:Call-with-current-continuation dbr:Call_stack dbc:Continuations dbr:Chris_Barker_(linguist) dbr:Static_single_assignment_form dbr:Computer_science dbr:Embedding dbr:Functional_programming dbr:Swing_(Java) dbr:Tail_call_optimization dbr:A-normal_form dbc:Functional_programming dbc:Implementation_of_functional_programming_languages dbr:C_(programming_language) dbr:Garbage_collection_(computer_science) dbr:Logic_programming dbr:Guy_L._Steele,_Jr. dbr:Functional_programming_language dbr:Procedural_programming dbr:Pythagorean_theorem dbr:Haskell_(programming_language) dbr:Java_(programming_language) dbr:AI_Memo dbc:Articles_with_example_Java_code dbr:Chicken_(Scheme_implementation) dbr:John_C._Reynolds dbr:Lambda_calculus dbc:Articles_with_example_Scheme_(programming_language)_code dbr:Tail-call_optimization dbr:Tail_recursion dbr:Classical_logic dbr:Identity_function dbr:Yoneda_embedding dbr:Π-calculus dbr:Semantics dbr:Imperative_programming dbr:Natural_language dbr:Programming_language dbr:First-class_function dbr:Trampoline_(computers) dbr:Lambda_(programming) dbr:Continuations dbr:Thunk_(delayed_computation) dbr:Chicken_Scheme_compiler dbr:Curry–Howard_isomorphism |
| dbp:wikiPageUsesTemplate | dbt:Center dbt:Cite_book dbt:Cite_journal dbt:Clarify dbt:Reflist dbt:See_also dbt:Manual |
| dct:subject | dbc:Continuations dbc:Functional_programming dbc:Implementation_of_functional_programming_languages dbc:Articles_with_example_Java_code dbc:Articles_with_example_Scheme_(programming_language)_code |
| gold:hypernym | dbr:Style |
| rdf:type | owl:Thing yago:WikicatContinuations yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Continuance101017987 yago:Event100029378 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity |
| rdfs:comment | Στο συναρτησιακό προγραμματισμό, το στυλ περάσματος συνεχειών (continuation-passing style, CPS) είναι ένα στυλ προγραμματισμού στο οποίο η ροή του ελέγχου δίνεται ρητά από το πέρασμα συνεχειών. (el) Unter Continuation-Passing Style (kurz CPS) versteht man einen Programmierstil, bei dem der Kontrollfluss ausschließlich durch Continuations gesteuert wird. Continuations sind Funktionen, die die verbleibenden Berechnungen repräsentieren. An die Stelle der Funktionsrückkehr tritt bei Programmen im Continuation-Passing Style der Aufruf der übergebenen Continuation. Viele Compiler logischer und funktionaler Programmiersprachen verwenden CPS als interne Repräsentation eines Programmes, da er es erleichtert, Schlüsse über das Programm zu ziehen, und damit Optimierungen vereinfacht. (de) In functional programming, continuation-passing style (CPS) is a style of programming in which control is passed explicitly in the form of a continuation. This is contrasted with direct style, which is the usual style of programming. Gerald Jay Sussman and Guy L. Steele, Jr. coined the phrase in AI Memo 349 (1975), which sets out the first version of the Scheme programming language.John C. Reynolds gives a detailed account of the numerous discoveries of continuations. (en) En la programación funcional, el Continuation-passing style (CPS) es un estilo de programación en el cual el Flujo de control se pasa explícitamente en forma de una Continuación, en oposición al estilo directo, que es el estilo habitual de programar. La notación CPS (abreviatura de continuation-passing style) es una forma de escribir el código de un programa en la que las Continuaciones se escriben y se pasan de forma explícita. (es) 継続渡しスタイル (CPS: Continuation-passing style) とは、プログラムの制御を継続を用いて陽に表すプログラミングスタイルのことである。この用語は、ジェラルド・ジェイ・サスマン とガイ・スティール・ジュニアにより、Scheme言語に関する初期の論文において導入された。 継続渡しスタイルで書かれた関数は、通常の直接スタイル (direct style) のように値を「返す」かわりに、「継続」を引数として陽に受け取り、その継続に計算結果を渡す。継続とは、関数の計算結果を受け取るための（一般には元の関数とは別の）1引数の関数のことである。継続渡しスタイルの関数を呼び出すときは、呼び出し側の関数が、呼び出される関数の「戻り値」を受け取るための継続を与える必要がある。この形でコードを書くと、直接スタイルにおいて暗黙に仮定されていた様々な動作が、陽に表される。例えば、手続きからの復帰が継続の呼び出しとして表される、計算の途中の値がすべて陽に名前を与えられる、引数の評価順序が陽に表される、末尾呼び出しは呼び出される手続きに呼び出し側と同じ継続を渡すことにあたる、等である。 (ja) |
| rdfs:label | Continuation-Passing Style (de) Στιλ περάσματος συνεχειών (el) Continuation-passing style (es) Continuation-passing style (en) 継続渡しスタイル (ja) Программирование в стиле передачи продолжений (ru) |
| rdfs:seeAlso | dbr:Callback_(computer_programming) |
| owl:sameAs | freebase:Continuation-passing style yago-res:Continuation-passing style wikidata:Continuation-passing style dbpedia-de:Continuation-passing style dbpedia-el:Continuation-passing style dbpedia-es:Continuation-passing style dbpedia-ja:Continuation-passing style dbpedia-ru:Continuation-passing style https://global.dbpedia.org/id/4uqRe |
| prov:wasDerivedFrom | wikipedia-en:Continuation-passing_style?oldid=1105224202&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Continuation-passing_style |
| is dbo:wikiPageDisambiguates of | dbr:CPS |
| is dbo:wikiPageRedirects of | dbr:CPS_conversion dbr:Direct_style dbr:Continuation_passing_style dbr:Continuation-passing dbr:Continuation_Passing_Style dbr:Continuation_passing |
| is dbo:wikiPageWikiLink of | dbr:Scheme_(programming_language) dbr:Tail_call dbr:Double-negation_translation dbr:Matthias_Felleisen dbr:Essentials_of_Programming_Languages dbr:Cilk dbr:Glossary_of_computer_science dbr:Monad_(functional_programming) dbr:Continuation dbr:Call-with-current-continuation dbr:Callback_(computer_programming) dbr:Calling_convention dbr:Closure_(computer_programming) dbr:Funarg_problem dbr:A-normal_form dbr:Trampoline_(computing) dbr:Futures_and_promises dbr:Curry–Howard_correspondence dbr:Fold_(higher-order_function) dbr:CPS_conversion dbr:Async/await dbr:Iota_and_Jot dbr:Direct_style dbr:Chicken_(Scheme_implementation) dbr:Threaded_code dbr:Continuation_passing_style dbr:CPS dbr:Static_single-assignment_form dbr:Scope_(formal_semantics) dbr:Store-passing_style dbr:Continuation-passing dbr:Continuation_Passing_Style dbr:Continuation_passing |
| is foaf:primaryTopic of | wikipedia-en:Continuation-passing_style |