Lập trình ký hiệu (tiếng Anh Logic Programming) là phương pháp lập trình dựa trên logic toán với các mối quan hệ và suy luận logic. Chương trình viết bằng ngôn ngữ lập trình logic bao gồm các sự kiện và luật (thuộc miền ứng dụng nào đó) và các câu truy vấn.

Khái niệm cơ bản

Chương trình logic không xác định trình tự thực hiện của các tập lệnh chương trình như trong các ngôn ngữ lập trình khác. Khi người sử dụng chỉ ra các thông số của câu truy vấn, máy tính sẽ tiến hành suy luận logic (chính là thực hiện chương trình logic), kết hợp sự kiện và luật đã cho trong chương trình để xác định cụ thể các thông số, để tìm ra câu trả lời cho câu truy vấn.

Ví dụ, biểu diễn thông tin một chuyến bay có định dạng như sau:

chuyenBay (so_hieu, diem_khoi_hanh, diem_ha_canh, thoi_gian_cat_canh, thoi_gian_ha_canh)

Chuyến bay từ Hà Nội tới thành phố Hồ Chí Minh có thể là chuyến bay thẳng, tương ứng với mô tả trong chương trình logic như sau:

chuyenBay (VN1, Hanoi, Hochiminh, 8:00AM, 10:00AM)

hoặc chuyến bay chuyển tiếp, tương ứng với hai mô tả như sau:

chuyenBay (VN21, Hanoi, Danang, 8:00AM, 9:00AM)

chuyenBay (VN22, Danang, Hochiminh, 10:00AM, 12:00AM)

Các mô tả trên được gọi là trường hợp cụ thể của quan hệ chuyenBay giữa 5 tham số, tương ứng với số hiệu chuyến bay, thành phố đi, thành phố đến, thời gian đi, thời gian đến.

Mệnh đề Horn

Mệnh đề Horn là mệnh đề IF (nếu) dưới dạng:

A₀ nếu A₁ và A₂ và A₃ và… và A_n.

Mỗi A_i có dạng R_i (…) trong đó R_i là tên quan hệ. Một cách trực quan, mệnh đề được diễn giải là: nếu tất cả các A₁ và A₂… và A_n đều đúng, thì A₀ cũng đúng. Trường hợp khi n bằng 0 mệnh đề Horn có nghĩa là A₀ đúng.

Chương trình logic

Mỗi chương trình logic là tập hợp các mệnh đề Horn, thường được tổ chức như sau:

Sự kiện: quan hệ giữa các đối tượng cụ thể

Luật: tập các mệnh đề Horn

Truy vấn: quan hệ giả thuyết A nào đó giữa các đối tượng.

Ví dụ: Sự kiện: cha_me (a, b); cha_me (b, c); cha_me (a, d); cha_me (d, e).

Luật: ong_ba (X, Z) nếu cha_me (X, Y) và cha_me (Y, Z).

Truy vấn: ong_ba (a, c).

Thực thi chương trình logic nhằm đưa ra khẳng định câu truy vấn.

Giả sử truy vấn là A. Quá trình tìm cách khẳng định A được thực hiện bằng kỹ thuật hợp giải như sau:

• Nếu có một sự kiện đã cho “A₀”, A₀ khớp với A, thì kết luận rằng việc khẳng định A là thành công;

• Nếu có mệnh đề Horn “A₀ nếu A₁ và … và A_n” sao cho A₀ khớp với A, thì sẽ tiếp tục tìm cách khẳng định A₁, … và A_n, bằng cách xét các truy vấn mới A₁, … và A_n. Trường hợp khẳng định A₁, … và A_n tất cả đều thành công thì kết luận rằng việc khẳng định A là thành công. Trường hợp chỉ cần một A_i không khẳng định được, thì sẽ tiếp tục xem có còn mệnh đề Horn nào khác có dạng “A₀ nếu …” hay không. Khi đã xét hết tất cả các mệnh đề Horn trong chương trình sẽ đưa ra kết luận rằng việc khẳng định A là không thành công.

Ví dụ, xét chương trình logic về quan hệ gia đình với các sự kiện và luật như trên.

Việc khẳng định ong_ba (a, c) dẫn đến kiểm tra xem có nằm trong các Sự kiện đã cho hay không. Do không có sự kiện ong_ba (a, c) nên chuyển sang xét xem có mệnh đề Horn đưa ra kết luận về ong_ba (a, c) hay không. Để khớp ong_ba (a, c) với ong_ba (X, Z) trong mệnh đề Horn, ta phải gán cho các biến X và Z các giá trị a và c tương ứng. Quá trình thực hiện quy về việc khẳng định hai truy vấn mới là cha_me (a, Y), cha_me (Y, c). Việc khẳng định cha_me (a, Y) bằng cách tìm kiếm trong các sự kiện đã cho, cho phép xác định Y có giá trị b. Khi đó, sự kiện còn lại cha_me (Y, c) cần phải khẳng định trở thành cha_me (b, c). Sự kiện này được khẳng định do có mặt trong số các sự kiện đã có. Điều này có nghĩa là câu truy vấn ong_ba (a, c) đã được khẳng định.

Lưu ý rằng câu trả lời của máy tính chỉ dựa trên các thông tin có sẵn. Do vậy, có thể thấy các nhược điểm của lập trình logic như sau:

• Quá trình xử lý truy vấn chậm và không hiệu quả, một số trường hợp không ra kết quả hợp lý do các sự kiện và luật không chặt chẽ;

• Càng nhiều sự kiện, quá trình suy diễn càng hiệu quả;

• Các luật là căn cứ để khẳng định các truy vấn, nên tập được cung cấp càng đầy đủ càng tốt;

• Lập trình viên phải biết cách diễn đạt sự kiện, luật và truy vấn...

Ngôn ngữ Prolog

Trong ngôn ngữ lập trình logic, người lập trình không xác định các tính toán hoặc chức năng cần thiết để đưa ra câu trả lời trong một miền ứng dụng. Ưu điểm lớn của ngôn ngữ khai báo là lập trình viên chỉ cần cung cấp thông tin đã biết (sự kiện, luật) và đặt câu truy vấn, mà không cần quan tâm đến cách vận dụng luật và sự kiện để khẳng định câu truy vấn. Từ góc độ của lập trình viên, đây là một cách tiếp cận cấp cao hơn khi giải quyết vấn đề so với các ngôn ngữ lập trình thủ tục hoặc lập trình hàm. Ngôn ngữ lập trình logic phổ biến là Prolog (PROgramming LOGic), được xây dựng năm 1972. Đây là ngôn ngữ logic hình thức đầu tiên. Prolog là một ngôn ngữ phi thủ tục, có các đặc điểm sau:

• Thực thi chương trình chính là suy diễn trên cơ sở sự kiện và quy tắc để trả lời các truy vấn;

• Lập trình viên chỉ cần cung cấp các sự kiện, luật và đưa ra câu truy vấn. Chương trình dịch của máy tính sẽ tiến hành áp dụng kỹ thuật hợp giải cho các cặp mệnh đề (clause) theo phương thức thử sai để suy ra câu trả lời cho truy vấn;

• Ngôn ngữ lập trình Prolog sử dụng các mệnh đề Horn.

Trên thực tế, trong ngôn ngữ lập trình Prolog, tất cả các truy vấn được thể hiện dưới dạng câu hỏi “có”/“không”. Câu trả lời sẽ có hai dạng như sau:

• "No", nghĩa là không thể tìm thấy trả lời cho câu truy vấn;

• "Yes", kèm theo tất cả các cách trả lời câu truy vấn.

Các thành phần cốt lõi của ngôn ngữ lập trình Prolog bao gồm:

• Các thực thể (Entities);

• Các biến (Variables);

• Các thuộc tính (Properties): thuộc tính của các thực thể;

• Mối quan hệ (Relationship): quan hệ giữa các thực thể;

• Rules (các luật): Các luật trong Prolog có ba thành phần:

o Kết luận;

o Ký hiệu "nếu";

o Các điều kiện.

Các ký hiệu logic được sử dụng như sau:

• Dấu phẩy hàm ý AND;

• Dấu chấm phẩy hàm ý OR;

• NOT hàm ý phủ định.

Tài liệu tham khảo

1. Bramer, Max. Logic programming with Prolog. Vol.9. Secaucus: Springer, 2005.
2. Lloyd, John W. Foundations of logic programming. Springer Science & Business Media, 2012.
3. David Hemmendinger, Computer programming language article, Britannica Encyclopedia