J'ai implémenté un compilateur qui convertit Lisp en C (parfois appelé un transpiler, mais ci-après appelé un compilateur) dans Go.
Les livrables sont disponibles sur PLC.
Dans cet article, j'ai résumé le processus d'implémentation d'un compilateur Lisp qui ne gère que des entiers et de pouvoir calculer les nombres de Fibonacci.
** Clause de non-responsabilité ** J'ai essayé de le faire avec Go, mais Go n'apparaît pas du tout dans l'histoire principale.
Ce n'est pas difficile de faire un simple compilateur
Il semble difficile de créer votre propre compilateur, mais si ce n'est pas si difficile, vous le pouvez peut-être.
Cependant, il est trop imprudent de créer un compilateur même si je ne suis pas familier avec le langage C lui-même.
Y a-t-il un langage qui semble moins difficile?
Donc Lisp.
C'est plein de parenthèses, mais c'est facile à analyser.
De plus, les éléments minimaux requis
Tout ce dont vous avez besoin est ceci. Seulement neuf. C'est merveilleux de pouvoir saisir l'image dans son ensemble. Ce n'est pas suffisant pour le débogage, ajoutons donc print et progn.
Maintenant, décidons du format de sortie.
8cc recrache l'assemblage, mais Human Resource Machine Je n'ai que les connaissances pour jouer, il semble donc préférable d'arrêter.
Considérez LLVM IR comme un candidat qui semble être plus gentil que l'assemblage. Il est difficile de sauvegarder les résultats d'exécution un par un, mais il semble qu'il existe également une structure.
J'ai essayé d'implémenter l'impression et c'est fait. Cela peut être possible.
Juste au cas où, j'essaierai également la sortie C plus douce.
Quand je l'ai essayé, c'était extrêmement pratique et la quantité de code était inférieure à la moitié de la sortie LLVM IR. Je n'ai pas beaucoup de force Implémentons-le avec la sortie C pour le moment, et disons que la sortie IR est un problème de développement (pas fait ici).
Tout d'abord, essayez de compiler à la main pour savoir s'il y a des problèmes avec la politique d'implémentation ou non, puis intégrez-la dans l'implémentation du compilateur.
En prenant print comme exemple, le code Lisp d'entrée est
(print 1 2 3)
Ensuite, le code C de sortie est
#include<stdio.h>
int main(void) {
printf("%d %d %d\n", 1, 2, 3);
}
Ce sera. Il n'y a aucun problème avec la sortie du modèle sauf pour la 4ème ligne, donc il n'y a rien à penser.
La clé de l'implémentation de print est d'organiser les spécifications de format en fonction des arguments, afin que vous puissiez l'implémenter rapidement.
Cela seul manque manifestement de fonctionnalités, alors créons quelque chose comme print après avoir fait quelque chose.
Par exemple, si vous «imprimez» le résultat de «1 + 2»,
(print (+ 1 2) (+ 3 4 5))
Quand ceci est compilé, le code excluant la partie de modèle est
int plus_0 = 1 + 2;
int plus_1 = 3 + 4 + 5;
printf("%d %d\n", plus_0, plus_1);
Mettre en œuvre pour que Enregistrez les résultats des calculs un par un et transmettez les résultats enregistrés à imprimer.
Au fait, j'implémente «+», et je l'implémente simplement en évaluant tous les arguments et en concaténant avec «+».
Cela entraînera la déclaration d'un grand nombre de variables dans la fonction principale, laissant la mémoire réservée. À l'origine, ce serait un endroit pour mettre en œuvre GC, mais je laisserai cela comme une question de développement également.
Maintenant que l'implémentation de «print» est terminée, passez à l'implémentation de «progn».
Cependant, puisque les arguments ne sont évalués que dans l'ordre, il n'y a pas de difficulté particulière et la valeur d'évaluation finale est la valeur de retour.
Maintenant que nous pouvons exécuter plusieurs processus, définissons define et gérons les variables.
(progn
(define a 1)
(print a))
int a = 1;
printf("%d\n", a);
Actuellement, nous ne traitons que des entiers, il n'y a donc pas de problème si vous êtes capable de définir des variables entières. Dans les coulisses, enregistrez la vérification de déclaration de variable afin qu'elle puisse être vérifiée par le traitement interne du compilateur.
Maintenant que nous pouvons définir des variables, nous allons passer à l'implémentation de lambda afin de pouvoir également définir des fonctions.
Tout d'abord, implémentons l'exécution immédiate de lambda avant de considérer la combinaison avec define.
(print ((lambda (x) (+ x 1)) 2))
int lambda_0(int *args) {
int x = args[0];
int add_0 = x + 1;
return add_0;
}
int main(void) {
int lambda_0_args[] = {2};
printf("%d\n", lambda_0(lambda_0_args));
}
Si vous utilisez lambda, nous le définirons comme une fonction séquentielle. Je ne veux pas considérer le nombre d'arguments, donc
Nous décidons de le recevoir sous forme de tableau et de le réaffecter aux variables comme il convient dans la fonction. Où vous appelez une fonction
Assurez-vous de stocker les arguments dans un tableau à l'avance.
Maintenant que nous avons lambda, implémentons la définition de la fonction en combinaison avec define.
Cependant, le simple fait d'assigner la fonction définie dans lambda au pointeur de fonction le fait ressembler à ça.
(define add1 (lambda (x) (+ x 1)))
int (*add1)(int*);
int lambda_0(int *args) {
int x = args[0];
int add_0 = x + 1;
return add_0;
}
int main(void) {
add1 = lambda_0;
}
Ensuite, je veux activer le branchement conditionnel, donc je vais implémenter ʻeq et ʻif. Ce que vous faites avec ʻeqest similaire à+, concaténez simplement avec &&au lieu de+`.
(eq 1 2 3)
bool eq_0 = 1==2 && 1==3;
Utilisez cette ʻeq pour commencer à implémenter ʻif.
(if (eq 1 2) 10 20)
int if_0;
int eq_0 = 1==2;
if (eq_0) {
if_0 = 10;
} else {
if_0 = 20;
}
Même si vous le convertissez en C ʻif, cela fonctionnera comme ça. Si vous ajoutez - ainsi que +` ici, vous pouvez calculer le nombre de Fibonacci de manière récursive.
Quand je l'essaye,
(progn
(define fib (lambda (n)
(if (eq n 0)
0
(if (eq n 1)
1
(+ (fib (- n 1)) (fib (- n 2)))))))
(print (fib 10)))
#include<stdio.h>
int (*fib)(int*);
int lambda_1(int *args){
int n = args[0];
int if_1;
int eq_2 = n == 0;
if (eq_2) {
if_1 = 0;
} else {
int if_3;
int eq_4 = n == 1;
if (eq_4) {
if_3 = 1;
} else {
int minus_5 = n;
minus_5 -= 1;
int fib_args_6[] = {
minus_5
};
int minus_7 = n;
minus_7 -= 2;
int fib_args_8[] = {
minus_7
};
int plus_9 = 0;
plus_9 += fib(fib_args_6);
plus_9 += fib(fib_args_8);
if_3 = plus_9;
}
if_1 = if_3;
}
return if_1;
}
int main(void) {
fib = lambda_1;
int fib_args_2[] = {
10
};
printf("%d\n" , fib(fib_args_2));
}
Ce type de code redondant est généré, mais lorsque vous l'exécutez réellement, il le calculera correctement.
J'ai fait un compilateur (transpiler) qui convertit lisp en C d'une manière simple.
Ce qui a été mis en œuvre dans le processus jusqu'à présent
https://github.com/kawakami-o3/PLC/tree/7d825a5ccbab45919c701ebb66cd8d2409c9f45d
Vous pouvez l'obtenir.
Quoi qu'il en soit, dans le but de bouger, je l'ai conçu et implémenté pour que la difficulté de montage soit la plus faible possible. J'ai pu l'implémenter au point où je pouvais calculer le nombre de Fibonacci avec presque aucune pierre d'achoppement.
Pour résumer les quelques points d'achoppement,
if
--Dans l'implémentation initiale, si elle était implémentée en tant que fonction, et après avoir évalué tous les arguments, la valeur de retour était décidée.
--Fonction rétroactive
«Je vérifiais ʻundefined, mais j'ai aussi eu la promesse que le timing d'affectation de define et le timing de définition de lambda` seraient mélangés et qu'une erreur serait lancée.Cette fois, j'ai implémenté Lisp qui ne gère que des entiers, et même s'il s'agissait de Lisp, je ne pouvais pas faire le traitement des listes correctement.
La prochaine fois, nous examinerons la structure des données afin que le traitement de la liste puisse être effectué, compilerons le code lisp de ʻeval, et implémenterons un compilateur qui peut exécuter ʻeval au moment de l'exécution.
Merci pour la lecture.
Ici, nous aborderons les éléments restants «atome», «quote», «car», «cdr», «cons».
La raison pour laquelle je ne l'ai pas traité dans la partie principale est que la valeur de retour est ʻintdans lelambda` implémenté dans cet article.
C'est parce qu'il y avait une erreur de conception fatale qui ne pouvait pas être utilisée avec «cdr» ou «cons».
Cependant, il est également désagréable de passer à l'objectif suivant sans le faire du tout, alors je l'ai mis en œuvre d'une manière moelleuse, comme mentionné ici.
Pour ʻatom, j'ai essayé d'évaluer l'argument au moment de la compilation et je l'ai initialisé avec 0ou1` selon qu'il s'agit d'un entier ou non.
Dans quote, les arguments sont limités aux entiers et aux listes d'entiers uniquement.
Si c'est un entier
(quote 1)
int quote_0 = 1;
S'il s'agit d'une liste d'entiers, elle sera convertie en tableau d'entiers.
(quote (1 2 3))
int quote_0[] = {1,2,3};
Pour car, nous l'avons implémenté en interne pour renvoyer la première valeur du tableau d'entiers, tout comme nous avons converti la liste d'entiers en un tableau d'entiers avec quote.
cdr a implémenté l'implémentation de placer le deuxième élément et les suivants dans le tableau nouvellement défini pour la liste d'entiers passée en argument.
Par contre, j'ai également créé un nouveau tableau pour insérer des éléments. J'ai décidé de travailler sur des listes imbriquées, etc. dans l'étape suivante, et ici je ne traiterai que des listes d'entiers à une dimension.
Ce qui précède est l'implémentation dans le compilateur couvert dans cet article.
Recommended Posts