Mierda de cerebro

Brainfuck es un lenguaje de programación esotérico creado en 1993 por Urban Müller.

Notable por su minimalismo extremo, el lenguaje consta de solo ocho comandos simples, un puntero de datos y un puntero de instrucciones. Si bien es completamente Turing completo, no está diseñado para un uso práctico, sino para desafiar y entretener a los programadores. Brainfuck requiere que uno rompa los comandos en pasos microscópicos.

El nombre del idioma es una referencia al término de la jerga brainfuck, que se refiere a cosas tan complicadas o inusuales que exceden los límites de la comprensión, como era no está diseñado ni hecho para diseñar software real, sino para desafiar los límites de la programación de computadoras.

Historia

En 1992, Urban Müller, un estudiante de física suizo, se hizo cargo de un pequeño archivo en línea para el software Amiga. El archivo se hizo más popular y pronto se reflejó en todo el mundo. Hoy en día, es el archivo Amiga más grande del mundo, conocido como Aminet.

Müller diseñó Brainfuck con el objetivo de implementar el compilador más pequeño posible, inspirado en el compilador de 1024 bytes para el lenguaje de programación FALSE. El compilador original de Müller se implementó en lenguaje de máquina y se compiló en un binario con un tamaño de 296 bytes. Cargó el primer compilador Brainfuck en Aminet en 1993. El programa venía con un "Readme" archivo, que describía brevemente el lenguaje y desafiaba al lector "¿Quién puede programar algo útil con él?:)". Müller también incluyó un intérprete y algunos ejemplos bastante elaborados. Una segunda versión del compilador usó solo 240 bytes. Actualmente hay muchos compiladores de brainfuck en la web.

A medida que Aminet crecía, el compilador se hizo popular entre la comunidad de Amiga y, con el tiempo, se implementó en otras plataformas.

P'': el 'lenguaje principal' formal de Brainfuck

Excepto por sus dos comandos de E/S, Brainfuck es una variación menor del lenguaje de programación formal P′′ creado por Corrado Böhm en 1964, que a su vez se basa explícitamente en la máquina de Turing. De hecho, usando seis símbolos equivalentes a los respectivos comandos Brainfuck +, -, <, >, [, ], Böhm proporcionó un programa explícito para cada una de las funciones básicas que juntas sirven para calcular cualquier función computable. Así que el primer "Brainfuck" Los programas aparecen en el artículo de Böhm de 1964, y fueron suficientes para probar la integridad de Turing.

El ábaco infinito: el 'abuelo' de Brainfuck idioma

Joachim Lambek introdujo una versión con direccionamiento de memoria explícito (en lugar de movimientos relativos en una pila) y un salto condicional (en lugar de bucles) en 1961 bajo el nombre de Infinite Abacus, que consiste en un número infinito de celdas y dos instrucciones:

• X+ (célula de interior X)
• X- else jump T (decremento X si es positivo más saltar a T)

Prueba que Infinite Abacus puede calcular cualquier función recursiva computable mediante la programación del conjunto Kleene de funciones recursivas μ básicas.

Su máquina fue simulada por el cálculo de modelado de máquina de Melzac a través de la aritmética (en lugar de la lógica binaria) imitando a un operador humano moviendo piedras en un ábaco, de ahí el requisito de que todos los números deben ser positivos. Melzac, cuya computadora con un conjunto de instrucciones es equivalente a un ábaco infinito, proporciona programas para la multiplicación, GCD, n^th número primo, representación en base b, clasificación por magnitud y muestra cómo simular una máquina de Turing arbitraria.

Diseño de lenguaje

El lenguaje consta de ocho comandos, que se enumeran a continuación. Un programa brainfuck es una secuencia de estos comandos, posiblemente intercalados con otros caracteres (que se ignoran). Los comandos se ejecutan secuencialmente, con algunas excepciones: un puntero de instrucción comienza en el primer comando y cada comando al que apunta se ejecuta, después de lo cual normalmente avanza al siguiente comando. El programa termina cuando el puntero de la instrucción se mueve más allá del último comando.

El lenguaje brainfuck utiliza un modelo de máquina simple que consta del programa y el puntero de instrucciones, así como una matriz unidimensional de al menos 30 000 celdas de bytes inicializadas a cero; un puntero de datos móvil (inicializado para apuntar al byte más a la izquierda de la matriz); y dos flujos de bytes para entrada y salida (la mayoría de las veces conectados a un teclado y un monitor respectivamente, y usando la codificación de caracteres ASCII).

Comandos

Los ocho comandos de idioma constan cada uno de un solo carácter:

(Alternativamente, el comando ] puede traducirse como un salto incondicional a el comando [ correspondiente, o viceversa; los programas se comportará igual pero se ejecutará más lentamente, debido a una doble búsqueda innecesaria).

[ y ] coinciden como suelen hacerlo los paréntesis: cada [ coincide exactamente con un ] y viceversa, el [ viene primero, y no puede haber ningún [ o ] no coincidente entre los dos.

Los programas de Brainfuck se pueden traducir a C usando las siguientes sustituciones, asumiendo que ptr es del tipo char* y se ha inicializado para apuntar a una matriz de bytes cero:

Como sugiere el nombre, los programas Brainfuck tienden a ser difíciles de comprender. Esto se debe en parte a que cualquier tarea levemente compleja requiere una larga secuencia de comandos y en parte a que el texto del programa no brinda indicaciones directas del estado del programa. Estas, además de la ineficiencia de Brainfuck y sus limitadas capacidades de entrada/salida, son algunas de las razones por las que no se usa para la programación seria. No obstante, como cualquier lenguaje completo de Turing, Brainfuck es teóricamente capaz de calcular cualquier función computable o simular cualquier otro modelo computacional, si se le da acceso a una cantidad ilimitada de memoria. Se han escrito una variedad de programas Brainfuck. Aunque los programas Brainfuck, especialmente los complicados, son difíciles de escribir, es bastante trivial escribir un intérprete para Brainfuck en un lenguaje más típico como C debido a su simplicidad. Incluso existen intérpretes de Brainfuck escritos en el propio lenguaje de Brainfuck.

Brainfuck es un ejemplo del llamado tarpit de Turing: se puede usar para escribir cualquier programa, pero no es práctico hacerlo, porque Brainfuck proporciona tan poca abstracción que los programas se vuelven muy largo o complicado.

Ejemplos

Sumar dos valores

Como primer ejemplo simple, el siguiente fragmento de código agregará el valor de la celda actual a la celda siguiente: cada vez que se ejecuta el bucle, la celda actual disminuye, el puntero de datos se mueve hacia la derecha, esa siguiente celda se incrementa y el puntero de datos se mueve hacia la izquierda nuevamente. Esta secuencia se repite hasta que la celda inicial es 0.

[-■+.]

Esto se puede incorporar en un programa de suma simple de la siguiente manera:

++ Celda c0 = 2■ +++++ Célula c1 = 5[ Comience sus bucles con su puntero celular en el contador de bucle (c1 en nuestro caso). + Añadir 1 a c0■ - Apartado 1 de c1] Termina tus bucles con el puntero celular en el contador de buclesEn este punto nuestro programa ha añadido 5 a 2 dejando 7 en c0 y 0 en c1pero no podemos producir este valor a la terminal ya que no es ASCII codificado.Para mostrar el carácter ASCII "7" debemos añadir 48 al valor 7.Usamos un bucle para calcular 48 = 6 * 8.++++ ++++ c1 = 8 y este será nuestro contador de vuelta[. ++ ++ Añadir 6 a c0■ - Apartado 1 de c1]. . Imprimir c0 que tiene el valor 55 que traduce a "7"!

¡Hola Mundo!

El siguiente programa imprime "¡Hola mundo!" y una nueva línea a la pantalla:

[ Este programa imprime "¡Hola Mundo!" y una nueva línea a la pantalla, su longitud 106 caracteres de comando activos. [No es el más corto.] Este bucle es un "loop de comentario inicial", una manera simple de agregar un comentario a un programa BF de tal manera que usted no tiene que preocuparse acerca de cualquier comando personajes. Cualquiera.", ",", "+", "-", "."y"■"Los personajes son simplemente ignorado, el["y"]"Los personajes sólo tienen que ser equilibrados. Esto el bucle y los comandos que contiene son ignorados porque la célula actual predeterminado a un valor de 0; el valor 0 hace que este bucle sea saltado.]++++++++ Set Cell #0 to 8[ ■++++ Añadir 4 a Celda #1; esto siempre establecerá Celda #1 a 4 [ como la celda será limpiada por el bucle ■++ Añadir 2 a Celda #2 ■++ Añadir 3 a Celda #3 ■++ Añadir 3 a Celda #4 ■+ Añadir 1 a Celda #5 " c)- Decrementar el contador de bucle en la celda #1 ] Ámbito hasta la Celda #1 es cero; número de iteraciones es 4 ■+ Añadir 1 a Celda #2 ■+ Añadir 1 a Celda #3 ■- Subtract 1 from Cell #4 >+ Añadir 1 a Celda #6 [.] Regrese a la primera célula cero que encuentre; esto Célula #1 que fue aclarada por el bucle anterior .- Decrementar el contador de bucle en la celda #0] Ámbito hasta Celda #0 es cero; número de iteraciones es 8El resultado de esto es:Celda no: 0 1 2 3 4 5 6Contenido: 0 72 104 88 32 8Puntos: ^>. Cell #2 tiene valor 72 que es 'H '■-.... Extracto 3 de Celda #3 para obtener 101 que es 'e'+++++++..++. Del mismo modo para 'llo' de Cell #3>. Celda #5 es 32 para el espacio.-. Extracto 1 de Celda #4 para 87 para dar una 'W'.. La célula #3 fue puesta a 'o' desde el final de 'Hola '++.---.---. Celda #3 para 'rl' y 'd '>+. Add 1 to Cell #5 nos da un punto de exclamación■++. Y finalmente una nueva línea de Cell #6

Para "legibilidad", este código se ha repartido en muchas líneas y se han agregado espacios en blanco y comentarios. Brainfuck ignora todos los caracteres excepto los ocho comandos +-<>[],. por lo que no se necesita una sintaxis especial para los comentarios (siempre y cuando los comentarios no contengan los caracteres de comando). El código también podría haber sido escrito como:

++++++++[■++++[■++■++■++■+" c)-]■+■+■->+[.].-]>.■-....+++++++..++.>..-...++.---.---.>+.■++.

ROT13

Este programa cifra su entrada con el cifrado ROT13. Para ello, debe asignar los caracteres A-M (ASCII 65–77) a N-Z (78-90) y viceversa. También debe mapear a-m (97-109) a n-z (110-122) y viceversa. Debe asignar todos los demás caracteres a sí mismos; lee los caracteres de uno en uno y genera sus equivalentes cifrados hasta que lee un EOF (aquí se supone que se representa como -1 o "sin cambios"), momento en el cual el programa finaliza.

El enfoque básico utilizado es el siguiente. Llamando al carácter de entrada x, divida x-1 entre 32, manteniendo el cociente y el resto. A menos que el cociente sea 2 o 3, solo da como resultado x, manteniendo una copia durante la división. Si el cociente es 2 o 3, dividir el resto ((x-1) módulo 32) entre 13; si el cociente aquí es 0, genera x+13; si es 1, salida x-13; si es 2, genera x.

Respecto al algoritmo de división, al dividir y entre z para obtener un cociente q y un resto r, hay un bucle externo que establece q y r primero en el cociente y el resto de 1/z, luego en los de 2/z, y así sucesivamente; después de haber ejecutado y veces, este bucle externo termina, dejando q y r establecidos en el cociente y el resto de y/z. (El dividendo y se usa como un contador decreciente que controla cuántas veces se ejecuta este ciclo). Dentro del ciclo, hay un código para incrementar r y disminuir y, que suele ser suficiente; sin embargo, cada zésima vez a través del ciclo externo, es necesario poner a cero r e incrementar q. Esto se hace con un contador decreciente ajustado al divisor z; cada vez que pasa por el bucle exterior, este contador se reduce y, cuando llega a cero, se vuelve a llenar moviendo el valor de r de vuelta a él.

-,+[ Leer el primer personaje y comenzar el bucle de lectura de caracteres externos -[ Skip forward if character is 0 >++++[■++++++++.-] Set up divisor (32) for division loop (MEMORY LAYOUT: dividendo copy remainder divisor quotient cero) .+.-[ Configurar dividendo (x menos 1) e introducir el bucle de división ■+■+■-[, titulado] Aumentar la copia y el resto / reducir divisor / Caso normal: saltar adelante .[[2]■+.-]>+■] Caso especial: trasladar el resto al divisor y aumentar el cociente - No. c)- Decremento dividendo ] Loop de división final ], titulado[-]+ Fin del bucle de salto; cero ex divisor y reutilizar espacio para una bandera ■--[-[.-■++[-]].[ Cero esa bandera a menos que el cociente fuera 2 o 3; cero cociente; bandera de verificación ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[ Si la bandera entonces establece divisor (13) para el segundo bucle de división (MEMORY LAYOUT: cero copy dividend divisor remainder quotient cero cero) ■-[■+>] Reducir el divisor; Caso normal: aumento del resto ■[+[.+■-]■+>] Caso especial: aumentar el resto / moverlo de nuevo a divisor / aumentar el cociente - No. c)- Disminución del dividendo ] Loop de división final >[.+■-] Añadir el resto de nuevo a divisor para conseguir un útil 13 ■[ Skip forward if quotient was 0 -[ Decremento cociente y saltar hacia adelante si cociente era 1 -..[-]> Cero cociente y divisor si el cociente era 2 ]..[..->-]> Cero divisor y restar 13 de copia si el cociente era 1 ]..[..+>-] Cero divisor y añadir 13 para copiar si el cociente era 0 ] Fin de salto exterior (jump a aquí si (caracter menos 1)/32) no era 2 o 3) .[-] Restos claros de la primera división si se saltó la segunda división ..[-] Salida ROT13ed carácter de copia y aclararlo .-,+ Leer el siguiente personaje] Loop de lectura de caracteres finales

Problemas de portabilidad

En parte porque Urban Müller no escribió una especificación completa del idioma, los muchos intérpretes y compiladores posteriores de brainfuck han implementado dialectos ligeramente diferentes de brainfuck.

Tamaño de celda

En la distribución clásica, las células son de 8 bits de tamaño (las células son bytes), y este sigue siendo el tamaño más común. Sin embargo, para leer datos no textuales, un programa de brainfuck puede necesitar distinguir una condición de extremo de cualquier valor byte posible; por lo tanto, también se han utilizado células de 16 bits. Algunas implementaciones han utilizado células de 32 bits, células de 64 bits o células de grano con rango teóricamente ilimitado, pero los programas que usan este rango extra son probablemente lentos, ya que almacenar el valor ${displaystyle n}$ en una celda requiere ${displaystyle O(n)}$ tiempo como el valor de una célula sólo puede ser cambiado al aumentar y decrementar.

En todas estas variantes, los comandos , y . siguen leyendo y escribiendo datos en bytes. En la mayoría de ellos, las celdas se envuelven, es decir, incrementar una celda que mantiene su valor máximo (con el comando +) la llevará a su valor mínimo y viceversa. Las excepciones son las implementaciones que están distantes del hardware subyacente, las implementaciones que usan bignums y las implementaciones que intentan imponer la portabilidad.

Por lo general, es fácil escribir programas de mierda que nunca provoquen el desbordamiento o el desbordamiento de enteros y, por lo tanto, no dependan del tamaño de la celda. En general, esto significa evitar el incremento de +255 (retorno de 8 bits sin signo) o evitar sobrepasar los límites de [-128, +127] (retorno de 8 bits con signo) (dado que no hay operadores de comparación, un programa no puede distinguir entre un La celda de tamaño de bits fijo en complemento a dos con signo y sin signo y la negatividad de los números es una cuestión de interpretación). Para obtener más detalles sobre el ajuste de enteros, consulte el artículo Desbordamiento de enteros.

Tamaño de matriz

En la distribución clásica, la matriz tiene 30 000 celdas y el puntero comienza en la celda más a la izquierda. Se necesitan incluso más celdas para almacenar cosas como el millonésimo número de Fibonacci, y la forma más fácil de completar el lenguaje Turing es hacer que la matriz sea ilimitada a la derecha.

Algunas implementaciones también extienden la matriz hacia la izquierda; Esta es una característica poco común y, por lo tanto, los programas portátiles de Brainfuck no dependen de ella.

Cuando el puntero se mueve fuera de los límites del arreglo, algunas implementaciones darán un mensaje de error, algunas intentarán extender el arreglo dinámicamente, otras no lo notarán y producirán un comportamiento indefinido, y algunas moverán el puntero al extremo opuesto de la matriz. Algunas compensaciones están involucradas: expandir la matriz dinámicamente hacia la derecha es el enfoque más fácil de usar y es bueno para los programas que consumen mucha memoria, pero conlleva una penalización de velocidad. Si se usa una matriz de tamaño fijo, es útil hacerla muy grande o, mejor aún, dejar que el usuario establezca el tamaño. Dar un mensaje de error por violaciones de límites es muy útil para la depuración, pero incluso eso conlleva una penalización de velocidad a menos que pueda ser manejado por las protecciones de memoria del sistema operativo.

Código de fin de línea

Diferentes sistemas operativos (ya veces diferentes entornos de programación) usan sutilmente diferentes versiones de ASCII. La diferencia más importante está en el código utilizado para el final de una línea de texto. MS-DOS y Microsoft Windows utilizan un CRLF, es decir, un 13 seguido de un 10, en la mayoría de los contextos. UNIX y sus descendientes (incluidos Linux y macOS) y Amigas usan solo 10, y las Mac más antiguas usan solo 13. Sería difícil si los programas de Brainfuck tuvieran que reescribirse para diferentes sistemas operativos. Sin embargo, fue fácil crear un estándar unificado. El compilador de Urban Müller y sus programas de ejemplo usan 10, tanto en la entrada como en la salida; lo mismo ocurre con la gran mayoría de los programas de mierda mental existentes; y 10 también es más conveniente de usar que CRLF. Por lo tanto, las implementaciones de brainfuck deberían asegurarse de que los programas de brainfuck que asumen newline = 10 se ejecutarán correctamente; muchos lo hacen, pero algunos no.

Esta suposición también es coherente con la mayoría de los códigos de muestra del mundo para C y otros lenguajes, ya que usan "n", o 10, para sus saltos de línea. En los sistemas que utilizan finales de línea CRLF, la biblioteca estándar de C reasigna de forma transparente "n" a "rn" en la salida y "rn" a "n" en la entrada para flujos no abiertos en modo binario.

Comportamiento al final del archivo

El comportamiento del comando , cuando se encuentra una condición de fin de archivo varía. Algunas implementaciones establecen la celda en el puntero en 0, algunas lo establecen en el EOF constante de C (en la práctica, esto suele ser -1), algunas dejan el valor de la celda sin cambios. No hay un consenso real; Los argumentos para los tres comportamientos son los siguientes.

Establecer la celda en 0 evita el uso de números negativos y hace que sea un poco más conciso escribir un bucle que lea caracteres hasta que ocurra EOF. Esta es una extensión de idioma ideada por Panu Kalliokoski.

Establecer la celda en -1 permite que EOF se distinga de cualquier valor de byte (si las celdas son más grandes que bytes), lo cual es necesario para leer datos no textuales; también, es el comportamiento de la traducción C de , proporcionada en el archivo Léame de Müller. Sin embargo, no es obvio que esas traducciones de C deban tomarse como normativas.

Dejar el valor de la celda sin cambios es el comportamiento del compilador Brainfuck de Urban Müller. Este comportamiento puede coexistir fácilmente con cualquiera de los otros; por ejemplo, un programa que asume EOF = 0 puede establecer la celda en 0 antes de cada comando ,, y luego funcionará correctamente en las implementaciones que hacen EOF = 0 o EOF = "sin cambios& #34;. Es tan fácil adaptarse a la opción "sin cambios" comportamiento que cualquier programador loco interesado en la portabilidad debería hacer.

Implementaciones

Aunque es trivial hacer un intérprete ingenuo de Brainfuck, escribir un compilador o intérprete de optimización se vuelve más un desafío y una diversión, al igual que lo es escribir programas en Brainfuck: para producir resultados razonablemente rápidos, el compilador necesita unir las piezas fragmentadas. instrucciones forzadas por el lenguaje. Las posibles optimizaciones van desde simples optimizaciones de mirilla de longitud de ejecución en comandos repetidos y patrones de bucle comunes como [-], a otras más complicadas como la eliminación de código muerto y el plegado constante.

Además de la optimización, también se han escrito otros tipos de intérpretes de brainfuck inusuales. Se han hecho varios compiladores Brainfuck de menos de 200 bytes; uno tiene solo 100 bytes en código de máquina x86.

Derivados

Muchas personas han creado equivalentes de brainfuck (lenguajes con comandos que se asignan directamente a brainfuck) o derivados de brainfuck (lenguajes que amplían su comportamiento o alteran su semántica).

Algunos ejemplos:

• Pi, que mapea el cerebro en errores en dígitos individuales de Pi.
• VerboseFuck, que parece un lenguaje de programación tradicional, sólo lo que aparece como parámetros o expresiones son en realidad partes de comandos más largos que no pueden ser alterados.
• DerpPlusPlus, en el que los comandos son reemplazados por palabras como 'HERP', 'DERP', 'GIGITY', etc.
• ¡Ook!, que mapea los ocho comandos del cerebro a combinaciones de dos palabras de "Ook.", "Ook?", y "Ook!", bromamente diseñado para ser "escrito y legible por orang-utans" según su creador, una referencia al orang-utan Librarian en las novelas de Terry Pratchett.
• Ternario, similar en el concepto de Ook! pero consistente en permutaciones de los caracteres ASCII 0, 1, y 2.
• BodyFuck, una implementación de BrainFuck basada en un sistema controlado por gestos para que los movimientos del programador sean capturados por una cámara de vídeo y convertidos en los 8 posibles personajes.
• OooWee, los comandos son variaciones de OooWee (por ejemplo, ooo,ooe,wee etc.). Inspirado del personaje de Rick y Morty, el Sr. PoopyButthole.
• Uso Arch btw, que mapea el cerebro en las palabras encontradas en la frase "Uso Arch btw". Inspirada en una frase acuñada por la comunidad de Arch Linux.
• Brainfunk, maps brainfuck to voice samples, which are used in a dance track, whose words encode a brainfuck program.
• ADN es un superset basado en moléculas de ADN, con comandos reemplazados por Nucleobase. Una forma utiliza la representación helix de la molécula de ADN.
• Cerebro², "un derivado del cerebro, excepto esta vez realmente divertido". Cada término en el lenguaje es un nombre de otro derivado del cerebro.
• Joder., un derivado del cerebro con "palabras clave más intuitivas", preparado con "fuck". Desarrollado por el adolescente, Josh Schiavone.