Lập Trình Logic Trong ProLog - PGS.TS. PHAN HUY KHÁNH phần 4

Chia sẻ: Dwefershrdth Vrthrtj | Ngày: | Loại File: PDF | Số trang:19

Thêm vào BST

Báo xấu

238
lượt xem 70
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Prolog rất thích hợp để giải quyết các bài toán liên quan tới các đối tượng và mối quan hệ giữa chúng. Prolog được ứng dụng chủ yếu trong lĩnh vực trí tuệ nhân tạo như công nghệ xử lý tri thức, hệ chuyên gia, máy móc, xử lý ngông ngữ, trò chơi

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Lập Trình Logic Trong ProLog - PGS.TS. PHAN HUY KHÁNH phần 4

50 L p trình lôgic trong Prolog III.3. Sp t th t các m nh và các ích III.3.1. Nguy cơ g p các vòng l p vô h n Xét m nh sau ây : p :- p Nghĩa c a m nh là « p úng n u p úng». V m t khai báo, m nh hoàn toàn úng n. Tuy nhiên, v m t th t c, m nh không dùng làm gì. Trong Prolog, m nh này gây ra r c r i. Ta xét câu h i : ?- p. S d ng m nh trên, ích p ư c thay th b i chính ích p, r i l i ư c thay th b i p, và c th ti p t c. Prolog b rơi vào tình tr ng qu n vô h n. Ví d này làm phương ti n th c hi n các vòng l p c a Prolog. Tr l i ví d con kh và qu chu i trên ây, ta có th thay i th t các ích bên trong c a các m nh . Ch ng h n các m nh thu c v quan h displacement ã ư c s p x p như sau : grab, climbing, pushing, walking (ta có th b sung thêm m nh descending n u mu n tr n v n). Các m nh này nói r ng con kh có th n m l y qu chu i (grab), trèo lên h p (climbing), v.v... V m t ng nghĩa th t c, th t các m nh nói r ng trư c con kh v i l y ư c qu chu i, nó ph i trèo lên h p, trư c khi trèo lên h p, nó ph i y cái h p, v.v... V i th t này, con kh l y ư c qu chu i (gi i quy t ư c bài toán). Bây gi n u ta thay i th t thì i u gì s x y ra ? Gi thi t r ng m nh walking xu t hi n u tiên. Lúc này, vi c th c hi n ích ã t ra trên ây : ?- couldtake(state(tothedoor, onthefloor, tothewindow, nothave)). s t o ra m t quá trình th c thi khác. B n danh sách ích u tiên như cũ (các tên bi n ư c t l i) : (1) couldtake(state(tothedoor, onthefloor, tothewindow, nothave)) Sau khi m nh th hai ư c áp d ng, ta có : (2) displacement(state(tothedoor, onthefloor, tothewindow, nothave), M’, S2’), couldtake(S2’) V i chuy n ng walking(tothedoor, P2’), ta nh n ư c :
51 Ng nghĩa c a chương trình Prolog (3) couldtake(state(P2’, onthefloor, tothewindow, nothave)) Áp d ng l n n a m nh th hai c a couldtake : (4) displacement(state(P2’, onthefloor, tothewindow, nothave), M’’, S2’’), couldtake(S2’’) T th i i m này, s khác nhau xu t hi n. M nh u tiên có ph n u có th so kh p v i ích u tiên trên ây bây gi s là walking (mà không ph i climbing như trư c). Ràng bu c là S2’’ = state(P2’’, onthefloor, tothewindow, nothave). Danh sách các ích tr thành : (5) couldtake(state(P2’’, onthefloor, tothewindow, nothave)) B ng cách áp d ng m nh th hai couldtake, ta nh n ư c (6) displacement(state(P2’’, onthefloor, tothewindow, nothave), M’’’, S2’’’), couldtake(S2’’’) Ti p t c áp d ng m nh walking cho m nh th nh t và ta có : (7) couldtake(state(P2’’’, onthefloor, tothewindow, nothave)) Bây gi ta so sánh các ích (3), (5) và (7). Chúng g n như gi ng h t nhau, tr các bi n P2’, P2’’ và P2’’’. Như ta ã th y, s thành công c a m t ích không ph thu c vào tên các bi n trong ích. i u này có nghĩa r ng k t danh sách các ích (3), quá trình th c hi n không có s ti n tri n nào. Th c t , ta nh n th y r ng m nh th hai c a couldtake và walking ã ư c s d ng qua l i. Con kh i loanh quanh trong phòng mà không bao gi có ý nh s d ng cái h p. Do không có s ti n tri n nào, nên v m t lý thuy t, quá trình tìm n qu chu i s di n ra m t cách vô h n. Prolog s không x lý nh ng tình hu ng vô ích như v y. Ví d này minh ho Prolog ang th gi i m t bài toán mà không bao gi t ư c l i gi i, d u r ng l i gi i t n t i. Nh ng tình hu ng như v y không ph i là hi m khi l p trình Prolog. Ngư i ta cũng hay g p nh ng vòng l p qu n vô h n trong các ngôn ng l p trình khác. Tuy nhiên, i u không bình thư ng so v i các ngôn ng l p trình khác là chương trình Prolog úng n v m t ng nghĩa khai báo, nhưng l i không úng n v m t th t c, nghĩa là không có câu tr l i i v i câu h i cho trư c. Trong nh ng trư ng h p như v y, Prolog không th xoá m t ích vì Prolog c g ng ưa ra m t câu tr l i trong khi ang i theo m t con ư ng x u (không d n n thành công).
52 L p trình lôgic trong Prolog Câu h i chúng ta mu n t ra là : li u chúng ta có th thay i chương trình sao cho có th d phòng trư c nguy cơ b qu n ? Có ph i chúng ta luôn luôn b ph thu c vào s s p t th t úng n c a các m nh và các ích ? Rõ ràng r ng các chương trình l n s tr nên d sai sót n u ph i d a trên m t th t nào ó c a các m nh và các ích. T n t i nhi u phương pháp khác cho phép lo i b các vòng l p vô h n, t ng quát hơn và áng tin c y hơn so v i phương pháp s p t th t . Sau ây, chúng ta s s d ng thư ng xuyên nh ng phương pháp này trong vi c tìm ki m các con ư ng, h p gi i các bài toán và duy t các th . III.3.2. Thay i th t m nh và ích trong chương trình Ngay các ví d u chương, ta ã th y nguy c x y ra các vòng l p vô h n. Chương trình mô t quan h t tiên : ancestor(X, Z) :- parent(X, Z). ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z). Ta hãy xét m t s bi n th c a chương trình này. V m t khai báo, t t c các chương trình là tương ương, nhưng v m t th t c, chúng s khác nhau. Tham kh o ng nghĩa khai báo c a Prolog, không nh hư ng n nghĩa khai báo, ta có th thay i như sau : Th t các m nh trong m t chương trình, và (1) Th t các ích bên trong thân c a các m nh . (2) Th t c ancestor trên ây g m hai m nh , uôi m nh th nh t có m t ích con và uôi m nh th hai có hai ích con. Như v y chương trình s có b n bi n th (=1×2×2) mà c b n u có cùng nghĩa khai báo. Ta nh n ư c như sau : o th t các m nh , và (1) o th t các ích cho m i s p t th t các m nh . (2) Hình dư i ây mô t b n th t c anc1, anc2, anc3, anc4 : % Th t c g c anc1(X, Z) :- parent(X, Z). anc1 (X, Z) :- parent(X, Y), anc1 (Y, Z). % Bi n th a : hoán i các m nh
53 Ng nghĩa c a chương trình Prolog anc2 (X, Z) :- parent(X, Y), anc2 (Y, Z). anc2(X, Z) :- parent(X, Z). % Bi n th b : hoán i các ích c a m nh th hai anc3(X, Z) :- parent(X, Z). anc3 (X, Z) :- anc3 (X, Y), parent(Y, Z). % Bi n th c : hoán i các ích và các m nh anc4 (X, Z) :- anc4 (X, Y), parent(Y, Z). anc4(X, Z) :- parent(X, Z). % Các câu h i ư c t ra l n lư t như sau : ?- anc1(tom, sue). -> Yes ?- anc2(tom, sue). -> Yes ?- anc3(tom, sue). -> Yes ?- anc4(tom, sue). ERR 211 Not enough local stack
54 L p trình lôgic trong Prolog anc2(tom, sue) anc2(X, Z) :- parent (X, Y), anc2 (Y, Z), parent (tom, Y’) anc2(X , Z) :- anc2(Y’, sue) parent (X, Z). Y’ = bill anc2(bill, sue) parent (bill, Y’’) parent (bill, sue) anc2 (Y’’, sue) thành công Y” = ann anc2(ann, sue) parent(ann, Y’’’) parent (ann, sue) Y’’ = sue anc2(Y’’’, sue) th t b i th t b i anc2(sue, sue) parent (sue, sue) parent (sue, Y’’’) anc2(Y’’’, sue) th t b i Y’’’ = jim anc2 (jim, sue) parent (jim, sue) parent(jim, Y’’’) anc2(Y’’’, sue) th t b i th t b i Hình III.6. Bi n th a c a quan h t tiên tr l i câu h i “Tom có ph i là m t t tiên c a Sue ?” Trong trư ng h p cu i cùng, Prolog không th tìm ra câu tr l i. Do b qu n vô h n nên Prolog thông báo “không b nh ”. Hình 2.4. mô t quá trình th c hi n c a anc1 (trư c ây là ancestor) cho cùng m t câu h i. Hình 2.13 (a, b, c) mô t quá trình th c hi n c a anc2, anc3 và anc4. Ta th y anc4 không có hy v ng và anc2 kém hi u qu hơn so v i anc1 do th c hi n nhi u l n tìm ki m và quay lui hơn trong cây. So sánh các quá trình so kh p trong các hình v , ta th y r ng c n khai báo các m nh ơn gi n khi gi i các bài toán. i v i bài toán quan h t tiên, c b n bi n th u d a trên hai ý :
55 Ng nghĩa c a chương trình Prolog ki m tra n u hai tham i c a quan h t tiên tho mãn quan h parent. • giai o n ph c t p nh t là tìm ai ó “gi a” nh ng ngư i là parent hay • ancestor. anc3(tom, sue) anc3(X, Z) :- parent(X, Z). parent (tom, sue) anc3(tom, Y’) anc3(X, Z) :- parent(Y’, sue) anc3(X, Y), th t b i parent(Y, Z). parent(tom, Y’) parent(Y’, sue) Y’ = bill paren(bill, sue) thành công Hình III.7. Bi n th b c a quan h t tiên tr l i câu h i “Tom có ph i là m t t tiên c a Sue ?” anc4(tom, sue) anc4(X, Z) :- anc4(X, Y), parent(Y, Z). anc4(tom, Y’) parent(Y’, sue) anc4(X, Z) :- parent(X, Z). anc4(tom, Y’‘) parent(Y’‘, Y’) parent(Y’, sue) anc4(tom, Y’’’) parent(Y’’’, Y’‘) parent(Y’‘, Y’) parent(Y’, sue) Hình III.8. Bi n th c c a quan h t tiên tr l i câu h i “Tom có ph i là m t t tiên c a Sue ?” Trong s b n bi n th c a quan h ancestor, ch có anc1 là th c hi n quá trình so kh p ơn gi n nh t. Trong khi ó, anc4 b t u quá trình khó khăn nh t. Còn anc2 và anc3 n m gi a hai thái c c này. Dù ta có xem xét chi ti t các quá trình th c hi n th nào i chăng n a, thì anc1 v n là lu t ơn gi n nh t. Ngư i ta khuyên nên s d ng cách này khi l p trình.
56 L p trình lôgic trong Prolog Ta không c n so sánh b n bi n th mà xem xét v i ki u câu h i nào thì m i bi n th d n n thành công hay th t b i. Ta d nh n th y r ng c hai th t c anc1 và anc2 u có kh năng ưa ra câu tr l i cho m i ki u câu h i. Còn anc3 thì không ch c ch n. Ch ng h n câu h i sau ây gây ra th t b i : anc3(liz, jim) ERR 212 Not enough global stack vì d n n nh ng l i g i quy vô h n. Như v y, ta không th xem anc3 là úng n v m t th t c. Tóm t t chương 2 Nh ng khái ni m ã ư c gi i thi u : • ích tho mãn, thành công ích không tho mãn/b th t b i, ích b xoá, nghĩa khai báo, nghĩa th t c, nghĩa lôgich, quay lui. th nghi m c a m t m nh , bi n th c a m t m nh L p trình trên ngôn ng Prolog là nh nghĩa các quan h và t câu h i trên các • quan h này. M t chương trình Prolog bao g m các m nh . Có ba ki u m nh : s ki n, • lu t và câu h i. M t quan h có th ư c c t b i các s ki n, b ng cách ghi nh n b −n i • tư ng tho mãn quan h , hay thi t l p các lu t liên quan n quan h . M t th t c là m t t p h p các m nh liên quan n cùng m t quan h . • Vi c t các câu h i trên các quan h tương t vi c v n tin m t cơ s d li u. • Prolog tr l i câu h i b ng cách li t kê t p h p các i tư ng làm tho mãn câu h i này. Trong Prolog, khi m t i tư ng làm tho mãn m t câu h i thì vi c tr l i câu • h i luôn luôn là m t quá trình ph c t p s d ng suy di n lôgich, khai thác các kh năng khác nhau, và cơ ch quay lui. Prolog ti n hành t ng quá trình này và v nguyên t c, NSD có th hi u ư c. Ngư i ta phân bi t nghĩa khai báo và nghĩa th t c khi l p trình. M t chương • trình Prolog thư ng có nghĩa khai báo là ch y u. Tuy nhiên, ngư i ta v n tìm th y nghĩa th t c trong m t s chương trình Prolog. Theo nghĩa th t c, chương trình Prolog th c hi n quá trình tìm ki m, so • kh p và quay lui.
57 Ng nghĩa c a chương trình Prolog Ng nghĩa khai báo c a Prolog xác nh n u m t ích là úng i v i m t • chương trình ã cho, tương ng v i ràng bu c c a các bi n. Ngư i ta quy ư c vi t phép giao (and) c a hai ích b ng cách t m t d u • ph y gi a chúng, phép ho c (or) b i m t d u ch m ph y. Ng nghĩa th t c c a Prolog ư c th hi n b i m t th t c tìm ki m làm • tho mãn m t danh sách các ích t m t chương trình ã cho. N u tìm ki m tho mãn, Prolog tr v các ràng bu c các bi n tương ng. N u t i m t bư c nào ó b th t b i, th t c này cho phép t ng quay lui (backtracking) tìm ki m tìm các kh năng khác có th d n n thành công. Nghĩa khai báo c a các chương trình thu n Prolog không ph thu c s s p • t các m nh , cũng như không ph thu c s s p t các ích bên trong các m nh . Nghĩa th t c ph thu c th t các ích và các m nh . Th t s p t này • có th nh hư ng n tính hi u qu ch y chương trình, và có th d n n nh ng l i g i quy vô h n. Cho trư c m t khai báo úng, có kh năng làm t i ưu hi u qu v n hành c a • h th ng b ng cách thay i th t các m nh , mà v n m b o tính úng n v m t khai báo. S s p t l i th t các ích và các m nh là m t trong nh ng phương pháp nh m tránh các vòng l p qu n vô h n. Còn có nh ng k thu t khác t ng quát hơn tránh các vòng l p qu n vô h n, • và làm cho chương trình v n hành áng tin c y hơn. Bài t p chương 2 1. T chương trình Prolog dư i ây: aeroplane(concorde). aeroplane(jumbo). on(fred, concorde). on(jim, No_18_bus). bird(percy). animal(leo). animal(tweety). animal(peter). has_feathers(tweety). has_feathers(peter). flies(X) :- bird(X). flies(X) :- aeroplane(X). flies(X) :- on(X, Y), aeroplane(Y).
58 L p trình lôgic trong Prolog bird(X) :- animal(X), has_feathers(X). Hãy cho bi t các k t qu nh n ư c t câu h i : ?- flies(X). b ng cách li t kê theo th t : X=kq1; X=kq2; v.v... 2. S d ng sơ ã cho trong ph n lý thuy t, hãy tìm hi u cách Prolog tìm ra các câu tr l i i v i các câu h i dư i ây. V sơ minh h a tương n g theo ki u sơ ã cho. Có kh năng Prolog quay lui không ? a) ?- parent(mary , bill). b) ?- mother(mary , bill). c) ?- grand parent(mary, ann). d) ?- grand parent(bill , jim). 3. Vi t l i chương trình dư i ây, nhưng không s d ng d u ch m h i : translate (Number, word) :- Number = 1, Word = one; Number = 2, Word = two; Number = 3, Word = three. 4. T chương trình execute trong lí thuy t, hãy v sơ quá trình th c hi n c a Prolog t câu h i sau : ?- thick( X ) , dack( X ). Hãy so sánh các quá trình mô ph ng câu h i trên và các ích dư i ây : ?- dack( X ), thick( X ). 5. i u gì x y ra khi yêu c u Prolog tr l i câu h i sau ây : ?- X = f( X ). So kh p có thành công không ? Gi i thích vì sao m t s h th ng Prolog tr l i : X = f(f(f(f(f(f(f(f(f(f( ... )))))))))) Yes 6. Tìm các phép thay th h p th c và tìm k t qu (n u có) c a các phép so kh p sau ây : a(1, 2) = a(X, X). a(X, 3) = a(4, Y). a(a(3, X)) = a(Y).
59 Ng nghĩa c a chương trình Prolog 1+2 = 3. X = 1+2. a(X, Y) = a(1, X). a(X, 2) = a(1, X). 7. Cho trư c chương trình dư i ây : f( 1, one ). f( s(1) , two ). f( s( s( 1 ) ) , three ). s( s( s( X ) ) ), N ) :- f( f(X , N+3). Hãy cho bi t cách Prolog tr l i các câu h i sau ây (khi có nhi u câu tr l i có th , hãy ưa ra ít nh t hai câu tr l i) ? a) ?- f( s( 1 ) , A ). b) ?- f( s( s( 1 ) ) , two ). c) ?- f( s( s( s( s( s( s( 1 ) ) ) ) ) ), C ). d) ?- f( D, three ). 8. Cho các v t p, a1, a2, a3, a4 ư c nh nghĩa b i các m nh sau ây : p(a, b). p(b, c b). a1(X, Y) :- p(X, Y). a1(X, Y) :- p(X, Z), a1(Z, Y). a2(X, Y) :- p(X, Y). a2(X, Y) :- a2(Z, Y), p(X, Z). a3(X, Y) :- p(X, Z), a3(Z, Y). a3(X, Y) :- p(X, Y). a4(X, Y) :- a4(Z, Y), p(X, Z). a4(X, Y) :- p(X, Y). a) V cây h p gi i SLD có các g c là a1(a, X), a2(a, X), a3(a, X), a4(a, X) ? b) So sánh nghĩa lôgich c a các v t a1, a2, a3, a4 ? 9. Vi t gói các m nh nh nghĩa các hàm sau : a) greathan(X, N) tr v giá tr X n u X > N, tr v N n u không ph i.
60 L p trình lôgic trong Prolog b) sum_diff(X, Y, X) tr v trong Z giá tr t ng X + Y n u X > Y, tr v hi u X - Y n u không ph i. 10. Vi t chương trình Prolog t bi u di n lôgich sau ây : ∀X: pet(X) ∧ small(X) → apartmentpet(X) ∀X: cat(X) ∨ dog(X) → pet(X) ∀X: poodle(X) → dog(X) ∧ small(X) poodle(fluffy) T t câu h i Prolog và v sơ quá trình th c hi n.
CHƯƠNG 3 C ác phép toán và s hc Chương này trình bày s h c sơ c p, các phép toán và m t s v t chu n ư c s d ng trong các chương trình Prolog. I. S hc I.1. Các phép toán s h c Như ã bi t, Prolog là ngôn ng ch y u dùng x lý ký hi u, không thích h p tính toán s . Do v y, các phương ti n tính toán trong h u h t các h th ng Prolog u r t h n ch . Sau ây là b ng các phép toán s h c chu n (standard arithmetic operations) c a Prolog : Ký hi u Phép toán C ng (addition) + Tr (subtraction) - Nhân (multiplication) * Chia s th c (real division) / Chia s nguyên (integer division) // Chia l y ph n dư (modulus) mod Lu th a (power) ** I.2. Bi u th c s h c Bi u th c s h c (arithmetic expressions) ư c xây d ng nh v t is. V t này là m t phép toán ti n t (infix operator) có d ng : Number is Expr Tham i bên trái phép toán is là m t i tư ng sơ c p. Tham i bên ph i là m t bi u th c s h c ư c h p thành t các phép toán s h c, các s và các bi n. Vì phép toán is s kh i ng vi c tính toán, cho nên khi th c hi n ích 61
62 L p trình lôgic trong Prolog này, t t c các bi n c n ph i ư c ràng bu c v i các giá tr s . Prolog so kh p thành công n u Number kh p ư c v i Expr. N u Expr là ki u th c (float) thì ư c xem như m t só nguyên. Ví d I.1 : ?- X is 3*4. X = 12 Yes ?- is(X, 40+50). X = 90 Yes ?- 1.0 is sin(pi/2). % sai do sin(pi/2) ư c làm tròn thành 1 No ?- 1.0 is float(sin(pi/2)). Yes Trong Prolog, các phép toán s h c kéo theo s tính toán trên các d li u. th c hi n các phép toán s h c, c n bi t cách g i dùng theo ki u Prolog mà không th g i tr c ti p ngay ư c như trong các ngôn ng l p trình m nh l nh. Ch ng h n, n u NSD c n c ng hai s 1 và 2 mà l i vi t như sau : ?- X = 1 + 2 thì Prolog s tr l i theo ki u c a Prolog : X=1+2 mà không ph i là X = 3 như mong mu n. Lý do r t ơn gi n : bi u th c X = 1 + 2 ch là m t h ng c a Prolog mà hàm t chính là +, còn 1 và 2 là các tham i c a nó. Không có gì trong ích trư c nó Prolog ti n hành phép c ng. Sau ây là m t s ví d : ?- X = 1 + 1 + 1. X = 1 + 1 + 1 (ou X = +(+(1, 1), 1)). Prolog ti n hành tính toán trên các phép toán s h c, s d ng phép toán is như sau : ?- X is 1 + 2. X=3 Phép c ng th c hi n ư c là nh m t th t c c bi t k t h p v i phép toán +. Nh ng th t c như v y ư c g i là th t c thư ng trú (built-in procedures). ?- X = 1 + 1 + 1, Y is X. X = 1 + 1 + 1, Y = 3. ?- X is 1 + 1 + a.
63 Các phép toán và s h c ERROR: Arithmetic: `a/0' is not a function (sai do a không ph i là hàm s ) ?- X is 1 + 1 + Z. ERROR: Arguments are not sufficiently instantiated (sai do a không ph i là s ) ?- Z = 2, X is 1 + 1 + Z. Z=2 X=4 ưu tiên c a các phép toán s h c ti n nh c a Prolog cũng là ưu tiên tho mãn tính ch t k t h p trong toán h c. Các c p d u ngo c có th làm thay i th t ưu tiên gi a các phép toán. Chú ý r ng +, -, *, / và // ư c nh nghĩa như là yfx, có nghĩa là vi c tính toán ư c th c hi n t trái sang ph i. Ví d , bi u th c : X is 5 -2 – 1 ư c gi i thích như là : X is ( 5 -2 ) - 1 Do ó : ?- X is 5 -2 - 1. X=2 Yes ?- X = 5 -2 - 1. X = 5-2-1 Yes Các phép so sánh giá tr s h c trong Prolog ư c th c hi n theo nghĩa Toán h c thông thư ng. Ch ng h n, ta c n so sánh n u tích c a 277 v i 37 là l n hơn 10000 v i ích sau : ?- 277 * 37 > 10000. Yes Bây gi gi s ta có quan h birth, cho phép liên h m t ngư i v i ngày tháng năm sinh c a ngư i ó. Ta có th tìm ư c tên c a nh ng ngư i sinh ra gi a năm 1950 và năm 1960 (k c hai năm này) b ng cách t câu h i : ?- birth( Name, Year ), Year >= 1950, Year
64 L p trình lôgic trong Prolog ?- X is exp(10). X = 22026.5 Yes ?- X is sqrt(9). X=3 Yes 7 ?- X is abs(1.99). X = 1.99 Yes ?- X is pi. X = 3.14159 Yes I.3. nh nghĩa các phép toán trong Prolog Bi u th c toán h c thư ng ư c vi t dư i d ng trung t (infix) như sau : 2*a+b*c v i + và * là các phép toán (operator), còn a, b và c là các toán h ng (operand), hay tham i (argument). Bi u th c trên còn ư c vi t dư i d ng ti n t (prefix) nh các hàm t + và * như sau : +( *(2, a), *(b, c) ) ho c d ng h u t (postfix) như sau : ( (2, a) *, (b, c) * )+ Do thói quen, ngư i ta thích vi t các bi u th c d ng trung t d c hơn. Prolog cho phép vi t các bi u th c dư i d ng trung t , là bi u di n bên ngoài, nhưng th c ch t, các bi u th c ư c bi u di n bên trong v n d ng ti n t , theo quy ư c vi t các h ng trong m t m nh . + * * 2 a b c Hình I.1. Bi u di n d ng cây c a bi u th c 2 * a + b * c Khi vi t a + b, Prolog hi u r ng ó là bi u th c +(a, b). Prolog có th hi u ư c úng n các bi u th c như là a + b * c, c n cho Prolog bi t r ng phép nhân * có ưu tiên cao hơn phép c ng +. Khi ó bi u th c này ph i ư c vi t dư i d ng : +( a, *(b, c) ) mà không ph i là :
65 Các phép toán và s h c *( + (a, b), c) Prolog quy ư c phép toán có ưu tiên cao nh t là hàm t chính c a h ng. N u các bi u th c ch a + và * tuân theo nh ng quy ư c thông thư ng, thì cách vi t a + b * c và a + (b * c) ch là m t. Còn n u mu n thay i th t ưu tiên, thì c n vi t rõ ràng b ng cách s d ng các c p d u ngo c (a + b) * c : M i NLT có th nh nghĩa các phép toán riêng c a mình, ch ng h n nh nghĩa các nguyên t is và support như là nh ng phép toán trung t vi t các s ki n trong m t chương trình. Ch ng h n : tom bald wall support ceiling là nh ng s ki n ư c vi t trong Prolog : is( tom, bald ). support( wall, ceiling ). M i phép toán là m t nguyên t có ưu tiên là m t giá tr s , tuỳ thu c phiên b n Prolog, thông thư ng n m trong kho ng gi a 1 và 1200. Các phép toán ư c c t b i h n h p tên phép toán f và các bi n (tham i) x và y. M i c t cho bi t cách k t h p (associative) phép toán ó và ư c ch n sao cho ph n ánh ư c c u trúc c a bi u th c. M t phép toán trung t ư c ký hi u b i m t f t gi a hai tham i d ng xfy. Còn các phép toán ti n t và h u t ch có m t tham i ư c t trư c (ho c t sau tương ng) d u phép toán f. Có ba nhóm ki u phép toán trong Prolog như sau : Các phép toán Không k t h p K t h p ph i K t h p trái Trung t xfx xfy yfx Ti n t fx fy H ut xf yf Hình I.2. Ba nhóm ki u phép toán trong Prolog. Có s khác nhau gi a x và y. gi i thích, ta ưa vào khái ni m ưu tiên c a tham i. N u các d u ngo c bao quanh m t tham i, hay tham i này là m t i tư ng không có c u trúc, thì ưu tiên c a nó b ng 0. ưu tiên c a m t c u trúc là ưu tiên c a hàm t chính. Do x là m t tham i nên ưu tiên c a x ph i th p hơn h n ưu tiên c a phép toán f, còn tham i y có ưu tiên th p hơn ho c b ng ưu tiên c a phép toán f. Khi g p m t bi u th c ch a phép toán op d ng : a op b op c Tính k t h p xác nh v trí d u ngo c theo th t ưu tiên như sau : • N u là k t h p trái, ta có : (a op b) op c
66 L p trình lôgic trong Prolog N u là k t h p ph i, ta có : a op (b op c) • Các quy t c trên cho phép lo i b tính nh p nh ng c a các bi u th c ch a các phép toán có cùng ưu tiên. Ch ng h n : a-b-c s ư c hi u là (a - b ) - c, mà không ph i a - (b - c). ây, phép tr «-» có ki u trung t yfx. Xem Hình I.3 dư i ây. Bây gi ta l y m t ví d khác v phép toán ti n t m t ngôi not. N u not ư c x p ki u fy, thì bi u th c sau ây vi t úng : not not p
67 Các phép toán và s h c - - a - - c ưu tiên 0 ưu tiên b c 0 a b Cách gi i thích 1 : (a - b ) – c Cách gi i thích 2 : a - (b - c) Hình I.3. Hai cách gi i thích cho bi u th c a - b - c v i gi thi t r ng phép tr «- ưu tiên là 500. N u «-» là yfx, thì cách gi i thích 2 là sai » có ưu tiên c a b - c không th p hơn ưu tiên c a «-». vì Trái l i, n u phép toán not ư c nh nghĩa như là fx, thì bi u th c trên s không còn úng n a, vì r ng tham i c a not u tiên là not p, s có cùng ưu tiên v i nó. Trong trư ng h p này, bi u th c ph i ư c vi t k t h p v i các c p d u ngo c : not ( not p ) Tính d c c a m t chương trình tuỳ thu c vào cách s d ng các phép toán. Trong các chương trình Prolog, nh ng m nh s d ng phép toán m i do ngư i dùng nh nghĩa thư ng ư c g i là các ch d n hay nh hư ng (directive). Các ch d n ph i xu t hi n trư c khi m t phép toán m i ư c s d ng n trong m t m nh , có d ng như sau : :- op( ưu tiên, Cách k t h p, Tên phép toán). Ch ng h n ngư i ta nh nghĩa phép toán is nh ch d n : :- op( 600, xfx, is ). Ch d n này báo cho Prolog bi t r ng is s ư c s d ng như là m t phép toán có ưu tiên là 600, còn ký hi u c t xfx ch nh ây là m t phép toán trung t . Ý nghĩa c a xfx như sau : f là d u phép toán ư c t gi a, còn x là tham i ư c t hai bên d u phép toán. Vi c nh nghĩa m t phép toán không kéo theo m t hành ng (action) ho c m t thao tác (opration) nào. V nguyên lý, không m t thao tác nào trên d li u ư c k t h p v i m t phép toán (tr m t vài trư ng h p hi m g p c bi t, như các phép toán s h c). Tương t như m i hàm t , các phép toán ch ư c dùng c u trúc các hàm t , mà không kéo theo m t thao tác nào trên các d li u, d u r ng tên g i «phép toán» có th g i lên vai trò ho t ng. Prolog cung c p s n m t s phép toán chu n. Nh ng phép toán ti n nh nghĩa này thay i tùy theo phiên b n Prolog. Hình 3.5 dư i ây trình bày m t s phép toán chu n ti n nh nghĩa c a Prolog. Chú ý r ng cùng m t m nh có th
68 L p trình lôgic trong Prolog nh nghĩa nhi u phép toán, mi n là chúng cùng ki u và cùng ưu tiên. Các tên phép toán ư c vi t trong m t danh sách. Các phép toán ti n nh nghĩa trong Prolog như sau : ưu tiên Cách k t h p Các phép toán 1200 -->, :- xfx 1200 :-, ?- fx 1100 ;, | xfy 1000 , xfy 900 \+ fy 900 ~ fx =, @=, \=, \==, is 600 xfy : 500 +, -, /\, \/, xor yfx 500 +, -, ?, \ fx 400 *, /, //, , mod, rem yfx 200 ** xfx 200 ^ xfy Hình 3.5. Các phép toán ti n nh nghĩa trong Prolog. minh ho , ta xét ví d vi t m t chương trình x lý các bi u th c lôgich (boolean). Gi s ta c n bi u di n m t trong các nh lý tương ương c a Morgan, ư c vi t dư i d ng toán h c như sau : ~ ( A & G ) ~ A ∨ ~ B Trong Prolog, m nh trên ph i ư c vi t như sau : equivalent( not ( and( A, B ) ), or(not ( A ), not ( B ) ) ). Tuy nhiên, cách l p trình t t nh t là th tìm cách b o lưu t i a s gi ng nhau gi a các ký hi u trong bài toán ã cho v i các ký hi u ư c s d ng trong chương trình..