Brainfuck

Brainfuck (Ing.: "Hirnfick") es un lenguaje de programación esotérico que el fundador de Aminet , Urban Müller de Suiza, diseñó en 1993. El lenguaje también se conoce como Brainf * ck, Brainf *** o BF.

Brainfuck es demasiado engorroso e ineficiente para un uso productivo, pero es adecuado para entrenar la metodología de desarrollo de software. En particular, Brainfuck se caracteriza por un concepto de lenguaje extremadamente simple y una implementación altamente compacta del compilador, pero al mismo tiempo la aplicabilidad universal (en el sentido teórico de computabilidad ) no estaba restringida.

General

El objetivo de Müller era diseñar un lenguaje simple de Turing completo que pudiera traducirse con el compilador más pequeño posible ; se inspiró en False , otro lenguaje de programación esotérico cuyo compilador tenía solo 1024  bytes . Finalmente logró escribir la segunda versión de su compilador para el Commodore Amiga en solo 240 bytes. Brian Raiter pudo socavar esto escribiendo un compilador Brainfuck para Linux x86 usando solo 171 bytes . Para MS-DOS hay un intérprete de cerebro de Bertram Felgenhauer con un tamaño de sólo 98 bytes.

Diseño de lenguaje

Un programa de cogida cerebral es muy similar a la definición formal de una máquina de Turing . Sin embargo, en lugar de un cabezal de lectura / escritura en una cinta, se utilizan estados y un alfabeto libremente definible, un puntero a un campo de datos , construcciones de bucle y una ALU rudimentaria en el sentido de un lenguaje de programación iterativo .

Conjunto de instrucciones

Brainfuck tiene ocho comandos, cada uno de los cuales consta de un solo personaje:

firmar Equivalente de C semántica
> ++ptr; incrementa el puntero
< --ptr; disminuye el puntero
+ ++*ptr; incrementa el valor actual de la celda
- --*ptr; disminuye el valor actual de la celda
. putchar(*ptr); Emite el valor actual de la celda como caracteres ASCII en la salida estándar
, *ptr = getchar(); Lee un carácter de la entrada estándar y almacena su valor ASCII en la celda actual
[ while (*ptr) { Salta al frente, después del ]comando apropiado , si el valor de celda actual es 0
] } Retrocede después del [comando apropiado si el valor de la celda actual no es 0

Nota: Hay varias variantes semánticamente equivalentes de los dos últimos comandos, pero las que se dan aquí son las más eficientes de implementar.

Otros caracteres que aparecen en el texto fuente (por ejemplo, letras, números, espacios, saltos de línea) generalmente se ignoran y, por lo tanto, se pueden usar como comentarios del texto fuente.

Completitud de Turing

La integridad de Turing ha sido probada para varios entornos de brainfuck :

  • Para un campo infinitamente grande de células de tamaño finito y para un campo finito de células de tamaño infinito por Daniel B. Cristofani .
  • Para un campo infinitamente grande de celdas de tamaño infinito por Frans Faase .

Una variante de Brainfuck con un tamaño de celda finito y un tamaño de campo finito (por ejemplo, BFmin) es, como cualquier computadora real, un autómata finito .

Programas de muestra en Brainfuck

Hola Mundo!

El siguiente programa muestra “ ¡Hola mundo! Y un salto de línea . 

 ++++++++++
 [
  >+++++++>++++++++++>+++>+<<<<-
 ]                       Schleife zur Vorbereitung der Textausgabe
 >++.                    Ausgabe von 'H'
 >+.                     Ausgabe von 'e'
 +++++++.                'l'
 .                       'l'
 +++.                    'o'
 >++.                    Leerzeichen
 <<+++++++++++++++.      'W'
 >.                      'o'
 +++.                    'r'
 ------.                 'l'
 --------.               'd'
 >+.                     '!'
 >.                      Zeilenvorschub
 +++.                    Wagenrücklauf

Para una mejor legibilidad, este código genial se ha distribuido en varias líneas y se ha comentado. Brainfuck ignora todos los personajes que no son comandos de Brainfuck. Por tanto, todos los caracteres a excepción de +-<>[],.pueden utilizarse para comentar el código fuente.

Primero, la primera celda (la "cero") del campo de datos se establece en el valor 10 ( a[0] = 10). El ciclo al principio del programa utiliza esta celda para calcular más valores para la segunda, tercera, cuarta y quinta celdas. El valor 70 se calcula para la segunda celda, que está cerca del valor ASCII de la letra 'H' (valor ASCII 72). La tercera celda recibe el valor 100, cerca de la letra 'e' (valor ASCII 101), la cuarta el valor 30 cerca del valor para espacios (valor ASCII 32), la quinta el valor 10, que corresponde al carácter ASCII "Línea Feed ”y se interpreta como un salto de línea (o debería serlo, consulte la sección “ Implementaciones ”).

El ciclo calcula los valores simplemente sumando 10 veces 7, 10, 3 y 1 a las celdas inicialmente inicializadas con 0. Después de cada pasada de bucle, un [0] se reduce en uno hasta que tiene el valor 0 y, por lo tanto, el bucle finaliza.

Al final del ciclo tiene el campo de datos y luego los siguientes valores a[0] = 0:; a[1] = 70; a[2] = 100; a[3] = 30; a[4] = 10;

A continuación, el puntero se coloca en la segunda celda del campo de datos ( a[1]) y el valor de la celda se incrementa en dos. Tiene el valor 72, que corresponde al valor ASCII del carácter 'H'. A continuación, se emite. Las otras letras a emitir se calculan según el mismo esquema con la ayuda de los valores inicializados por el bucle y los valores ya utilizados.

Conceptos básicos de programación en Brainfuck

Nota : El intérprete ignora todos los caracteres fuera del conjunto de comandos Brainfuck. Por tanto, se interpretan como un comentario. Dado que, por ejemplo, los signos más no se entienden como un comentario, sino que se evalúan como un comando de incremento , en el ejemplo que se muestra a continuación hay n más 1 en el comentario por este motivo .

cintas

Los bucles comienzan con el carácter '[' y terminan con el asociado ']'. El ciclo se ejecuta hasta que el valor de la celda actual sea cero. La forma significativa más simple es el ciclo cero, que disminuye el valor de la celda actual hasta que es cero: 

  [-]

Bucle simple

  ,[.,]

Programa de eco simple. Los caracteres se leen desde la entrada estándar y se devuelven a la salida estándar.

Bucles anidados

La definición de los dos comandos de bucle también incluye la opción de programar bucles anidados. Los ejemplos correspondientes se pueden encontrar en el código fuente de varias operaciones aritméticas (ver más abajo).

condiciones

  • x no es igual ay (obtenido restando los dos números)

Es importante que la celda 0 se establezca en 0, de lo contrario, el bloque de condición se puede llamar varias veces. 

  >+++++           addiere 5 zu Zelle 1
  >++++            addiere 4 zu Zelle 2
  [<->-]           subtrahiere Zelle 2 von Zelle 1
  <                gehe zu Zelle 1

  [                wird aufgerufen wenn Zelle 1 ungleich 0 ist
  <                gehe zu Zelle 0 (somit wird die Schleife nur einmal durchlaufen)
  ]

Operaciones aritmeticas

Cambiando el valor de una celda a la siguiente (primero poniendo a cero la siguiente celda, luego incrementando la siguiente celda en un ciclo , simultáneamente disminuyendo la actual): 

  >[-]<[>+<-]

Un valor se copia moviéndolo a dos celdas subsiguientes y luego moviéndolo hacia atrás: 

 >[-]>[-]<<          nur notwendig wenn die beiden Variablen nicht leer sind
 [>+>+<<-]           verschiebe Inhalt von Zelle n nach Zellen n plus 1 und n plus 2
 >>[<<+>>-]          verschiebe Inhalt von Zelle n plus 2 nach Zelle n
 <<                  gehe wieder auf Zelle n

Suma : p [1] = p [1] + p [0]; Efecto secundario: p [0] = 0 

  [>+<-]

Resta : p [1] = p [1] - p [0]; Efecto secundario: p [0] = 0 

  [>-<-]

Multiplicación con constante p[1] = p[0] * 5:; Efecto secundario: p [0] = 0 Se lleva a cabo un desplazamiento normal, por lo que la celda objetivo no aumenta en uno, sino en el factor correspondiente. 

  [>+++++<-]

Multiplicación con un valor de celda: Aquí, el segundo factor se agrega al producto mediante la función de copia anterior repetidamente p[2] = p[0] * p[1]:; Efecto secundario:p[0] = p[3] = 0 

  [>[>+>+<<-]>>[<<+>>-]<<<-]

Exponenciación : escribir un número con +++ en una celda requiere más tiempo, a más tardar a partir de números de dos dígitos. Por lo tanto, uno se ayuda a sí mismo usando poderes: p [2] = 5 ^ 3 = 125; Efecto secundario: p [0] = p [1] = 0 

  +++++[>+++++[>+++++<-]<-]

La división funciona más fácilmente como una división completa, todo lo demás en este caso da como resultado un bucle infinito. Por lo demás, la idea es la misma que con la multiplicación: p [1] = p [0] / 5; Efecto secundario: p [0] = 0 

  [>+<-----]

La división restante en Brainfuck, sin embargo, es un poco más complicada.

El código C para el siguiente programa Brainfuck: 

while(p[0]--) {
  p[1]--;
  p[2]++;
  if(p[1] == 0) {
   p[3]++;
   p[1] = p[2];
   p[2] = 0;
  }
 }
 p[2] = p[0] % p[1];
 p[3] = p[0] / p[1];

Efecto secundario: p [0] = 0; p [4] = 0; p [5] = 0; p [1] = p [1] - p [0]% p [1] 

 >>[-]>[-]>[-]>[-]<<<<<[->>+<-[>>>]>[[<+>-]>+>>]<<<<<]

Conversión

El siguiente código genera un número en forma decimal 

 ++++++++[>++++++++<-]>[-<++>]<-----     schreibt die Zahl 123 in die erste Zelle
 >[-]++++++++[>[-]<[->+<]>-]<<<<<<<<<    Löschen der nächsten Zellen
 [->+<]>[>+<-<+>]>[>>>>>[->+<]>+<<<<<    der eigentliche Code
 ++++++++++<[->>+<-[>>>]>[[<+>-]>+>>]
 <<<<<]>[-]>[-<<+>>]>[-<<+>>]<<]>>>>>
 [<<<<+++++++[-<+++++++>]<-[<+>-]<.[-
 ]>>>>>>[-<+>]<-]<<<<<<<

Implementaciones

Dado que Brainfuck no es un lenguaje de programación estandarizado , pueden surgir incompatibilidades. Estos se refieren principalmente a los diferentes formatos de salto de línea de los sistemas operativos Windows y Unix , así como a sus diferentes códigos de caracteres para la tecla Intro. La mayoría de los programas de brainfuck, incluido Urban Müller, están diseñados para entornos Unix y, por lo tanto, no se pueden traducir correctamente con implementaciones que comienzan con códigos de caracteres de Windows.

Idiomas similares

También está el lenguaje de programación Brainfuck 2D , que traslada el concepto Brainfuck a un espacio de dibujo bidimensional. Una cadena se forma con caracteres de texto, cuya dirección indica el comando correspondiente de Brainfuck, por lo que la longitud es insignificante para el número de llamadas. Una instrucción se repite según la suma de todos los dígitos de su segmento. Entonces + ********* es el mismo comando que +; Sin embargo, +93 *** ejecuta el comando doce veces (9 + 3 = 12). El comando +0 **** no se interpreta porque no se ejecuta en absoluto. De esta forma puedes crear espacio para tu línea si no es suficiente. Si el curso de la cadena no es claramente reconocible para el intérprete o si la cadena termina, el programa finaliza.

¡Otra variante de Brainfuck, que no pretende ser muy seria, es Ook! .

Otra variante 2D es Path, que permite usar / y \ como espejo. El flujo del programa representa entonces una especie de rayo de luz, en Flow , que es bastante similar a Path , el flujo del programa corre como el agua, es decir, cuando se ramifica, se divide y, por lo tanto, habilita (pseudo) hilos.

literatura

  • Oliver Lau: Hexenwerk - Un llamado a los lenguajes de programación esotéricos . En: c't 22/2007, págs. 192-199.

enlaces web

  • Esolang : descripción general, ejemplos y clasificación del lenguaje de programación
  • Intérprete en línea Brainfuck en JavaScript con una extensa biblioteca de programas.
  • awib - compilador Brainfuck escrito en Brainfuck

Evidencia individual

  1. ↑ hugi.scene.org
  2. ↑ hevanet.com
  3. ↑ hevanet.com
  4. ^ BF es Turing completo . iwriteiam.nl
  5. ↑ Referencia de Brainfuck 2D
  6. ↑ Página del proyecto Flowbf en GitHub