LispKit
From OFSET Wiki
Contents |
[edit] Une boîte à outils pour construire des interpréteurs LISP
LispKit est, comme son nom l'indique, un kit pour fabriquer du LISP.
La syntaxe minimaliste de LISP permet d'implémenter un interpréteur très facilement. En fait, c'est tellement facile qu'en utilisant Smalltalk comme langage hôte, il n'est même pas nécessaire de passer par une analyse syntactique, ni a fortiori par un compilateur de compilateur. Smalltalk peut exécuter du code LISP directement !
LispKit propose donc un interpréteur minimal, LispKernel, que ses sous-classes spécialisent soit en enrichissant sa bibliothèque de primitives, soit en modifiant ses stratégies d'évaluation.
Le panneau supérieur permet d'évaluer de larges expressions, le panneau inférieur est le REPL
La fenêtre d'exploration (en gris) a été créée par la dernière commande visible
[edit] ULisp, un Scheme au standard R4RS
Le produit le plus spectaculaire de LispKit est une implémentation complète de Scheme sous Squeak.
C'est la sous-classe ULisp de LispKernel. L'interface graphique peut être invoquée par la commande ULisp openNew.
[edit] Statut actuel
ULisp respecte le standard R4RS, à de mineures exceptions près (notamment le protocole nombres exacts/inexacts).
Ceci dit, il subsiste quelques bugs...
[edit] SScheme
SScheme est une sous-classe de ULisp qui y ajoute le support des macros
hygiéniques (basé sur les 'macros-that-work de SLIB).
SScheme est encore très expérimental.
[edit] Bibliothèques et applications compatibles
Afin de tester et d'étendre ULisp, les contributions suivantes font partie de la distribution LispKit:
[edit] SLIB
SLIB est une bibliothèque Scheme standard, par Aubrey Jaffer.
[edit] JACAL
JACAL est une application de calcul symbolique, basée sur SLIB, toujours par Aubrey Jaffer.
Pour lancer JACAL (version 1b7) sous ULisp, faire (require-library 'jacal)
[edit] Tiny-CLOS
Tiny-CLOS est un système d'objects pour Scheme reprenant les principes de CLOS, le système d'objects de Common Lisp.
(require-library 'tiny-clos)
[edit] Schelog
Schelog, par Dorai Sitaram, est une extension de Scheme similaire à Prolog.
(require-library 'schelog)
[edit] Pregexp
Pregexp, toujours par Dorai Sitaram, implémente les expressions régulières de type Perl en Scheme.
(require-library 'pregexp)
[edit] miniKANREN
miniKANREN est un système de programmation en logique déclarative.
Pour le tester, faire
SScheme openNew
(car on a besoin des macros hygiéniques), puis
(require-library 'mini-kanren)
[edit] Partis pris d'implémentation
L'originalité de LispKit réside dans certains partis pris quant à sa structure et son implémentation, qui sont illustrés dans cette section.
[edit] Transparence
Comme je l'ai dis dans l'introduction, Smalltalk peut exécuter du code LISP directement !
En effet, considérons les expressions suivantes:
#(+ 1 1) 1 perform: #+ withArguments: #(1) #(copyFrom:to: 'schtroumpf' 5 8) 'schtroumpf' perform: #copyFrom:to: withArguments: #(5 8)
On voit qu'un interpréteur ultra minimaliste pourrait s'écrire
SystemDictionary>>interpret: anArray
anArray isArray ifFalse: [^ anArray].
^ (Smalltalk interpret: anArray second) perform: anArray first
withArguments: ((anArray allButFirst: 2)
collect: [:ea | Smalltalk interpret: ea ])
Quoi de plus simple ?
Smalltalk interpret: #(copyFrom:to: 'schtroumpf' (asInteger (sqrt 25)) (+ 2 (+ 2 (+ 2 2))))
...ça marche !
Bien entendu, on ne peut pas en rester là. Cependant, il est remarquable que, fondamentalement, oui, on en reste là. Et notamment, il n'est nul besoin de parseur. C'est ainsi que l'on peut écrire:
ELisp new top:
#(progn
(defun fib (x)
(if (< x 2) x (+ (fib (- x 1)) (fib (- x 2)))))
(fib 10)).
L'aspect transparent de LispKit vient donc du fait que du code LISP peut être écrit directement sous forme de tableau en Smalltalk.
[edit] Simplicité
Les algorithmes de LispKit ne sont pas étudiés pour être malins ni particulièrement performants. Plutôt, ils cherchent à réifier de la façon la plus directe les concepts fondamentaux de Lisp.
Par exemple les listes sont réellement formées de cellules cons (classe ConsCell). Ou encore, les continuations de ULisp sont simplement des continuations de Squeak (instances de la class Continuation empruntée à Seaside), juste un peu tronquées.
[edit] Intégration
Simplicité, transparence et intégration sont des notions liées: par intégration je veux dire que la frontière entre LISP et Smalltalk est aussi poreuse qu'il est possible, ce qui est permis par les vertus de transparence et de simplicité déjà évoquées.
Par exemple, tout object qui n'est pas une cellule cons (ConsCell) est atomique au sens de LISP. De même, les valeurs booléennes de ULisp (Scheme) sont les true et false de Smalltalk, tandis que celles de LispKernelsont #t et nil.
De façon générale, et sauf exception, il n'y a pas de conversion à faire pour qu'un object Smalltalk puisse être utilisé comme une donnée LISP.
[edit] Modularité
Les structures d'un interpréteur LISP sont exposées de façon modulaire par LispKernel, ce qui permet de modifier des aspects entiers de l'interpréteur avec relativement de facilité.
C'est ainsi que, bien que LispKernel soit un Lisp-2 à variables de portée dynamique (similaire à Emacs Lisp), on peut avoir une de ses sous-classes qui est un Scheme, soit un Lisp-1 avec fermetures lexicales, et une autre qui est un Lisp-2 avec fermetures lexicales plus variables spéciales dynamique, comme Common Lisp.
[edit] Extensibilité
Il est très facile d'ajouter de nouvelles primitives aux interpréteurs. Cela revient simplement à coder une nouvelle méthode dans la classe correspondante. Il suffit ensuite de faire évaluer (update-primitives) par n'importe quel interpréteur pour que la primitive deviennent immédiatement disponible à tous les interpréteurs existants.
Exemple:
ELisp openNew puis, dans le REPL:
top> (/ 1 5) 1/5 top> (reciprocal 5) LispError: no function bound to symbol reciprocal top>
on code alors
ELisp>>reciprocal: aConsCell ^ 1 / aConsCell car
(méthode qui doit être classée dans une catégorie dont le nom commence par 'LISP-functions')
puis, de retour dans le REPL:
top> (update-primitives) t top> (reciprocal 5) 1/5 top>
ajouter une forme spéciale est tout aussi simple, il suffit de catégoriser la méthode sous 'Lisp-special forms'.
[edit] Détails d'implémentation
[edit] Lisp-1 et Lisp-2
c'est pour plus tard...
[edit] Portée lexicale, portée dynamique
c'est pour plus tard...
[edit] Primitives et formes spéciales
c'est pour plus tard...
[edit] Continuations
c'est pour plus tard...
[edit] Optimisation d'appel terminal
c'est pour plus tard...
[edit] Curiosités
[edit] Fonctions circulaires
Parce que LispKernel évalue le code LISP bêtement de cellule cons en cellule cons, il est possible de lui faire évaluer une structure circulaire, et on peut donc implémenter la fonction factorielle sans itération ni récursion ! Un simple branchement de sortie sur une boucle infinie suffit:
(defun fact (n) #1=(if (< n 1) 1 (setq n (- n 1)) (* (+ 1 n) #1#)))
... ça n'a peut-être l'air de rien, mais peu de systèmes LISP autorisent ce genre de privauté.
[edit] Fonctions auto-modifiantes
c'est pour plus tard...
[edit] Interface graphique et éditeur
c'est pour plus tard...
[edit] Perspectives
c'est pour plus tard...
[edit] Limitations actuelles
c'est pour plus tard...
