อัลกอริทึมทุกอันถูกกำหนดด้วยภาษาบางภาษา ซึ่งความหมายของภาษา (semantics) นั้นกำหนดการคำนวณที่อัลกอริทึมแสดงออกมา เราได้เห็นแล้วว่าภาษาที่แตกต่างกันสามารถมีความหมายที่แตกต่างกัน และสามารถถูกออกแบบมาสำหรับคอมพิวเตอร์ที่แตกต่างกัน ตัวอย่างเช่น อัลกอริทึมที่เขียนด้วยภาษาโปรแกรมมิ่งจะถูกประมวลผลบนคอมพิวเตอร์อิเล็กทรอนิกส์ และโดยทั่วไปแล้วหมายถึงการคำนวณข้อมูล ในทางกลับกัน อัลกอริทึมที่เขียนด้วยภาษาโน้ตดนตรีจะถูกประมวลผลโดยนักดนตรีและหมายถึงเสียงต่างๆ แม้จะมีความแตกต่างเหล่านี้ ภาษาที่ไม่ธรรมดาส่วนใหญ่ก็มีคุณสมบัติที่น่าสนใจร่วมกัน นั่นคือ ประกอบด้วยคำสั่งสองประเภท: (1) operations ที่ส่งผลโดยตรง และ (2) control structures สำหรับจัดระเบียบลำดับ การประยุกต์ใช้ และการทำซ้ำของคำสั่งต่างๆ

โครงสร้างควบคุม (control structures) ไม่เพียงมีบทบาทสำคัญในการกำหนดอัลกอริทึม แต่ยังกำหนดความสามารถในการแสดงออกของภาษาต่างๆ ด้วย นั่นหมายความว่า การนิยามโครงสร้างควบคุมและการตัดสินใจว่าจะรวมโครงสร้างควบคุมใดไว้ในภาษาหนึ่งๆ จะกำหนดว่าอัลกอริทึมใดบ้างที่สามารถแสดงออกในภาษานั้น และด้วยเหตุนี้จึงกำหนดว่าปัญหาใดบ้างที่สามารถแก้ไขได้ด้วยภาษานั้น

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

Forever and a Day (ตลอดกาลและหนึ่งวัน)

คุณอาจเคยได้ยินเกี่ยวกับวันกราวด์ฮ็อก (Groundhog Day) ซึ่งเป็นประเพณีที่กราวด์ฮ็อกสามารถทำนาย—ตามตัวอักษร—ว่าฤดูหนาวจะยืดเยื้อต่อไปอีกหกสัปดาห์หรือจะถึงฤดูใบไม้ผลิเร็วขึ้น โดยมีหลักการดังนี้ ทุกปีในวันที่สองของเดือนกุมภาพันธ์ กราวด์ฮ็อกจะออกมาจากโพรงของมัน ถ้าในวันที่แดดออกมันเห็นเงาของตัวเอง มันจะถอยกลับเข้าไปในโพรง ซึ่งบ่งบอกว่าฤดูหนาวจะคงอยู่ต่อไปอีกหกสัปดาห์ ถ้าในวันที่มีเมฆมากมันไม่เห็นเงาของตัวเอง นั่นหมายถึงการมาถึงของฤดูใบไม้ผลิที่เร็วขึ้น

เมื่อเติบโตขึ้นนอกสหรัฐอเมริกา ผมได้เรียนรู้เกี่ยวกับประเพณีนี้ผ่านภาพยนตร์ปี 1993 เรื่อง Groundhog Day ซึ่งฟิล คอนเนอร์ส ผู้รายงานสภาพอากาศที่เริ่มต้นด้วยความหยิ่งยโสและเยาะเย้ยถากถางจากพิตส์เบิร์ก ไปรายงานเกี่ยวกับเทศกาลวันกราวด์ฮ็อกในเมืองเล็กๆ ชั้นพักซะทอนี (Punxsutawney) จุดเด่นที่น่าสนใจของหนังเรื่องนี้คือ ฟิล คอนเนอร์สต้องใช้ชีวิตวันเดิมซ้ำแล้วซ้ำเล่า ทุกเช้าเขาตื่นนอนเวลา 6:00 น. พร้อมกับเพลงเดิมทางวิทยุ และต้องประสบกับสถานการณ์ชุดเดิมๆ เนื้อเรื่องดำเนินไปเมื่อเขาตอบสนองต่อสถานการณ์เหล่านี้แตกต่างกันไปตลอดทั้งเรื่อง

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

ฟิล: คุณจะทำยังไงถ้าติดอยู่ที่ไหนสักแห่งที่ทุกวันมันเหมือนเดิมทุกประการ และไม่มีอะไรที่คุณทำแล้วมีความหมาย?

ราล์ฟ: นั่นก็ประมาณชีวิตผมเลยนะ

บทสนทนานี้สามารถสรุปได้ในรูปแบบการอธิบายชีวิตของคนเราด้วยลูปดังนี้:

repeat   กิจวัตรประจำวัน   until   คุณตาย

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

วันของเรามักจะน่าหงุดหงิดน้อยกว่าวันกราวด์ฮ็อกที่วนซ้ำไม่รู้จบ เพราะการกระทำของเราเมื่อวานส่งผลต่อวันนี้ ดังนั้น แต่ละวัน ไม่ว่าจะดูซ้ำซากแค่ไหน ก็เกิดขึ้นในบริบทที่แตกต่างกัน และการรู้ว่าสิ่งที่เราและคนอื่นทำนั้นสร้างความแตกต่าง ทำให้เรามีความรู้สึกถึงการเปลี่ยนแปลงและความก้าวหน้าอย่างต่อเนื่อง ข้อสังเกตเหล่านี้ชี้ให้เห็นถึงความแตกต่างระหว่างลูปสองประเภท นั่นคือ ลูปที่ให้ผลลัพธ์เหมือนเดิมในแต่ละ iteration และลูปที่ให้ผลลัพธ์แตกต่างกัน ตัวอย่างของประเภทแรกคือลูปที่พิมพ์ชื่อเมืองที่คุณเกิด เช่น นิวยอร์ก ถ้าไม่มีการเปลี่ยนชื่อเมือง ลูปนี้จะสร้างผลลัพธ์เดิมๆ ออกมาตลอด เช่น "นิวยอร์ก" "นิวยอร์ก" "นิวยอร์ก" … ในทางตรงกันข้าม ลูปที่รายงานว่าฝนตกหรือไม่จะสร้างกระแสข้อมูลที่ผสมระหว่างค่าใช่และไม่ใช่—เว้นแต่คุณอาศัยอยู่ที่เชอร์ราปุนจี 1 ซึ่งมีแนวโน้มว่าจะสร้างกระแสค่าใช่ตลอดเวลา

สังเกตว่าแม้ในลูปที่ให้ผลลัพธ์แตกต่างกัน body ของลูปก็ยังเหมือนเดิมในทุก iteration ความหลากหลายเกิดขึ้นได้ผ่าน ตัวแปร (variables) ตัวแปรคือชื่อที่ชี้ไปยังส่วนหนึ่งของโลก ผ่านชื่อตัวแปร อัลกอริทึมสามารถสังเกตและจัดการกับโลกได้ ตัวอย่างเช่น ตัวแปร weather ชี้ไปยังสภาพอากาศปัจจุบัน สมมติว่าแดดออก และอัลกอริทึมที่ตรวจสอบสภาพอากาศปัจจุบันโดยการเข้าถึงตัวแปรนี้จะได้ค่าที่สอดคล้องกัน ตัวแปร weather ไม่สามารถถูกเปลี่ยนแปลงโดยอัลกอริทึมได้ แต่ตัวแปร pebble ที่อ้างอิงถึงก้อนกรวดถัดไปที่ฮันเซลกับเกรเทลเดินไปหา จะเปลี่ยนแปลงไปตามแต่ละก้อนกรวดที่เยี่ยมชม ในทำนองเดียวกัน ในคำสั่งให้ค้นหาธาตุที่เล็กที่สุดในลิสต์ซึ่งเป็นส่วนหนึ่งของ selection sort ตัวแปร smallest element จะเปลี่ยนแปลงในแต่ละ iteration เว้นแต่ลิสต์จะมีค่าซ้ำกัน

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

repeat   รายงานสภาพอากาศ   until   ตลอดไป

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

ฝนตก มีเมฆมาก แดดออก แดดออก พายุฝนฟ้าคะนอง แดดออก …

ลูปการรายงานสภาพอากาศนี้บรรยายถึงประเภทของลูปที่ฟิล คอนเนอร์สพบเจอ: ทุกเช้าเขาต้องเตรียมรายงานพยากรณ์อากาศจากเพื่อนร่วมงานของเขา ซึ่งก็คือกราวด์ฮ็อกพักซะทอนี ฟิล (Punxsutawney Phil) (ที่น่าสนใจคือ แม้จะมีความผันแปรอันน่าตื่นเต้นมากมายที่เขาสร้างขึ้นในแต่ละวัน—ครั้งหนึ่งถึงกับพยายามฆ่าพักซะทอนี ฟิล—เขาก็ดูเหมือนจะไม่เคยพลาดรายงานเกี่ยวกับการพยากรณ์ของกราวด์ฮ็อก) แน่นอนว่า ฟิล คอนเนอร์สหวังว่าลูปที่เขาติดอยู่นั้นจะไม่วนซ้ำตลอดไป ที่จริงแล้ว เขาสันนิษฐานว่าลูปนี้มีรูปแบบดังนี้:

repeat   รายงานสภาพอากาศ   until ' เงื่อนไขที่ซ่อนอยู่บางอย่าง'

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

ลูปวันกราวด์ฮ็อกเป็นตัวอย่างของโครงร่างลูปทั่วไปดังนี้: 2

repeat   step   until   condition

Termination condition ปรากฏอยู่ที่ส่วนท้ายและถูกประเมินหลังจาก body ของลูปถูกประมวลผลแล้ว ถ้าเงื่อนไขเป็นจริง ลูปจะหยุด ถ้าไม่เป็นจริง body จะถูกประมวลผลอีกครั้ง หลังจากนั้นเงื่อนไขจะถูกตรวจสอบอีกครั้งเพื่อตัดสินใจว่าจะดำเนินการต่อหรือจบลูป และทำไปเรื่อยๆ

เป็นที่ชัดเจนว่า termination condition ที่เป็นเท็จในเวลาหนึ่งจะกลายเป็นจริงในภายหลังได้ก็ต่อเมื่อมันมีตัวแปรที่สามารถเปลี่ยนแปลงได้โดยการกระทำใน body ของลูป ตัวอย่างเช่น ความพยายามในการสตาร์ทรถที่น้ำมันหมดจะไม่สำเร็จจนกว่าจะเติมน้ำมัน ดังนั้น ถ้าการกระทำที่ทำซ้ำมีเพียงการบิดกุญแจสตาร์ท หรืออาจจะเตะยางหรือสวดมนต์คาถาวิเศษ ก็จะไม่ช่วยอะไร Termination condition จึงช่วยให้เราแยกแยะระหว่าง terminating loops (ลูปที่สิ้นสุด) ซึ่ง termination condition ในที่สุดก็กลายเป็นจริง กับ nonterminating loops (ลูปที่ไม่สิ้นสุด) ซึ่ง termination condition ยังคงเป็นเท็จตลอดไป

มีคำกล่าวกันว่าความบ้าคือการทำสิ่งเดิมซ้ำแล้วซ้ำเล่าและคาดหวังผลลัพธ์ที่แตกต่างออกไป 3 เราอาจถูกล่อลวงให้ตราหน้าว่าลูปที่ไม่สิ้นสุด (nonterminating loops) ว่าบ้า แต่ก็มีตัวอย่างของลูปที่ถูกต้องสมบูรณ์ซึ่งไม่สิ้นสุด ตัวอย่างเช่น เว็บเซอร์วิสคือลูปที่รับ request, ประมวลผล, แล้วก็ไปรับ request ถัดไป อย่างไม่สิ้นสุด อย่างไรก็ตาม เมื่อลูปเป็นส่วนหนึ่งของอัลกอริทึม—โดยเฉพาะเมื่อมันตามด้วยขั้นตอนอื่นๆ—เราคาดหวังว่ามันจะจบลงในที่สุด เพราะไม่อย่างนั้นขั้นตอนที่ตามหลังลูปก็จะไม่มีวันถูกประมวลผล และอัลกอริทึมก็จะไม่สิ้นสุดเช่นกัน

การสิ้นสุด (termination) เป็นหนึ่งในคุณสมบัติที่สำคัญที่สุดของลูป Termination condition เป็นตัวกำหนดว่าลูปจะสิ้นสุดหรือไม่ แต่ผลกระทบที่ body ของลูปมีต่อโลกต่างหากที่สำคัญต่อการสิ้นสุดของลูป โดยเฉพาะผลกระทบต่อส่วนต่างๆ ของโลกที่ termination condition ขึ้นอยู่กับการรายงานสภาพอากาศไม่ได้เปลี่ยนแปลงโลกมากนัก และดูเหมือนจะไม่น่าจะมีผลต่อ termination condition ที่ไม่รู้จักในลูปวันกราวด์ฮ็อกของฟิล คอนเนอร์ส ด้วยความหงุดหงิด เขาจึงลองทำอะไรที่รุนแรงมากขึ้นเรื่อยๆ รวมถึงการฆ่าตัวตายในรูปแบบต่างๆ และการฆ่าพักซะทอนี ฟิล โดยหวังอย่างสิ้นหวังว่าจะมีผลต่อโลกเพื่อให้ termination condition กลายเป็นจริงในที่สุด

Everything under Control (ทุกอย่างอยู่ภายใต้การควบคุม)

เมื่อวันกราวด์ฮ็อกเริ่มวนซ้ำ ฟิล คอนเนอร์สไม่ได้เป็นผู้ควบคุมชีวิตของเขาเลยแม้แต่น้อย ตรงกันข้าม เขาอยู่ภายใต้การควบคุมของลูปวันกราวด์ฮ็อก และเขาก็ตระหนักถึงข้อเท็จจริงนี้อย่างเจ็บปวด การอยู่ภายใต้การควบคุมของลูปในที่นี้หมายความว่า เขาอาศัยอยู่ภายใน body ของลูปที่ควบคุมว่าเมื่อใดการทำซ้ำจะสิ้นสุดลงและเมื่อใดเขาจะหนีออกไปได้

ลูปควบคุมว่า body ของมันจะถูกประมวลผลกี่ครั้ง แต่ผลของลูปนั้นได้มาจากขั้นตอนใน body ของมันเท่านั้น กล่าวอีกนัยหนึ่ง ลูปไม่ได้มีผลโดยตรงใดๆ แต่มีผลทางอ้อมผ่านการทำซ้ำของขั้นตอนใน body ของมัน เนื่องจากโดยทั่วไปแล้วจำนวนครั้งที่ขั้นตอนของอัลกอริทึมถูกประมวลผลนั้นมีความสำคัญ ลูปจึงใช้อิทธิพลผ่านจำนวนครั้งที่มันประมวลผล body ของมัน เนื่องจากลูปควบคุมผลของ body ของมัน (ผ่าน termination condition) มันจึงถูกเรียกว่า โครงสร้างควบคุม (control structure) ลูปคือโครงสร้างควบคุมสำหรับการประมวลผลกลุ่มของขั้นตอนอัลกอริทึมซ้ำๆ โครงสร้างควบคุมหลักอีกสองแบบคือ sequential composition และ conditional

Sequential composition (การประกอบแบบลำดับ) เชื่อมต่อสองกลุ่มของขั้นตอนเข้าเป็นลำดับขั้นตอนที่มีลำดับที่ ผมเคยใช้คำว่า and เพื่อจุดประสงค์นี้มาก่อน แต่เพื่อบ่งบอกว่าทั้งสองขั้นตอนต้องถูกประมวลผลตามลำดับ ไม่ใช่แบบขนาน อาจจะดีกว่าถ้าใช้คีย์เวิร์ดเช่น andThen หรือ followedBy อย่างไรก็ตาม เพื่อความง่ายและกระชับ ผมจะใช้สัญกรณ์ที่ใช้ในภาษาโปรแกรมมิ่งส่วนใหญ่ นั่นคือ การเชื่อมสองขั้นตอนด้วยเครื่องหมายอัฒภาค (;) สัญกรณ์นี้คล้ายกับการเขียนรายการสิ่งต่างๆ ยิ่งไปกว่านั้น มันสั้นและไม่เบี่ยงเบนความสนใจจากขั้นตอนจริงของอัลกอริทึม ตัวอย่างเช่น get up ; have breakfast หมายถึงให้ตื่นก่อนแล้วค่อยทานอาหารเช้า แน่นอนว่าลำดับของขั้นตอนนั้นสำคัญ และสำหรับบางคน have breakfast ; get up คือการเปลี่ยนกิจวัตรที่น่าต้อนรับในวันอาทิตย์ รูปแบบทั่วไปของ sequential composition คือ:

step ; step

ในที่นี้ step เป็น nonterminal ที่สามารถแทนที่ด้วยขั้นตอนเดี่ยวหรือขั้นตอนผสมใดๆ โดยเฉพาะอย่างยิ่ง step สามารถเป็น sequential composition ของขั้นตอนอื่นๆ ได้ ดังนั้น ถ้าคุณต้องการแทรกการอาบน้ำระหว่างการตื่นนอนกับการทานอาหารเช้า คุณสามารถใช้ sequential composition สองครั้งโดยขยาย step แรกเป็น get up; take a shower และขั้นที่สองเป็น have breakfast ซึ่งรวมกันแล้วได้ get up; take a shower; have breakfast . 4

เช่นเดียวกับตัวอย่างการพับกระดาษสองครั้ง "fold and fold" ซึ่งตอนนี้เราเขียนเป็น fold ; fold ขั้นตอนที่เชื่อมด้วย ; ไม่จำเป็นต้องต่างกัน การประมวลผลลูป repeat   fold   until   paper fits (หรือ repeat   fold three times ) ให้ผลลัพธ์การคำนวณเดียวกันกับลำดับ fold ; fold ; fold ซึ่งแสดงให้เห็นว่าลูปเป็นเครื่องมือในการอธิบายลำดับของการกระทำ การมีส่วนร่วมที่สำคัญของลูปคือมันสร้างลำดับของขั้นตอนที่มีความยาวตามต้องการในขณะที่ต้องกล่าวถึงการกระทำที่ต้องทำซ้ำเพียงครั้งเดียว

Conditional (เงื่อนไข) เลือกหนึ่งในสองกลุ่มของขั้นตอนเพื่อประมวลผลโดยขึ้นอยู่กับเงื่อนไข เช่นเดียวกับลูป มันใช้เงื่อนไขในการตัดสินใจ รูปแบบทั่วไปของ conditional คือ:

if   condition   then   step   else   step

เมื่อใดก็ตามที่พักซะทอนี ฟิลถูกถามให้ทำนายสภาพอากาศ โดยพื้นฐานแล้วเขาจะประมวลผลอัลกอริทึมรายงานสภาพอากาศดังนี้:

if   sunny   then   ประกาศฤดูหนาวอีกหกสัปดาห์   else   ประกาศฤดูใบไม้ผลิมาเร็ว

Conditional คือโครงสร้างควบคุมที่ช่วยให้อัลกอริทึมสามารถเลือกและตัดสินใจระหว่างขั้นตอนทางเลือกได้ Conditional ข้างต้นเป็นส่วนหนึ่งของลูปประจำปีสำหรับพักซะทอนี ฟิล และลูปรายวันสำหรับฟิล คอนเนอร์ส ซึ่งแสดงให้เห็นว่าโครงสร้างควบคุมสามารถรวมกันได้ในรูปแบบต่างๆ กล่าวคือ conditional สามารถเป็นส่วนหนึ่งของลูปหรือ sequential composition, ลูปสามารถเกิดขึ้นในทางเลือกของ conditional หรือเป็นส่วนหนึ่งของลำดับขั้นตอน และอื่นๆ

ขั้นตอนพื้นฐานของอัลกอริทึมก็เหมือนกับการเดินหมากในเกม (เช่น การส่งบอลหรือการยิงประตูในฟุตบอล หรือการโจมตีตัวหมากหรือการเข้าปราสาทในหมากรุก) จากนั้นโครงสร้างควบคุมจะกำหนดกลยุทธ์ในเกมเหล่านั้น ตัวอย่างเช่น repeat   pass   until   in front of goal (หรือถ้าคุณคือลิโอเนล เมสซี repeat   dribble   until   in front of goal ) นั่นคือ โครงสร้างควบคุมจะประกอบการเคลื่อนไหวพื้นฐานเข้าเป็นเกมเพลย์ที่ใหญ่ขึ้น

ดังที่แสดงใน บทที่ 8 มีสัญกรณ์มากมายในการอธิบายดนตรี เช่นเดียวกัน ก็มีสัญกรณ์ที่แตกต่างกันสำหรับอัลกอริทึม ภาษาโปรแกรมมิ่งแต่ละภาษาเป็นตัวอย่างของสัญกรณ์เฉพาะสำหรับอัลกอริทึม และแม้ว่าภาษาต่างๆ อาจแตกต่างกันอย่างมากในโครงสร้างควบคุมเฉพาะที่พวกมันมีให้ แต่ส่วนใหญ่ก็มีลูป, conditional, และ composition ในบางรูปแบบ 5 สัญกรณ์หนึ่งที่แสดงให้เห็นความแตกต่างระหว่างโครงสร้างควบคุมได้ดีคือ flowchart Flowchart (ผังงาน) แสดงอัลกอริทึมเป็นกล่องที่เชื่อมต่อด้วยลูกศร การกระทำพื้นฐานจะแสดงภายในกล่อง และการตัดสินใจจะอยู่ในรูปทรงสี่เหลี่ยมขนมเปียกปูน ลูกศรบ่งชี้ว่าการคำนวณดำเนินไปอย่างไร สำหรับ sequential composition นี่หมายถึงการเดินตามลูกศรเดี่ยวจากกล่องหนึ่งไปอีกกล่องหนึ่ง แต่สำหรับ conditional และ loop ซึ่งเงื่อนไขของมันมีลูกศรขาออกสองเส้น การเลือกว่าจะเดินตามลูกศรใดขึ้นอยู่กับเงื่อนไข ตัวอย่างบางส่วนของสัญกรณ์ flowchart แสดงใน รูปที่ 10.1 .

รูปที่ 10.1 สัญกรณ์ Flowchart สำหรับโครงสร้างควบคุม ซ้าย: ลำดับขั้นตอนที่ฟิล คอนเนอร์สทำทุกเช้า กลาง: Conditional แสดงการตัดสินใจที่พักซะทอนี ฟิลต้องเผชิญในแต่ละวันกราวด์ฮ็อก ขวา: ลูปที่แสดงชีวิตของฟิล คอนเนอร์สระหว่างภาพยนตร์ Groundhog Day . ลูกศร "no" และลูกศรที่ไปยังเงื่อนไขรวมกันเป็นวงจรผ่านสองโหนด

เป็นที่น่าสนใจว่าสัญกรณ์ของ conditional และ loop นั้นคล้ายคลึงกันมาก ทั้งสองประกอบด้วยเงื่อนไขที่มีทางดำเนินการต่อได้สองทาง ความแตกต่างที่สำคัญเพียงอย่างเดียวคือเส้นทาง "no" จากเงื่อนไขในลูปนำไปสู่ขั้นตอนที่ย้อนกลับไปยังเงื่อนไขอีกครั้ง วงจรที่เกิดขึ้นนี้ให้คำอธิบายที่เป็นภาพที่ดีของชื่อ loop สำหรับโครงสร้างควบคุมนี้

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

Flowcharts ค่อนข้างเป็นที่นิยมในยุค 1970 และบางครั้งก็ยังคงถูกใช้สำหรับการจัดทำเอกสารซอฟต์แวร์ แต่ปัจจุบันไม่ค่อยถูกใช้เป็นสัญกรณ์สำหรับการเขียนโปรแกรมแล้ว เหตุผลหนึ่งคือสัญกรณ์นี้ไม่สามารถขยายขนาดได้ดีนัก แม้แต่ flowchart ขนาดปานกลางก็อ่านยาก—การมีลูกศรมากมายจนรกถูกเรียกว่า spaghetti code ยิ่งไปกว่านั้น ความคล้ายคลึงกันระหว่างสัญกรณ์ของ conditional กับ loop แม้จะมีประโยชน์ในการแสดงความสัมพันธ์ของพวกมัน แต่ก็ทำให้ยากต่อการระบุและแยกแยะระหว่างโครงสร้างควบคุมใน flowcharts

โครงสร้างควบคุมที่นำเสนอในที่นี้คือโครงสร้างที่ใช้โดยอัลกอริทึมสำหรับคอมพิวเตอร์เครื่องเดียว ไมโครโปรเซสเซอร์สมัยใหม่มาพร้อมกับหลายคอร์ที่สามารถประมวลผลการดำเนินการแบบขนานได้ มนุษย์ก็สามารถคำนวณแบบขนานได้เช่นกัน โดยเฉพาะเมื่ออยู่ในทีม เพื่อใช้ประโยชน์จากความขนาน อัลกอริทึมต้องการโครงสร้างควบคุมที่ออกแบบมาโดยเฉพาะสำหรับจุดประสงค์นี้ ตัวอย่างเช่น เราสามารถเขียน walk ‖ chew gum เพื่อสั่งให้ใครสักคนเดินและเคี้ยวหมากฝรั่งไปพร้อมกัน ซึ่งแตกต่างจาก walk ; chew gum ซึ่งหมายถึงเดินก่อนแล้วค่อยเคี้ยวหมากฝรั่ง

Parallel composition มีประโยชน์เมื่อผลลัพธ์สองอย่างที่ไม่ขึ้นต่อกันถูกต้องการคำนวณอื่น ตัวอย่างเช่น เชอร์ล็อก โฮล์มส์และวัตสันมักจะแบ่งงานสืบสวนในการคลี่คลายคดี ในทางกลับกัน เราไม่สามารถตื่นนอนและอาบน้ำพร้อมกันได้ การกระทำสองอย่างนี้ต้องถูกประมวลผลตามลำดับอย่างเคร่งครัด (และลำดับก็มีความสำคัญ)

ที่เกี่ยวข้องกับการคำนวณแบบขนานคือการคำนวณแบบกระจาย (distributed computing) ซึ่งการคำนวณเกิดขึ้นผ่านการสื่อสารระหว่าง agent ที่มีปฏิสัมพันธ์กัน ตัวอย่างเช่น เมื่อฟิล คอนเนอร์สและทีมของเขาสร้างรายงานเกี่ยวกับการพยากรณ์ของกราวด์ฮ็อก พวกเขาต้องซิงโครไนซ์การทำงานของกล้องกับการพูดของฟิล คอนเนอร์ส อัลกอริทึมสำหรับอธิบายการประสานงานนี้ต้องมีโครงสร้างควบคุมของตัวเอง โดยเฉพาะสำหรับการส่งและรับข้อความ

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

A Loop Is a Loop Is a Loop (ลูปคือลูปคือลูป)

ในความพยายามที่จะหนีจากลูปวันกราวด์ฮ็อก ฟิล คอนเนอร์สกำลังพยายามค้นหา termination condition ของมัน นี่เป็นวิธีที่ค่อนข้างผิดปกติในการจัดการกับอัลกอริทึมโดยทั่วไป หรือกับลูปโดยเฉพาะ โดยปกติ เราจะแสดงอัลกอริทึมและประมวลผลมันเพื่อให้ได้การคำนวณที่ต้องการ ในทางตรงกันข้าม ฟิล คอนเนอร์สเป็นส่วนหนึ่งของการคำนวณซึ่งอัลกอริทึมที่อธิบายมันเขาไม่รู้ ในการค้นหาการกระทำที่จะทำให้ termination condition กลายเป็นจริง เขากำลังพยายาม reverse-engineer อัลกอริทึม

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

ด้วยความสำคัญของลูป จึงไม่น่าแปลกใจที่มีวิธีการอธิบายลูปที่แตกต่างกัน โครงร่างลูปที่เราใช้มาจนถึงตอนนี้ repeat   step   until   condition , เรียกว่า repeat loop (ลูปแบบทำซ้ำ) มันมีคุณสมบัติที่ body ของลูปจะถูกประมวลผลอย่างน้อยหนึ่งครั้ง ไม่ว่า termination condition จะเป็นอย่างไรก็ตาม ในทางกลับกัน while loop (ลูปแบบwhile) จะประมวลผล body ก็ต่อเมื่อเงื่อนไขของมันเป็นจริง ดังนั้นมันอาจไม่ถูกประมวลผลเลยก็ได้ while loop มีรูปแบบดังนี้:

while   condition   do   step

แม้ว่าทั้งสองลูปจะถูกควบคุมโดยเงื่อนไข แต่บทบาทของเงื่อนไขในแต่ละลูปนั้นแตกต่างกัน ในขณะที่เงื่อนไขควบคุมการออกจาก repeat loop แต่มันควบคุมการเข้า (หรือกลับเข้า) ของ while loop กล่าวอีกนัยหนึ่ง ถ้าเงื่อนไขเป็นจริง repeat loop จะสิ้นสุด ในขณะที่ while loop จะดำเนินการต่อ ถ้าเงื่อนไขเป็นเท็จ repeat loop จะดำเนินการต่อ ในขณะที่ while loop จะสิ้นสุด 6 ความแตกต่างนี้ยังถูกเน้นโดยสัญกรณ์ flowchart สำหรับลูปทั้งสอง ดังแสดงใน รูปที่ 10.2 .

แม้จะมีพฤติกรรมที่ดูแตกต่างกัน แต่เราสามารถแสดง repeat loop โดยใช้ while loop และในทางกลับกันได้ สำหรับสิ่งนี้ เราต้อง negate เงื่อนไข นั่นคือ เปลี่ยนเงื่อนไขให้เป็นจริงในกรณีเดียวกับที่เงื่อนไขเดิมเป็นเท็จ ตัวอย่างเช่น termination condition สำหรับ repeat loop วันกราวด์ฮ็อก "การเป็นคนดี" กลายเป็น entry condition "การไม่เป็นคนดี" หรือ "การเป็นคนไม่ดี" สำหรับ while loop ที่สอดคล้องกัน ยิ่งไปกว่านั้น เราต้องระมัดระวังเพื่อให้แน่ใจว่ามีจำนวน iteration เท่ากัน ตัวอย่างเช่น repeat loop ทำให้ฟิล คอนเนอร์สประสบกับวันกราวด์ฮ็อกอย่างน้อยหนึ่งครั้งไม่ว่าจะอย่างไรก็ตาม ในขณะที่ while loop จะทำเช่นนั้นก็ต่อเมื่อเขาเป็นคนไม่ดีเท่านั้น เนื่องจากนี่เป็นกรณีในเรื่อง ลูปทั้งสองจึงมีพฤติกรรมเหมือนกัน

การแสดงภาษาทำให้เราสามารถแสดงความเท่าเทียมระหว่างลูปได้อย่างเป็นทางการมากขึ้นผ่านสมการง่ายๆ:

รูปที่ 10.2 สัญกรณ์ Flowchart แสดงพฤติกรรมที่แตกต่างของ repeat และ while loops ซ้าย: Flowchart ของ repeat loop ขวา: Flowchart ของ while loop

repeat   step   until   condition = step ; while   not condition   do   step

อีกครั้ง step เริ่มต้นก่อน while loop เป็นสิ่งจำเป็นเพราะ body ของ while loop อาจไม่ถูกประมวลผลเลย แตกต่างจาก body ของ repeat loop ที่ถูกประมวลผลอย่างน้อยหนึ่งครั้ง ความแตกต่างระหว่างลูปทั้งสองบางครั้งมีความสำคัญจริงๆ ลองพิจารณาตัวอย่างอัลกอริทึมของฮันเซลกับเกรเทล เมื่อแสดงเป็น repeat loop จะอ่านได้ดังนี้:

repeat   find pebble   until   at home

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

วิธีการอธิบายลูปอีกแบบหนึ่งสามารถทำได้โดยใช้การเรียกซ้ำ (recursion) ผมจะอธิบาย recursion ในรายละเอียดใน บทที่ 12 แต่แนวคิดพื้นฐานนั้นเข้าใจง่าย (อันที่จริง recursion ถูกอธิบายไว้ใน connection กับอัลกอริทึม divide-and-conquer ใน บทที่ 6 ) สำหรับการอธิบายอัลกอริทึมแบบ recursion อันดับแรกเราต้องตั้งชื่อให้มัน จากนั้นใช้ชื่อนั้นในนิยามของมันเอง ลูปวันกราวด์ฮ็อกจึงสามารถอธิบายได้ดังนี้:

GroundhogDay = experience the day ; if   good person?   then   do nothing   else   GroundhogDay

นิยามนี้จำลอง repeat loop ได้อย่างมีประสิทธิภาพ: หลังจากใช้ชีวิตผ่านวันนั้น conditional จะตรวจสอบ termination condition ถ้ามันเป็นเท็จ การคำนวณก็จะสิ้นสุดลงโดยไม่ทำอะไรเลย มิฉะนั้น อัลกอริทึมจะถูกประมวลผลอีกครั้ง การประมวลผลแบบ recursion ของอัลกอริทึมก็เหมือนกับการกระโดดไปยังจุดเริ่มต้นของลำดับและทำให้เกิดการประมวลผลลูปซ้ำอีกครั้ง

คำอธิบายลูปทั้งหมดที่เราได้พบมา (repeat, while, และ recursion) มีจุดร่วมคือการสิ้นสุดของมันถูกควบคุมโดยเงื่อนไขที่ถูกประเมินใหม่ก่อนหรือหลังการประมวลผล body แต่ละครั้ง การสิ้นสุดของลูปขึ้นอยู่กับว่า body มีผลที่ทำให้ termination condition กลายเป็นจริงในที่สุด (หรือ entry condition กลายเป็นเท็จ ในกรณีของ while loop) นั่นหมายความว่าเราไม่ทราบล่วงหน้าว่าลูปจะผ่านไปกี่ iteration มันไม่ชัดเจนด้วยซ้ำว่าลูปใดๆ จะสิ้นสุดหรือไม่ ความไม่แน่นอนนี้แท้จริงแล้วเป็นส่วนสำคัญของลูปวันกราวด์ฮ็อกที่ฟิล คอนเนอร์สประสบ

แต่สำหรับการคำนวณบางอย่างที่อธิบายโดยลูป จะมีความชัดเจนว่าควรประมวลผลลูปกี่ครั้ง ตัวอย่างเช่น ถ้างานคือการคำนวณกำลังสองของจำนวนธรรมชาติสิบตัวแรก ก็ชัดเจนว่าการคำนวณนี้สามารถทำได้โดยลูปที่ทำซ้ำการดำเนินการยกกำลังสองสิบครั้งพอดี หรือจำอัลกอริทึมการพับกระดาษเพื่อให้ใส่ในซองจดหมายได้ ซึ่งอธิบายโดยลูปที่ถูกประมวลผลสองครั้งพอดี สำหรับกรณีเช่นนี้ เราใช้ for loops (ลูปแบบ for) ซึ่งมีรูปแบบทั่วไปดังนี้: 7

for   number   times do   step

โดยใช้โครงร่างนี้ ลูปการพับกระดาษจะแสดงเป็น for 2 times do   fold ข้อดีของ for loop คือมันชัดเจนแม้ก่อนที่จะถูกประมวลผลว่าจะดำเนินการกี่ iteration ซึ่งไม่ใช่กรณีของลูปอื่นๆ เพราะเราจะรู้ก็ต่อเมื่อประมวลผลลูปเท่านั้น นี่คือความแตกต่างที่สำคัญอย่างยิ่ง เนื่องจาก for loop รับประกันว่าจะสิ้นสุด ในขณะที่ลูปอื่นๆ อาจทำงานตลอดไป (ดู บทที่ 11 )

ที่เกี่ยวข้องอย่างใกล้ชิดคือคำถามเรื่องระยะเวลาทำงาน (runtime) ของลูป เป็นที่ชัดเจนว่าลูปที่ถูกประมวลผล 100 ครั้งใช้เวลาอย่างน้อย 100 ขั้นตอน กล่าวอีกนัยหนึ่ง ลูปเป็นแบบเชิงเส้น (linear) ตามจำนวน iteration ของมัน และนี่เป็นกรณีสำหรับลูปทุกประเภท นอกจากจำนวน iteration แล้ว เรายังต้องพิจารณาระยะเวลาทำงานของ body ของลูปด้วย ระยะเวลาทำงานของลูปคือจำนวน iteration คูณกับระยะเวลาทำงานของ body ตัวอย่างเช่น selection sort คือลูปที่ body ของมันประกอบด้วยการค้นหาค่าต่ำสุดในลิสต์ ลูปเป็นแบบเชิงเส้นตามขนาดของลิสต์ และ body ใช้เวลาโดยเฉลี่ยตามสัดส่วนของความยาวลิสต์ครึ่งหนึ่ง ดังนั้น ระยะเวลาทำงานของ selection sort จึงเป็นแบบกำลังสอง (quadratic) ตามขนาดของลิสต์

เนื่องจาก for loop ดูเหมือนจะมีพฤติกรรมที่คาดเดาได้มากกว่าลูปประเภทอื่นๆ มาก ทำไมไม่ใช้ for loop เพียงอย่างเดียวล่ะ? เหตุผลคือ for loop มีความสามารถในการแสดงออกน้อยกว่า while loop และ repeat loop (และ recursion) กล่าวคือ มีปัญหาที่สามารถแก้ไขได้ด้วย while loop หรือ repeat loop แต่ไม่สามารถแก้ไขได้ด้วย for loop ลูปวันกราวด์ฮ็อกเป็นตัวอย่างที่เราไม่รู้ตั้งแต่แรก (อย่างน้อยก็ไม่ใช่สำหรับฟิล คอนเนอร์ส) ว่าต้องใช้กี่ iteration มันง่ายที่จะเห็นว่า for loop ใดๆ สามารถแสดงด้วย while (หรือ repeat) loop โดยการรักษาตัวนับ for loop ไว้อย่างชัดเจน แต่ในทางกลับกันไม่เป็นความจริง เพราะเราไม่สามารถเห็นได้ทันทีว่า while loop หรือ repeat loop ต้องใช้กี่ iteration ก่อนที่จะสิ้นสุด

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