while-loop - programacion - php5

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 pueden entender las gramáticas del lenguaje, estas son 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, ¡así que no me culpen si falta algo o es incorrecto!

La pieza de código para implementar es esta:

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

En cualquier caso, si quiere seguir adelante y escribir eso usando las reglas de lenguaje anteriores, 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 trampas: la gramática anterior no incluye declaraciones de interrupción, declaraciones de devolución ni excepciones. No los uses

Tengo mi código escrito para esto (que publicaré solo para demostrar que esto no es una publicación de code me). Sin embargo, soy un poco curioso de lo que otros puedan pensar.

Answer 1

¿Esto funcionaría?

td := d
x := 1

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

Answer 2

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 3

Para ser Turing completo, debe admitir tanto la selección como la 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, puedes hacer todo lo que necesites aplicando esas técnicas. Me imagino que algunos complicados flujos de control se pondrían muy feos. :-)

Answer 4

Se puede hacer con un solo ciclo while, pero no está tan claro:

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

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

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

Answer 5

Sin usar detalles de las ramas verdadera o falsa, 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 la respuesta de Eamon .

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

• evaluar <condition> ;
• si era cierto, ejecute la declaració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 ejecuta;
• de lo contrario, ejecute la instrucción entre do y od , y ejecute la instrucción while nuevamente.

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

Deja que gensymN sea ​​un nombre que no se usa para ninguna otra variable; luego emita el siguiente código

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:

• Asignar 0 a gensymN .
• Evalúa gensymN = 0 and A (es verdadero si f A es verdadero)
• Si es verdadero, entonces:
  • ejecutar B
  • ejecutar gensymN = 1
  • evaluar gensymN = 0 and A (es falso)
  • evaluar gensymN = 0 (es falso)
• else (si gensymN = 0 and A era falso):
  • evaluar gensymN = 0 (es verdad)
  • ejecutar C
  • ejecutar gensymN := 1
  • evaluar gensymN = 0 (es falso)

Observe la siguiente subestructura de lo anterior:

• Evalúa (efectivamente) A ;
• Si es verdadero, ejecuta B , de lo contrario C
• Además de A , B y C , el programa (fragmento) solo gensymN 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 al pie: si A es verdadero cuando se evalúa, se evaluará una vez más (a menos que esté en cortocircuito). Si el lenguaje permite almacenar variables booleanas en variables, se puede introducir una variable ficticia más y hacer dummy := A; <insert the above program here, with dummy instead of A> 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 suave", con las condiciones del párrafo anterior, que esta es una traducción correcta general de if a while . La generalidad completa establece la respuesta de este (= Eamon) aparte de los demás, en mi opinión.