Comment relier la théorie et la mise en œuvre des boucles while?

8

Je travaille sur mon propre petit langage de programmation à des fins éducatives et j'ai rencontré un petit problème. Il existe plusieurs solutions différentes, mais toutes semblent inélégantes - et d'après ce que je comprends, inutiles. Mais en lisant les livres que j'ai et les recherches Google, je ne trouve pas la solution élégante.

Donc, le problème est que je me fonde sur le calcul lambda de base tel que je le comprends. J'ai défini vrai / faux comme termes d'abstraction. Je peux les combiner avec des fonctions pour faire si / alors / autre sorte de comportement. Le problème vient des boucles. Je peux définir une boucle while de base via la récursivité, mais en pratique, cela provoque un débordement de pile. Si je comprends bien, la solution habituelle serait d'effectuer l'optimisation des appels de queue, mais je ne vois pas comment je peux - les conditions sont définies en langage. Pour cette raison, le compilateur ne sait pas que le corps de la boucle while est en position de queue.

Le livre du dragon se concentre sur la mise en œuvre de la boucle en supposant qu'il existe des étiquettes et des gotos. Je pourrais certainement le faire. Il semble que d'autres langages qui ne construisent pas en boucle construisent au moins des conditionnels, puis effectuent le TCO. Et je pourrais certainement le faire aussi. Mais ma compréhension est que tant que je peux appliquer des abstractions et effectuer des réductions, les boucles (et tout le reste) devraient pouvoir être construites à partir de ces blocs de base.

Alors qu'est-ce qui me manque? Ou est-ce un de ces cas où "vous pouvez modéliser n'importe quoi une fois que vous avez X et Y" n'est pas la même chose que "vous pouvez modéliser n'importe quoi une fois que vous avez X et Y sur un vrai ordinateur" et des intégrés sont nécessaires pour la pratique fins?

Telastyn
la source
Je pense que vous avez répondu à votre propre question dans ce dernier paragraphe. Ce n'est pas parce que la théorie dit que vous pouvez faire quelque chose que c'est pratique de le faire.
svick
1
De nombreux langages ont des conditions et une récursivité et implémentent l'optimisation des appels de queue. Cherchez au-delà du livre des dragons.
Dave Clarke
Laissez-moi comprendre: vous partez du pur λ-calcul? Autrement dit, il n'a rien d'autre queλet abstractions?
Andrej Bauer
svick - bien sûr, mais en tant qu'apprenant, je ne peux pas dire si c'est le cas ici ou si j'ignore quelque chose. Dave Clarke - de nombreuses langues ont intégré des conditions et implémentent l'optimisation des appels de queue. J'ai fait des recherches et je n'ai produit aucun résultat pour le TCO conditionnel et en langue. Si vous avez une référence que j'ai négligée ... Andrej Bauer - pas tout à fait, mais assez proche. Pas de types intégrés, pas de fonctions intégrées. Vous pouvez déclarer des fonctions et appliquer des fonctions. Aller en profondeur sur ma situation particulière ferait une question de mauvaise qualité.
Telastyn
1
@Raphael L'utilisation du lambda calcul comme langue intermédiaire était une grande chose dans les années 1970 et 1980. Je crois que l'intention était de détecter les optimisations sémantiques. Ma compréhension (sachez que je ne suis pas un expert des techniques de compilation) est qu'il s'avère que les optimisations sémantiques sont vraiment difficiles, alors que les optimisations locales peuvent payer beaucoup et sont plus faciles à voir sur une langue avec des affectations de registre et une utilisation modérée de goto. Néanmoins, les idées du lambda calcul sont pertinentes pour la conception du compilateur, par exemple l'idée d'une affectation unique et le concept de continuation.
Gilles 'SO- arrête d'être méchant'

Réponses:

5

J'ai donc réussi à résoudre ce problème aujourd'hui. Le code de ma boucle while:

while (condition: ~>bool) (body: ~>void) => void {
    if condition { 
        body; 
        while condition body; 
    };
}

Quand je vais construire cela dans CIL (un runtime basé sur la pile, important pour le pseudo-code, pas important pour la réponse), cela ressemble à:

ldarg 0
<build closure from { body; while condition body; }>
call if

La chose importante qui me manquait est que dans le whilecode, le conditionnel était la chose en position de queue. Du point de vue du compilateur, le bloc et la fonction while sont deux fonctions distinctes, avec deux "queues" distinctes. Chacun de ceux-ci est facilement évalué pour la position de la queue, ce qui rend l'optimisation viable malgré le manque de conditions intégrées.

Telastyn
la source
5

Je pense que vous manquez la notion de continuation . Bien que votre compilateur ne puisse pas s'appuyer sur cette notion, en tant que concepteur de compilateur avec un langage fonctionnel comme langage source ou intermédiaire (ou cible), il est important de comprendre cette notion et de garder cela à l'esprit.

La suite d'un morceau de code décrit à quoi le code se termine. En termes impératifs, il incarne non seulement l'emplacement auquel le code saute ou tombe, mais également l'état du programme (pile et tas) à ce moment-là. En termes de calcul lambda, la continuation d'un sous-terme est le contexte dans lequel il est évalué.

Lorsque vous traduisez du code impératif dans un langage fonctionnel, l'une des difficultés est de faire face à du code qui peut sortir de plusieurs manières différentes. Par exemple, le code peut renvoyer ou déclencher une exception. Ou, le corps d'une boucle peut soit continuer à vérifier la condition à nouveau, soit quitter complètement la boucle ( breakconstruction). Il existe deux façons principales de faire face à cela:

  • Multiplexage: faire en sorte que le code retourne un type somme pour toutes les sorties possibles. Dans le cas d'un corps en boucle, ce serait Continue | Break.
  • Style de passage continu : traduire le code en une fonction qui prend un paramètre supplémentaire qui est la fonction à exécuter ensuite. Ce paramètre supplémentaire est la continuation de la fonction. Le code qui peut sortir de différentes manières reçoit un tel paramètre pour chacune des manières.

Le style de passage continu est la façon dont les structures de données sont intégrées dans le calcul lambda pur. Par exemple, lorsque vous représentez vrai commeλX,y.X et faux comme λX,y.y, les arguments X et y sont les deux suites possibles, et le booléen est une instruction "if" qui sélectionne l'une ou l'autre suite.

Dans un style passant-continuation,

while (condition) body

est traduit en

let rec f (continuation) =
  if (condition, body (f (continuation)), continuation)

Dans la traduction d'un programme dans un langage impératif typique dans un style passant-continu, la continuation est toujours la dernière chose qu'un morceau de code exécute. Par exemple, la suite de ce qui bodyprécède est exécutée après tout le code de body, donc l'optimisation des appels de queue entraîne la libération de toutes les variables locales bodyjuste avant d'exécuter la suite.

Certains langages offrent des continuations de première classe avec une construction comme call-with-current-continuation . L'appel / cc ne se prête généralement pas à l'optimisation des appels de queue - il peut en fait être une opération assez coûteuse car il peut conduire à dupliquer tout l'état du programme.

Gilles 'SO- arrête d'être méchant'
la source