Quel est un exemple de continuation non mise en œuvre en tant que procédure?

15

Une discussion intéressante sur la distinction entre rappels et continuations sur SO a amené cette question. Par définition, une continuation est une représentation abstraite de la logique nécessaire pour effectuer un calcul. Dans la plupart des langues, cela se manifeste comme une procédure à un argument à laquelle vous transmettez la valeur qui nécessite un traitement continu.

Dans un langage purement fonctionnel (où toutes les fonctions sont des citoyens purs et de première classe), je pense qu'une suite pourrait être entièrement modélisée comme une fonction. C'est, après tout, ainsi que j'ai compris jusqu'ici les suites. Cependant, le monde est plein d'état (soupir ..) et donc la définition générale n'exige pas qu'un état de programme de capture de continuation - il ait seulement besoin d'englober l'intention.

Pour faciliter ma compréhension, peut-on fournir un exemple dans un langage fonctionnel où la suite s'exprime de manière plus abstraite qu'une fonction? Je sais que Scheme vous permet de saisir la continuation actuelle de manière de première classe (call / cc), mais même ainsi, il semble que la procédure à un argument passée à call / cc reçoive simplement la continuation actuelle sous la forme d'une autre procédure d'argument à laquelle la fonction call / cc'd peut appliquer son résultat.

David Cowden
la source
Peut-être l'intersection des continations et de la défonctionnalisation en tant que: les continuations peuvent être converties en structures de données via la défonctionnalisation; pourrait être un domaine intéressant à regarder.
Dan D.
@DanD. avez-vous des suggestions de littérature intéressante à lire? Ce sujet semble utile.
David Cowden

Réponses:

11

tl; dr; Le type est l'abstraction globale sur une continuation


Une continuation est le type de ses entrées et sorties

La chose la plus proche que vous trouverez d'une continuation non basée sur une procédure est probablement la monade de continuation dans Haskell car elle est exprimée en tant que type, pour lequel de nombreuses fonctions peuvent être utilisées pour interagir avec le type pour interrompre, reprendre, revenir en arrière, et al.

Vous pouvez encapsuler cette fermeture dans un type tel que le Conttype dans Haskell où vous obtenez l'abstraction de la monade comme une "abstraction de niveau supérieur", et il existe d'autres formes d'abstraction sur les continuations que vous obtenez lorsque vous regardez la continuation comme un type au lieu de simplement une procédure , par exemple

  • Vous pouvez prendre deux suites et faire une alternative entre elles si le type suit les lois pour être monoïde
  • Vous pouvez résumer le type pour modifier les types d'entrée ou de sortie de la continuation si vous encapsulez la fermeture dans un type qui respecte les lois d'un foncteur
  • Vous pouvez appliquer ou décorer arbitrairement et partiellement votre suite avec des fonctionnalités telles que la validation d'entrée ou la conversion d'entrée si vous encapsulez la fermeture dans un type qui suit les lois d'un foncteur applicatif

Clôture vs procédure

À la fin de la journée, vous avez fondamentalement raison; une continuation est une "procédure", même si je préfère parler de clôture. Souvent, les prolongations de temps sont mieux exprimées comme des fermetures de première classe qui ont enfermé un environnement lié. Dans un langage purement fonctionnel, vous pourriez dire que ce n'est pas particulièrement raisonnable parce que vous manquez de références; cela est vrai, mais vous pouvez inclure des valeurs et une affectation unique fait exactement la même chose entre la valeur et la référence. Cela donne lieu à Haskell:

(\x -> \y -> insideYIcanAccess x (and y))

Un langage qui n'a pas la capacité de contenir un environnement contraignant peut techniquement manquer de fermetures de première classe, mais même dans ce cas, il existe un environnement (généralement le global) qui est disponible pour la fermeture.

Je dirais donc qu'il est plus exact de décrire une continuation comme: Une fermeture utilisée d'une manière particulière.


Conclusion

A la question "Est-ce qu'une continuation est implémentable d'une autre manière qu'une procédure?" Non. Si vous n'avez pas de fonctions de première classe, vous ne pouvez vraiment pas avoir de continuations en tant que telles (oui, les pointeurs de fonction comptent comme des fonctions de première classe, donc un accès à la mémoire arbitraire peut suffire).

Passons maintenant à la question "Existe-t-il des moyens d'exprimer une suite de manière plus abstraite qu'une procédure?" L'exprimer en tant que type vous donne une abstraction beaucoup plus grande, vous permettant de traiter la continuation de manière très générale de sorte que vous pouvez interagir avec la continuation de bien plus de façons que de simplement l'exécuter.

Jimmy Hoffa
la source
1
Cela se généralise à "Une continuation peut être simplement tout ce qui vous permet d'obtenir le résultat du reste du programme". Comme cela nécessite normalement d'avoir du code (le reste du programme), la plupart des langues utilisent des fonctions. Théoriquement, vous pouvez construire une suite à partir de n'importe quoi. Lors de la conversion de continuation dans mes compilateurs, j'ai utilisé des arbres partiellement remplis.
Daniel Gratzer
1
@jozefg Les arbres partiellement remplis sont une représentation correcte d'un calcul en tant qu'expression, mais à la fin de la journée, le code en cours d'écriture est une sorte d'expression qui ne peut pas être identifiablement différente d'une procédure, telle que je la comprends. Cela mis à part, les arbres partiellement remplis sont la représentation du compilateur; la représentation des développeurs est en principe une expression de calcul normative avec la syntaxe et la sémantique du langage, qui apparaîtrait à 99% des développeurs comme une "procédure", une "fonction" ou autre. Vous pensez du point de vue du développeur du compilateur heh
Jimmy Hoffa
2

Un exemple que vous pourriez aimer sont les coroutines. Par exemple, les Coroutines de Lua ou les itérateurs / générateurs de Python ou C # ont une puissance similaire aux continuations ponctuelles (continuations que vous n'êtes autorisé à appeler qu'une seule fois) mais la continuation n'est pas explicitement transformée en fonction. Au lieu de cela, vous avez des moyens de faire avancer la coroutine jusqu'à la prochaine instruction "yield".

Par exemple, considérez le programme Python suivant:

def my_iterator():
   yield 1
   yield 2
   yield 3

def main():
   it = my_iterator()
   x = it.next()
   y = it.next()
   z = it.next()
   print x + y + z

Son genre de semblable au programme Javascript suivant avec des rappels explicites:

function my_iterator()
  return function(cb1){
    cb1(1, function(cb2){
      cb2(2, function(cb3){
        cb3(3, function(cb4){
          throw "stop iteration";
        });
      });
    });
  });
}

function main(){
   var getNext1 = my_iterator();
   getNext1(function(x, getNext2){
      getNext2(function(y, getNext3){
         getNext3(function(z, getNext4){
            console.log(x + y + z);
         });
      });
   });
}

L'exemple Javascript est un peu bruyant car chaque étape doit renvoyer la suite suivante en plus de renvoyer la valeur produite (dans le Python garde une trace de la suite à l'intérieur de l'ite

hugomg
la source