Compilation de Scheme

L’auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour les copains/copines,

je travaille actuellement sur une projet de compilateur pour un langage très fortement inspiré de Scheme écrit en C89 (pour le plaisir/pleurer un bon coup). Autant j’ai une idée assez précise de comment tout va se goupiller, autant je suis assez perdu concernant l’expansion des macros et de la "fonction" eval.

En effet, même si je remplace un appel à une macro par son corps (moyennant des ajustements avec les quotations), je ne vois pas comment je peux compiler un appel à eval puisque celle-ci peut nécessiter des informations disponibles uniquement au runtime. Par exemple, dans le code suivant, mes deux premières lignes de codes devraient être équivalentes, mais à cause du eval, je devrais connaître la valeur de f à la compilation, ce qui n’est pas garanti, comme montré dans le bout de code juste après.

1
2
3
4
5
6
(eval (list 'f 5))
(f 5)

;; Certes personne ne devrait écrire ça, mais ça illustre bien ce que je veux dire.
(let ((function-name (readline)))
  (eval (list (string->symbol function-name) 5)))

J’aurais donc voulu savoir comment régler ce problème, s’il y a une technique bien connue/définie pour compiler cette fonctionnalité du Scheme.

Par ailleurs, question annexe, j’ai cherché d’autres compilateurs de Scheme écrits en C pour voir comment d’autres font et je ne tombe que sur des compilateurs de "mini-Scheme" servant à bootstrap le vrai compilateur. Est-ce finalement obligé ou est-ce ainsi parce que le Scheme est quand-même bien plus agréable que le C écrire un compilateur ? Si, par hasard, vous connaissez un compilateur de Scheme écrit en C (uniquement en C) qui puisse me servir d’inspiration, il serait gentil de me mettre dans le coup :)

Merci beaucoup pour votre lecture et de vos éventuelles réponses.
Lalla.

+0 -0
Auteur du sujet

Je vois ! Donc typiquement il faudrait que je fasse une bibliothèque de mon compilateur (et un programme qui l’utilise pour compiler des fichiers, ça tombe sous le sens) et que je lie chaque programme contenant un eval à celui-ci ?

+0 -0

Cette réponse a aidé l’auteur du sujet

Salut.

Un des problèmes du eval est la gestion de l’environnement. D’abord, il est bon de noter que la norme R5RS ne permet pas au eval d’accéder à l’environnement local. Seul l’environnement global peut être lu (ce post explique pourquoi). Donc le code que tu montres en exemple est invalide (pour R5R5. Je ne sais pas ce que disent les autres normes, mais c’est surement pareil).

Comme dit Saroupille, tu dois utiliser un système externe pour implémenter le eval. Tu peux faire appel à un autre compilateur, mais ça peut être difficile parce que tu dois lui transmettre ton environnement global (ça fait un travail, et une dépendance supplémentaire).

L’autre solution est d’embarquer ton propre compilateur/interprète, ça simplifie la gestion de l’environnement. Après tout, c’est ton code donc tu sais comment l’environnement est représenté.

Une autre chose intéressante est que tu peux embarquer ce système uniquement si le programme que tu compiles utilise eval. Dans tous les autres cas, pas besoin de l’intégrer, donc le code généré reste léger.

Pour ta seconde question, non tu peux très bien faire un bootstrap sans utiliser d’autre compilateur ("mini-Scheme" comme tu les appelles). Dans ce cas tu as deux solutions:

  1. Tu conserves et distribues un build de l’ancienne version de ton compilateur qui est utilisé pour construire l’actuelle. Mais conserver un build complet est assez lourd, et si tu génères de l’assembleur (donc le build est en binaire), c’est pas très portable.
  2. Tu écris ton compilateur dans un Scheme standard, et tu utilises un autre compilateur pour construire le tiens. Puis tu utilises la sortie pour compiler à nouveau ton compilateur. Le problème cette fois est que tu as une dépendance externe (ton compilateur n’est plus auto-suffisant).

Donc l’autre solution est d’utiliser un autre petit compilateur qui est très primitif, et pas optimisé (quelques centaines de lignes de code). Tu peux même éviter d’utiliser un GC, eval, les continuations, etc… Avec ce petit compilateur, tu compiles une version non efficace de ton vrai compilateur. Puis tu utilises la sortie pour compiler à nouveau ton compilateur pour avoir une version, cette fois, efficace. Et là, tu deviens vraiment auto-suffisant. :magicien:

Donc non tu n’est pas obligé d’utiliser un second petit compilateur, mais c’est bien plus satisfaisant :D

Édité par kelepoc

+0 -0
Auteur du sujet

Vis à vis du bootstrap, ce qui m’intéresse, c’est pas vraiment le procédé. Je sais ce que c’est et comment m’y prendre. En fait, ce qui m’interpèle c’est que lors que je recherche une implémentation en C d’un langage dérivé de Scheme (ou même d’un Lisp quelconque), je ne trouve jamais un compilateur écrit purement en C et basta. Je finis toujours par avoir un compilateur minimal en C et derrière le vrai compilateur écrit en Scheme. Suis-je le seul masochiste à vouloir tout faire en C ? Je dois dire que c’est assez perturbant, surtout que le C est l’un des langages les plus utilisés au monde, il n’y a pas de raison que ça n’existe pas du tout.

D’accord, je comprends mieux le pourquoi du comment, merci beaucoup. :)

+0 -0

Suis-je le seul masochiste à vouloir tout faire en C ?

Lalla

Beaucoup de langages essaient d’être auto-suffisant. Et j’ai souvent lu que Scheme était de bons langages pour écrire des compilateurs. Seuls les langages interprétés (Python, ruby, PHP) restent généralement en C-like.

+0 -0

Je dois dire que c’est assez perturbant, surtout que le C est l’un des langages les plus utilisés au monde, il n’y a pas de raison que ça n’existe pas du tout.

Bof, en 2017 c’est utilisé pour de l’embarqué parce qu’il n’y a pas le choix ou pour des raisons historiques. Pour écrire des compilateurs, c’est particulièrement inadapté.

+0 -0
Auteur du sujet

Oui évidemment, le C n’est pas adapté à l’écriture de compilateurs, on est d’accord. Mais puisque ce langage est toujours enseigné comme langage de référence j’aurais pensé qu’à un moment où à un autre quelqu’un d’autre aurait écrit un compilateur de Scheme en C. Visiblement ça n’est pas le cas et bien que je sois d’accord sur l’aspect pratique, je pense qu’il s’agit d’un challenge intéressant (d’autant plus que bon nombre de compilateurs/VM/interpréteurs pour d’autres langages sont écrits en C).

+0 -0

ce langage est toujours enseigné comme langage de référence

C’est toujours enseigné parce que ça reste difficilement contournable, mais comme « référence », bof : le langage généraliste à la mode, c’est Java ou Python maintenant. Les formations où le C prend cette place sont soit des formations assez orientées électronique ou embarqué, soit des formations où les gens qui décident des programmes ne sont pas informaticiens et ne connaissent de toute façon rien d’autre que le (mauvais) « C/C++ ».

je pense qu’il s’agit d’un challenge intéressant

Pas tellement, en fait. Si c’est pour faire du C, il y a un tas de choses plus intéressantes et instructives, et si c’est pour apprendre la compilation, il y a plein d’autres langages qui rendent la tâche plus intéressante. Devoir se concentrer sur la gestion de la mémoire alors qu’on cherche à écrire un compilateur, donc un programme qui effectue des opérations complexes sur des données riches, c’est contre-productif. Alors bien sûr, ça reste possible, mais ce serait une erreur de penser que « c’est plus dur donc j’apprends plus de choses » à la « ce qui ne me tue pas me rend plus fort ».

(d’autant plus que bon nombre de compilateurs/VM/interpréteurs pour d’autres langages sont écrits en C).

Les VM, c’est possible, pour deux raisons : d’une part, le format des entrées est en général particulièrement simple (parce que tout le travail de transformation depuis un langage expressif a été fait par la compilation), d’autre part, c’est un programme qui cherche en général explicitement des hautes performances, et pour lequel on veut souvent toucher un peu aux détails de l’architecture qui exécutera le code. Le C n’est probablement pas le langage le plus adapté pour autant, mais c’est un choix qui se comprend déjà plus. Pour les compilateurs, à part les compilateurs C (parce qu’on veut être auto-suffisant), c’est de plus en plus rare.

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte