Les programmeurs Lisp se vantent que Lisp est un langage puissant qui peut être construit à partir d'un très petit ensemble d'opérations primitives . Mettons cette idée en pratique en jouant au golf avec un interprète appelé dialecte tinylisp.

Spécification de la langue

Dans cette spécification, toute condition dont le résultat est décrit comme "non défini" peut faire n'importe quoi dans votre interprète: planter, échouer de manière silencieuse, produire un gobbldegook aléatoire ou fonctionner comme prévu. Une implémentation de référence dans Python 3 est disponible ici .

Syntaxe

Les jetons dans tinylisp sont (, )ou toute chaîne d'un ou plusieurs caractères ASCII imprimables, à l'exception des parenthèses ou des espaces. (C'est-à-dire les expressions rationnelles suivantes:. [()]|[^() ]+) Tout jeton constitué uniquement de chiffres est un littéral entier. (Les zéros en tête sont corrects.) Tout jeton contenant des chiffres non numériques est un symbole, même des exemples sous forme numérique 123abc, tels que 3.14, et -10. Tous les espaces (y compris au minimum les caractères ASCII 32 et 10) sont ignorés, sauf dans la mesure où ils séparent les jetons.

Un programme tinylisp consiste en une série d'expressions. Chaque expression est un entier, un symbole ou une expression s (liste). Les listes se composent de zéro ou plusieurs expressions entourées de parenthèses. Aucun séparateur n'est utilisé entre les éléments. Voici des exemples d'expressions:

4
tinylisp!!
()
(c b a)
(q ((1 2)(3 4)))

Les expressions qui ne sont pas bien formées (en particulier, qui ont des parenthèses incomparables) donnent un comportement non défini. (L'implémentation de référence ferme automatiquement les parenthèses ouvertes et arrête l'analyse sur des parents proches non appariés.)

Types de données

Les types de données de tinylisp sont des entiers, des symboles et des listes. Les fonctions intégrées et les macros peuvent également être considérées comme un type, bien que leur format de sortie ne soit pas défini. Une liste peut contenir un nombre quelconque de valeurs de tout type et peut être imbriquée de manière arbitraire et en profondeur. Les entiers doivent être pris en charge au moins de -2 ^ 31 à 2 ^ 31-1.

La liste vide - ()également appelée nil - et le nombre entier 0sont les seules valeurs considérées comme logiquement fausses; tous les autres entiers, les listes non vides, les commandes intégrées et tous les symboles sont logiquement vrais.

Évaluation

Les expressions dans un programme sont évaluées dans l'ordre et les résultats de chacune sont envoyés à stdout (plus d'informations sur le formatage de la sortie ultérieurement).

• Un littéral entier est évalué à lui-même.
• La liste vide ()s’évalue à elle-même.
• Une liste d'un ou plusieurs éléments évalue son premier élément et la traite comme une fonction ou une macro, en l'appelant avec les éléments restants comme arguments. Si l'élément n'est pas une fonction / macro, le comportement n'est pas défini.
• Un symbole est évalué en tant que nom, donnant la valeur liée à ce nom dans la fonction en cours. Si le nom n'est pas défini dans la fonction en cours, la valeur qui lui est liée à l'échelle globale est évaluée. Si le nom n'est pas défini dans la portée actuelle ou globale, le résultat est indéfini (l'implémentation de référence donne un message d'erreur et renvoie nil).

Fonctions intégrées et macros

Tinylisp comporte sept fonctions intégrées. Une fonction évalue chacun de ses arguments avant de leur appliquer une opération et de renvoyer le résultat.

• c- contre [liste de texte]. Prend deux arguments, une valeur et une liste, et retourne une nouvelle liste obtenue en ajoutant la valeur au début de la liste.
• h- tête ( voiture , dans la terminologie Lisp). Prend une liste et retourne le premier élément de celle-ci, ou nil si nil est donné.
• t- tail ( cdr , en terminologie Lisp). Prend une liste et retourne une nouvelle liste contenant tout sauf le premier élément, ou nil si nil est donné.
• s- soustraire. Prend deux entiers et retourne le premier moins le second.
• l- moins que. Prend deux entiers; renvoie 1 si le premier est inférieur au second, 0 sinon.
• e- égal. Prend deux valeurs du même type (les deux entiers, les deux listes ou les deux symboles); renvoie 1 si les deux sont égaux (ou identiques dans chaque élément), 0 sinon. Le test d'égalité dans les éléments intégrés n'est pas défini (l'implémentation de référence fonctionne comme prévu).
• v- eval. Prend une liste, un entier ou un symbole représentant une expression et l’évalue. Par exemple, faire (v (q (c a b)))est la même chose que faire (c a b); (v 1)donne 1.

"Valeur" comprend ici toute liste, entier, symbole ou propriété intégrée, sauf indication contraire. Si une fonction est répertoriée comme prenant des types spécifiques, le fait de transmettre différents types constitue un comportement indéfini, tout comme le fait de transmettre un nombre incorrect d'arguments (l'implémentation de référence se bloque généralement).

Il existe trois macros intégrées dans tinylisp. Une macro, contrairement à une fonction, n'évalue pas ses arguments avant de leur appliquer des opérations.

• q- citation. Prend une expression et la retourne non évaluée. Par exemple, evaluation (1 2 3)donne une erreur car il essaie d'appeler en 1tant que fonction ou macro mais (q (1 2 3))renvoie la liste (1 2 3). L'évaluation adonne la valeur liée au nom a, mais (q a)donne le nom lui-même.
• i- si. Prend trois expressions: une condition, une expression iftrue et une expression iffalse. Évalue la condition en premier. Si le résultat est faux ( 0ou nul), évalue et renvoie l'expression iffalse. Sinon, évalue et renvoie l'expression iftrue. Notez que l'expression qui n'est pas renvoyée n'est jamais évaluée.
• d- def. Prend un symbole et une expression. Evalue l'expression et la lie au symbole donné traité comme un nom à portée globale , puis renvoie le symbole. Tenter de redéfinir un nom doit échouer (en mode silencieux, avec un message ou en cas de plantage; l’implémentation de référence affiche un message d’erreur). Note: il est nécessaire de ne pas citer le nom avant de le transmettre d, mais il est nécessaire de citer l'expression si elle est une liste ou d'un symbole que vous ne voulez pas évalué: par exemple (d x (q (1 2 3))).

Le fait de transmettre un nombre incorrect d'arguments à une macro constitue un comportement indéfini (plantage de l'implémentation de référence). Le fait de passer quelque chose qui n'est pas un symbole en tant que premier argument de dest un comportement indéfini (l'implémentation de référence ne génère pas d'erreur, mais la valeur ne peut pas être référencée ultérieurement).

Fonctions et macros définies par l'utilisateur

À partir de ces dix fonctions intégrées, le langage peut être étendu en créant de nouvelles fonctions et macros. Ceux-ci n'ont pas de type de données dédié; ce sont simplement des listes avec une certaine structure:

• Une fonction est une liste de deux éléments. Le premier est soit une liste d'un ou plusieurs noms de paramètres, soit un nom unique qui recevra une liste des arguments passés à la fonction (permettant ainsi des fonctions à arité variable). La seconde est une expression qui est le corps de la fonction.
• Une macro est identique à une fonction, sauf qu'elle contient nil avant le nom du paramètre, ce qui en fait une liste à trois éléments. (Tenter d'appeler des listes à trois éléments qui ne commencent pas par nil est un comportement indéfini; l'implémentation de la référence ignore le premier argument et les traite également comme des macros.)

Par exemple, l'expression suivante est une fonction qui ajoute deux entiers:

(q               List must be quoted to prevent evaluation
 (
  (x y)          Parameter names
  (s x (s 0 y))  Expression (in infix, x - (0 - y))
 )   
)

Et une macro qui prend un nombre quelconque d'arguments, évalue et renvoie le premier:

(q
 (
  ()
  args
  (v (h args))
 )
)

Les fonctions et les macros peuvent être appelées directement, liées à des noms à l'aide de d, et transmises à d'autres fonctions ou macros.

Comme les corps de fonction ne sont pas exécutés au moment de la définition, les fonctions récursives sont facilement définissables:

(d len
 (q (
  (list)
  (i list                      If list is nonempty
   (s 1 (s 0 (len (t list))))  1 - (0 - len(tail(list)))
   0                           else 0
  )
 ))
)

Notez cependant que ce qui précède n’est pas un bon moyen de définir une fonction de longueur car elle n’utilise pas ...

Récursion d'appel

La récursion d'appel est un concept important dans Lisp. Il implémente certains types de récursivité sous forme de boucles, réduisant ainsi la pile d'appels. Votre interprète tinylisp doit implémenter une récursion d’appel de queue appropriée!

• Si l'expression de retour d'une fonction ou d'une macro définie par l'utilisateur est un appel à une autre fonction ou macro définie par l'utilisateur, votre interprète ne doit pas utiliser la récursivité pour évaluer cet appel. Au lieu de cela, il doit remplacer la fonction et les arguments actuels par la nouvelle fonction, les arguments et la boucle jusqu'à la résolution de la chaîne d'appels.
• Si l'expression de retour d'une fonction ou d'une macro définie par l'utilisateur est un appel à i, n'évaluez pas immédiatement la branche sélectionnée. Au lieu de cela, vérifiez s'il s'agit d'un appel à une autre fonction ou macro définie par l'utilisateur. Si tel est le cas, remplacez la fonction et les arguments comme ci-dessus. Ceci s'applique aux occurrences arbitrairement profondément imbriquées de i.

La récursion de la queue doit fonctionner à la fois pour la récursion directe (une fonction s'appelle elle-même) et pour la récursivité indirecte (la fonction aappelle la fonction bqui appelle [etc] qui appelle la fonction a).

Une fonction de longueur récursive de la queue (avec une fonction d'assistance len*):

(d len*
 (q (
  (list accum)
  (i list
   (len*
    (t list)
    (s 1 (s 0 accum))
   )
   accum
  )
 ))
)
(d len
 (q (
  (list)
  (len* list 0)
 ))
)

Cette implémentation fonctionne pour des listes arbitrairement grandes, limitées uniquement par la taille maximale de l'entier.

Portée

Les paramètres de fonction sont des variables locales (en fait, les constantes, car elles ne peuvent pas être modifiées). Ils sont dans la portée pendant l'exécution du corps de l'appel de cette fonction et sortent de la portée lors d'appels plus profonds et après le retour de la fonction. Ils peuvent "masquer" les noms définis globalement, rendant ainsi le nom global temporairement indisponible. Par exemple, le code suivant renvoie 5 et non 41:

(d x 42)
(d f
 (q (
  (x)
  (s x 1)
 ))
)
(f 6)

Toutefois, le code suivant renvoie 41 car xau niveau d’appel 1, il n’est pas accessible à partir du niveau d’appel 2:

(d x 42)
(d f
 (q (
  (x)
  (g 15)
 ))
)
(d g
 (q (
  (y)
  (s x 1)
 ))
)
(f 6)

Les seuls noms possibles à un moment donné sont 1) les noms locaux de la fonction en cours d'exécution, le cas échéant, et 2) les noms globaux.

Conditions de soumission

Entrée et sortie

Votre interprète peut lire le programme depuis stdin ou depuis un fichier spécifié via stdin ou un argument de ligne de commande. Après avoir évalué chaque expression, le résultat de cette expression doit être exporté sur stdout avec une nouvelle ligne.

• Les entiers doivent apparaître dans la représentation la plus naturelle de votre langage d'implémentation. Des entiers négatifs peuvent être générés, avec des signes moins principaux.
• Les symboles doivent être affichés sous forme de chaînes, sans guillemets ni échappements.
• Les listes doivent être sorties avec tous les éléments séparés par un espace et placés entre parenthèses. Un espace entre les parenthèses est facultative: (1 2 3)et ( 1 2 3 )sont tous deux des formats acceptables.
• La sortie des fonctions intégrées et des macros est un comportement indéfini. (L'interprétation de référence les affiche comme <built-in function>.)

Autre

L'interpréteur de référence comprend un environnement REPL et la possibilité de charger des modules tinylisp à partir d'autres fichiers. ceux-ci sont fournis pour votre commodité et ne sont pas nécessaires pour relever ce défi.

Cas de test

Les scénarios de test sont séparés en plusieurs groupes afin que vous puissiez tester les plus simples avant de passer à des complexes plus complexes. Cependant, ils fonctionneront également très bien si vous les déposez tous dans un fichier. N'oubliez pas de supprimer les en-têtes et la sortie attendue avant de l'exécuter.

Si vous avez correctement implémenté la récursivité d'appel final, le cas de test final (en plusieurs parties) sera renvoyé sans provoquer de débordement de pile. L'implémentation de référence le calcule en six secondes environ sur mon ordinateur portable.

Python 2, 685 675 660 657 646 642 640 octets

import sys,re
E=[]
G=zip("chtsle",[eval("lambda x,y=0:"+f)for f
in"[x]+y (x+[E])[0] x[1:] x-y +(x<y) +(x==y)".split()])
def V(e,L=E):
 while 1:
    try:return e and int("0%s"%e)
    except:A=e[1:]
    if""<e:return dict(G+L).get(e,e)
    f=V(e[0],L)
    if""<f:
     if f in"iv":t=V(A[0],L);e=(e[~bool(t)],t)[f>"u"];continue
     if"e">f:G[:]+=(A[0],V(A[1],L)),
     return A[0]
    if[]>f or f[0]:A=[V(a,L)for a in A]
    if[]>f:return f(*A)
    P,e=f[-2:];L=([(P,A)],zip(P,A))[P<""]
F=lambda x:V<x<""and"(%s)"%" ".join(map(F,x))or"%s"%x
for t in re.sub("([()])"," \\1 ",sys.stdin.read()).split():
 if")"==t:t=E.pop()
 if"("==t:E+=[],
 elif E:E[-1]+=t,
 else:print F(V(t))

Lit les entrées de STDIN et écrit les sorties dans STDOUT.

Bien que cela ne soit pas strictement nécessaire, l'interpréteur prend en charge les fonctions et les macros nullaires et optimise les appels finaux exécutés v.

Explication

L'analyse

Pour analyser l'entrée, nous entourons d'abord chaque occurrence de (et )avec des espaces, puis scindons la chaîne résultante en mots; cela nous donne la liste des jetons. Nous maintenons une pile d'expression E, qui est initialement vide. Nous numérisons les jetons, dans l'ordre:

• si nous rencontrons un (, nous poussons une liste vide en haut de la pile d'expression;
• si nous rencontrons un ), nous affichons la valeur en haut de la pile d’expressions et nous l’ajoutons à la liste qui se trouvait précédemment en dessous de celle-ci sur la pile;
• sinon, nous ajoutons le jeton actuel, en tant que chaîne, à la liste située en haut de la pile d'expression (nous conservons les entiers sous forme de chaînes à ce stade et les analysons lors de l'évaluation.)

Si, lors du traitement d'un jeton ordinaire, ou après avoir extrait une expression de la pile en raison de ), la pile d'expression est vide, nous sommes à une expression de niveau supérieur et nous évaluons la valeur que nous aurions autrement ajoutée, à l'aide de V(), et imprimer son résultat, formaté de manière appropriée en utilisant F().

Évaluation

Nous maintenons la portée globale G, sous forme de liste de paires clé / valeur. Initialement, il ne contient que les fonctions internes (mais pas les macros, et vque nous traitons comme une macro), qui sont implémentées comme des lambdas.

L' évaluation se produit à l' intérieur V(), qui prend l'expression à évaluer, eet le champ d' application locale, Lqui est, lui aussi, une liste de paires clé / valeur (lors de l' évaluation d' une expression de niveau haut, la portée locale est vide.) Les entrailles de V()concert Comme nous le verrons plus tard, l’optimisation de l’appel final est une boucle infinie.

Nous traitons eselon son type:

• s'il s'agit de la liste vide ou d'une chaîne convertible en int, nous la retournons immédiatement (éventuellement après conversion en int); autrement,

• s'il s'agit d'une chaîne, nous le recherchons dans un dictionnaire construit à partir de la concaténation des portées globale et locale. Si nous trouvons une valeur associée, nous la retournons; sinon, edoit être le nom d'une macro prédéfinie (c'est q-à- dire i, dou v) et nous le retournons tel quel. Sinon, si en'est pas une chaîne,

• eest une liste (non vide), c’est-à-dire un appel de fonction. Nous évaluons le premier élément de la liste, c'est-à-dire l'expression de la fonction, en appelant de V()manière récursive (en utilisant la portée locale actuelle); nous appelons le résultat f. Le reste de la liste A, est la liste des arguments. fil ne peut s'agir que d'une chaîne, auquel cas il s'agit d'une macro intégrée (ou de la fonction v), d'un lambda, auquel cas il s'agit d'une fonction intégrée ou d'une liste, auquel cas il s'agit d'une macro ou d'une fonction définie par l'utilisateur.

  Si fest une chaîne, c'est-à-dire une macro intégrée, nous la gérons sur place. S'il s'agit de la macro iou v, nous évaluons son premier opérande et sélectionnons le deuxième ou le troisième opérande en conséquence dans le cas de i, ou utilisons le résultat du premier opérande dans le cas de v; au lieu d'évaluer récursivement l'expression sélectionnée, ce qui éliminerait le coût total de possession, nous la remplacerons simplement epar ladite expression et passerons au début de la boucle. Si fest la macro d, nous ajoutons une paire dont le premier élément est le premier opérande et dont le deuxième élément est le résultat de l'évaluation du deuxième opérande, à la portée globale G, et renvoie le premier opérande. Sinon, fc'est la macro q, auquel cas nous retournons simplement son opérande.

  Autrement, s'il fs'agit d'un lambda ou d'une liste dont le premier élément n'est pas (), il s'agit d'une fonction non nullary, pas d'une macro. Dans ce cas, nous évaluons ses arguments, c'est-à-dire les éléments de A, et nous les remplaçons Apar le résultat.

  Si fest un lambda, nous l'appelons, en lui transmettant les arguments non compressés Aet en renvoyant le résultat.

  Sinon, fest une liste, c'est-à-dire une fonction ou une macro définie par l'utilisateur; sa liste de paramètres est l'avant-dernier élément et son corps est le dernier. Comme dans le cas des macros iet v, pour effectuer le TCO, nous n'évaluons pas le corps de manière récursive, mais le remplaçons plutôt epar le corps et passons à la prochaine itération. Contrairement à iet vcependant, nous remplaçons également la portée locale Lpar la nouvelle portée locale de la fonction. Si la liste des paramètres, Pest, en fait, une liste, la nouvelle portée locale est construite par zipper la liste des paramètres, Pavec la liste des arguments, A; sinon, nous avons affaire à une fonction variadique, auquel cas la nouvelle portée locale ne comporte qu'un seul élément, la paire (P, A).

REPL

Si vous voulez jouer avec, voici une version de l'interpréteur REPL. Il prend en charge la redéfinition des symboles et l'importation de fichiers via les arguments de ligne de commande ou la (import <filename>)macro. Pour quitter l’interprète, mettez fin à la saisie (généralement Ctrl + D ou Ctrl + Z).

try:import sys,re,readline
except:0
E=[];G=zip("chtsle",[eval("lambda x,y=0:"+f)for f
in"[x]+y (x+[E])[0] x[1:] x-y +(x<y) +(x==y)".split()])
def V(e,L=E):
 while 1:
    try:return e and int("0%s"%e)
    except:A=e[1:]
    if""<e:return dict(G+L).get(e,e)
    f=V(e[0],L)
    if""<f:
     if f in"iv":t=V(A[0],L);e=(e[~bool(t)],t)[f>"u"];continue
     if"e">f:G[:]+=(A[0],V(A[1],L)),
     elif"j">f:X(open(str(A[0])).read())
     return A[0]
    if[]>f or f[0]:A=[V(a,L)for a in A]
    if[]>f:return f(*A)
    P,e=f[-2:];L=([(P,A)],zip(P,A))[P<""]
F=lambda x:V<x<""and"(%s)"%" ".join(map(F,x))or"%s"%x
def X(s,v=0):
 for t in re.sub("([()])"," \\1 ",s).split():
    if")"==t:t=E.pop()
    if"("==t:E[:]+=[],
    elif E:E[-1]+=t,
    else:
     x=V(t)
     if v:print F(x)
for f in sys.argv[1:]:X("(g %s)"%f)
while 1:
 try:X(raw_input(">."[[]<E]*3+" "),1)
 except EOFError:break
 except KeyboardInterrupt:E=[];print
 except Exception as e:print"Error: "+e.message

Et voici un exemple de session mettant en œuvre le tri par fusion:

>>> (d let d) (d if i) (d head h) (d tail t) (d prepend c) (d less l)
let
if
head
tail
prepend
less
>>>
>>> (let list (q (x... x...)))
list
>>> (let lambda (q (() (params body) (list params body))))
lambda
>>> (let def (q (() (name params body) (
...     v (list (q let) name (list (q lambda) params body))
... ))))
def
>>>
>>> (def else(body) body)
else
>>> (def or(x y) ( if x x y ))
or
>>> (def and(x y) ( if x y x ))
and
>>>
>>> (def front-half(L) ( front-half/impl L L ))
front-half
>>> (def front-half/impl(L M) (
...     if M (
...         prepend (head L)
...                 (front-half/impl (tail L) (tail (tail M)))
...     ) (else
...         ()
...     )
... ))
front-half/impl
>>>
>>> (def back-half(L) ( back-half/impl L L ))
back-half
>>> (def back-half/impl(L M) (
...     if M (
...         back-half/impl (tail L) (tail (tail M))
...     ) (else
...         L
...     )
... ))
back-half/impl
>>>
>>> (def merge(L M comp) (
...     if (and L M) (
...         if (comp (head M) (head L)) (
...             prepend (head M) (merge L (tail M) comp)
...         ) (else (
...             prepend (head L) (merge (tail L) M comp)
...         ))
...     ) (else (
...         or L M
...     ))
... ))
merge
>>>
>>> (def sort(L comp) (
...     if (and L (tail L)) (
...         merge (sort (front-half L) comp)
...               (sort (back-half L) comp)
...               comp
...     ) (else
...         L
...     )
... ))
sort
>>>
>>>
>>> (let my-list (list 4 7 2 5 9 1 6 10 8 3))
my-list
>>> my-list
(4 7 2 5 9 1 6 10 8 3)
>>> (sort my-list less)
(1 2 3 4 5 6 7 8 9 10)
>>> (sort my-list (lambda(x y) ( less y x )))
(10 9 8 7 6 5 4 3 2 1)

C (GNU), 1095 octets

Une grande partie de l'action se déroule dans la vfonction géante . Au lieu d'implémenter explicitement la récursion de queue, la vstructure est telle que de nombreux appels de và vseront traités par l'optimisation de la récursion de queue de gcc. Il n'y a pas de collecte de déchets.

Cela fait un usage intensif des extensions GCC, il ne peut donc être compilé qu'avec gcc (utilisez la commande gcc -w -Os tl.c). Il utilise également des scanfextensions non disponibles sous Windows, que j'utilise habituellement. La perspective d'écrire l'analyseur avec standard scanfétait si terrible que j'ai plutôt utilisé une machine virtuelle Linux pour tester le programme. L'analyse sans scanfclasses de caractères aurait probablement ajouté plus de 100 octets.

#define O(...)({o*_=malloc(32);*_=(o){__VA_ARGS__};_;})
#define P printf
#define F(I,B)({for(I;x->c;x=x->l)B;})
#define Z return
typedef struct o{struct o*n,*l,*c;int i,t;}o;E(o a,o b){Z
a.n?!strcmp(a.n,b.n):a.c?b.c&&E(*a.c,*b.c)&E(*a.l,*b.l):!b.c&a.i==b.i;}p(o*x){x->t?P("%d ",x->i):x->n?P("%s ",x->n):F(P("("),p(x->c);P(")"));}o*x,G,N;*C(o*h,o*t){Z
O(c:h,l:t);}o*v(o*x,o*e){o*W(o*l,o*e){Z
l->c?C(v(l->c,e),W(l->l,e)):&N;}o*y,*a,*f;int t;Z
x->c?y=v(x->c,e),x=x->l,t=y->i,t?9/t?a=v(x->c,e),t>7?(t>8?a->c:a->l)?:a:t>6?v(a,e):t<6?x=v(x->l->c,e),t>4?C(a,x):O(t:1,i:t>3?E(*a,*x):t>2?a->i<x->i:a->i-x->i):v((a-&N&&!a->t|a->i?x:x->l)->l->c,e):(t&1&&d(x->c->n,v(x->l->c,e)),x->c):(y->l->l->l?y=y->l:(x=W(x,e)),a=y->c,v(y->l->c,a->n?O(n:a->n,c:x,l:&G):F(f=&G,(f=O(n:a->c->n,c:x->c,l:f),a=a->l);f))):x->n?e->n?strcmp(x->n,e->n)?v(x,e->l):e->c:e:x;}d(o*n,o*x){*v(O(n:""),&G)=(o){n:n,c:x,l:O()};}*R(h){char*z,*q;Z
scanf(" %m[^ \n()]",&q)>0?h=strtoul(q,&z,10),C(*z?O(n:q):O(t:1,i:h),R()):~getchar()&1?q=R(),C(q,R()):&N;}main(i){for(;++i<12;)d(strndup("slecivthqd"+i-2,1),O(i:i));F(x=R(),p(v(x->c,&G)));}

Semi-Ungolfed

typedef struct o o;
struct o {
    char* n;
    o* l, //next in this list
     * c; 
    int i,
        t;
} ;



#define O(...)({o*_=malloc(32);*_=(o){__VA_ARGS__};_;})

E(o a, o b) { //tests equality 
    return
        a.n ? !strcmp(a.n,b.n) :
        a.t ? a.i==b.i :
        a.c ? b.c && E(*a.c,*b.c)&E(*a.l,*b.l) :
        !b.c
    ;
}

#define P printf


p(o*x){
    x->t?P("%d ",x->i):x->n?P("%s ",x->n):({for(P("(");x->c;x=x->l)p(x->c);P(")");});
}


o*_,G,N; //N = nil



o*C(o*h,o*t){return O(c:h,l:t);}


/*
        2 3 4 5 6 7 8 9 10 11
        s l e c i v t h d  q
    */


o* v(o* x, o* e) { //takes list, int, or name
    o*W(o* l, o* e) { //eval each item in list
        return l->c ? C(v(l->c ,e), W(l->l, e)) : &N;
    }

    o*y,*a,*f;int t;
    return x->c ? //nonempty list = function/macro call
        y = v(x->c,e), //evals to function/macro
        x = x->l,   //list position of first arg (if it exists)
        (t=y->t)?   //builtin no., if any
             t>9 ?
              t&1 ? x->c // 11 = q
                : //10 = d
                (d(x->c,v(x->l->c,e)),x->c)
           : (a = v(x->c,e), //eval'd first arg
             t)>7 ? // t/h
                (t > 8 ? a->c : a->l) ?: a
           : t>6 ? //v
                v(a,e)
           : (x = x->l, //position of 2nd arg in list
             t)>5 ? //i
                v( (a->n||a->l||a->i|a->t>1 ? x : x->l)->c, e)
           : (x = v(x->c,e), //evaluated 2nd arg
             t)>4 ? // c
                C(a,x)
           : O(t:1,i:
                t>3 ? E(*a,*x) :  //e
                t>2 ? a->i<x->i : //l
                      a->i-x->i   //s
              )
        :
        (
            y->l->l->l ? //whether this is macro
                y = y->l :
                (x = W(x,e)),  //eval args
            a = y->c,  //a = arg list
            //a = a->n ? x=C(x, &N), C(a, &N) : a, //transform variadic style to normal
            v(y->l->c,
               a->n ? //variadic
                O(n:a->n,c:x,l:&G)
              : ({
                   for(f=&G; a->c; a=a->l,x=x->l)
                      f=O(n:a->c->n, c: x->c, l:f);
                   f;
                })
            )
        )
    :
    x->n ? // name
        e->n ?
            strcmp(x->n,e->n) ?
                v(x,e->l)
            : e->c
        : e
     : x; //int or nil
}

d(o*n,o*x){
    * v(O(n:""),&G) =
        (o){n:n->n,c:x,l:O()};
}


;
o*R(){
    char*z,*q;int h;
return scanf(" %m[^ \n()]",&q)>0?
    h=strtoul(q,&z,10),
    C(*z ? O(n:q) : O(t:1,i:h), R())
: getchar()&1?&N:(q=R(),C(q,R()));
}
main(i) {

    for(;++i<12;) d(O(n:strndup("slecivthdq"+i-2,1)),O(t:i));

    o *q;
    for(q=R(); q->c; q=q->l) p(v(q->c,&G));

}

Ceylan, 2422 octets

(Je pense que c'est mon plus long programme de golf à ce jour.)

import ceylon.language{sh=shared,va=variable,fo=formal,O=Object}import ceylon.language.meta.model{F=Function}interface X{sh fo V v(S t);sh fo G g;}class G(va Map<S,V>m)satisfies X{v(S t)=>m[t]else nV;g=>this;sh S d(S s,V v){assert(!s in m);m=map{s->v,*m};return s;}}V nV=>nothing;class LC(G c,Map<S,V>m)satisfies X{g=>c;v(S t)=>m[t]else g.v(t);}alias C=>V|Co;interface Co{sh fo C st();}interface V{sh fo C l(X c,V[]a);sh default Boolean b=>0<1;sh fo C vO(X c);sh default V vF(X c){va C v=vO(c);while(is Co n=v){v=n.st();}assert(is V r=v);return r;}}class L(sh V*i)satisfies V{vO(X c)=>if(nonempty i)then i[0].vF(c).l(c,i.rest)else this;equals(O o)=>if(is L o)then i==o.i else 1<0;b=>!i.empty;string=>"(``" ".join(i)``)";hash=>i.hash;sh actual C l(X c,V[]p){value[h,ns,x]=i.size<3then[f,i[0],i[1]]else[m,i[1],i[2]];value n=if(is L ns)then[*ns.i.narrow<S>()]else ns;assert(is S|S[]n,is V x);V[]a=h(c,p);LC lC=if(is S n)then LC(c.g,map{n->L(*a)})else LC(c.g,map(zipEntries(n,a)));return object satisfies Co{st()=>x.vO(lC);};}}class S(String n)satisfies V{vO(X c)=>c.v(this);l(X c,V[]a)=>nV;equals(O o)=>if(is S o)then n==o.n else 1<0;hash=>n.hash;string=>n;}class I(sh Integer i)satisfies V{vO(X c)=>this;l(X c,V[]a)=>nV;equals(O o)=>if(is I o)then i==o.i else 1<0;hash=>i;b=>!i.zero;string=>i.string;}V[]f(X c,V[]a)=>[for(v in a)v.vF(c)];V[]m(X c,V[]a)=>a;L c(X c,V h,L t)=>L(h,*t.i);V h(X c,L l)=>l.i[0]else L();V t(X c,L l)=>L(*l.i.rest);I s(X c,I f,I s)=>I(f.i-s.i);I l(X c,I f,I s)=>I(f.i<s.i then 1else 0);I e(X c,V v1,V v2)=>I(v1==v2then 1else 0);C v(X c,V v)=>v.vO(c);V q(X c,V a)=>a;C i(X c,V d,V t,V f)=>d.vF(c).b then t.vO(c)else f.vO(c);S d(X c,S s,V x)=>c.g.d(s,x.vF(c));class B<A>(F<C,A>nat,V[](X,V[])h=f)satisfies V given A satisfies[X,V+]{vO(X c)=>nV;string=>nat.declaration.name;l(X c,V[]a)=>nat.apply(c,*h(c,a));}{<S->V>*}b=>{S("c")->B(`c`),S("h")->B(`h`),S("t")->B(`t`),S("s")->B(`s`),S("l")->B(`l`),S("e")->B(`e`),S("v")->B(`v`),S("q")->B(`q`,m),S("i")->B(`i`,m),S("d")->B(`d`,m)};[V*]p(String inp){value ts=inp.split(" \n()".contains,1<0,1<0);va[[V*]*]s=[];va[V*]l=[];for(t in ts){if(t in" \n"){}else if(t=="("){s=[l,*s];l=[];}else if(t==")"){l=[L(*l.reversed),*(s[0]else[])];s=s.rest;}else if(exists i=parseInteger(t),i>=0){l=[I(i),*l];}else{l=[S(t),*l];}}return l.reversed;}sh void run(){va value u="";while(exists l=process.readLine()){u=u+l+"\n";}V[]e=p(u);X c=G(map(b));for(v in e){print(v.vF(c));}}

J'aurais pu jouer plus sur quelques octets, car j'ai utilisé des identifiants à deux lettres à certains endroits, mais je n'ai plus beaucoup de lettres simples qui ont du sens. Même si cela ne ressemble pas beaucoup à Ceylan ...

Ceci est une implémentation orientée objet .

Nous avons une interface de valeur Vavec des classes implémentantes L(list - juste un wrapper autour d’une suite de Ceylan V), S(symbol - wrapper autour d’une chaîne), I(entier - un wrapper autour d’un entier de Ceylan) et B(fonction intégrée ou macro, un wrapper autour d’un Fonction de Ceylan).

J'utilise la notation d'égalité de Ceylan standard en implémentant la equalsméthode (et également l' hashattribut, qui n'est nécessaire que pour les symboles), ainsi que l' stringattribut standard pour la sortie.

Nous avons un attribut booléen b(qui est true par défaut, remplacé par Iet Lpour renvoyer false pour les listes vides), et deux méthodes l(call, c'est-à-dire utiliser cet objet en tant que fonction) et vO(évaluer une étape). Tous deux renvoient soit une valeur, soit un objet Continuation qui permet ensuite une évaluation pour une étape supplémentaire, et vF(évalue complètement) en boucle jusqu'à ce que le résultat ne soit plus une continuation.

Une interface contextuelle permet d'accéder aux variables. Il y a deux implémentations, Gpour le contexte global (qui permet d'ajouter des variables à l'aide de la commande dintégrée) et LCpour un contexte local, actif lors de l'évaluation de l'expression d'une fonction utilisateur (elle revient au contexte global).

L'évaluation des symboles accède au contexte, les listes (si non vides) sont évaluées en évaluant d'abord leur premier élément, puis en appelant sa méthode d'appel. Call est mis en œuvre uniquement par listes et commandes intégrées - il évalue d’abord l’argument (si une fonction, pas si une macro), puis effectue le travail intéressant - pour les commandes intégrées, ce qui est codé en dur, pour les listes, il crée un nouveau contexte local et renvoie un continuation avec ça.

Pour les fonctions intégrées, j'ai utilisé une astuce similaire à celle utilisée dans mon interpréteur de décalage , ce qui me permet de les définir avec les types d'arguments dont ils ont besoin, mais de les appeler avec une séquence générique utilisant la réflexion (les types seront vérifiés au moment de l'appel). Cela évite les problèmes de conversion / assertion de type à l'intérieur des fonctions / macros, mais nécessite des fonctions de niveau supérieur pour que je puisse obtenir leurs Functionobjets de méta-modèle .

La fonction p(analyse) divise la chaîne au niveau des espaces, des nouvelles lignes et des parenthèses, puis parcourt les marques et construit des listes à l'aide d'une pile et d'une liste en cours d'exécution.

L'interpréteur (dans la runméthode, qui est le point d'entrée) prend ensuite cette liste d'expressions (qui ne sont que des valeurs), les évalue et affiche le résultat.

Vous trouverez ci-dessous une version avec des commentaires et un formateur.

Une version antérieure à mes débuts (et avec quelques incompréhensions à propos de l'évaluation de liste) se trouve dans mon référentiel Github , je vais y mettre celle-ci bientôt (veillez donc à regarder la première version si vous voulez l'original).

//  Tiny Lisp, tiny interpreter
//
// An interpreter for a tiny subset of Lisp, from which most of the
// rest of the language can be bootstrapped.
//
// Question:   https://codegolf.stackexchange.com/q/62886/2338
// My answer:  https://codegolf.stackexchange.com/a/63352/2338
//
import ceylon.language {
    sh=shared,
    va=variable,
    fo=formal,
    O=Object
}
import ceylon.language.meta.model {
    F=Function
}

// context

interface X {
    sh fo V v(S t);
    sh fo G g;
}
// global (mutable) context, with the buildins 
class G(va Map<S,V> m) satisfies X {
    // get entry throws error on undefined variables. 
    v(S t) => m[t] else nV;
    g => this;
    sh S d(S s, V v) {
        // error when already defined
        assert (!s in m);
        // building a new map is cheaper (code-golf wise) than having a mutable one.
        m = map { s->v, *m };
        return s;
    }
}

// This is simply a shorter way of writing "this is not an allowed operation".
// It will throw an exception when trying to access it.
// nV stands for "no value".
V nV => nothing;

// local context
class LC(G c, Map<S,V> m) satisfies X {
    g => c;
    v(S t) => m[t] else g.v(t);
    // sh actual String string => "[local: ``m``, global: ``g``]";
}

// continuation or value
alias C => V|Co;

// continuation
interface Co {
    sh fo C st();
}

// value
interface V {
    // use this as a function and call with arguments.
    // will not work for all types of stuff.
    sh fo C l(X c, V[] a);
    // check the truthiness. Defaults to true, as
    // only lists and integers can be falsy.
    sh default Boolean b => 0 < 1;
    // evaluate once (return either a value or a continuation).
    // will not work for all kinds of expression.
    sh fo C vO(X c);
    /// evaluate fully
    sh default V vF(X c) {
        va C v = vO(c);
        while (is Co n = v) {
            v = n.st();
        }
        assert (is V r = v);
        return r;
    }
}
class L(sh V* i) satisfies V {

    vO(X c) => if (nonempty i) then i[0].vF(c).l(c, i.rest) else this;
    equals(O o) => if (is L o) then i == o.i else 1 < 0;
    b => !i.empty;
    string => "(``" ".join(i)``)";
    hash => i.hash;

    sh actual C l(X c, V[] p) {
        value [h, ns, x] =
                i.size < 3
                then [f, i[0], i[1]]
                else [m, i[1], i[2]];
        // parameter names – either a single symbol, or a list of symbols.
        // If it is a list, we filter it to throw out any non-symbols.
        // Should throw an error if there are any, but this is harder.
        value n = if (is L ns) then [*ns.i.narrow<S>()] else ns;
        assert (is S|S[] n, is V x);
        V[] a = h(c, p);

        // local context
        LC lC = if (is S n) then
            LC(c.g, map { n -> L(*a) })
        else
            LC(c.g, map(zipEntries(n, a)));
        // return a continuation instead of actually
        // calling it here, to allow stack unwinding.
        return object satisfies Co {
            st() => x.vO(lC);
        };
    }
}

// symbol
class S(String n) satisfies V {
    // evaluate: resolve
    vO(X c) => c.v(this);
    // call is not allowed
    l(X c, V[] a) => nV;
    // equal if name is equal
    equals(O o) => if (is S o) then n == o.n else 1 < 0;
    hash => n.hash;
    string => n;
}

// integer
class I(sh Integer i) satisfies V {

    vO(X c) => this;
    l(X c, V[] a) => nV;
    equals(O o) => if (is I o) then i == o.i else 1 < 0;
    hash => i;
    b => !i.zero;
    string => i.string;
}

// argument handlers for functions or macros
V[] f(X c, V[] a) => [for (v in a) v.vF(c)];
V[] m(X c, V[] a) => a;

// build-in functions
// construct
L c(X c, V h, L t) => L(h, *t.i);
// head
V h(X c, L l) => l.i[0] else L();
// tail
V t(X c, L l) => L(*l.i.rest);
// subtract
I s(X c, I f, I s) => I(f.i - s.i);
// lessThan
I l(X c, I f, I s) => I(f.i < s.i then 1 else 0);
// equal
I e(X c, V v1, V v2) => I(v1 == v2 then 1 else 0);
// eval (returns potentially a continuation)
C v(X c, V v) => v.vO(c);

// build-in macros
// quote
V q(X c, V a) => a;
// if (also returns potentially a continuation)
C i(X c, V d, V t, V f) => d.vF(c).b then t.vO(c) else f.vO(c);
// define symbol in global context
S d(X c, S s, V x) => c.g.d(s, x.vF(c));

// buildin function or macro, made from a native function and an argument handler
class B<A>(F<C,A> nat, V[](X, V[]) h = f)
        satisfies V
        given A satisfies [X, V+] {
    vO(X c) => nV;
    string => nat.declaration.name;
    // this "apply" is a hack which breaks type safety ...
    // but it will be checked at runtime.
    l(X c, V[] a) => nat.apply(c, *h(c, a));
}

// define buildins
{<S->V>*} b => {
    S("c") -> B(`c`),
    S("h") -> B(`h`),
    S("t") -> B(`t`),
    S("s") -> B(`s`),
    S("l") -> B(`l`),
    S("e") -> B(`e`),
    S("v") -> B(`v`),
    S("q") -> B(`q`, m),
    S("i") -> B(`i`, m),
    S("d") -> B(`d`, m)
};

// parses a string into a list of expressions.
[V*] p(String inp) {
    // split string into tokens (retain separators, don't group them –
    // whitespace and empty strings will be sorted out later in the loop)
    value ts = inp.split(" \n()".contains, 1 < 0, 1 < 0);
    // stack of not yet finished nested lists, outer most at bottom
    va [[V*]*] s = [];
    // current list, in reverse order (because appending at the start is shorter)
    va [V*] l = [];
    for (t in ts) {
        if (t in " \n") {
            // do nothing for empty tokens
        } else if (t == "(") {
            // push the current list onto the stack, open a new list.
            s = [l, *s];
            l = [];
        } else if (t == ")") {
            // build a lisp list from the current list,
            // pop the latest list from the stack, append the created lisp list. 
            l = [L(*l.reversed), *(s[0] else [])];
            s = s.rest;
        } else if (exists i = parseInteger(t), i >= 0) {
            // append an integer to the current list.
            l = [I(i), *l];
        } else {
            // append a symbol to the current list.
            l = [S(t), *l];
        }
    }
    return l.reversed;
}

// Runs the interpreter.
// This handles input and output, calls the parser and evaluates the expressions.
sh void run() {
    va value u = "";
    while (exists l = process.readLine()) {
        u = u + l + "\n";
    }
    V[] e = p(u);
    // create global context
    X c = G(map(b));
    // iterate over the expressions, ...
    for (v in e) {
        // print("  '``v``' → ...");
        // ... evaluate each (fully) and print the result.
        print(v.vF(c));
    }
}