Vị từ bagof and findall
Chúng ta có thể sinh ra, nhờ backtracking, tất cả những đối tượng, từng đối
tượng một thỏa mãn được mục tiêu nào đó. Mỗi lần một lời giải mới được tạo
ra, lời giải cũ đã biến mất và không còn có thể truy đạt đến.
Tuy nhiên, đôi khi ta cần gom tất cả các lời giải lại, thí dụ, thành một list.
Vị từ thư viện bagof và findall phục vụ cho mục đích này.
Vị từ bagof(X,P,L) sinh ra một list L các đối tượng X thỏa mãn quan hệ P.
Điều này có nghĩa chỉ khi X và P có những biến chung.
Ví dụ: Ta có các sự kiện
age(peter,7).
age(ann,5).
age(pat,8).
age(tom,5).
Để có một danh sách tất cả những đứa trẻ 5 tuổi, ta dùng truy vấn:
?- bagof( Child, age(Child, 5), List).
List = [ann, tom]
Nếu ta để tuổi là biến chưa gán trị, ta sẽ được, thông qua sự quay lui, ba danh
sách, tuỳ theo ba độ tuổi của trẻ.
?- bagof( Child, age(Child, Age), List).
Age = 7
List = [peter];
Age = 5
List = [ann, tom];
Age = 8
List = [pat]
No
Một vị từ tương tự như bagof là vị từ findall.
Vị từ findall(X, P,L) sinh ra một list L các đối tượng X thỏa mãn quan hệ P.
Điểm khác biệt của findall với bagof là tất cả các đối tượng X được thu gom
bất kể những lời giải khác nhau cho các biến trong P mà khác với X.
Thí dụ:
?- findall( Child,age(Child, Age), List).
List = [peter, ann, pat, tom]
68 trang |
Chia sẻ: thucuc2301 | Lượt xem: 700 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Prolog techniques - Chapter 2: Prolog Programming Techniques, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
1
Chapter 2
KỸ THUẬT LẬP TRÌNH PROLOG
(Prolog Programming Techniques)
2
Nội dung
Caùch bieåu dieãn list
Soá hoïc
Caùch bieåu dieãn caáu truùc
Ñieàu khieån backtracking
Xuaát/nhaäp
Moät soá vò töø thö vieän quan troïng
3
CÁCH BIỂU DIỄN LIST
List là một cấu trúc dữ liệu đơn giản được dùng trong lập trình phi số
học. Một list là một chuỗi với số lượng bất kỳ của các phân tử .
Thí dụ: [ann, tennis, tom, skiing] là một list ở PROLOG
Tuy nhiên đấy chỉ là hình thức bên ngoài của list. Lưu ý rằng, mọi đối
tượng có cấu trúc ở PROLOG được diễn tả bằng cấu trúc cây. list cũng
vậy.
Một list rỗng được diễn tả bởi [ ]
Một list khác rỗng được coi như gồm hai thành phần:
Phần tử đầu tiên của list được gọi là đầu (head) của list
Phần con lại của list được gọi là đuôi (tail) của list
Trong thí dụ trên, ann là đầu của list và [ tenmis, tom, skiing] là đuôi
của list.
4
Một cách tổng quát , head và tail của một list được phối
hợp lại thành ra một cấu trúc nhờ một hàm tử đặc biệt.
Việc chọn hàm tử này tuỳ thuộc vào Prolog cụ thể. Ở đây
giả định rằng đó là dấu chấm .
.( Head, Tail)
Thí dụ: .( ann, .( tennis,. ( tom, .(skiing, []))))
ann
tennis
tom
skiing
[ ]
.
.
.
.
5
Một list mà chỉ gồm một phần tử tương đương với :
[skiing] = .(skiing, [ ])
Lối ký hiệu dấu chấm không dễ dùng bằng lối ký hiệu [ , ].
Lập trình viên có thể dùng cả hai lối ký hiệu, nhưng lối ký
hiệu dấu ngoặc vuông thông dụng hơn. Nhưng hãy nhớ rằng
các list được diễn tả bên trong bằng các cây nhị phân.
Các phần tử của một list cũng có thể là bất kỳ loại đối
tượng nào, kể cả các list. Đuôi của một list có thể được coi
như là một đối tượng.
Thí dụ: L = [ a,b,c ]
Tail = [b, c] và L = .(a, Tail )
6
Trong lối ký hiệu dấu ngoặc vuông, Prolog đưa vào
dấu để tách biệt đầu và đuôi của list
L = [ a Tail ]
[ a,b,c ] = [ a [b,c] ] = [ a,b [c] ] = [ a,b,c [ ] ]
Tóm lại: Prolog cung cấp 3 cách viết :
[Item1, Item2, ]
[Head Tail ]
[Item1, Item2, Others ]
7
CÁC THAO TÁC TRÊN LIST
2.1 Quan heä thaønh vieân:
Vò töø member( X , L ) xeùt xem X coù phaûi laø moät phaàn töû cuûa
list L.
Thí duï: member( b, [ a,b,c ]) true
member( b, [ a| [b, c] ]) false
member( X, [ X _ ]).
member( X, [ Head Tail ]):- member( X, Tail).
8
Ghép kề ( Concatenrtion)
Vị từ: conc(L1, L2 , L3 ): L3 là sự ghép kề L1 và L2.
Thí dụ : conc( [a,b ], [c,d ], [a,b,c,d] ) true
conc([], L , L ).
conc([ X L1], L2, [ X, L3 ]) :- conc( L1 , L2, L3).
Ta có thể dùng conc để phân rã một list thành rã hai list :
?- conc( L1, L2, [ a,b,c] ).
L1 = [ ]
L2 = [ a,b,c ]
L1 = [ a ]
L2 = [ b,c ]
L1 = [a,b ]
L2 = [ c ]
L1 = [ a,b,c ]
L2 = [ ]
9
Thêm một phần tử vào list
Thêm một phần tử vào đầu của list, ta cần một procedure như
sau :
add( X, L , [ X L ] ). ( Sự kiện)
2.4 Xoá một phần tử ra khỏi list :
Xoá một phần tử X ra khỏi list L, có thể được lập trình như một
vị từ :
del(X , L , L1 )
del( X, [ X Tail ], Tail ).
del( X, [ Y Tail ] , [ Y Tail1] ) :- del( X , Tail , Tail1 ).
? - del( a, [ a,b,a,a ] , L ).
L = [ b,a,a ];
L = [ a,b,a ];
L = [ a,b,a ]
Ta có thể dùng vị từ del để định nghĩa thao tác thêm một phần tử
vào bất kỳ chỗ nào trong một list .
insert( X, List , BiggerList ) :- del( X, BiggerList, List ).
10
Sublist
Vị từ này có hai đối số : sublist( S , L )
Vị từ xét xem list S có phải là một list con của List L không.
sublist( S, L ) :- conc(L1, L2, L), conc( S , L3 , L2 ).
L1 S L3
L2
L
11
CÁC THAO TÁC TRÊN LIST
2.1 Quan heä thaønh vieân:
Vò töø member( X , L ) xeùt xem X coù phaûi laø moät
phaàn töû cuûa list L.
Thí duï: member( b, [ a,b,c ]) true
member( b, [ a| [b, c] ]) false
member( X, [ X _ ]).
member( X, [ Head Tail ]):- member( X, Tail).
12
Hoán vị
Công dụng: sinh ra các hoán vị của một list.
Vị từ :
permutation( [ ], [ ]).
permutation( [X L], P ) :- permutation( L, L1), insert( X , L1, P ).
Vị từ insert đã định nghĩa ở phần trước.
?- permutation( [ a,b,c ], P).
p = [ a,b,c ];
p = [ a,c,b ]; 3 ! = 6
p = [ b,c,a ];
p = [b,a,c ];
p = [ c,a,b ];
p = [ c,b,a ];
13
SỐ HỌC
Các phương tiện để tính toán số ở Prolog khá đơn giản. Các toán tử có sẵn gồm:
+, -, *, /, mod
Lưu ý:
Trong Prolog khi viết X = 1 + 2, X được dùng đồng nhất với toán hạng 1 + 2
?- X = 1+ 2.
X = 3
Toán tử is bắt buộc sự định trị của biểu thức số học đi sau nó:
?- X is 1 + 2
X = 3
Số học có liên quan đến khi so sánh các trị số học.
?- 277*39 > 10000.
yes
Các toán tử số học so sánh:
>
<
> =
< =
=:= equal
=\= not equal
14
Toán tử = ở X = Y khiến cho hai đối tượng X và Y hợp nhất với nhau
(khiến cho biến trong X và Y được gán trị cụ thể).
Trái lại toán tử X =:= Y khiến cho X và Y được định trị số học với hai
trị đem so sánh với nhau.
?- 1+2 =:= 2+1
yes
?- 1+2 = 2+1
no
Vài thí dụ:
Tìm ước số chung lớn nhất của 2 số nguyên, X, Y.
Nếu X = Y thì D = X
Nếu X < Y thì D là ước số chung lớn nhất của X và Y – X
Nếu Y < X thì giống như (2) những đổi vai trò Y và X
gcd(X,X,X).
gcd(X,Y,D):- X<Y, Y1 is Y – X, gcd(X,Y1,D).
gcd(X,Y,D):- Y<X, gcd(Y,X,D).
15
SỬ DỤNG CẤU TRÚC
Trong Prolog, ngoài list, cấu trúc (structure) là một phương
tiện lập trình khá mạnh để tạo cấu trúc dữ liệu.
Trong mục này, chúng ta học cách sử dụng cấu trúc qua một
thí dụ lập trình: bài toán Tám Con Hậu.
Bài toán 8 con hậu:
Đặt 8 con hậu trên một bàn cờ rộng ( 8 8 ô) sao cho không
có con hậu nào tấn công được các con hậu khác.
Lời giải sẽ được lập trình như một vị từ một đối số:
solution( Pos)
mà là đúng nếu Pos diễn tả một sắp xếp trong đó 8 con hậu
không thể tấn công nhau.
Có nhiều ý tưởng khác nhau cho bài toán này. Ta xem xét 3
chương trình khác nhau.
16
Cách giải 1
Chương trình 1:
Vấn đề diễn tả bàn cờ.
Một ô trong bàn cờ được diễn tả bằng một cặp toạ độ
( X ,Y )
p(X ,Y)
Như vậy bài toán là tìm 1 list cặp tọa độ có dạng
[p( X1 , Y1) , p( X2 , Y2), , p( X8 , Y8)] mà
thoả mãn đòi hỏi không tấn công.
17
1 2 3 4 5 6 7 8
X
X
X
X
X
X
X
X
8
7
6
5
4
3
2
1
[p(1,4) , p(2,2),
p( 3,7), p(4,3) ,..,
p(7,5) , p(8,1)]
laø moät lôøi giaûi
18
Cách giải 1 (tt)
Quan hệ solution được định nghĩa bằng cách xem xét 2 trường
hợp:
Case1. list các con hậu rỗng: list rỗng là một lời giải vì không có sự tấn công.
Case2. List các con hậu khác rỗng: [p(X , Y)| Others]
Con hậu thứ nhất ở vị trí (X , Y) và những con hậu khác ở các ô được mô tả
bởi list Others. Nếu đây là một lời giải thì 3 điều kiện sau phải thoả:
Bản thân Others cũng là lời giải đối với bàn cờ nhỏ hơn (n – 1)(n – 1).
X và Y phải là số nguyên từ 1 đến 8.
Con hậu ở ô (X,Y) không tấn công bất cứ con hậu nào ở danh sách Others.
solution([p(X ,Y) I Others]):-
solution(Others),
member( Y, [1,2,3,4,5,6,7,8]),
noattack( p(X,Y), others).
19
Cách giải 1 (tt)
Bây giờ cần phải định nghĩa điều kiện: “con hậu ở một ô
không tấn công một con hậu ở một ô khác”. Tức là không
cùng hàng, không cùng cột, và không cùng đường chéo.
Cái khuôn mẫu của lời giải sẽ đảm bảo các con hậu ở trên
các cột khác nhau. Do đó chỉ cần:
Các toạ độ Y của con hậu phải khác nhau
Chúng không cùng trên đường chéo tức là khoảng cách giữa các
ô theo trục X phải khác khoảng cách các ô theo trục Y.
20
% solution( boardposition)
solution([ ]).
solution([ p(X , Y) I Others]):-
solution( Others), member(Y , [1,2,3,4,5,6,7,8]),
noattack(p(X,Y), Others).
noattack( _ , [ ]).
noattack(p(X,Y), [ p(X1,Y1) I Others]):-
Y =\= Y1 , Y1 – Y = \ = X1 – X , Y1 – Y =\= X – X1,
noattack(p(X , Y), Others).
member( I,[ I |_ ]).
member(I, [_I Rest]):- member(I , Rest).
?-solution([p(1,Y1),p(2,Y2),p(3,Y3),p(4,Y4), p(5,Y5),
p(6,Y6), p(7,Y7), p(8,Y8)]).
21
Chương trình 2
Trong cách biểu diễn bàn cờ ở chương trình 1, mỗi lời giải có dạng
[p(1,Y1), p(2,Y2), , p(8,Y8)]
Vì các con hậu được đặt ở các cột kế tiếp nhau, ta không hề mất thông
tin nếu ta bỏ qua các tọa độ X. Như vậy, một cách biểu diễn bàn cờ tiết
kiệm chỗ hơn là chỉ giữ lại các toạ độ Y của con hậu:
[Y1 , Y2,, Y8 ]
Để tránh tấn công nhau, 2 con hậu không ở trên cùng hàng. Điều này
đặt một ràng buộc trên các toạ độ Y. Do đó lời giải được diễn tả bằng
một hoán vị của list
[1,2,3,4,5,6,7,8].
Một hoán vị S là lời giải nếu tất cả các con hậu là an toàn.
Do đó, ta có thể viết:
solution(S) :- permutation([1,2,3,4,5,6,7,8], S), safe(S).
22
Chương trình 2 (tt)
Vị từ permutation thì ta đã có, giờ cần định nghĩa vị từ safe.
Ta có tách định nghĩa của safe thành 2 trường hợp:
S : rỗng thì S safe
S : không rỗng và có dạng [ Queen I Others]. S sẽ an toàn nếu danh sách
Others là an toàn và Queen không tấn công bất kì một con con hậu nào
trong danh sách Others.
safe([ ])
safe([Queen I Others]):- safe(Others), noattack(Queen, Others)
Quan hệ noattack được định nghĩa dựa vào nhận xét:
23
°
°
X
°
X_Dist = 3
X_Dist = 1
Others
24
Nếu Others rỗng thì Queen không hề có tấn công.
Nếu Others khác rỗng thì Queen không được tấn công
con hậu đầu tiên trong Others (có khoảng cách X_dist = 1
từ Queen) và các con hậu ở đuôi của Others (có khoảng
cách X_dist >1 đối với Queen)
solution(Queens):-permutation([1,2,3,4,5,6,7,8], Queens),
safe(Queens).
permutation( [ ], [ ]).
permutation([ X I L], P):- permutation(L, L1),
insert(X, L1, P).
25
del(X, [XI Tail], Tail).
del(X,[Y I Tail], [Y I Tail1]):- del(X, Tail, Tail1).
insert(X, List, Biggerlist):- del(X ,Biggerlist, List).
safe([ ]).
safe([Queen I Others]):- safe(Others),
noattack(Queen, Others, 1).
noattack( _ , [ ], _ ).
noattack(Y, [Y1 I Ylist], Xdist):-
Y1 – Y=\= Xdist , Y – Y1 =\= Xdist,
Dist1 is Xdist +1, noattack(Y, Ylist, Dist1).
26
Chương trình 3
Trong chương trình này, mỗiô của bàn cờ được biểu diễn theo 4 toạ độ:
x: hàng
y: cột
u: đường chéo thứ nhất
v: đường chéo thứ hai.
Với x, y cho trước, u và v được xác định bởi: u = x –y và v = x –y.
Các miền trị của 4 chiều là:
Dx = [1, 2, 3, 4, 5, 6, 7, 8]
Dy = [1, 2, 3, 4, 5, 6, 7, 8]
Du = [-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7]
Dv = [ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
27
Bài toán được giải như sau:
Chọn 8 bộ tứ từ các miền trị Dx, Dy, Du,
Dv sao cho không chọn cùng trị từ bất kỳ miền trị nào
cho các bộ tứ này. Cho trước 4 miền trị, chọn vị trí cho
con hậu thứ nhất, loại các trị tương ứng ra khỏi cả 4 miền
trị và dùng các phần còn lại của các miền trị để gán cho
các con hậu còn lại.
% solution (Ylist) is true if Ylist is a list of
%Y-coordinates of eight non-attacking queens
solution(Ylist):-
sol(Ylist, [1, 2, 3, 4, 5, 6, 7, 8],
[1, 2, 3, 4, 5, 6, 7, 8],
[-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7],
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]).
28
y
x
-7
-2 +7
u = x - y
12 14 16 2 6 v = x + y
8
7
6
5
4
3
2
1
1 2 3 4 5 6 7 8
29
Chương trình 3
sol([], [], _, _, _).
sol( [Y|Ylist], [X|Dx1], Dy, Du, Dv):-
del(Y, Dy, Dy1),
U is X – Y,
del(U, Du, Du1),
V is X + Y,
del(V, Dv, Dv1),
sol(Ylist, Dx1, Dy1, Du1, Dv1).
del(Item, [Item| List], List).
del(Item, [First| List], [First| List1]):-
del(Item, List, List1).
30
Nhận xét
Ba cách giải bài toán 8 con hậu dùng ba cách biểu diễn dữ liệu
khác nhau.
Trong ba chương trình, cách giải III minh hoạ một cách tiếp
cận đáng chú ý: tạo ra 8 cấu trúc bốn thành phần, mỗi thành
phần từ những miền trị khác nhau sao cho thỏa mãn những
ràng buộc.
Trong ba chương trình, cách nào là tốt nhất?
Cách II là kém nhất vì nó phải tạo ra tất cả các hoán vị rồi mới tìm
ra hoán vị hợp lệ để làm lời giải. (Phương pháp sinh và thử).
Cách I và III có thể nhận dạng và loại bỏ ngay những hoán vị
“không an toàn” ngay khi chúng vừa được tạo ra chưa đầy đủ.
Cách III hữu hiệu nhất.
“Thu hẹp các miền trị” theo cách “lan truyền ràng buộc”.
31
ĐIỀU KHIỂN BACKTRACKING
Ngăn chặn Backtracking:
Trên lý thuyết ta có thể điều khiển quá trình thực thi
một CT bằng cách sắp lại thứ tự của các mệnh đề và
tiểu mục tiêu.
Ở đây ta xem xét một phương tiện điều khiển khác,
được gọi là nhát cắt (cut) để ngăn chặn hồi quy.
Prolog thường tự động quay lui khi cần thiết để thoả
một mục tiểu mục tiêu.
Tự động quay lui là một tính chất mà làm nhẹ gánh cho
lập trình viên khỏi phải lập trình quay lui một cách
tường minh.
Mặt khác, quay lui không điều khiển có thể làm cho CT
không hữu hiệu.
32
Đôi khi, ta cần phải điều khiển ngăn chặn quay lui. Điều này được thực
hiện bằng phương tiện “cut”.
Xét thí dụ:
Qui tắc 1: nếu X < 3 thì Y = 0
Qui tắc 2: Nếu 3 ≤ X < 6 thì Y =2
Qui tắc 3: Nếu 6 ≤ X thì Y = 4
Trong Prolog, ta định nghĩa vị từ f(X,Y) như sau:
f(X, 0):- X < 3
f(X , 2):- 3≤ X, X >6.
f(X , 4):- 6 ≤ X.
Xem xét truy vấn
?- f(1,Y), 2<Y.
Y = 0 và tiểu mục tiêu 2<0 sẽ thất bại và làm cho toàn bộ mục tiêu thất
bại. Prolog sẽ hồi quy với (2), (3) một cách vô ích.
33
Ngăn chặn Backtracking (tt.)
Vì 3 mệnh đề có tính loại trừ lẫn nhau, chỉ một trong số chúng là thành
công.
Chương trình được viết lại là
f(X,0):- X < 3,!.
f(X,2) :- 3 ≤ X, X <6,!.
f(X, 4):- 6 ≤ X.
Cut ngăn chặn hồi quy ngay tại điểm mà nó xuất hiện trong chương
trình.
Thực hiện lại truy vấn
?-f(1,Y), 2 < Y.
các nhánh tương ứng với rule 2 và rule 3 sẽ không được thực hiện.
Tóm lại: đưa “cut” vào, chúng ta chỉ thay đổi ý nghĩa thủ tục của
chương trình mà không ảnh hưởng đến ngữ nghĩa khai báo của chương
trình.
34
Bây giờ, hãy xem xét truy vấn
?- f(7,Y).
Y = 4.
Tiểu mục tiêu 3 ≤ X gây ra một sự thử thừa.
Diễn tả lại:
if X < 3 then Y =0,
else if X < 6 then Y = 2
else Y =4.
f(X,0):- X < 3,!.
f(X,2) :- X < 6,!.
f(X,4).
Lần này các kí hiệu cut không chỉ thay đổi ý nghĩa thủ tục mà còn ảnh
hưởng đến ý nghĩa của khai báo chương trình.
35
Định nghĩa: Tiểu mục tiêu cha (parent subgoal) là mục tiêu mà hợp nhất
với đầu mệnh đề có chứa kí hiệu “cut”.
Khi gặp phải một kí hiệu cut như là một mục tiêu nó thành công ngay
lập tức, nhưng nó buộc chặt hệ thống với những lựa chọn đã thực hiện
từ lúc “mục tiêu cha” được gọi cho đến lúc gặp phải ký hiệu cut. Tất cả
những lựa chọn khác nằm giữa tiểu mục tiêu cha và ký hiệu cut đều bị
loại bỏ.
G: tiểu mục tiêu cha
H:- B1, B2, , Bm ,!, , Bn
Giả sử tiểu mục tiêu G đối sánh với H của mệnh đề này, thì G là tiểu
mục tiêu cha. Tại lúc gặp phải kí hiệu cut, thì hệ thống đã tìm thấy lời
giải nào đó cho B1, B2, , Bm . khi gặp phải kí hiệu cut, lời giải hiện
hành của B1, B2, , Bm sẽ được chọn và toàn bộ những lựa chọn khác
sẽ bị loại bỏ. (Tiểu mục tiêu G sẽ kết với mệnh đề này: mọi cố gắng để
hợp nhất G với đầu của một vài mệnh đề khác sẽ bị ngăn chặn.)
36
Thí dụ:
C:- P,Q,R,!,S,T,U.
C:- V.
A:- B,C,D.
?- A.
Khi hợp nhất C trong A với mệnh đề C:- P,Q,R,!,S,T,U. ta được danh
sách mục tiêu:
B, P,Q,R,!,S,T,U,D
Backtracking có thể áp dụng cho P,Q,R nhưng một khi đã gặp ký hiệu
cut, tất cả những lựa chọn khác cho danh sách các tiểu mục tiêu P,Q,R
sẽ bị ngăn chận.
Mệnh đề C:- V sẽ không được chọn.
37
Một số thí dụ về cut:
Tính maximum.
max(X , Y , X) :- X ≥ Y.
max(X,Y,Y):- X < Y.
Hai qui taéc loaïi tröø hoã töông. Dieãn ñaït laïi
if X ≥ Y then max = X
else max = Y.
max(X,Y,X):- X≥ Y,!.
max(X,Y,Y).
Vò töø member moät lôøi giaûi:
Xeùt : member(X,L)
member(X,[X | _ ).
member(X,[Y | L):- member(X,L).
Chöông trình naøy khoâng taát ñònh (nondeterministic) : neáu X xuaát hieän nhieàu
laàn thì moãi laàn xuaát hieän ñeàu ñöôïc tìm thaáy.
a vaø [a,b,c,a,d]
38
Vò töø member moät lôøi giaûi
Ta có thể chuyển member về thành một procedure tất định mà chỉ tìm
thấy lần xuất hiện đầu tiên.
Chương trình thứ 2 :
member(X,[X| _]):- !.
member(X,[_ | L]) :- member(X,L).
Chương trình này sẽ đưa lại chỉ lời giải
?- member(X,[a,b,c]).
X = a
39
Đưa một phần tử vào một danh sách mà
không lặp lại.
Ta muốn đưa một phần tử X vào list L sao cho X được thêm vào chỉ khi
X không thấy trong L.
add(X,L, L1)
Nếu X là một phần tử của L thì L1 = L.
Ngược lại, L1 bằng với L có X điền thêm vào.
add(X,L,L): member(X,L),!.
add(X,L,[X|L]).
?- add(a,[a,b,c],L)
L = [a,b,c]
40
Sự phủ định như là một thất bại (negation as
failure)
Thí dụ: “ mary thích mọi thú vật trừ rắn”
like(mary,X):- snake(X),!, fail.
likes(mary,X):- animal(X).
fail là một subgoal đặc biệt, nó luôn luôn thất bại, nó làm cho tiểu mục
tiêu cha bị thất bại.
Thí dụ 2: ta muốn định nghĩa vị từ
different(X,Y)
different(X,X):- !, fail.
different(X,Y).
Qua hai ví dụ trên ta thấy nảy sinh nhu cầu về một vị từ not.
41
Vò töø not
Nhiều hệ thống Prolog có cung cấp vị từ này. Nếu không
có thì chúng ta có thể tự định nghĩa lấy vị từ not.
not(P):- P,!, fail.
not(P).
Lưu ý: not được định nghĩa như là một thất bại, nó không
tương ứng hoàn toàn với trong logic toán.
Ta viết lại 2 thí dụ trên, nó tự nhiên hơn và dễ đọc.
likes(mary,X):- animal(X), not snake(X).
different(X,Y):- not(X = Y).
42
Những vấn đề với cut và not
Tóm tắt về tiện lợi và bất tiện của chương trình như sau:
Với ký hiệu cut, chúng ta có thể cải biến độ hữu hiệu của
chương trình: ta bảo Prolog đừng thử những lựa chọn mà
dẫn đến thất bại.
Dùng cut, ta có thể mô tả được những nguyên tắc loại trừ
lẫn nhau, chúng ta có thể diễn tả những qui tắc có dạng.
If condition P then coclusion Q,
otherwise conclution R.
Một nhược điểm của cut xuất phát từ sự kiện là chúng ta
có thể mất đi mối tương ứng quí báu giữa ý nghĩa khai
báo và ý nghĩa thủ tục của chương trình.
43
Vị từ not, negation của 1 subgoal như là sự thất bại của
subgoal đó.
Vì lý do sáng sủa của CT, chúng ta thích dùng not hơn là tổ hợp cut và
fail.
Khi Prolog thực thi một not(G), Prolog không cố chứng minh not(G)
một cách trực tiếp. Và nó tìm cách chứng minh điều ngược lại. Nếu
điều ngược lại không thể chứng minh được ( = thất bại) thì Prolog giả
định rằng not(G) là đúng.
Lối suy luận như vậy được gọi sự giả định thế giới đóng (close world
assumption).
Một thế giới là đóng theo ý nghĩa rằng mọi cái tồn tại là trong CT, hoặc
dẫn ra từ CT. Do vậy, một cái gì không tồn tại (hoặc không dẫn xuất ra)
từ CT thì nó là sai và phủ định nó là đúng.
Thí dụ: Nếu ta không đưa vào chương trình mệnh đề
human(mary).
Thì ?- human(mary).
no
Bởi vì “không có đủ thông tin trong CT chứng tỏ rằng mary là human”.
44
XUẤT NHẬP
Tương tác với file:
Cho đến bây giờ, tương tác giữa người sử dụng với CT chỉ là người sử
dụng đặt các truy vấn với CT và CT trả lời bằng những sự gán trị cụ thể
vào biến.
Phương cách tương tác này rất hạn chế. Những mở rộng sau đây là cần
thiết :
Nhập dữ liệu ở dạng khác với các truy vấn – thí dụ những câu văn bản.
Xuất dữ liệu khác với khuôn mẫu mong muốn.
Xuất/nhập từ file, chứ không chỉ từ terminal của người sử dụng.
Các vị từ thư viện dùng cho I/O tuỳ thuộc vào từng hệ thống Prolog. Ta
nên tham khảo sách hướng dẫn sử dụng cho hệ thống Prolog để biết
chi tiết về những vị từ đó.
Trong chương này trình bày một số vị từ xuất/nhập cơ bản nhất.
45
Về nguyên tắc, CT có đọc dữ liệu từ nhiều file nhập, cũng được gọi là
dòng nhập (input stream), và xuất dữ liệu ra nhiều file xuất được gọi là
dòng xuất (output stream)
Terminal
Người sử
dụng
Chương trình
Những dòng xuất Những dòng
nhập
File1
File2
File3
File4
user user
Dữ liệu từ terminal của người sử dụng cũng được coi như là một dòng nhập dữ
liệu được xuất ra terminal của người sử dụng cũng được coi như là một dòng
xuất. Cả hai tập tin này được coi như có tên là “user”.
46
Tương tác với file
Tên của các file khác được chọn bởi người lập trình.
Tại mỗi lúc thực thi một chương trình Prolog, chỉ có hai file tham
gia: một cho nhập và một cho xuất. Hai file này được gọi là dòng
nhập hiện hành và dòng xuất hiện hành.
Ban đầu, hai dòng này tương ứng với terminal của người sử dụng.
Ta có thể chuyển dòng nhập hiện hành sang một file khác, filename,
bởi ví dụ:
see(filename)
Một mục tiêu như vậy sẽ khiến việc nhập dữ liệu được chuyển từ
dòng dữ liệu trước đó sang tập tin filename.
Thí dụ:
see(file1),
// nhập liệu từ tập tin file1//
see(user),
.
47
Tương tác với file (tt.)
Dòng dữ liệu xuất được chuyển hướng bằng mục tiêu có
dạng:
tell(Filename)
Thí dụ:
tell(file3),
// xuất dữ liệu ra tập tin file3//
tell(user),
.
Mục tiêu seen đóng file nhập hiện hành.
Mục tiêu told đóng file xuất hiện hành.
48
Xử lý các file toán hạng
Read và write.
Vị từ thư viện read được dùng để đọc các toán hạng trên dòng nhập
hiện hành.
Tiểu mục tiêu
read(X)
sẽ khiến một toán hạng T, được đọc và toán hạng này sẽ đối sánh
với X. Nếu X là một biến thì X được gán giá trị T. Nếu sự đối sánh
không thành công thì tiểu mục tiêu read(X) thất bại.
Vị từ read(X) là tất định, vì khi nó thất bại thì không có
backtracking để lấy vào toán hạng khác.
Nếu read(X) được thực thi mà gặp điểm cuối file, thì X sẽ được gán
trị đặc biệt nguyên tử end-of-file.
49
Vị từ write xuất ra một toán hạng. Như vậy, tiểu mục tiêu write(X) sẽ
xuất toán hạng X tại file xuất hiện hành.
Vị từ write biết cách trình bày mọi toán hạng, bất luận nó phức tạp như
thế nào.
Có những vị từ thư viện giúp việc lập khuôn mẫu khi xuất.
Đó là vị từ
tab(N)
khiến cho N khoảng trống được xuất ra.
Vị từ nl khiến cho bắt đầu một hàng mới.
? – cube.
2.
8
5.
125
12.
1728
stop.
yes
Thí dụ:
cube :- read(X), process(X).
process(stop):- !.
process(N) :- C is N*N*N, write(C), nl,
cube.
50
Cải tiến thủ tục cube:
cube:- write(‘ Next item, please:’),read(X),process(X).
process(stop):- !.
process(N) :- C is N*N*N, write(‘ Cube of’), write(N), write(‘is’),
write( C), nl , cube.
?-cube.
Next item, please: 5.
Cube of 5 is 125
Next item, please :12.
Cube of 12 is 1728
Next item, please: stop.
yes
51
Trình bày list.
writelist([ L ]).
writelist([X | L]):- write(X), nl, writelist(L).
Mỗi phần tử ở trên 1 hàng riêng.
In ra một list của list.
writelist2([])
writelist2([L|LL]):- doline(L), nl , writelist2(LL).
doline([ ])
doline([X|L]):- write(X), write(‘ ’), doline(L).
Sẽ in ra mỗi phần tử trên một hàng.
?- writelist2([[a,b,c]),[d,e,f],[g,h]]).
a b c
d e f
g h
52
Chế biến các ký tự
Một kí tự được đưa ra dòng xuất hiện hành bằng tiểu mục tiêu .
put( C )
với C là mã ASCII của kí tự xuất.
Thí dụ: ?- put(65), put(66), put(67).
sẽ gây ra dòng xuất như sau
ABC
Một ký tự có thể được đọc từ dòng dữ liệu nhập từ tiểu mục tiêu:
get0(C).
Điều này khiến cho một kí tự hiện hành được đọc từ dòng nhập và kí tự
C được gán mã ASCII của kí tự này.
Một biến dạng của vị từ get0 là vị từ get, mà được dùng để đọc những
ký tự khác khoảng trống.
Tiểu mục tiêu get(C) sẽ bỏ qua những ký tự không in được (non-
printable) từ vị trí nhập hiện hành.
53
Thí dụ:
squeeze :- get0(C), put(C) dorest( C ).
dorest( 46 ):- !. % 46 là mã ASCII của dấu chấm.
dorest( 32 ) :- !, get( C ), % 32 là mã ASCII cho khoảng trống
put( C ), dorest(C ).
dorest(letter):- squeeze.
Đọc chương trình: ( consult ):
Để ra lệnh cho Prolog đọc một chương trình từ một file văn bản F (tên
của một file chương trình), ta dùng tiểu mục tiêu :
consult(F).
Hiệu ứng: tất cả các mệnh đề trong F sẽ được đọc và sẽ được dùng bởi
Prolog khi trả lời những câu hỏi sau đó từ người sử dụng.
( F phải là một file văn bản đã được tạo ra)
54
MỘT SỐ VỊ TỪ THƯ VIỆN QUAN TRỌNG
Thử loại toán hạng:
Các vị từ var, nonvar, atom, integer, real, atomic
Toán hạng có thể thuộc nhiều loại
Toán hạng
biến
Số nguyên, số thực
Nguyên tử
Nếu một toán hạng là một biến thì nó có thể được gán trị
(instantiated). Tại một thời điểm thực thi nào đó, hoặc không được
gán trị. Khi được gán trị, thì trị của nó có thể là một nguyên tử, cấu
trúc, v.v Đôi khi rất có ích khi biết loại của trị nào: thí dụ, chúng ta
có thể viết:
Z is X + Y
Nếu chúng ta không chắc rằng X và Y được gán trị ( trước khi được
cộng ) thì chúng ta nên thử, bằng cách dùng hàm thư viện integer
..., integer(X), integer(Y), Z is X + Y, ...
55
Các vị từ thư viện thuộc loại này gồm: var, nonvar, atom,
integer, real, atomic.
var(X) : sẽ thành công khi X là một biến không gán trị
nonvar(X) : sẽ thành công nếu X là một toán hạng khác biến
hoặc X là một biến đã được gán trị
atom(X) : sẽ thành công nếu X là một nguyên tử
integer(X) : sẽ thành công nếu X là một số nguyên
real(X) : sẽ thành công nếu X là một số thư thực
atomic(X) : sẽ thành công nếu X hiện là một số nguyên hoặc là
một nguyên tử.
56
? - Z = 2 , var( Z ).
no
?- integer( Z ), Z = 2. % chöa gaùn trò maø thöû integer( Z )
no
? - Z = 2, integer( Z ), nonvar( Z ).
Z = 2.
?- atom( 22 ).
no
?- atom(==> ).
yes
?- atom( p(1) ).
no
Thí duï 1:
Ta muoán ñeám coù bao nhieâu laàn moät nguyeân töû xuaát hieän trong moät
list ñoái töôïng count( A, L , N ).
count( _, [ ] , O ).
count( A , [ BL ], N ) :- atom( B ), A = B, ! , count( A, L, N1 ),
N is N1 + 1.
count( A , [ _L ] , N ) :- count( A, L, N ) .
57
Cấu tạo và phân rã toán hạng: = .., functor,
arg
Có 3 vị từ thư viện dùng để phân rã toán hạng và cấu tạo toán hạng
mới: functor, arg, và = ..
Xét = .. , được viết như là một toán tử infix.
Tiểu mục tiêu
Term = .. L
là đúng nếu L là một list bao gồm hàm tử chính của tóan hạng Term và
sau đó là các đối số của nó.
Thí dụ:
? – f(a,b) = .. L
L = [f,a,b]
? – T =.. [rectangle, 3,5].
T = rectangle(3,5)
?- Z = .. [p,X,f(X,Y)].
Z = p(X, f(X,Y))
58
Tại sao ta lại cần phân rã toán hạng thành những phần : hàm tử và đôí
số ? và tại sao ta muốn xây dựng 1 toán hạng mới từ một hàm tử và các
toán hạng đã cho ?
Thí dụ:
Bài toán xử lý ký hiệu của công thức: tác vụ thay thế những biểu thức
con nào đó bằng những biểu thức con khác.
Ta định nghĩa quan hệ:
substitute(Subterm, Term, Subterm1, Term1)
Như sau: tất cả những sự xuất hiện của Subterm trong Term được thay
thế bằng Subterm1, và rồi ta sẽ có được Term1.
?- substitute( sin(x), 2*sin(x)*f(sin(x)), t, F).
F = 2*t*f(t)
Sự xuất hiện của Subterm trong Term hiểu theo nghĩa một bộ phận nào
đó trong Term hợp nhất được với Subterm.
?- subtitute( a + b, f(a, A + B),v, F).
sẽ cho ra :
F = f(a,v)
A = a
B = b
59
% sutitute(subterm, term,subterm1,term1):
% if all occurrences of subterm in term subtitute with subterm1
% then rise get term1
% case 1: thay toaùn haïng
subtitute(Term, Term, Term1, Term1):- !.
% case 2: khoâng thay gì caû neáu term laø nguyeân töû hoaëc soá
subtitute( _ , Term, _ , Term) :- atomic(Term),!.
% case 3: thöïc hieän thay theá treân caùc ñoái soá.
subtitute(Sub, Term, Sub1, Term1) :- Term = .. [ F | Args],
substlist( Sub, Args, Sub1, Args1),
Term1 = .. [ F | Args1].
substlist( _ ,[], _ , []).
substlist(Sub,[Term| Terms], Sub1, [Term1, Terms1]):-
subtitute(Sub, Term, Sub1, Term1),
substlist(Sub, Terms, Sub1, Terms1).
60
Vị từ =..
Toán hạng mà được cấu tạo bằng cách dùng vị từ “ = ..”
thì cũng có thể được dùng như những mục tiêu. Tiện lợi
của cách này là khi thực thi CT có thể tạo và thực thi
những mục tiêu dạng thức không thể tiên đoán trước tại
lúc viết CT.
Thí dụ : Đoạn chương trình với 1 chuỗi mục tiêu:
obtain( Functor),
compute(Arglist),
Goal = .. [ Functor| Arglist], Goal.
Ở đây obtain và compute là những vị từ cấu tạo nên
mục tiêu mà cần thực thi. Mục tiêu được tạo ra, rồi sẽ
được gọi ra để thực thi bằng cách nêu tên nó lên, goal
61
Nhiều hệ thống Prolog đòi hỏi một mục tiêu phải được
viết như là một nguyên tử hay là một cấu trúc với một
nguyên tử dùng như là một hàm tử. Một biến, dù thế
nào, cũng không được chấp nhận về mặt ngữ pháp như
là một mục tiêu.
Vấn đề này có thể được khắc phục bằng một vị từ thư
viện, call, mà đối số của nó là một tiểu mục tiêu cần thực
thi.
.........
Goal = ..[ Functor| Arglist], call(Goal).
Đôi khi ta cần trích ra từ một toán hạng chỉ hàm tử chính
của nó hoặc là một trong những đối số của nó.
62
Các vị từ functor và arg
functor( Term, F, N)
traû veà trò ñuùng neáu F laø haøm töû chính cuûa Term vaø N laø soá ñoái soá cuûa
Term.
arg(N, Term,A)
laø ñuùng neáu A laø ñoái soá thöù N cuûa Term.
Thí duï:
?- functor(t(f(X),X,t),Fun,Arity).
Fun = t
Arity = 3
?- arg(2,f(X,t(a),t(b)),Y).
Y = t(a)
?- functor(D,date,3), arg(1,D,29), arg(2,D,june), arg(3,D,1982).
D = date(29, june, 1982)
63
Các loại đẳng thức khác nhau
Có 3 loại đẳng thức khác nhau.
Loại thứ nhất dựa trên sự đối sánh:
X = Y trả về trị đúng nếu X và Y hợp nhất được
Loại thứ nhất khác được viết là:
X is E trả về trị đúng nếu X đối sánh được với trị của biểu thức số học E
Loại thứ hai để so sánh 2 biểu thức số học:
E1 =:= E2 trả về trị đúng nếu hai trị của hai biểu thức số học bằng nhau.
E1=\= E2 trả về trị đúng nếu hai trị của hai biểu thức số học tại E1, E2 là
khác nhau.
Loại thứ 3 ( một loại đẳng thức khó tính hơn)
T1 = = T2 trả về trị đúng nếu hai toán hạng T1, T2 giống hệt nhau (chúng
có cùng cấu trúc và tất cả các thành phần giống hệt nhau)
T1 \ = = T2 T1, T2 không giống hệt nhau
64
Thí dụ: ?- f( a,b) = = f(a,b).
yes
?- f(a,b) = = f(a,X).
no
?- t(X,f(a,X)) = = t(X,f(a,X)).
yes
Thí dụ: Đếm số lần suất hiện của một toán hạng trong một list.
count( _ , [], 0).
count(Term,[Head| Tail], N):- Term = = Head,!,
count(Term, Tail, N1), N is N1 +1.
count(Term, [ _ | Tail], N):- count(Term, Tail, N).
65
Các phương tiện điều khiển
Chúng ta đã điểm qua tất cả các phương tiện điều khiển trừ repeat.
+ cut: ngăn cản backtracking.
+ fail : mục tiêu mà luôn luôn thất bại.
+ true : mục tiêu mà luôn luôn thành công
+ not(P): một dạng của phủ định mà có nghĩa
not(P) : - P,!, fail.
not(P).
+ call(P): gọi mục tiêu P, nó thành công nếu P thành công.
+ repeat: là một mục tiêu luôn luôn thành công. Đặc tính đặc biệt của
nó là không tất định; do đó mỗi lần nó được đạt tới do quay lui, nó sinh
ra một nhánh thực thi khác. repeat làm việc như là:
repeat.
repeat :- repeat.
66
repeat
Thí dụ:
dosquares:-
repeat,
read(X), dowrite(X).
dowrite(X):- X = stop,!.
dowrite(X):-
Y is X*X, write(Y), nl, fail.
Thủ tục trên đọc vào một chuỗi con số và xuất ra những bình phương
của chúng. Chuỗi thực hiện này kết thúc với nguyên tử stop. Loại vòng
lặp này được gọi là failure-driven-loop.
67
Vị từ bagof and findall
Chúng ta có thể sinh ra, nhờ backtracking, tất cả những đối tượng, từng đối
tượng một thỏa mãn được mục tiêu nào đó. Mỗi lần một lời giải mới được tạo
ra, lời giải cũ đã biến mất và không còn có thể truy đạt đến.
Tuy nhiên, đôi khi ta cần gom tất cả các lời giải lại, thí dụ, thành một list.
Vị từ thư viện bagof và findall phục vụ cho mục đích này.
Vị từ bagof(X,P,L) sinh ra một list L các đối tượng X thỏa mãn quan hệ P.
Điều này có nghĩa chỉ khi X và P có những biến chung.
Ví dụ: Ta có các sự kiện
age(peter,7).
age(ann,5).
age(pat,8).
age(tom,5).
Để có một danh sách tất cả những đứa trẻ 5 tuổi, ta dùng truy vấn:
?- bagof( Child, age(Child, 5), List).
List = [ann, tom]
68
Nếu ta để tuổi là biến chưa gán trị, ta sẽ được, thông qua sự quay lui, ba danh
sách, tuỳ theo ba độ tuổi của trẻ.
?- bagof( Child, age(Child, Age), List).
Age = 7
List = [peter];
Age = 5
List = [ann, tom];
Age = 8
List = [pat]
No
Một vị từ tương tự như bagof là vị từ findall.
Vị từ findall(X, P,L) sinh ra một list L các đối tượng X thỏa mãn quan hệ P.
Điểm khác biệt của findall với bagof là tất cả các đối tượng X được thu gom
bất kể những lời giải khác nhau cho các biến trong P mà khác với X.
Thí dụ:
?- findall( Child,age(Child, Age), List).
List = [peter, ann, pat, tom]
Các file đính kèm theo tài liệu này:
- prolog_techniques_9551_1810934.pdf