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

Cechy edytuj

  • 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 edytuj

Składnia edytuj

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

 

gdzie:

  •   jest stałą,
  •     są zmiennymi
  •     to programy WHILE

Semantyka edytuj

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   wartości otrzymanej poprzez dodanie zmiennej   i stałej   Specjalnym przypadkiem jest tutaj sytuacja, gdzie wartość stałej   jest równa zeru. Wtedy wartość zmiennej   zostaje bezpośrednio przyznana zmiennej  

xi := xj + 0

Wyrażenie postaci

xi := xj – c

oznacza przyznanie zmiennej   wartości otrzymanej poprzez odjęcie stałej   od zmiennej   w przypadku gdy wartość stałej jest wyższa niż wartość zmiennej wynikiem odejmowania jest 0.

Kompozycja dwóch programów WHILE ma postać

   

i oznacza, że program   zostanie wykonany przed programem  

Pętla WHILE ma postać

WHILE   DO   END

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

Przykładowa implementacja edytuj

Dodawanie edytuj

Następujący program WHILE przyznaje zmiennej x0 sumę zmiennych x1 i x2:

x0 := x1 + 0;
y := x2 + 0;
WHILE   DO
         =  
         =   + 1
END

Symulacja pętli WHILE za pomocą programu GOTO edytuj

Pętlę postaci

WHILE x   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 M2 są dowolne.

Zobacz też edytuj

Bibliografia edytuj

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