Eso es casi Lisp!

14

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.

globby
fuente
¿Cómo se interpreta (if (not (array 1)) 8 false) -> false?
fiesta
@feersum buena captura, se supone que es 8.
globby
1
¿Cómo debemos evaluar (+ 3 (if false 5))? En términos generales, ¿qué es realmente "no devolver nada"? No especificó ningún tipo de unidad para volver a
ajustar
3
1. ¿Por qué es (+ bool bool...)lógico AND y (- bool bool...)lógico OR? La notación de anillo estándar se usaría +para OR y *para AND. 2. ¿Se pretende que la "entrada no válida" cubra casos como los (/ 2 0)que son sintácticamente correctos? 3. Para =, si los valores no son todos iguales, ¿debería volver false? 4. La definición de notparece ser al revés. 5. ¿Qué son los tokens? Usted dice que el intérprete debe manejar espacios en blanco adicionales, pero no dice en qué espacio en blanco puede confiar. Para preguntas complejas como esta, realmente debería usar el sandbox para que se pueda verificar la especificación.
Peter Taylor
1
no está claro cómo debería funcionar la aplicación parcial: ¿es ((+ 2 3) 4)igual 9o un error? En particular, para las funciones var-arg, no está claro cuándo se debe considerar la aplicación parcial. Se vuelve aún más turbio con cosas como((if true (+ 2 3) (- 5)) 4)
MtnViewMark

Respuestas:

6

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)
MtnViewMark
fuente
b los casos e[K,L _]que podría usar drop 1 como una versión segura taily usar takepara una versión segura de headunir las dos definiciones dee[K,L _]
proud haskeller
puede usar la función notElem.otro consejo: puede hacerlo s=stringy usarlo en lugar de ambos stringy char( s"C"vs. char 'C'). otro consejo: use guardias en lugar de ifs
proud haskeller
Otra cosa que pensé: puedes codificar Maybevalores por listas. Nothinges []y Just xes [x]. Esto se deshace de los constructores largos y añade algunas funcionalidades más: if p then Just x else Nothinges [x|p], (==Nothing)es null, la lista mónada se convierte en la misma que la mónada tal vez, y así sucesivamente.
orgulloso Haskeller
@proudhaskeller ¡Gracias, todos aplicados!
MtnViewMark
4

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

Sp3000
fuente
más de un desafío de código que un código de golf pero aún así, 4872 * 0.8 = 3897,6
Def
3

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
jlahd
fuente
2
siempre que no sea una especie de función eval ...
Def
2

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.

orgulloso Haskeller
fuente