A linguagem enquanto

Question

Para a minha teoria da computação classe línguas, temos uma lição de casa para implementar um pedaço de código em uma linguagem que só tem enquanto declarações para controle de fluxo (sem if). Isto é principalmente para provar que você pode escrever uma linguagem Turing-completa com apenas um tempo loop.

Para aqueles de vocês que pode compreender gramáticas de língua, aqui estão as regras de linguagem:

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)

Esta é copiada de minhas notas de aula, então não me culpe se algo está faltando ou está! Incorreta

O pedaço de código para implementar é o seguinte:

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

De qualquer forma, se você quiser ir em frente e escrever que usando as regras de linguagem acima, vá em frente. Caso contrário, vá em frente e escrever em qualquer linguagem que você está mais confortável. Mas existem algumas ressalvas!

• Não se declarações ou qualquer outro tipo de controle de fluxo diferente enquanto loops.
• Sem batota: a gramática acima não inclui quaisquer instruções break, instruções de retorno, ou exceções. Não usá-los.

Eu tenho o meu pedaço de código escrito para isso (que eu vou postar só para provar este não é um show me teh codez post). Eu estou meio curioso o que qualquer outra pessoa pode vir até com embora.

Answer 1

Aqui está o meu 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

Isso pode ser feito com um único loop while, mas não está claro:

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

Explicação, se d = 0, então D será 1, também será um 1. Isto termina o laço.

Agora x está definido para a / d que é bom, porque se d é 0, a / d avalia a 1.

Answer 3

Será que este trabalho?

td := d
x := 1

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

Answer 4

Para ser Turing completa, você precisa para apoiar tanto a seleção e iteração. While obviamente iteração. A seleção pode ser realizada fazendo passar pelo circuito uma vez, se a condição for verdadeira, e não em tudo o contrário.

Assim pior caso você pode fazer tudo o que você precisa, aplicando essas técnicas. Eu imagino que alguns fluxos de controle complicadas ficaria rápido feio embora. : -)

Answer 5

Sem o uso de detalhes das verdadeiras ou falsas ramos, e sem repetir o 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 é uma expansão do de Eamon resposta .

A semântica de if <condition> then <stmt> else <stmt> fi é o seguinte:

• avaliar <condition>;
• se era verdade, executar a instrução entre then e else;
• Caso contrário, executar a instrução entre else e fi.

A semântica de while <condition> do <stmt> od é o seguinte:

• avaliar <condition>;
• se for falso, a declaração while é feito de execução;
• Caso contrário, executar a instrução entre do e od, e executar a instrução while novamente.

Para expressar if A then B else C em termos de while, execute o seguinte transformação:

Let gensymN ser um nome não for utilizado para qualquer outra variável; em seguida, emitir o seguinte código

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

A semântica deste programa é:

• Atribuir 0 a gensymN.
• Avaliar gensymN = 0 and A (é verdade A sse é verdade)
• Se for verdade, então:
  • executar B
  • executar gensymN = 1
  • avaliar gensymN = 0 and A (é falso)
  • avaliar gensymN = 0 (é falso)
• else (se gensymN = 0 and A era falso):
  • avaliar gensymN = 0 (é verdade)
  • executar C
  • executar gensymN := 1
  • avaliar gensymN = 0 (é falso)

Observe o seguinte subestrutura do acima:

• (efetivamente) avalia A;
• Se for verdade, ele executa B, caso contrário C.
• Para além da A, B e C, o programa (fragmento) apenas remexe gensymN, que não está presente no programa de entrada.

Assim, este programa tem a mesma semântica

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

Uma nota de rodapé: se A é verdadeira quando avaliada, ele será avaliado mais uma vez (a menos que and é curto-circuito). Se o idioma permite armazenar booleans em variáveis, pode-se introduzir uma variável mais manequim e fazer dummy := A; <insert the above program here, with dummy instead of A>. Em seguida, as duas avaliações de dummy são essencialmente apenas uma carga. Se avaliar expressões booleanas não podem ter efeitos colaterais, impedindo a segunda avaliação não é necessária para a correção; pode (ou não) ser uma otimização.

Leve o acima como uma "prova soft", com as condições do parágrafo anterior, que este é um correto totalmente geral tradução de if para while. A generalidade completa define este (= de Eamon) resposta para além dos outros, na minha opinião.