BlooP y FlooP ( bucle acotado y bucle libre ) son lenguajes de programación simples diseñados por Douglas Hofstadter para ilustrar un punto de su libro Gödel, Escher, Bach . [1] BlooP es un lenguaje de programación no completo de Turing cuya estructura de flujo de control principal es un bucle acotado (es decir,no se permite la recursividad [ cita necesaria ] ). Todos los programas en el lenguaje deben terminar y este lenguaje solo puede expresar funciones recursivas primitivas . [2]
FlooP es idéntico a BlooP excepto que admite bucles ilimitados; Es un lenguaje completo de Turing y puede expresar todas las funciones computables . Por ejemplo, puede expresar la función de Ackermann , que (al no ser recursiva primitiva) no se puede escribir en BlooP. Tomando prestado de la terminología estándar en lógica matemática , [3] [4] Hofstadter llama bucles MU a los bucles ilimitados de FlooP. Como todos los lenguajes de programación completos de Turing, FlooP sufre el problema de la detención : es posible que los programas no finalicen y, en general, no es posible decidir qué programas lo hacen.
BlooP y FlooP pueden considerarse modelos de computación y, en ocasiones, se han utilizado para enseñar computabilidad. [5]
Las únicas variables son OUTPUT(el valor de retorno del procedimiento) y (una secuencia ilimitada de variables de números naturales, indexadas por constantes, como en Unlimited Register Machine [6] ). Los únicos operadores son ( asignación ), (suma), (multiplicación), (menor que), (mayor que) e (igual).CELL(i)⇐+×<>=
Cada programa utiliza sólo un número finito de celdas, pero los números en las celdas pueden ser arbitrariamente grandes. Las estructuras de datos como listas o pilas se pueden manejar interpretando el número en una celda de maneras específicas, es decir, numerando por Gödel las posibles estructuras.
Las construcciones de flujo de control incluyen bucles acotados, declaraciones condicionales , ABORTsaltos de bucles y QUITsaltos de bloques. BlooP no permite recursividad, saltos sin restricciones ni cualquier otra cosa que tenga el mismo efecto que los bucles ilimitados de FlooP. Se pueden definir procedimientos con nombre, pero estos sólo pueden llamar a procedimientos previamente definidos. [7]
DEFINIR PROCEDIMIENTO FACTORIAL [N]:BLOQUE 0: COMENZAR SALIDA ⇐ 1; CELDA(0) ⇐ 1; BUCLE EN LA MAYORÍA DE N VECES: BLOQUE 1: COMENZAR SALIDA ⇐ SALIDA × CELDA(0); CELDA(0) ⇐ CELDA(0) + 1; BLOQUE 1: FINAL;BLOQUE 0: FINAL.
Esta no es una operación incorporada y (al estar definida en números naturales) nunca da un resultado negativo (por ejemplo, 2 − 3 := 0). Tenga en cuenta que OUTPUTcomienza en 0, como todos los CELLs, y por lo tanto no requiere inicialización.
DEFINIR PROCEDIMIENTO MENOS [M,N]:BLOQUE 0: COMENZAR SI M < N, ENTONCES: SALIR DEL BLOQUE 0; BUCLE COMO MÁXIMO M + 1 VECES: BLOQUE 1: COMENZAR SI SALIDA + N = M, ENTONCES: ABORTAR BUCLE 1; SALIDA ⇐ SALIDA + 1; BLOQUE 1: FINAL;BLOQUE 0: FINAL.
El siguiente ejemplo, que implementa la función de Ackermann , se basa en la simulación de una pila usando la numeración de Gödel : es decir, en funciones numéricas previamente definidas PUSH, POPy TOPque satisfacen PUSH [N, S] > 0, TOP [PUSH [N, S]] = Ny POP [PUSH [N, S]] = S. Dado que se utiliza un ilimitado MU-LOOP, este no es un programa BlooP legal. Las QUIT BLOCKinstrucciones en este caso saltan al final del bloque y repiten el bucle, a diferencia de ABORT, que sale del bucle. [3]
DEFINIR PROCEDIMIENTO ACKERMANN [M, N]:BLOQUE 0: COMENZARCELDA(0) ⇐ M;SALIDA ⇐ N;CELDA(1) ⇐ 0;BUCLE MU:BLOQUE 1: COMENZARSI CELDA(0) = 0, ENTONCES:BLOQUE 2: COMENZARSALIDA ⇐ SALIDA + 1;SI CELDA(1) = 0, ENTONCES: ABORTAR EL BUCLE 1;CELDA(0) ⇐ SUPERIOR [CELDA(1)];CELDA(1) ⇐ POP [CELDA(1)];SALIR DEL BLOQUE 1;BLOQUE 2: FINALSI SALIDA = 0, ENTONCES:BLOQUE 3: COMENZARSALIDA ⇐ 1;CELDA(0) ⇐ MENOS [CELDA(0), 1];SALIR DEL BLOQUE 1;BLOQUE 3: FINALSALIDA ⇐ MENOS [SALIDA, 1];CELDA(1) ⇐ EMPUJAR [MENOS [CELDA(0), 1], CELDA(1)];BLOQUE 1: FINAL;BLOQUE 0: FINAL.