#Vaλisp 5 : finitions, performances et perspectivesCopier le lien

Dernier jalon pour Vaλisp : améliorer l’expérience développeur, optimiser les performances et ouvrir la voie aux évolutions. Le but n’est plus d’ajouter une fonctionnalité isolée mais de consolider l’ensemble : appels en position terminale sans débordement de pile, REPL confortable, bibliothèque standard en Lisp lui-même, et documentation d’architecture à jour.

#1. Optimiser l’évaluation : les appels terminauxCopier le lien

Un appel est en position terminale quand son résultat est directement le résultat de la fonction : dans (if c a b), les branches sont en position terminale. Un évaluateur récursif naïf empile un cadre C par appel Lisp : (fact 100000) fait cent mille appels eval imbriqués et fait déborder la pile du programme C, ligne de code qui n’existe pas dans le programme Lisp.

La solution est une boucle plutôt qu’une récursion dans eval : quand on reconnaît un appel terminal, au lieu d’appeler eval récursivement, on réaffecte expr et env puis on remonte au début de la fonction :

1TaggedValue eval(TaggedValue expr, Env *env, Arena *a) {2    for (;;) {3        if (is_symbol(expr)) return env_lookup(env, expr);4        if (!is_cons(expr)) return expr;5 6        /* ... formes spéciales ; pour if en position terminale : */7        expr = branche_a_prendre;   /* la branche alors ou sinon, selon la condition */8        continue;                 /* pas d'appel récursif : la pile C ne grandit pas */9 10        /* ... application : si la closure est en position terminale,11               lier les paramètres dans un cadre neuf, env = ce cadre, continue ; */12    }13}

La profondeur de pile C devient constante, quelle que soit la récursion Lisp. C’est exactement la garantie que la spécification Scheme exige des implants conformes, et la raison pour laquelle les boucles Lisp s’écrivent par récursion terminale.

Variante pragmatique si la réécriture vous résiste : augmenter la limite système (ulimit -s) dépanne pour tester, mais ne corrige rien ; la boucle est la seule vraie réponse.

Mesurer avant d’optimiser. Compilez en release puis comparez un benchmark avant/après la modification :

1make release2echo '(bench-fib 25)' | ./valisp --bench

Notez le temps affiché ; seule l’amélioration mesurée compte (et elle sera spectaculaire sur la récursion profonde : de « stack overflow » à un temps fini).

#2. Un REPL agréableCopier le lien

Quatre améliorations font passer le prototype d’essai à l’outil quotidien :

1#include <readline/readline.h>2#include <readline/history.h>3 4int repl(Env *env, Arena *a) {5    for (;;) {6        char *line = readline("va> ");7        if (!line) break;                        /* EOF (Ctrl-D) : sortie propre */8        if (*line) add_history(line);            /* historique ; lignes vides exclues */9        TaggedValue expr = parse_line(line, a);10        if (!erreur_syntaxe) {11            TaggedValue res = eval(expr, env, a);12            print_value(res);13            putchar('\n');14        }

• readline procure édition de ligne et historique ; le point de propriété est explicite : la chaîne appartient à l’appelant, un free par itération. Compilez avec -lreadline (et gardez un repl sans readline derrière une macro pour les machines qui ne l’ont pas).
• Les erreurs (syntaxe, symbole inconnu, arité) n’interrompent pas la session : elles affichent et rebouclent. Un interpréteur qui meurt à la première faute de frappe n’est pas utilisable.
• (load "fichier.val") lit et évalue un fichier : c’est le mécanisme de bibliothèque standard.
• (exit 0) quitte proprement en libérant les ressources de l’interpréteur.

#3. Une bibliothèque standard, en LispCopier le lien

Tout ce qui ne nécessite pas de primitive C s’écrit en Lisp, chargé au démarrage :

1; stdlib.val2(define (map f lst)3  (if (= lst '())4      '()5      (cons (f (car lst)) (map f (cdr lst)))))6 7(define (filter pred lst)8  (cond ((= lst '()) '())9        ((pred (car lst)) (cons (car lst) (filter pred (cdr lst))))10        (else (filter pred (cdr lst)))))11 12(define (reduce f init lst)13  (if (= lst '())14      init

Notez define avec la forme sucrée (define (nom params) corps) : quelques lignes côté parseur, un confort immense. reduce est en position terminale : il bénéficie de l’optimisation de la section 1.

1./valisp2va> (load "stdlib.val")3va> (reduce + 0 (map (lambda (x) (* x x)) '(1 2 3 4)))430

#4. Ouvrir la voieCopier le lien

Trois extensions naturelles, classées par effort croissant :

• Bytecode et machine virtuelle : compiler les s-expressions en tableau d’instructions, exécuter dans une boucle. Gain typique d’un facteur 2 à 10, et c’est le sujet du module compilation.
• Structures persistantes : vecteurs et tables dans l’arène, avec partage structurel.
• FFI : appeler des fonctions C depuis Lisp. Délicat : il faut typer les conversions et sécuriser les frontières ; réservez-le en projet d’extension.

#Atelier : jalon 5Copier le lien

1. Réécrivez eval avec la boucle d’appels terminaux. Test : (define (compte n) (if (= n 0) 'fini (compte (- n 1)))) puis (compte 1000000) doit afficher fini et non pas planter.
2. Intégrez readline et l’historique, gestion d’erreur par session, (load ...) et (exit 0).
3. Écrivez stdlib.val avec map, filter, reduce et vérifiez le jalon ci-dessus (somme des carrés = 30).
4. Rédigez ARCHITECTURE.md : schéma de l’arène et de la liste libre, contrat des racines du GC, liste des primitives, façon de lancer les tests. Ce document est votre preuve de maîtrise : s’il est clair, le projet est compris.

1cc -std=c17 -Wall -Wextra -Wpedantic -g -fsanitize=address,undefined *.c -lreadline -o valisp2./valisp < session-jalon5.txt

1va> fini2va> 303va> bye