MỤC LỤC
Phần 1 Giới thiệu Visual prolog 3
1.1 Đặc điểm chung của ngôn ngữ prolog 4
1.2 Cấu trúc của chương trình Visual prolog 13
1.3 Các thành phần trong chương trình Visual prolog 15
Phần 2 Kết nối Visual prolog với C# 28
2.1 Tạo ra file .dll trong chương trình Visual prolog 29
2.2 Kết nối với C# 33
Phần 3 Bài toán ta-canh 36
3.1 Giới thiệu thuật toán A* 37
3.2 Giải bài toán ta canh bằng thuật toán A* 38
3.3 Giải thuật A* của bài toán ta canh viết bằng Visual prolog 39
3.4 Mở rộng bài toán N-puzzle 39
3.5 Giới thiệu về chương trình trò chơi ta canh 42
Phần 4 Tài liệu tham khảo 48
Phần 1: GIỚI THIỆU VISUAL PROLOG
Visual prolog là ngôn ngữ lập trình logic được PDC phát triển dưạ trên nền tảng của Prolog và TurboProlog. Tên gọi Prolog được xuất phát từ cụm từ tiếng Pháp Programmation en logique, nghĩa là "lập trình theo logic". Xuất hiện từ năm 1972 (do Alain Colmerauer và Robert Kowalski thiết kế), mục tiêu của Visual prolog là để hổ trợ lập trình công nghiệp, nhấn mạnh đến những vấn đề phức tạp của tri thức. Ngày nay Visual prolog rất mạnh và là ngôn ngữ lập trình logic rất tốt, kết hợp các chức năng của logic, chức năng (function) và lập trình theo mô hình hướng đối tượng. Đặc biệt là trong ngành xử lý ngôn ngữ tự nhiên vì đây là mục tiêu thiết kế ban đầu của nó. Cú pháp và ngữ nghĩa của Prolog đơn giản và sáng sủa, nó được người Nhật coi là một trong những nền tảng để xây dựng máy tính thế hệ thứ năm mà ở đó, thay vì phải mô tả cách giải quyết một bài toán trên máy tính, con người chỉ cần mô tả bài toán và máy tính sẽ hỗ trợ họ nốt phần còn lại.
Các chức năng của Visual prolog
· Khái niệm lập trình logic (backtracking ,pattern matching)
· Hỗ trợ unicode
· Quản lý bộ nhớ tự động
· Tính đa hình
·
Visual prolog là môi trường lập trình hoàn hảo với:
· Graphical Integrated Development Environment (IDE)
· Compiler
· Linker
· Debugger
Với Visual prolog bạn có thể xây dựng các ứng dụng trên nền tảng Microsoft Windows 32. Nó cũng hổ trợ client-server và three-tier solutions(các giải pháp 3 tầng).
1.1. Đặc điểm chung của ngôn ngữ prolog
- Prolog không phân biệt giữa khái niệm Data và Program như trong Pascal.
- Sức mạnh của Prolog là đệ qui.
- Toàn bộ chương trình được xem như một cơ sở tri thức (knowledgebase).
- Chương trình Prolog là một tập hợp các luật (rules).
- Prolog là ngôn ngữ được thiết kế chủ yếu cho các suy luận, không coi trọng tính toán.
- Kowalski nói Algorithm = logic+control.
- Logic là phát biểu về cái gì bài toán phải giải quyết.
- Control phát biểu về làm thế nào bài toán được giải quyết.
- Người lập trình luận lý chỉ phải thực hiện phần logic còn phần control hệ thống sẽ đảm nhiệm.
1.1.1. Đặc điểm của biến
- Biến và hằng : Prolog qui định biến có ký tự bắt đầu là ký tự in (upppercase) hay ký tự gạch dưới (underscore). Hằng có ký tự bắt đầu là ký tự thường (lowercase).
Thí dụ:
Minh, X, Người, _minh, _x, _người là 6 biến.
minh, x, người, là 3 hằng.
- Biến trong mỗi clauses phải xuất hiện ít nhất 2 lần.
- Nếu biến chỉ xuất hiện một lần trong clauses thì phải thay 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ó thể thay nó bằng biến rỗng.
- Biến rỗng được biểu diễn bằng ký hiệu gạch dưới _ (underscore).
Thí dụ:
clauses
danăng(X) :- biết(X, Y), chơi(X, Z).
Biến Y và Z chỉ xuất hiện 1 lần nên phải đổi thành biến rỗng. Do đó :
clauses
danăng(X) :- biết(X, _ ), chơi(X, _ ).
- Các trạng thái của biến là : tự do (free), bị trói (bound), được cởi (unbound). Các trạng thái này do hệ thống thực hiện. Người lập trình không có bất kỳ tác động nào lên biến để 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.
1.1.2. Kiểu danh sách
- Đây là một loại tập hợp có bản chất đệ qui. Do đó những thao tác trên danh sách cần khai thác tính đệ qui triệt để.
- Danh sách là một loại tập hợp có phần tử là chuỗi các phần tử của một tập hợp trong miền Domains.
- Kiểu danh sách của Prolog được định nghĩa bằng cách thêm ký tự * vào tên kiểu phần tử.
Thí dụ:
domains
họtên = symbol .
dsSV = họtên* .
dsSố = integer* .
dsTên = symbol* .
dsNghềnghiệp = string* .
dsSV là danh sách các phần tử mà mỗi phần tử có kiểu hotên.
dsSố là danh sách các phần tử mà mỗi phần tử là số nguyên.
- Dạng thức của một biến kiểu danh sách :
o Liệt kê : các phần tử của danh sách đặt cách nhau bằng dấu phẩy. Tất cả đặt ở giữa 2 dấu móc vuông.
Thí dụ :
domains
dssố = integer*
Biến X có kiểu Dssố là một danh sách 4 số nguyên 1, 2, 3, 4, được viết như sau :
X = [1,2,3,4]
o Đệ qui : Danh sách được biểu diễn gồm 2 phần, phần Head gồm 1 phần tử đầu của biểu diễn liệt kê và phần Tail gồm những phần tử còn lại của biểu diễn liệt kê. Phần Tail được biểu diễn bằng một danh sách liệt kê khác. Head và Tail đặt cách nhau dấu sổ xuống. Head và Tail được đặt trong dấu móc vuông.
Thí dụ :
domains
dssố = integer*
Biến X có kiểu Dssố là một danh sách 4 số nguyên 1, 2, 3, 4, được viết như sau :
X = [1|[2,3,4]].
- Một số danh sách đặc biệt :
a. Danh sách trống [] có head và tail không được định nghĩa.
b. Danh sách [1,2,3,4] = [1|[2,3,4]] có head là 1, tail là [2,3,4].
c. Danh sách [1] = [1|[] ] có head là 1, tail là danh sách trống [].
d. Danh sách [[1,2,3], [2,3,4,5], [6]] = [[1,2,3]|[[2,3,4,5], [6]]] có head là [1,2,3] và tail là [[2,3,4,5],[6]].
1.1.3. Nguyên tắc trả lời GOAL của Prolog
- Tuần tự từ trên xuống : hệ thống sẽ trả lời cho subgoal đầu tiên, kế đến là subgoal thứ 2, thứ 3, cho đến subgoal cuối cùng.
- So trùng (matching) : để trả lời cho từng subgoal hệ thống dò subgoal tuần tự theo từng dòng trong clauses. Việc dò tìm sẽ dừng khi subgoal trùng với một dòng clause nào đó, nếu không trùng thì dò tiếp cho đến dòng cuối cùng của clauses.
1.1.4. Cơ chế hoạt động của Prolog
1.1.4.1. Đồng nhất (unification): Khi so trùng subgoal với các dòng của clauses hệ thống prolog áp dụng cơ chế đồng nhất.
- Nếu subgoal so trùng với một dòng của clauses là fact thì nó sẽ đồng nhất tên vị từ kế đến là danh sách thông số. Các thông số sẽ được đồng nhất theo dạng thức.
Thí dụ :
class predicates
chếtạo(symbol, symbol) .
clauses
chếtạo(minh, tênlửa). (1)
chếtạo(dũng, máytính). (2)
chếtạo(thư, xehơi). (3)
goal
chếtạo(thư, X).
Prolog sẽ trả lời bằng cách dò trên 3 mệnh đề của phần clauses.
o Với mệnh đề 1 chế tạo (minh, tênlửa) : tên vị từ phù hợp cùng là chế tạo, cùng có 2 thông số, nhưng thông số thứ 1 của goal là thư khác với thông số thứ 1 của mệnh đề 1 là minh. Do đó mệnh đề này không phù hợp với goal. Việc so trùng tiếp tục.
o Với mệnh đề 2 chế tạo (dũng, máytính) : tên vị từ phù hợp cũng là chế tạo, cùng có 2 thông số, nhưng thông số thứ 1 của goal là thư khác với thông số thứ 1 của mệnh đề 1 là dũng. Do đó mệnh đề này không phù hợp với goal. Việc so trùng tiếp tục.
o Với mệnh đề 3 chế tạo (thư, xehơi) : tên vị từ phù hợp cũng là chếtạo, cùng có 2 thông số, 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ị nên đồng nhất với thông số thứ 2 là xe hơi. Vậy hệ thống sẽ trả lời X là xe hơi.
- Nếu subgoal so trùng với một dòng của clauses là rule thì nó đồng nhất tên, kế đó đồng nhất dạng thức thông số. Cuối cùng là kiểm tra các subgoal diên tả điều kiện có trong mệnh đề đó.
Thí dụ :
domains
dssố = integer*
class predicates
dub(dssố,dssố)
clauses
sub( [], _ ) :- subgoal, . (1)
sub( [_|[3|Y]], [] ) :- subgoal, . (2)
sub( X, [2|[3,4]] ) :- subgoal, . (3)
goal
sub([5], [Y|[3]] ).
Để thoả mãn goal, hệ thống sẽ tiến hành dò từ mệnh đề 1 đến mệnh đề 3.
o Với mệnh đề 1, ở thông số 1 có [] ≠ [5].
o Với mệnh đề 2, ở thông số 1 có _ = [5] nhưng [3|Y]] ≠ [],
o Với mệnh đề 3, ở thông số 1 có X = [5], ở thông số 2 có Y = 2 và [3,4] ≠ [3] (vì danh sách [3,4] có 2 phần tử còn danh sách [3] chỉ có 1 phần tử),
Hệ thống trả lời là không đáp ứng được goal này mặc dù chưa hề kiểm tra đến các subgoal.
- Nhận xét :
o Sự khác biệt giữa rule của Prolog và if then của Pascal.
o If Điềukiện then Kếtquả = lệnh điều kiện của Pascal.
o Kếtquả if Điềukiện = Rule của Prolog.
o Hệ thống Pascal khi thực hiện lệnh if-then sẽ kiểm tra điều kiện trước, nếu đúng mới thực hiện kết quả. Nhưng với rule của Prolog thì kết quả được kiểm tra trước. Việc kiểm tra được thực hiện gồm hai phần - dạng thức và giá trị. Khi dạng thức và giá trị phù hợp thì hệ thống mới kiểm tra điều kiện (các subgoal).
o Trong một số trường hợp trình tự thực hiện này của Prolog có tiện lợi, vì nếu hình thức kết quả không phù hợp thì không cần thiết kiểm tra điều kiện. Trong khi Pascal việc kiểm tra điều kiện và hình thức kết quả đươc gom chung vào trong điều kiện.
1.1.4.2. Thối lui (backtracking)
- Giả sử có mệnh đề P :- P1, P2, P3. Muốn mệnh đề P thỏa thì các subgoal P1, P2, P3 phải thỏa. Giả sử P1 thỏa nhưng còn 5 trường hợp chưa xét đến. Khi đó hệ thống sẽ kiểm tra xem P2 có thoả hay không. Nếu P2 không thỏa thì hệ thống sẽ thối lui lại để kiểm tra P1 với 5 trường hợp chưa xét. Việc này thực hiện được nhờ cơ chế thối lui của Prolog.
- Các trạng thái của biến
o Tự do (free) : Trước khi bị buộc thì biến được gọi là tự do.
o Bị trói (bound) : Khi biến được đồng nhất thì nó bị buộc giá trị được đồng nhất vào.
o Được cởi (unbind) : Khi backtracking tại vị từ nào thì biến trong thông số của vị từ đó được cởi bỏ giá trị đã mang trước đó ra, và từ lúc này nó được tự do và chờ để bị buộc giá trị mới vào.
Ví dụ :
class predicates
chơisymbol, symbol)
biếtsymbol, symbol)
danăngsymbol)
clauses
chơi(minh, piano). chơi(kính, violon)
chơi(tân, keyboard). chơi(trang, guitare)
biết(tân, vẽtranh). biết(kính, làmthơ)
biết(kính, điêukhắc). biết(kính, soạnnhạc)
đanăng(X) :- biết(X, _), chơi(X, _)
goal
đanăng(X).
+ Để goal thỏa thì 2 subgoal biết(X,_) và chơi(X,_) phải thỏa.
+ Subgoal biết(X, _ ) sẽ được duyệt trên clauses và sẽ lấy giá trị là biết(tân, vẽtranh) và còn 3 mệnh đề mà subgoal này chưa duyệt.
+ Kế đó subgoal chơi(tân, _ ) (biến X không còn tự do đã bị buộc vào giá trị tân) được duyệt nhưng không có mệnh đề nào để nó thỏa vì vậy nó thất bại. Hệ thống sẽ tự thối lui đồng thời biến X được cởi bỏ giá trị tân, nó trở lại trạng thái tự do và dò trở lại subgoal biết(X, _) với 3 mệnh đề còn lại. Như vậy sẽ lấy giá trị biết(kính, làmthơ). Subgoal chơi lại được dò trùng để lấy giá trị. Nó lấy được giá trị chơi(kính, violon). Khi đó goal đã được thỏa và biến X của vị từ đanăng lấy giá trị là kính.
o Chú ý : Biến trong Prolog chỉ có ý nghĩa trong mệnh đề chứa nó. Do đó nhiều mệnh đề khác nhau có thể có cùng tên biến.
1.2. Cấu trúc của chương trình Visual prolog
- Hệ thống visual prolog cung cấp sẵn một số miền tập hợp (Domains) để người lập trình sử dụng : integer, char, real, symbol, string, .
- Hệ thống Visual prolog cũng cung cấp cho người lập trình khả 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.
- Gồm 4 phần: Domains, Predicates, Clauses, Goal.
o Domains là nơi để người lập trình định nghĩa những tập hợp mới (hay đặt tên lại).
o Predicates là phần khai báo các quan hệ giữa các domains.
o Clauses là phần định nghĩa các quan hệ đã khai báo trong phần predicates. Clauses gồm các rule. Rule được dùng để biểu diễn cho câu khai báo có dạng điều kiện - if nguyên_nhân then hậu_quả. Nếu rule không có nguyên nhân thì được gọi là sự kiện (fact). Do đó fact là hậu quả tất yếu xảy ra không không cần một nguyên nhân nào.
o Goal là phần đặt câu hỏi đối với hệ thống.
1.2.1. 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.
- Cách khai báo:
domains
=.
Thí dụ :
domains
songuyen=integer.
- Chú thích: Một số kiểu (tập hợp) cơ bản có sẵn:
o integer : kiểu số nguyên,
o real : kiểu số thực,
o char : kiểu ký tự,
o 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.
o 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.
1.2.2. Predicates
- Tạo quan hệ giữa các tập hợp.
- Cách khai báo:
class predicates
ds1,ds2, ,dsn) [pattern][flow pattern] .
pattern: procedure, multi, determ, nondeterm .
flowpatern: i,o,anyflow.
file:///C:/Users/SPA3CC~1/AppData/Local/Temp/msohtmlclip1/01/clip_image002.jpg
Bảng: Pattern of Predicates
Thí dụ :
domains
songuyen=integer.
class predicates
giaithuasonguyen,songuyen) procedure anyflow.
1.2.3. Clauses
Gồm hai phần: sự kiện(fact) và luật (rule)
- Fact: là một quan hệ trên các tập hợp đã xác định (có sẵn hay đã được xác định trong Domains).
- Rule : gồm 2 phần head và body
o Cách khai báo một Rule là dùng kí hiệu :-
Thí dụ:
giaithua(N,1):-N<1,!. %Phần khai báo các rule
giaithua(N,N*F):-giaithua(N-1,F).
o Rule là quan hệ được định nghĩa từ nhiều quan hệ khác.
o Rule có dạng của câu điều kiện, nghĩa là gồm nguyên nhân và hậu quả (nguyên nhân → hậu quả). Tuy nhiên Rule là câu điều kiện được trình bày theo dạng thức : Hậu quả ← nguyên nhân.
- Do đó Fact có thể được xem là một loại rule đặc biệt - rule không có điều kiện.
Nhận xét :
- Một predicates được định nghĩa trong clauses bằng nhiều fact hay nhiều rule hay kết hợp vừa fact vừa rule.
1.2.4. Goal
- Goal là nơi đặt câu hỏi với hệ thống và hệ thống sẽ cho câu trả lời.
- 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.
- Chương trình thể hiện các phần khai bao trong Visual prolog
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
Phần 1 Giới thiệu Visual prolog 3
1.1 Đặc điểm chung của ngôn ngữ prolog 4
1.2 Cấu trúc của chương trình Visual prolog 13
1.3 Các thành phần trong chương trình Visual prolog 15
Phần 2 Kết nối Visual prolog với C# 28
2.1 Tạo ra file .dll trong chương trình Visual prolog 29
2.2 Kết nối với C# 33
Phần 3 Bài toán ta-canh 36
3.1 Giới thiệu thuật toán A* 37
3.2 Giải bài toán ta canh bằng thuật toán A* 38
3.3 Giải thuật A* của bài toán ta canh viết bằng Visual prolog 39
3.4 Mở rộng bài toán N-puzzle 39
3.5 Giới thiệu về chương trình trò chơi ta canh 42
Phần 4 Tài liệu tham khảo 48
Phần 1: GIỚI THIỆU VISUAL PROLOG
Visual prolog là ngôn ngữ lập trình logic được PDC phát triển dưạ trên nền tảng của Prolog và TurboProlog. Tên gọi Prolog được xuất phát từ cụm từ tiếng Pháp Programmation en logique, nghĩa là "lập trình theo logic". Xuất hiện từ năm 1972 (do Alain Colmerauer và Robert Kowalski thiết kế), mục tiêu của Visual prolog là để hổ trợ lập trình công nghiệp, nhấn mạnh đến những vấn đề phức tạp của tri thức. Ngày nay Visual prolog rất mạnh và là ngôn ngữ lập trình logic rất tốt, kết hợp các chức năng của logic, chức năng (function) và lập trình theo mô hình hướng đối tượng. Đặc biệt là trong ngành xử lý ngôn ngữ tự nhiên vì đây là mục tiêu thiết kế ban đầu của nó. Cú pháp và ngữ nghĩa của Prolog đơn giản và sáng sủa, nó được người Nhật coi là một trong những nền tảng để xây dựng máy tính thế hệ thứ năm mà ở đó, thay vì phải mô tả cách giải quyết một bài toán trên máy tính, con người chỉ cần mô tả bài toán và máy tính sẽ hỗ trợ họ nốt phần còn lại.
Các chức năng của Visual prolog
· Khái niệm lập trình logic (backtracking ,pattern matching)
· Hỗ trợ unicode
· Quản lý bộ nhớ tự động
· Tính đa hình
·
Visual prolog là môi trường lập trình hoàn hảo với:
· Graphical Integrated Development Environment (IDE)
· Compiler
· Linker
· Debugger
Với Visual prolog bạn có thể xây dựng các ứng dụng trên nền tảng Microsoft Windows 32. Nó cũng hổ trợ client-server và three-tier solutions(các giải pháp 3 tầng).
1.1. Đặc điểm chung của ngôn ngữ prolog
- Prolog không phân biệt giữa khái niệm Data và Program như trong Pascal.
- Sức mạnh của Prolog là đệ qui.
- Toàn bộ chương trình được xem như một cơ sở tri thức (knowledgebase).
- Chương trình Prolog là một tập hợp các luật (rules).
- Prolog là ngôn ngữ được thiết kế chủ yếu cho các suy luận, không coi trọng tính toán.
- Kowalski nói Algorithm = logic+control.
- Logic là phát biểu về cái gì bài toán phải giải quyết.
- Control phát biểu về làm thế nào bài toán được giải quyết.
- Người lập trình luận lý chỉ phải thực hiện phần logic còn phần control hệ thống sẽ đảm nhiệm.
1.1.1. Đặc điểm của biến
- Biến và hằng : Prolog qui định biến có ký tự bắt đầu là ký tự in (upppercase) hay ký tự gạch dưới (underscore). Hằng có ký tự bắt đầu là ký tự thường (lowercase).
Thí dụ:
Minh, X, Người, _minh, _x, _người là 6 biến.
minh, x, người, là 3 hằng.
- Biến trong mỗi clauses phải xuất hiện ít nhất 2 lần.
- Nếu biến chỉ xuất hiện một lần trong clauses thì phải thay 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ó thể thay nó bằng biến rỗng.
- Biến rỗng được biểu diễn bằng ký hiệu gạch dưới _ (underscore).
Thí dụ:
clauses
danăng(X) :- biết(X, Y), chơi(X, Z).
Biến Y và Z chỉ xuất hiện 1 lần nên phải đổi thành biến rỗng. Do đó :
clauses
danăng(X) :- biết(X, _ ), chơi(X, _ ).
- Các trạng thái của biến là : tự do (free), bị trói (bound), được cởi (unbound). Các trạng thái này do hệ thống thực hiện. Người lập trình không có bất kỳ tác động nào lên biến để 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.
1.1.2. Kiểu danh sách
- Đây là một loại tập hợp có bản chất đệ qui. Do đó những thao tác trên danh sách cần khai thác tính đệ qui triệt để.
- Danh sách là một loại tập hợp có phần tử là chuỗi các phần tử của một tập hợp trong miền Domains.
- Kiểu danh sách của Prolog được định nghĩa bằng cách thêm ký tự * vào tên kiểu phần tử.
Thí dụ:
domains
họtên = symbol .
dsSV = họtên* .
dsSố = integer* .
dsTên = symbol* .
dsNghềnghiệp = string* .
dsSV là danh sách các phần tử mà mỗi phần tử có kiểu hotên.
dsSố là danh sách các phần tử mà mỗi phần tử là số nguyên.
- Dạng thức của một biến kiểu danh sách :
o Liệt kê : các phần tử của danh sách đặt cách nhau bằng dấu phẩy. Tất cả đặt ở giữa 2 dấu móc vuông.
Thí dụ :
domains
dssố = integer*
Biến X có kiểu Dssố là một danh sách 4 số nguyên 1, 2, 3, 4, được viết như sau :
X = [1,2,3,4]
o Đệ qui : Danh sách được biểu diễn gồm 2 phần, phần Head gồm 1 phần tử đầu của biểu diễn liệt kê và phần Tail gồm những phần tử còn lại của biểu diễn liệt kê. Phần Tail được biểu diễn bằng một danh sách liệt kê khác. Head và Tail đặt cách nhau dấu sổ xuống. Head và Tail được đặt trong dấu móc vuông.
Thí dụ :
domains
dssố = integer*
Biến X có kiểu Dssố là một danh sách 4 số nguyên 1, 2, 3, 4, được viết như sau :
X = [1|[2,3,4]].
- Một số danh sách đặc biệt :
a. Danh sách trống [] có head và tail không được định nghĩa.
b. Danh sách [1,2,3,4] = [1|[2,3,4]] có head là 1, tail là [2,3,4].
c. Danh sách [1] = [1|[] ] có head là 1, tail là danh sách trống [].
d. Danh sách [[1,2,3], [2,3,4,5], [6]] = [[1,2,3]|[[2,3,4,5], [6]]] có head là [1,2,3] và tail là [[2,3,4,5],[6]].
1.1.3. Nguyên tắc trả lời GOAL của Prolog
- Tuần tự từ trên xuống : hệ thống sẽ trả lời cho subgoal đầu tiên, kế đến là subgoal thứ 2, thứ 3, cho đến subgoal cuối cùng.
- So trùng (matching) : để trả lời cho từng subgoal hệ thống dò subgoal tuần tự theo từng dòng trong clauses. Việc dò tìm sẽ dừng khi subgoal trùng với một dòng clause nào đó, nếu không trùng thì dò tiếp cho đến dòng cuối cùng của clauses.
1.1.4. Cơ chế hoạt động của Prolog
1.1.4.1. Đồng nhất (unification): Khi so trùng subgoal với các dòng của clauses hệ thống prolog áp dụng cơ chế đồng nhất.
- Nếu subgoal so trùng với một dòng của clauses là fact thì nó sẽ đồng nhất tên vị từ kế đến là danh sách thông số. Các thông số sẽ được đồng nhất theo dạng thức.
Thí dụ :
class predicates
chếtạo(symbol, symbol) .
clauses
chếtạo(minh, tênlửa). (1)
chếtạo(dũng, máytính). (2)
chếtạo(thư, xehơi). (3)
goal
chếtạo(thư, X).
Prolog sẽ trả lời bằng cách dò trên 3 mệnh đề của phần clauses.
o Với mệnh đề 1 chế tạo (minh, tênlửa) : tên vị từ phù hợp cùng là chế tạo, cùng có 2 thông số, nhưng thông số thứ 1 của goal là thư khác với thông số thứ 1 của mệnh đề 1 là minh. Do đó mệnh đề này không phù hợp với goal. Việc so trùng tiếp tục.
o Với mệnh đề 2 chế tạo (dũng, máytính) : tên vị từ phù hợp cũng là chế tạo, cùng có 2 thông số, nhưng thông số thứ 1 của goal là thư khác với thông số thứ 1 của mệnh đề 1 là dũng. Do đó mệnh đề này không phù hợp với goal. Việc so trùng tiếp tục.
o Với mệnh đề 3 chế tạo (thư, xehơi) : tên vị từ phù hợp cũng là chếtạo, cùng có 2 thông số, 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ị nên đồng nhất với thông số thứ 2 là xe hơi. Vậy hệ thống sẽ trả lời X là xe hơi.
- Nếu subgoal so trùng với một dòng của clauses là rule thì nó đồng nhất tên, kế đó đồng nhất dạng thức thông số. Cuối cùng là kiểm tra các subgoal diên tả điều kiện có trong mệnh đề đó.
Thí dụ :
domains
dssố = integer*
class predicates
dub(dssố,dssố)
clauses
sub( [], _ ) :- subgoal, . (1)
sub( [_|[3|Y]], [] ) :- subgoal, . (2)
sub( X, [2|[3,4]] ) :- subgoal, . (3)
goal
sub([5], [Y|[3]] ).
Để thoả mãn goal, hệ thống sẽ tiến hành dò từ mệnh đề 1 đến mệnh đề 3.
o Với mệnh đề 1, ở thông số 1 có [] ≠ [5].
o Với mệnh đề 2, ở thông số 1 có _ = [5] nhưng [3|Y]] ≠ [],
o Với mệnh đề 3, ở thông số 1 có X = [5], ở thông số 2 có Y = 2 và [3,4] ≠ [3] (vì danh sách [3,4] có 2 phần tử còn danh sách [3] chỉ có 1 phần tử),
Hệ thống trả lời là không đáp ứng được goal này mặc dù chưa hề kiểm tra đến các subgoal.
- Nhận xét :
o Sự khác biệt giữa rule của Prolog và if then của Pascal.
o If Điềukiện then Kếtquả = lệnh điều kiện của Pascal.
o Kếtquả if Điềukiện = Rule của Prolog.
o Hệ thống Pascal khi thực hiện lệnh if-then sẽ kiểm tra điều kiện trước, nếu đúng mới thực hiện kết quả. Nhưng với rule của Prolog thì kết quả được kiểm tra trước. Việc kiểm tra được thực hiện gồm hai phần - dạng thức và giá trị. Khi dạng thức và giá trị phù hợp thì hệ thống mới kiểm tra điều kiện (các subgoal).
o Trong một số trường hợp trình tự thực hiện này của Prolog có tiện lợi, vì nếu hình thức kết quả không phù hợp thì không cần thiết kiểm tra điều kiện. Trong khi Pascal việc kiểm tra điều kiện và hình thức kết quả đươc gom chung vào trong điều kiện.
1.1.4.2. Thối lui (backtracking)
- Giả sử có mệnh đề P :- P1, P2, P3. Muốn mệnh đề P thỏa thì các subgoal P1, P2, P3 phải thỏa. Giả sử P1 thỏa nhưng còn 5 trường hợp chưa xét đến. Khi đó hệ thống sẽ kiểm tra xem P2 có thoả hay không. Nếu P2 không thỏa thì hệ thống sẽ thối lui lại để kiểm tra P1 với 5 trường hợp chưa xét. Việc này thực hiện được nhờ cơ chế thối lui của Prolog.
- Các trạng thái của biến
o Tự do (free) : Trước khi bị buộc thì biến được gọi là tự do.
o Bị trói (bound) : Khi biến được đồng nhất thì nó bị buộc giá trị được đồng nhất vào.
o Được cởi (unbind) : Khi backtracking tại vị từ nào thì biến trong thông số của vị từ đó được cởi bỏ giá trị đã mang trước đó ra, và từ lúc này nó được tự do và chờ để bị buộc giá trị mới vào.
Ví dụ :
class predicates
chơisymbol, symbol)
biếtsymbol, symbol)
danăngsymbol)
clauses
chơi(minh, piano). chơi(kính, violon)
chơi(tân, keyboard). chơi(trang, guitare)
biết(tân, vẽtranh). biết(kính, làmthơ)
biết(kính, điêukhắc). biết(kính, soạnnhạc)
đanăng(X) :- biết(X, _), chơi(X, _)
goal
đanăng(X).
+ Để goal thỏa thì 2 subgoal biết(X,_) và chơi(X,_) phải thỏa.
+ Subgoal biết(X, _ ) sẽ được duyệt trên clauses và sẽ lấy giá trị là biết(tân, vẽtranh) và còn 3 mệnh đề mà subgoal này chưa duyệt.
+ Kế đó subgoal chơi(tân, _ ) (biến X không còn tự do đã bị buộc vào giá trị tân) được duyệt nhưng không có mệnh đề nào để nó thỏa vì vậy nó thất bại. Hệ thống sẽ tự thối lui đồng thời biến X được cởi bỏ giá trị tân, nó trở lại trạng thái tự do và dò trở lại subgoal biết(X, _) với 3 mệnh đề còn lại. Như vậy sẽ lấy giá trị biết(kính, làmthơ). Subgoal chơi lại được dò trùng để lấy giá trị. Nó lấy được giá trị chơi(kính, violon). Khi đó goal đã được thỏa và biến X của vị từ đanăng lấy giá trị là kính.
o Chú ý : Biến trong Prolog chỉ có ý nghĩa trong mệnh đề chứa nó. Do đó nhiều mệnh đề khác nhau có thể có cùng tên biến.
1.2. Cấu trúc của chương trình Visual prolog
- Hệ thống visual prolog cung cấp sẵn một số miền tập hợp (Domains) để người lập trình sử dụng : integer, char, real, symbol, string, .
- Hệ thống Visual prolog cũng cung cấp cho người lập trình khả 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.
- Gồm 4 phần: Domains, Predicates, Clauses, Goal.
o Domains là nơi để người lập trình định nghĩa những tập hợp mới (hay đặt tên lại).
o Predicates là phần khai báo các quan hệ giữa các domains.
o Clauses là phần định nghĩa các quan hệ đã khai báo trong phần predicates. Clauses gồm các rule. Rule được dùng để biểu diễn cho câu khai báo có dạng điều kiện - if nguyên_nhân then hậu_quả. Nếu rule không có nguyên nhân thì được gọi là sự kiện (fact). Do đó fact là hậu quả tất yếu xảy ra không không cần một nguyên nhân nào.
o Goal là phần đặt câu hỏi đối với hệ thống.
1.2.1. 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.
- Cách khai báo:
domains
Thí dụ :
domains
songuyen=integer.
- Chú thích: Một số kiểu (tập hợp) cơ bản có sẵn:
o integer : kiểu số nguyên,
o real : kiểu số thực,
o char : kiểu ký tự,
o 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.
o 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.
1.2.2. Predicates
- Tạo quan hệ giữa các tập hợp.
- Cách khai báo:
class predicates
pattern: procedure, multi, determ, nondeterm .
flowpatern: i,o,anyflow.
file:///C:/Users/SPA3CC~1/AppData/Local/Temp/msohtmlclip1/01/clip_image002.jpg
Bảng: Pattern of Predicates
Thí dụ :
domains
songuyen=integer.
class predicates
giaithuasonguyen,songuyen) procedure anyflow.
1.2.3. Clauses
Gồm hai phần: sự kiện(fact) và luật (rule)
- Fact: là một quan hệ trên các tập hợp đã xác định (có sẵn hay đã được xác định trong Domains).
- Rule : gồm 2 phần head và body
o Cách khai báo một Rule là dùng kí hiệu :-
Thí dụ:
giaithua(N,1):-N<1,!. %Phần khai báo các rule
giaithua(N,N*F):-giaithua(N-1,F).
o Rule là quan hệ được định nghĩa từ nhiều quan hệ khác.
o Rule có dạng của câu điều kiện, nghĩa là gồm nguyên nhân và hậu quả (nguyên nhân → hậu quả). Tuy nhiên Rule là câu điều kiện được trình bày theo dạng thức : Hậu quả ← nguyên nhân.
- Do đó Fact có thể được xem là một loại rule đặc biệt - rule không có điều kiện.
Nhận xét :
- Một predicates được định nghĩa trong clauses bằng nhiều fact hay nhiều rule hay kết hợp vừa fact vừa rule.
1.2.4. Goal
- Goal là nơi đặt câu hỏi với hệ thống và hệ thống sẽ cho câu trả lời.
- 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.
- Chương trình thể hiện các phần khai bao trong Visual prolog
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links