Le langage de programmation Scheme est reconnu pour son puissant
système de macro-transformations. La représentation
du code source d'un programme, sous forme de données manipulables
par le langage,
permet aux programmeurs de modifier directement
l'arbre de syntaxe abstraite sous-jacent.
Les macro-transformations
utilisent une syntaxe similaire aux procédures régulières mais,
elles définissent plutôt des procédures à exécuter
lors de la phase de compilation.
Ces procédures retournent une représentation sous
forme d'arbre de syntaxe abstraite qui devra être substitué
à l'emplacement de l'appel du transformateur. Les procédures
exécutées durant la phase de compilation profitent
de la même puissance que celles exécutées durant de la phase d'évaluation.
Avec ce genre de système de macro-transformations,
un programmeur peut créer des règles de syntaxe spécialisées
sans aucun coût additionnel en performance:
ces extensions syntactiques
permettent l'abstraction de code sans les coûts d'exécution
habituels reliés à la création d'une fermeture sur le tas.
Cette représentation pour le code source de Scheme provient
directement du langage de programmation Lisp. Le code source
est représenté sous forme de listes manipulables
de symboles, ou bien de
listes contenants d'autres listes: une structure appelée
S-expression. Cependant, avec cette approche simpliste,
des conflits de noms peuvent apparaître.
En effet, l'association référée par un certain identifiant
est déterminée exclusivement par
le contexte lexical de celui-ci.
En déplaçant un identifiant dans l'arbre de syntaxe abstraite,
il est possible que cet identifiant se retrouve dans
un contexte lexical contenant une certaine association pour un identifiant du même nom.
Dans de tels cas,
l'identifiant déplacé pourrait ne plus référer à l'association
attendue, puisque cette seconde
association pourrait avoir prévalence sur
la première. L'assurance de transparence référentielle est alors perdue.
En conséquence, le choix de nom pour les identifiants
vient maintenant influencer directement
le comportement du programme,
générant des erreurs difficiles à comprendre.
Les conflits de noms
peuvent être corrigés manuellement dans le code en utilisant,
par exemple, des noms d'identifiants uniques.
La préservation automatique de la transparence référentielle
se nomme hygiène, une notion qui a été beaucoup
étudiée dans le contexte
des langages de la famille Lisp.
La dernière version du Scheme revised report, utilisée
comme spécification pour le langage, étend ce dernier
avec un support pour les macro-transformations hygiéniques.
Jusqu'à maintenant,
l'implémentation Gambit de Scheme ne fournissait
pas de tel système à sa base. Comme contribution, nous
avons ré-implémenter le système de macro de Gambit pour
supporter les macro-transformations hygiéniques au plus bas niveau
de l'implémentation. L'algorithme choisi se base sur l'algorithme
set of scopes implémenté dans le langage Racket et créé par Matthew Flatt.
Le langage Racket s'est grandement inspiré
du langage Scheme mais, diverge
sur plusieurs fonctionnalités importantes. L'une de
ces différences est le puissant système de macro-transformation
sur lequel Racket base la majorité de ses primitives.
Dans ce contexte, l'algorithme a donc été testé
de façon robuste.
Dans cette thèse, nous donnerons un aperçu du langage
Scheme et de sa syntaxe. Nous énoncerons le problème d'hygiène
et décrirons différentes stratégies utilisées
pour le résoudre. Nous justifierons par la suite
notre choix d'algorithme et fourniront une définition
formelle. Finalement, nous présenterons une analyse
de la validité et de la performance du compilateur en
comparant la version originale de Gambit avec notre
version supportant l'hygiène. / The Scheme programming language is known for
its powerful macro system.
With Scheme source code represented as actual Scheme data,
macro transformations
allow the programmer, using that data, to act directly on the
underlying abstract syntax tree.
Macro transformations use a similar syntax to
regular procedures but, they define procedures
meant to be executed at compile time.
Those procedures return an abstract syntax tree representation
to be substituted at the transformer's call location.
Procedures executed at compile-time use the same
language power as run-time procedures.
With the macro system,
the programmer can create specialized
syntax rules without additional performance costs.
This also allows for code abstractions
without the expected run-time cost of closure creations.
Scheme's representation of source code using values
inherits that virtue from the Lisp programming language.
Source code is represented as a list of symbols, or lists
of other lists: a structure coined S-expressions.
However, with this simplistic approach,
accidental name clashes can occur.
The binding to which an identifier refers to
is determined by the lexical context of that identifier.
By moving an identifier around in the abstract syntax tree,
it can be caught within the lexical context of another binding definition with the same name.
This can cause unexpected behavior for programmers
as the choice of names can create substantial changes
in the program.
Accidental name clashes can be manually fixed in the code,
using name obfuscation, for instance.
However, the programmer becomes responsible
for the program's safety.
The automatic preservation of referential transparency
is called hygiene and was
thoroughly studied in the context
of lambda calculus and Lisp-like languages.
The latest Scheme revised report, used as a specification for the
language, extend the language with hygienic macro
transformations.
Up to this point, the Gambit Scheme implementation
wasn't providing a built-in hygienic macro system.
As a contribution, we re-implemented Gambit's
macro system to support hygienic transformations
at its core.
The algorithm we chose is
based on the set of scopes algorithm, implemented in the
Racket language by Matthew Flatt.
The Racket language is heavily based on Scheme but,
diverges on some core features.
One key aspect of the Racket language is
its extensive hygienic syntactic macro system, on
which most core features are built on:
the algorithm
was robustly tested in that context.
In this thesis, we will give an overview of the Scheme language
and its syntax. We will state the hygiene problem and describe
different strategies used to enforce hygiene automatically.
Our algorithmic
choice is then justified and formalized. Finally, we
present the original Gambit macro system and explain
the changes required. We also provide a validity and performance
analysis, comparing the original Gambit implementation to
our new system.
| Identifer | oai:union.ndltd.org:umontreal.ca/oai:papyrus.bib.umontreal.ca:1866/28709 |
| Date | 07 1900 |
| Creators | Doucet, Antoine |
| Contributors | Feeley, Marc |
| Source Sets | Université de Montréal |
| Language | English |
| Detected Language | French |
| Type | thesis, thèse |
| Format | application/pdf |
Page generated in 0.0036 seconds