Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
บทความนี้อาจขยายความได้โดยการแปลบทความที่ตรงกันในภาษาอังกฤษ คลิกที่ [ขยาย] เพื่อศึกษาแนวทางการแปล
|
ภาษาโปรล็อก (อังกฤษ: 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) คือ
- อะตอม [] ใช้แทนลิสต์ว่าง
- ถ้า 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) เนื่องจากค่อนข้างอันตราย เพราะความถูกต้องจะขึ้นกับตำแหน่งที่ใช้ตัวตัดและลำดับของกฎ การตัดแปะที่ผิดพลาดอาจจะทำให้เกิดปัญหาได้ ถ้ากฎสลับกันก็จะกลายเป็นว่าจะกู้เงินเต็มที่ก่อน แล้วค่อยใช้เงินสดที่มีอยู่
อินเตอร์พรีตเตอร์โปรล็อก
- Turbo Prolog โดย บอร์แลนด์, ปัจจุบันโดย PDC (http://www.visual-prolog.com/ 2022-04-13 ที่ เวย์แบ็กแมชชีน)
- Open Prolog (http://www.cs.tcd.ie/open-prolog/)
- Ciao Prolog (http://www.clip.dia.fi.upm.es/Software/Ciao)
- GNU Prolog (http://gnu-prolog.inria.fr 2011-08-14 ที่ เวย์แบ็กแมชชีน)
- YAP Prolog (http://www.ncc.up.pt/~vsc/Yap 2004-07-06 ที่ เวย์แบ็กแมชชีน)
- SWI Prolog (http://www.swi-prolog.org)
- Visual Prolog (http://www.visual-prolog.com 2022-04-13 ที่ เวย์แบ็กแมชชีน)
- SICStus Prolog (http://www.sics.se/sicstus/)
- Amzi! Prolog (http://www.amzi.com/)
- B-Prolog (http://www.probp.com/)
- TuProlog (http://tuprolog.sourceforge.net/)
- XSB (http://xsb.sourceforge.net/)
- Trinc Prolog (http://www.trinc-prolog.com)
- Strawberry Prolog (http://www.dobrev.com/)
ส่วนขยาย
- ได้รับการพัฒนาขึ้น เพื่อเสริมสิ่งที่โปรล็อกขาดในด้านกราฟิกและการติดต่อ
อ้างอิง
- Runnable examples
- A prolog interpreter that runs in the browser
- Prolog: The ISO standard
- Visual Prolog 2022-04-13 ที่ เวย์แบ็กแมชชีน: An evolution of Turbo Prolog developed by at Denmark.
- Prolog Tutorial 2004-12-04 ที่ เวย์แบ็กแมชชีน
- Learn Prolog Now! 2007-08-26 ที่ เวย์แบ็กแมชชีน
หนังสืออ่านเพิ่มเติม
- Leon Sterling and Ehud Shapiro (1994), "The Art of Prolog: Advanced Programming Techniques", (2nd Edition), The MIT Press, Massachusetts,
- Françis Giannesini et al. (1986), "PROLOG", Addison-Wesley, U.K.,
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
lingkkhamphasa inbthkhwamni miiwihphuxanaelaphurwmaekikhbthkhwamsuksaephimetimodysadwk enuxngcakwikiphiediyphasaithyyngimmibthkhwamdngklaw krann khwrribsrangepnbthkhwamodyerwthisudbthkhwamnixackhyaykhwamidodykaraeplbthkhwamthitrngkninphasaxngkvs khlikthi khyay ephuxsuksaaenwthangkaraeplkhunsamarthdu karaepldwykhxmphiwetxrcakbthkhwaminphasaxngkvs ekhruxngmuxchwyaeplxyang diphaexl hrux kuekilthranselth epncuderimtnthidisahrbkaraepl xyangirktam phuaeplcatxngtrwcsxbkhxphidphladcakkaraepldwykhxmphiwetxraelayunynwakaraeplnnthuktxng erakhxptiesthenuxhathikhdlxkcakekhruxngmuxaeplthiimmikartrwcthankxnephyaephr krunaxyaaeplswnkhxngkhxkhwamthiduaelwechuxthuximidhruxmikhunphaphta thaepnipid oprdchwyyunyndwykartrwcsxbaehlngxangxingthipraktinbthkhwamphasann oprdrabuiwinkhwamyxkaraekikhwakhunaeplenuxhamacakphasaid khunkhwrephimaemaebb Translated en Prolog iwinhnaphudkhuy sahrbkhaaenanaaelaaenwthangephimetim oprdsuksaidthi wikiphiediy karaepl phasaoprlxk xngkvs Prolog epnphasasahrbkarekhiynopraekrmechingtrrka idchuxmacak PROgrammation en LOGique logic programming srangkhunody Alain Colmerauer raw kh s 1972 phasaoprlxkekidcakkhwamphyayamthicasrangphasathixasywithikarthangtrrksastraethnthicakahndkhasngxyanglaexiydihkbkhxmphiwetxr phasaoprlxkthuknaipichinopraekrmsahrbpyyapradisth aelaphasasastrechingkhanwn computational linguistics odyechphaakarpramwlphlphasathrrmchati iwyakrnaelakhwamhmaykhxngphasanneriybngayaelachdecn epahmayaerkkhxngphasakhuxepnekhruxngmuxsahrbnkphasasastrthiimrukhxmphiwetxr nganwicycanwnmakthithaihekidkarphthnaphasaoprlxkinpccubnnn epnphlmacakokhrngkarrabbkhxmphiwetxryukhthiha fifth generation computer systems project FGCS sungeluxkrupaebbhnungkhxngphasaoprlxkepnphasaaekn Kernel Language khxngrabbptibtikar phasaoprlxkmiphunthanmacak predicate calculus hruxeriyketm wa first order predicate calculus odycakdihichechphaa Horn clause kardaeninkarkhxngopraekrmoprlxk kkhuxkarprayuktwithiphisucnthvsdibthodyich first order resolution aenwkhidphunthanthiekiywkhxngidaek unification tail recursion backtracking aebbchnidkhxmulphasaoprlxkimmiaebbchnidkhxmulehmuxnkbphasaopraekrmthw ip hwkhxnicaphudthungsphthkhxngswnyxykhxngphasaaethn xatxm xatxm atom khux khakhngthisungekhiynaethndwykhxkhwam odyxatxmkhuxladbthiprakxbdwy twxksr twelkh esnitxkkhra underscores aelacatxngkhuntndwytwphimphelk odypktiaelwthatxngkarxatxmthiichekhruxnghmayphiess caekhiynekhruxnghmayxyprakasediyw kakbiw echn epn xatxm aet epntwdaeninkar twelkh rabbphasaoprlxkswnihycaimaebngaeykrahwangelkhcanwnetm kbelkhcanwncring twaepr twaeprcaaesdngdwysayxkkhrathiprakxbdwy twxksr twelkh aelaesnitxksr odycatxngkhuntndwytwphimphihy twaeprinphasaoprlxkimichthiekbkhxmul aetcamilksnakhlayrupaebb pattern sungkahndiwineruxng twaeprnirnam anonymous variable caekhiynodyich ekhruxnghmayesnitxksrephiyngtwediyw phcn phcn term ichaethnkhxmulthimikhwamsbsxn prakxbdwy swnhw head epnxatxm eriykwa fngketxr functor aelapharamietxrtang imkahndpraephth canwnpharamietxrcaeriykwa xaridi arity phcnsamarthekhiynaethnodyichephiyngswnhwaelaxaridi odyekhiynepn fngketxr xariti list listimichkhxmulaebbediyw aetepnokhrngsrangthiniyamaebberiyksa odyichphcn 2 khux xatxm ichaethnlistwang tha T epnlist aela H epnswnyxy caichphcn H T aethnlist swnyxyaerk eriykwaswnhw H catamdwyswnthiehluxkhxnglist thieriykwaswnhang T hrux tail echn list 1 2 3 caekhiynaethndwy 1 2 3 tamiwyakrnkhxngphasaaelwxaccaekhiynlistwa H T withiniepnthiniymmakkwakarich karpramwlphlkhxmulinlist cathaodypramwlphlkhxmulswnhwkxn aelwkhxythaswnthiehlux odyichkareriyksa listsamarthekhiynidhlayaebb tamkhwamsadwkkhxngopraekrmemxr ekhiynswnyxythuktw abc 1 f x Y g A rst ekhiynswnaerktwediyw abc L1 ekhiynswnaerkhlaytw abc 1 f x L2 ekhiynepnkarkhyaykhxngphcn abc 1 f x Y g A rst inkarichngancring listkhxngoprlxkmilksnakhlaykb dkithpping khxngphasasmyihmodythwip hruxxacklawidwa dkithppingidnaexawithikarkhxngoprlxkipichenuxngcak phasaoprlxk nnekidmakxnphasaehlann sayxkkhra sayxkkhracaekhiynxyuinekhruxnghmayxyprakaskhu sungphayincaaethndwylistkhxngrhsaexskikhxethccringkarekhiynopraekrmphasaoprlxknn caaetktangcakkarichphasaechingkrabwnkhasng procedural langugage odyerimcakkarsrangthankhxmulkhxethccring facts aela kd rules caknncungichkarsxbtham queries ephuxhakhatxb hnwyphunthankhxngphasaoprlxkkhux predicate sungichniyamkhwamcring ephrdiekhtcaekhiynxyuinrupphcn sungprakxbdwyswnhw aelaxarkiwemnt echn cat tom cat khuxswnhw aelamixarkiwemnthnungtwkhux tom caknncasamarthsxbthamoprlxkthungkhwamcringniid cat tom yes cat X X tom no odythwip caichephrdiekhtniyamkhwamcringekiywkbsingthiopraekrmru aetkarichephrdiekhtktxngxasykhxtklngthiaennxn xyangephrditekhtintwxyangkhanglang caichaebbihn ephuxbxkwa Pat epnphxkhxng Sally father sally pat father pat sally thngsxngkrnimiswnhwkhux father aelaxarkiwemntkhux pat aela sally krniaerk sally makxn swnkrnihlng pat makxn krniaerkepntwxyangkhxngkarniyamaebb kriya prathan krrm swnkrnihlngcaepnaebb kriya krrm prathan enuxngcakrabboprlxkimekhaikhphasaxngkvs dngnncungsamarthichidthngsxngaebb aetkhwrcakahndrupaebbthiaennxninopraekrmediywkn aelakhwrhlikeliyngkarekhiyn echn father pat sally father jessica james miephrdiekhthlaytw thikahndiwintwphasa ephuxthaihopraekrmsamarththangantang id echn xinphut exatphut ichkrafik aelasingtang ephuxtidtxkbrabbptibtikar echn ephrdiekht write ichsahrbaesdngphlxxkcx write Hello caaesdngkhawa Hello bncxkdkhasngxikrupaebbhnungkhxngphasaoprlxkkhux kd rules echn light on switch on ekhruxnghmay aeplwa tha kdnihmaykhwamwa light on epncring tha switch on epncring nxkcaknisamarthichtwaeprinkdid odytwaeprcakhuntndwytwphimphihy swnkhakhngthicakhundwytwphimphelk echn father X Y parent X Y male X hmaykhwamwa thakhnhnungepnphxaemkhxngxikkhnhnungaelaepnphuchayaelwkhnnncaepnphx ich aethn aela ladbkarekhiynswnehtuaelaphlcatrngkhamkbtrrksastrthwip aetksamarthekhiynswnphlhlay twinkdediywknid echn a b c d caehmuxnkbkarekhiynkdsamkhx a d b d c d aetoprlxkimxnuyatihekhiynkdwa a b c sungaeplwa tha c aelw a hrux b ich aethn hrux ephraaepnkhxcakdkhxngkarpraeminkhaemuxswnaeplkhasngkhxngphasaoprlxkidrbkarsxbtham kcakhnhakhxethccringthiekhaknidkbkarsxbthamnn thaimmikhxethccringxyu kcalxngtrwcsxbkdthithaihidkhxethccring echn 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 emuxsxbthamtamtwxyangtxip kcaidwacring sibling sally erica yes opraekrmcahakhatxbniethiybkbkd sibling X Y odyechuxm xyangimepnthangkar khux aethnthi sally kb X aela erica kb Y aelathaihkarsxbthamkhyayipyng parent Z sally aela parent Z erica caknncunghaphxaemthnghmdkhxng sally aetwa parent trude sally ichimid ephraaemuxaethn Z dwy trude caid parent trude erica aetimmikhxethccringnixyu rabbcunglxngaethn Z dwy tom cungidwa sally epnphinxngkb erica khasngtxip mother X Y parent X Y female X parent X Y father X Y dunasngsy ephraaphxaemthukkhnimidepnphx aetphxepnphxaemcring aelaaemkhuxphxaemthiepnphuhying thacabxkwaphxthukkhnepnphuchay kcaekhiynidwa male X father X odyimtxngsnicwalukcaepnikhr cungichtwaeprnirnamsungekhiyndwyesnitxksr niesth karsxbthamcaepnethc emuximsamarthhakhxethccringhruxkdthisnbsnunkarsxbthamnnid lksnaaebbnieriykwa khxsmmutiolkpid Closed world assumption sungkkhuxsmmutiwathuksingthikhwrcaruekbiwinthankhxmulaelw dngnncungimmisingidthixyuphaynxkkhxbekhtnirwmthungsingthiimru hruxxiknyhnung khxethccringthiyngimruwaepncring hruxethc casmmutiwaepnethc dngnnkdechn legal X NOT illegal X cahakhaodykhnhathuksingthiepn illegal aelaepriybethiybkb X thaimphb X kcathuxwa X epn legal caeriykwithikarniwa Negation by failure kardaeninkarenuxngcakphasaoprlxkepnphasaechingtrrka dngnninthangthvsdiaelwcungimcaepntxngsnicwaopraekrmthanganynging aetkarsuksakarthanganhruxkhntxnwithithiichxnuman cachwypxngknopraekrmthiimihthanganekincaepn twxyangechn samarthekhiynkhasngephuxnbcanwnsmachikkhxnglistid khux elems 0 elems H T X elems T Y X is Y 1 thacaxthibayngay kcaidwa listwang camicanwnsmachikethakb 0 thalistimwang caidcanwnsmachikethakb Y 1 emux Y khuxcanwnsmachikswnthiehluxemuxaeykswnhwxxk krniniaeykkrnikhxngswnenguxnikhkhxngkdxxkcakknidchdecn aetthaepnkrnitdsinicwacaelnphnnhruxim gamble X gotmoney X gamble X gotcredit X NOT gotmoney X thamiengin kcaelnphnntx thaimmienginaelwktxngkuengin hruxthaekidwngenginkcaimelntx gotmoney xaccaepnephrdiekhtthiichewlananmak echn xaccatxngtxphanxinethxrentipechkhcanwnengininbychithnakhar sung gotcredit kichewlananechnediywkn tamthvsdiaelw rabboprlxkxaccaphicarnakdimepniptamladb dngnncungsamarthekhiynkdklbknepn gamble X gotcredit X NOT gotmoney X gamble X gotmoney X sungepnsingthiid enuxngcakenguxnikhthngsxngaeykcakkn aetcaimcaepntxngechkhwacakuenginidhruxeplaely tharuwamiyngmienginxyu dngnninthangptibti rabboprlxkcatrwcsxbkdthnghmdkxn aelasamarthichtwtd cut operator ichekhruxnghmay ephuxbxkihtwaeplkhasnghyudhatweluxkxun hlngcakidkhatxbaerkaelw echn gamble X gotmoney X gamble X gotcredit X NOT gotmoney X xyangnieriykwatwtdekhiyw green cut operator sungcabxkihtwaeplkhasnghyudhatweluxkxunhlngcaktwtd inkrnithitxngkarengincungcatrwcsxbkdkhxthisxng aelacaphbwa gotmoney inkdkhxthisxngimmipraoychn ephraaruxyuaelwwaimmiengin aelarabbkimtrwcsxbkdkhxsxngkxn dngnncungekhiynkhasngihmidwa gamble X gotmoney X gamble X gotcredit X xyangnieriykwatwtdaedng red cut operator enuxngcakkhxnkhangxntray ephraakhwamthuktxngcakhunkbtaaehnngthiichtwtdaelaladbkhxngkd kartdaepathiphidphladxaccathaihekidpyhaid thakdslbknkcaklayepnwacakuenginetmthikxn aelwkhxyichenginsdthimixyuxinetxrphritetxroprlxkTurbo Prolog ody bxraelnd pccubnody PDC http www visual prolog com 2022 04 13 thi ewyaebkaemchchin Open Prolog http www cs tcd ie open prolog Ciao Prolog http www clip dia fi upm es Software Ciao GNU Prolog http gnu prolog inria fr 2011 08 14 thi ewyaebkaemchchin YAP Prolog http www ncc up pt vsc Yap 2004 07 06 thi ewyaebkaemchchin SWI Prolog http www swi prolog org Visual Prolog http www visual prolog com 2022 04 13 thi ewyaebkaemchchin SICStus Prolog http www sics se sicstus Amzi Prolog http www amzi com B Prolog http www probp com TuProlog http tuprolog sourceforge net XSB http xsb sourceforge net Trinc Prolog http www trinc prolog com Strawberry Prolog http www dobrev com swnkhyayidrbkarphthnakhun ephuxesrimsingthioprlxkkhadindankrafikaelakartidtxxangxingRunnable examples A prolog interpreter that runs in the browser Prolog The ISO standard Visual Prolog 2022 04 13 thi ewyaebkaemchchin An evolution of Turbo Prolog developed by at Denmark Prolog Tutorial 2004 12 04 thi ewyaebkaemchchin Learn Prolog Now 2007 08 26 thi ewyaebkaemchchinhnngsuxxanephimetimLeon Sterling and Ehud Shapiro 1994 The Art of Prolog Advanced Programming Techniques 2nd Edition The MIT Press Massachusetts ISBN 0 262 19338 8 Francis Giannesini et al 1986 PROLOG Addison Wesley U K ISBN 0 201 12911 6