ความหมาย (ภาษาโปรแกรม)

ในทฤษฎีภาษาโปรแกรมความหมายคือการศึกษาตรรกะทางคณิตศาสตร์ที่เข้มงวดเกี่ยวกับความหมายของภาษาโปรแกรม [ ^{1 ] ความ}หมายจะกำหนดความหมายเชิงคำนวณ ให้กับ สตริง ที่ถูกต้อง ในไวยากรณ์ของภาษาโปรแกรมมันมีความเกี่ยวข้องอย่างใกล้ชิดกับ และมักจะทับซ้อนกับความหมายของการพิสูจน์ทางคณิตศาสตร์

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

ประวัติศาสตร์

ในปี พ.ศ. 2510 Robert W. Floydได้ตีพิมพ์บทความเรื่องAssigning meanings to programsโดยมีเป้าหมายหลักคือ "มาตรฐานที่เข้มงวดสำหรับการพิสูจน์เกี่ยวกับโปรแกรมคอมพิวเตอร์ รวมถึงการพิสูจน์ความถูกต้องความเท่าเทียมกัน และการสิ้นสุด" ^{[ 2 ]}^{[ 3 ]} Floyd ยังเขียนเพิ่มเติมอีกว่า: ^{[ 2 ]}

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

ในปี พ.ศ. 2512 โทนี่ โฮร์ได้ตีพิมพ์บทความเกี่ยวกับตรรกะของโฮร์ซึ่งมีพื้นฐานมาจากแนวคิดของฟลอยด์ ปัจจุบันบางครั้งเรียกรวมกันว่าอรรถศาสตร์เชิงสัจพจน์^{[ 4 ]}^{[ 5 ]}

ในทศวรรษ 1970 คำว่าความหมายเชิงปฏิบัติการและความหมายเชิงความหมายได้เกิดขึ้น^{[ 5 ]}

ภาพรวม

สาขาวิชาอรรถศาสตร์เชิงรูปธรรมครอบคลุมสิ่งต่อไปนี้ทั้งหมด:

นิยามของแบบจำลองเชิงความหมาย
ความสัมพันธ์ระหว่างแบบจำลองความหมายต่างๆ
ความสัมพันธ์ระหว่างแนวทางต่างๆ ในการทำความเข้าใจความหมาย
ความสัมพันธ์ระหว่างการคำนวณและโครงสร้างทางคณิตศาสตร์พื้นฐานจากสาขาต่างๆ เช่นตรรกศาสตร์ทฤษฎีเซตทฤษฎีแบบจำลองทฤษฎีหมวดหมู่เป็นต้น

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

แนวทาง

มีวิธีการวิเคราะห์ความหมายเชิงรูปธรรมอยู่หลายวิธี ซึ่งแบ่งออกเป็น 3 ประเภทหลัก ได้แก่:

ความหมายเชิงสัญลักษณ์^{[ 6 ]}โดยที่แต่ละวลีในภาษาจะถูกตีความว่าเป็นสัญลักษณ์ กล่าวคือ ความหมายเชิงแนวคิดที่สามารถคิดได้ในเชิงนามธรรม สัญลักษณ์ดังกล่าวมักจะเป็นวัตถุทางคณิตศาสตร์ที่อยู่ในพื้นที่ทางคณิตศาสตร์ แต่ไม่จำเป็นต้องเป็นเช่นนั้นเสมอไป ในทางปฏิบัติ สัญลักษณ์จะถูกอธิบายโดยใช้สัญลักษณ์ทางคณิตศาสตร์บางรูปแบบ ซึ่งสามารถทำให้เป็นทางการได้ในภาษาเมตาเชิงสัญลักษณ์ ตัวอย่างเช่น ความหมายเชิงสัญลักษณ์ของภาษาฟังก์ชันมักจะแปลภาษาไปเป็นทฤษฎีโดเมนคำอธิบายความหมายเชิงสัญลักษณ์ยังสามารถทำหน้าที่เป็นการแปลแบบองค์ประกอบจากภาษาโปรแกรมไปเป็นภาษาเมตาเชิงสัญลักษณ์ และใช้เป็นพื้นฐานในการออกแบบคอมไพเลอร์
ความหมายเชิงปฏิบัติการ [⁷^]ซึ่งการดำเนินการของภาษาจะถูกอธิบายโดยตรง (แทนที่จะผ่านการแปล) ความหมายเชิงปฏิบัติการสอดคล้องกับการตีความ อย่างหลวม ^ๆแม้ว่า "ภาษาการใช้งาน" ของตัวตีความโดยทั่วไปจะเป็นรูปแบบทางคณิตศาสตร์ก็ตาม ความหมายเชิงปฏิบัติการอาจกำหนดเครื่องจักรนามธรรม (เช่นเครื่องจักร SECD ) และให้ความหมายแก่วลีโดยการอธิบายการเปลี่ยนผ่านที่เกิดขึ้นกับสถานะของเครื่องจักร หรืออีกทางหนึ่ง เช่นเดียวกับแคลคูลัสแลมบ์ดา บริสุทธิ์ ความหมายเชิงปฏิบัติการสามารถกำหนดได้ผ่านการแปลงทางไวยากรณ์บนวลีของภาษาเอง
ความหมายเชิงสัจพจน์ [⁸^]ซึ่งให้ความหมายแก่วลีโดยการอธิบายสัจพจน์ ที่ใช้กับวลีเหล่านั้น ความหมายเชิงสัจพจน์ไม่แยกความแตกต่างระหว่างความ ^หมายของวลีกับสูตรตรรกะที่อธิบายวลีนั้น ความหมายของวลีคือสิ่งที่สามารถพิสูจน์ได้ในตรรกะบางอย่าง ตัวอย่างที่เป็นแบบอย่างของความหมายเชิงสัจพจน์คือตรรกะของ Hoare

นอกเหนือจากการเลือกใช้แนวทางเชิงความหมาย เชิงปฏิบัติ หรือเชิงสัจพจน์แล้ว ความแตกต่างส่วนใหญ่ในระบบความหมายเชิงรูปธรรมนั้นเกิดจากการเลือกใช้รูปแบบทางคณิตศาสตร์ที่รองรับ

การเปลี่ยนแปลง

รูปแบบต่างๆ ของความหมายเชิงรูปธรรมมีดังต่อไปนี้:

ความหมายของการกระทำ^{[ 9 ]}เป็นแนวทางที่พยายามแบ่งความหมายของการกำหนดความหมายออกเป็นโมดูล โดยแบ่งกระบวนการกำหนดรูปแบบออกเป็นสองชั้น (ความหมายระดับมหภาคและระดับจุลภาค) และกำหนดเอนทิตีความหมายสามรายการล่วงหน้า (การกระทำ ข้อมูล และตัวให้ผลผลิต) เพื่อลดความซับซ้อนของข้อกำหนด
ความหมายเชิงพีชคณิต^{[ 8 ]}เป็นรูปแบบหนึ่งของความหมายเชิงสัจพจน์ที่อิงตามกฎพีชคณิต สำหรับการอธิบายและการให้เหตุผลเกี่ยวกับ ความหมายของโปรแกรมใน ลักษณะ ที่เป็นทางการนอกจากนี้ยังสนับสนุนความหมายเชิงสัญลักษณ์และความหมายเชิงปฏิบัติการด้วย
ไวยากรณ์แอตทริบิวต์^{[ 10 ]}กำหนดระบบที่คำนวณ "เมตาเดตา " (เรียกว่าแอตทริบิวต์ ) อย่างเป็นระบบสำหรับกรณีต่างๆ ของไวยากรณ์ของภาษา ไวยากรณ์แอตทริบิวต์สามารถเข้าใจได้ว่าเป็นความหมายเชิงสัญลักษณ์ โดยที่ภาษาเป้าหมายเป็นเพียงภาษาดั้งเดิมที่เสริมด้วยคำอธิบายแอตทริบิวต์ นอกเหนือจากความหมายเชิงรูปธรรมแล้ว ไวยากรณ์แอตทริบิวต์ยังถูกใช้สำหรับการสร้างโค้ดในคอมไพเลอร์และเพื่อเสริม ไวยากรณ์ ปกติหรือไวยากรณ์แบบไร้บริบทด้วยเงื่อนไขที่ไวต่อบริบท
ความหมายเชิง หมวดหมู่ (หรือ "เชิงฟังก์ชัน") ^{[ 11 ]}ใช้ทฤษฎีหมวดหมู่เป็นรูปแบบทางคณิตศาสตร์หลัก ความหมายเชิงหมวดหมู่มักได้รับการพิสูจน์แล้วว่าสอดคล้องกับความหมายเชิงสัจพจน์บางอย่างที่ให้การนำเสนอเชิงไวยากรณ์ของโครงสร้างเชิงหมวดหมู่ นอกจากนี้ ความหมายเชิงสัญลักษณ์มักเป็นตัวอย่างของความหมายเชิงหมวดหมู่ทั่วไป^{[ 12 ]}
ความหมายของการทำงานพร้อมกัน^{[ 13 ]}เป็นคำที่ครอบคลุมความหมายเชิงรูปธรรมใดๆ ที่อธิบายการคำนวณพร้อมกัน รูปแบบการทำงานพร้อมกันที่มีความสำคัญทางประวัติศาสตร์ ได้แก่โมเดลแอคเตอร์และแคลคูลัสกระบวนการ
ความหมายของเกม^{[ 14 ]}ใช้คำอุปมาที่ได้รับแรงบันดาลใจจากทฤษฎีเกม
ความหมายของตัวแปลงภาคแสดง^{[ 15 ]}ซึ่งพัฒนาโดย Edsger W. Dijkstraอธิบายความหมายของส่วนย่อยของโปรแกรมว่าเป็นฟังก์ชันที่แปลงเงื่อนไขหลังเป็นเงื่อนไข ก่อน ที่จำเป็นในการสร้างเงื่อนไขนั้น

การอธิบายความสัมพันธ์

ด้วยเหตุผลหลายประการ เราอาจต้องการอธิบายความสัมพันธ์ระหว่างความหมายเชิงรูปธรรมที่แตกต่างกัน ตัวอย่างเช่น:

เพื่อพิสูจน์ว่าความหมายเชิงปฏิบัติการเฉพาะสำหรับภาษาหนึ่งนั้นสอดคล้องกับสูตรตรรกะของความหมายเชิงสัจพจน์สำหรับภาษานั้น การพิสูจน์เช่นนี้แสดงให้เห็นว่าการให้เหตุผลเกี่ยวกับกลยุทธ์การตีความ (เชิงปฏิบัติการ) เฉพาะโดยใช้ ระบบการพิสูจน์ (เชิงสัจพจน์) เฉพาะนั้น "สมเหตุสมผล"
เพื่อพิสูจน์ว่าความหมายเชิงปฏิบัติการบนเครื่องจักรระดับสูงมีความสัมพันธ์กันโดยการจำลองกับความหมายบนเครื่องจักรระดับต่ำ โดยที่เครื่องจักรนามธรรมระดับต่ำมีการดำเนินการพื้นฐานมากกว่าคำจำกัดความของเครื่องจักรนามธรรมระดับสูงของภาษาที่กำหนด การพิสูจน์ดังกล่าวแสดงให้เห็นว่าเครื่องจักรระดับต่ำ "ดำเนินการตาม" เครื่องจักรระดับสูงได้อย่างถูกต้อง

นอกจากนี้ ยังสามารถเชื่อมโยงความหมายหลายอย่างเข้าด้วยกันผ่านนามธรรมโดยอาศัยทฤษฎีการตีความเชิงนามธรรมได้อีก ด้วย

ดูเพิ่มเติม

อ่านเพิ่มเติม

ตำราเรียน

Floyd, Robert W. (1967). "การกำหนดความหมายให้กับโปรแกรม" (PDF)ใน Schwartz, JT (บรรณาธิการ). แง่มุมทางคณิตศาสตร์ของวิทยาศาสตร์คอมพิวเตอร์ รายงานการประชุม สัมมนาคณิตศาสตร์ประยุกต์ เล่มที่ 19 สมาคมคณิตศาสตร์อเมริกัน หน้า 19–32 ISBN 0821867288.
เฮนเนสซี, เอ็ม. (1990). ความหมายของภาษาโปรแกรม: บทนำเบื้องต้นโดยใช้ความหมายเชิงปฏิบัติการเชิงโครงสร้าง . ไวลีย์. ISBN 978-0-471-92772-3.
เทนเนนต์, โรเบิร์ต ดี. (1991). ความหมายของภาษาโปรแกรม . เพรนติส ฮอลล์. ISBN 978-0-13-805599-8.
กุนเทอร์, คาร์ล (1992). ความหมายของภาษาโปรแกรม . สำนักพิมพ์ MIT. ISBN 0-262-07143-6.
นีลสัน, เอชอาร์; นีลสัน, เฟลมมิง (1992). ความหมายเชิงประยุกต์: บทนำอย่างเป็นทางการ (PDF) . ไวลีย์. ISBN 978-0-471-92980-2เก็บถาวรจากต้นฉบับ(PDF)เมื่อวันที่ 17 เมษายน 2555 เรียกดูเมื่อวันที่ 27 พฤษภาคม 2554
วินสเกล, กลินน์ (1993). ความหมายเชิงรูปธรรมของภาษาโปรแกรม: บทนำ . สำนักพิมพ์ MIT. ISBN 0-262-73103-7.
มิตเชล, จอห์น ซี. (1995). พื้นฐานสำหรับภาษาโปรแกรม (โพสต์สคริปต์ )
Slonneger, Kenneth ; Kurtz, Barry L. (1995). ไวยากรณ์และความหมายเชิงรูปธรรมของภาษาโปรแกรม . Addison-Wesley. ISBN 0-201-65697-3.
เรย์โนลด์ส, จอห์น ซี. (1998). ทฤษฎีของภาษาโปรแกรม . สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์. ISBN 0-521-59414-6.
ฮาร์เปอร์, โรเบิร์ต (2006). พื้นฐานเชิงปฏิบัติสำหรับภาษาโปรแกรม (PDF) . เก็บถาวรจากต้นฉบับ(PDF)เมื่อ 27 มิถุนายน 2007(ฉบับร่าง)
นีลสัน, เอชอาร์; นีลสัน, เฟลมมิง (2007). ความหมายเชิงประยุกต์: บทนำ . สปริงเกอร์. ISBN 978-1-84628-692-6.
สตัมป์, แอรอน (2014). พื้นฐานของภาษาโปรแกรม . ไวลีย์. ISBN 978-1-118-00747-1.
Krishnamurthi, Shriram (2012). "ภาษาโปรแกรม: การประยุกต์ใช้และการตีความ" (ฉบับที่ 2)

บันทึกการบรรยาย

วินสเกล, กลินน์. "ความหมายเชิงสัญลักษณ์" (PDF) . มหาวิทยาลัยเคมบริดจ์.

ลิงก์ภายนอก

Aaby, Anthony (2004). บทนำสู่ภาษาโปรแกรม . เก็บถาวรจากต้นฉบับเมื่อ 2015-06-19.ความหมายของคำ

1 ] ความ

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

7

8

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]