Compilation de Scheme

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.

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 ?

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.

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.

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é.

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).

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.