EDITAR: Como algunos de ustedes sospecharon, había un error en el intérprete oficial: .
se invirtió el orden de composición . Tenía dos versiones del intérprete y usé la incorrecta aquí. Los ejemplos también se escribieron para esta versión incorrecta. He arreglado el intérprete en el repositorio y los ejemplos a continuación. La descripción de >
también fue un poco ambigua, así que lo arreglé. Además, las disculpas por haber tardado tanto, quedé atrapado en algunas cosas de la vida real.
EDIT2: Mi intérprete tuvo un error en la implementación .
que se reflejó en los ejemplos (confiaban en un comportamiento indefinido). El asunto ha sido arreglado.
Introducción
Shift es un lenguaje de programación funcional esotérico que hice hace un par de años, pero que publiqué hoy. Está basado en la pila, pero también tiene curry automático como Haskell.
Especificación
Hay dos tipos de datos en Shift:
- Funciones, que tienen una aridad positiva arbitraria (número de entradas) y que devuelven una lista de salidas. Por ejemplo, una función que duplica su única entrada tiene arity 1, y una función que intercambia sus dos entradas tiene arity 2.
- Los espacios en blanco, que son todos idénticos y no tienen otro propósito que no ser funciones.
Un programa Shift consta de cero o más comandos , cada uno de los cuales es un único carácter ASCII. Hay 8 comandos en total:
!
( aplicar ) muestra una funciónf
y un valorx
de la pila, y se aplicaf
ax
. Sif
tiene arity 1, la listaf(x)
se agrega al frente de la pila. Si tiene arity, se empujan > 1
una nueva(n-1)
función -aryg
a la pila. Toma entradas y retornos .x1,x2,...,xn-1
f(x,x1,x2,...,xn-1)
?
(en blanco ) empuja un espacio en blanco a la pila.+
( clone ) empuja a la pila una función unaria que duplica su entrada: cualquier valorx
se asigna a[x,x]
.>
( shift ) empuja a la pila una función unaria que toma unan
función -aryf
, y devuelve una(n+1)
función -aryg
que ignora su primer argumentox
, invocaf
los restantes y agregax
delante del resultado. Por ejemplo,shift(clone)
es una función binaria que toma entradasa,b
y retornos[a,b,b]
./
( fork ) empuja a la pila una función ternaria que toma tres entradasa,b,c
y devuelve[b]
sia
está en blanco, y de lo[c]
contrario.$
( Llamada ) empuja a la pila de una función binaria que aparece una funciónf
y un valorx
, y se aplicaf
ax
exactamente como!
lo hace..
( cadena ) empuja a la pila una función binaria que muestra dos funcionesf
yg
devuelve su composición: una funciónh
que tiene la misma aridad quef
, y que toma sus entradas normalmente, se aplicaf
a ellas y luego se aplica completamenteg
al resultado (llamadas tantas veces como lo dicta su arity), con elementos no utilizados de la salida def
permanecer en el resultado deh
. Por ejemplo, suponga quef
es una función binaria que clona su segundo argumento yg
es call . Si la pila contiene[f,g,a,b,c]
y nosotros.!!
, entonces contiene[chain(f,g),a,b,c]
; si lo hacemos a!!
continuación,f
primero se aplica aa,b
, produciendo[a,b,b]
, luegog
se aplica a los primeros dos elementos de eso ya que su arity es 2, produciendo[a(b),b]
, y la pila finalmente lo será[a(b),b,c]
.@
( digamos ) empuja una función unaria que simplemente devuelve su entrada e imprime0
si estaba en blanco y1
si era una función.
Tenga en cuenta que todos los comandos, excepto !
simplemente insertar un valor en la pila, no hay forma de realizar la entrada, y la única forma de generar algo es usar @
. Un programa se interpreta evaluando los comandos uno por uno, imprimiendo 0
so 1
s cada vez que se llama "say", y saliendo. Cualquier comportamiento no descrito aquí (aplicar un espacio en blanco, aplicar una pila de longitud 0 o 1, llamar "cadena" en un espacio en blanco, etc.) no está definido: el intérprete puede fallar, fallar silenciosamente, pedir información o lo que sea.
La tarea
Su tarea es escribir un intérprete para Shift. Debe tomar de STDIN, línea de comando o argumento de función un programa Shift para ser interpretado, e imprimir en STDOUT o devolver la salida resultante (posiblemente infinita) de 0
sy 1
s. Si escribe una función, debe poder acceder a las salidas de longitud infinita de alguna manera (generador en Python, lista diferida en Haskell, etc.). Alternativamente, puede tomar otra entrada, un número n
y devolver al menos n
caracteres de la salida si es más larga que n
.
El conteo de bytes más bajo gana, y las lagunas estándar no se permiten.
Casos de prueba
Este programa Shift imprime 01
:
?@!@@!
Comenzando desde la izquierda: presione un espacio en blanco, presione say , luego aplique el say al espacio en blanco. Esto da salida 0
. Luego, presione decir dos veces y aplique el segundo decir al primero. Esto da salida 1
.
Este programa se repite para siempre, sin producir resultados:
$+.!!+!!
Presione call y clone , luego aplique chain a ellos (necesitamos dos !
s ya que chain es una función binaria). Ahora la pila contiene una función que toma un argumento, lo duplica y llama a la primera copia del segundo. Con +!!
, duplicamos esta función y la llamamos a sí misma.
Este programa imprime 0010
:
?@$.++>!.!!.!!.!!!!+?/!!!@!@>!!!
Empuje un espacio en blanco y diga . Luego, componga una función binaria que copie su segundo argumento b
, luego a
copie el primero y lo componga consigo mismo, luego aplique la composición a la copia de b
, regresando [a(a(b)),b]
. Aplíquelo a say y blank, luego aplique say a los dos elementos restantes en la pila.
Este programa imprime 0
. Para cada uno !!!
que anexe, imprime un adicional 0
.
?@+$>!>!+>!///!!>!>!.!!.!!.!!+!!!!
Empuje un espacio en blanco y diga . Luego, componga una función ternaria que tome f,g,x
como entradas y retornos [f,f,g,g(x)]
. Clone esa función y aplíquela a sí misma, digamos , y al espacio en blanco. Esta aplicación no cambia la pila, por lo que podemos volver a aplicar la función tantas veces como queramos.
Este programa imprime la secuencia infinita 001011011101111...
, donde el número de 1
s siempre aumenta en uno:
@?/!@>!??/!!>!+.!!.!!.!!.+>!.!!$$$$+$>!>!$>!>!+>!$>!>!>!+>!>!///!!>!>!>!.!!.!!.!!.!!.!!.!!.!!.!!.!!.!!+!!!!!
El repositorio contiene una versión anotada.
fuente
f(x1, x2, ..., xn)
yg(y1, y2, ..., ym)
. Llamar los.
hace saltar a ambos y empuja una funciónh(z1, z2, ..., zn)
. Ahora puedes consumir todos esos argumentos al graduarlos gradualmente!
. Después den
tales aplicaciones, la función restante tenía solo un argumento, y en ese punto se computaf(z1, z2, ..., zn)
(es decir, sef
aplica a todos los argumentos en los que se cursó), lo que empuja algunos valores nuevos, y luego consume inmediatamente losm
valores de la pila y los invocag
..
funciona exactamente como Martin describió, excepto que sif
devuelve una lista dem
valores inferiores a , el resultado no está definido (la composición tiene aridadn
, por lo que no puede comer más argumentos de la pila). Esencialmente, la salida def
se usa como una pila temporal, en la queg
se empuja y se aplicam
veces!
, y el resultado se agrega a la pila principal.Respuestas:
Python 2,
752667534506445436427404398393 bytesEsto no es para nada corto ... pero hice lo mejor que pude. Cualquier sugerencia de golf sería muy apreciada ...
EDITAR6: Esto es ahora un script en lugar de una función. Guárdelo en un archivo (shift.py, forex), luego ejecútelo con
$ python shift.py '<my_input>'
. Asegúrese de poner la entrada entre comillas simples, o bash se volverá loco con los caracteres de entrada.EDIT7: Aaaaaa y ... ya no es legible. Pero me deshice de 23 bytes más, así que eso es bueno, supongo. También publicaré una versión sin golf.
EDITAR8: Un golf más, gracias a @Zgarb.
EDITAR: ¡gracias a @DLosc por la ayuda en el golf! Logró reducirlo en 85 bytes.
EDIT2: recorta una tonelada de envoltorios innecesarios y lo dejó caer en otros 133 bytes.
EDIT3: ... y 28 más gracias a @ Sp3000 y @orlp en el chat.
EDIT4: con la ayuda de @orlp & @ Sp3000, eliminé todos los decoradores y ahora es 61 bytes más corto.
EDIT5: ayúdame, no puedo dejar de jugar al golf ... 9 bytes más desaparecidos. Deshacerse de la declaración de impresión final ahorraría otros 7, pero si ejecuta m () en un bucle, toda la salida está en la misma línea ... ¿está bien?
Aquí hay una versión sin golf:
La idea básica es que la lista de Python funciona muy bien como una pila, y al almacenar
u=k.append
, no solo guardo los caracteres,sino que también puedo usarlos(¡ya no más!).@u
como decorador para empujar funcionesComo las dos funciones que actúan sobre las funciones de n-arity necesitan poder aceptar un número arbitrario de argumentos, tuve que usar
*args
, lo que significaba que mi plan original de seguimiento f.func_code.co_argcount tenía que ser reemplazado por un arity atributodecorador.En términos de manejo de programas infinitos, el intérprete se ejecuta hasta alcanzar la profundidad recursiva máxima; el controlador RuntimeError en la parte inferior hace que salga silenciosamente en ese punto e imprime la cadena de salida actual.
Casos de prueba:
fuente
['1','0'][...]
con solo'10'[...]
. 3) ¿Por quéx is 0
y nox==0
(ox<1
)? 4) No te molestes en especificarRuntimeError
, soloexcept
servirá. 5) Dado que está utilizando Python 2, las pestañas y los espacios cuentan como diferentes niveles de sangría, feo, pero debería ahorrarle ~ 25 bytes.x.a==1and x(y)or u(a(x.a-1)(b.partial(x,y)))
los operadores lógicos todavía están en cortocircuito, pero usan menos caracteres que el ternario. A continuación, guarde otro byte mediante el uso dex.a-1
la condición (0 / false six
es 1, distinto de cero / verdadero lo contrario) y el canje de la 'continuación' y 'lo demás' expresiones:x.a-1and u(a(x.a-1)(b.partial(x,y)))or x(y)
. (Tengo que jugar al golf un poco más ahora que me has pasado ...; ^))x.a==1
es cierto perox(y)
devuelve algo falso, también intenta evaluarlou(...)
. ¡Pero parece que no necesita guardar los 3 bytes miserables que le habrían dado! Lo admito, señor: me ha superado.RuntimeError
tiempo mientras que el mío solo le pide al usuario que redirija stderr ... por lo que probablemente incluso tengamos dudas. ; ^)*_
las lambdas?Ghostscript
Todavía no he jugado al golf, ya que todavía necesito resolver la función de análisis.
Esta implementación usa
_
y en:
lugar de>
y/
, y requiere que todos los caracteres del programa se separen con espacios. Esto se debe>
y/
no son nombres válidos en Postscript, y los operadores no son auto-delimitación, pero este problema se solucionará cuando escribo el analizador.La primera parte del código debe ser bastante transparente, ya que simplemente está repitiendo las definiciones de las funciones del operador. La magia ocurre en la definición de
!
.La forma en que
!
funciona es simple: en primer lugar, agrega argumentosx
alf
prefijarx
el contenido def
, empujarlo hacia atrás en la pila y nombrar una copia del resultadofun
.Luego envuelve toda la pila como una matriz.
.runandhide
es una extensión de Ghostscript para ejecutar código de espacio aislado, ocultando el contenido de la matriz anterior del procedimiento en el que se invoca. Eldict
comando empuja un nuevo diccionario en la pila de dict, reduciendo el alcance de los nombres definidos dentro hasta queend
lo desactive. También reemplaza=only
(el operador de salida que uso@
) con uno ficticio, suprimiendo la salida durante la ejecución de prueba.stopped
es el equivalente PostScript de latry
declaración que se encuentra en otros lenguajes, y devuelve verdadero si su procedimiento arrojó un error, y falso si se ejecutó hasta su finalización.Una vez que se completa la ejecución de prueba
fun
, el programa restaura la pila original de la matriz oculta y, si sefun
completa sin error, la ejecuta de manera real, manteniendo la salida.fuente
Python3,
685670634633 bytesEstoy bastante seguro de que es lo más largo que he jugado al golf. Solía ser algo legible, pero seguir los consejos de @ sirpercival ha eliminado ese inconveniente.
k
es la pila, que contiene funciones representadas como cadenas como"h(0,0)"
(que es c h ain ). Cuando una función se pasa como argumento a otra función, se ponerepr
'd y todos los números incrementa:"h('h(1,1)',0)"
. Una vez que todos los0
s se reemplazan en una función, todo se pasa aeval
, llamando a la función Python apropiada, la mayoría de las cuales son funciones lambda generadas a partir de la cadena grande en la línea 6 por laexec
línea 7.Obtener múltiples niveles de funciones anidadas incrementadas, citadas y escapadas correctamente fue el mayor dolor de cabeza. Podría ahorrar un poco más en las operaciones de expresiones regulares si pudiera asumir que el anidamiento de funciones no avanzará más allá de los 9 niveles, pero como se señaló en los comentarios, probablemente no sea una suposición segura.
Versión anterior sin codificar del código:
El único defecto potencial de esta implementación es que utiliza la recursividad, por lo que los programas que deberían ser infinitos alcanzan la profundidad máxima de recursión con bastante rapidez. (Probablemente desee redirigir stderr cuando ejecuta un programa infinito; de lo contrario, el seguimiento de la pila inundará la salida real). Aparte de eso, todo parece estar funcionando.
fuente
lambda a
yk.pop()
.k.pop()
todos modos, hice la situación un poco menos repetitiva)Ceilán,
116710571031No lo entiendo tan corto como las versiones de python mono-tipadas ...
import ceylon.language.meta.model{N=Function}import ceylon.collection{H=HashMap}interface D of F|b{}object b satisfies D{}class F(shared Integer a,[D+](D+)f,[D*]c=[])satisfies D{shared[D+]o(D i){[D+]s=[i].prepend(c);return a==1then f(*s)else[F(a-1,f,s)];}shared[D+]y([D+]i){return f(*i.prepend(c));}}F m<A>(N<[D+],A>f)given A satisfies[D+]=>F(f.parameterTypes.size,(D+i)=>f.apply(*i));[D,D]e(D x)=>[x,x];[F]t(F f){[D+]g(D+i){assert(is[D+]r=i.rest);return[i[0],*f.y(r)];}return[F(f.a+1,g)];}[D]k(D a,D d,D c)=>a==b then[d]else[c];[D+]l(F a,D x)=>a.o(x);[F]n(F f,F g){[D+]h(D+i){[D+]r=f.y(i);assert(is[D+]d=r[0:g.a]);return g.y(d).append(r[g.a...]);}return[F(f.a,h)];}[D]y(D x){process.write(x==b then"0"else"1");return[x];}class I(){variable D[]s=[];value c=H{'?'->b,'+'->m(`e`),'>'->m(`t`),'/'->m(`k`),'$'->m(`l`),'.'->m(`n`),'@'->m(`y`)};shared void r(Character i){if(i=='!'){assert(is F f=s[0],is D x=s[1]);s=f.o(x).append(s[2...]);}else{assert(is D d=c[i]);s=[d].append(s);}}}shared void z(){process.readLine()?.collect(I().r);}
Aquí hay una versión formateada (y comentada) del mismo código (con espacios / líneas nuevas / comentarios se convierte en 4867 bytes):
Las funciones clone
e
, shiftt
, forkk
, calll
, sayy
y chainn
usan la última letra de los nombres para la versión abreviada, porque eso dio menos colisiones. (Trivia: la bifurcación se definió originalmente de esta manera:[Data] fork(Data a, Data b, Data c) => a == blank then [b] else [c];
cuando cambié el nombreblank
deb
esto, esto se rompió, porque ahora comparó los parámetrosa
y, enb
cambio,a
con el espacio en blanco. Me llevó algo de tiempo depurar).La
z
función se comparte porque mi IDE ejecuta esas funciones: la herramienta de línea de comandos también puede ejecutar funciones no compartidas.fuente