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

xi := xj + 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}{:}$

xi := xj + 0

Wyrażenie postaci

xi := xj – 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₂:

x0 := x1 + 0;
y := x2 + 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:

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

gdzie instrukcje za znacznikiem M₂ są dowolne.

Zobacz też

• program GOTO
• program LOOP

Bibliografia

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