Program WHILE

Program WHILE to jedno z narzędzi teorii obliczalności służące do ustanowienia, czy dana funkcja jest obliczalna.

• Klasa funkcji obliczalnych za pomocą WHILE odpowiada klasie funkcji obliczalnych za pomocą maszyny Turinga lub programów GOTO.
• Programy WHILE bazują syntaktycznie i semantycznie, z wyjątkiem pętli WHILE, na programach LOOP.

Programy WHILE składają się z symboli: WHILE, DO, END, +, -, :=, ;, ${\displaystyle \neq }$ oraz dowolnej liczby zmiennych i stałych, przy czym stałe są elementami zbioru liczb naturalnych.

Program P jest syntaktycznie zdefiniowany w notacji BNF jako:

${\displaystyle {\begin{array}{lrl}P&::=&x_{i}:=x_{j}+c\\&|&x_{i}:=x_{j}-c\\&|&P_{1};P_{2}\\&|&\mathrm {WHILE} \,x_{i}\neq 0\,\mathrm {DO} \,P\,\mathrm {END} \end{array}}}$

gdzie:

• ${\displaystyle c}$ jest stałą,
• ${\displaystyle x_{i},}$ ${\displaystyle x_{j}}$ są zmiennymi
• ${\displaystyle P_{1},}$ ${\displaystyle P_{2}}$ to programy WHILE

Wszystkie użyte w danym programie zmienne zostają zainicjalizowane przed wykonaniem programu. Zmienne nie zainicjalizowane bezpośrednio otrzymują domyślną wartość 0.

Wyrażenie postaci

xi := xj + c

oznacza przyznanie zmiennej ${\displaystyle x_{i}}$ wartości otrzymanej poprzez dodanie zmiennej ${\displaystyle x_{j}}$ i stałej ${\displaystyle c.}$ Specjalnym przypadkiem jest tutaj sytuacja, gdzie wartość stałej ${\displaystyle c}$ jest równa zeru. Wtedy wartość zmiennej ${\displaystyle x_{j}}$ zostaje bezpośrednio przyznana zmiennej ${\displaystyle x_{i}{:}}$

xi := xj + 0

Wyrażenie postaci

xi := xj – c

oznacza przyznanie zmiennej ${\displaystyle x_{i}}$ wartości otrzymanej poprzez odjęcie stałej ${\displaystyle c}$ od zmiennej ${\displaystyle x_{j}.}$ w przypadku gdy wartość stałej jest wyższa niż wartość zmiennej wynikiem odejmowania jest 0.

Kompozycja dwóch programów WHILE ma postać

${\displaystyle P_{1};}$ ${\displaystyle P_{2}}$

i oznacza, że program ${\displaystyle P_{1}}$ zostanie wykonany przed programem ${\displaystyle P_{2}.}$

Pętla WHILE ma postać

WHILE ${\displaystyle x_{i}\neq 0}$ DO ${\displaystyle P}$ END

przy czym liczba przebiegów programu, w przeciwieństwie do programów LOOP, nie jest z góry ustalona w zmiennej ${\displaystyle x_{i},}$ lecz może ulegać zmianom dynamicznie podczas wykonywania programu.

Następujący program WHILE przyznaje zmiennej x₀ sumę zmiennych x₁ i x₂:

x0 := x1 + 0;
y := x2 + 0;
WHILE ${\displaystyle y!=0}$ DO
       ${\displaystyle y{:}}$ = ${\displaystyle y-1;}$
       ${\displaystyle x_{1}{:}}$ = ${\displaystyle x_{1}}$ + 1
END

Pętlę postaci

WHILE x ${\displaystyle \neq }$ 0 DO P END

można przedstawić za pomocą następującego programu GOTO:

M1: IF x = 0 THEN GOTO M2;
    P;
    GOTO M1;
M2: ...

gdzie instrukcje za znacznikiem M₂ są dowolne.

• program GOTO
• program LOOP

• Uwe Schöning: Theoretische Informatik – kurzgefasst. Spektrum Akademischer Verlag. ISBN 3-8274-1099-1. Brak numerów stron w książce