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, +, -, :=, ;, $\ne$ 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}{ccc}P& ::=& x_i:=x_j+c\\ & |& x_i:=x_j-c\\ & |& P_1;P_2\\ & |& \mathrm{W}\mathrm{H}\mathrm{I}\mathrm{L}\mathrm{E}{x}_i\ne 0\mathrm{D}\mathrm{O}P\mathrm{E}\mathrm{N}\mathrm{D}\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\ne 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 $\ne$ 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

• Szablon:Cytuj książkę