Quelles sont les fonctions mises en scène (conceptuellement)?

24

Dans un récent article du CACM [1], les auteurs présentent une implémentation des fonctions par étapes . Ils utilisent le terme comme s'il était bien connu, et aucune des références ne ressemble à une introduction évidente.

Ils donnent une brève explication (l'accent est mis sur le mien et le numéro de référence a changé; c'est 22 dans l'original)

Dans le contexte de la génération de programmes, la programmation en plusieurs étapes (MSP, staging en abrégé) telle qu'établie par Taha et Sheard [2] permet aux programmeurs de retarder explicitement l'évaluation d'une expression de programme à un stade ultérieur (donc de mettre en scène une expression). La présente étape agit effectivement comme un générateur de code qui compose (et éventuellement exécute) le programme de la prochaine étape.

Cependant, Taha et Sheard écrivent (c'est moi qui souligne):

Un programme en plusieurs étapes est un programme qui implique la génération, la compilation et l'exécution de code, le tout à l'intérieur du même processus. Les langues à plusieurs étapes expriment des programmes à plusieurs étapes. La mise en scène, et par conséquent la programmation en plusieurs étapes, répondent au besoin de solutions à usage général qui ne paient pas de frais d'interprétation d'exécution.

Ils passent ensuite à plusieurs références à des travaux plus anciens qui montreraient que la mise en scène est efficace, ce qui suggère que le concept est encore plus ancien. Ils ne donnent pas de référence pour le terme lui-même.

Ces affirmations semblent orthogonales, sinon contradictoires; peut-être que ce que Rompf et Odersky écrivent est une application de ce que Taha et Sheard proposent, mais c'est peut-être une autre perspective sur la même chose. Ils semblent convenir qu'un point important est que les programmes (ré) écrivent des parties d'eux-mêmes au moment de l'exécution, mais je ne sais pas si c'est une capacité nécessaire et / ou suffisante.

Alors, qu'est-ce que la mise en scène, respectivement, sont des interprétations de la mise en scène dans ce contexte? D'où vient le terme?


  1. Staging modulaire léger: une approche pragmatique de la génération de code d'exécution et des DSL compilés par T. Rompf et M. Odersky (2012)
  2. Programmation MetaML et multi-étapes avec annotations explicites par W. Taha et T. Sheard (2000)
Raphael
la source
Quelle contradiction voyez-vous entre les deux déclarations? Pour moi, ils semblent parler de la même chose, avec un accent différent.
Gilles 'SO- arrête d'être méchant'
@Gilles Je n'ai pas besoin de génération / compilation de code à l'exécution pour retarder l'évaluation de quelque chose (voir continuables). Il se peut très bien que ce soit juste un autre accent (j'admets cette option dans la question), mais je ne peux pas vraiment le dire.
Raphael
Vous pouvez consulter l'implémentation du langage de programmation Julia et la documentation de métaprogrammation sur @generated functions: julia.readthedocs.org/en/latest/manual/metaprogramming/…
SalchiPapa

Réponses:

21

À ma connaissance, le terme calcul par étapes a été utilisé pour la première fois par Bill Scherlis dans cet article . Auparavant, le terme « évaluation partielle » était utilisé pour à peu près le même concept, mais l'idée de calcul par étapes est subtilement différente. Les deux idées sont liées au théorème Smn de Kleene .

Si vous avez une fonction de deux arguments, mais que vous connaissez un argument, disons m , vous pouvez effectuer immédiatement une partie du calcul de la fonction en utilisant la connaissance du premier argument. Il vous reste alors une fonction ϕ m ( n ) dont les calculs ne dépendent que du deuxième argument, inconnu.ϕ(m,n)mϕm(n)

L'idée de l'évaluation partielle est de calculer automatiquement la fonction spécialisée . Étant donné le code de la fonction d'origine ϕ , l'évaluation partielle effectue une analyse statique pour déterminer quels bits du code dépendent de m et quels bits dépendent de n , et le transforme en une fonction ϕ qui, étant donné m , construit ϕ m . Le deuxième argument n peut alors être appliqué à cette fonction spécialisée.ϕm(n) ϕmnϕmϕmn

L'idée du calcul par étapes est de penser d'abord à la fonction . On l'appelle une fonction "par étapes" car elle fonctionne en plusieurs étapes. Une fois que nous lui avons donné le premier argument m , il construit le code de la fonction spécialisée ϕ m . Il s'agit de la «première étape». Dans la deuxième étape, le deuxième argument est fourni à ϕ m qui fait le reste du travail.ϕmϕmϕm

ϕϕ

  • Comment définir les fonctions par étapes?
  • Quels langages de programmation et systèmes de types utiliser pour définir les fonctions intermédiaires?
  • Quelle est la sémantique de ces langues?
  • Comment assurer la cohérence et l'exactitude des fonctions mises en scène?
  • Quelles techniques sont utiles pour construire automatiquement ou semi-automatiquement des fonctions par étapes?
  • Comment prouver l'exactitude de telles techniques?

Le calcul par étapes peut être très important dans la pratique. En fait, chaque compilateur est en fait un calcul par étapes. Étant donné un programme source, il construit un programme cible traduit et optimisé, qui peut ensuite prendre l'entrée réelle et calculer le résultat. Il est difficile d'écrire des programmes de calcul par étapes dans la pratique, car nous devons jongler avec les multiples étapes et nous assurer que les bonnes choses sont faites au bon moment. Tous ceux qui ont écrit un compilateur ont eu des problèmes avec ces problèmes. Il est également difficile d'écrire des programmes qui écrivent d'autres programmes, qu'il s'agisse de programmes en langage machine (compilateurs), de requêtes SQL (manipulations de bases de données) ou de code HTML / Pages de serveur / Javascript (applications Web) et d'une myriade d'autres applications.

Uday Reddy
la source
ϕϕ
Donc, ce que vous entendez par évaluation partielle est une abstraction sur la programmation en plusieurs étapes, ce qui signifie qu'une évaluation partielle n'implique pas une programmation en plusieurs étapes, mais une programmation en plusieurs étapes implique une évaluation partielle. Grâce à quoi une évaluation partielle peut être effectuée en une ou plusieurs étapes, car le currying dans les langages fonctionnels n'implique pas nécessairement plusieurs étapes et la génération de code lors de l'exécution, n'est-ce pas?
denis631
1
Pas exactement. Un évaluateur partiel compile un programme ordinaire en un programme en 2 étapes puis exécute sa première étape. Dans la programmation par étapes, vous écrivez vous-même le programme en plusieurs étapes.
Uday Reddy
9

Bien que les autres réponses soient techniquement correctes, je ne pense pas qu'elles donnent une bonne compréhension de la raison pour laquelle les informaticiens s'intéressent aux fonctions par étapes.

En créant des fonctions intermédiaires, vous définissez des programmes qui génèrent des programmes. L'un des grands objectifs de la théorie moderne du langage pratique est de maximiser la réutilisation potentielle. Nous voulons permettre d'écrire des bibliothèques qui ne sont pas seulement des fonctions et des objets utiles, mais qui aident les programmeurs en fournissant des constructions architecturales d'ordre supérieur.

Ce serait formidable si nous pouvions nous débarrasser de tout le code passe-partout. Nous devrions être en mesure de minimiser le langage de spécification. Si nous voulons qu'un répartiteur piloté par événement, par exemple, communique avec d'autres répartiteurs avec une conception de thread donnée, nous devrions être en mesure de le spécifier de manière compacte, et tous les écouteurs d'E / S et les connexions d'objet de file d'attente et de thread devraient pouvoir être construits à partir de cette spécification.

Les langues de domaine sont généralement les représentations compactes que nous recherchons. Lorsque les gens travaillent dans un domaine pendant un certain temps, la langue qu'ils utilisent a tendance à supprimer la plupart des doublons d'informations et à devenir une spécification allégée. Cette théorie de la mise en scène tend donc à devenir un système de traduction des langages de domaine vers le langage d'exécution.

Les compilateurs sont techniquement des stagers, mais il manque le but. L'objectif de la mise en scène moderne est de permettre la création de programmes qui créent des programmes afin de maximiser la réutilisation et d'automatiser la construction de programmes dans la mesure du possible. Ce serait formidable si un jour les exigences fonctionnelles d'un programme étaient le programme.

Voir «Programmation générative» de Czarnecki et Eisenecker (ISBN-13: 978-0201309775).

ex0du5
la source
@Raphael: Voici le chapitre trois avec les bases sur les domaines et la réutilisation. Regardez même l'optimisation que vous mentionnez. La FFT ne se fait pas par mise en scène pour accélérer son exécution. Cela est fait pour que le programmeur n'ait pas à calculer la table de valeurs à chaque fois à la main, à les copier dans le programme et à créer une grande liste. C'est pour minimiser le travail effectué et réutiliser les étapes de base. Même chose avec le déroulement de la boucle. Le faire à la main répète les informations et ne peut pas être réutilisé.
ex0du5
Ce point de vue DSL semble limiter la mise en scène à un niveau (un compilateur DSL à l'intérieur du programme), non?
Raphael
1
@Raphael: Cela dépend vraiment de votre point de vue. De toute évidence, le concept n'ajoute aucune puissance de calcul lorsqu'il est considéré simplement comme la source -> traduction exécutable. Nous pourrions simplement construire un compilateur pour le langage DS et être fait. D'où vient sa force, c'est dans l'itération. Lors de la construction de bibliothèques qui seront utilisées et développées par des projets à l'avenir, des étapes naturelles apparaissent à l'intérieur des limites de la bibliothèque. Vous pouvez avoir une bibliothèque qui transforme les spécifications des objets en source pour une sérialisation complète, puis une autre bibliothèque qui construit la couche transport basée sur des spécifications de répartition ...
ex0du5
1
@Raphael: La mise en scène peut plus naturellement se faire en plusieurs étapes. Si un morceau de code a vu ses exigences changer beaucoup au fil du temps, alors que d'autres sont beaucoup plus stables, il peut être approprié en raison de "couches de cisaillement" de séparer le transfert en couches avec des interfaces plus stables. Vous pouvez ensuite affecter moins le système avec des modifications et respecter une forme de mise en scène du principe ouvert-fermé. Ce sont des préoccupations pratiques qui n'ont pas de nécessité mathématique, mais tout est basé sur l'aspect pratique. Nous ne voulons pas un seul langage de compilation, nous voulons permettre l'évolution.
ex0du5
5

La réponse est donnée dans la partie perspective technique de l'article en question [1]. Le problème considéré est la zone de tension entre le code général et le code spécifique:

Les programmes peuvent être écrits pour être à usage général ou à usage spécial. Le code à usage général a l'avantage d'être utilisable dans une variété de situations, tandis que le code à usage spécial peut être écrit de manière à tirer parti des caractéristiques uniques de l'environnement d'exécution et ainsi gagner en efficacité au détriment de la réutilisation.

Bien sûr, nous voulons résoudre cette tension, c'est-à-dire réaliser un code général et une implémentation spécifique:

On peut se poser la question: est-il possible d'écrire du code pour qu'il soit à usage général mais de le faire ensuite se spécialiser automatiquement dans la situation en cours d'exécution?

Cela a donné lieu à l'idée d'avoir des programmes (généraux) (ré) écrivant eux-mêmes au moment de l'exécution pour s'adapter à une situation spécifique:

En conséquence, une direction importante de la recherche a impliqué la recherche d'un langage et d'une technologie de compilation qui peuvent permettre aux programmeurs d'écrire du code à usage général qui est ensuite correctement et efficacement transformé en code spécialisé hautes performances au moment de l'exécution.

Je suppose que le JIT de Java est un bon exemple. Une idée particulière est la programmation en plusieurs étapes, que Lee explique comme ceci:

Dans cette ligne de recherche, l'une des idées fondamentales est le concept de mise en scène. Nous imaginons l'exécution d'un programme se déroulant en une série d'étapes, chacune calculant les valeurs utilisées par les étapes ultérieures. Ce que nous cherchons, alors, est d'écrire le code du programme afin que ces étapes soient rendues apparentes. Si cela est accompli, nous pouvons alors organiser la compilation du code à un stade ultérieur dans des générateurs de code qui optimisent par rapport aux résultats des calculs à un stade antérieur.

C'est-à-dire que le "staging" est une manière de regarder les fonctions / codes appropriés qui identifient les phases du calcul / exécution qui peuvent être simplifiées en connaissant les résultats des phases précédentes. Un "retard" du calcul comme dans la première citation de la question peut être un effet secondaire nécessaire pour séparer correctement les étapes, mais ce n'est pas le point.

Rompf et Odersky citent la transformation de Fourier rapide comme exemple qui peut être instructif.


  1. Le renard et le hérisson: perspective technique par Peter Lee (2012)
Raphael
la source