วิกิพีเดียภาษาไทย
กลับไปหน้าบทความ

อ่าน 10 นาที

ทฤษฎีบทโปรแกรมเชิงโครงสร้าง

ใน ทฤษฎีภาษาการเขียนโปรแกรม ทฤษฎีบท โปรแกรมที่มีโครงสร้าง ซึ่งโดยทั่วไปเรียกว่า ทฤษฎีบท Böhm–Jacopini [ 1 ] [ 2 ] ระบุว่าคลาสของ กราฟควบคุมการไหล (ในอดีตเรียกว่า ผังงาน...

ทฤษฎีบทโปรแกรมเชิงโครงสร้าง

ในทฤษฎีภาษาการเขียนโปรแกรมทฤษฎีบทโปรแกรมที่มีโครงสร้างซึ่งโดยทั่วไปเรียกว่าทฤษฎีบท Böhm–Jacopini [ 1 ] [ 2 ]ระบุว่าคลาสของกราฟควบคุมการไหล (ในอดีตเรียกว่าผังงาน ในบริบทนี้) สามารถคำนวณ ฟังก์ชันที่คำนวณได้ใดๆ โดยใช้ โครงสร้างควบคุมสามแบบต่อไปนี้เพื่อรวมโปรแกรมย่อย ( คำสั่งและบล็อก ) เท่านั้น: [ 3 ]

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

คำจำกัดความที่ละเอียดกว่านี้มีอยู่ในหัวข้อถัดไป

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

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

การควบคุมการไหลของทฤษฎีโปรแกรมเชิงโครงสร้าง—ลำดับ การเลือก และการทำซ้ำ—แสดงด้วยแผนภาพ NS (สีน้ำเงิน) และผังงาน (สีเขียว)

ที่มาและรูปแบบต่างๆ

ในปี พ.ศ. 2507 Corrado Böhmได้กำหนด ภาษาการเขียนโปรแกรม ที่สมบูรณ์แบบ Turing อย่างง่าย ( P′′ ) โดยอาศัยลำดับและการวนซ้ำ [ 4 ] ในบทความต่อมา Böhm และGiuseppe Jacopiniได้กล่าวถึงผลลัพธ์นี้อีกครั้ง[ 5 ]

โดย ทั่วไปแล้ว ทฤษฎีบทโปรแกรมที่มีโครงสร้างมักได้รับการยกย่อง[ 6 ]ให้กับบทความปี 1966 นั้นHarelเขียนในปี 1980 ว่าบทความของ Böhm–Jacopini ได้รับ "ความนิยมอย่างกว้างขวาง" [ 6 ]โดยเฉพาะอย่างยิ่งกับผู้สนับสนุนการเขียนโปรแกรมที่มีโครงสร้าง Harel ยังตั้งข้อสังเกตอีกว่า "เนื่องจากรูปแบบทางเทคนิคที่ค่อนข้าง [บทความของ Böhm–Jacopini ปี 1966] ดูเหมือนจะถูกอ้างถึงบ่อยกว่าที่จะอ่านอย่างละเอียด" [ 6 ]และหลังจากตรวจสอบบทความจำนวนมากที่ตีพิมพ์จนถึงปี 1980 Harel โต้แย้งว่าเนื้อหาของการพิสูจน์ของ Böhm–Jacopini มักถูกนำเสนอผิดว่าเป็นทฤษฎีบทพื้นบ้าน ที่โดยพื้นฐานแล้วมีผลลัพธ์ที่ง่ายกว่า ซึ่งผลลัพธ์นั้นเองสามารถสืบย้อนไปถึงจุดเริ่มต้นของทฤษฎีการ คำนวณสมัยใหม่ในบทความของvon Neumann [ 7 ]และKleene [ 8 ]

Harel ยังเขียนอีก ว่า [ 6 ]ชื่อทั่วไปนี้ได้รับการเสนอโดยHD Millsในชื่อ "ทฤษฎีบทโครงสร้าง" ในช่วงต้นทศวรรษ 1970 [ 9 ]

วิวัฒนาการของทฤษฎีบทเป็นดังนี้

1. Böhm 1964 (การสร้างโปรแกรม/การคำนวณ)

ผลลัพธ์
ฟังก์ชันเรียกซ้ำบางส่วนทุก ฟังก์ชัน สามารถคำนวณได้ด้วยโปรแกรม[ 10 ]โดยใช้เพียงลำดับและการวนซ้ำ[ 4 ]
หมายเหตุ
ผลลัพธ์นี้มุ่งเน้นไปที่ การสร้างโปรแกรมไม่จำเป็นต้องมีการเลือก : พฤติกรรมตามเงื่อนไขจะถูกเข้ารหัสด้วยลูป P′′ป้องกันการไหลของการควบคุม ที่ไม่มีโครงสร้าง ผ่านการออกแบบภาษา บังคับใช้โครงสร้างที่แหล่งที่มา Böhm กล่าวถึงผลลัพธ์ของเขาอีกครั้งในส่วนที่ 2 ของ Böhm-Jacopini (1966) [ 5 ]

2. Böhm–Jacopini 1966 (การเปลี่ยนแปลงโปรแกรม)

ผลลัพธ์
ผังงานทุกผัง ( กราฟควบคุมการไหล , CFG) สามารถแปลงเป็นโปรแกรมที่มีโครงสร้างได้โดยใช้เพียงลำดับและการวนซ้ำเท่านั้น[ 5 ]
หมายเหตุ
ทฤษฎีบทเวอร์ชันนี้มุ่งเน้นไปที่การแปลง โปรแกรม โดยมีความเกี่ยวข้องกับการเพิ่มประสิทธิภาพคอมไพเลอร์ เป็นหลัก มากกว่าการตัดสินใจด้านการออกแบบซอฟต์แวร์ ในส่วนที่ 1 ของ Böhm–Jacopini (1966) Jacopini พิสูจน์ว่ากราฟควบคุมการไหล (CFG) ใดๆ [ 11 ] สามารถเขียนใหม่เป็นกราฟที่มีโครงสร้างได้[ 12 ]โดยใช้เพียงการเลือกลำดับและการวนซ้ำในขณะที่ยังคงรักษาโครงสร้างของโปรแกรมเดิมไว้[ 3 ]ในส่วนที่ 2 Böhm แสดงให้เห็นว่าการเลือกไม่จำเป็นอย่างเคร่งครัด: CFG ใดๆ ก็สามารถแปลงได้โดยใช้เพียงลำดับและการวนซ้ำ
การพิสูจน์ของ Jacopini ดำเนินไปโดยการอุปมานตามโครงสร้างของแผนผังการไหล[ 6 ]เนื่องจากใช้การจับคู่รูปแบบในกราฟการพิสูจน์จึงไม่ได้มีประโยชน์ในทางปฏิบัติในฐานะ อัลกอริธึม การแปลงโปรแกรมและด้วยเหตุนี้จึงเปิดโอกาสให้มีการวิจัยเพิ่มเติมในทิศทางนี้[ 13 ]

3. ทฤษฎีบทพื้นฐาน (การแปลงแบบวนซ้ำน้อยที่สุด)

ผลลัพธ์
ผังงานทุกผังเทียบเท่ากับ โปรแกรม whileที่มีwhile-do เกิดขึ้นหนึ่งครั้ง โดยอนุญาตให้มีตัวแปรเพิ่มเติมได้[ 14 ]
หมายเหตุ
ทฤษฎีบทเวอร์ชันนี้ทำให้การแปลง Böhm–Jacopini แบนราบลง ลดการวนซ้ำ ทั้งหมด เหลือเพียงลูปเดียวการเลือกถูกนำกลับมาใช้เพื่อความชัดเจน แต่ในทางทฤษฎีแล้วไม่จำเป็น
ทฤษฎีพื้นฐานนี้แทนที่การควบคุมการไหลของโปรแกรมดั้งเดิมด้วยwhileลูปทั่วโลกเพียงลูปเดียวที่จำลองตัวนับโปรแกรมที่วนไปตามป้ายกำกับที่เป็นไปได้ทั้งหมด (กล่องผังงาน) ในโปรแกรมที่ไม่เป็นโครงสร้างดั้งเดิม[ 3 ] Harel ได้สืบย้อนต้นกำเนิดของทฤษฎีพื้นฐานนี้ไปยังเอกสารสองฉบับที่เป็นจุดเริ่มต้นของการคำนวณ ฉบับหนึ่งคือคำอธิบายสถาปัตยกรรม von Neumann ในปี 1946 ซึ่งอธิบายวิธี การทำงาน ของตัวนับโปรแกรมในแง่ของลูป while Harel ตั้งข้อสังเกตว่าลูปเดียวที่ใช้โดยทฤษฎีการเขียนโปรแกรมเชิงโครงสร้างเวอร์ชันพื้นฐานนั้นโดยพื้นฐานแล้วให้ความหมายเชิงปฏิบัติการสำหรับการดำเนินการผังงานบนคอมพิวเตอร์ von Neumann [ 8 ]แหล่งที่มาที่เก่ากว่าอีกแหล่งหนึ่งที่ Harel สืบย้อนไปถึงทฤษฎีพื้นฐานนี้คือทฤษฎีรูปแบบปกติของStephen Kleeneจากปี 1936 [ 8 ]
p := 1 ในขณะที่p > 0 ทำซ้ำถ้าp = 1 ให้ดำเนินการขั้นตอนที่ 1 จากผังงานp := หมายเลขขั้นตอนถัดไปของขั้นตอนที่ 1 จากผังงาน( 0 ถ้าไม่มีขั้นตอนถัดไป) จบเงื่อนไขถ้าp = 2 ให้ดำเนินการขั้นตอนที่ 2 จากผังงานp := หมายเลขขั้นตอนถัดไปของขั้นตอนที่ 2 จากผังงาน( 0 ถ้าไม่มีขั้นตอนถัดไป) จบเงื่อนไข... ถ้าp = n ให้ดำเนินการขั้นตอนที่n จากผังงานp := หมายเลขขั้นตอนถัดไปของขั้นตอนที่n จากผังงาน( 0 ถ้าไม่มีขั้นตอนถัดไป) จบเงื่อนไข
Donald Knuthวิพากษ์วิจารณ์รูปแบบการพิสูจน์นี้ ซึ่งส่งผลให้เกิดรหัสเทียมดังตัวอย่างข้างต้น โดยชี้ให้เห็นว่าโครงสร้างของโปรแกรมดั้งเดิมนั้นสูญหายไปอย่างสิ้นเชิงในการแปลงนี้[ 15 ]ในทำนองเดียวกัน Bruce Ian Mills ได้เขียนเกี่ยวกับแนวทางนี้ว่า "จิตวิญญาณของโครงสร้างบล็อกเป็นรูปแบบ ไม่ใช่ภาษา การจำลองเครื่องจักร von Neumann ทำให้เราสามารถสร้างพฤติกรรมของโค้ดสปาเก็ตตี้ ใดๆ ก็ได้ ภายในขอบเขตของภาษาที่มีโครงสร้างบล็อก แต่นั่นไม่ได้หมายความว่ามันจะไม่เป็นสปาเก็ตตี้" [ 16 ]

4. คำแถลงเกี่ยวกับตำราเรียนสมัยใหม่

การเขียนโปรแกรมเชิงโครงสร้างมักถูกกล่าวว่า

ผลลัพธ์
ฟังก์ชันเรียกซ้ำบางส่วนทุกฟังก์ชันสามารถคำนวณได้ด้วยโปรแกรมที่มีโครงสร้างโดยใช้ลำดับ ( การเลือก ) และการวนซ้ำยิ่งไปกว่านั้น ด้วยการเข้ารหัสสถานะควบคุมที่เหมาะสมลูปเดียวก็เพียงพอแล้ว[ 17 ]while
หมายเหตุ
ซึ่งประกอบด้วย:
  1. Böhm (1964) – ผู้พิสูจน์ว่าสำหรับฟังก์ชันเรียกซ้ำบางส่วนทุกฟังก์ชัน จะมีโปรแกรม P′′ (ที่มีโครงสร้าง) ซึ่งคำนวณฟังก์ชันนั้น – ซึ่งเป็นการสร้างการมีอยู่ของอัลกอริทึมแทนที่จะเขียนอัลกอริทึมที่มีอยู่ใหม่[ 18 ]
  2. Böhm–Jacopini (1966) – ซึ่งแสดงให้เห็นว่าโปรแกรมหรือผังงานที่มีอยู่สามารถเขียนใหม่ได้โดยใช้เพียงการเลือกลำดับและการวนซ้ำ (โดยการเลือกนั้นซ้ำซ้อน) [ 5 ]
  3. ผลลัพธ์จากลูปเดี่ยวตามหลักการพื้นฐาน แสดงให้เห็นว่าการวนซ้ำสามารถลดลงเหลือเพียงลูปเดียวได้โดยใช้การเข้ารหัสสถานะควบคุมแบบชัดเจน

5. รุ่นกลับด้านได้

ทฤษฎีบทโปรแกรมโครงสร้างแบบย้อนกลับได้[ 19 ]เป็นแนวคิดสำคัญในสาขาการคำนวณแบบย้อนกลับได้โดยระบุว่าการคำนวณใดๆ ที่ทำได้โดยโปรแกรมแบบย้อนกลับได้ก็สามารถทำได้ผ่านโปรแกรมแบบย้อนกลับได้โดยใช้เพียงการรวมกันแบบมีโครงสร้างของโครงสร้างการควบคุมการไหล เช่น ลำดับ การเลือก และการวนซ้ำ การคำนวณใดๆ ที่ทำได้โดยโปรแกรมแบบดั้งเดิมที่ไม่สามารถย้อนกลับได้ก็สามารถทำได้ผ่านโปรแกรมแบบย้อนกลับได้เช่นกัน แต่มีข้อจำกัดเพิ่มเติมคือแต่ละขั้นตอนต้องสามารถย้อนกลับได้และมีเอาต์พุตเพิ่มเติม[ 20 ]นอกจากนี้ โปรแกรมแบบไม่มีโครงสร้างที่สามารถย้อนกลับได้ก็สามารถทำได้ผ่านโปรแกรมแบบย้อนกลับได้ที่มีโครงสร้างโดยมีการวนซ้ำเพียงครั้งเดียวโดยไม่มีเอาต์พุตเพิ่มเติม ทฤษฎีบทนี้วางรากฐานหลักการสำหรับการสร้างอัลกอริทึมแบบย้อนกลับได้ภายในกรอบการเขียนโปรแกรมแบบมีโครงสร้าง

สำหรับทฤษฎีบทโปรแกรมที่มีโครงสร้างวิธีการพิสูจน์ ทั้งแบบท้องถิ่น [ 5 ]และแบบทั่วโลก[ 21 ] เป็นที่รู้จัก อย่างไรก็ตาม สำหรับเวอร์ชันที่ย้อนกลับได้ แม้ว่าจะมีการยอมรับวิธีการพิสูจน์แบบทั่วโลก แต่วิธีการแบบท้องถิ่นที่คล้ายกับที่ดำเนินการโดย Böhm และ Jacopini [ 5 ]ยังไม่เป็นที่รู้จัก ความแตกต่างนี้เป็นตัวอย่างที่เน้นย้ำถึงความท้าทายและรายละเอียดปลีกย่อยในการสร้างรากฐานของการคำนวณแบบย้อนกลับได้เมื่อเทียบกับกระบวนทัศน์การคำนวณแบบดั้งเดิม

นัยยะและการปรับปรุงแก้ไข

การพิสูจน์ของ Böhm–Jacopini ไม่ได้ยุติคำถามว่าควรนำการเขียนโปรแกรมเชิงโครงสร้าง มา ใช้ในการพัฒนาซอฟต์แวร์หรือไม่ ส่วนหนึ่งเป็นเพราะโครงสร้างดังกล่าวมีแนวโน้มที่จะทำให้โปรแกรมคลุมเครือมากกว่าที่จะปรับปรุงให้ดีขึ้น ตรงกันข้าม มันกลับเป็นสัญญาณเริ่มต้นของการถกเถียงจดหมายที่มีชื่อเสียงของEdsger Dijkstra เรื่อง Go To Statement Considered Harmfulตามมาในปี 1968 [ 22 ]

นักวิชาการบางคนใช้แนวทางที่เคร่งครัดต่อผลลัพธ์ของ Böhm–Jacopini และโต้แย้งว่าแม้แต่คำสั่งเช่นbreakและreturnจากตรงกลางของลูปก็ถือเป็นวิธีปฏิบัติที่ไม่ดี เนื่องจากไม่จำเป็นในหลักฐานของ Böhm–Jacopini ดังนั้นพวกเขาจึงสนับสนุนให้ลูปทั้งหมดมีจุดออกเพียงจุดเดียว แนวทางที่เคร่งครัดนี้ปรากฏอยู่ในภาษาโปรแกรม Pascal (ออกแบบในปี 1968–1969) ซึ่งจนถึงกลางทศวรรษ 1990 ยังคงเป็นเครื่องมือที่นิยมใช้ในการสอนวิชาการเขียนโปรแกรมเบื้องต้นในสถาบันการศึกษา[ 23 ]

Edward Yourdonตั้งข้อสังเกตว่าในช่วงทศวรรษ 1970 มีการคัดค้านเชิงปรัชญาต่อการแปลงโปรแกรมที่ไม่มีโครงสร้างให้เป็นโปรแกรมที่มีโครงสร้างโดยวิธีการอัตโนมัติ โดยอ้างว่าจำเป็นต้องคิดแบบการเขียนโปรแกรมที่มีโครงสร้างตั้งแต่เริ่มต้น ข้อโต้แย้งเชิงปฏิบัติคือการแปลงดังกล่าวเป็นประโยชน์ต่อโปรแกรมที่มีอยู่จำนวนมาก[ 24 ]หนึ่งในข้อเสนอแรกสำหรับการแปลงอัตโนมัติคือบทความในปี 1971 โดย Edward Ashcroft และZohar Manna [ 25 ]

การประยุกต์ใช้ทฤษฎีบท Böhm–Jacopini โดยตรงอาจส่งผลให้มีการนำตัวแปรท้องถิ่นเพิ่มเติมเข้ามาในแผนภูมิโครงสร้าง และอาจส่งผลให้เกิดการทำซ้ำโค้ดบางส่วน[ 26 ]ปัญหาหลังนี้เรียกว่าปัญหาลูปครึ่งรอบในบริบทนี้[ 27 ]ภาษาปาสคาลได้รับผลกระทบจากปัญหาทั้งสองนี้ และจากการศึกษาเชิงประจักษ์ที่อ้างถึงโดยEric S. Roberts พบ ว่าโปรแกรมเมอร์นักเรียนมีปัญหาในการกำหนดสูตรวิธีแก้ปัญหาที่ถูกต้องในภาษาปาสคาลสำหรับปัญหาง่ายๆ หลายปัญหา รวมถึงการเขียนฟังก์ชันสำหรับการค้นหาองค์ประกอบในอาร์เรย์ การศึกษาในปี 1980 โดย Henry Shapiro ที่อ้างถึงโดย Roberts พบว่าการใช้โครงสร้างควบคุมที่ภาษาปาสคาลจัดให้เท่านั้น มีเพียง 20% ของผู้เข้าร่วมเท่านั้นที่ให้คำตอบที่ถูกต้อง ในขณะที่ไม่มีผู้เข้าร่วมคนใดเขียนโค้ดที่ไม่ถูกต้องสำหรับปัญหานี้หากได้รับอนุญาตให้เขียนคำสั่ง return จากตรงกลางของลูป[ 23 ]

ในปี พ.ศ. 2516 S. Rao Kosarajuได้พิสูจน์ว่าสามารถหลีกเลี่ยงการเพิ่มตัวแปรเพิ่มเติมในการเขียนโปรแกรมเชิงโครงสร้างได้ ตราบใดที่อนุญาตให้มีการหยุดหลายระดับที่มีความลึกตามอำเภอใจจากลูป[ 1 ] [ 29 ]นอกจากนี้ Kosaraju ยังพิสูจน์ว่ามีลำดับชั้นที่เข้มงวดของโปรแกรมอยู่ ซึ่งปัจจุบันเรียกว่าลำดับชั้น Kosarajuโดยที่สำหรับจำนวนเต็มn ทุกตัว จะมีโปรแกรมที่มีการหยุดหลายระดับที่มีความลึกnซึ่งไม่สามารถเขียนใหม่เป็นโปรแกรมที่มีการหยุดหลายระดับที่มีความลึกน้อยกว่าnได้ (โดยไม่ต้องแนะนำตัวแปรเพิ่มเติม) [ 1 ] Kosaraju อ้างถึงโครงสร้างการหยุดหลายระดับใน ภาษาการเขียนโปรแกรม BLISSการหยุดหลายระดับในรูปแบบของคำหลักนั้นถูกนำมาใช้ในเวอร์ชัน BLISS-11 ของภาษานั้น BLISS ดั้งเดิมมีเพียงการหยุดระดับเดียวเท่านั้น ตระกูลภาษา BLISS ไม่ได้ให้ goto ที่ไม่จำกัด ต่อมา ภาษาการเขียนโปรแกรม Javaก็ได้ปฏิบัติตามแนวทางนี้เช่นกัน[ 30 ]leave label

ผลลัพธ์ที่ง่ายกว่าจากบทความของ Kosaraju คือ โปรแกรมจะลดรูปเป็นโปรแกรมที่มีโครงสร้าง (โดยไม่ต้องเพิ่มตัวแปร) ได้ก็ต่อเมื่อโปรแกรมนั้นไม่มีลูปที่มีทางออกสองทางที่แตกต่างกัน Kosaraju นิยามความสามารถในการลดรูปอย่างคร่าวๆ ว่าคือการคำนวณฟังก์ชันเดียวกันและใช้ "การกระทำพื้นฐาน" และ述語 (predicate) เดียวกันกับโปรแกรมดั้งเดิม แต่ใช้โครงสร้างการไหลของควบคุมที่แตกต่างกันได้ (นี่เป็นแนวคิดเรื่องความสามารถในการลดรูปในวงแคบกว่าที่ Böhm–Jacopini ใช้) ด้วยแรงบันดาลใจจากผลลัพธ์นี้ ในส่วนที่ VI ของบทความที่ได้รับการอ้างอิงอย่างสูงซึ่งแนะนำแนวคิดเรื่องความซับซ้อนแบบไซโคลมาติก Thomas J. McCabe ได้อธิบายถึงอนาล็อกของทฤษฎีบทของ Kuratowskiสำหรับกราฟการไหลของควบคุม (CFG) ของโปรแกรมที่ไม่มีโครงสร้าง ซึ่งก็คือกราฟย่อย ขั้นต่ำ ที่ทำให้ CFG ของโปรแกรมไม่มีโครงสร้าง กราฟย่อยเหล่านี้มีคำอธิบายที่ดีมากในภาษาธรรมชาติ ได้แก่:

  1. การแยกสาขาออกจากลูป (นอกเหนือจากการทดสอบวงจรลูป)
  2. แยกออกเป็นวงวน
  3. แยกออกเป็นการตัดสินใจ (เช่น แยกออกเป็น "สาขา" ของเงื่อนไข if)
  4. การแตกแขนงออกไปจากการตัดสินใจ

แมคเคบพบว่ากราฟทั้งสี่นี้ไม่เป็นอิสระเมื่อปรากฏเป็นกราฟย่อย ซึ่งหมายความว่าเงื่อนไขที่จำเป็นและเพียงพอสำหรับโปรแกรมที่ไม่เป็นโครงสร้างคือ CFG ของโปรแกรมนั้นจะต้องมีกราฟย่อยหนึ่งในเซตย่อยใด ๆ ของกราฟสามในสี่กราฟนี้ เขายังพบอีกว่าหากโปรแกรมที่ไม่เป็นโครงสร้างมีกราฟย่อยหนึ่งในสี่กราฟนี้ มันจะต้องมีกราฟย่อยที่แตกต่างกันอีกกราฟหนึ่งจากเซตของกราฟทั้งสี่ ผลลัพธ์หลังนี้ช่วยอธิบายว่าการไหลของควบคุมของโปรแกรมที่ไม่เป็นโครงสร้างนั้นพันกันยุ่งเหยิงในสิ่งที่เรียกกันทั่วไปว่า "โค้ดสปาเก็ตตี้" ได้อย่างไร แมคเคบยังได้คิดค้นมาตรวัดเชิงตัวเลขที่เมื่อกำหนดโปรแกรมใด ๆ แล้ว จะวัดว่าโปรแกรมนั้นห่างไกลจากอุดมคติของการเป็นโปรแกรมที่มีโครงสร้างมากน้อยเพียงใด แมคเคบเรียกมาตรวัดของเขาว่าความซับซ้อนที่จำเป็น[ 31 ]การกำหนดลักษณะของกราฟต้องห้ามสำหรับการเขียนโปรแกรมที่มีโครงสร้างของแมคเคบอาจถือว่าไม่สมบูรณ์ อย่างน้อยที่สุดหากโครงสร้าง D ของไดจ์กสตราถือเป็นส่วนประกอบพื้นฐาน[ 32 ]

จนถึงปี 1990 มีวิธีการมากมายที่เสนอสำหรับการกำจัด goto จากโปรแกรมที่มีอยู่ ในขณะที่ยังคงรักษาโครงสร้างส่วนใหญ่ไว้ แนวทางต่างๆ ในการแก้ปัญหานี้ยังเสนอแนวคิดเรื่องความเท่าเทียมกันหลายประการ ซึ่งเข้มงวดกว่าความเท่าเทียมกันของทัวริง เพื่อหลีกเลี่ยงผลลัพธ์เช่นทฤษฎีบทพื้นบ้านที่กล่าวถึงข้างต้น ความเข้มงวดของแนวคิดเรื่องความเท่าเทียมกันที่เลือกจะกำหนดชุดโครงสร้างการไหลของควบคุมขั้นต่ำที่จำเป็น บทความ JACM ปี 1988 โดย Lyle Ramshaw ได้สำรวจสาขานี้จนถึงจุดนั้น รวมถึงเสนอวิธีการของตนเองด้วย[ 33 ]ตัวอย่างเช่น อัลกอริทึมของ Ramshaw ถูกนำมาใช้ในโปรแกรมถอดรหัส Java บางตัว เนื่องจาก โค้ด เครื่องเสมือน Javaมีคำสั่งสาขาที่มีเป้าหมายที่แสดงเป็นออฟเซ็ต แต่ภาษา Java ระดับสูงมีเพียงคำสั่งหลายระดับbreakและcontinueคำสั่ง เท่านั้น [ 34 ] [ 35 ] [ 36 ] Ammarguellat (1992) เสนอวิธีการแปลงที่ย้อนกลับไปบังคับใช้การออกทางเดียว[ 13 ]

การประยุกต์ใช้กับ COBOL

ในช่วงทศวรรษ 1980 ฮาร์ลัน มิลส์นักวิจัยของ IBMได้ดูแลการพัฒนาCOBOL Structuring Facilityซึ่งใช้ขั้นตอนวิธีจัดโครงสร้างกับ โค้ด COBOLการแปลงโค้ดของมิลส์ประกอบด้วยขั้นตอนต่อไปนี้สำหรับแต่ละกระบวนการ

  1. ระบุส่วนประกอบพื้นฐานในกระบวนการ
  2. กำหนดป้ายกำกับ ที่ไม่ซ้ำกัน ให้กับเส้นทางเข้าของแต่ละบล็อก และติดป้ายกำกับเส้นทางออกของแต่ละบล็อกด้วยป้ายกำกับของเส้นทางเข้าที่เชื่อมต่อกัน ใช้ 0 สำหรับเส้นทางกลับจากขั้นตอน และ 1 สำหรับเส้นทางเข้าของขั้นตอน
  3. แบ่งขั้นตอนออกเป็นส่วนประกอบพื้นฐาน
  4. สำหรับแต่ละบล็อกที่เป็นปลายทางของทางออกเพียงทางเดียว ให้เชื่อมต่อบล็อกนั้นเข้ากับทางออกนั้นอีกครั้ง
  5. ประกาศตัวแปรใหม่ในขั้นตอนการทำงาน (ตั้งชื่อว่าLเพื่อความสะดวก)
  6. ในแต่ละเส้นทางออกที่ยังไม่เชื่อมต่อ ให้เพิ่มคำสั่งที่กำหนดค่าLให้เป็นค่าป้ายกำกับบนเส้นทางนั้น
  7. รวมโปรแกรมที่ได้เข้าด้วยกันเป็นคำสั่งเลือกที่เรียกใช้โปรแกรมที่มีป้ายกำกับเส้นทางเข้าที่ระบุด้วยตัวอักษรL
  8. สร้างลูปที่ดำเนินการคำสั่งเลือกนี้ตราบใดที่Lไม่เป็น 0
  9. สร้างลำดับที่กำหนดค่าเริ่มต้นให้Lเป็น 1 แล้วจึงวนลูป

โครงสร้างนี้สามารถปรับปรุงได้โดยการแปลงบางกรณีของคำสั่งเลือกให้เป็นขั้นตอนย่อย

ดูเพิ่มเติม

หมายเหตุและเอกสารอ้างอิง

  1. ^ a b c Kozen & Tseng 2008 .
  2. ^มหาวิทยาลัยบัฟฟาโล ปี 2004
  3. ↑ a b c Barendregt 2019 , หน้า. 12.
  4. ^ a b Böhm 1964 .
  5. ↑ a b c d e f Böhm และ Jacopini 1966 .
  6. ↑ a b c d e Harel 1980 , p. 381.
  7. ↑เบิร์กส, โกลด์สตีน และฟอน นอยมันน์ พ.ศ. 2490
  8. ^ a b c Harel 1980 , หน้า 383.
  9. ^ มิล ส์ 1972
  10. ^ภาษา P′′เป็น ภาษา ที่สมบูรณ์แบบในเชิงทัวริงและตรงตามข้อกำหนด Brainfuckซึ่งเป็นภาษาที่แตกแขนงมาจาก P′′ ก็มีโครงสร้างที่ออกแบบมาอย่างดีเช่นกัน
  11. ^ Böhm–Jacopini ไม่ได้กำหนดอย่างชัดเจนว่า “โปรแกรม” จะต้องมีทางเข้าเดียวและทางออกเดียวโดยที่ทุกโหนดสามารถเข้าถึงได้ แต่การพิสูจน์ของพวกเขาอาศัยเงื่อนไขนี้ Mills (1972 , หน้า 32) ได้ระบุข้อกำหนดทั้งสองนี้ไว้อย่างชัดเจน
  12. ^ กราฟ CFG แบบทางเข้าเดียว ทางออกเดียว (SESE) จะเรียกว่า "มีโครงสร้าง" หากกราฟย่อยแต่ละกราฟเป็น SESE
  13. ^ a b Ammarguellat 1992 .
  14. ^ฮาเรล 1980 , หน้า 380.
  15. ^ Knuth 1974 , หน้า 274.
  16. ^มิลส์ 2005 , หน้า 279.
  17. ^เกรบาช 1975บทที่ 4. โปรแกรมที่มีโครงสร้าง
  18. ^ Böhm 1964 , หน้า 191, ผลลัพธ์หลักของงานวิจัยนี้
  19. ↑โยโกยามา, แอ็กเซลเซ่น และกลึค 2016 .
  20. ^ เบนเน็ต ต์ 1973
  21. ^คูเปอร์ 1967
  22. ^ ไดจ์ก สตรา 1968
  23. ^ a b Roberts 1995 .
  24. ^ Yourdon 1979 , หน้า 49–50.
  25. ^แอชครอฟต์ แอนด์ แมนนา 1971
  26. ^ Watt & Findlay 2004 , หน้า 228.
  27. ^ Louden & Lambert 2011 , หน้า 422–423.
  28. ^ โคสารา จู 1974
  29. ↑ Kosaraju 1973 , [ 28 ]อ้างโดย Knuth 1974 .
  30. ↑เบรนเดอร์ 2002 , หน้า 960–965.
  31. ^เอกสารต้นฉบับคือ McCabe 1976สำหรับคำอธิบายเพิ่มเติม โปรดดู Jorgensen 2002
  32. ^วิลเลียมส์ 1983 , หน้า 274–275.
  33. ^ แรมชอ ว์ 1988
  34. ^โนแลน 2004
  35. ^ Proebsting & Watterson 1997
  36. ↑มารุยามะ, โอกาวะ และมัตสึโอกะ 2542

บรรณานุกรม

  • Ammarguellat, Z. (1992). "อัลกอริทึมการทำให้การไหลของควบคุมเป็นมาตรฐานและความซับซ้อนของมัน" IEEE Transactions on Software Engineering . 18 (3): 237– 251. doi : 10.1109/32.126773 .
  • Ashcroft, Edward; Manna, Zohar (1971). "การแปลงโปรแกรม go to เป็นโปรแกรม 'while'". รายงานการประชุม IFIP Congress .ตีพิมพ์ซ้ำในYourdon 1979หน้า 51–61
  • Bennett, CH (พฤศจิกายน 1973). "ความสามารถในการย้อนกลับเชิงตรรกะของการคำนวณ". IBM Journal of Research and Development . 17 (6): 525– 532. doi : 10.1147/rd.176.0525 .
  • Böhm, Corrado (มิถุนายน 1962) "มัคชิเนอินดีริซซี, ดอตาเต ดิ อุน นูเมโร มินิโม ดิ อิสตรูซิโอนี " เรนดิคอนติ เดลล์อัคคาเดเมีย นาซิโอนาเล เดย ลินเซ Classe di Scienze Fisiche, Matematiche e Naturali, Serie VIII (ในภาษาอิตาลี) 32 : 923– 930.
  • Böhm, Corrado (1964). "เกี่ยวกับตระกูลเครื่องจักรทัวริงและภาษาโปรแกรมที่เกี่ยวข้อง" (PDF) . ICC Bulletin . 3 : 185– 194.
  • Böhm, คอร์ราโด ; Jacopini, Giuseppe [ในภาษาอิตาลี] (มิถุนายน 1962) "Nuove tecniche di programmazione semplificanti la sintesi di macchine universali di Turing" . เรนดิคอนติ เดลล์อัคคาเดเมีย นาซิโอนาเล เดย ลินเซ Classe di Scienze Fisiche, Matematiche e Naturali, Serie VIII (ในภาษาอิตาลี) 32 : 913– 922.
  • Böhm, Corrado ; Jacopini, Giuseppe [ในภาษาอิตาลี] (พฤษภาคม 1966). "แผนภาพการไหล เครื่องจักรทัวริง และภาษาที่มีกฎการสร้างเพียงสองข้อ" Communications of the ACM . 9 (5): 366– 371. CiteSeerX  10.1.1.119.9119 . doi : 10.1145/355592.365646 . S2CID  10236439 .ตีพิมพ์ซ้ำในYourdon 1979หน้า 13–25
  • Brender, Ronald F. (2002). "ภาษาการเขียนโปรแกรม BLISS: ประวัติความเป็นมา" (PDF) . ซอฟต์แวร์: การปฏิบัติและประสบการณ์ . 32 (10): 955– 981. doi : 10.1002/spe.470 . S2CID  45466625 .
  • Burks, Arthur W. ; Goldstine, Herman ; von Neumann, John (1947). การอภิปรายเบื้องต้นเกี่ยวกับการออกแบบเชิงตรรกะของเครื่องมือคำนวณอิเล็กทรอนิกส์ (รายงาน). พรินซ์ตัน, นิวเจอร์ซีย์: สถาบันเพื่อการศึกษาขั้นสูง.
  • Cooper, David C. (สิงหาคม 1967). "การลดแผนผังการไหลของ Böhm และ Jacopini" . Communications of the ACM . 10 (8): 463. doi : 10.1145/363534.363539 .
  • Dijkstra, Edsger (1968). "Go To Statement Considered Harmful" . Communications of the ACM . 11 (3): 147– 148. doi : 10.1145/362929.362947 . S2CID  17469809 .ตีพิมพ์ซ้ำในYourdon 1979หน้า 29–33
  • เกรบาค, ชีลา เอ. (1975). ทฤษฎีโครงสร้างโปรแกรม: โครงร่าง ความหมาย การตรวจสอบ . บันทึกการบรรยายในวิทยาการคอมพิวเตอร์ เล่มที่ 36. เบอร์ลิน ไฮเดลเบิร์ก นิวยอร์ก: สปริงเกอร์-เวอร์แลก. ISBN 978-3-540-07415-1. ลคซีเอ็น 75031780 .
  • Harel, David (1980). "เกี่ยวกับทฤษฎีบทพื้นบ้าน" . Communications of the ACM . 23 (7): 379– 389. doi : 10.1145/358886.358892 . S2CID  16300625 .
  • Jorgensen, Paul C. (2002). การทดสอบซอฟต์แวร์: แนวทางของช่างฝีมือ (ฉบับที่ 2). สำนักพิมพ์ CRC. หน้า  150–153 . ISBN 978-0-8493-0809-3.
  • Knuth, Donald (1974). "การเขียนโปรแกรมเชิงโครงสร้างด้วยคำสั่ง go to". Computing Surveys . 6 (4): 261– 301. CiteSeerX  10.1.1.103.6084 . doi : 10.1145/356635.356640 . S2CID  207630080 .ตีพิมพ์ซ้ำในYourdon 1979หน้า 259–321
  • Kosaraju, S. Rao (พฤษภาคม 1973). "การวิเคราะห์โปรแกรมที่มีโครงสร้าง". รายงานการประชุมสัมมนาประจำปีครั้งที่ 5 ของ ACM ว่าด้วยทฤษฎีการคำนวณ . ACM. หน้า  240–252 ." การวิเคราะห์โปรแกรมที่มีโครงสร้าง" วารสารวิทยาการคอมพิวเตอร์และระบบ 9 ( 3): 232– 255. 1974 [1973]. doi : 10.1016/S0022-0000(74) 80043-7
  • Kozen, Dexter ; Tseng, Wei-Lung Dustin (2008). "คณิตศาสตร์ของการสร้างโปรแกรม – ทฤษฎีบท Böhm–Jacopini เป็นเท็จในเชิงประพจน์" (PDF) . MPC 2008 . Lecture Notes in Computer Science. Vol. 5133. pp.  177– 192. CiteSeerX  10.1.1.218.9241 . doi : 10.1007/978-3-540-70594-9_11 . ISBN 978-3-540-70593-2.
  • ลูเดน, เคนเนธ ซี.; แลมเบิร์ต, เคนเนธ เอ. (2011). ภาษาโปรแกรม: หลักการและแนวปฏิบัติ (ฉบับที่ 3). เซงเกจ เลิร์นนิง. ISBN 978-1-111-52941-3.
  • Maruyama, Fuyuhiko; Ogawa, Hirotaka; Matsuoka, Satoshi (1999). "อัลกอริทึมการถอดรหัสที่มีประสิทธิภาพสำหรับไบต์โค้ด Java" (PDF) . www.openjit.org (เป็นภาษาญี่ปุ่น) . สืบค้นเมื่อ12 กรกฎาคม 2025 .
  • McCabe, Thomas J. (ธันวาคม 1976). "การวัดความซับซ้อน" . IEEE Transactions on Software Engineering . SE-2 (4): 315– 318. doi : 10.1109/tse.1976.233837 . S2CID  9116234 .
  • มิลส์, เอช. (1972). พื้นฐานทางคณิตศาสตร์สำหรับการเขียนโปรแกรมเชิงโครงสร้าง (รายงานทางเทคนิค). เกเธอร์สเบิร์ก, แมริแลนด์: ฝ่ายระบบของรัฐบาลกลางของ IBM. หน้า 62.
  • มิลส์, บรูซ เอียน (2005). บทนำเชิงทฤษฎีเกี่ยวกับการเขียนโปรแกรม . สปริงเกอร์. หน้า 279. ISBN 978-1-84628-263-8.
  • โนแลน, ก็อดฟรีย์ (2004). การถอดรหัสภาษาจาวา . สำนักพิมพ์เอเพรส. หน้า 142. ISBN 978-1-4302-0739-9.
  • Proebsting, Todd A.; Watterson, Scott A. (1997). "Krakatoa: การถอดรหัสในภาษา Java" (PDF) . usenix.org . สืบค้นเมื่อ12 กรกฎาคม 2025 .
  • Ramshaw, L. (1988). "การกำจัด go to ในขณะที่ยังคงรักษาโครงสร้างโปรแกรมไว้" . Journal of the ACM . 35 (4): 893– 920. doi : 10.1145/48014.48021 . S2CID  31001665 .
  • Roberts, E. (1995). "Loop Exits and Structured Programming: Reopening the Debate" (PDF) . ACM SIGCSE Bulletin . 27 (1): 268– 272. เก็บถาวร(PDF)จากต้นฉบับเมื่อวันที่ 25 กรกฎาคม 2014
  • มหาวิทยาลัยบัฟฟาโล (22 พฤศจิกายน 2547). "CSE 111, ภาคเรียนฤดูใบไม้ร่วง 2547, ทฤษฎีบทโบห์ม-จาโคปินี" . มหาวิทยาลัยบัฟฟาโล. เก็บถาวรจากต้นฉบับเมื่อวันที่ 22 พฤศจิกายน 2547. สืบค้นเมื่อ12 กรกฎาคม 2568 .
  • วัตต์, เดวิด แอนโทนี ; ฟินด์เลย์, วิลเลียม (2004). แนวคิดการออกแบบภาษาโปรแกรม . จอห์น ไวลีย์ แอนด์ ซันส์. ISBN 978-0-470-85320-7.
  • Williams, MH (1983). "แผนผังกระบวนการทำงานและปัญหาของการตั้งชื่อ". The Computer Journal . 26 (3): 270– 276. doi : 10.1093/comjnl/26.3.270 .
  • Yokoyama, Tetsuo; Axelsen, Holger Bock; Glück, Robert (มกราคม 2016). "พื้นฐานของภาษาผังงานแบบย้อนกลับได้" . วิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎี . 611 : 87– 115. doi : 10.1016/j.tcs.2015.07.046 .
  • Yourdon, EN , บรรณาธิการ (1979). คลาสสิกในวิศวกรรมซอฟต์แวร์ . นิวยอร์ก, NY: Yourdon Press. หน้า xi, 424. ISBN 978-0-917072-14-7. ลคซีเอ็น 79-63449 .

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

  • DeMillo, Richard A. ; Eisenstat, Stanley C.; Lipton, Richard J. (มกราคม 1980). "การแลกเปลี่ยนระหว่างพื้นที่และเวลาในการเขียนโปรแกรมเชิงโครงสร้าง: ทฤษฎีบทการฝังเชิงรวมที่ได้รับการปรับปรุง"วารสารของ ACM 27 ( 1): 123– 127. doi : 10.1145/322169.322180 . S2CID  15669719 .
  • Devienne, Philippe; Lebègue, Patrick; Routier, Jean-Christophe; Würtz, Jörg (กุมภาพันธ์ 1994). "One binary Horn clause is enough". Proceedings of the 11th Symposium on Theoretical Aspects of Computer Science (STACS '94) . Lecture Notes in Computer Science. Vol. 775. pp.  21– 32. CiteSeerX  10.1.1.14.537 . doi : 10.1007/3-540-57785-8_128 . ISBN 978-3-540-57785-0.
ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Structured_program_theorem&oldid=1352557552 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ ทฤษฎีบทโปรแกรมเชิงโครงสร้าง

ใน ทฤษฎีภาษาการเขียนโปรแกรม ทฤษฎีบท โปรแกรมที่มีโครงสร้าง ซึ่งโดยทั่วไปเรียกว่า ทฤษฎีบท Böhm–Jacopini [ 1 ] [ 2 ] ระบุว่าคลาสของ กราฟควบคุมการไหล (ในอดีตเรียกว่า ผังงาน...

ที่มาและรูปแบบต่างๆ

ในปี พ.ศ. 2507 Corrado Böhm ได้กำหนด ภาษาการเขียนโปรแกรม ที่สมบูรณ์แบบ Turing อย่างง่าย ( P′′ ) โดย อาศัยลำดับ และ การวนซ้ำ [ 4 ] ใน บทความต่อมา Böhm และ Giuseppe Jacopini ได้กล่าวถึงผลลัพธ์นี้อีกครั้ง [ 5 ]

1. Böhm 1964 (การสร้างโปรแกรม/การคำนวณ)

ผลลัพธ์ ฟังก์ชันเรียกซ้ำบางส่วน ทุก ฟังก์ชัน สามารถคำนวณได้ด้วยโปรแกรม [ 10 ] โดยใช้เพียง ลำดับ และ การวน ซ้ำ [ 4 ] หมายเหตุ ผลลัพธ์นี้มุ่งเน้นไปที่ การสร้าง โปรแกรมไม่จำเป็นต้องมี การเลือก : พฤติกรรมตามเงื่อนไขจะถูกเข้ารหัสด้วยลูป P′′ ป้องกัน...

2. Böhm–Jacopini 1966 (การเปลี่ยนแปลงโปรแกรม)

ผลลัพธ์ ผังงานทุกผัง ( กราฟควบคุมการไหล , CFG) สามารถแปลงเป็นโปรแกรมที่มีโครงสร้างได้โดยใช้เพียง ลำดับ และ การวนซ้ำ เท่านั้น [ 5 ] หมายเหตุ ทฤษฎีบทเวอร์ชันนี้มุ่งเน้นไปที่ การแปลง โปรแกรม โดยมีความเกี่ยวข้องกับ การเพิ่มประสิทธิภาพคอมไพเลอร์ เป็นหลัก...