III.3. Mäüt säú vê dủ vãư danh sạch 109
CHỈÅNG 5 K THÛT LÁÛP TRÇNH PROLOG 117
I. NHẠT CÀÕT 117
I.1. Khại niãûm nhạt càõt 117
I.2. K thût sỉí dủng nhạt càõt 118
I.3. Phẹp ph âënh 126
II. SỈÍ DỦNG CẠC CÁÚU TRỤC 131
II.1. Truy cáûp thäng tin cáúu trục tỉì mäüt cå såí dỉỵ liãûu 132
II.2. Trỉìu tỉåüng hoạ dỉỵ liãûu 136
II.3. Mä phng ätämat hỉỵu hản 138
II.4. Vê dủ : láûp kãú hoảch âi du lëch bàòng mạy bay 144
II.5. Bi toạn tạm qn háûu 150
III. QUẠ TRÇNH VO-RA V LM VIÃÛC VÅÏI TÃÛP 163
III.1. Khại niãûm 163
III.2. Lm viãûc våïi cạc tãûp 164
III.3. ỈÏng dủng chãú âäü lm viãûc våïi cạc tãûp 172
PHỦ LỦC A MÄÜT SÄÚ CHỈÅNG TRÇNH PROLOG 187
PHỦ LỦC B HỈÅÏNG DÁÙN SỈÍ DỦNG SWI-PROLOG 194
I. GIÅÏI THIÃUU SWI-PROLOG 194
II. LAIM VIÃUC VÅÏI SWI-PROLOG 195
II.1. Âàût cáu hi 195
II.2. Chảy trçnh demo 196
II.3. Chảy trçnh demo XPCE 197
II.4. Cạc lãûnh âån (Menu commands) 198
II.5. Soản tho chỉång trçnh 200
III. MÄÜT SÄÚ LÃÛNH SWI-PROLOG THÄNG DỦNG 201
TI LIÃÛU THAM KHO 203
iii
CHỈÅNG 1
Måí âáưu vãư ngän ngỉỵ Prolog
« A program is a theory (in some logic)
and computation is deduction from the theory »
J. A. Robinson
« Program = data structure + algorithm »
N. Wirth
« Algorithm = logic + control »
R. Kowalski
I. Giåïi thiãûu ngän ngỉỵ Prolog
I.1. P
rolog l ngän ngỉỵ âỉåüc sỉí dủng phäø biãún nháút trong dng cạc ngän
ngỉỵ láûp trçnh lägich (Prolog cọ nghéa l PROgramming in LOGic).
Ngän ngỉỵ Prolog do giạo sỉ ngỉåìi Phạp Alain Colmerauer v nhọm
nghiãn cỉïu ca äng âãư xút láưn âáưu tiãn tải trỉåìng Âải hc Marseille âáưu
nhỉỵng nàm 1970. Âãún nàm 1980, Prolog nhanh chọng âỉåüc ạp dủng räüng ri
åí cháu Áu, âỉåüc ngỉåìi Nháût chn lm ngän ngỉỵ phạt triãøn dng mạy tênh
thãú hãû 5. Prolog â âỉåüc ci âàût trãn cạc mạy vi tênh Apple II, IBM-PC,
Macintosh.
rolog l ngän ngỉỵ láûp trçnh lägich
P
P
Prolog cn âỉåüc gi l ngän ngỉỵ láûp trçnh k hiãûu (symbolic programming)
tỉång tỉû cạc ngän ngỉỵ láûp trçnh hm (functional programming), hay láûp trçnh phi
säú (non-numerical programming). Prolog ráút thêch håüp âãø gii quút cạc bi toạn
liãn quan âãún cạc âäúi tỉåüng (object) v mäúi quan hãû (relation) giỉỵa chụng.
Prolog âỉåüc sỉí dủng phäø biãún trong lénh vỉûc trê tû nhán tảo. Ngun l
láûp trçnh lägich dỉûa trãn cạc mãûnh âãư Horn (Horn logêc). Mäüt mãûnh âãư Horn
biãùu diãùn mäüt sỉû kiãûn hay mäüt sỉû viãûc no âọ l âụng hồûc khäng âụng, xy
ra hồûc khäng xy ra (cọ hồûc khäng cọ, v.v ).
1
2 Láûp trçnh logic trong Prolog
Vê dủ I.1 : Sau âáy l mäüt säú mãûnh âãư Horn :
1. Nãúu mäüt ngỉåìi gi m (v) khän ngoan thç ngỉåìi âọ hảnh phục.
2. Jim l ngỉåìi hảnh phục.
3. Nãúu X l cha mẻ ca Y v Y l cha mẻ ca Z thç X l äng ca Z.
4. Tom l äng ca Pat.
5. Táút c mi ngỉåìi âãưu chãút (hồûc Nãúu ai l ngỉåìi thç ai âọ phi chãút).
6. Socrat l ngỉåìi.
Trong cạc mãûnh âãư Horn åí trãn, cạc mãûnh âãư 1, 3, 5 âỉåüc gi l cạc lût
(rule), cạc mãûnh âãư cn lải âỉåüc gi l cạc sỉû kiãûn (fact). Mäüt chỉång trçnh
lägich cọ thãø âỉåüc xem nhỉ l mäüt cå såí dỉỵ liãûu gäưm cạc mãûnh âãư Horn, hồûc
dảng lût, hồûc dảng sỉû kiãûn, chàóng hản nhỉ táút c cạc sỉû kiãûn v lût tỉì 1
âãún 6 åí trãn. Ngỉåìi sỉí dủng (NSD) gi chảy mäüt chỉång trçnh lägich bàòng
cạch âàût cáu hi (query/ question) truy váún trãn cå såí dỉỵ liãûu ny, chàóng
hản cáu hi :
Socrat cọ chãút khäng ?
(tỉång âỉång khàóng âënh Socrat chãút âụng hay sai ?)
Mäüt hãû thäúng lägich s thỉûc hiãûn chỉång trçnh theo cạch «suy lûn»-tçm
kiãúm dỉûa trãn väún «hiãøu biãút» â cọ l chỉång trçnh - cå såí dỉỵ liãûu, âãø minh
chỉïng cáu hi l mäüt khàóng âënh, l âụng (Yes) hồûc sai (No). Våïi cáu hi
trãn, hãû thäúng tçm kiãúm trong cå såí dỉỵ liãûu khàóng âënh Socrat chãút v «tçm
tháúy» lût 5 tho mn (vãú thç). Váûn dủng lût 5, hãû thäúng nháûn âỉåüc Socrat
l ngỉåìi (vãú nãúu) chênh l sỉû kiãûn 5. Tỉì âọ, cáu tr låìi s l :
Yes
cọ nghéa Socrat chãút l âụng.
I.2. Cụ phạp Prolog
I.2.1. Cạc thût ngỉỵ
Mäüt chỉång trçnh Prolog l mäüt cå såí dỉỵ liãûu gäưm cạc mãûnh âãư (clause).
Mäùi mãûnh âãư âỉåüc xáy dỉûng tỉì cạc vë tỉì (predicat). Mäüt vë tỉì l mäüt phạt
biãøu no âọ vãư cạc âäúi tỉåüng cọ giạ trë chán âụng (true) hồûc sai (fail). Mäüt vë
tỉì cọ thãø cọ cạc âäúi l cạc ngun lägich (logic atom).
Måí âáưu vãư ngän ngỉỵ Prolog 3
Mäùi ngun tỉí (nọi gn) biãøu diãùn mäüt quan hãû giỉỵa cạc hảng (term).
Nhỉ váûy, hảng v quan hãû giỉỵa cạc hảng tảo thnh mãûnh âãư.
Hảng âỉåüc xem l nhỉỵng âäúi tỉåüng “dỉỵ liãûu” trong mäüt trçnh Prolog.
Hảng cọ thãø l hảng så cáúp (elementary term) gäưm hàòng (constant), biãún
(variable) v cạc hảng phỉïc håüp (compound term).
Cạc hảng phỉïc håüp biãøu diãùn cạc âäúi tỉåüng phỉïc tảp ca bi toạn cáưn gii
quút thüc lénh vỉûc âang xẹt. Hảng phỉïc håüp l mäüt hm tỉí (functor) cọ
chỉïa cạc âäúi (argument), cọ dảng
Tãn_hm_tỉí(Âäúi_1, , Âäúi_n)
Tãn hm tỉí l mäüt chùi chỉỵ cại v/hồûc ch säú âỉåüc bàõt âáưu båíi mäüt chỉỵ
cại thỉåìng. Cạc âäúi cọ thãø l biãún, hảng så cáúp, hồûc hảng phỉïc håüp. Trong
Prolog, hm tỉí âàûc biãût “.” (dáúu cháúm) biãøu diãùn cáúu trục danh sạch (list).
Kiãøu dỉỵ liãûu hm tỉí tỉång tỉû kiãøu bn ghi (record) v danh sạch (list) tỉång
tỉû kiãøu mng (array) trong cạc ngän ngỉỵ láûp trçnh mãûnh lãûnh (C, Pascal ).
Vê dủ I.2 :
f(5, a, b).
student(robert, 1975, info, 2, address(6, 'mal juin', 'Caen')).
[a, b, c]
Mãûnh âãư cọ thãø l mäüt sỉû kiãûn, mäüt lût (hay quy tàõc), hay mäüt cáu hi.
Prolog quy ỉåïc viãút sau mäùi mãûnh âãư mäüt dáúu cháúm âãø kãút thục nhỉ sau :
• Sỉû kiãûn : < >. (tỉång ỉïng våïi lût < > :- true. )
• Lût : < > :- < >.
• Cáu hi ?- < >. (åí chãú âäü tỉång tạc cọ dáúu nhàõc lãûnh)
I.2.2. Cạc kiãøu dỉỵ liãûu Prolog
Hçnh 1.1. biãøu diãùn mäüt sỉû phán låïp cạc kiãøu dỉỵ liãûu trong Prolog gäưm
kiãøu dỉỵ liãûu så cáúp v kiãøu dỉỵ liãûu cọ cáúu trục. Sỉû phán låïp ny nháûn biãút
kiãøu ca mäüt âäúi tỉåüng nhåì bãư ngoi cụ phạp.
Cụ phạp ca Prolog quy âënh mäùi kiãøu âäúi tỉåüng cọ mäüt dảng khạc nhau.
Prolog khäng cáưn cung cáúp mäüt thäng tin no khạc âãø nháûn biãút kiãøu ca
mäüt âäúi tỉåüng. Trong Prolog, NSD khäng cáưn khai bạo kiãøu dỉỵ liãûu.
4 Láûp trçnh logic trong Prolog
kiãøu dỉỵ liãûu
kiãøu så cáúp kiãøu phỉïc håüp
hàòng biãún
säú chùi k tỉû ngun tỉí
Hçnh I.1. Cạc kiãøu dỉỵ liãûu trong Prolog
Cạc kiãøu dỉỵ liãûu Prolog âỉåüc xáy dỉûng tỉì cạc k tỉû ASCII :
• Cạc chỉỵ cại in hoa A, B, , Z v chỉỵ cại in thỉåìng a, b, , z.
• Cạc chỉỵ säú 0, 1, , 9.
• Cạc k tỉû âàûc biãût, chàóng hản + − ∗ / < > = : . & _ ∼.
I.2.3. Chụ thêch
Trong mäüt chỉång trçnh Prolog, chụ thêch (comment) âỉåüc âàût giỉỵa hai
càûp k hiãûu /* v */ (tỉång tỉû ngän ngỉỵ C). Vê dủ :
/∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗/
/∗∗∗ Âáy l mäüt chụ thêch ∗∗∗/
/∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗/
Trong trỉåìng håüp mún âàût mäüt chụ thêch ngàõn sau mäùi pháưn khai bạo
Prolog cho âãún hãút dng, cọ thãø âàût trỉåïc mäüt k hiãûu %.
Vê dủ :
%%%%%%%%%%%%%%%
% Âáy cng l mäüt chụ thêch
%%%%%%%%%%%%%%%
Prolog s b qua táút c cạc pháưn chụ thêch trong th tủc.
Måí âáưu vãư ngän ngỉỵ Prolog 5
II. Cạc kiãøu dỉỵ liãûu så cáúp ca Prolog
II.1. Cạc kiãøu hàòng (trỉûc kiãûn)
II.1.1. Kiãøu hàòng säú
Prolog sỉí dủng c säú ngun v säú thỉûc. Cụ phạp ca cạc säú ngun v säú
thỉûc ráút âån gin, chàóng hản nhỉ cạc vê dủ sau :
1 1515 0 -97
3.14 -0.0035 100.2
Tu theo phiãn bn ci âàût, Prolog cọ thãø xỉí l cạc miãưn säú ngun v
miãưn säú thỉûc khạc nhau. Vê dủ trong phiãn bn Turbo Prolog, miãưn säú
ngun cho phẹp tỉì -32768 âãún 32767, miãưn säú thỉûc cho phẹp tỉì ±
1e-307
âãún ±
1e+308. Cạc säú thỉûc ráút khi âỉåüc sỉí dủng trong Prolog. L do ch úu åí
chäù Prolog l ngän ngỉỵ láûp trçnh k hiãûu, phi säú.
Cạc säú ngun thỉåìng chè âỉåüc sỉí dủng khi cáưn âãúm säú lỉåüng cạc pháưn tỉí
hiãûn diãûn trong mäüt danh sạch Prolog dảng [a
1
, a
2
, , a
n
].
II.1.2. Kiãøu hàòng lägich
Prolog sỉí dủng hai hàòng lägich cọ giạ trë l true v fail. Thäng thỉåìng cạc
hàòng lägich khäng âỉåüc dng nhỉ tham säú m âỉåüc dng nhỉ cạc mãûnh âãư.
Hàòng fail thỉåìng âỉåüc dng âãø tảo sinh låìi gii bi toạn.
II.1.3. Kiãøu hàòng chùi k tỉû
Cạc hàòng l chùi (string) cạc k tỉû âỉåüc âàût giỉỵa hai dáúu nhạy kẹp.
"Toto \#\{@ tata" chùi cọ tu k tỉû
"" chùi räùng (empty string)
"\"" chùi chè cọ mäüt dáúu nhạy kẹp.
II.1.4. Kiãøu hàòng ngun tỉí
Cạc hàòng ngun tỉí Prolog l chùi k tỉû åí mäüt trong ba dảng nhỉ sau :
(1) Chùi gäưm chỉỵ cại, chỉỵ säú v k tỉû _ ln ln âỉåüc bàõt âáưu bàòng mäüt
chỉỵ cại in thỉåìng.
newyork a_
nil x__y
x25 tom_cruise
6 Láûp trçnh logic trong Prolog
(2) Chùi cạc k tỉû âàûc biãût :
< > .:.
======> ::==
(3) chùi âàût giỉỵa hai dáúu nhạy âån (quote) âỉåüc bàõt âáưu bàòng chỉỵ in
hoa, dng phán biãût våïi cạc tãn biãún :
’Jerry’ ’Tom SMITH’
II.2. Biãún
Tãn biãún l mäüt chùi k tỉû gäưm chỉỵ cại, chỉỵ säú, bàõt âáưu båíi chỉỵ hoa
hồûc dáúu gảch dỉåïi dng :
X, Y, A
Result, List_of_members
_x23, _X, _,
III. Sỉû kiãûn v lût trong Prolog
III.1. Xáy dỉûng sỉû kiãûn
Vê dủ III.1 : Quan hãû gia âçnh
Âãø xáy dỉûng cạc sỉû kiãûn trong mäüt chỉång trçnh Prolog, ta láúy mäüt vê dủ
vãự. Ta xáy dỉûng mäüt cáy gia hãû nhỉ sau :
(a) (b)
pam
jim
pat
ann
liz
bob
tom
parent
tom bob
Hçnh III.1.Cáy gia hãû.
Måí âáưu vãư ngän ngỉỵ Prolog 7
Trong cáy gia hãû (a), cạc nụt chè ngỉåìi, cn cạc mi tãn chè quan hãû cha
mẻ ca (parent of). Sỉû kiãûn Tom l cha mẻ ca Bob âỉåüc viãút thnh mäüt vë
tỉì Prolog nhỉ sau (chụ mãûnh âãư âỉåüc kãút thục båíi mäüt dáúu cháúm) :
parent(tom, bob). % Chụ khäng cọ dáúu cạch trỉåïc dáúu måí ngồûc
ÅÍ âáy, vë tỉì parent cọ hai âäúi l tom v bob. Ngỉåìi ta cọ thãø biãøu diãùn vë
tỉì ny båíi mäüt cáy nhỉ trong Hçnh III.1 (b) : nụt gäúc l tãn vë tỉì, cạc nụt lạ lạ
cạc âäúi.
Tỉì cáy gia hãû trãn âáy, cọ thãø tiãúp tủc viãút cạc vë tỉì khạc âãø nháûn âỉåüc
mäüt chỉång trçnh Prolog gäưm 6 vë tỉì nhỉ sau :
parent(pam, bob).
parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).
Sau khi hãû thäúng Prolog nháûn âỉåüc chỉång trçnh ny, thỉûc cháút l mäüt cå
såí dỉỵ liãûu, ngỉåìi ta cọ thãø âàût ra cạc cáu hi liãn quan âãún quan hãû parent.
Vê dủ cáu hi Bob cọ phi l cha mẻ ca Pat âỉåüc g vo trong hãû thäúng âäúi
thoải Prolog (dáúu nhàõc ?-_) nhỉ sau :
?- parent(bob, pat).
Sau khi tçm tháúy sỉû kiãûn ny trong chỉång trçnh, Prolog tr låìi :
Yes
Ta tiãúp tủc âàût cáu hi khạc :
?- parent(liz, pat).
No
Båíi vç Prolog khäng tçm tháúy sỉû kiãûn Liz l ngỉåìi mẻ ca Pat trong
chỉång trçnh. Tỉång tỉû, Prolog tr låìi No cho sỉû kiãûn :
?- parent(tom, ben).
Vç tãn ben chỉa âỉåüc âỉa vo trong chỉång trçnh. Ta cọ thãø tiãúp tủc âàût
ra cạc cáu hi thụ vë khạc. Chàóng hản, ai l cha (hay mẻ) ca Liz ?
?- parent(X, liz).
Láưn ny, Prolog khäng tr låìi Yes hồûc No, m âỉa ra mäüt giạ trë ca X
lm tho mn cáu hi trãn âáy :
8 Láûp trçnh logic trong Prolog
X = tom
Âãø biãút âỉåüc ai l con ca Bob, ta chè cáưn viãút :
?- parent(bob, X).
Våïi cáu hi ny, Prolog s cọ hai cáu tr låìi, âáưu tiãn l :
X = ann ->;
Âãø biãút âỉåüc cáu tr låìi tiãúp theo, trong háưu hãút cạc ci âàût ca Prolog,
NSD phi g vo mäüt dáúu cháúm pháøy (;) sau -> (Arity Prolog) :
X = pat
Nãúu â hãút phỉång ạn tr låìi m váùn tiãúp tủc u cáưu (;), Prolog tr låìi
No.
NSD cọ thãø âàût cạc cáu hi täøng quạt hån, chàóng hản : ai l cha mẻ ca
ai ? Nọi cạch khạc, cáưn tçm X v Y sao cho X l cha mẻ ca Y. Ta viãút nhỉ
sau :
?- parent(X, Y).
Sau khi hiãøn thë cáu tr låìi âáưu tiãn, Prolog s láưn lỉåüt tçm kiãúm nhỉỵng
càûp cha mẻ − con tho mn v láưn lỉåüt hiãøn thë kãút qu nãúu chỉìng no NSD
cn u cáưu cho âãún khi khäng cn kãút qu låìi gii no nỉỵa (kãút thục båíi
Yes) :
X = pam
Y = bob ->;
X = tom
Y = bob ->;
X = tom
Y = liz ->;
X = bob
Y = ann ->;
X = bob
Y = pat ->;
X = pat
Y = jim
Yes
Tu theo ci âàût Prolog, NSD cọ thãø g vo mäüt dáúu cháúm (.) hồûc Enter
âãø cháúm dỉït giỉỵa chỉìng lưng tr låìi.
Không có nhận xét nào:
Đăng nhận xét