HAKUROU L'amour est dans le code

Mini interpréteur de langage Lisp like

Mini interpréteur de langage Lisp like<br>

La science des langages est un sujet passionnant, trop peut être, c'est assez chronophage de se lancer dedans, j'ai voulu via le langage PHP écrire un petit interpréteur de langage de la famille du Lisp afin de mieux développer une version plus sérieuse pour un autre projet en C++.

Le Lisp est un langage fonctionnel créé par John McCarthy au M.I.T., on le reconnait assez facilement, ses parenthèses à foison, ses S-expressions, son fonctionnel, sa grammaire ultra simplifiée en font un langage d'exception en I.A. et en parsing de langage.

Grammaire simplifiée ne veut pas dire que le langage se limite à des choses simples, tout au contraire, contrairement à d'autres languages, celui ci permet de se concenter sur l'algorythmie et non pas sur une syntaxe particulière.

 

Je me suis lancé dans l'étude de la compilation / interprétation d'un langage par passion, en effet, comment fait on pour créer un langage qui permet lui même de créer des applications ?!

J'en avais également besoin dans un projet pour lequel j'avais besoin d'un langage embarqué permettant de scripter entre autres des I.A., je me suis dit que ce serait un choix merveilleux que de partir sur la voie sur Lisp et ses accolites tel que Common Lisp et le Scheme, bien sûr je me suis heurté à un problème majeur qui m'a fait changé d'optique pour prendre un langage déjà prêt pour l'embarqué, le LUA.

Le garbage collector m'a complètement bloqué, je me retrouve à créer des closures qui capturent leurs scopes respectifs et les transmettent dans d'autres sans fin de vie, des variables déclarées dans le scope global que je ne peux supprimer par manque d'information sur son utilisation, niveau optimisation on a vu mieux, on se retrouve avec une mémoire qui gonfle au fur et à mesure de l'éxécution du script.

 

Je reprendrais certainement le projet quand j'aurais appris ce qui me manque vis à vis de la gestion des symbols en mémoire mais en attendant, j'ai codé une version très simplifiée en PHP permettant de se faire un peu plaisir.

Le parseur de mini Lisp permet donc de parser une version simplifiée de Lisp/Scheme, elle ne prend pas en compte des choses comme les listes, les paires, les macros, les closures mais constitue une base pour se faire la main.

 

Pour lancer le parseur, il suffit de créer un fichier, disposer d'un autoload acceptant les namespaces et écrire le code suivant:

$ml = new \library\ml\MiniLisp();
$ml->parseFile('NomVersLeFichierAParser.lsp');

 

On peut donc tester des expressions simples comme:

(display "hello,world!")

Qui affichera "hello,world! à l'écran.

 

Création d'une variable pour l'afficher ensuite:

(define maChaine "hello world !")
(display maChaine)

 

Création d'une fonction:

(define toto (lambda () 
  (display "good job")))

(toto)

 

Création d'une fonction retournant une fonction:

(define mf 
  (lambda () 
  
    (display "in function")
  
    (lambda ()
      (newline) 
      (display "coucou"))))

(define toto (mf))
(toto) ;; éxécution de la fonction retournée
(newline)
((mf)) ;; éxécution de la fonction retournée par "mf"

 

Quelques calculs:

((lambda (x y) (display (+ x y))) 1 2)

 

Assignation de mots clés du langage à des simples variables:

(define function lambda)
(define alert (function (str) (display str)))
(alert "hello,world!")

 

Redéfinition des fonctions primitives du langage:

(define + (lambda (a b) (- a b)))
(display (+ 8 7))

Pour les fanatiques du Scheme, effectivement une redéfinition utiliserait set! et non défine, comme dit c'est une simplification mais rien n'empêche de l'implémenter.

 

Le code du parseur est, je l'espère, assez simple pour permettre l'implémentation de nouvelles fonctionnalités permettant d'agrandir les possibilités du mini Lisp utilisé.
Le parseur utilise les automates finis déterministes afin de lexicaliser le code, l'analyse syntaxique créé un AST qui est automatiquement évalué à la volé, ce qui fait qu'il n'y a pas d'analyse sémantique mais il est possible de rajouter cette étape. Il y a la table des symboles qui stocke toutes les variables utilisés ainsi que les fonctions créée, et supprime automatiquement les éléments périmés via un processus de pile (Stack); un simili système de registre est là pour y stocker les valeurs réelles des symboles.

Le parseur est perfectible mais il est d'une bonne source d'enrichissement dans la compréhension du processus d'évaluation d'un langage.

Les sources peuvent être trouvées sur github https://github.com/hakurou/mini-lisp.