Comment les langages de programmation définissent-ils les fonctions?

28

Comment les langages de programmation définissent-ils et sauvegardent-ils les fonctions / méthodes? Je crée un langage de programmation interprété dans Ruby et j'essaie de comprendre comment implémenter la déclaration de fonction.

Ma première idée est de sauvegarder le contenu de la déclaration dans une carte. Par exemple, si je faisais quelque chose comme

def a() {
    callSomething();
    x += 5;
}

Ensuite, j'ajouterais une entrée dans ma carte:

{
    'a' => 'callSomething(); x += 5;'
}

Le problème avec cela est qu'il deviendrait récursif, car je devrais appeler ma parseméthode sur la chaîne, qui appellerait ensuite à parsenouveau lorsqu'elle se rencontrerait doSomething, puis je manquerais finalement d'espace de pile.

Alors, comment les langages interprétés gèrent-ils cela?

Poignée de porte
la source
Oh, et ceci est mon premier post sur Programmers.SE, alors s'il vous plaît, informez-moi si je fais quelque chose de mal ou si c'est hors sujet. :)
Poignée de porte
Dans le passé, je les ai tous stockés en ligne dans mes jetons et les appels de fonction ne sont que des sauts vers un décalage spécifique (un peu comme les étiquettes dans Assembly). Êtes-vous en train de symboliser le script? Ou analyser les chaînes à chaque fois?
Simon Whitehead
@SimonWhitehead J'ai divisé la chaîne en jetons, puis analysé chaque jeton séparément.
Poignée de porte
3
Si vous êtes nouveau dans la conception et l'implémentation d'un langage de programmation, vous voudrez peut-être consulter une partie de la littérature sur le sujet. Le plus populaire est le "Dragon Book": en.wikipedia.org/wiki/… , mais il existe d'autres textes plus concis qui sont également très bons. Par exemple, la mise en œuvre de langages de programmation par Aarne Ranta peut être obtenue gratuitement ici: bit.ly/15CF6gC .
evilcandybag
1
@ddyer Merci! J'ai cherché sur Google un interprète lisp dans différentes langues et cela m'a vraiment aidé. :)
Poignée de porte

Réponses:

31

Aurais-je raison de supposer que votre fonction "analyser" non seulement analyse le code mais l'exécute également en même temps? Si vous souhaitez le faire de cette façon, au lieu de stocker le contenu d'une fonction dans votre carte, stockez l' emplacement de la fonction.

Mais il y a une meilleure façon. Cela demande un peu plus d'efforts à l'avance, mais cela donne de bien meilleurs résultats à mesure que la complexité augmente: utilisez un arbre de syntaxe abstraite.

L'idée de base est que vous n'analysez le code qu'une seule fois. Ensuite, vous avez un ensemble de types de données représentant des opérations et des valeurs, et vous en créez un arbre, comme ceci:

def a() {
    callSomething();
    x += 5;
}

devient:

Function Definition: [
   Name: a
   ParamList: []
   Code:[
      Call Operation: [
         Routine: callSomething
         ParamList: []
      ]
      Increment Operation: [
         Operand: x
         Value: 5
      ]
   ]
]

(Il s'agit simplement d'une représentation textuelle de la structure d'un AST hypothétique. L'arbre réel ne serait probablement pas sous forme de texte.) Quoi qu'il en soit, vous analysez votre code dans un AST, puis vous exécutez directement votre interpréteur sur l'AST, ou utilisez un deuxième passage ("génération de code") pour transformer l'AST en une forme de sortie.

Dans le cas de votre langue, ce que vous feriez probablement, c'est d'avoir une mappe qui mappe les noms de fonction aux AST de fonction, au lieu des noms de fonction aux chaînes de fonction.

Mason Wheeler
la source
D'accord, mais le problème est toujours là: il utilise la récursivité. Je manquerai éventuellement d'espace de pile si je le fais.
Poignée de porte
3
@ Doorknob: Qu'est-ce qui utilise la récursivité en particulier? Tout langage de programmation structuré en blocs (qui est chaque langage moderne à un niveau supérieur à ASM) est intrinsèquement basé sur un arbre et donc de nature récursive. Dans quel aspect spécifique êtes-vous préoccupé par les débordements de pile?
Mason Wheeler
1
@ Doorknob: Oui, c'est une propriété inhérente à n'importe quelle langue, même si elle est compilée en code machine. (La pile d'appels est une manifestation de ce comportement.) Je suis en fait un contributeur à un système de script qui fonctionne de la manière que j'ai décrite. Rejoignez-moi dans le chat à chat.stackexchange.com/rooms/10470/… et je discuterai avec vous de quelques techniques pour une interprétation efficace et minimiser l'impact sur la taille de la pile. :)
Mason Wheeler
2
@ Doorknob: Il n'y a pas de problème de récursivité ici car l'appel de fonction dans l'AST fait référence à la fonction par son nom , il n'a pas besoin d'une référence à la fonction réelle . Si vous compilez le code machine, vous aurez éventuellement besoin de l'adresse de la fonction, c'est pourquoi la plupart des compilateurs effectuent plusieurs passes. Si vous voulez avoir un compilateur en un seul passage, vous avez besoin de "déclarations avant" de toutes les fonctions afin que le compilateur puisse attribuer des adresses à l'avance. Les compilateurs de bytecode ne se soucient même pas de cela, la gigue gère la recherche de nom.
Aaronaught
5
@ Doorknob: C'est en effet récursif. Et oui, si votre pile ne contient que 16 entrées, vous ne pourrez pas analyser (((((((((((((((( x ))))))))))))))))). En réalité, les piles peuvent être beaucoup plus grandes et la complexité grammaticale du code réel est assez limitée. Certainement si ce code doit être lisible par l'homme.
MSalters
4

Vous ne devriez pas appeler l'analyse syntaxique en voyant callSomething()(je suppose que vous vouliez dire callSomethingplutôt que doSomething). La différence entre aet callSomethingest que l'un est une définition de méthode tandis que l'autre est un appel de méthode.

Lorsque vous voyez une nouvelle définition, vous voudrez faire des vérifications pour vous assurer que vous pouvez ajouter cette définition, donc:

  • Vérifier si la fonction n'existe pas déjà avec la même signature
  • Assurez-vous que la déclaration de méthode est effectuée dans la portée appropriée (c'est-à-dire que les méthodes peuvent être déclarées à l'intérieur d'autres déclarations de méthode?)

En supposant que ces vérifications réussissent, vous pouvez l'ajouter à votre carte et commencer à vérifier le contenu de cette méthode.

Lorsque vous trouvez un appel de méthode comme callSomething(), vous devez effectuer les vérifications suivantes:

  • callSomethingExiste- t- il sur votre carte?
  • Est-il correctement appelé (le nombre d'arguments correspond à la signature que vous avez trouvée)?
  • Les arguments sont-ils valides (si des noms de variables sont utilisés, sont-ils déclarés? Sont-ils accessibles à cette portée?)?
  • Est-ce que callSomething peut être appelé d'où vous êtes (est-ce privé, public, protégé?)?

Si cela vous callSomething()convient, à ce stade, ce que vous voulez faire dépend vraiment de la façon dont vous souhaitez l'aborder. À strictement parler, une fois que vous savez qu'un tel appel est correct à ce stade, vous ne pouvez enregistrer que le nom de la méthode et les arguments sans entrer dans les détails. Lorsque vous exécutez votre programme, vous invoquerez la méthode avec les arguments que vous devriez avoir au moment de l'exécution.

Si vous voulez aller plus loin, vous pouvez enregistrer non seulement la chaîne mais un lien vers la méthode actuelle. Ce serait plus efficace, mais si vous devez gérer la mémoire, cela peut devenir déroutant. Je vous recommanderais simplement de conserver la chaîne au début. Plus tard, vous pouvez essayer d'optimiser.

Notez que tout cela suppose que vous avez lexxed votre programme, ce qui signifie que vous avez reconnu tous les jetons de votre programme et que vous savez ce qu'ils sont . Cela ne veut pas dire que vous savez s'ils ont encore du sens ensemble, ce qui est la phase d'analyse. Si vous ne savez pas encore ce que sont les jetons, je vous suggère de vous concentrer d'abord sur l'obtention de ces informations en premier.

J'espère que ça aide! Bienvenue chez Programmers SE!

Neil
la source
2

En lisant votre message, j'ai remarqué deux questions dans votre question. Le plus important est de savoir comment analyser. Il existe plusieurs types de parseurs (par exemple analyseur de descente récursive , LR Parsers , Packrat parseurs ) et générateurs d'analyseur (par exemple GNU bison , ANTLR ) vous pouvez utiliser pour parcourir un programme textuel « récursive » donné une grammaire (explicite ou implicite).

La deuxième question concerne le format de stockage des fonctions. Lorsque vous ne faites pas de traduction dirigée par la syntaxe , vous créez une représentation intermédiaire de votre programme, qui peut être une arborescence de syntaxe abstraite ou un langage intermédiaire personnalisé, afin de poursuivre le traitement avec lui (compiler, transformer, exécuter, écrire sur un fichier, etc.).

Thiago Silva
la source
1

D'un point de vue générique, la définition d'une fonction n'est guère plus qu'une étiquette, ou un signet, dans le code. La plupart des autres opérateurs de boucle, de portée et conditionnels sont similaires; ce sont des remplaçants pour une commande de base "jump" ou "goto" dans les niveaux d'abstraction inférieurs. Un appel de fonction se résume essentiellement aux commandes informatiques de bas niveau suivantes:

  • Concaténer les données de tous les paramètres, plus un pointeur vers l'instruction suivante de la fonction actuelle, dans une structure connue sous le nom de "trame de pile d'appel".
  • Poussez ce cadre sur la pile d'appels.
  • Aller à l'offset mémoire de la première ligne du code de la fonction.

Une déclaration "retour" ou similaire fera alors ce qui suit:

  • Chargez la valeur à renvoyer dans un registre.
  • Chargez le pointeur de l'appelant dans un registre.
  • Pop le cadre de pile actuel.
  • Accédez au pointeur de l'appelant.

Les fonctions ne sont donc que des abstractions dans une spécification de langage de niveau supérieur, qui permettent aux humains d'organiser le code de manière plus facile à gérer et intuitive. Lorsqu'elles sont compilées dans un langage assembleur ou intermédiaire (JIL, MSIL, ILX), et définitivement lorsqu'elles sont rendues sous forme de code machine, presque toutes ces abstractions disparaissent.

KeithS
la source