Comment implémenter l'évaluation paresseuse de if ()

10

J'implémente actuellement un évaluateur d'expressions (expressions sur une seule ligne, comme des formules) basé sur les éléments suivants:

  • l'expression entrée est symbolisée pour séparer les booléens littéraux, les entiers, les décimales, les chaînes, les fonctions, les identificateurs (variables)
  • J'ai implémenté l'algorithme Shunting-yard (légèrement modifié pour gérer les fonctions avec un nombre variable d'arguments) pour se débarrasser des parenthèses et ordonner les opérateurs avec une priorité décente dans un ordre postfixé
  • mon shunting-yard produit simplement une file d'attente (simulée) de jetons (au moyen d'un tableau, mon langage Powerbuilder Classic peut définir des objets, mais n'a que des tableaux dynamiques comme stockage natif - pas une vraie liste, pas de dictionnaire) que j'évalue séquentiellement avec un machine à empiler simple

Mon évaluateur fonctionne bien, mais il me manque encore un if()et je me demande comment procéder.

Avec mon évaluation shunt-yard postfixée et basée sur la pile, si j'ajoute if()une autre fonction avec des parties vraies et fausses, un seul if(true, msgbox("ok"), msgbox("not ok"))affichera les deux messages tandis que je voudrais en afficher un seul. En effet, lorsque j'ai besoin d'évaluer une fonction, tous ses arguments ont déjà été évalués et placés sur la pile.

Pourriez-vous me donner un moyen de mettre if()en œuvre de manière paresseuse?

J'ai pensé à les traiter comme une sorte de macro, mais au début, je n'ai pas encore évalué l'état. Peut-être que j'ai besoin d'utiliser un autre type de structure qu'une file d'attente pour conserver séparément la condition et les expressions vrai / faux? Pour l'instant, l'expression est analysée avant l'évaluation, mais je prévois également de stocker la représentation intermédiaire comme une sorte d'expression précompilée pour une évaluation future.

Edit : après quelques réflexions sur le problème, je pense que je pourrais construire une représentation arborescente de mon expression (un AST au lieu d'un flux de jeton linéaire), à ​​partir de laquelle je pourrais facilement ignorer l'une ou l'autre branche de ma if().

Seki
la source

Réponses:

9

Il y a deux options ici.

1) Ne pas implémenter en iftant que fonction. Faites-en un langage avec une sémantique spéciale. Facile à faire, mais moins "pur" si vous voulez que tout soit fonction.

2) Implémentez la sémantique "appel par nom", ce qui est beaucoup plus compliqué, mais permet à la magie du compilateur de prendre en charge le problème d'évaluation paresseuse tout en restant ifen fonction au lieu d'un élément de langage. Ça va comme ça:

ifest une fonction qui prend deux paramètres, tous deux déclarés "par nom". Lorsque le compilateur constate qu'il transmet quelque chose à un paramètre de nom, il modifie le code à générer. Au lieu d'évaluer l'expression et de transmettre la valeur, il crée une fermeture qui évalue l'expression et la transmet à la place. Et lors de l'appel d'un paramètre de nom dans la fonction, le compilateur génère du code pour évaluer la fermeture.

Mason Wheeler
la source
Je ne suis pas sûr, mais la «fermeture» devrait-elle être «thunk»? Hmm, peut-être pas; vient de regarder la page wikipedia: "un thunk est une fermeture sans paramètre".
Lorsque vous dites «appeler par son nom», faites-vous référence à l'échelle mondiale? Alternativement à l'appel par nom global, il suffit d'implémenter un type de fermeture, alors la fonction if ne prend que 3 fermetures et en évalue deux (condition, puis ou sinon), mais tout ne doit pas être reconnu comme une fermeture, comme un appel complet par- nom sémantique
Jimmy Hoffa
@Matt: Le terme "thunk" peut signifier plusieurs autres choses dans le contexte de la programmation, et "fermeture sans paramètre" n'est pas le premier auquel je pense quand je l'entends. La «fermeture» est beaucoup plus claire.
Mason Wheeler
1
@JimmyHoffa: Quand je dis "appeler par nom", je fais référence à un style spécifique de configuration d'un argument de fonction, qui devrait être facultatif. Tout comme de nombreuses langues existantes vous permettront de choisir de passer un paramètre par valeur ou par référence, pour ce scénario, vous devez choisir de passer par nom.
Mason Wheeler
Alors que votre suggestion sur la sémantique "appel par nom" m'a montré quelques points intéressants, c'est un peu exagéré pour mon évaluateur qui n'est pas un compilateur complet, car mes appels de fonction sont sur une seule ligne (pensez aux formules MS-excel). Je pense que je pourrais ajouter une étape après la mise en file d'attente des jetons en faisant une pseudo-évaluation de la pile pour déduire l'arbre appelant. Il devrait être plus facile de savoir à partir de l'arbre les branches à jeter.
Seki
3

Plutôt que la fonction ayant la signature:

object if(bool, object, object)

Donnez-lui la signature:

object if(bool, object function(), object function())

Ensuite, votre iffonction appellera la fonction appropriée en fonction de la condition, en évaluant uniquement l'une d'entre elles.

Hand-E-Food
la source
1

C'est assez facile, si vous compilez tout paresseusement. Vous devez avoir un moyen de voir si une valeur est déjà évaluée, ou si elle a besoin de plus de précisions.

Ensuite, vous pouvez faire ce qui suit: S'il s'agit d'un littéral ou d'une variable (en avez-vous?, C'est-à-dire les noms de fonctions?), Poussez-le sur la pile. S'il s'agit d'une application d'une fonction, compilez-la séparément et poussez le point d'entrée sur la pile.

L'exécution d'un programme n'est alors qu'une boucle jusqu'à ce que le haut de la pile soit évalué et non une fonction. S'il n'est pas évalué ou s'il s'agit d'une fonction, appelez le code vers lequel pointe la pile.

Ingo
la source