Gültigkeit von Variablen... oder so etwas. (Seite 2) (Allgemeines zu Perl)

[thread]11322[/thread]

Gültigkeit von Variablen... oder so etwas. (Seite 2)

Leser: 13

murphy

2008-02-20 15:28

User since
2004-07-19
1776 Artikel
HausmeisterIn

Goto mit Parametern gibt's in Perl auch:

Code (perl): (dl )

use 5.010;
use strict;
use warnings;

sub foo {
  say 'Tail-calling bar...';
  @_ = (1, 2);
  goto &bar;
  say 'This should never be reached!';
}

sub bar {
  my ($a, $b) = @_;
  say "bar($a, $b) called";
}

say 'Calling foo...';
foo();
say '... returned from foo';

Bei dieser Form von goto wird der aktuelle Funktionsaufruf durch einen neuen ersetzt, ohne dass ein neuer Stackframe angelegt wird. So etwas nennt man auch einen Tail-Call.

Tail-Calls haben mit Continuation-passing-style nur insofern etwas zu tun, als letzterer ohne Tail-Calls zwangsläufig irgendwann zum Stapelüberlauf führt.

Der eigentliche Sinn von Continuation-passing-style ist der, in einer Sprache, die das nicht nativ unterstützt, Continuations explizit zu machen, wobei eine Continuation so etwas wie der eingefrorene Zustand eines Programmes ist, das darauf wartet einen Rückgabewert zu empfangen und weiterzurechnen.

Man ersetzt also jede Rückgabe eines Wertes durch den Aufruf einer Funktion, die als Parameter übergeben wurde. Normaler Code:

Code (perl): (dl )

use 5.010;
use strict;
use warnings;

sub square($) {
  my $x = shift;
  return $x * $x;
}

sub square_and_say($) {
  my $x = shift;
  my $s = square($x);
  say "$x ^ 2 = $s";
}

square_and_say 2;

Continuation-passing-style:

Code (perl): (dl )

use 5.010;
use strict;
use warnings;

sub square(&$) {
  my ($rc, $x) = @_;
  @_ = ($x * $x); goto &$rc;
}

sub square_and_say(&$) {
  my ($rc, $x) = @_;
  my $square_rc = sub {
    my $s = shift;
    say "$x ^ 2 = $s";
    @_ = (); goto &$rc;
  };
  @_ = ($square_rc, $x); goto &square;
}

square_and_say { } 2;

Diesen zusätzlichen Parameter für jede Funktion nennt man jetzt einfach die Rückgabe-Continuation der Funktion.

Das ganze sieht umständlich aus und ist es auch, aber andererseits erkennt man, dass diese Transformation sehr kanonisch ist und leicht von einem Compiler automatisch durchgeführt werden könnte. Außerdem stellt man schnell fest, dass man sich hier neue Möglichkeiten der Programmierung eröffnet hat: Um in Perl-Terminologie zu sprechen, hat man nun praktisch in jeder Subroutinene eine Referenz \&return zur Verfügung nämlich die Return-Continuation der Subroutinen. Diese Referenz kann man nun aber nicht wie return nur in der Subroutine benutzen, zu der sie eigentlich gehört, sondern sie lustig in der Gegend herumübergeben und von anderen Stellen des Programmes aus aufrufen um den Kontrollfluss zu verändern.

Auf Basis von Continuations kann man zum Beispiel trivial Exceptions mit optionalem Neustart des fehlerbehafteten Codes implementieren, oder Webapplikationen, die mehrere Formulare hintereinander präsentieren müssen schreiben, als handele es sich um ein lineares Programm, das nacheinander mehrere Seiten an den Browser sendet und die Eingaben einliest.

Einfacher zu benutzen sind Continuations natürlich, wenn die Programmiersprache spezifische Unterstützung dafür mitbringt zum Beispiel indem der Compiler automatisch alles in Continuation-passing-style transformiert. Bekanntere Sprachen, die das können, sind zum Beispiel Scheme, JavaScript (in manchen neueren Versionen), Ruby, Smalltalk (manche Dialekte) und SML/NJ.

Wie auch bei goto sollte man mit der exzessiven Verwendung von Continuations in der Regel vorsichtig sein, weil sonst niemand mehr das Programm versteht. Alles in allem sind sie aber eine nette Spielerei, die durchaus auch nützlich sein kann ;-)

When C++ is your hammer, every problem looks like your thumb.

KurtZ

2008-02-20 17:56

User since
2007-12-13
411 Artikel
BenutzerIn
[default_avatar]

murphy+2008-02-20 14:28:52--
Goto mit Parametern gibt's in Perl auch:

hmm ... stimmt ...habe ich bisher nur in Autoloadkonstrukten gesehen..

murphy+2008-02-20 14:28:52--
. wobei eine Continuation so etwas wie der eingefrorene Zustand eines Programmes ist, das darauf wartet einen Rückgabewert zu empfangen und weiterzurechnen.

Eine Statemachine?

murphy+2008-02-20 14:28:52--
.Man ersetzt also jede Rückgabe eines Wertes durch den Aufruf einer Funktion, die als Parameter übergeben wurde. Normaler Code:

Ok ich erkennen in deinem Code diverse Regeln:

1. Für benannte Sub ist $_[0] immer die Folgeroutine als code_ref (=def Continuation?)

2. Letzte Aktion statt eines Returns ist der Aufruf der Folgeroutine mittels
"goto &$_[0](args)"

3. Im einfachsten Fall erhält man eine lineare Kette von Aufrufen, $_[0] ist ein Code_ref auf den jeweilige Folgeroutine.

vereinfachtes Codebeispiel: [1]
statt

Code (perl): (dl )

1
2
3

sub1(); 
sub2();
sub3()

schreibt man

Code (perl): (dl )

sub1(\&sub2)

und in sub1 kommt als letztes eine übergabe von \&sub3 als Folgeroutine

Code (perl): (dl )

sub1 {
   ...
   $_[0]->(\&sub3) ;# => sub2(\&sub3)
}

4. will man eine Routinen verschachtelt aufrufen, [ wie im Bsp. mit Effekt say(square($x)) ] dann ruft die Oberroutine die Untere mit einer code_ref auf ein Closures der Oberoutine auf,
sodass die Unterroutine immer wieder die Kontrolle an die obere übergibt.

also statt:

Code (perl): (dl )

sub subA {
  {block1}
  sub2();
  {block2}
  sub3()
  {block 3}
  return; 
}

gibts

Code (perl): (dl )

sub subA {
  $rc_contA=shift;

  $rc1= sub {block1; sub2( $rc2 ) }
  $rc2= sub {block2; sub3( $rc3 ) }
  $rc3= sub {block3; &$rc_contA; }

  $rc1->(); #aufruf
}

OK ... ich kann mir vorstellen das man Statemachines damit gut und performant realisieren kann...

Hmm ...richtig schätzen würde man sowas aber erst wenn man entsprechende Design Patterns beherrscht.

Aber ist der Overhead für Routinenaufrufe wirklich so hoch, dass das lohnt?

Gruß
Kurt

[1] der Lesbarkeit willen hab ich auf Gotos verzichtet und die Folgeroutinen konventionell übergeben, was natürlich zu Stacküberläufen führen würde. Auch Argumente hab ich mal weggelassen. Der Codeablauf sollte klar werden.

TMTOWTDYOG (there's more than one way to dig your own grave)

Struppi

2008-02-20 19:21

User since
2006-02-17
628 Artikel
BenutzerIn

Hat das was mit Lambda Closures zu tun?
hxx:// perldesign***** .com /?LambdaClosure
Last edited: 2020-01-28 18:26:43 +0100 (CET)

murphy

2008-02-20 23:25

User since
2004-07-19
1776 Artikel
HausmeisterIn

@KurtZ: Der Overhead für Funktionsaufrufe ist nicht hoch und die Transformation in CPS lohnt sich nur aus konzeptuellen Gründen, zur Obfuscation oder wenn sie vom Compiler übernommen wird ;-) Im letzteren Fall kann ein CPS-transformiertes Programm tatsächlich Geschwindigkeitsvorteile haben, was aber weniger damit zusammenhängt, dass Funktionsaufrufe vermieden werden, sondern damit, dass man spezielle Speicherverwaltungsstrategien anwenden kann...

@Struppi: Klar hat das etwas mit Closures zu tun, nachdem Closure in Perl praktisch ein Synonym für anonyme Subroutine ist :-)

When C++ is your hammer, every problem looks like your thumb.

Struppi

2008-02-21 00:09

User since
2006-02-17
628 Artikel
BenutzerIn

Ich sprach von Lambda Closures, das sind Ketten von Funktionsaufrufen oder auf deutsch Zuständigkeitsketten, das ist doch sowas ähnliches wie ihr hier beschreibt.

KurtZ

2008-02-21 16:46

User since
2007-12-13
411 Artikel
BenutzerIn
[default_avatar]

Struppi+2008-02-20 23:09:12--
Ich sprach von Lambda Closures, das sind Ketten von Funktionsaufrufen oder auf deutsch Zuständigkeitsketten, das ist doch sowas ähnliches wie ihr hier beschreibt.

so wie ich den Link verstehe (danke übrigens sehr interessant) bedeutet Lamda Closure nur das ein anonymes Sub in einer Closurevariablen gehalten wird, die Standardmethode von Perl um Routinen zu lokalisieren.

Um CPS-Konstrukte in Perl zu implementieren braucht man wohl die gleiche Technik... AFAIK.

Das gezeigte Beispiel ist aber zu CPS conträr, schließlich wird mit jedem Listenelement eine weitere Rekursionstiefe erzeugt, CPS will aber den Stack schonen und den Code durch Nutzung der Register beschleunigen.

sowas wie (ungestestet)

Code (perl): (dl )

{
  @code_refs=();
 
  sub add_cr {
     push @code_refs, shift ;
  }

  sub  run_cr {
     for my $cr (@code_refs) {
         $cr->(@_);
     }
  }
}

sollte übrigens auch den gleichen Effekt haben wie das Lamda Closure Beispiel ohne den Stack so sehr zu belasten. Wen ich sowas mal bräuchte würde ichs aber wohl Q&D mit EVAL realisieren.

Zurück zu CPS, was ich im Netz gefunden habe ist ziemlich widersprüchlich, naja warum sollte da nicht ein ähnliches Sprachwirrwar herrschen wie bei OOP. Jeder pickt sich da was anderes heraus.

Was mich fasziniert ist das dieses Konstrukt erlaubt GOTOs lesbar und wartbar zu machen und bei zeitkristischen Anwendung überzeugen dürfte.

Habe Implementierungsbeispiele für JS Rhino gesehen, AFAIS ließe sich sowas auch in einem Perl-Modul anbieten.

Was ich bisher noch nicht so gesehen habe sind aber Anwendungsbeispiele, deren Probleme in CPS einfacher und intuitiver zu modellieren sind als mit klassischen Mitteln.

Mir fallen wie gesagt nur Statemachines ein.

TMTOWTDYOG (there's more than one way to dig your own grave)

murphy

2008-02-21 16:53

User since
2004-07-19
1776 Artikel
HausmeisterIn

@Struppi: Vielleicht liegt's daran, dass ich zu viele Programmiersprachen kenne, aber die Ausdrücke "innere Funktion", "Closure", "Lambda Ausdruck", "Lambda Closure", "anonyme Funktion", "anonyme Subroutine" oder "Delegate" kommen alle an verschiedenen Stellen mit identischer Bedeutung vor. Ich weiß also nicht, was für Dich der Unterschied zwischen einer Lambda Closure und einer Closure ist. Nach Lektüre des von Dir verlinkten Artikels konnte ich auch nur feststellen, dass er genau das Konzept beschreibt, welches mit all den erwähnten Begriffen bezeichnet werden kann: Das Erstellen von (anonymen) Funktionen, die über alle am Ort und zum Zeitpunkt der Erstellung gültigen lexikalischen Variablen abgeschlossen sind.

Eine CPS-Transformation benutzt solche Funktionen um das weiterreichende Konzept der Continuations zu emulieren. Während eine Closure über lexikalische Variablen abgeschlossen ist, ist eine Continuation zusätzlich über den Aufrufstack abgeschlossen.

Continuations sind das funktionale Äquivalent zu goto-Befehlen, können aber zusätzlich Parameter aufnehmen und neben einem nicht-lokalen Kontrolltransfer auch eine Modifikation von (Variablen- und Aufruf-) Stackinhalt und Stacktiefe verursachen. Continuations sind damit auch ein echt mächtigeres Konstrukt als Exceptions, welche zwar ebenfalls einen nicht-lokalen Kontrolltransfer verursachen, dabei aber die Stacktiefe lediglich verringern und den tieferen Inhalt nicht verändern können.

Das Konzept der Continuations ist nicht ganz trivial nicht umsonst gibt es eine Witzprogrammiersprache namens Unlambda, die als einzige explizite Flusskontrollstruktur Continuations enthält, um maximal unverständlichen Code zu erzwingen ;-)

When C++ is your hammer, every problem looks like your thumb.

murphy

2008-02-21 17:06

User since
2004-07-19
1776 Artikel
HausmeisterIn

KurtZ+2008-02-21 15:46:20--
[...]
Habe Implementierungsbeispiele für JS Rhino gesehen, AFAIS ließe sich sowas auch in einem Perl-Modul anbieten.

In Rhino JS muss man nicht im CPS programmieren, weil es native Continuations gibt! In Perl müsste man entweder selbst CPS schreiben, den Compiler hacken um automatisch in CPS zu transformieren, den Interpreter hacken um Interpreterthreads zur Emulation von Continuations zu benutzen, oder auf Perl6 warten, denn Parrot soll native Unterstützung für Continuations bekommen :-)

Quote
Was ich bisher noch nicht so gesehen habe sind aber Anwendungsbeispiele, deren Probleme in CPS einfacher und intuitiver zu modellieren sind als mit klassischen Mitteln.

Mir fallen wie gesagt nur Statemachines ein.

Es gibt ein paar Webframeworks, die Continuations oder Techniken mit vergleichbarem Effekt einsetzen, um die asynchrone, anfragegesteuerte Natur einer Webanwendung zu verschleiern und dem Programmierer mehr das Gefühl eines linearen, interaktiven Programmablaufes zu geben. Für Perl existiert beispielsweise CPAN:

Continuity, für PLT Scheme gibt es einen Webserver der Continuations ausnutzt.

When C++ is your hammer, every problem looks like your thumb.

KurtZ

2008-02-21 17:55

User since
2007-12-13
411 Artikel
BenutzerIn
[default_avatar]

murphy+2008-02-21 16:06:57--
KurtZ+2008-02-21 15:46:20--
[...]
Habe Implementierungsbeispiele für JS Rhino gesehen, AFAIS ließe sich sowas auch in einem Perl-Modul anbieten.

In Rhino JS muss man nicht im CPS programmieren, weil es native Continuations gibt!

ist das entsprechender Code?
http://wiki.apache.org/cocoon/RhinoWithContinuations

murphy+2008-02-21 16:06:57--
In Perl müsste man entweder selbst CPS schreiben, den Compiler hacken um automatisch in CPS zu transformieren, den Interpreter hacken um Interpreterthreads zur Emulation von Continuations zu benutzen, oder auf Perl6 warten, denn Parrot soll native Unterstützung für Continuations bekommen :-)

Naja es reicht doch wohl für den anfang ein codefilter der den Syntax von Goto erweitert, so das implizit @_ gesetzt wird. Zugegeben Codefilter machen Probleme in Evals, aber was solls.

murphy+2008-02-21 16:06:57--
KurtZ+2008-02-21 15:46:20--
Mir fallen wie gesagt nur Statemachines ein.

Es gibt ein paar Webframeworks, die Continuations oder Techniken mit vergleichbarem Effekt einsetzen, um die asynchrone, anfragegesteuerte Natur einer Webanwendung zu verschleiern und dem Programmierer mehr das Gefühl eines linearen, interaktiven Programmablaufes zu geben.

Klar, für mich sind http-requests naheliegende Beispiele für Statemachines. Jeder request überführt den Zustand der angezeigten Seite in einen anderen.

Um ein Beispiel zu geben, sei die Aufgabenstellung eine Wikiseite zu realisieren mit den Zuständen "saved" <->"edit" <-> "preview" ->"saved". (also ein Zustandsdreieck mit zwei bidirektionalen Kanten)

Mir fehlt aber noch ein kleines konkretes Beispiel, wie ich ein Konzept intuitiver in CPS umsetze.
Gerne auch in Perl6 oder Javascript (scheme, lisp udn haskell kann ich leider nicht)

bye
Kurt

TMTOWTDYOG (there's more than one way to dig your own grave)

murphy

2008-02-22 00:07

User since
2004-07-19
1776 Artikel
HausmeisterIn

KurtZ+2008-02-21 16:55:51--
murphy+2008-02-21 16:06:57--
[...] In Rhino JS muss man nicht im CPS programmieren, weil es native Continuations gibt!

ist das entsprechender Code?
http://wiki.apache.org/cocoon/RhinoWithContinuations

Ja, ist es.

Quote
Klar, für mich sind http-requests naheliegende Beispiele für Statemachines. Jeder request überführt den Zustand der angezeigten Seite in einen anderen.

So habe ich das noch gar nicht betrachtet, aber Du hast natürlich recht. Irgendwie haben Continuations ja auch einen starken Bezug zu Statemachines, weil man sagen könnte, dass ein Programm das Continuations nutzt eine einzige große Statemachine ist, wobei jede Continuation einen möglichen Zustand darstellt.

Quote
Mir fehlt aber noch ein kleines konkretes Beispiel, wie ich ein Konzept intuitiver in CPS umsetze.
Gerne auch in Perl6 oder Javascript (scheme, lisp udn haskell kann ich leider nicht)

Mal schauen, ob mir da noch was schönes einfällt. Das einzige kleine, übersichtliche und instruktive Programm, was ich mal auf Basis von Continuations gebastelt habe, war ein Lösungsalgorithmus für Logikrätsel mit Backtracking. Das ist aber in Scheme geschrieben. Wenn ich mal zu viel Zeit habe, könnte ich das vielleicht in Perl in CPS umschreiben und ins Wiki stellen...

When C++ is your hammer, every problem looks like your thumb.

View all threads created 2008-02-18 13:44.