P ′ ′ (P doble primo [1] ) es un lenguaje de programación de computadoras primitivo creado por Corrado Böhm [2] [3] en 1964 para describir una familia de máquinas de Turing .
Paradigma | Imperativo , estructurado |
---|---|
Diseñada por | Corrado Böhm |
Apareció por primera vez | 1964 |
Disciplina de mecanografía | sin tipificar |
Dialectos | |
Brainfuck | |
Influenciado | |
Brainfuck |
Definición
(de aquí en adelante escrito P ′ ′ ) se define formalmente como un conjunto de palabras en el alfabeto de cuatro instrucciones, como sigue:
Sintaxis
- y son palabras en P ′ ′.
- Si y son palabras en P ′ ′, entonces es una palabra en P ′ ′.
- Si es una palabra en P ′ ′, entonces es una palabra en P ′ ′.
- Solo las palabras derivables de las tres reglas anteriores son palabras en P ′ ′.
Semántica
- es el alfabeto de cinta de una máquina de Turing con cinta infinita a la izquierda,siendo el símbolo en blanco , equivalente a.
- Todas las instrucciones en P ′ ′ son permutaciones del conjuntode todas las configuraciones de cinta posibles; es decir, todas las configuraciones posibles tanto del contenido de la cinta como de la posición del cabezal de la cinta.
- es un predicado que dice que el símbolo actual no es. No es una instrucción y no se usa en programas, sino que se usa para ayudar a definir el idioma.
- significa mover el cabezal de la cinta hacia la derecha una celda (si es posible).
- significa reemplazar el símbolo actual con y luego mueva el cabezal de la cinta hacia la izquierda una celda.
- significa la composición de la función . En otras palabras, la instrucción se realiza antes .
- significa iterar en un bucle while , con la condición.
Relación con otros lenguajes de programación
- P ′ ′ fue el primer lenguaje de programación estructurado imperativo "sin GOTO " probado con Turing-completo [2] [3]
- El lenguaje Brainfuck (aparte de sus comandos de E / S) es una variación informal menor de P ′ ′. Böhm da programas P ′ ′ explícitos para cada una de un conjunto de funciones básicas suficientes para calcular cualquier función computable , usando solo, y las cuatro palabras dónde con denotando el la iteración de, y . Estos son los equivalentes de los seis comandos Brainfuck respectivos [,], +, -, <,> . Tenga en cuenta que desde, incrementando el símbolo actual los tiempos se ajustarán para que el resultado sea "disminuir" el símbolo en la celda actual en uno ().
Programa de ejemplo
Böhm [2] da el siguiente programa para calcular el predecesor ( x -1) de un entero x > 0:
que se traduce directamente al programa Brainfuck equivalente :
> [ > ] < [ - [ < [ < ]] - < ] > +
El programa espera que un número entero se represente en notación biyectiva base-k , con codificar los dígitos respectivamente, y tener antes y después de la cadena de dígitos. (Por ejemplo, en biyectiva base-2, el número ocho se codificaría como, porque 8 en biyectiva base-2 es 112.) Al principio y al final del cálculo, el cabezal de la cinta está en el antes de la cadena de dígitos.
Referencias
- ^ https://github.com/Pbtflakes/pdbl
- ^ a b c Böhm, C .: "Sobre una familia de máquinas de Turing y el lenguaje de programación relacionado", ICC Bull. 3, 185-194, julio de 1964.
- ^ a b Böhm, C. y Jacopini, G .: "Diagramas de flujo, máquinas de Turing y lenguajes con sólo dos reglas de formación", CACM 9 (5), 1966. (Nota: Este es el artículo más citado sobre el programa estructurado teorema .)
Enlaces web
- P ′ ′ Intérprete en línea : demostración de lacancióniterativa99 Bottles of Beerinterpretada en 337568instruccionesP ′ ′.