Xem mẫu
- Prolog Fast Foot Prolog Fast Foot .
NỘI DUNG thức. Mọi tấm huy chương đều có mặt trái. Nhưng tốt nhất là đừng lật
mặt trái của nó lên.
HƯỚNG DẪN 2 Hãy nhớ rằng ngôn ngữ là phương tiện, bất kể nó là loại ngôn ngữ nào.
ĐẶC ĐIỂM CỦA PROLOG 5 Nội dung truyền đạt quan trọng hơn là cách thức truyền đạt.
Tài liệu này cung cấp một số kiến thức cơ bản, giúp cho người đọc hiểu
CẤU TRÚC CỦA CHƯƠNG TRÌNH PROLOG 6
được quan điểm lập trình luận lý (logic programming). Cung cách lập
DOMAINS 7
trình này có khác với loại lập trình cấu trúc thường gặp trong các ngôn
PREDICATES 9
ngữ Pascal, C, Fortran, … . Vì vậy việc làm quen với một phong cách
CLAUSES 10
mới cần phải có thời gian. Thời gian để quên cái cũ. Do đó tài liệu này
GOAL 13
cố tránh né việc trình bày dưới góc độ cấu trúc. Tuy nhiên cũng đã có
ĐẶC ĐIỂM CỦA BIẾN 14 đôi lúc vì sự cám dỗ của người đọc mà lại sa đà vào. Và cũng hy vọng
BẢN CHẤT ĐỆ QUI 15 rằng, đây cũng như là sự cám dỗ cuối cùng của chúa.
KIỂU DANH SÁCH 17 Một bài toán từ khi đặt ra cho đến khi có được lời giải phải thực hiện
NGUYÊN TẮC TRẢ LỜI GOAL 20 một khối lượng công việc là M. Dù bài toán được giải bằng ngôn ngữ
CƠ CHẾ HOẠT ĐỘNG CỦA PROLOG 23 lập trình nào thì khối lượng vẫn là M. Ai sẽ đảm nhiệm khối lượng này
LẬP TRÌNH LUẬN LÝ − MÔ TẢ 30 ?. Người lập trình đương nhiên sẽ phải đảm nhiệm một phần, phần còn
lại do hệ thống gánh vác. Như vậy người lập trình trong hệ thống phải
LẬP TRÌNH LUẬN LÝ − ĐỆ QUI 34
biết phần việc nào mình làm và phần việc nào mình không làm. Đây
TẠP LUẬN 45
chính là hành vi cần phải nhận thức. Sự phân chia này sẽ rất khác nhau
LỊCH SỬ 59
ở các ngôn ngữ lập trình. Người lập trình trong hệ thống Prolog luôn là
TÀI LIỆU THAM KHẢO 62 một ông chủ nhàn hạ vì hệ thống Prolog là một người thích ôm lấy
HƯỚNG DẪN công việc. Còn lập trình cấu trúc thì không như vậy, hệ thống của các
ngôn ngữ cấu trúc luôn “thụ động”. Nó chỉ làm việc với sự chỉ bảo của
Thức ăn nhanh giúp người ta nhanh chân hơn trong việc giành lấy cơ người lập trình.
hội. Nhưng cũng rất nguy hiểm - nếu lạm dụng. Hãy thận trọng và ý Vậy người lập trình Prolog sẽ làm gì ?. Họ chỉ cần mô tả bài toán theo
qui định của luận lý (logic). Nghĩa là dùng các câu khai báo để mô tả
N.T. Son 1 2 N.T. Son
- Prolog Fast Foot Prolog Fast Foot .
bài toán. Ngoài ra không cần làm thêm gì cả, hệ thống Prolog sẽ đảm
nhiệm hết phần còn lại.
Phải quên đi một thói quen là một hành vi thường gặp trong các
hoạt động nghiên cứu khoa học. Đây chính là xóa bỏ định kiến.
Học tập ngoài mặt tốt của nó còn có một khía cạnh khác là hình
thành định kiến. Như vậy định kiến là điều không thể tránh khỏi
trong quá trình học tập. Vì vậy hãy chọn lựa phương pháp học tập
sao cho phần định kiến được giảm thiểu. Lập trình luận lý sẽ
phần nào giúp chúng ta giải quyết được bài toán này.
N.T. Son 3 4 N.T. Son
- Prolog Fast Foot Prolog Fast Foot .
ĐẶC ĐIỂM CỦA PROLOG • Hệ thống prolog cũng cung cấp cho người lập trình khả
• Prolog không phân biệt giữa khái niệm Data và Program năng tạo ra các tập hợp mới phù hợp với bài toán cần giải.
như trong Pascal. • Domains là nơi để người lập trình định nghĩa những tập
• Sức mạnh của Prolog là đệ qui. hợp mới (hoặc đặt tên lại).
• Toàn bộ chương trình được xem như một cơ sở tri thức • Predicates là phần khai báo các quan hệ giữa các domains.
(knowledgebase). • Clauses là phần định nghĩa các quan hệ đã khai báo trong
• Chương trình Prolog là một tập hợp các luật (rules). phần predicates.
• Prolog là ngôn ngữ được thiết kế chủ yếu cho các suy luận, • Clauses gồm các rule. Rule được dùng để biểu diễn cho câu
không coi trọng tính toán. khai báo có dạng điều kiện - if nguyên_nhân then hậu_quả.
• Kowalski nói Algorithm = logic+control. Nếu rule không có nguyên nhân thì được gọi là sự kiện
Logic là phát biểu về cái gì bài toán phải giải quyết. (fact). Do đó fact là hậu quả tất yếu xảy ra không không
Control phát biểu về làm thế nào bài toán được giải quyết. cần một nguyên nhân nào.
• Người lập trình luận lý chỉ phải thực hiện phần logic còn • Goal là phần đặt câu hỏi đối với hệ thống.
phần control hệ thống sẽ đảm nhiệm. DOMAINS
• Nơi tạo tập hợp mới có cùng kiểu với tập hợp có sẵn.
Thí dụ :
Domains
Tên = symbol
Tuổi = integer
CẤU TRÚC CỦA CHƯƠNG TRÌNH PROLOG
NghềNghiệp = symbol
• Domains, Predicates, Clauses, Goal.
Chú thích :
• Hệ thống prolog cung cấp sẵn một số tập hợp để người lập
1. Một số kiểu (tập hợp) cơ bản :
trình sử dụng : Integer, Char, Real, Symbol, String, … .
integer : kiểu số nguyên,
N.T. Son 5 6 N.T. Son
- Prolog Fast Foot Prolog Fast Foot .
real : kiểu số thực, Tập hợp thành phần của hội có thể là tập hợp có một phần
char : kiểu ký tự, tử. Thí dụ âm, dương là hai tập hợp có một phần tử.
string : kiểu chuỗi, gồm chuỗi các ký tự có chiều dài
‘tuỳ ý’ được đặt giữa hai dấu nháy.
symbol : là kiểu gồm những ký hiệu, mỗi ký hiệu có
chiều dài tối đa 255 ký tự, bắt đầu bằng ký tự
thường.
2. Dù miền Tên và miền NghềNghiệp có cùng kiểu symbol
nhưng chúng không so sánh hoặc đồng nhất được với
nhau. Nói chung là các tập hợp trong Domains nếu
không cùng tên thì sẽ không tương thích với nhau.
• Tạo tập hợp là tích các tập hợp.
Thí dụ :
Domains
Ấnphẩm = Tạpchí(symbol, symbol)
TiểuSử = LýLịch(symbol, integer, symbol, symbol)
• Tạo tập hợp là hội các tập hợp.
Thí dụ :
Domains
Tên = symbol
Tàiliệu = Book(Tên,Tên) or Magazine(Tên,Tên)
Dấu = âm ; dương ; Kýsố(integer)
Hội hai tập hợp bằng ký hiệu OR hoặc CHẤM PHẨY.
N.T. Son 7 8 N.T. Son
- Prolog Fast Foot Prolog Fast Foot .
PREDICATES Turbo Prolog qui định biến có ký tự bắt đầu là ký tự in
• Tạo quan hệ giữa các tập hợp. (upppercase) hoặc ký tự gạch dưới (underscore). Hằng có ký
Thí dụ : tự bắt đầu là ký tự thường (lowercase).
Domains Thí dụ :
Tên = symbol Minh, X, Người, _minh, _x, _người … là 6 biến.
Nghềnghiệp = string minh, x, người, … là 3 hằng.
Tuổi = integer • Fact
Predicates Fact là một quan hệ trên các tập hợp đã xác định (có sẵn
Lýlịch(Tên, Tuổi, Nghềnghiệp) hoặc đã được xác định trong Domains).
• Tạo quan hệ trống. Đây là cách xác định tập hợp bằng liệt kê.
Thí dụ : Thí dụ :
Predicates Predicates
Repeat() Chơi(symbol, symbol)
Khôngmàu Biết(symbol, symbol)
Repeat và Khôngmàu là tên của hai quan hệ. Tập hợp mà Clauses
nó quan hệ là tập trống. Quan hệ Repeat() còn có thể viết là Chơi(sơ, piano). Chơi(kính, violon).
Repeat. Quan hệ Khôngmàu có thể viết là Khôngmàu(). Chơi(tân, keyboard). Chơi(trang, guitare).
Chơi(sơ, guitare). Chơi(kính, piano).
Biết(sơ, vẽtranh). Biết(kính, làmthơ).
Biết(kính, điêukhắc). Biết(kính, soạnnhạc).
• Rule
CLAUSES Rule là quan hệ được định nghĩa từ nhiều quan hệ khác.
• Biến và hằng Đây là cách xác định tập hợp bằng phương pháp trưng tính.
N.T. Son 9 10 N.T. Son
- Prolog Fast Foot Prolog Fast Foot .
Rule có dạng của câu điều kiện, nghĩa là gồm nguyên nhân Đanăng(X) :- Biết(X, Y), Chơi(X, Z).
và hậu quả (nguyên nhân → hậu quả). Tuy nhiên Rule là Một học sinh X đa năng nếu biết ít nhất một môn nghệ
câu điều kiện được trình bày theo dạng thức : Hậu quả thuật Y và chơi được một môn thể thao Z.
← nguyên nhân. Thí dụ :
Các dạng sau đây tương đương : Chuyển đổi tam đoạn luận sang Prolog :
Hậu quả ← Nguyên nhân hay Mọi người đều phải chết.
Hậu quả if Nguyên nhân hay Socrates là người.
Hậu quả :- Nguyên nhân. Vậy Socrates phải chết.
Do đó Fact có thể được xem là một loại rule đặc biệt - rule Predicates
không có điều kiện. Làngười(symbol)
Nếu mệnh đề nguyên nhân gồm 3 mệnh đề nguyên nhân Chết(symbol)
ngnh1, ngnh2 và ngnh3 kết hợp lại thì được biểu diễn như Clauses
sau : Làngười(socrates).
Nguyên nhân = Ngnh1 and Ngnh2 and Ngnh3. Chết(Ai) :- Làngười(Ai).
Hoặc
Nguyên nhân = Ngnh1, Ngnh2, Ngnh3. Nhận xét :
Một predicates được định nghĩa trong clauses bằng nhiều fact
Thí dụ : hoặc nhiều rule hoặc kết hợp vừa fact vừa rule.
Predicates Thí dụ :
Chơi(symbol, symbol) /* định nghĩa ở trên */ Xác định tập hợp A = {1,2,3,4,5,6,8,10,12,14, … }
Biết(symbol, symbol) /* định nghĩa ở trên */ Predicates
Đanăng(symbol) PtửA(integer)
Clauses Clauses
PtửA(1).
N.T. Son 11 12 N.T. Son
- Prolog Fast Foot Prolog Fast Foot .
PtửA(3). ĐẶC ĐIỂM CỦA BIẾN TRONG TURBO PROLOG
PtửA(5). • Biến trong mỗi clauses phải xuất hiện ít nhất 2 lần.
PtửA(X) :- (X mod 2) = 0. • Nếu biến chỉ xuất hiện một lần trong clauses thì phải thay
Vị từ PtửA được định nghĩa gồm 3 fact và 1 rule. nó bằng biến rỗng (anonymous). Ngoài ra một thông số
nào của vị từ trong clauses mà ta không quan tâm cũng có
GOAL thể thay nó bằng biến rỗng.
• Goal là nơi đặt câu hỏi với hệ thống và hệ thống sẽ cho câu • Biến rỗng được biểu diễn bằng ký hiệu gạch dưới _
trả lời. (underscore).
• Goal gồm một hay nhiều predicates cùng với thông số. Nếu
goal gồm nhiều thành phần thì mỗi thành phần được gọi là
subgoal. Thí dụ :
Thí dụ : Clauses
Cho hệ thống tam đoạn luận như thí dụ ở trên. Khi đó có Đanăng(X) :- Biết(X, Y), Chơi(X, Z).
thể đặt 1 trong 5 câu hỏi sau : Biến Y và Z chỉ xuất hiện 1 lần nên phải đổi thành biến
Goal Chết(Ai). rỗng. Do đó :
Goal Chết(socates). Clauses
Goal Làngười(Ai). Đanăng(X) :- Biết(X, _ ), Chơi(X, _ ).
Goal Làngười(socrates). • Các trạng thái của biến là : tự do (free), bị trói (bound),
Goal Chết(Ai), Làngười(socrates). được cởi (unbound). Các trạng thái này do hệ thống thực
Bốn Goal đầu có 1 subgoal. Nhưng goal cuối có 2 subgoal hiện. Người lập trình không có bất kỳ tác động nào lên biến
là Chết(Ai) và Làngười(socrates). để thay đổi trạng thái. Do đó Prolog không có hành động
gán (assignment) giá trị cho biến như trong ngôn ngữ
Pascal.
N.T. Son 13 14 N.T. Son
- Prolog Fast Foot Prolog Fast Foot .
Miền Cây là hội của hai tập hợp. Tập hợp thứ nhất chỉ có
BẢN CHẤT ĐỆ QUI một phần tử là Trống và tập hợp thứ hai là tập hợp đệ qui
Vì Prolog không phân biệt giữa dữ liệu và chương trình như Tree(symbol, Cây).
Pascal nên vấn đề đệ qui được thực hiện cả trong domains và
clauses.
Nền tảng toán học của đệ qui là định lý truy chứng. Việc áp • Đệ qui trong phần clauses
dụng đệ qui trong Prolog sử dụng cả 2 dạng truy chứng. Thí dụ :
Dạng 1 : Tính giai thừa của một số nguyên.
P1. Giai thừa của 5 là 5 ! = 1×2×3×4×5. Như vậy để tính giai
Pn → Pn+1. thừa của 5 thì tính giai thừa của 4 (=5–1). Sau đó lấy kết
Dạng 2 : quả nhân với 5.
P1. Vậy 5 ! = 4! × 5.
Pm → Pn+1, với m ∈ [1, n]. Predicates
Trong thực tế mệnh đề P1 của truy chứng tương ứng với một Giaithừa (real, real)
tập hợp các mệnh đề sự kiện (fact). Clauses
Mệnh đề Pn → Pn+1 cũng tương ứng với một tập hợp các mệnh Giaithừa(1,1).
đề qui luật (rule). Giaithừa(N,T) :- M=N–1, Giaithừa(M,S), T=S*N.
• Đệ qui trong khai báo Domains Tập hợp thứ nhất gồm một mệnh đề sự kiện là
Thí dụ : Giaithừa(1,1) và tập hợp một mệnh đề đệ qui là
Domains Giaithừa(N,T) :- M=N –1, Giaithừa(M, S), T = S*N.
Cây = Tree(symbol, Cây); Trống
N.T. Son 15 16 N.T. Son
- Prolog Fast Foot Prolog Fast Foot .
KIỂU DANH SÁCH Dssố = integer*
Đây là một loại tập hợp có bản chất đệ qui. Do đó những thao Biến X có kiểu Dssố là một danh sách 4 số nguyên
tác trên danh sách cần khai thác tính đệ qui triệt để. 1, 2, 3, 4, được viết như sau :
• Danh sách là một loại tập hợp có phần tử là chuỗi các phần X = [1,2,3,4]
tử của một tập hợp trong miền Domains. − Đệ qui : Danh sách được biểu diễn gồm 2 phần, phần
• Kiểu danh sách của Prolog được định nghĩa bằng cách thêm Head gồm 1 phần tử đầu của biểu diễn liệt kê và phần
ký tự * vào tên kiểu phần tử. Tail gồm những phần tử còn lại của biểu diễn liệt kê.
Thí dụ : Phần Tail được biểu diễn bằng một danh sách liệt kê
Domains khác. Head và Tail đặt cách nhau dấu sổ xuống. Head
Họtên = symbol và Tail được đặt trong dấu móc vuông.
DsSV = Họtên* Thí dụ :
DsSố = integer* Domains
DsTên = symbol* Dssố = integer*
DsNghềnghiệp = string* Biến X có kiểu Dssố là một danh sách 4 số nguyên
DsSV là danh sách các phần tử mà mỗi phần tử có kiểu 1, 2, 3, 4, được viết như sau :
Hotên. X = [1|[2,3,4]].
DsSố là danh sách các phần tử mà mỗi phần tử là số − Một số danh sách đặc biệt :
nguyên. a. Danh sách trống [] có head và tail không được
• Dạng thức của một biến kiểu danh sách : định nghĩa.
− Liệt kê : các phần tử của danh sách đặt cách nhau b. Danh sách [1,2,3,4] = [1|[2,3,4]] có head là 1,
bằng dấu phẩy. Tất cả đặt ở giữa 2 dấu móc vuông. tail là [2,3,4].
Thí dụ : c. Danh sách [1] = [1|[] ] có head là 1, tail là danh
Domains sách trống [].
N.T. Son 17 18 N.T. Son
- Prolog Fast Foot Prolog Fast Foot .
d. Danh sách [[1,2,3], [2,3,4,5], [6]] = Msg(Cột, Cột)
[[1,2,3]|[[2,3,4,5], [6]]] có head là [1,2,3] và tail Clauses
là [[2,3,4,5],[6]]. Hanoi :- Hanoi(5). (1)
Hanoi(N) :- Dời(N, trái, giữa, phải). (2)
NGUYÊN TẮC TRẢ LỜI GOAL CỦA PROLOG Dời(1, A, _, C) :- Msg(A, C), !. (3)
• Tuần tự từ trên xuống : hệ thống sẽ trả lời cho subgoal Dời(N, A, B, C) :- (4)
đầu tiên, kế đến là subgoal thứ 2, thứ 3, … cho đến M = N-1,
subgoal cuối cùng. Dời(M, A, C, B),
• So trùng (matching) : để trả lời cho từng subgoal hệ thống Msg(A, C), !,
dò subgoal tuần tự theo từng dòng trong clauses. Việc dò Dời(M, B, A, C).
tìm sẽ dừng khi subgoal trùng với một dòng clause nào đó, Msg(Loc1, Loc2) :- (5)
nếu không trùng thì dò tiếp cho đến dòng cuối cùng của write("Dời đĩa từ ", Loc1, " vào", Loc2), nl, !.
clauses. Goal
Thí dụ : Tháp Hà Nội. Hanoi.
Đừng cố tìm hiểu ý nghĩa của chương trình này, chỉ cần Mô tả cấu trúc chương trình :
quan sát hình thức của nó. 1. Sử dụng 2 miền : Cột và integer.
Các ký hiệu ! và nl là các subgoal. 2. Khai báo 4 vị từ :
Domains vị từ Hànội không có thông số,
Cột = symbol vị từ Hànội có 1 thông số,
Predicates vị từ Dời có 4 thông số,
Hanoi vị từ Msg có 2 thông số.
Hanoi(integer) 3. Phần định nghĩa của các vị từ trong clauses :
Dời(integer, Cột, Cột, Cột) vị từ Hànội có 1 mệnh đề,
vị từ Hànội(_) có 1 mệnh đề,
N.T. Son 19 20 N.T. Son
- Prolog Fast Foot Prolog Fast Foot .
vị từ Dời(_,_,_,_) có 2 mệnh đề,
vị từ Msg(_,_) có 1 mệnh đề. CƠ CHẾ HOẠT ĐỘNG CỦA PROLOG
Để thỏa mãn Goal Hanoi, hệ thống sẽ dò tuần tự từ mệnh • Đồng nhất (unification). Khi so trùng subgoal với các
đề đầu tiên đến mệnh đề thứ 5 trong phần clauses. dòng của clauses hệ thống prolog áp dụng cơ chế đồng
Goal Hanoi trùng với phần đầu của mệnh đề 1 nhất.
Hanoi :- Hanoi(5). − Nếu subgoal so trùng với một dòng của clauses là fact
Để thỏa mãn mệnh đề này thì subgoal Hanoi(5) phải được thì nó sẽ đồng nhất tên vị từ kế đến là danh sách
thoả. Khi đó hệ thống sẽ dò trong 5 mệnh đề xem mệnh đề thông số. Các thông số sẽ được đồng nhất theo dạng
nào trùng với Hanoi(5) : thức.
Với mệnh đề 1, Hanoi(5) không so trùng được vì Thí dụ :
phần đầu của mệnh đề 1 là Hanoi (không có thông Predicates
số) còn Hanoi(5) có một thông số. Chếtạo(symbol, symbol)
Với mệnh đề 2, Hanoi(5) so trùng được vì phần đầu Clauses
của mệnh đề 1 là Hanoi(N). Lúc này N bị buộc Chếtạo(minh, tênlửa). (1)
vào giá trị 5. Để mệnh đề này được thỏa thì điều Chếtạo(dũng, máytính). (2)
kiện Dời(N,trái,giữa,phải) của mệnh đề 2 cần phải Chếtạo(thư, xehơi). (3)
được thỏa mãn. Hệ thống lại dò trong 5 mệnh đề Goal
và thấy rằng điều kiện này trùng với mệnh đề 3. Chếtạo(thư, X).
Do đó điều kiện của mệnh đề 3 Msg(A, C) cũng Prolog sẽ trả lời bằng cách dò trên 3 mệnh đề của
phải được thỏa. phần clauses.
Quá trình này diễn tiến cho đến khi không còn điều Với mệnh đề 1 Chếtạo(minh, tênlửa) :
kiện nào đòi hỏi thì hệ thống dừng. tên vị từ phù hợp cùng là Chếtạo,
cùng có 2 thông số,
N.T. Son 21 22 N.T. Son
- Prolog Fast Foot Prolog Fast Foot .
nhưng thông số thứ 1 của goal là thư khác với Domains
thông số thứ 1 của mệnh đề 1 là minh. Do đó Dssố = integer*
mệnh đề này không phù hợp với goal. Việc so Predicates
trùng tiếp tục. Sub(Dssố, Dssố)
Với mệnh đề 2 Chếtạo(dũng, máytính) : Clauses
tên vị từ phù hợp cũng là Chếtạo, Sub( [], _ ) :- subgoal, … . (1)
cùng có 2 thông số, Sub( [_|[3|Y]], [] ) :- subgoal, … . (2)
nhưng thông số thứ 1 của goal là thư khác với Sub( X, [2|[3,4]] ) :- subgoal, .. . (3)
thông số thứ 1 của mệnh đề 1 là dũng. Do đó Goal
mệnh đề này không phù hợp với goal. Việc so Sub([5], [Y|[3]] ).
trùng tiếp tục. Để thoả mãn goal, hệ thống sẽ tiến hành dò từ mệnh
Với mệnh đề 3 Chếtạo(thư, xehơi) : đề 1 đến mệnh đề 3.
tên vị từ phù hợp cũng là Chếtạo, Với mệnh đề 1, ở thông số 1 có [] ≠ [5].
cùng có 2 thông số, Với mệnh đề 2, ở thông số 1 có _ = [5] nhưng [3|Y]]
thống số thứ 1 giống nhau cùng là thư, ≠ [],
thông số thứ 2 của goal là biến X chưa có giá trị Với mệnh đề 3, ở thông số 1 có X = [5], ở thông số 2
nên đồng nhất với thông số thứ 2 là xehơi. Vậy có Y = 2 và [3,4] ≠ [3] (vì danh sách [3,4] có 2
hệ thống sẽ trả lời X là xehơi. phần tử còn danh sách [3] chỉ có 1 phần tử),
− Nếu subgoal so trùng với một dòng của clauses là rule Hệ thống trả lời là không đáp ứng được goal này mặc
thì nó đồng nhất tên, kế đó đồng nhất dạng thức thông dù chưa hề kiểm tra đến các subgoal.
số. Cuối cùng là kiểm tra các subgoal diên tả điều kiện Nhận xét :
có trong mệnh đề đó. Sự khác biệt giữa rule của Prolog và if … then của Pascal.
Thí dụ : If Điềukiện then Kếtquả = lệnh điều kiện của Pascal.
N.T. Son 23 24 N.T. Son
- Prolog Fast Foot Prolog Fast Foot .
Kếtquả if Điềukiện = Rule của Prolog. − Bị trói (bound) : Khi biến được đồng nhất thì nó bị
Hệ thống Pascal khi thực hiện lệnh if-then sẽ kiểm tra điều buộc giá trị được đồng nhất vào.
kiện trước, nếu đúng mới thực hiện kết quả. Nhưng với rule − Được cởi (unbind) : Khi backtracking tại vị từ nào thì
của Prolog thì kết quả được kiểm tra trước. Việc kiểm tra biến trong thông số của vị từ đó được cởi bỏ giá trị đã
được thực hiện gồm hai phần - dạng thức và giá trị. Khi mang trước đó ra, và từ lúc này nó được tự do và chờ
dạng thức và giá trị phù hợp thì hệ thống mới kiểm tra điều để bị buộc giá trị mới vào.
kiện (các subgoal). Thí dụ :
Trong một số trường hợp trình tự thực hiện này của Prolog Predicates
có tiện lợi, vì nếu hình thức kết quả không phù hợp thì Chơi(symbol, symbol)
không cần thiết kiểm tra điều kiện. Trong khi Pascal việc Biết(symbol, symbol)
kiểm tra điều kiện và hình thức kết quả đươc gom chung Đanăng(symbol)
vào trong điều kiện. Clauses
• Thối lui (backtracking) Chơi(minh, piano). Chơi(kính, violon).
− Giả sử có mệnh đề P :- P1, P2, P3. Muốn mệnh đề P Chơi(tân, keyboard). Chơi(trang, guitare).
thỏa thì các subgoal P1, P2, P3 phải thỏa. Giả sử P1 thỏa Biết(tân, vẽtranh). Biết(kính, làmthơ).
nhưng còn 5 trường hợp chưa xét đến. Khi đó hệ thống Biết(kính, điêukhắc). Biết(kính, soạnnhạc).
sẽ kiểm tra xem P2 có thoả hay không. Nếu P2 không Đanăng(X) :- Biết(X, _), Chơi(X, _).
thỏa thì hệ thống sẽ thối lui lại để kiểm tra P1 với 5 Goal
trường hợp chưa xét. Việc này thực hiện được nhờ cơ Đanăng(X).
chế thối lui của Prolog. Để goal thỏa thì 2 subgoal Biết(X,_) và Chơi(X,_) phải
• Các trạng thái của biến thỏa.
− Tự do (free) : Trước khi bị buộc thì biến được gọi là
tự do.
N.T. Son 25 26 N.T. Son
- Prolog Fast Foot Prolog Fast Foot .
Subgoal Biết(X, _ ) sẽ được duyệt trên clauses và sẽ lấy bất lợi hơn là thuận lợi. Lập trình prolog có thể hình dung
giá trị là Biết(tân, vẽtranh) và còn 3 mệnh đề mà subgoal bằng hai từ : mô tả và đệ qui.
này chưa duyệt. Những hướng dẫn sau giúp cho người lập trình quên đi thói
Kế đó subgoal Chơi(tân, _ ) (biến X không còn tự do đã quen lập trình cấu trúc.
bị buộc vào giá trị tân) được duyệt nhưng không có • Hãy mô tả bài toán lại thành các câu khai báo.
mệnh đề nào để nó thỏa vì vậy nó thất bại. Hệ thống sẽ Cần nhận dạng ra các câu điều kiện và các câu chỉ sự kiện.
tự thối lui đồng thời biến X được cởi bỏ giá trị tân, nó Thí dụ :
trở lại trạng thái tự do và dò trở lại subgoal Biết(X, _) Dạng ban đầu của bài toán :
với 3 mệnh đề còn lại. Như vậy sẽ lấy giá trị Biết(kính, Mọi người có sách đều có thể cho Trang mượn. Biết
làmthơ). Subgoal Chơi lại được dò trùng để lấy giá trị. rằng Tâm có một quyển sách.
Nó lấy được giá trị Chơi(kính, violon). Khi đó goal đã Hỏi rằng Tâm có thể cho Trang mượn sách hay
được thỏa và biến X của vị từ Đanăng lấy giá trị là không ?
kính. Dạng câu khai báo :
Chú ý : - Nếu ai có sách thì cho Trang mượn sách.
Biến trong Prolog chỉ có ý nghĩa trong mệnh đề chứa nó. - Tâm có sách.
Do đó nhiều mệnh đề khác nhau có thể có cùng tên biến. - Tâm cho Trang mượn sách ?
• Nhận dạng các quan hệ.
Để nhận dạng ra các quan hệ bằng cách chọn trong các
động từ của các câu khai báo. Còn đối tượng của quan hệ
chính là các danh từ.
LẬP TRÌNH LUẬN LÝ – MÔ TẢ Khi động từ là thì chọn quan hệ là tính từ đi theo nó.
Một việc khó khăn cho người lập trình Prolog là nếu họ đã quá Thí dụ : (tiếp theo)
quen thuộc với lập trình cấu trúc. Kinh nghiệm này gây nhiều Các động từ : Có, Chomượn.
N.T. Son 27 28 N.T. Son
- Prolog Fast Foot Prolog Fast Foot .
Các đối tượng : Nếu đối tượng trừu tượng chỉ có một đối tượng cụ thể
ai (có sách), người (cho mượn), thì ghép nó vào quan hệ. Đối tượng trừu tượng Cáigì chỉ
người (được cho mượn), sách. có một đối tượng cụ thể là sách nên ta ghép sách vào các
Có thể chuyển thành các quan hệ : động từ tương ứng.
Cósách(người), (1) Do đó chỉ còn có các quan hệ :
Có(Ai, Cái_sở_hữu), (2) Cósách(người), (1)
Chomượnsách(Ai_cho, Ai_mượn), (3) Chomượnsách(Ai_cho, Ai_mượn), (3)
Chomượn(Ai_cho,Ai_mượn,Cái_được_mượn) (4) • Chuyển thành fact và rule.
Như vậy có nhiều lựa chọn để mô tả bài toán : Khi chuyển câu điều kiện thành rule nhớ đảo ngược vị trí –
a. (1) & (3). hệ quả đặt phía trước và nguyên nhân đât ở sau.
b. (1) & (4). Thí dụ : (tiếp theo)
c. (2) & (3). if Cósách(Ai) then Chomượnsách(Ai, trang),
d. (2) & (4). Cósách(tâm),
Dữ liệu cụ thể với tất cả quan hệ trên : Chomượnsách(tâm, trang) ?,
Cósách(tâm), Thí dụ :
Có(tâm, sách), a. Dạng ban đầu : Người nào kính trọng mình thì được
if Cósách(Ai) then Chomượnsách(Ai, trang), người khác kính trọng. Trang kính trọng mình. Ai được
if Có(Ai, sách) then Chomượn(Ai, trang, sách), Tâm kính trọng ?.
Chomượnsách(tâm, trang) ?, b. Dạng khai báo :
Chomượn(tâm, trang, sách) ?. - Nếu mình kính trọng mình thì người khác kính trọng
Như vậy dựa vào đâu để có quyết định có một lựa chọn mình.
?. - Trang kính trọng Trang.
- Dựa vào các đối tượng cụ thể. - Tâm kính trọng ai ?.
N.T. Son 29 30 N.T. Son
- Prolog Fast Foot Prolog Fast Foot .
c. Chọn quan hệ : Thí dụ : Phần tử của một danh sách.
- động từ : KínhTrọng, Qui ước L[n] là danh sách L có chiều dài n.
- đối tượng : người, Trang, Tâm. Các đối tượng đều a. Dạng nguyên thủy :
thuộc lớp đối tượng trừu tượng là Người. P = “X là phần tử X của danh sách L”.
d. Chuyển thành fact và rule : b. Biến đổi P tương đương với vô hạn mệnh đề Pn :
Nếu KínhTrọng(X, X) thì KínhTrọng(Y, X), P = (∀n)Pn,
KínhTrọng(trang, trang), KínhTrọng(tâm, Ai). với Pn = “X là phần tử của danh sách L[n] ”.
e. Dạng Prolog tương ứng : c. Dạng truy chứng 1 :
KínhTrọng(Y, X) :- KínhTrọng(X, X). P1.
KínhTrọng(trang, trang). Pn → Pn+1.
Goal KínhTrọng(tâm, Ai). d. Dạng truy chứng tương đương với hai mệnh đề :
LẬP TRÌNH LUẬN LÝ – ĐỆ QUI X là phần tử của L[1].
Để lập trình đệ qui thì trước hết vẫn phải thực hiện phần lập Nếu X là phần tử của L[n] thì X cũng là phần tử của
trình mô tả. Sau đó chọn các câu khai báo có bản chất truy L[n+1].
chứng để chuyển thành dạng đệ qui. Một câu khai báo được e. Tương đương với :
gọi là có bản chất truy chứng khi có thể biến đổi thành tương P1 = X là phần tử của L[1].
đương với vô hạn câu khai báo. Trong thực tế một câu khai P1 = X là phần tử đầu của L, hay
báo có bản chất truy chứng có thể có nhiều dạng tương đương L = [X, … ] = [X|_] (a)
truy chứng. Các thí dụ sau sẽ minh họa điều này. Lý thuyết tập (Pn → Pn+1) = (X là phần tử của L[n+1] :- X là phần
hợp cho chúng ta biết có hai dạng truy chứng hữu hạn. Lập tử của L[n]).
trình luận lý sử dụng cả 2 dạng này. = Nếu X là phần tử của L[n] thì X là phần tử của L[n]
Về việc nhận dạng các câu khai báo có thể đọc thêm ở tài liệu thêm phần tử A ở đầu.
tham khảo [9]. Về các kỹ thuật chuyển một câu sang dạng truy
chứng có thể xem phụ chương 4 của tài liệu tham khảo [10].
N.T. Son 31 32 N.T. Son
- Prolog Fast Foot Prolog Fast Foot .
= Nếu X là phần tử của L[n] thì X là phần tử của b. Pn = X[n] là prefix của L.
[A|L[n]]. c. X[0] = [] là prefix của L.
= Nếu X là phần tử của L[n] thì X cũng là phần tử Nếu X là prefix của L thì [A}X] là prefix của [A|L].
của [_|L[n]]. (truy chứng trên chiều dài của X).
= X là phần tử của [_|L[n]] if X là phần tử của L[n]. [A|Y]) là prefix của [A|L] nếu Y là prefix của L.
(b) d. Prefix([], L). (1)
f. Chọn quan hệ : Ptử(Phàntử, Danhsách). Prefix([A|Y], [A|L]) :- Prefix(Y,L). (2)
g. Chuyển thành vị từ của Prolog : Chú thích :
Domains 1. Ký hiệu [A|L] là thêm phần tử A vào đầu danh sách L.
Phầntử = char (kiểu tùy ý) 2. Biến L trong (1) và (2) chẳng dính dánh gì với nhau.
Danhsách = char* Có thể viết lại (2) là
Predicates Prefix([A|Y], [A|Z]) :- Prefix(Y,Z).
Ptử(Phàntử, Danhsách) 3. Trường hợp này có 2 số nguyên để truy chứng là
Clauses chiều dài của X và chiều dài của L. Nhưng tính chất
Ptử(X, [X | _ ]). (từ a) prefix không thay đổi theo chiều dài của L nên ta
Ptử(X, [_ | Y]) :- Ptử(X,Y). (từ b) chọn truy chứng theo chiều dài của X. Một số thí dụ
Thí dụ : Prefix. sau có thể truy chứng trên nhiều số nguyên khác
(Danh sách đầu của một danh sách) nhau).
(Ap dụng truy chứng dạng thứ 1) Thí dụ : Suffix.
Danh sách X = 234 là danh sách đầu (prefix) của danh (Danh sách đuôi của 1 danh sách)
sách L = 23457894566. (Ap dụng truy chứng dạng thứ 2)
Nhưng danh sách Q = 457 không là danh sách đầu của Danh sách X = 566 là danh sách đuôi (suffix) của danh
L. sách L = 23457894566.
a. P = X là prefix của L.
N.T. Son 33 34 N.T. Son
- Prolog Fast Foot Prolog Fast Foot .
Nhưng danh sách Q = 457 không là danh sách đuôi của 1. Việc phân chia L thành P, Q với chủ ý lấy suffix của
L. một prefix. Nếu tồn tại một điểm cắt như vậy thì X là
a. P = X là suffix của L. chuỗi con của L. Việc kiểm tra điểm này có tồn tại
b. Pn = X là suffix của L[n]. hay không do hệ thống Prolog lo, người lập trình
c. Danh sách X là phần đuôi của danh sách X. không phải lo.
Nếu Danh sách X là phần đuôi của danh sách L[n] thì X 2. Điểm cắt đôi chuỗi L[n] là tuỳ ý, do đó nó là dạng
là phần đuôi của danh sách L[n+1]. truy chứng 2. Vì bài toán sẽ áp dụng cho chuỗi L[m]
d. Subfix(L, L). với m < n. Nếu cắt tại phần tử đầu là truy chứng dạng
Subfix(X,[_|Z]) :- Subfix(X,Z). 1, P = 2, Q = 34579894566.
Thí dụ : Sublist. 3. Thử áp dụng dạng truy chứng 1 để giải bài tập này.
(Danh sách con của một danh sách) Thí dụ : Sublist.
(Ap dụng truy chứng dạng thứ 2) (Ap dụng truy chứng dạng thứ 2)
Danh sách X = 579 là danh sách con của danh sách L = a. P = X là sublist của L.
234579894566. b. Pn = X là sublist của L[n].
Nhưng danh sách Q = 452 không là danh sách con của c. Cắt chuỗi L = 234579894566 làm 2 phần gồm P và Q.
L. Chọn P = 234 và Q = 579894566. Khi đó Q là suffix của
a. P = X là sublist của L. L. Nếu X là prefix của Q thì X là sublist của L. Việc
b. Pn = X là sublist của L[n]. phân chia này với chủ ý lấy prefix của một suffix.
c. Cắt chuỗi L làm 2 phần, L = PQ. d. Sublist(X,Y) :- Prefix(X,Q), Suffix(Q,Y).
Chọn P = 234579 và Q = 894566. Thí dụ : Sublist.
Khi đó P là prefix của L. (Ap dụng 2 lần truy chứng dạng 1)
Nếu X là suffix của P thì X là sublist của L. a. P = X là sublist của L.
d. Sublist(X,Y) :- Prefix(P,Y), Suffix(X,P). b. Pn = X là sublist của L[n].
Chú thích : c. X là sublist của L[n].
N.T. Son 35 36 N.T. Son
- Prolog Fast Foot Prolog Fast Foot .
Nếu X là prefix của L thì X là sublist L. X[1] là [H] thì kết quả là [H|L].
(Trường hợp X không là prefix của L thì X có thể là X[n+1] là [H|T] thì kết nối T với L sau đó lấy kết quả
prefix của L’, với L’ là L bỏ phần tử đầu). thêm phần tử H ở đầu.
Nếu X là sublist của L thì X là sublist của [_|L]. Chỉ cần thể hiện chiều dài 0 và chiều dài n+1.
d. Sublist(X,L) :- Prefix(X,L). Lấy vị từ append có 3 thông số. Thông số 1 là X, thông
Sublist(X,[_|L]) :- Sublist(X,L). số 2 là L và thông số 3 là kết quả.
Chú thích : d. Append([], L, L).
1. Khi trường hợp X không là prefix của L thì X có thể Append([H|T], L, [H|Z]) :- Append(T, L, Z).
là prefix của L nhưng bỏ đi phần tử đầu. Phần tử đầu
của L liên tiếp bị cắt đi nếu X chưa là prefix của L. Thí dụ : Sublist.
2. Như vậy có thể áp dụng tương tự cho suffix của L và (Ap dụng truy chứng dạng thứ 2)
bỏ đi phần tử đuôi khi X không là suffix của L hay a. P = X là sublist của L.
không ?. Điều này không được vì không có cách trực b. Pn = X là sublist của L[n].
tiếp bỏ đi phần tử đuôi. Chỉ có cách xác định trực tiếp c. Danh sách L có thể coi như gồm có 3 phần : P (prefix),
phần tử đầu là nhờ biểu diễn head và tail). X và S (suffix).
3. Biến L của 2 mệnh đề trong phần d không dính dáng Chuỗi L = PXS = 234579894566 thì P = 234, X = 579
gì với nhau. và S = 894566.
Thí dụ : Kết nối 2 danh sách. Một chuỗi nào đó ( _ ) kết hợp với một chuỗi K (XS) có
(Ap dụng truy chứng dạng thứ 1) kết quả là L và chuỗi K là kết quả của sự kết nối giữa X
Danh sách X = 1234, danh sách L = 5678910. Danh sách và chuỗi nào đó.
kết nối là XL = 12345678910. Nếu có được sự kết nối như vậy thì X là chuỗi con của
a. P = Kết nối X vào L. L.
b. Pn = Kết nối X[n] vào L. d. Sublist(X, PXS) :- Append(_ , XS, PXS),
c. X[0] là danh sách trống thì kết quả là L. Append(X, _ , XS).
N.T. Son 37 38 N.T. Son
- Prolog Fast Foot Prolog Fast Foot .
Chú thích : Chú thích :
1. Các thông số X, XS, PXS là tên của 3 biến, không Vị từ Ptử có thể coi như là một trường hợp đặc biệt của
phải là kết nối. Tên biến được đặt như vậy để nhận Sublist. Vì Ptử(X,Y) :- Sublist([X],Y).
dạng sự kết hợp mong muốn giữa các danh sách. Do Thí dụ : Đảo ngược một danh sách.
đó có thể thay tên biến XS bằng tên Y và tên biến (Ap dụng truy chứng dạng thứ 1)
PXS bằng tên L. Kết quả vẫn không có gì thay đổi. a. P = Đảo ngược danh sách L.
Do đó có thể viết lại như sau : b. Pn = Đảo ngược danh sách L[n].
Sublist(X,L) :-Append(_,K,L), Append(X,_,K). c. L[0] có đảo ngược là L[0].
2. Mệnh đề Append(_ , XS, PXS) được sử dụng ở dạng Để đảo ngược L[n+1] = [H|Y] ta đảo ngược Y sau đó kết
này giống như để kiểm tra XS là suffix của PXS, còn nối nó với H.
Append(X, _ , XS) giống như để kiểm tra X là prefix d. Reverse([], []).
của XS. Reverse([H|Y],Z) :- reverse(Y,T), append(T,[H],Z).
Thí dụ : Sublist. Thí dụ : Đảo ngược một danh sách.
(Ap dụng truy chứng dạng thứ 2) a. P = Đảo ngược danh sách L.
a. P = X là sublist của L. b. Pn = Đảo ngược danh sách L[n].
b. Pn = X là sublist của L[n]. c. Nếu L[n] nghịch đảo thì L[n+1] có nghịch đảo. Lấy
c. Subfix của prefix và sử dụng append. phần tử đầu X của danh sách L append với danh sách
Một chuỗi Q (PX) kết hợp với một chuỗi nào đó (_ ) có trống E, nghĩa là có [X|E]. Việc này thực hiện cho đến
kết quả là L (PXS) và chuỗi Q là kết quả của sự kết nối khi L thành trống.
giữa X và chuỗi nào đó. d. Reverse(L, Y) :- Reverse3(L, [], Y).
Nếu có được sự kết nối như vậy thì X là chuỗi con của Reverse3([], E, E) :- !.
L. Reverse3([X | Z], E, Y) :- Reverse3(Z, [X|E], Y).
d. Sublist(X, PXS) :- Append(PX, _ , PXS),
Append(_ , X, PX).
N.T. Son 39 40 N.T. Son
nguon tai.lieu . vn
