Giáo trình Lập trình logic trong Prolog (Phần 2)

95 
CHƯƠNG 4 
Cấu trúc danh sách 
Chương này trình bày khái niệm về danh sách, một trong những cấu trúc đơn 
giản nhất và thông dụng nhất, cùng với những chương trình tiêu biểu minh hoạ 
cách vận dụng danh sách trong Prolog. Cấu trúc danh sách tạo nên một môi 
trường lập trình thuận tiện của ngôn ngữ Prolog. 
I. Biểu diễn cấu trúc danh sách 
Danh sách là kiểu cấu trúc dữ liệu được sử dụng rộng rãi trong các ngôn ngữ 
lập trình phi số. Một danh sách là một dãy bất kỳ các đối tượng. Khác với kiểu dữ 
liệu tập hợp, các đối tượng của danh sách có thể trùng nhau (xuất hiện nhiều lần) 
và mỗi vị trí xuất hiện của đối tượng đều có ý nghĩa. 
Danh sách là cách diễn đạt ngắn gọn của kiểu dữ liệu hạng phức hợp trong 
Prolog. Hàm tử của danh sách là dấu chấm “.”. Do việc biểu diễn danh sách bởi 
hàm tử này có thể tạo ra những biểu thức mập mờ, nhất là khi xử lý các danh 
sách gồm nhiều phần tử lồng nhau, cho nên Prolog quy ước đặt dãy các phần tử 
của danh sách giữa các cặp móc vuông. 
Chẳng hạn .(a,.(b,[ ])). Là danh sách [ a, b ]. 
Danh sách các phần tử anne, tennis, tom, skier (tên người) được viết : 
[ anne, tennis, tom, skier ] 
chính là hàm tử : 
. ( anne, .( tennis, .( tom, .( skier, [ ] ) ) ) ) 
Cách viết dạng cặp móc vuông chỉ là xuất hiện bên ngoài của một danh sách. 
Như đã thấy ở mục trước, mọi đối tượng cấu trúc của Prolog đều có biểu diễn 
cây. Danh sách cũng không nằm ngoại lệ, cũng có cấu trúc cây. 
Làm cách nào để biểu diễn danh sách bởi một đối tượng Prolog chuẩn ? Có 
hai khả năng xảy ra là danh sách có thể rỗng hoặc không. Nếu danh sách rỗng, nó 
được viết dưới dạng một nguyên tử : 
[ ] 
Lập trình lôgic trong Prolog 96 
Nếu danh sách khác rỗng, có thể xem nó được cấu trúc từ hai thành phần (pair 
syntax) : 
1. Thành phần thứ nhất, được gọi là đầu (head) của danh sách. 
2. Thành phần thứ hai, phần còn lại của danh sách (trừ ra phần đầu), được 
gọi là đuôi (tail) của danh sách, cũng là một danh sách. 
Trong ví dụ trên thì đầu là anne, còn đuôi là danh sách : 
[ tennis, tom, skier ] 
Nói chung, đầu của danh sách có thể là một đối tượng bất kỳ của Prolog, có 
thể là cây hoặc biến, nhưng đuôi phải là một danh sách. Hình I.1. Biểu diễn dạng 
cây của danh sách mô tả cấu trúc cây của danh sách đã cho : 
Hình I.1. Biểu diễn dạng cây của danh sách 
Vì đuôi tail là một danh sách, nên tail có thể rỗng, hoặc lại có thể được 
tạo thành từ một đầu head và một đuôi tail khác. 
Chú ý rằng danh sách rỗng xuất hiện trong số các hạng, vì rằng phần tử cuối 
cùng có thể xem là danh sách chỉ gồm một phần tử duy nhất có phần đuôi là một 
danh sách rỗng: 
[ skier ] 
Ví dụ trên đây minh hoạ nguyên lý cấu trúc dữ liệu tổng quát trong Prolog áp 
dụng cho các danh sách có độ dài tuỳ ý. 
?- L1 = [ a, b, c ]. 
?- L2 = [ a, a, a ]. 
L1 = [ a, b, c ] 
L2 = [ a, a, a ] 
?- Leisure1 = [ tennis, music, [ ] ]. 
?- Leisure2 = [ sky, eating ], 
?- L = [ anne, Leisure1, tom, Leisure2 ]. 
Leisure1 = [ tennis, music ] 
Leisure2 = [ sky, eating ] 
L = [ anne, [ tennis, music ], tom, [ sky, eating ] ] 
. 
anne . đuôi cũng là danh sách 
đầu tennis . 
tom . 
skier [ ] 
Cấu trúc danh sách 97 
Như vậy, các phần tử của một danh sách có thể là các đối tượng có kiểu bất 
kỳ, kể cả kiểu danh sách. Thông thường, người ta xử lý đuôi của danh sách như 
là một danh sách. Chẳng hạn, danh sách : 
L = [ a, b, c ] 
có thể viết : 
tail = [ b, c ] và L = .(a, tail) 
Để biểu diễn một danh sách được tạo thành từ đầu (Head) và đuôi (Tail), 
Prolog sử dụng ký hiệu | (split) để phân cách phần đầu và phần đuôi như sau : 
L = [ a | Tail ] 
Ký hiệu | được dùng một cách rất tổng quát bằng cách viết một số phần tử tuỳ 
ý của danh sách trước | rồi danh sách các phần tử còn lại. Danh sách bây giờ 
được viết lại như sau : 
 [ a, b, c ] = [ a | [ b, c ] ] = [ a, b | [ c ] ] = [ 
a, b, c | [ ] ] 
Sau đây là một số cách viết danh sách : 
Kiểu hai thành phần Kiểu liệt kê phần tử 
[ ] [ ] 
[ a | [ ] ] [ a ] 
[ a | b | [ ] ] [ a, b ] 
[ a | X ] [ a | X ] 
[ a | b | X ] [ a, b | X ] 
[ X1 | [ ... [ Xn | [ ] ]... ] ] [ X1, ... , Xn ] 
Ta có thể định nghĩa danh sáchtheo kiểu đệ quy như sau : 
List 
 [ ] 
List 
 [ Element | List ] 
II. Một số vị từ xử lý danh sách của Prolog 
SWI-Prolog có sẵn một số vị từ xử lý danh sách như sau : 
Vị từ Ý nghĩa 
append(List1, List2, 
List3) 
Ghép hai danh sách List1 và List2 thành List3. 
member(Elem, List) 
Kiểm tra Elem có là phần tử của danh sách List hay 
không, nghĩa là Elem hợp nhất được với một trong các 
phần tử của List. 
nextto(X, Y, List) Kiểm tra nếu phần tử Y có đứng ngay sau phần tử X 
trong danh sách List hay không. 
Lập trình lôgic trong Prolog 98 
delete(List1, Elem, 
List2) 
Xoá khỏi danh sách List1 những phần tử hợp nhất 
được với Elem để trả về kết quả List2. 
select(Elem, List, 
Rest) 
Lấy phần tử Elem ra khỏi danh sách List để trả về 
những phần tử còn lại trong Rest, có thể dùng để chèn 
một phần tử vào danh sách. 
nth0(Index, List, 
Elem) 
Kiểm tra phần tử thứ Index (tính từ 0) của danh sách 
List có phải là Elem hay không. 
nth1(Index, List, 
Elem) 
Kiểm tra phần tử thứ Index (tính từ 1) của danh sách 
List có phải là Elem hay không. 
last(List, Elem) Kiểm tra phần tử đứng cuối cùng trong danh sách 
List có phải là Elem hay không. 
reverse(List1, 
List2) 
Nghịch đảo thứ tự các phần tử của danh sách List1 để 
trả về kết quả List2. 
permutation(List1, 
List2) 
Hoán vị danh sách List1 thành danh sách List2. 
flatten(List1, 
List2) 
Chuyển danh sách List1 chứa các phần tử bất kỳ 
thành danh sách phẳng List2. 
Ví dụ : flatten([a, [b, [c, d], e]], X). 
cho kết quả X = [a, b, c, d, e]. 
sumlist(List, Sum) 
Tính tổng các phần tử của danh sách List chứa toàn 
số để trả về kết quả Sum. 
numlist(Low, High, 
List) 
Nếu Low và High là các số sao cho Low =< High, thì 
trả về danh sách List = [Low, Low+1, ..., 
High]. 
Chú ý một số vị từ xử lý danh sách có thể sử dụng cho mọi ràng buộc, kể cả 
khi các tham đối đều là biến. 
Trong Prolog, tập hợp được biểu diễn bởi danh sách, tuy nhiên, thứ tự các 
phần tử trong một tập hợp là không quan trọng, các đối tượng dù xuất hiện nhiều 
lần chỉ được xem là một phần tử của tập hợp. Các phép toán về danh sách có thể 
áp dụng cho các tập hợp. Đó là : 
• Kiểm tra một phần tử có mặt trong một danh sách tương tự việc kiểm tra một 
phần tử có thuộc về một tập hợp không ? 
• Ghép hai danh sách để nhận được một danh sách thứ ba tương ứng với phép 
hợp của hai tập hợp. 
• Thêm một phần tử mới, hay loại bỏ một phần tử. 
Cấu trúc danh sách 99 
Prolog có sẵn một số vị từ xử lý tập hợp như sau : 
Vị từ Ý nghĩa 
is_set(Set) Kiểm tra Set có phải là một tập hợp hay không 
list_to_set(List, Set) 
Chuyển danh sách List thành tập hợp Set giữ 
nguyên thứ tự các phần tử của List (nếu List có các 
phần tử trùng nhau thì chỉ lấy phần tử gặp đầu tiên). 
Ví dụ : list_to_set([a,b,a], X) cho kết quả 
X = [a,b]. 
intersection(Set1, 
Set2, Set3) 
Phép giao của hai tập hợp Set1 và Set2 là Set3. 
subtract(Set, Delete, 
Result) 
Trả về kết quả phép hiệu của hai tập hợp Set và 
Delete là Result (là tập Set sau khi đã xoá hết các 
phần tử của Delete có mặt trong đó). 
union(Set1, Set2, Set3) Trả về kết quả phép hợp của hai tập hợp Set1 và 
Set2 là Set3. 
subset(Subset, Set) Kiểm tra tập hợp Subset có là tập hợp con của Set hay không. 
III. Các thao tác cơ bản trên danh sách 
III.1. Xây dựng lại một số vị từ có sẵn 
Sau đây ta sẽ trình bày một số thao tác cơ bản trên danh sách bằng cách xây 
dựng lại một số vị từ có sẵn của Prolog. 
III.1.1. Kiểm tra một phần tử có mặt trong danh sách 
Prolog kiểm tra một phần tử có mặt trong một danh sách như sau : 
member(X, L) 
trong đó, X là một phần tử và L là một danh sách. Đích member(X, L) được 
thoả mãn nếu X xuất hiện trong L. Ví dụ : 
?- member( b, [ a, b, c ] ) 
Yes 
?- member( b, [ a, [ b, c ] ] ) 
No 
?- member( [ b, c], [ a, [ b, c ] ] ) 
Yes 
Từ các kết quả trên, ta có thể giải thích quan hệ member(X, L) như sau : 
Lập trình lôgic trong Prolog 100 
Phần tử X thuộc danh sách L nếu : 
1. X là đầu của L, hoặc nếu 
2. X là một phần tử của đuôi của L. 
Ta có thể viết hai điều kiện trên thành hai mệnh đề, mệnh đề thứ nhất là một 
sự kiện đơn giản, mệnh đề thứ hai là một luật : 
member( X, [ X | Tail ] ). 
member( X, [ Head | Tail ] ) :- member( X, Tail ). 
hoặc : 
member(X, [X|T]). 
member(X, [_|T]) :- member(X, T). 
III.1.2. Ghép hai danh sách 
Để ghép hai danh sách, Prolog có hàm : 
append( L1, L2, L3). 
trong đó, L1 và L2 là hai danh sách, L3 là danh sách kết quả của phép ghép L1 
và L2. Ví dụ : 
?- append( [ a, b ], [ c, d ], [ a, b, c, d ] ). 
Yes 
?- append( [ a, b ], [ c, d ], [ a, b, a, c ] ). 
No 
Hình III.1. Ghép hai danh sách [ X | L1 ] và L2 thành [ X | L3 ]. 
Hàm append hoạt động phụ thuộc tham đối đầu tiên L1 theo cách như sau : 
1. Nếu tham đối đầu tiên là danh sách rỗng, thì tham đối thứ hai và thứ ba phải 
là một danh sách duy nhất, gọi là L. Ta viết trong Prolog như sau : 
append( [ ], L, L). 
2. Nếu tham đối đầu tiên của append là danh sách khác rỗng, thì nó gồm 
một đầu và một đuôi như sau 
[ X | L1 ] 
X L3 
X L1 L2 
[ X | L1 ] 
L3 
[ X | L3 ] 
Cấu trúc danh sách 101 
Kết quả phép ghép danh sách là danh sách [ X | L3 ], với L3 là phép 
ghép của L1 và L2. Ta viết trong Prolog như sau : 
append( [ X | L1 ], L2, [ X | L3 ] ) :- append( L1, 
L2, L3 ). 
Hình 4.2 minh hoạ phép ghép hai danh sách [ X | L1 ] và L2. 
Ta có các ví dụ sau : 
?- append( [ a, b, c ], [ 1, 2, 3 ], L ). 
L = [ a, b, c, 1, 2, 3 ] 
?- append( [ a, [ b, c ], d ], [ a, [ ], b ], L ] ). 
L = [ a, [ b, c ], d, a, [ ], b ] 
Thủ tục append được sử dụng rất mềm dẻo theo nhiều cách khác nhau. 
Chẳng hạn Prolog đưa ra bốn phương án để phân tách một danh sách đã cho 
thành hai danh sách mới như sau : 
?- append( 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 = [ ]; 
Yes 
Sử dụng append, ta cũng có thể tìm kiếm một số phần tử trong một danh 
sách. Chẳng hạn, từ danh sách các tháng trong năm, ta có thể tìm những tháng 
đứng trước một tháng đã cho, giả sử tháng năm (May) : 
?- append( Before, [ May | After ] , 
[ jan, fev, mar, avr, may, jun, jul, aut, sep, oct, 
nov, dec ] ). 
Before = [ jan, fev, mar, avr ] 
After = [ jun, jul, aut, sep, oct, nov, dec ] 
Yes 
Tháng đứng ngay trước và tháng đứng ngay sau tháng năm nhận được như sau : 
?- append( _, [ Month1, may, Month2 | _ ] , 
[ jan, fev, mar, avr, may, jun, jul, aut, sep, oct, 
nov, dec ] ). 
Lập trình lôgic trong Prolog 102 
Month1 = avr 
Month2 = jun 
Yes 
Bây giờ cho trước danh sách : 
L1 = [ a, b, z, z, c, z, z, z, d, e ] 
Ta cần xóa các phần tử đứng sau ba chữ z liên tiếp, kể cả ba chữ z : 
?- L1 = [ a, b, z, z, c, z, z, z, d, e ], 
append( L2, [ z, z, z | _ ], L1 ). 
L1 = [ a, b, z, z, c, z, z, z, d, e ] 
L2 = [ a, b, z, z, c ] 
Hình III.2. Thủ tục member1 tìm tuần tự một đối tượng trong danh sách đã cho. 
Trước đây ta đã định nghĩa quan hệ member( X, L ) để kiểm tra một phần 
tử X có mặt trong một danh sách L không. Bây giờ bằng cách sử dụng append, ta 
có thể định nghĩa lại member như sau : 
member1( X, L ) :- append( L1, [ X | L2], L). 
member1( b, [ a, b, c ] 
) 
Mệnh đề 2 của append 
So khớp : 
L1 = [ X | L1’ ] 
[ b | L2 ] = L2’ 
[ a, b, c ] = [ X | L3’ ] 
Từ đó kéo theo : 
 X = a, L3’ = [ b, c ] 
Mệnh đề 1 của append 
So khớp : 
L1’ = [ ] 
[ b | L2 ] = [ b, c ] 
Từ đó kéo theo : 
L2 = [ c ] 
thành công 
Mệnh đề 1 của append 
So khớp : 
L1 = [ ] 
[ b | L2 ] = [ a, b, c ] 
Thất bại vì b ≠ a 
append( L1, [ b | L2 ], [ a, b, c ] 
) 
append( L1’, [ b | L2 ], [ b, c ] ) 
Cấu trúc danh sách 103 
Mệnh đề này có nghĩa : nếu X có mặt trong danh sách L thì L có thể được 
phân tách thành hai danh sách, với X là đầu của danh sách thứ hai. Định nghĩa 
member1 hoàn toàn tương đương với định nghĩa member. 
Ở đây ta sử dụng hai tên khác nhau để phân biệt hai cách cài đặt Prolog. Ta 
cũng có thể định nghĩa lại member1 bằng cách sử dụng biến nặc danh 
(anonymous variable) : 
member1( X, L ) :- 
append( _ , [ X | _ ], L). 
So sánh hai cách cài đặt khác nhau về quan hệ thành viên, ta nhận thấy nghĩa 
thủ tục trong định nghĩa member được thể hiện rất rõ : 
Trong member, để kiểm tra phần tử X có mặt trong một danh sách L không, 
1. Trước tiên kiểm tra phần tử đầu của L là đồng nhất với X, nếu không, 
2. Kiểm tra rằng X có mặt trong phần đuôi của L. 
Nhưng trong trường hợp định nghĩa member1, ta thấy hoàn toàn nghĩa khai 
báo mà không có nghĩa thủ tục. 
Để hiểu được cách member1hoạt động như thế nào, ta hãy xem xét quá trình 
Prolog thực hiện câu hỏi : 
?- member1( b, [ a, b, c ] ). 
Cách tìm của thủ tục member1 trên đây tương tự member, bằng cách duyệt 
từng phần tử, cho đến khi tìm thấy đối tượng cần tìm, hoặc danh sách đã cạn. 
III.1.3. Bổ sung một phần tử vào danh sách 
Phương pháp đơn giản nhất để bổ sung một phần tử vào danh sách là đặt nó ở 
vị trí đầu tiên, để nó trở thành đầu. Nếu X là một đối tượng mới, còn L là danh 
sách cần bổ sung thêm, thì danh sách kết quả sẽ là : 
[ X | L ] 
Người ta không cần viết thủ tục để bổ sung một phần tử vào danh sách. Bởi vì 
việc bổ sung có thể được biểu diễn dưới dạng một sự kiện nếu cần : 
insert( X, L, [ X | L ] ). 
III.1.4. Loại bỏ một phần tử khỏi danh sách 
Để loại bỏ một phần tử X khỏi danh sách L, người ta xây dựng quan hệ : 
remove( X, L, L1 ) 
trong đó, L1 đồng nhất với L, sau khi X bị loại bỏ khỏi L. Thủ tục remove có 
cấu trúc tương tự member. Ta có thể lập luận như sau 
1. Nếu phần tử X là đầu của danh sách, thì kết quả là đuôi của danh sách. 
Lập trình lôgic trong Prolog 104 
2. Nếu không, tìm cách loại bỏ X khỏi phần đuôi của danh sách. 
remove( X, [ X | Tail ], Tail ). 
remove( X, [ Y | Tail ], [ Y | Tail1 ] ) :- 
remove( X, Tail, Tail1 ). 
Tương tự thủ tục member, thủ tục remove mang tính không xác định. Nếu có 
nhiều phần tử là X có mặt trong danh sách, thì remove có thể xoá bất kỳ phần tử 
nào, do quá trình quay lui. Tuy nhiên, mỗi lần thực hiện, remove chỉ xoá một 
phần tử là X mà không đụng đến những phần tử khác. Ví dụ : 
?- remove( a, [ a, b, a, a ], L ). 
L = [ b, a, a ]; 
L = [ a, b, a ]; 
L = [ a, b, a ] 
No 
Thủ tục remove thất bại nếu danh sách không chứa phần tử cần xoá. Người 
ta có thể sử dụng remove trong một khía cạnh khác, mục đích để bổ sung một 
phần tử mới vào bất cứ đâu trong danh sách. 
Ví dụ, nếu ta muốn đặt phần tử a vào tại mọi vị trí bất kỳ trong danh sách [ 
1, 2, 3 ], chỉ cần đặt câu hỏi : Cho biết danh sách L nếu sau khi xoá a, ta 
nhận được danh sách [ 1, 2, 3 ] ? 
?- remove( a, L, [ 1, 2, 3 ] ). 
L = [ a, 1, 2, 3 ]; 
L = [ 1, a, 2, 3 ]; 
L = [ 1, 2, a, 3 ]; 
L = [ 1, 2, 3, a ] 
No 
Một cách tổng quát, phép toán chèn insert một phần tử X vào một danh 
sách List được định nghĩa bởi thủ tục remove bằng cách sử dụng một danh 
sách lớn hơn LargerList làm tham đối thứ hai : 
insert( X, List, LargerList ) :- 
remove( X, LargerList, List ). 
Ta đã ... 'f2.txt'), see('f1.txt'), copie, seen, told. 
Yes 
Trong thủ tục copie có sử dụng vị từ repeat. Vị từ repeat luôn luôn 
thành công, tạo ra một vòng lặp vô hạn. Vị từ repeat được định nghĩa như sau : 
repeat. 
repeat :- repeat. 
III.3.3. Thao tác trên các ký tự 
Một số vị từ xử lý ký tự của Prolog như sau : 
Tên vị từ Ý nghĩa 
put(Char) Đưa Char ra dòng ra hiện hành, Char hoặc là một giá 
trị nguyên trong khoảng 0..255, hoặc một ký tự 
put(File, Char) Đưa Char ra tệp File 
get_char(Char) Đọc từ tệp File và hợp nhất Char với ký tự tiếp theo. 
get_char(File, 
Char) Hợp nhất Char với ký tự tiếp theo trong tệp File. 
get0(Char) Đọc ký tự tiếp theo 
get0(File, 
Char) Đọc ký tự tiếp theo trong tệp File. 
get(-Char) Đọc ký tự khác khoảng trống từ dòng vào và hợp nhất 
với Char. 
get(File, Char) Đọc ký tự khác khoảng trống tiếp theo trong tệp File. 
skip(Char) Đọc vào và bỏ qua các ký tự đọc được cho đến khi gặp 
đúng ký tự khớp được với Char. 
Kỹ thuật lập trình Prolog 171 
skip(File, 
Char) 
Đọc vào từ tệp File và bỏ qua các ký tự đọc được cho 
đến khi gặp đúng ký tự khớp được với Char. 
Ví dụ III.11 : 
% Đưa ra liên tiếp các ký tự A, B và C có mã ASCII lần lượt là 65, 66, 67 
?- put( 65), put( 66), put( 67). 
ABC 
yes 
% Đọc và ghi các ký tự 
?- get0(X). 
|: a % Gõ vào một ký tự rồi Enter (↵), không gõ dấu chấm 
X = 97 
Yes. 
?- get0(X). 
^D 
X = -1. 
Yes. 
Ví dụ III.12 : 
Sau đây ta xây dựng thủ tục del_space đọc vào một câu gồm nhiều từ cách 
nhau bởi các khoảng trống và trả về đúng câu đó sau khi đã loại bỏ các khoảng 
trống thừa, chỉ giữ lại một khoảng trống giữa các từ mà thôi. 
Thủ tục hoạt động tương tự các thủ tục xử lý tệp, bằng cách đọc lần lượt từng 
ký tự rồi đưa ra màn hình. Thủ tục sử dụng kỹ thuật nhát cắt để xử lý tình huống 
ký tự đọc vào hoặc là một khoảng trống, hoặc là một chữ cái, hoặc là một dấu 
chấm kết thúc. Sau đây là thủ tục del_space : 
del_space :- 
get0( C), 
put( C), 
follow( C). 
follow( 46) :- !. % 46 là mã ASCII của dấu chấm 
follow( 32) :- !, % 32 là mã ASCII của dấu khoảng 
trống 
get( C), % Bỏ qua các dấu khoảng trống tiếp theo 
put( C), 
follow( C). 
follow( Letter) :- 
del_space. 
Chạy thử như sau : 
?- del_space. 
|: The robot try to cast the balls 
to the basket. 
172 Lập trình lägich trong Prolog 
The robot try to cast the balls to the basket. 
Yes 
III.3.4. Thao tác trên các nguyên tử 
Prolog có vị từ name/2 cho phép đặt tương ứng các nguyên tử với các mã 
ASCII : 
name( A, L) 
Vị từ thoả mãn khi L là danh sách các của các ký tự của A. Ví dụ : 
?- name(mic29, [109, 105, 99, 50, 57 ]). 
Yes 
?- name( aikieutuido, L). 
L = [ 97, 105, 107, 105, 101, 117, 116, 117, 105 |... ] 
Yes 
?- name(X, [ 97, 105, 107, 105, 101, 117, 116, 117, 105, 
100, 111 ]). 
X = aikieutuido 
Yes 
Hai chức năng chính của vị từ name như sau : 
1. Chuyển một nguyên tử thành một danh sách các ký tự (mã ASCII). 
2. Tạo một nguyên tử từ một danh sách các ký tự. 
Ví dụ III.13 : 
Xây dựng thủ tục quản lý các cuộc gọi dịch vụ xe taxi chở hành khách nhờ 
các nguyên tử sau : 
Tên các cuộc gọi call1, call2, ... 
Tên các lái xe chauffeur1, chauffeur2, ... 
Tên các xe taxi taxi1, taxi2, ... 
Vị từ taxi( X ) kiểm tra một nguyên tử có biểu diễn đúng một taxi theo 
cách biểu diễn như trên không : 
taxi( T ) :- 
name( T, Tlist), 
name( taxi, L), 
append( L, _ , Tlist). 
Một cách tương tự, ta có thể xây dựng các vị từ chauffer và taxi. 
Ví dụ III.14 : 
Sau đây ta xây dựng thủ tục cho phép tạo ra một nguyên tử bằng cách tổ hợp 
các ký tự. Thủ tục readsentence( Wordlist) sẽ đọc một câu thuộc ngôn 
ngữ tự nhiên rồi gán cho Wordlist danh sách các giá trị mã biểu diễn trong của 
Kỹ thuật lập trình Prolog 173 
các ký tự trong câu. Tiếp theo, mỗi câu được xem là một danh sách các từ, mỗi từ 
được chuyển thành một nguyên tử. 
readsentence( WordList) :- 
get0( Char), 
readchain( Char, WordList). 
readchain( 46,[ ] ) :- !. % dấu chấm kết thúc câu 
readchain( 32, WordList) :- 
readsentence(WordList). % Bỏ qua các dấu khoảng trống 
readchain( L, [ W | WordList ] ) :- 
readletter( L, Letters, Nextchar ), % Đọc các ký tự của 
từ tiếp theo 
name( W, Letters), 
readchain( Nextchar, WordList). 
readletter( 46, [ ], 46) :- !. % kết thúc từ là một dấu chấm 
readletter( 32, [ ], 32) :- !. % kết thúc từ là một dấu khoảng 
trống 
readletter( C, [ C | Letters] , Nextchar) :- 
get0( Char), 
readletter( Char, Letters, Nextchar). 
Chạy chương trình, ta có các kết quả như sau : 
?- readsentence( WordList). 
|: The robot ASIMO try to cast the balls to the basket. 
WordList = ['The', robot, 'ASIMO', try, to, cast, the, 
balls, to|...] 
Yes 
?- readsentence( WordList). 
|: " Ai đi trăm suối ngàn rừng " % dấu Enter ↵ sau dấu nháy kép 
|: . % dấu chấm kết thúc câu 
WordList = [ '" Ai', đi, trăm, suối, ngàn, 'rừng "\n' ] 
Yes 
Trong thủ tục, ta đã giả thiết rằng kết thúc câu vào là một dấu chấm và nếu có 
dấu chấm câu trong câu, thì tuỳ theo cách xuất hiện mà nó được xem như là một 
từ hoặc dính vào với từ. 
Thủ tục đọc ký tự đầu tiên là Char, rồi chuyển cho thủ tục readchain. 
Thủ tục readchain xử lý 3 trường hợp như sau : 
(1) Nếu Char là một dấu chấm, thì quá trình đọc câu vào kết thúc. 
(2) Nếu Char là một khoảng trống, áp dụng thủ tục readsentence cho 
phần còn lại của câu. 
174 Lập trình lägich trong Prolog 
(3) Nếu Char là một ký tự : trước tiên đọc từ W được bắt đầu bởi ký tự Char, 
sau đó sử dụng readsentence để đọc phần còn lại của câu và tạo ra 
danh sách WordList. Kết quả được tích luỹ trong [ W | WordList ]. 
Thủ tục readletter( L, Letters, Nextchar ) đọc các ký tự của một 
từ, trong đó : 
(1) L là chữ cái hiện hành (đã được đọc) của từ đang đọc. 
(2) Letters là danh sách các chữ cái, bắt đầu bởi L cho đến hết từ. 
(3) Nextchar là ký tự theo sau từ đang đọc, có thể không phải là một chữ 
cái. 
Nhờ cách biểu diễn các từ của câu trong một danh sách, người ta có thể sử 
dụng Prolog để xử lý ngôn ngữ tự nhiên, như tìm hiểu nghĩa của câu theo một 
quy ước nào đó, v.v.. thuộc lĩnh vực trí tuệ nhân tạo. 
III.3.5. Một số vị từ xử lý cơ sở dữ liệu 
Sau đây là một số vị từ chuẩn cho phép xử lý trên các luật và sự kiện của một 
cơ sở dữ liệu Prolog. 
assert(P) 
Thêm P vào cơ sở dữ liệu. Ví dụ cho cơ sở dữ liệu lúc ban đầu : 
personal(tom). 
personal(ann). 
Sau khi thực hiện đích : 
?- assert(personal(bob)). 
cơ sở dữ liệu lúc này trở thành : 
personal(tom). 
personal(ann). 
personal(bob). 
Do NSD không biết assert đã thêm P vào đầu hay cuối của cơ sở dữ liệu, 
Prolog cho phép sử dụng hai dạng khác là : 
asserta(P) Thêm P vào đầu cơ sở dữ liệu. 
assertz(P) Thêm P vào cuối cơ sở dữ liệu. 
Sử dụng vị từ : 
assert((P :- B, C, D)). 
có thể làm thay đổi nội dung một mệnh đề trong chương trình. Tuy nhiên, người 
ta khuyên không nên sử dụng lệnh này. 
retract(P) 
Kỹ thuật lập trình Prolog 175 
Loại bỏ P khỏi cơ sở dữ liệu. Ví dụ cho cơ sở dữ liệu lúc ban đầu : 
personal(tom). 
personal(ann). 
personal(bob). 
Sau khi thực hiện đích : 
?- retract(personal(ann)). 
cơ sở dữ liệu lúc này chỉ còn : 
personal(tom). 
personal(bob). 
Có thể sử dụng biến trong retract như sau : 
?- retract(personal(X)). 
X = tom ; 
X = bob ; 
No 
Lúc này cơ sở dữ liệu đã rỗng. 
abolish(Term, Arity) 
Loại bỏ tất cả các hạng Term có cấp Arity khỏi cơ sở dữ liệu. Ví dụ : 
?- abolish(personal, 2). 
Loại bỏ tất cả các hạng Term có cấp Arity=2. 
Ví dụ III.15 
Xây dựng bộ siêu diễn dịch Prolog trong Prolog, việc xoá một đích được viết 
lại như sau : 
prove(Goal) :- call(Goal). 
hoặc : 
prove(Goal) :- Goal. 
hoặc viết các mệnh đề : 
prove(true). 
prove((Goal1, Goal2)) :- 
prove(Goal1), 
prove(Goal2). 
prove(Goal) :- 
clause(Goal, Body), 
prove(Body). 
176 Lập trình lägich trong Prolog 
Tóm tắt chương 5 : 
Kỹ thuật nhát cắt và phủ định 
• Nhát cắt ngăn cản sự quay lui, không những làm tặng hiệu quả chạy 
chương trình mà còn làm tối ưu tính biểu hiện của ngôn ngữ. 
• Để tặng hiệu quả chạy chương trình, người lập trình sử dụng nhát cắt để chỉ 
ra cho Prolog biết những con đường dẫn đến thất bại. 
• Nhát cắt cho phép tạo ra các kết luận loại trừ nhau dạng : 
If Condition Thì Conclusion_1 nếu Conclusion_2 
• Nhát cắt cho phép định nghĩa phép phủ định : not Goal thoả mãn nếu 
Goal thất bại. 
• Prolog có hai đích đặc biệt : true luôn luôn đúng và fail luôn luôn sai. 
• Cần thận trọng khi sử dụng kỹ thuật nhát cắt, nhát cắt có thể làm sai lệch 
sự tương ứng giữa nghĩa khai báo và nghĩa thủ tục của một chương trình. 
• Phép phủ định not trong Prolog không hoàn toàn mang ý nghĩa lôgich, cần 
chú ý khi sử dụng not. 
Sử dụng các cấu trúc 
Các ví dụ đã trình bày trong chương này minh hoạ những đặc trưng rất tiêu 
biểu của kỹ thuật lập trình Prolog : 
• Trong Prolog, tập hợp các sự kiện đủ để biểu diễn một cơ sở dữ liệu. 
• Kỹ thuật đặt câu hỏi và so khớp của Prolog là những phương tiện mềm dẻo 
cho phép truy cập tù cơ sở dữ liệu những thông tin có cấu trúc. 
• Cần sử dụng phương pháp trừu tượng hoá dữ liệu như là một kỹ thuật lập 
trình cho phép sử dụng các cấu trúc dữ liệu phức tạp một cách đơn giản, 
làm chương trình trở nên dễ hiểu. Trong Prolog, phương pháp trừu tượng 
hoá dữ liệu rất dễ triển khai. 
• Những cấu trúc toán học trừu tượng như ôtômat cũng rất dễ cài đặt trong 
Prolog. 
• Người ta có thể tiếp cận đến nhiều lời giải khác nhau cho một bài toán nhờ 
sử dụng nhiều cách biểu diễn dữ liệu khác nhau, như trường hợp bài toán 
tám quân hậu. Cách biểu diễn dữ liệu sử dụng nhiều thông tin tiết kiệm 
được tính toán, mặc dù làm cho chương trình trở nên rườm rà, khó cô 
đọng. 
• Kỹ thuật tổng quát hoá một bài toán, tuy trừu tượng, nhưng lại làm tăng 
khả năng hướng đến lời giải, làm đơn giản hoá phát biểu bài toán. 
Kỹ thuật lập trình Prolog 177 
Làm việc với tệp 
Cùng với chế độ tương tác câu hỏi-trả lời, quá trình vào ra và chế độ làm việc 
với tệp đã làm phong phú môi trường làm việc của Prolog. 
• Các tệp trong Prolog đều hoạt động theo kiểu tuần tự. Prolog phân biệt 
dòng vào hiện hành và dòng ra hiện hành. 
• Thiết bị cuối (terminal) của NSD gồm màn hình và bàn phím được xem 
như một tệp giả có tên là user. 
• Prolog có nhiều vị từ có sẵn để xử lý các dòng vào-ra. 
• Khi làm việc với tệp, chế độ đọc ghi là xử lý từng ký tự hoặc từng hạng. 
Bài tập chương 5 
1. Cho chương trình : 
p( 1 ). 
p( 2 ) :- !. 
p( 3 ). 
Cho biết các câu trả lời của Prolog tù các câu hỏi sau : 
(a) ?- p( X ). 
(b) ?- p( X ), p( Y ). 
(c) ?- p( X ), !, p( Y ). 
2. Quan hệ sau đây cho biết một số có thể là dương, bằng không, hoặc âm : 
sign( Number, positive) :- 
Number > 0. 
sign( 0, null). 
sign( Number, negative) :- 
Number < 0. 
Hãy sử dụng kỹ thuật nhát cắt để viết lại chương trình trên hiệu quả hơn. 
3. Thủ tục separate(Number, Positive, Negative) xếp các phần tử 
trong danh sách Number lần lượt thành hai danh sách, danh sách Positive 
chỉ chứa các số dương, hoặc bằng không, danh sách Negative chỉ chứa các 
số âm. Ví dụ : 
separate( [ 3, -1, 0, 5, -2 ], [ 3, 0, 5 ], [ -1, -2 ] ) 
Hãy định nghĩa thủ tục trên theo hai cách, một cách không sử dụng kỹ thuật 
nhát cắt, một cách có sử dụng kỹ thuật nhát cắt. 
178 Lập trình lägich trong Prolog 
4. Cho hai danh sách, Accept và Reject, hãy viết danh sách các đích sử dụng 
kỹ thuật quay lui và các quan hệ member và not để tìm các phần tử có mặt 
trong Accept nhưng không có mặt trong Reject. 
5. Định nghĩa thủ tục difference( Set1, Set2, SetDiff) tìm hiệu hai 
tập hợp Set1 và Set2 với quy ước các tập hợp được biểu diễn bởi các danh 
sách.. Chẳng hạn : 
difference( [ a, b, c, d ], [ b, d, e, f ], [ a, c ] ) 
6. Hãy định nghĩa vị từ unifiable( List1, Term, List2) để kiểm tra so 
khớp, trong đó List2 là danh sách tất cả các phần tử của List1 có thể so 
khớp với Term nhưng không thực hiện phép thế trên các biến đã được so 
khớp. Ví dụ : 
?- unifiable( [ X, bibo, t( Y ) ], t(a), List ). 
List = [X, t( Y )] 
Chú ý rằng X và Y vẫn là các biến tự do không thực hiện phép thế t(a) cho 
X, hay phép thế a cho Y. Muốn vậy, thực hiện hướng dẫn sau : 
Sử dụng phép phủ định not( Term1 = Term2). Nếu quan hệ Term1 = 
Term2 được thoả mãn, khi đó, not( Term1 = Term2) sẽ thất bại, và 
phép thế biến không xảy ra. 
7. Bài toán mã đi tuần. Giả sử các ô của bàn cờ vua 8×8 được biểu diễn bởi các 
cặp toạ độ có dạng X/Y, với X và Y nằm trong khoảng 1 và 8. 
(a) Định nghĩa quan hệ jump( case1, case2 ), bằng cách sử dụng luật đi 
của quân mã, và giả sử rằng case1 luôn luôn bị ràng buộc. Ví dụ : 
?- jump( 1/1, C ). 
C = 3/2; 
C = 2/3; 
No 
(b) Định nghĩa quan hệ mvt_ knight( path ), với path là một danh sách 
gồm các ô biểu diễn lộ trình các bước nhảy hợp lý của quân mã trên bàn 
cờ rỗng. 
(c) Sử dụng quan hệ mvt_ knight, viết một câu hỏi để tìm tất cả các lộ 
trình bốn bước nhảy hợp lý của quân mã, xuất phát từ ô có toạ độ 2/1, để 
đến biên bên phải của bàn cờ (Y = 8) và để đến ô 5/4 sau hai bước nhảy. 
8. Cho f một tệp chứa các hạng, hãy định nghĩa thủ tục findterm(Term) để 
đưa ra màn hình hạng đầu tiên của f khớp được với Term ? 
9. Cho f một tệp chứa các hạng, hãy định nghĩa thủ tục findallterm(Term) 
để đưa ra màn hình tất cả các hạng của f khớp được với Term ? Kiểm tra 
tính chất biến Term không thể được gán giá trị khi thực hiện tìm kiếm. 
Kỹ thuật lập trình Prolog 179 
10. Hãy mở rộng thủ tục del_space đã được trình bày trong phần lý thuyết để 
có thể xử lý loại bỏ các dấu cách thừa nằm trước dấu phẩy (comma) và chỉ 
giữ lại một dấu cách nằm ngay sau dấu phẩy. 
11. Tương tự bài 3 cho các dấu chấm câu khác như dấu chấm (period), dấu chấm 
phẩy (semicolon), dấu chấm hỏi (question mark), v.v... 
12. Định nghĩa quan hệ firstchar( Atom, Char) cho phép kiểm tra Char 
có phải là ký tự đầu tiên của Atom không (Atom bắt đầu bởi Char) ? 
13. Định nghĩa thủ tục cho phép đổi một danh từ tiếng Anh từ số ít (singular) 
sang số nhiều (plural) được thực hiện như sau : 
?- plural ( table, X ). 
X = tables 
Yes 
14. Áp dụng thủ tục readsentence đã được trình bày trong phần lý thuyết để 
xây dựng thủ tục : 
?- find( Keyword, Sentence ). 
cho phép tìm trong tệp đang đọc một câu có chứa từ khoá Keyword. Câu 
Sentence phải ở dạng mới được đọc vào chưa xử lý, nghĩa là được biểu 
diễn bởi một chuỗi ký tự, hoặc bởi một nguyên tử. 
THÔNG TIN VỀ TÁC GIẢ 
GIÁO TRÌNH “LẬP TRÌNH LÔGIC” 
1 Thông tin về tác giả : 
+ Họ và tên : Phan Huy Khánh 
+ Quê quán : Nghệ An 
+ Cơ quan công tác : 
Khoa Công nghệ Thông tin, 
Trường Đại học Bách khoa, Đại học Đà Nẵng 
+ Email: 
[email protected], [email protected] 
2 Phạm vi và đối tượng sử dụng : 
+ Giáo trình dùng tham khảo cho các ngành Công nghệ Thông tin 
+ Có thể dùng ở các trường có đào tạo các chuyên ngành Công nghệ Thông tin 
+ Từ khóa : 
Sự kiện, luật, luật đệ quy, mệnh đề, hạng, vị từ, đích, đệ quy, danh sách, 
hợp nhất, nhát cắt. 
+ Yêu cầu kiến thức trước khi học môn này : 
Tin học đại cương, Toán rời rạc, Cấu trúc dữ liệu và thuật toán 
+ Đã xuất bản : 
“Lập trình logic trong Prolog”, Nhà Xuất bản Đại học Quốc gia Hà Nội, 2004