วิกิพีเดีย

ภาษาโปรล็อก

ภาษาโปรล็อก (อังกฤษ: Prolog) เป็นภาษาสำหรับการเขียนโปรแกรมเชิงตรรกะ ได้ชื่อมาจาก PROgrammation en LOGique (logic programming) สร้างขึ้นโดย Alain Colmerauer ราว ค.ศ. 1972 ภาษาโปรล็อกเกิดจากความพยายามที่จะสร้างภาษาที่อาศัยวิธีการทางตรรกศาสตร์แทนที่จะกำหนดคำสั่งอย่างละเอียดให้กับคอมพิวเตอร์

ภาษาโปรล็อกถูกนำไปใช้ในโปรแกรมสำหรับปัญญาประดิษฐ์ และภาษาศาสตร์เชิงคำนวณ (computational linguistics) โดยเฉพาะการประมวลผลภาษาธรรมชาติ ไวยากรณ์และความหมายของภาษานั้นเรียบง่ายและชัดเจน (เป้าหมายแรกของภาษาคือเป็นเครื่องมือสำหรับนักภาษาศาสตร์ที่ไม่รู้คอมพิวเตอร์) งานวิจัยจำนวนมากที่ทำให้เกิดการพัฒนาภาษาโปรล็อกในปัจจุบันนั้น เป็นผลมาจากโครงการระบบคอมพิวเตอร์ยุคที่ห้า (fifth generation computer systems project - FGCS) ซึ่งเลือกรูปแบบหนึ่งของภาษาโปรล็อกเป็นภาษาแก่น (Kernel Language) ของระบบปฏิบัติการ

ภาษาโปรล็อกมีพื้นฐานมาจากแคลคูลัสภาคแสดง (predicate calculus) หรือเรียกเต็ม ๆ ว่า แคลคูลัสภาคแสดงอันดับที่หนึ่ง (first-order predicate calculus) โดยจำกัดให้ใช้เฉพาะอนุประโยคของฮอร์น (Horn clause) การดำเนินการของโปรแกรมโปรล็อก ก็คือการประยุกต์วิธีพิสูจน์ทฤษฎีบทโดยใช้รีโซลูชันอันดับหนึ่ง (first-order resolution) แนวคิดพื้นฐานที่เกี่ยวข้องได้แก่ การทำให้เท่ากัน (unification), การเรียกซ้ำจากส่วนท้าย (tail recursion), การย้อนรอย (backtracking)

แบบชนิดข้อมูล แก้

ภาษาโปรล็อกไม่มีแบบชนิดข้อมูลเหมือนกับภาษาโปรแกรมทั่ว ๆ ไป หัวข้อนี้จะพูดถึงศัพท์ของส่วนย่อยของภาษาแทน

อะตอม แก้

อะตอม (atom) คือ ค่าคงที่ซึ่งเขียนแทนด้วยข้อความ โดยอะตอมคือลำดับที่ประกอบด้วย ตัวอักษร ตัวเลข เส้นใต้อักขระ (underscores) และจะต้องขึ้นต้นด้วยตัวพิมพ์เล็ก โดยปกติแล้วถ้าต้องการอะตอมที่ใช้เครื่องหมายพิเศษ จะเขียนเครื่องหมายอัญประกาศเดี่ยว (') กำกับไว้ เช่น '+' เป็น อะตอม แต่ + เป็นตัวดำเนินการ

ตัวเลข แก้

ระบบภาษาโปรล็อกส่วนใหญ่จะไม่แบ่งแยกระหว่างเลขจำนวนเต็ม กับเลขจำนวนจริง

ตัวแปร แก้

ตัวแปรจะแสดงด้วยสายอักขระที่ประกอบด้วย ตัวอักษร ตัวเลข และเส้นใต้อักษร โดยจะต้องขึ้นต้นด้วยตัวพิมพ์ใหญ่ ตัวแปรในภาษาโปรล็อกไม่ใช่ที่เก็บข้อมูล แต่จะมีลักษณะคล้ายรูปแบบ (pattern) ซึ่งกำหนดไว้ในเรื่องการทำให้เท่ากัน

ตัวแปรนิรนาม (anonymous variable) จะเขียนโดยใช้ เครื่องหมายเส้นใต้อักษรเพียงตัวเดียว (_)

พจน์ แก้

พจน์ (term) ใช้แทนข้อมูลที่มีความซับซ้อน ประกอบด้วย ส่วนหัว (head) เป็นอะตอม เรียกว่า ฟังก์เตอร์ (functor) และพารามิเตอร์ต่างๆ (ไม่กำหนดประเภท) จำนวนพารามิเตอร์จะเรียกว่า อะริดี (arity) พจน์สามารถเขียนแทนโดยใช้เพียงส่วนหัวและอะริดี โดยเขียนเป็น ฟังก์เตอร์/อะริตี

ลิสต์ แก้

ลิสต์ไม่ใช่ข้อมูลแบบเดี่ยว แต่เป็นโครงสร้างที่นิยามแบบเรียกซ้ำ (โดยใช้พจน์ '.'/2) คือ

  1. อะตอม [] ใช้แทนลิสต์ว่าง
  2. ถ้า T เป็นลิสต์ และ H เป็นส่วนย่อย จะใช้พจน์​ '.'(H,T) แทนลิสต์

ส่วนย่อยแรก เรียกว่าส่วนหัว (H) จะตามด้วยส่วนที่เหลือของลิสต์ ที่เรียกว่าส่วนหาง (T หรือ tail) เช่น ลิสต์ [1,2,3] จะเขียนแทนด้วย '.'(1, '.'(2, 3)) ตามไวยากรณ์ของภาษาแล้วอาจจะเขียนลิสต์ว่า [H|T] วิธีนี้เป็นที่นิยมมากกว่าการใช้ '.' การประมวลผลข้อมูลในลิสต์ จะทำโดยประมวลผลข้อมูลส่วนหัวก่อน แล้วค่อยทำส่วนที่เหลือ โดยใช้การเรียกซ้ำ

ลิสต์สามารถเขียนได้หลายแบบ ตามความสะดวกของโปรแกรมเมอร์

  • เขียนส่วนย่อยทุกตัว: [abc, 1, f(x), Y, g(A,rst)]
  • เขียนส่วนแรกตัวเดียว: [abc | L1]
  • เขียนส่วนแรกหลายตัว: [abc, 1, f(x) | L2]
  • เขียนเป็นการขยายของพจน์: '.'(abc, '.'(1, '.'(f(x), '.'(Y, '.'(g(A,rst), [])))))

ในการใช้งานจริง ลิสต์ของโปรล็อกมีลักษณะคล้ายกับ ดักไทปปิง ของภาษาสมัยใหม่โดยทั่วไป หรืออาจกล่าวได้ว่า ดักไทปปิงได้นำเอาวิธีการของโปรล็อกไปใช้เนื่องจาก ภาษาโปรล็อก นั้นเกิดมาก่อนภาษาเหล่านั้น

สายอักขระ แก้

สายอักขระจะเขียนอยู่ในเครื่องหมายอัญประกาศคู่ ซึ่งภายในจะแทนด้วยลิสต์ของรหัสแอสกี

ข้อเท็จจริง แก้

การเขียนโปรแกรมภาษาโปรล็อกนั้น จะแตกต่างจากการใช้ภาษาเชิงกระบวนคำสั่ง (procedural langugage) โดยเริ่มจากการสร้างฐานข้อมูลข้อเท็จจริง (facts) และ กฎ (rules) จากนั้นจึงใช้การสอบถาม (queries) เพื่อหาคำตอบ หน่วยพื้นฐานของภาษาโปรล็อกคือ เพรดิเคต (predicate) ซึ่งใช้นิยามความจริง เพรดิเคตจะเขียนอยู่ในรูปพจน์ ซึ่งประกอบด้วยส่วนหัว และอาร์กิวเมนต์ เช่น 

cat(tom).

cat คือส่วนหัว และมีอาร์กิวเมนต์หนึ่งตัวคือ tom จากนั้นจะสามารถสอบถามโปรล็อกถึงความจริงนี้ได้ 

 ?- cat(tom).
     yes.

 ?- cat(X).
     X = tom;
     no.

โดยทั่วไป จะใช้เพรดิเคตนิยามความจริงเกี่ยวกับสิ่งที่โปรแกรมรู้ แต่การใช้เพรดิเคตก็ต้องอาศัยข้อตกลงที่แน่นอน อย่างเพรดิตเคตในตัวอย่างข้างล่าง จะใช้แบบไหน เพื่อบอกว่า Pat เป็นพ่อของ Sally 

father(sally,pat).
father(pat,sally).

ทั้งสองกรณีมีส่วนหัวคือ father และอาร์กิวเมนต์คือ pat และ sally กรณีแรก sally มาก่อน ส่วนกรณีหลัง pat มาก่อน กรณีแรกเป็นตัวอย่างของการนิยามแบบ กริยา ประธาน กรรม ส่วนกรณีหลังจะเป็นแบบ กริยา กรรม ประธาน เนื่องจากระบบโปรล็อกไม่เข้าใขภาษาอังกฤษ ดังนั้นจึงสามารถใช้ได้ทั้งสองแบบ แต่ควรจะกำหนดรูปแบบที่แน่นอนในโปรแกรมเดียวกัน และควรหลีกเลี่ยงการเขียน เช่น 

father(pat,sally).
father(jessica,james).

มีเพรดิเคตหลายตัว ที่กำหนดไว้ในตัวภาษา เพื่อทำให้โปรแกรมสามารถทำงานต่างๆ ได้ (เช่น อินพุต/เอาต์พุต ใช้กราฟิก และสิ่งต่างๆ เพื่อติดต่อกับระบบปฏิบัติการ) เช่น เพรดิเคต write ใช้สำหรับแสดงผลออกจอ 

write('Hello').

จะแสดงคำว่า Hello บนจอ

กฎ แก้

คำสั่งอีกรูปแบบหนึ่งของภาษาโปรล็อกคือ กฎ (rules) เช่น 

light(on) :- switch(on).

เครื่องหมาย ":-" แปลว่า "ถ้า" กฎนี้หมายความว่า light(on) เป็นจริง ถ้า switch(on) เป็นจริง นอกจากนี้สามารถใช้ตัวแปรในกฎได้ โดยตัวแปรจะขึ้นต้นด้วยตัวพิมพ์ใหญ่ ส่วนค่าคงที่จะขึ้นด้วยตัวพิมพ์เล็ก เช่น 

father(X,Y) :- parent(X,Y), male(X).

หมายความว่า "ถ้าคนหนึ่งเป็นพ่อแม่ของอีกคนหนึ่งและเป็นผู้ชายแล้วคนนั้นจะเป็นพ่อ" (ใช้ "," แทน "และ") ลำดับการเขียนส่วนเหตุและผลจะตรงข้ามกับตรรกศาสตร์ทั่วไป แต่ก็สามารถเขียนส่วนผลหลาย ๆ ตัวในกฎเดียวกันได้ เช่น 

a,b,c :- d.

จะเหมือนกับการเขียนกฎสามข้อ 

a :- d.
b :- d.
c :- d.

แต่โปรล็อกไม่อนุญาตให้เขียนกฎว่า 

a;b :- c.

ซึ่งแปลว่า "ถ้า c แล้ว a หรือ b" (ใช้ ";" แทน "หรือ") เพราะเป็นข้อจำกัดของอนุประโยคของฮอร์น

การประเมินค่า แก้

เมื่อส่วนแปลคำสั่งของภาษาโปรล็อกได้รับการสอบถาม ก็จะค้นหาข้อเท็จจริงที่เข้ากันได้กับการสอบถามนั้น ถ้าไม่มีข้อเท็จจริงอยู่ ก็จะลองตรวจสอบกฎที่ทำให้ได้ข้อเท็จจริง เช่น 

sibling(X,Y) :- parent(Z,X), parent(Z,Y).
father(X,Y) :- parent(X,Y), male(X).
mother(X,Y) :- parent(X,Y), female(X).
parent(X,Y) :- father(X,Y).
parent(X,Y) :- mother(X,Y).
mother(trude, sally).
father(tom, sally).
father(tom, erica).
father(mike, tom).
male(tom).
female(trude).
male(mike).

เมื่อสอบถามตามตัวอย่างต่อไป ก็จะได้ว่าจริง 

 ?- sibling(sally, erica).
      yes.

โปรแกรมจะหาคำตอบนี้เทียบกับกฎ sibling(X,Y) โดยเชื่อม (อย่างไม่เป็นทางการ คือ แทนที่) sally กับ X และ erica กับ Y และทำให้การสอบถามขยายไปยัง parent(Z,sally) และ parent(Z,erica) จากนั้นจึงหาพ่อแม่ทั้งหมดของ sally แต่ว่า parent(trude,sally) ใช้ไม่ได้ เพราะเมื่อแทน Z ด้วย trude จะได้ parent(trude,erica) แต่ไม่มีข้อเท็จจริงนี้อยู่ ระบบจึงลองแทน Z ด้วย tom จึงได้ว่า sally เป็นพี่น้องกับ erica

คำสั่งต่อไป 

mother(X,Y) :- parent(X,Y), female(X).
parent(X,Y) :- father(X,Y).

ดูน่าสงสัย เพราะพ่อแม่ทุกคนไม่ได้เป็นพ่อ แต่พ่อเป็นพ่อแม่จริง และแม่คือพ่อแม่ที่เป็นผู้หญิง

ถ้าจะบอกว่าพ่อทุกคนเป็นผู้ชาย ก็จะเขียนได้ว่า 

male(X) :- father(X,_).

โดยไม่ต้องสนใจว่าลูกจะเป็นใคร จึงใช้ตัวแปรนิรนามซึ่งเขียนด้วยเส้นใต้อักษร

นิเสธ แก้

การสอบถามจะเป็นเท็จ เมื่อไม่สามารถหาข้อเท็จจริงหรือกฎที่สนับสนุนการสอบถามนั้นได้ ลักษณะแบบนี้เรียกว่า ข้อสมมุติโลกปิด (Closed world assumption) ซึ่งก็คือสมมุติว่าทุกสิ่งที่ควรจะรู้เก็บไว้ในฐานข้อมูลแล้ว ดังนั้นจึงไม่มีสิ่งใดที่อยู่ภายนอกขอบเขตนี้รวมถึงสิ่งที่ไม่รู้ หรืออีกนัยหนึ่ง ข้อเท็จจริงที่ยังไม่รู้ว่าเป็นจริง (หรือเท็จ) จะสมมุติว่าเป็นเท็จ

ดังนั้นกฎเช่น 

legal(X) :- NOT illegal(X).

จะหาค่าโดยค้นหาทุกสิ่งที่เป็น illegal และเปรียบเทียบกับ X ถ้าไม่พบ X ก็จะถือว่า X เป็น legal จะเรียกวิธีการนี้ว่า นิเสธโดยความขัดข้อง (Negation by failure)

การดำเนินการ แก้

เนื่องจากภาษาโปรล็อกเป็นภาษาเชิงตรรกะ ดังนั้นในทางทฤษฎีแล้วจึงไม่จำเป็นต้องสนใจว่าโปรแกรมทำงานยังไง แต่การศึกษาการทำงานหรือขั้นตอนวิธีที่ใช้อนุมาณ จะช่วยป้องกันโปรแกรมที่ไม่ให้ทำงานเกินจำเป็น

ตัวอย่างเช่น สามารถเขียนคำสั่งเพื่อนับจำนวนสมาชิกของลิสต์ได้ คือ 

elems([],0).
elems([H|T], X) :- elems(T, Y), X is Y + 1.

ถ้าจะอธิบายง่ายๆ ก็จะได้ว่า ลิสต์ว่าง จะมีจำนวนสมาชิกเท่ากับ 0 ถ้าลิสต์ไม่ว่าง จะได้จำนวนสมาชิกเท่ากับ Y+1 เมื่อ Y คือจำนวนสมาชิกส่วนที่เหลือเมื่อแยกส่วนหัวออก

กรณีนี้แยกกรณีของส่วนเงื่อนไขของกฎออกจากกันได้ชัดเจน แต่ถ้าเป็นกรณีตัดสินใจว่าจะเล่นพนันหรือไม่ 

gamble(X) :- gotmoney(X).
gamble(X) :- gotcredit(X), NOT gotmoney(X).

ถ้ามีเงิน ก็จะเล่นพนันต่อ ถ้าไม่มีเงินแล้วก็ต้องกู้เงิน หรือถ้าเกิดวงเงินก็จะไม่เล่นต่อ gotmoney อาจจะเป็นเพรดิเคตที่ใช้เวลานานมาก เช่น อาจจะต้องต่อผ่านอินเทอร์เน็ตไปเช็คจำนวนเงินในบัญชีธนาคาร ซึ่ง gotcredit ก็ใช้เวลานานเช่นเดียวกัน

ตามทฤษฎีแล้ว ระบบโปรล็อกอาจจะพิจารณากฎไม่เป็นไปตามลำดับ ดังนั้นจึงสามารถเขียนกฎกลับกันเป็น 

gamble(X) :- gotcredit(X), NOT gotmoney(X).
gamble(X) :- gotmoney(X).

ซึ่งเป็นสิ่งที่ได้ เนื่องจากเงื่อนไขทั้งสองแยกจากกัน แต่จะไม่จำเป็นต้องเช็คว่าจะกู้เงินได้หรือเปล่าเลย ถ้ารู้ว่ามียังมีเงินอยู่ ดังนั้นในทางปฏิบัติ ระบบโปรล็อกจะตรวจสอบกฎทั้งหมดก่อน และสามารถใช้ตัวตัด (cut operator -- ใช้เครื่องหมาย !) เพื่อบอกให้ตัวแปลคำสั่งหยุดหาตัวเลือกอื่นๆ หลังจากได้คำตอบแรกแล้ว เช่น 

gamble(X) :- gotmoney(X),!.
gamble(X) :- gotcredit(X), NOT gotmoney(X).

อย่างนี้เรียกว่าตัวตัดเขียว (green cut operator) ซึ่งจะบอกให้ตัวแปลคำสั่งหยุดหาตัวเลือกอื่นหลังจากตัวตัด ในกรณีที่ต้องการเงินจึงจะตรวจสอบกฎข้อที่สอง และจะพบว่า gotmoney ในกฎข้อที่สองไม่มีประโยชน์ เพราะรู้อยู่แล้วว่าไม่มีเงิน และระบบก็ไม่ตรวจสอบกฎข้อสองก่อน ดังนั้นจึงเขียนคำสั่งใหม่ได้ว่า 

gamble(X) :- gotmoney(X),!.
gamble(X) :- gotcredit(X).

อย่างนี้เรียกว่าตัวตัดแดง (red cut operator) เนื่องจากค่อนข้างอันตราย เพราะความถูกต้องจะขึ้นกับตำแหน่งที่ใช้ตัวตัดและลำดับของกฎ การตัดแปะที่ผิดพลาดอาจจะทำให้เกิดปัญหาได้ ถ้ากฎสลับกันก็จะกลายเป็นว่าจะกู้เงินเต็มที่ก่อน แล้วค่อยใช้เงินสดที่มีอยู่

อินเตอร์พรีตเตอร์โปรล็อก แก้

ส่วนขยาย แก้

  • OW Prolog ได้รับการพัฒนาขึ้น เพื่อเสริมสิ่งที่โปรล็อกขาดในด้านกราฟิกและการติดต่อ

อ้างอิง แก้

หนังสืออ่านเพิ่มเติม แก้

  • Leon Sterling and Ehud Shapiro (1994), "The Art of Prolog: Advanced Programming Techniques", (2nd Edition), The MIT Press, Massachusetts, ISBN 0-262-19338-8
  • Françis Giannesini et al. (1986), "PROLOG", Addison-Wesley, U.K., ISBN 0-201-12911-6
เข้าถึงจาก "https://th.wikipedia.org/w/index.php?title=ภาษาโปรล็อก&oldid=11184511"