Prolog là gì: ngôn ngữ lập trình bằng sự kiện và luật suy diễn logic

Prolog là ngôn ngữ lập trình trong đó người viết không ra lệnh "làm bước 1, bước 2", mà khai báo sự kiện (điều đúng) và luật (nếu điều này đúng thì điều kia đúng), rồi đặt câu hỏi; máy tự suy diễn để tìm câu trả lời. Ngôn ngữ ra đời năm 1972 ở Marseille (Pháp) do Alain Colmerauer và Philippe Roussel xây dựng; tên gọi lấy từ tiếng Pháp programmation en logique — lập trình bằng logic.

Sự kiện: những điều được cho là đúng

Lấy một gia phả nhỏ: ông Hai có hai con trai là Ba và Tư; Ba có con là Năm; Tư có con là Sáu. Trong Prolog viết:

cha(hai, ba).

cha(hai, tu).

cha(ba, nam).

cha(tu, sau).

Mỗi dòng là một sự kiện, đọc là "hai là cha của ba"… Quy ước bắt buộc: tên riêng (hằng) viết chữ thường, biến viết bắt đầu bằng chữ hoa (X, Y, Con…). Dấu chấm kết thúc mỗi câu.

Đặt câu hỏi bằng ?-:

• ?- cha(hai, ba). — máy trả lời true (có trong sự kiện).
• ?- cha(ba, tu). — máy trả lời false.
• ?- cha(hai, X). — "ông Hai là cha của ai?". Máy trả lời X = ba; người dùng gõ dấu chấm phẩy để hỏi tiếp, máy trả X = tu; hỏi tiếp nữa thì false (hết).

Câu hỏi thứ ba là chỗ Prolog khác hẳn ngôn ngữ thường: không có vòng lặp nào được viết ra, nhưng máy tự tìm mọi giá trị khớp.

Luật: nếu – thì viết ngược

Bằng lời: "X là ông nội của Z nếu X là cha của một người Y nào đó, và Y là cha của Z." Trong Prolog:

ong_noi(X, Z) :- cha(X, Y), cha(Y, Z).

Dấu :- đọc là "nếu", dấu phẩy đọc là "và". Phần bên trái là kết luận (đầu luật), phần bên phải là điều kiện (thân luật). Viết sang ký hiệu logic (∀ là "với mọi", ∧ là "và", → là "nếu… thì…"):

∀X ∀Y ∀Z: cha(X, Y) ∧ cha(Y, Z) → ong_noi(X, Z)

Một luật chỉ có đúng một kết luận và thân là chuỗi "và" như vậy gọi là mệnh đề Horn (theo tên nhà logic Alfred Horn). Prolog được thiết kế quanh đúng loại mệnh đề này, vì với chúng máy có cách suy diễn vừa đơn giản vừa hiệu quả.

Máy suy diễn thế nào: lần theo từng bước

Hỏi ?- ong_noi(hai, Z). Máy làm như sau:

1. Khớp với đầu luật. ong_noi(hai, Z) khớp với ong_noi(X, Z) khi X = hai. Việc làm cho hai biểu thức giống nhau bằng cách gán biến gọi là hợp nhất (unification). Mục tiêu giờ là: cha(hai, Y), cha(Y, Z).
2. Giải mục tiêu đầu. Tìm trong sự kiện từ trên xuống: cha(hai, ba) khớp với Y = ba.
3. Giải mục tiêu thứ hai với Y đã biết: cha(ba, Z). Sự kiện cha(ba, nam) khớp với Z = nam. Hết mục tiêu: trả lời Z = nam.
4. Hỏi tiếp (quay lui). Máy quay lại điểm lựa chọn gần nhất: còn sự kiện nào khác khớp cha(ba, Z)? Không. Lùi tiếp: còn sự kiện nào khớp cha(hai, Y)? Có, cha(hai, tu), Y = tu.
5. Giải cha(tu, Z): khớp cha(tu, sau), trả lời Z = sau.
6. Hỏi tiếp nữa: không còn lựa chọn nào, trả lời false.

Cách làm "thử từng lựa chọn theo thứ tự, gặp ngõ cụt thì lùi lại lựa chọn gần nhất" gọi là quay lui (backtracking). Đây cũng là cách người ta giải tay câu đố logic: giả sử, suy ra, vấp mâu thuẫn thì đổi giả sử.

Đệ quy: định nghĩa tổ tiên

"X là tổ tiên của Y" nếu X là cha của Y, hoặc X là cha của một người Z mà Z là tổ tiên của Y:

to_tien(X, Y) :- cha(X, Y).

to_tien(X, Y) :- cha(X, Z), to_tien(Z, Y).

Hỏi ?- to_tien(hai, sau). Lần theo:

1. Luật đầu: cần cha(hai, sau) — không có sự kiện nào. Thất bại, thử luật thứ hai.
2. Luật hai: cần cha(hai, Z), to_tien(Z, sau). Lựa chọn đầu Z = ba.
3. Giải to_tien(ba, sau): luật đầu cần cha(ba, sau) — không có. Luật hai: cha(ba, Z₂) cho Z₂ = nam, rồi to_tien(nam, sau): cha(nam, sau) không có; cha(nam, …) cũng không có. Thất bại toàn bộ nhánh Z = ba.
4. Quay lui: Z = tu. Giải to_tien(tu, sau): luật đầu cần cha(tu, sau) — có. Trả lời true.

Lỗi hay gặp: logic đúng mà chương trình sai

1. Đổi thứ tự điều kiện thành vòng lặp vô tận

Viết luật thứ hai theo kiểu khác, đúng y về logic:

to_tien(X, Y) :- to_tien(X, Z), cha(Z, Y).

Về logic, "X là tổ tiên của Z và Z là cha của Y" cũng cho "X là tổ tiên của Y". Nhưng nếu luật này đứng trước cả luật cơ sở, máy giải to_tien(hai, sau) bằng cách giải to_tien(hai, Z), mà muốn giải nó lại phải giải to_tien(hai, Z′)… mãi mãi, chưa kịp nhìn một sự kiện nào. Kể cả khi đặt nó sau luật cơ sở, một câu hỏi có đáp án false như ?- to_tien(ba, sau). vẫn rơi vào vòng gọi lồng không đáy, vì máy cứ thử "tổ tiên xa hơn nữa" mà không bao giờ hết. Bài học quan trọng nhất về Prolog: ý nghĩa logic không đổi khi đổi thứ tự, nhưng cách máy tìm kiếm thì đổi. Quy tắc thực hành: đặt trường hợp cơ sở trước, và điều kiện "đi xuống dữ liệu" (cha(X, Z)) trước lời gọi đệ quy.

2. Quên điều kiện "khác nhau"

anh_em(X, Y) :- cha(P, X), cha(P, Y).

Hỏi ?- anh_em(ba, ba). máy trả lời true: P = hai là cha của ba, và cũng là cha của ba. Ai cũng thành anh em với chính mình. Cần thêm X \= Y ("X không hợp nhất được với Y"):

anh_em(X, Y) :- cha(P, X), cha(P, Y), X \= Y.

Thử lại: ?- anh_em(ba, tu). — P = hai, cha(hai, tu) đúng, ba khác tu: true. ?- anh_em(ba, ba). — điều kiện cuối thất bại: false.

3. "false" không có nghĩa là "sai trên đời"

Hỏi ?- cha(hai, lan). máy trả lời false. Điều đó chỉ có nghĩa là không chứng minh được từ những gì đã khai. Prolog dùng giả định thế giới đóng: điều gì không có trong cơ sở dữ liệu và không suy ra được thì coi là sai. Toán tử \+ (phủ định) cũng hoạt động theo nghĩa đó, gọi là "phủ định bằng thất bại". Trong một danh bạ khép kín (danh sách lớp, kho hàng), giả định này hợp lý; với tri thức chưa đầy đủ thì phải cẩn thận khi đọc chữ false.

Dòng thời gian

Ngày nay Prolog không phải ngôn ngữ phổ biến, nhưng vẫn sống ở hệ chuyên gia, xử lý ngôn ngữ, kiểm tra cấu hình, lập lịch, và ý tưởng của nó còn trong Datalog — một biến thể dùng để truy vấn cơ sở dữ liệu và phân tích mã nguồn.

Bài tập

Dùng bốn sự kiện cha(…) ở đầu bài.

1. ?- cha(X, nam). trả lời gì? — Đáp án: X = ba.
2. ?- ong_noi(X, sau). trả lời gì? — Đáp án: X = hai (Y = tu).
3. ?- to_tien(ba, sau). trả lời gì? — Đáp án: false; Ba chỉ có con là Năm, Năm không có con.
4. Thêm sự kiện cha(nam, bay). Hỏi ?- to_tien(hai, bay). — Đáp án: true, qua chuỗi hai → ba → nam → bay.
5. Viết luật chau_noi(Z, X) nghĩa là "Z là cháu nội của X". — Đáp án: chau_noi(Z, X) :- ong_noi(X, Z).

Dùng vào đâu

• Sinh viên học Trí tuệ nhân tạo, Logic toán: Prolog là cách nhanh nhất để thấy "suy diễn tự động" chạy thật, từng bước một.
• Người học logic hình thức: viết lại các tam đoạn luận, các lập luận "nếu – thì" thành luật Prolog là một cách kiểm tra mình đã hiểu lượng từ và phép kéo theo chưa.
• Thử ngay: có bản cài đặt Prolog mã nguồn mở miễn phí (SWI-Prolog là bản phổ biến) và các trang chạy Prolog trên trình duyệt; gõ lại gia phả trong bài là chạy được.
• Đọc tiếp: bài toán SAT trong cùng danh mục, để thấy vì sao giới hạn ở mệnh đề Horn giúp suy diễn nhanh.