Prolog
là một ngôn ngữ lập trình. Tên gọi được xuất phát từ cụm từ tiếng Pháp Programmation en logique, nghĩa là "lập trình theo lô gích". Xuất hiện từ năm 1972 (do Alain Colmerauer và Robert Kowalski thiết kế), mục tiêu của là giúp người dùng mô tả lại bài toán ...
là một ngôn ngữ lập trình. Tên gọi được xuất phát từ cụm từ tiếng Pháp Programmation en logique, nghĩa là "lập trình theo lô gích". Xuất hiện từ năm 1972 (do Alain Colmerauer và Robert Kowalski thiết kế), mục tiêu của là giúp người dùng mô tả lại bài toán trên ngôn ngữ của logic, dựa trên đó, máy tính sẽ tiến hành suy diễn tự động dựa vào những cơ chế suy diễn có sẵn (hợp nhất, quay lui và tìm kiếm theo chiều sâu) để tìm câu trả lời cho người dùng.
được sử dụng nhiều trong các ứng dụng của trí tuệ nhân tạo và ngôn ngữ học trong khoa học máy tính (đặ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 đơ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.
Một chương trình bao gồm các luật được biểu diễn dưới dạng mệnh đề Horn. Một mệnh đề Horn có dạng
Head:-Body.
Head là một vị từ logic, còn Body có thể là rỗng hoặc là một tập các vị từ logic. Ví dụ như sau:
chẵn(X):- X chia_dư 2 = 0.
Phần lớn các bộ dịch của các chương trình đều yêu cầu vị từ logic ở phần đầu của một mệnh đề Horn là một vị từ dương (không có dấu phủ định đi kèm), còn các vị từ trong phần Body có thể có dấu phủ định đi kèm. Chương trình logic mà không có sự xuất hiện của dấu phủ định đi kèm gọi là chương trình logic xác định, còn không thì được gọi là chương trình logic thường.
Dữ kiện
Dữ kiện là những mệnh đề Horn mà phần Body là rỗng. Kiểu mệnh đề này thường được sử dụng để mô tả các dự kiện của bài toán, ví dụ như việc khai báo "tôm" là một con mèo:
mèo(tôm).
Khoảng cách từ Hà Nội vào thành phố Hồ Chí Minh là khoảng 2000Km:
khoảng_cách(Hà_Nội,TP_Hồ_Chí_Minh,2000).
Luật
Phần còn lại của các mệnh đề trong một chương trình được gọi là luật. Nó thường thể hiện những phát biểu logic trong bài toán, ví dụ như nếu công tác đèn bật thì đèn sáng:
đèn_sáng(X) :- công_tắc_bật(X).
Toán tử ":-" được dịch thô là "nếu", trong logic thì nó đại diện cho toán tử suy ra "<-". Phát biểu trên được phát biểu dưới dạng văn xuôi là "Nếu công tắc của đèn X bật thì đèn X sẽ sáng". Tất nhiên, bạn có thể chưa thoả mãn với phát biểu này và bổ sung vào nó để có một phát biểu chặt chẽ hơn:
đèn_sáng(X) :- công_tắc_bật(X), có_điện.
Một chương trình logic có ngữ nghĩa của riêng nó. Ngữ nghĩa quyết định những kết luận "đúng" nào có thể rút ra được từ một chương trình . Ví dụ một chương trình gồm một dữ kiện:
mèo(tôm).
Khi đó, ta có thể rút ra duy nhất một dữ kiện đúng là "tôm là một con mèo". Trong một ứng dụng , bạn có thể hỏi một trong hai câu hỏi sau để có được trả lời đúng:
?- mèo(tôm). yes.
Và
?- mèo(X). X = tôm; no.
Trong ví dụ trên, "no" có nghĩa là không còn câu trả lời nào nữa. Mọi câu hỏi khác đều cho trả lời là sai. Điều này có nghĩa là trong một chương trình , người ta sử dụng giả thiết thế giới đóng, mọi thứ bạn khai báo là đúng, nếu không thì nó là sai. Vì vậy trong ví dụ trên, khi bạn hỏi "mitu có phải là một con mèo hay không", bạn sẽ nhận được câu trả lời "no".
Với một chương trình xác định, ngữ nghĩa của nó được định nghĩa là một mô hình tối thiểu của nó.
Với một chương trình bình thường, có nhiều loại ngữ nghĩa được sử dụng như ngữ nghĩa đầy đủ, ngữ nghĩa tối thiểu, ngữ nghĩa hoàn chỉnh,...
Đa số các chương trình biên dịch phổ thông (SWI-, GNU-) sử dụng ngữ nghĩa đầy đủ mà đi kèm là thủ tục suy diễn SLDNF.
Phần này trình bày một số chương trình ví dụ, nó có thể chạy tốt trong SWI-PROLOG.
QuickSort
split(H, [A|X], [A|Y], Z) :- order(A, H), split(H, X, Y, Z). split(H, [A|X], Y, [A|Z]) :- not(order(A, H)), split(H, X, Y, Z). split(_, [], [], []). quicksort([], X, X). quicksort([H|T], S, X) :- split(H, T, A, B), quicksort(A, S, [H|Y]), quicksort(B, Y, X).
Tháp Hà Nội
hanoi(N) :- move(N, left, centre, right). move(0, _, _, _) :- !. move(N, A, B, C) :- M is N-1, move(M, A, C, B), inform(A, B), move(M, C, B, A). inform(X, Y) :- write([move, a, disc, from, the, X, pole, to, the, Y, pole]), nl.
Đại số
/* Tính đạo hàm */ d(X,X,1) :- !. /* d x dx = 1 */ d(C,X,0) :- atomic(C). /* d c dx = 0 */ d(-U,X,-A) :- d(U,X,A). /* d -u dx = - d u dx */ d(U+V,X,A+B) :- d(U,X,A), d(V,X,B). /* d u+v dx = d u dx + d v dx */ d(U-V,X,A-B) :- d(U,X,A), d(V,X,B). /* d u-v dx = d u dx - d v dx */ d(C*U,X,C*A) :- atomic(C), C = X, d(U,X,A), !. /* d c*u dx = c*d u dx */ d(U*V,X,B*U+A*V) :- d(U,X,A), d(V,X,B). /* d u*v dx = u*d v dx + v*d u dx */ d(U/V,X,A) :- d(U*V^(-1),X,A). /* d u/v dx = d (u*v)^-1 dx */ d(U^C,X,C*U^(C-1)*W) :- atomic(C), C = X, d(U,X,W). /* d u^c dx = c*u^(c-1)*d u dx */ d(log(U),X,A*U^(-1)) :- d(U,X,A). /* d ln(u) dx = u^-1 * d u dx */ /* Tính tích phân */ i(0,X,0) :- !. /* Int 0 dx = 0 */ i(X,X,(X*X)/2) :- !. /* Int X dx = (X^2)/2 */ i(C,X,C*X) :- atomic(C). /* Int c dx = c*x */ i(-U,X,-A) :- i(U,X,A). /* Int -U dx = - Int U dx */ i(U+V,X,A+B) :- i(U,X,A), i(V,X,B). /* Int U+V dx = Int U dx + Int V dx */ i(U-V,X,A-B) :- i(U,X,A), i(V,X,B). /* Int U-V dx = Int U dx - Int V dx */ i(C*U,X,C*A) :- atomic(C), C = X, i(U,X,A), !. /* Int cU dx = c (Int U dx) */ i(X^C,X,(X^(C+1))/(C+1)) :- atomic(C), !. /* Int x^c dx = x^(c+1)/(c+1) */ i(U,V,U*V-A) :- d(V,U,A), !. /* Int u dv = u*v - Int v du */ /* Một số luật đơn giản */ s(+,X,0,X). /* x + 0 = x */ s(+,0,X,X). /* 0 + x = x */ s(+,X,Y,X+Y). /* x + y = x + y */ s(+,X,Y,Z) :- integer(X), integer(Y), Z is X+Y. /* x + y = z <- Calculate */ s(*,_,0,0). /* anything * 0 = 0 */ s(*,0,_,0). /* 0 * anything = 0 */ s(*,1,X,X). /* 1 * x = x */ s(*,X,1,X). /* x * 1 = x */ s(*,X,Y,X*Y). /* x * y = x * y */ s(*,X*Y,W,X*Z) :- integer(Y), integer(W), Z is Y*W. s(*,X,Y,Z) :- integer(X), integer(Y), Z is X*Y. /* x * y = z <- Calculate */ /* Đơn giản hoá */ simp(E,E) :- atomic(E), !. simp(E,F) :- E =.. [Op, La, Ra], simp(La,X), simp(Ra,Y), s(Op,X,Y,F).
