Il y a quelques années, j'ai commencé à écrire un interprète pour un peu de langage spécifique de domaine qui comprenait des fonctions définies par programmeur.
Au début, j'ai mis en œuvre une portée variable à l'aide d'une simple pile de tables de symboles. Mais maintenant, je veux passer à un cadre lexical approprié (avec la possibilité de fermetures). Quelqu'un peut-il expliquer la structure de données et l'algorithme derrière une portée lexicale?
5 Réponses :
Il n'y a pas de bonne façon de faire cela. L'important est d'indiquer clairement la sémantique que vous cherchez à fournir, puis les structures de données et les algorithmes suivront.
Sûr. Je peux toujours essayer de dériver moi-même le tout. :-) Mais pour de nombreuses tâches de programmation bien comprises, il existe généralement des solutions existantes déjà connues et largement enseignées et adoptées, non?
Le livre référencé dans le commentaire à votre question, ou le célèbre livre avec le dragon sur la couverture, prendra en charge cela.
Pour obtenir un cadre et des fermetures lexiques corrects dans un interprète, tout ce que vous avez à faire est de suivre ces règles:
eval (expression, env) => valeur .
- Lorsque le code interprété appelle une fonction, l'environnement est pas transmis à cette fonction. La signature de votre fonctionnement de la fonction fonction est comme
Appliquer (fonction, arguments) => Valeur .
- Lorsqu'une fonction interprétée est appelée, l'environnement que son corps est évalué est
l'environnement dans lequel la définition de la fonction a été faite, et n'a rien à voir avec l'appelant. Donc, si vous avez une fonction locale, il s'agit d'une fermeture , c'est-à-dire une structure de données contenant des champs {définition de la fonction, env-d-définition-temps} . < / li>
pour développer ce dernier bit dans la syntaxe Python-ISH: xxx doit être exécuté comme s'il était xxx < / Pré> Lorsque le second argument dict peut être juste l'actuel-ENV plutôt que la structure de données construite à ce moment-là. (D'autre part, retenir l'ensemble de l'ENV plutôt que les variables fermées peuvent signifier que les programmes ont des fuites de mémoire surprenantes, car les fermetures se tiennent à des choses dont la nécessité n'est pas nécessaire. Cela vaut la peine de réparer dans n'importe quelle mise en œuvre "pratique", mais pas Lorsque vous expérimentez simplement la sémantique du langage.)
Il existe de nombreuses façons différentes de mettre en œuvre le cadre lexical. Voici quelques-uns de mes favoris:
Si vous n'avez pas besoin de performances super-rapides, utilisez une structure de données purement fonctionnelle pour implémenter vos tables de symboles et représenter une fonction imbriquée par une paire contenant un pointeur sur le code et un pointeur sur la table des symboles. .
Si vous avez besoin de vitesses de code natif, ma technique préférée est décrite dans faisant un curry rapide par Simon Marlow et Simon Peyton Jones.
Si vous avez besoin de vitesses de code natif, mais les fonctions au curry ne sont pas si importantes, considérez Style de passage de fermeture .
Le papier sur Currying semble être parfois informel de manière inappropriée. Par exemple, voir la 2e phrase du dernier paragraphe de la 2e section: "L'appel est à une fonction connue - une dont le compilateur peut" voir "" . Par "voir", ils signifient que la fonction apparaît dans la portée lexicale où elle est utilisée. Sinon, je suppose que c'est une bonne lecture si vous êtes comme moi essayant de comprendre comment faire un interprète.
STROSTRUP Mise en place dans le premier compilateur C ++ avec une seule table de symboles par périmètre et une règle de chaînage qui suivit des étendues vers l'extérieur jusqu'à la découverte d'une définition. Comment cela fonctionne exactement dépend de votre sémantique précise. Assurez-vous de clouer ceux-ci en premier.
Knuth In L'art de la programmation informatique, Vol 1, donne un algorithme pour une table de symboles COBOL dans laquelle le scopage est effectué via des liens.
Vous devriez lire essentiels de langages de programmation cs.indiana.edu/eopl " a>