PROLOG FAST FOOT

Chia sẻ: Minh Nguyen | Ngày: | Loại File: PDF | Số trang:31

Thêm vào BST

Báo xấu

296
lượt xem 82
download

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

Thức ăn nhanh giúp người ta nhanh chân hơn trong việc giành lấy cơ hội. Nhưng cũng rất nguy hiểm - nếu lạm dụng. Hãy thận trọng và ý 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ãy nhớ rằng ngôn ngữ là phương tiện, bất kể nó là loại ngôn ngữ nào. Nội dung truyền đạt quan trọng hơn là cách thức truyền đạt.

Chủ đề:

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

Lưu

Nội dung Text: PROLOG FAST FOOT

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