El lenguaje while

Question

Para mi teoría de la clase de idiomas informáticos, obtuvimos una tarea para implementar un fragmento de código en un lenguaje que solo tiene sentencias while para control de flujo (no declaraciones if). Esto es principalmente para demostrar que puedes escribir un lenguaje de Turing completo con solo un ciclo while.

Para aquellos de ustedes que puede entender las gramáticas de lenguaje, aquí están las reglas del lenguaje:

S -> S;S | while C do S od | id := E 

E -> E + T | T | E - T 

T -> T * F | F | F/T 

F -> id | cons | (E) 

C -> E = E | E > E | E < E | E >= E | E <= E | E != E | C and C | C or C | not(C) 

Esto se copia de mis notas de clase, por lo que no me culpes si algo falta o es incorrecto!

El trozo de código para implementar es la siguiente:

if d = 0 do 
    x := 1 
else 
    x := a/d 

En cualquier caso, si desea seguir adelante y escribir que el uso de las reglas del lenguaje anterior, adelante. De lo contrario, adelante y escríbalo en el idioma en el que se sienta más cómodo. ¡Pero hay algunas advertencias!

• No si las declaraciones o cualquier otro tipo de control de flujo que no sean while loops.
• Sin trampa: la gramática anterior no incluye ninguna declaración de interrupción, declaraciones de devolución o excepciones. No los uses

Tengo mi pedazo de código escrito para este (que voy a publicar sólo para demostrar que esto no es un show me teh posterior codez). Sin embargo, soy un poco curioso de lo que otros puedan pensar.

Answer 1

Aquí está mi código:

continue := True 
while d = 0 and continue do 
    x := 1 
    continue := False 
od 
while d != 0 and continue do 
    x := a/d 
    continue := False 
od 

Answer 2

Se puede hacer con un solo bucle while, pero no es tan clara:

while d == 0 do 
    d := 1; 
    a := 1 
od 
x := a/d; 

Explicación, si D = 0, d será 1, también a será 1. Esto finaliza el ciclo.

Ahora x se establece en a/d, que está muy bien, porque si era d 0, a/d evalúa a 1.

Answer 3

Para ser Turing completo, tiene que soportar tanto la selección e iteración. Mientras que los bucles obviamente iteran. La selección puede lograrse haciendo que pase por el ciclo una vez si la condición es verdadera, y de ninguna otra manera.

En el peor de los casos, puede hacer todo lo que necesite aplicando esas técnicas. Me imagino que algunos complicados flujos de control se pondrían muy feos. :-)

Answer 4

¿Funcionaría?

td := d 
x := 1 

while td != 0 do 
    x := a/d 
    td := 0 
od 

Answer 5

Sin utilizar detalles de las ramas de verdadero o falso, y sin repetir el predicado:

statementIncomplete := True 
while d = 0 and statementIncomplete do 
    x := 1 
    statementIncomplete := False 
od 
while statementIncomplete do 
    x := a/d 
    statementIncomplete := False 
od 

Answer 6

Esta es una expansión de Eamon's answer.

La semántica de if <condition> then <stmt> else <stmt> fi es la siguiente:

• evaluar <condition>;
• si fue verdadero, ejecute la instrucción entre then y else;
• de lo contrario, ejecute la instrucción entre else y fi.

La semántica de while <condition> do <stmt> od es la siguiente:

• evaluar <condition>;
• si es falso, la instrucción while se ha ejecutado;
• de lo contrario, ejecute la instrucción entre do y od, y ejecute de nuevo la instrucción while.

Para expresar if A then B else C en términos de while, realice la siguiente transformación:

Vamos gensymN ser un nombre no se utiliza para cualquier otra variable; entonces emitir el siguiente código de

gensymN := 0; 
while gensymN = 0 and A do B; gensymN = 1; od; 
while gensymN = 0 do C; gensymN = 1; od 

La semántica de este programa es:

• Assign 0 a gensymN.
• Evaluar gensymN = 0 and A (es cierto si y sólo si A es cierto)
• Si es verdad, entonces:
  • ejecutar B
  • ejecutar gensymN = 1
  • evaluar gensymN = 0 and A (que es falso)
  • evaluar gensymN = 0 (que es falsa)
• otra cosa (si gensymN = 0 and A era falso):
  • evaluar gensymN = 0 (es verdad)
  • ejecutar C
  • ejecutar gensymN := 1
  • evaluar gensymN = 0 (que es falsa)

observar el siguiente subestructura de lo anterior:

• (efectivamente) evalúa A;
• Si es verdadero, ejecuta B, de lo contrario C.
• Aparte de A, B y C, el programa (fragmento) solo juguetea con gensymN, que no está presente en el programa de entrada.

Por lo tanto este programa tiene la misma semántica que

if A then B else C fi; gensymN := 1 

Una nota: si A es cierto cuando se evaluó, se evaluó una vez (a menos que and es cortocircuitos). Si el lenguaje permite almacenar booleanos en variables, se puede introducir una variable ficticia más y hacer dummy := A; <insert the above program here, with dummy instead of A>. Entonces las dos evaluaciones de dummy son esencialmente solo una carga. Si la evaluación de expresiones booleanas no puede tener efectos secundarios, evitar la segunda evaluación no es necesario para la corrección; puede (o no) ser una optimización.

Tome lo anterior como una "prueba en pantalla", con las condiciones del párrafo anterior, que esta es una correcta totalmente general, traducción de if a while. La generalidad completa establece la respuesta de este (= Eamon) aparte de los demás, en mi opinión.