Desafío

Su desafío es diseñar un intérprete para un lenguaje similar al lisp, que a partir de ahora será acuñado: GLisp . El código del programa para GLisp consistirá en una cantidad arbitraria de expresiones anidadas indicadas entre paréntesis, en la siguiente forma:

(func arg1 arg2 ...)

Tenga en cuenta que el intérprete debe permitir espacios en blanco extraños antes y después de corchetes, funciones y argumentos.

Tipos

Implementará cuatro tipos, Integer, List, Boolean y Function. Los valores enteros y booleanos se pueden insertar explícitamente en el código fuente con su propia sintaxis. Su intérprete debe suponer que una serie de caracteres numéricos denota un entero (no es necesario que implemente una sintaxis para insertar explícitamente enteros negativos). Su intérprete también debe asumir eso truey falsese designan valores booleanos. Las funciones no pueden ser definidas explícitamente por el usuario, y siempre devolverán un valor único (una Lista de cualquier longitud cuenta como un valor único).

Las funciones

Se requieren las siguientes funciones para ser implementadas, y están en el formato Función , Arity . Si un Arity nes procesado por un signo más, entonces eso denota no más argumentos. Puede suponer que todos los argumentos dados a una función son del mismo tipo, a menos que se especifique lo contrario. También puede suponer que si no se especifica ningún comportamiento para un tipo certian, puede suponer que ningún argumento de esa función será nunca de ese tipo. Se hará referencia a los argumentos en el siguiente diagrama:

(func argument1 argument2 ... argumentn)

• + , 2+

  • Si todos los argumentos son del tipo Integer , debe devolver la suma de los argumentos
  • Si todos los argumentos son del tipo Lista , debe devolver la concatenación de los argumentos en orden ascendente ( arg1+arg2+ ...)
  • Si todos los argumentos son del tipo booleano , debe devolver la secuencia lógica de todos los argumentos
  • (+ 1 2 3 4 5) -> 15
  • (+ (list 1 2) (list 3 4)) -> (list 1 2 3 4)
  • (+ true true true) -> true

• - , 2+

  • Si todos los argumentos son del tipo Integer , debe devolver la diferencia de los argumentos ( arg1-arg2- ...)
  • Si todos los argumentos son del tipo booleano , debe devolver el lógico Cualquiera de la secuencia de argumentos
  • (- 8 4 3) -> 1
  • (- 0 123) -> -123
  • (- true false false true false) -> true

• * , 2+

  • Si todos los argumentos son de tipo Integer , debe devolver el producto de los argumentos
  • Si un argumento es de tipo Lista y el otro es de tipo Entero (puede suponer que estos serán los únicos argumentos dados), debe devolver una nueva Lista con los elementos en arg1repetidas arg2ocasiones.
  • (* 1 2 3 4 5) -> 120
  • (* (list 1 2 3) 2) -> (list 1 2 3 1 2 3)

• / , 2+

  • Si todos los argumentos son del tipo Integer , debe devolver el cociente de los argumentos (arg/arg2/ ... ) (puede suponer que la división se realiza secuencialmente y que la porción decimal en cada paso se trunca)
  • Si un argumento es de tipo Lista y el otro es de tipo Función , debe devolver la Lista resultante después de que arg2se haya asignado sobre cada valor
  • (/ 100 10 3) -> 3
  • (/ (list 1 2 3) inc) -> (list 2 3 4)

• % , 2

  • Si todos los argumentos son del tipo Entero , debe devolver el módulo de los argumentos
  • (% 4 2) -> 0

• = , 2+

  • Si tanto el tipo como el valor de todos los argumentos son iguales, debe devolver verdadero. De lo contrario, devuelve falso.
  • (= 0 0 0) -> true
  • (= 0 false (list)) -> false

• lista , 0+

  • Debe devolver una lista de todos los argumentos, independientemente del tipo. Si no se dan argumentos, debe devolver una lista vacía
  • (list 3 4 (list 5)) -> (list 3 4 (list 5))

• inc , 1

  • Si el argumento es de tipo Entero , debe devolver el Entero incrementado en uno
  • Si el argumento es de tipo Lista , debe devolver la Lista girada en sentido horario una sola rotación
  • (inc 1) -> 2
  • (inc (list 1 2 3)) -> (list 3 1 2)

• dic , 1

  • Si el argumento es de tipo Entero , debe devolver el Entero decrementado en uno
  • Si el argumento es de tipo Lista , debe devolver la Lista girada en sentido antihorario una sola rotación
  • (dec 1) -> 0
  • (dec (list 1 2 3)) -> (list 2 3 1)

• si , 3

  • Si se le dan tres argumentos de cualquier tipo: si el valor de verdad de arg1es verdadero, devuelve arg2, de lo contrario devuelvearg3
  • (if (not (list 1)) 8 false) -> false

• no 1

  • Si se le da un argumento de cualquier tipo, si el valor de verdad de arg1es False, return true, else return false.
  • (not (list)) -> true

• len , 1

  • Si se le da un argumento de tipo Lista , devuelve la longitud dearg1
  • (len (list 4 2 true (list 3) (list))) -> 5

Tabla de verdad: 0, (list), false -> falsedonde (list)denota una lista vacía. Todo lo demás es true.

Su intérprete puede ser un programa completo que lee la entrada de origen de stdin o un archivo, o una función que toma el origen como una cadena y devuelve el valor de salida.

Si elige el primero, la salida para números enteros es simplemente números, para booleanos es trueo false, y para listas es una secuencia de valores separados por espacios entre corchetes (por ejemplo, (1 2 3 4 (5 6 7))denota (list 1 2 3 4 (list 5 6 7))).

Si elige este último, el valor debe devolverse en el tipo correspondiente del lenguaje de implementación o, si no existe un tipo similar, un tipo personalizado. Las listas se pueden devolver como matrices o vectores si el idioma no tiene un tipo de lista , booleanos deben ser devueltos como un tipo booleano en el lenguaje, o un tipo personalizado si el idioma no es compatible con ellos.

Casos de prueba

(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

Aclaraciones

• Su intérprete puede lidiar con entradas no válidas de cualquier manera que elija, pero no debe lanzar una excepción (sin embargo, puede imprimir un mensaje de error y salir sin problemas)
• Las funciones siempre evaluarán los argumentos de izquierda a derecha
• La entrada inválida es cualquier entrada que sea sintácticamente incorrecta. Esto incluye, entre otros, corchetes no coincidentes, división por cero y funciones parcialmente aplicadas (a menos que vaya por la bonificación)
• Para =, si alguno de los valores es diferente o alguno de los tipos es diferente, regresefalse

Bonos

• Puntuación * 0.8 si admite funciones parcialmente aplicadas. Por ejemplo, ((+ 2) 3)sería lo mismo que (+ 2 3), pero permite cosas como (/ (list 1 2 3) (+ 2)). Puede suponer que una función se aplica parcialmente si recibe menos de su número mínimo de argumentos
• Puntuación * 0.85 si no evalúa los argumentos aplicados a ifmenos que se vayan a devolver

Este es el código de golf, por lo que gana el intérprete con el conteo de bytes más bajo.

Haskell, 1370 1263 1179 1128 1163 1107 1084 bytes * 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

Programa completo, lectura stdiny escritura a stdout. ges la versión de la función, también.

Implementa ambas funciones parciales y una evaluación perezosa de if.

Ejecuciones de muestra (de la versión de la función):

λ: 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)

Ahora tiene todas las pruebas unitarias de la descripción:

λ: 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())

Revisión completa. Si desea ver las versiones anteriores, consulte el historial de edición .

Hay mucho más por jugar al golf. Estoy trabajando lentamente en eso.

Con zlib / base64 obtenemos 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="))

Nota: Si ves que mi puntaje sube, probablemente sea porque encontré algunos errores

Lisp común, 868 bytes * 0.85 = 737.8

¿Es una trampa implementar Lisp con Lisp? Mucho para optimizar aquí, todavía.

(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 una E en caso de un error en la entrada. Ejecuciones de muestra:

$ 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

Una solución bastante hacky. esto almacena todo como cadenas en forma lista para la salida (sus tipos se pueden distinguir por su primera letra) 0..9para números, (para listas,t o fbooleanos y todo lo demás para funciones.

para ejecutar usa la rfunción.