Program WHILE

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

Cechy

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.

Formalna definicja

Składnia

Programy WHILE składają się z symboli: WHILE, DO, END, +, -, :=, ;, $\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:

{\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:

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

Semantyka

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

x_i := x_j + c

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

x_i := x_j + 0

Wyrażenie postaci

x_i := x_j – c

oznacza przyznanie zmiennej $x_{i}$ wartości otrzymanej poprzez odjęcie stałej $c$ od zmiennej $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ć

 $P_{1};$   $P_{2}$

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

Pętla WHILE ma postać

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

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

Przykładowa implementacja

Dodawanie

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

x₀ := x₁ + 0;
y := x₂ + 0;
WHILE  $y!=0$  DO
        $y{:}$  =  $y-1;$ 
        $x_{1}{:}$  =  $x_{1}$  + 1
END

Symulacja pętli WHILE za pomocą programu GOTO

Pętlę postaci

WHILE x  $\neq$  0 DO P END

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

M₁: IF x = 0 THEN GOTO M₂;
    P;
    GOTO M₁;
M₂: ...

gdzie instrukcje za znacznikiem M₂ są dowolne.

Zobacz też

Bibliografia

Uwe Schöning: Theoretische Informatik – kurzgefasst. Spektrum Akademischer Verlag. ISBN 3-8274-1099-1.