Konstrukcja forall ma formę:
(forall C then C)
Są to wszystkie lokalne zmienne spełniające warunek C, a ponadto C. Odpowiednikiem forall jest podwójna negacja: not (C and not (C) )
Foral C then C ma wartość logiczną True gdy wszystkie zmienne spełniające warunek C spełniają także C. Implikacja odwrotna nie musi byc oczywiście spełniona.
Przykładem użycia forall może być następująca definicja podzbioru
X podzbiorem Y if
(forall x belongs-to X then x belongs-to Y)
Warunek or służy do łączenia kilku części jednej definicji. Pamiętamy regułę określającą czy zmienna x jest rodzicem
x parent-of y if x father-of y
x parent-of y if x mother-of y.
Or łączy nam to w jedną zwartą regułę:
x parent-of y if (either x father-of y or x mother-of y)
Or używane jest w formie (either C or C),
gdzie C i C są pojedynczymi lub złożonymi warunkami. Równie łatwo możemy ułożyć przejrzystą i prostą definicję definicji belongs-to: Zamiast
x belongs-to (x/y)
x belongs-to (y/z) if x belongs-to z
piszemy po prostu:
x belongs-to (y/z) if (eitcher x EQ y or x belongs-to z)
Jedną z najbardziej fascynujących możliwości PROLOGU jest operowanie listami. Podstawową relacją służącą do pracy na listach jest APPEND, zdefiniowana następująco:
APPEND (x y z) zachodzi wtedy, gdy lista z jest połączeniem listy x oraz y. Dla przykładu podam kilka list przed i po połączeniu:
(A B C D) i (E F G) daje (A B C D E F G)
( ) i (A B) daje (A B)
(a) i ((a) (b c)) daje (a (a) (b c)) itd.
Dzięki APPEND możemy zdefiniować na nowo bardzo Użyteczną relację belongs-to, której definicja poprzednio wyglądała następująco:
()belongs-to()
X belongs-to (y z) if
(either x EQ y or x belongs-to z)
Obecnie możemy tę definicję znacznie uprościć: y belongs-to Z if APPEND (x (y|Y) Z)
czyli y jest elementem zbioru (listy) Z jeżeli zbiór Z możemy utworzyć przez połączenie jakiejś listy X i listy (y)Y) o pierwszym elemencie równym y. Dodam, ze skonstruowana w ten sposób definicja jest znacznie szybsza od poprzedniej, gdyż nie jest rekurencyjna i operuje na oryginalnej relacji z PROLOGU. Wykorzystując tę relację możemy utworzyć wiele bardzo użytecznych definicji. Możemy najpierw zdefiniować pierwszy i ostatni element listy.
first (x Y) if (first — pierwszy)
APPEND ((x) Z Y)
pamiętajmy, że w tej relacji x jest elementem.
zaś Z. Y listami.
Gdybyśmy zamiast (x) napisali x to na pytanie which x: first (x (a b c). Prolog odpowiedziałby: (a), czyli nie byłaby to już definicja pierwszego elementu, ale pierwszej składowej jednoelemen-towej listy. Gdy piszemy (x) to PROLOG „wie", że (x) jest listą czyli x jest jej elementem. Podobna jest definicja ostatniego elementu:
last (x y) if (last — ostatni)
APPEND (z (x) y)
Odpowiedzią na pytanie:
which (x y:APPEND (x y (a b c d e f))) jest
() (a b c d e f)
(a) (b c d e f)
(a b) (c d e f)
(a b c) (d e f)
(a b c d) (e f)
(a b c d e) (f)
(a b c d e f) ()
Dlatego, że są to wszystkie możliwe połączenia dwóch list, aby uzyskać listę (a b c d e f).
Wydawać by się mogło, że konieczne jest jeszcze jedno ograniczenie w definicji „first" i „last" na to, by lista (x) miała tylko jeden element. Lecz pamiętajmy, że przecież sam zapis (x) oznacza listę jednoelementową.Jedną z najistotniejszych definicji jest front (x y z), która jest prawdziwa wtedy i tylko wtedy, gdy lista y stanowi x pierwszych elementów listy z,
front (x y z) if APPEND (y y1 z) and x length-of y.
Obrazowo mówiąc relacja front wybiera z wszystkich rozbić listy z na y i y1, takie w którym y ma dokładnie x elementów.
which (x: front( 3 x (A B C D E F G)))
(ABC)
Ciekawe jest rozdzielanie listy na składowe segmenty: dwie relacje (xlX) initial-segment-of z if APPEND (xlX)
(yz)
(ylY) back-segment-of z if APPEND (x (yl Y) z)
dają po złożeniu według definicji:
x segment-of z if y back-segment-of z and
x initial-segment-of y relację segment-of (x z), która rozdziela listę na pod-listy
which (x: x segment-of (A B C D)) (A) (A B)
(ABC)
(A B C D)
(B)
(B C)
(B C D)
(C)
(C D)
(D)
Relacja taka jest konieczna do utworzenia innej niezwykle istotnej relacji power-set (zbiór potęgowy)
Zbiorem potęgowym zbioru x nazywamy zbiór podzbiorów utworzonych przez połączenie na wszystkie sposoby elementów X. Zbiór potęgowy oznaczamy symbolem 2X.
power-set (x(())y)) if y isall (z: z segment-of x)
Na przykład:
which (x: power-set( (a b c) x)) (0 (c) (b c) (b) (a b c) (a b) (a c) (a))
Kolejną relacją, na którą warto zwrócić uwagę, jest reverse (x y). Relacja ta pobiera listę y i odwraca ją, tworząc tym samym listę x,
(x) reverse (x)
(x y|X) reverse z if (y|X) reverse Y and APPEND (Y (x) z)
Jak widzimy jest również rekurencyjna postać definicji
which (x: (A B C D E) reverse x) (E D C B A)
Jeszcze jedną relacją, na którą pragnąłbym przybliżyć czytelnikom, jest nth-el. Jej wartością logiczną TRUE (nth-el (x y z) = TRUE) wtedy, gdy element y jest x-tym elementem listy z.
nth-el (X Y Z) if
x length-of Z and (1)
(either X LESS x or X EQ x) and (2)
APPEND (y (Y/z) Z) and (3)
X1 length-of y and (4)
SUM (X1 1 X). (5)
Ponieważ jest to relacja ciekawa, a jej definicja bardzo pouczająca, więc pokrótce ją zanalizujemy.
Na początku zakładamy, że parametrami tej relacji będą po kolei liczba element i lista. W punkcie (1) definiujemy długość listy z, będzie ona równa x. Warunek (2) polega na sprawdzeniu czy numer elementu, który pragniemy poznać nie wykracza poza rozmiar listy, czyli X mniejsze lub równe x. Dalej w (3) rozbijamy listę Z na dwie składowe, z których pierwsza ma długość X-1 (warunek (4) i (5)). Z zapisu APPEND (y (Y/z) Z) wynika, że jeżeli lista y ma długość X-1, (czyli zawiera elementy o numerach od 1 do X-1), to lista (Y/z) ma długość x-X i numery jej poszczególnych elementów to X, X + 1, ...x. W szczególności pierwszy element listy (Y/z) ma numer X (ten, o który nam chodziło). Stąd już prosty wniosek, że X-tym elementem jest głowa listy (Y/z), czyli Y. On też jest odpowiedzią w relacji nth-el (X Y Z).
Ułóżmy relację, która będzie permutowała dowolną listę. Najpierw utworzymy relację pomocniczą „del".
del(x X Y) zachodzi gdy lista Y jest listą X zubożoną o jeden dowolny element x.
del (x X Y) if APPEND(X1 (x|X2) X) and AP-PEND(X1 X2 Y)
Działanie relacji „del" obrazuje następujący przykład:
which (x: del(x (a b c) (a c))) b
No (more) answers.
Definicja permutation-of wygląda następująco:
Opermutation-of) (yjY) permutation-of X if del (y X Z) and Y permutation-of Z.
which (X: X permutation-of (a b c))
(abc)
(acb)
(bac)
(bca)
(cab)
(cba)
Na zakończenie pragnąłbym zaznajomić Czytelników ze składnią oryginalnego PROLOGU. Każda definicja napisana przez nas ma swój odpowiednik w oryginalnym PROLOGU. Pokażę teraz jak każda z definicji wprowadzonych dzisiaj wygląda w zapisie listowym,
belonges-to:
((belonges-to(H))
((belonges-to X (Y|Z))
(OR(( EQ X Y)) ((belones-to X Z))))
first:
((first X Y)
(APPEND (X) Z Y))
front:
((front X Y Z)
(APPEND Y x Z) (LENGTH-OF X Y)
segment-of:
((segment-of X Y)
(back-segment-of Z Y) (initial-segment-of X Z) power-set: ((power-set X(()|Y))
(ISALL Y Z (segment-of Z X))) reverse; ((reverse (X) (X))) ((reverse (X Y Z) x) (reverse (Y Z) y) (APPEND y (X) x)) nth-el: ((nth-el X Y Z) (lenght-of x Z)
(OR ((LESS X x)) ((EQ X x))) (APPEND y (Y z) Z) (lenght-of X1 y) (SUM X1 1 X))
del:
((del X Y Z)
(APPEND x (X|y) Y) (APPEND x y Z))
permutation:
((permutation-of()()))
((permutation-of (X Y) Z) (del X Z x) (perm Y x))
Już z pobieżnych obserwacji wynika, że w oryginalnej pisowni cała definicja jest listą. Początek tej listy to nazwa definicji wraz z parametrami. Każda następna lista stanowi jakiś warunek. Czytając tak zapisaną definicję moglibyśmy wstawić między pierwszy a drugi element „if", a między każcie kolejne „and". Te części listy, które są względem siebie alternatywne, umieszczamy w liście (OR ((...)) ((...))..((...))) Poza tym PROLOG posługując się w definicji pewnej relacji definicją innej relacji, nie rozbija tej drugiej na pewne pierwotne zastrzeżone symbole, lecz przedstawia ją w postaci nazwy i listy parametrów. Postępowanie takie zwiększa z pewnością czytelność programu, gdyż każda definicja jest strukturalizowana, nie wzmaga jednak prędkości jej przetwarzania.
Na tym kończymy wstępny kurs programowania w microPrologu. Tym, których zainteresował język logiki obiecujemy, że będziemy wracać w Bajtku do tego tematu.
Adam Krauze
