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ónfy un valorxde la pila, y se aplicafax. Siftiene arity 1, la listaf(x)se agrega al frente de la pila. Si tiene arity, se empujan > 1una nueva(n-1)función -aryga la pila. Toma entradas y retornos .x1,x2,...,xn-1f(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 valorxse asigna a[x,x].>( shift ) empuja a la pila una función unaria que toma unanfunción -aryf, y devuelve una(n+1)función -arygque ignora su primer argumentox, invocaflos restantes y agregaxdelante del resultado. Por ejemplo,shift(clone)es una función binaria que toma entradasa,by retornos[a,b,b]./( fork ) empuja a la pila una función ternaria que toma tres entradasa,b,cy devuelve[b]siaestá en blanco, y de lo[c]contrario.$( Llamada ) empuja a la pila de una función binaria que aparece una funciónfy un valorx, y se aplicafaxexactamente como!lo hace..( cadena ) empuja a la pila una función binaria que muestra dos funcionesfygdevuelve su composición: una funciónhque tiene la misma aridad quef, y que toma sus entradas normalmente, se aplicafa ellas y luego se aplica completamentegal resultado (llamadas tantas veces como lo dicta su arity), con elementos no utilizados de la salida defpermanecer en el resultado deh. Por ejemplo, suponga quefes una función binaria que clona su segundo argumento yges 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,fprimero se aplica aa,b, produciendo[a,b,b], luegogse 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 imprime0si estaba en blanco y1si 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 0so 1s 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 0sy 1s. 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 ny devolver al menos ncaracteres 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 acopie 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,xcomo 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 1s 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 dentales aplicaciones, la función restante tenía solo un argumento, y en ese punto se computaf(z1, z2, ..., zn)(es decir, sefaplica a todos los argumentos en los que se cursó), lo que empuja algunos valores nuevos, y luego consume inmediatamente losmvalores de la pila y los invocag..funciona exactamente como Martin describió, excepto que sifdevuelve una lista demvalores 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 defse usa como una pila temporal, en la quegse empuja y se aplicamveces!, 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!).@ucomo 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 0y nox==0(ox<1)? 4) No te molestes en especificarRuntimeError, soloexceptservirá. 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-1la condición (0 / false sixes 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==1es 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.RuntimeErrortiempo 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 argumentosxalfprefijarxel contenido def, empujarlo hacia atrás en la pila y nombrar una copia del resultadofun.Luego envuelve toda la pila como una matriz.
.runandhidees 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. Eldictcomando empuja un nuevo diccionario en la pila de dict, reduciendo el alcance de los nombres definidos dentro hasta queendlo desactive. También reemplaza=only(el operador de salida que uso@) con uno ficticio, suprimiendo la salida durante la ejecución de prueba.stoppedes el equivalente PostScript de latrydeclaració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 sefuncompleta 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.
kes 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 los0s 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 laexeclí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 ayk.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, sayyy chainnusan 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 nombreblankdebesto, esto se rompió, porque ahora comparó los parámetrosay, enbcambio,acon el espacio en blanco. Me llevó algo de tiempo depurar).La
zfunción se comparte porque mi IDE ejecuta esas funciones: la herramienta de línea de comandos también puede ejecutar funciones no compartidas.fuente