Défi

Votre défi est de concevoir un interprète pour une langue de type lisp, qui sera désormais inventée: GLisp . Le code du programme pour GLisp consistera en une quantité arbitraire d'expressions imbriquées désignées par des crochets, sous la forme suivante:

(func arg1 arg2 ...)

Notez que l'interpréteur doit autoriser les espaces blancs superflus avant et après les crochets, les fonctions et les arguments.

Les types

Vous implémenterez quatre types, Integer, List, Boolean et Function. Les entiers et les valeurs booléennes peuvent être insérés explicitement dans le code source avec leur propre syntaxe. Votre interprète doit supposer qu'une série de caractères numériques dénote un entier (vous n'avez pas à implémenter une syntaxe pour insérer explicitement des entiers négatifs). Votre interprète doit également supposer cela trueet falsesont des valeurs booléennes désignées. Les fonctions ne peuvent pas être définies explicitement par l'utilisateur et renverront toujours une seule valeur (une liste de toute longueur compte comme une seule valeur).

Les fonctions

Les fonctions suivantes doivent être implémentées et sont au format Fonction , Arity . Si une entité nest précédée d'un signe plus, cela indique un nou plusieurs arguments. Vous pouvez supposer que tous les arguments donnés à une fonction sont du même type, sauf indication contraire. Vous pouvez également supposer que si aucun comportement n'est spécifié pour un type certian, vous pouvez supposer qu'aucun argument de cette fonction ne sera jamais de ce type. Les arguments seront appelés comme dans le diagramme suivant:

(func argument1 argument2 ... argumentn)

• + , 2+

  • Si tous les arguments sont de type Integer , vous devez renvoyer la somme des arguments
  • Si tous les arguments sont du type List , vous devez renvoyer la concaténation des arguments dans l'ordre croissant ( arg1+arg2+ ...)
  • Si tous les arguments sont de type booléen , vous devez renvoyer l'ensemble logique de la séquence d'arguments
  • (+ 1 2 3 4 5) -> 15
  • (+ (list 1 2) (list 3 4)) -> (list 1 2 3 4)
  • (+ true true true) -> true

• - , 2+

  • Si tous les arguments sont de type Integer , vous devez renvoyer la différence des arguments ( arg1-arg2- ...)
  • Si tous les arguments sont de type booléen , vous devez renvoyer la logique quelconque de la séquence d'arguments
  • (- 8 4 3) -> 1
  • (- 0 123) -> -123
  • (- true false false true false) -> true

• * , 2+

  • Si tous les arguments sont de type Integer , vous devez renvoyer le produit des arguments
  • Si un argument est de type List et l'autre est de type Integer (vous pouvez supposer que ce ne seront que les seuls arguments donnés), vous devez renvoyer une nouvelle List avec les éléments à arg1plusieurs arg2reprises.
  • (* 1 2 3 4 5) -> 120
  • (* (list 1 2 3) 2) -> (list 1 2 3 1 2 3)

• / , 2+

  • Si tous les arguments sont du type Entier , vous devez renvoyer le quotient des arguments ( arg/arg2/ ...) (vous pouvez supposer que la division est effectuée séquentiellement et que la partie décimale à chaque étape est tronquée)
  • Si un argument est de type Liste et l'autre est de type Fonction , vous devez renvoyer la Liste résultante après arg2avoir été mappée sur chaque valeur
  • (/ 100 10 3) -> 3
  • (/ (list 1 2 3) inc) -> (list 2 3 4)

• % , 2

  • Si tous les arguments sont de type Integer , vous devez renvoyer le module des arguments
  • (% 4 2) -> 0

• = , 2+

  • Si à la fois le type et la valeur de tous les arguments sont les mêmes, vous devez retourner vrai. Sinon, retournez false.
  • (= 0 0 0) -> true
  • (= 0 false (list)) -> false

• liste , 0+

  • Vous devez renvoyer une liste de tous les arguments, quel que soit leur type. Si aucun argument n'est donné, vous devez renvoyer une liste vide
  • (list 3 4 (list 5)) -> (list 3 4 (list 5))

• inc , 1

  • Si l'argument est de type Integer , vous devez renvoyer Integer incrémenté d'une unité.
  • Si l'argument est de type Liste , vous devez renvoyer la Liste tournée dans le sens horaire d'une seule rotation
  • (inc 1) -> 2
  • (inc (list 1 2 3)) -> (list 3 1 2)

• déc , 1

  • Si l'argument est de type Integer , vous devez renvoyer l' Integer décrémenté d'une unité
  • Si l'argument est de type Liste , vous devez renvoyer la Liste tournée dans le sens antihoraire une seule rotation
  • (dec 1) -> 0
  • (dec (list 1 2 3)) -> (list 2 3 1)

• si , 3

  • Si on donne trois arguments de n'importe quel type: Si la valeur de vérité de arg1est vraie, retourne arg2, sinon retournearg3
  • (if (not (list 1)) 8 false) -> false

• non , 1

  • Si un argument de n'importe quel type lui est donné, si la valeur de vérité de arg1est False, return true, else return false.
  • (not (list)) -> true

• len , 1

  • Si un argument de type List est donné , retourne la longueur dearg1
  • (len (list 4 2 true (list 3) (list))) -> 5

Table de vérité:, 0, (list), false -> falseoù (list)dénote une liste vide. Tout le reste l'est true.

Votre interpréteur peut être soit un programme complet qui lit l'entrée source depuis stdin ou un fichier, soit une fonction qui prend la source comme chaîne et renvoie la valeur de sortie.

Si vous choisissez le premier, la sortie pour les entiers est simplement des nombres, pour les booléens est trueou false, et pour les listes est une séquence de valeurs séparées par des espaces entre crochets (par exemple, (1 2 3 4 (5 6 7))dénote (list 1 2 3 4 (list 5 6 7))).

Si vous choisissez ce dernier, la valeur doit être retournée dans le type correspondant du langage d'implémentation ou, s'il n'existe aucun type similaire, un type personnalisé. Listes peuvent être renvoyées sous forme de tableaux ou de vecteurs si la langue n'a pas de type Liste , les booléens doivent être renvoyés sous forme de type booléen dans la langue ou un type personnalisé si la langue ne les prend pas en charge.

Cas de test

(list 1 2 3 (list 4 5 true))  -> (1 2 3 (4 5 true))
(/ 4000 (+ 1 2 3 4 (* 5 8)))  -> 80
(+ (not (- (len (list 5 6 7)) (/ 10 3))) true)  -> true
(if (           len (list )  ) 4 (if    (+ (= 8 8    8) (not (list 4))) 8 5))  -> 5

Clarifications

• Votre interprète peut traiter les entrées invalides de la manière que vous choisissez, mais ne doit pas lever d'exception (cependant, il peut imprimer un message d'erreur et quitter en douceur)
• Les fonctions évalueront toujours les arguments de gauche à droite
• Une entrée non valide est une entrée qui est syntaxiquement incorrecte. Cela inclut, mais sans s'y limiter, les parenthèses incompatibles, la division par zéro et les fonctions partiellement appliquées (sauf si vous optez pour le bonus)
• Pour =, si l'une des valeurs est différente ou l' un des types est différent, retournezfalse

Bonus

• Score * 0,8 si vous supportez des fonctions partiellement appliquées. Par exemple, ((+ 2) 3)serait le même que (+ 2 3), mais permet des choses telles que (/ (list 1 2 3) (+ 2)). Vous pouvez supposer qu'une fonction est partiellement appliquée si elle reçoit moins que son nombre minimum d'arguments
• Score * 0,85 si vous n'évaluez pas les arguments appliqués à ifmoins qu'ils ne soient retournés

C'est du code-golf, donc l'interprète avec le plus petit nombre d'octets gagne!

Haskell, 1370 1263 1179 1128 1163 1107 1084 octets * 0,8 * 0,85 = 737,12

import Text.Parsec
data V=I Int|L[V]|T|F|P[V]|X|A|S|M|D|U|E|Q|J|K|C|N|W deriving Eq
m Q=0;m C=3;m f|f`elem`[J,K,N,W]=1;m _=2
l=length
x v=[n|I n<-v]
y v=[l|L l<-v]
z v=[0<1|T<-v]++[1<0|F<-v]
(&)f=l.f>>=(.l).(==)
b a|a=T|0<1=F
s(I n)=show n
s(L v)='(':tail(v>>=(' ':).s)++")"
s T=d!!0;s F=d!!1;s _="error"
i(L v)=e$i%v
i v=v
e(P v:a)=e$v++a
e(f:a)|m f>l a=P(f:a)
e(A:a)|x&a=I$sum$x a|y&a=L$concat$y a|z&a=b$and$z a
e(S:a)|x&a=I$f$x a|z&a=b$or$z a
e(M:a)|x&a=I$product$x a
e[M,v,I n]=e$A:replicate n v
e(D:a)|x&a=I$v$x a
e[D,L v,f]=L$map(\a->e[f,a])v
e[U,I a,I b]=I$a`mod`b
e(E:a:v)=b$all(==a)v
e(Q:a)=L a
e[J,I a]=I$a+1
e[J,L[]]=L[]
e[J,L v]=L$last v:init v
e[K,I a]=I$a-1
e[K,L v]=L$drop 1 v++take 1 v
e[C,a,b,c]|a`elem`[I 0,L[],F]=c|0<1=b
e[N,a]=e[C,a,F,T]
e[W,L v]=I$l v
e _=X
f(a:b)=a-sum b
v(a:b)=foldl div a b
(%)f=fmap f
p=k$choice$try%([(I .read)%many1 digit,L%between(w"(")(k$w")")(many$try p)]++zipWith((.return).(>>).w)d[T,F,A,S,M,D,U,E,Q,J,K,C,N,W])
k=(spaces>>)
w=string
d=words"true false + - * / % = list inc dec if not len"
g=either show(s.i).parse p""
main=interact g

Programme complet, lecture stdinet écriture à stdout. gest également la version fonctionnelle.

Implémente à la fois des fonctions partielles et une évaluation paresseuse de if.

Exemples d'exécutions (de la version de fonction):

λ: g "(list 1 2 3 (list 4 5 true))"
(1 2 3 (4 5 true))

λ: g "(/ 4000 (+ 1 2 3 4 (* 5 8)))"
80

λ: g "(+ (not (- (len (list 5 6 7)) (/ 10 3))) true)"
true

λ: g "(if (           len (list )  ) 4 (if    (+ (= 8 8    8) (not (list 4))) 8 5))"
5

λ: g "(if false (/ 1 0) 5)"
5

λ: g "((+ 2) 3)"
5

λ: g "(/ (list 1 2 3) (+ 2))"
(3 4 5)

A maintenant tous les tests unitaires de la description:

λ: runTests 
passed: g "(+ 1 2 3 4 5)" ==> 15
passed: g "(+ (list 1 2) (list 3 4))" ==> (1 2 3 4)
passed: g "(+ true true true)" ==> true
passed: g "(- 8 4 3)" ==> 1
passed: g "(- 0 123)" ==> -123
passed: g "(- true false false true false)" ==> true
passed: g "(* 1 2 3 4 5)" ==> 120
passed: g "(* (list 1 2 3) 2)" ==> (1 2 3 1 2 3)
passed: g "(/ 100 10 3)" ==> 3
passed: g "(/ (list 1 2 3) inc)" ==> (2 3 4)
passed: g "(% 4 2)" ==> 0
passed: g "(= 0 0 0)" ==> true
passed: g "(= 0 false (list))" ==> false
passed: g "(list 3 4 (list 5))" ==> (3 4 (5))
passed: g "(inc 1)" ==> 2
passed: g "(inc (list 1 2 3))" ==> (3 1 2)
passed: g "(dec 1)" ==> 0
passed: g "(dec (list 1 2 3))" ==> (2 3 1)
passed: g "(if (not (list 1)) 8 9)" ==> 9
passed: g "(not (list))" ==> true
passed: g "(len (list 4 2 true (list 3) (list)))" ==> 5
passed: g "(list 1 2 3 (list 4 5 true))" ==> (1 2 3 (4 5 true))
passed: g "(/ 4000 (+ 1 2 3 4 (* 5 8)))" ==> 80
passed: g "(+ (not (- (len (list 5 6 7)) (/ 10 3))) true)" ==> true
passed: g "(if (           len (list )  ) 4 (if    (+ (= 8 8    8) (not (list 4))) 8 5))" ==> 5
passed: g "(if false (/ 1 0) 5)" ==> 5
passed: g "((+ 2) 3)" ==> 5
passed: g "(/ (list 1 2 3) (+ 2))" ==> (3 4 5)

Python 2, 1417 * 0,8 * 0,85 = 963,56

from operator import*
A=type;K="list"
def E():print"E";exit()
def R(G):
 len(G)or E();T=G.pop(0);L=[]
 if"("==T:
  G or E()
  while")"!=G[0]:L+=[R(G)];G or E()
  G.pop(0);return L
 if")"==T:E()
 try:
  x=eval(T.title())
  if Q(x)<2:return x
  E()
 except:return T
H="+ - * / = % if inc dec not len"
Z=lambda y:lambda x:reduce(y,x)
D=dict(zip(H.split(),[[sum,any,0,lambda x:sum((y[1:]for y in x),[K])],[Z(sub)],[Z(mul),all,0,lambda x:x[0][:1]+x[0][1:]*x[1]],[Z(div),lambda x:[K]+map(lambda z:S([x[1],z]if Q(x[1])==2else x[1]+[z]),x[0][1:])],[lambda x:len(set(map(str,x)))<2]*6,[lambda x:x[0]%x[1]],[lambda x:S(x[2])if S(x[0])in[0,[K]]else S(x[1])]*6,[lambda x:x[0]+1,0,0,lambda x:x[0][:1]+x[0][-1:]+x[0][1:-1]],[lambda x:x[0]-1,0,0,lambda x:x[0][:1]+x[0][2:]+[x[0][1]]],[lambda x:x[0]in[0,[K]]]*6,[0]*3+[lambda x:len(x)-1]]))
H=H[:15]+H+" if"
def Q(x):
 t=A(x);w=int,bool,str
 if t in w:return w.index(t)
 if t==list and x:return 5-(2*(x[0]==K)+(str==A(x[0])and len(x)<H.count(x[0])+1))
 E()
def S(G):
 if Q(G)<2:return G
 G or E();c=G[0];r=G[1:];c==K or r or E()
 if c!="if":r=[x if Q(x)in{2,4}else S(x)for x in r]
 if c==K:return[c]+r
 k=map(Q,r);m=min(k);M=max(k);v=[m,[-1,3][{m,M}=={4,5}]][m!=M]
 try:return D[c][v](r)
 except:E()
def C(x):return"(%s)"%" ".join(map(C,x))if A(x)==list else str(x).lower()
def I(G):
 for c in"+-*/%=()":G=G.replace(c," %s "%c)
 return C(S(R(G.strip().split())))
print I(raw_input())

Refonte complète. Si vous souhaitez voir les versions précédentes, consultez l' historique des modifications .

Il y a beaucoup plus à jouer au golf. J'y travaille lentement.

Avec zlib / base64, nous obtenons 1093 * 0,8 * 0,85 = 743,24 :

import base64,zlib
exec zlib.decompress(base64.b64decode("eJx9VE1P4zAQvedXGEuV7MbttgX2kOADAtSugANbTljWKqSuNku+5Lg0BfHfd8ZJCwjt9tLpdN6bmTczXtuqIFVtbOIqS7KirqwbBufS7WoTX0uaZ42jwcqsyRXjUW2z0tErGps2c4x7/08251FAclOCARwQF9/L+biuajbh8Y1UOiDZmjIq5T0EkjnposDc/s5yQzk9knM10dFNKBXS6fhDzIHJGrexJbnxbNyz+Qhnd0jbSvOc5Ox+7DKXG8YRm63JHWv52SzqwS04Pci0qand3n0fLCQNyYgMyTciyQCBWZmSlUlJWTlsjgYPMk+Kx1VCdlFvtIBfbVLDdqLlwaVcZaljL1nNFuOmzlEhoVSzKURS7sREHFDgYmynppFeQ5s7SEVaCL3WXAv1wJrNY2cUm5yLJM8/YlsQSkVTHXoDKIatmmofvsqe+Xsg0IVFUrPe8RItmcJQ8aI7WcDmUs5M3hiCP0L1ornY02IFBy4cbmMcQ77GWeiWg6h6+P1DDAIHfS0H5xLSzDSHhGhNwCrVBDvVPu2yq+IrUTiFnv/Z9Qjq2/c/+pwQvaP/gmeAVR1Yf4EeyvMlTfTwOPysQssxISzXQi6A81SHi5DiQvpbwGWDXXTyHIx4K+FaxGNV5QJEw7UlDme93a/ddpyVK9Myx7s/pcRzI0m58qvlY05HbDb02kl5zUOUXyI9iomBXVFni3FabUrX+cMpbv9Vf6DL7kD90OcfbmEeHE4xTv0Bxha+QFv4Ka/xL3s4Q0CnR5JCo5GVqt1fVla+zsTJ236YHPe5xR6t7jBA1OdTqQ5BhCeJS3QnLI8LWWQle+LxLfhaNJ6lKgSMVxxr9VqI2zcpX0/E6ZvWqjiSt7o79r7+S2BUz5rZ93Pet3yBc+jCKBs0nA4ooeM/FaTD7Be4wFAdTqnX3HcA2oJnnFdbY3umH5142FcKfdFwNPw2kIzTaA5vnDV1nsD9p4KSQUPoIIVa+vIu2JLBYzYGUngR+P5FgE/gn1Ggtsn2V1bWG3T/BUW+qRU="))

Remarque: Si vous voyez mon score augmenter, c'est probablement parce que j'ai trouvé quelques bugs

Lisp commun, 868 octets * 0,85 = 737,8

Est-ce de la triche d'implémenter Lisp avec Lisp? Encore beaucoup à optimiser ici.

(SETF (READTABLE-CASE *READTABLE*) :PRESERVE)(PRINC(LABELS((B(X)(FIND X'(true false)))(R(X)(IF X'true'false))(V(X)(MEMBER X'(0()false)))(A(&REST X)(R(NOTANY #'V X)))(O(&REST X)(R(NOTEVERY #'V X)))(E(X &KEY N)(IF(LISTP X)(ECASE(FIRST X)(+(APPLY(IF(EVERY'NUMBERP #1=(MAPCAR(IF N #'IDENTITY #'E)(CDR X)))'+(IF(EVERY'LISTP #1#)'APPEND #'A))#1#))(-(APPLY(IF(EVERY'NUMBERP #1#)'- #'O)#1#))(*(IF(LISTP #2=(CAR #1#))(LOOP FOR I TO(1-(CADR #1#))APPEND #2#)(APPLY'* #1#)))(/(IF(LISTP #2#)(LOOP FOR I IN #2#COLLECT(E `(,(CADR #1#),I):N T))(REDUCE'FLOOR #1#)))(%(APPLY'MOD #1#))(=(R(LOOP FOR I IN(CDR #1#)ALWAYS(EQUAL I #2#))))(list #1#)(inc(IF(LISTP #2#)(APPEND(LAST #2#)(BUTLAST #2#))(1+ #2#)))(dec(IF(LISTP #2#)(APPEND(CDR #2#)`(,(FIRST #2#)))(1- #2#)))(if(IF(V(E(CADR X)))(E(CADDDR X))(E(CADDR X))))(not(R(V #2#)))(len(LENGTH #2#)))X)))(OR(IGNORE-ERRORS(OR(E(READ))"()")):E))

Imprime un E en cas d'erreur d'entrée. Exemples de cycles:

$ sbcl --script glisp.lisp
(list 1 2 3 (list 4 5 true))
(1 2 3 (4 5 true))

$ sbcl --script glisp.lisp
(/ 4000 (+ 1 2 3 4 (* 5 8)))
80

$ sbcl --script glisp.lisp
(+ (not (- (len (list 5 6 7)) (/ 10 3))) true)
true

$ sbcl --script glisp.lisp
(if (           len (list )  ) 4 (if    (+ (= 8 8    8) (not (list 4))) 8 5))
5

$ sbcl --script glisp.lisp
(this is an error)
E

$ sbcl --script glisp.lisp
(if (% 4 2) (this is an error) 42)
42

Haskell, 972

r=fst.f
f('(':s)|(f:a,b)<-g s=(f%filter(/="")a,b)
f s=span(`notElem`" ()")s
j=dropWhile(==' ')
g""=([],"")
g s|')':l<-r=([x],l)|(y,t)<-g$j r=(x:y,t)where(x,r)=f$j s
"%"%c=show$foldr(mod.read)(maxBound::Int)c
"+"%c|t(c!!0)<1="(list "++tail(c>>=(' ':).drop 6.init)++")"|t(c!!0)<2=show$sum$map read c|0<1=i$all((=='t').head)c
"-"%c|t(c!!0)<2=show$foldl1(-)$map read c|0<1=i$any((=='t').head)c
"*"%c=fst$f$"(+ "++unwords([1..read$last c]>>init c)++")"
"="%c=i$all(==c!!0)c
"/"%c|t(c!!0)<1,[a,b]<-c="list"%map(\x->b%[x])(fst$g$drop 6 a)|0<1=show$foldl1 div$map read c
"if"%[p,a,b]|elem p["0","()","false"]=b|0<1=a
"list"%c="(list "++unwords c++")"
"len"%[c]=show$length(words c)-1
"inc"%[c]|t c>0=show$read c+1|([],_)<-g$drop 6 c="(list)"|(x,_)<-g$drop 6 c="list"%(last x:init x)
"dec"%[c]|t c<1,(x,_)<-g$drop 6 c="list"%(drop 1 x++take 1 x)|0<1=show$read c-1
"not"%[c]="if"%[c,"false","true"]
s%c="?"
i p|p="true"|0<1="false"
t('(':_)=0
t(c:s)|c<':',c>'/'=1|elem c"th"=2
t _=3

une solution assez hacky. cela stocke tout sous forme de chaînes sous forme prête à la sortie - leurs types peuvent être distingués par leur première lettre - 0..9pour les nombres, les (listes tou les fbooléens, et tout le reste pour les fonctions.

pour exécuter, utilisez la rfonction.