P′′
(denotado también simplemente P′′) es un lenguaje de programación esotérico, creado por Corrado Böhm[1][2] en 1964 para describir a una familia de máquinas de Turing.
| P′′ | ||
|---|---|---|
| ? | ||
| Información general | ||
| Paradigma | Esotérico | |
| Apareció en | 1964 | |
| Diseñado por | Corrado Böhm | |
| Implementaciones | Múltiples | |
| Influido por | Máquina de Turing | |
| Ha influido a | Brainfuck | |
Definición
P′′ se define formalmente como un conjunto de palabras sobre un alfabeto de cuatro instrucciones {R, λ, (, )}, como sigue:
Sintaxis
- R y λ son palabras en P′′.
- Si p y q son palabras en P′′, entonces pq es una palabra en P′′.
- Si q es una palabra en P′′, entonces (q) es una palabra en P′′.
- Solamente palabras derivadas de las tres reglas anteriores son palabras en P′′.
Semántica
- {a0, a1, ..., an}(n ≥ 1) es el alfabeto de la cinta de una máquina de Turing con cinta infinita por la izquierda, siendo a0 el símbolo blanco.
- R significa mover la cabeza de la cinta una celda hacia la derecha (si procede).
- λ significa reemplazar el símbolo actual ai por ai+1 (tomando an+1 = a0), y luego moviendo la cabeza de la cinta una celda hacia la izquierda.
- (q) significa iterar q en un bucle while, con la condición que el símbolo actual no sea a0.
- Un programa es una palabra en P′′. La ejecución de un programa se produce de izquierda a derecha, ejecutando R, λ, y (q) según como se encuentren, hasta que no haya más que ejecutar.
Relación con otros lenguajes de programación
P′′ fue el primer lenguaje imperativo de programación estructurada que prescindió del GOTO para ser demostrada su pertenencia a los Turing completos.[1][2]
El lenguaje Brainfuck (aparte de sus comandos de E/S) es una variación menos informal de P′′, que influyó a su vez posteriormente la creación de otros lenguajes esotéricos, tales como Ook! y Tink. Böhm[1] define programas explícitos para P′′ para cada uno de los conjuntos de funciones básicas suficientes para computar cualquier función computable, utilizando solo (, ) y las cuatro palabras r ≡ λR, r′ ≡ rn, L ≡ r′λ, R. Estos son los comandos equivalentes de los seis usados respectivamente por Brainfuck: [, ], +, -, <, >. Note que desde an+1 = a0, realizar r (símbolo de "incremento" en la celda actual) n veces dará como resultado un "decremento" del símbolo en la celda actual (r′).
Ejemplos de programas
Böhm[1] define el siguiente programa para computar el antecesor (x-1) de un entero x > 0:
R ( R ) L ( r' ( L ( L ) ) r' L ) R r
lo que se traduce directamente al equivalente programa en brainfuck
> [ > ] < [ − [ < [ < ] ] − < ] > +
Este programa recibe como entrada un número entero definido en notación de numeración biyectiva base-n, con a1, ..., an codificando los dígitos 1,...,n, respectivamente, y agregando un blanco a0 antes y después del string del dígito. (Por ejemplo, en numeración biyectiva base-2, el número 8 se codificaría como a0a1a1a2a0, porque 8 = 1*22 + 1*21 + 2*20.) Al comienzo y al final del cómputo, la cabeza de la cinta está en el a0 precediendo el string que representa el dígito.
Referencias
- ↑ Böhm, C.: "On a family of Turing machines and the related programming language", ICC Bull. 3, 185-194, julio de 1964.
- ↑ Böhm, C. and Jacopini, G.: "Flow diagrams, Turing machines and languages with only two formation rules", CACM 9(5), 1966. (Nota: Este es el artículo más citado sobre el Teorema del programa estructurado.)