Befunge

Befunge es un lenguaje de programación esotérico, reflexivo y basado en pilas bidimensionales. Se diferencia de los lenguajes convencionales en que los programas se organizan en una cuadrícula bidimensional. "Flecha" las instrucciones dirigen el flujo de control hacia la izquierda, la derecha, hacia arriba o hacia abajo, y los bucles se construyen enviando el flujo de control en un ciclo. Se ha descrito como "un cruce entre Forth y Lemmings".

Un compañero digno de INTERCAL; una familia de lenguaje computador que escapa a la limitación quotidiana del flujo de control lineal y abraza los contadores del programa volando a través de múltiples dimensiones con topologías exóticas.

—Jargon File

Historia

El lenguaje fue creado originalmente por Chris Pressey en 1993 para Amiga, como un intento de diseñar un lenguaje que fuera lo más difícil de compilar posible. Tenga en cuenta que el comando p permite la automodificación del código. Sin embargo, posteriormente se han escrito varios compiladores. Varias extensiones del original "Befunge-93" También existen especificaciones, en particular Funge-98, que amplía el concepto a un número arbitrario de dimensiones y puede ser multiproceso, con múltiples punteros de instrucción que operan simultáneamente en el mismo espacio. Las extensiones y variantes de Befunge se llaman Fungeoids o simplemente Funges.

La especificación Befunge-93 restringe cada programa válido a una cuadrícula de 80 instrucciones horizontales por 25 instrucciones verticales. La ejecución del programa que supera estos límites se "envuelve" a un punto correspondiente en el otro lado de la cuadrícula; un programa Befunge es de esta manera topológicamente equivalente a un toro. Dado que un programa Befunge-93 solo puede tener una sola pila y su matriz de almacenamiento está limitada, el lenguaje Befunge-93 no es Turing-completo (sin embargo, se ha demostrado que Befunge-93 es Turing completo con tamaño de palabra de pila ilimitado). La última especificación Funge-98 proporciona la integridad de Turing al eliminar las restricciones de tamaño en el programa; en lugar de envolverse en un límite fijo, el movimiento de un puntero de instrucción Funge-98 sigue un modelo denominado "Lahey-space" después de su creador, Chris Lahey. En este modelo, la cuadrícula se comporta como un toroide de tamaño finito con respecto a la envoltura, mientras que todavía se permite extenderse indefinidamente.

Etimología

La palabra Befunge se deriva de un error de escritura en una discusión en línea, donde la palabra 'antes de' se pretendía.

Compilación

Como se indicó, el objetivo de diseño de Befunge era crear un lenguaje que fuera difícil de compilar. Esto se intentó con la implementación de código automodificable (la instrucción 'p' puede escribir nuevas instrucciones en el campo de juego) y un campo de juego multidimensional (la misma instrucción se puede ejecutar en cuatro direcciones diferentes).

Sin embargo, estos obstáculos se han superado, hasta cierto punto, y los compiladores de Befunge se han escrito usando las técnicas apropiadas.

El compilador bef2c incluido con la distribución estándar de Befunge-93 utiliza código de subprocesos: cada instrucción se compila en un fragmento de código C y el control fluye a través de los fragmentos tal como lo hace en un intérprete de Befunge (es decir, condicionalmente a la valor de algún registro de 'dirección'). Esto no resulta en una ventaja significativa sobre un buen intérprete. Tenga en cuenta que el compilador bef2c no es correcto ya que no maneja ni 'p' o el modo de cadena, pero no sería imposible hacerlo (aunque el lenguaje C podría no ser adecuado para esto).

El compilador Betty, por ejemplo, trata todas las líneas rectas posibles de instrucciones como un subprograma, y si un 'p' instrucción altera ese subprograma, ese subprograma se vuelve a compilar. Esta es una variación interesante de la compilación justo a tiempo, y resulta en una ventaja mucho mayor sobre un intérprete, ya que muchas instrucciones pueden ejecutarse en código nativo sin tomar decisiones intermedias en la 'dirección' Registrarse.

Ejemplo de código Befunge-93

La técnica de usar flechas para cambiar el flujo de control se demuestra en el siguiente programa generador de números aleatorios. El puntero de instrucción Befunge comienza en la esquina superior izquierda y se desplazará hacia la derecha si no se redirige. Siguiendo las flechas, las instrucciones ? envían el puntero de instrucción en direcciones cardinales aleatorias hasta que el puntero toca un dígito, empujándolo hacia la pila. Luego, las flechas navegan hasta . para generar el dígito de la pila y devolver el puntero al primer aleatorizador direccional. No hay @ para terminar este programa, por lo que produce un flujo interminable de números aleatorios del 1 al 9.

 v título titulado v 12345 ¿Qué? ■ ? ? ¿V? v 6789 , titulado v ^ ..

El siguiente código es un ejemplo del clásico "¡Hola mundo!" programa. Primero las letras "olleH" se colocan en la pila como números ASCII. Luego, estos se extraen de la pila en orden LIFO y se muestran como caracteres de texto para dar "Hola". Un espacio es el carácter número 32 en ASCII, que aquí se construye multiplicando 4 y 8, antes de generarse como texto. El código restante genera "¡Mundo!" de manera similar, seguido del carácter ASCII 10 (un carácter de avance de línea, que mueve el cursor de salida a una nueva línea).

■ vv ,,,"Hola".■48*, vv,,,,"¡Mundo!".■25*,@

El siguiente código es una versión un poco más complicada. Agrega el carácter ASCII 10 (un carácter de salto de línea) a la pila y luego empuja "!dlrowolleH" a la pila. De nuevo, el orden LIFO significa que "H" es ahora la parte superior de la pila y será la primera impresa, "e" es el segundo, y así sucesivamente. Para imprimir los caracteres, el programa ingresa un ciclo que primero duplica el valor superior en la pila (así que ahora la pila se vería como "n!dlrowolleHH"). Entonces el "_" La operación mostrará el valor duplicado e irá a la derecha si es un cero, a la izquierda de lo contrario. (Esto supone un intérprete compatible que "devuelve" 0 cuando extrae una pila vacía). Cuando se va a la izquierda, extrae e imprime el valor superior como un carácter ASCII. Luego duplica el siguiente carácter y regresa al "_" prueba, continúa imprimiendo el resto de la pila hasta que esté vacía y el siguiente valor que aparece es 0, momento en el que "@" finaliza el programa.

 ■25*"DlrowolleH":v v:_@ ■ ^

Lista de instrucciones Befunge-93

La mayoría de los lenguajes de programación unidimensionales requieren alguna distinción sintáctica entre el texto del comentario y el código fuente, aunque esa distinción puede ser tan trivial como la regla de Brainfuck de que cualquier carácter que no esté en el conjunto +-[]< >,. es un comentario. Los lenguajes como Lisp y Python tratan las cadenas como comentarios en contextos donde no se usan los valores. De manera similar, en Befunge, no hay sintaxis de comentarios: para incrustar documentación en el código, el programador simplemente enruta el flujo de control alrededor del "comentario" área, para que el texto en esa área nunca se ejecute.