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

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

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

ซ้ำแล้วซ้ำอีก (Forever and a Day)

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

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

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

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

Ralph: คิดว่าคงประมาณนั้นสำหรับผมแหละ.

การแลกเปลี่ยนนี้สามารถสรุปได้ในลักษณะชีวิตที่เป็น loop ดังนี้:

ทำซ้ำ กิจวัตรประจำวัน จนกว่า คุณจะตาย

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

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

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

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

ทำซ้ำ รายงานสภาพอากาศ จนกว่า ตลอดไป

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

ฝน เมฆครึ้ม แดด แดด พายุฝนฟ้าคะนอง แดด …

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

ทำซ้ำ รายงานสภาพอากาศ จนกว่า 'บางเงื่อนไขที่ซ่อนอยู่'

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

Groundhog Day loop เป็นกรณีตัวอย่างของสูตรลูปทั่วไปต่อไปนี้:

ทำซ้ำ ขั้นตอน จนกว่า เงื่อนไข

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

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

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

การสิ้นสุดเป็นหนึ่งในคุณสมบัติที่สำคัญที่สุดของลูป เงื่อนไขการสิ้นสุดกำหนดว่าลูปจะจบหรือไม่ แต่สิ่งที่สำคัญต่อการสิ้นสุดคือผลที่ body ของลูปมีต่อโลก โดยเฉพาะผลต่อส่วนของโลกที่เงื่อนไขการสิ้นสุดนั้นอาศัยอยู่ การรายงานสภาพอากาศไม่ได้เปลี่ยนแปลงโลกมากนักและดูไม่น่าจะมีผลต่อเงื่อนไขการสิ้นสุดที่ไม่ทราบตัวในลูปของ Phil Connors ในความสิ้นหวัง เขาลองทำสิ่งสุดโต่งมากขึ้น รวมทั้งการฆ่าตัวตายรูปแบบต่างๆ และการพยายามฆ่า Punxsutawney Phil โดยหวังว่าการกระทำเหล่านั้นจะเปลี่ยนโลกให้เงื่อนไขการสิ้นสุดเป็นจริงในที่สุด

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

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

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

Sequential composition เชื่อมสอง (กลุ่มของ) ขั้นตอนให้เป็นลำดับของขั้นตอน ก่อนหน้านี้ผมเคยใช้คำว่า and เพื่อจุดประสงค์นี้ แต่เพื่อระบุให้ชัดเจนว่าทั้งสองขั้นตอนจะถูกปฏิบัติเป็นลำดับ ไม่ใช่พร้อมกัน อาจใช้คีย์เวิร์ดอย่าง andThen หรือ followedBy อย่างไรก็ตาม เพื่อความเรียบง่ายและกระชับ ผมยึดสัญลักษณ์ที่ภาษาโปรแกรมส่วนใหญ่ใช้ คือการเชื่อมสองขั้นตอนด้วย semicolon ซึ่งคล้ายกับการเขียนรายการสิ่งของ นอกจากนี้ยังสั้นและไม่รบกวนขั้นตอนหลักของอัลกอริทึม เช่น 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 และ step ที่สองเป็น have breakfast ซึ่งรวมกันเป็น get up; take a shower; have breakfast

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

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

if condition then step else step

เมื่อใดก็ตามที่ Punxsutawney Phil ถูกถามให้ทำนายอากาศ เขาจะแทบจะรันอัลกอริทึมการรายงานสภาพอากาศต่อไปนี้:

if sunny then announce six more weeks of winter else announce early spring

Conditional เป็น control structure ที่อนุญาตให้อัลกอริทึมเลือกทำงานระหว่างตัวเลือกที่ต่างกัน ข้อความ conditional ข้างต้นเป็นส่วนหนึ่งของลูประดับปีสำหรับ Punxsutawney Phil และลูประดับวันสำหรับ Phil Connors ซึ่งแสดงให้เห็นว่าควบคุมโครงสร้างสามารถรวมกันได้อย่างอิสระ กล่าวคือ conditional สามารถเป็นส่วนหนึ่งของลูปหรือ sequential composition ได้ ลูปสามารถอยู่ในทางเลือกของ conditional หรือเป็นส่วนหนึ่งของลำดับของขั้นตอน และอื่นๆ

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

ตามที่แสดงใน [chapter 8] มีสัญลักษณ์หลายรูปแบบสำหรับบรรยายดนตรี ในทำนองเดียวกันก็มีสัญลักษณ์ต่างๆ สำหรับอัลกอริทึม ภาษาโปรแกรมแต่ละภาษาคือตัวอย่างของสัญลักษณ์เฉพาะสำหรับอัลกอริทึม และถึงแม้ภาษาจะต่างกันใน control structures ที่ให้มา ส่วนใหญ่ก็มีรูปแบบของ loop, conditional และ composition สัญลักษณ์ที่ชี้ให้เห็นความแตกต่างระหว่าง control structures ได้อย่างชัดเจนคือ flowchart flowchart ซึ่งแสดงอัลกอริทึมเป็นกล่องที่เชื่อมต่อด้วยลูกศร การกระทำพื้นฐานจะแสดงภายในกล่อง และการตัดสินใจถูกใส่ในรูปเพชร ลูกศรบอกว่าการคำนวณดำเนินต่ออย่างไร สำหรับ sequential composition หมายถึงการตามลูกศรจากกล่องหนึ่งไปยังอีกกล่อง แต่สำหรับ conditionals และ loops ซึ่งเงื่อนไขมีสองลูกศรออกไป การเลือกว่าจะตามลูกศรอันใดขึ้นอยู่กับเงื่อนไข ตัวอย่างของสัญลักษณ์ flowchart แสดงใน [figure 10.1]

Figure 10.1 สัญลักษณ์ flowchart สำหรับ control structures. ซ้าย: ลำดับของขั้นตอนที่ Phil Connors ทำทุกเช้า. กลาง: conditional ที่แสดงการตัดสินใจซึ่ง Punxsutawney Phil ต้องเผชิญในแต่ละ Groundhog Day. ขวา: ลูปที่สื่อถึงชีวิตของ Phil Connors ในภาพยนตร์ Groundhog Day. ลูกศร "no" และลูกศรที่ชี้กลับไปยังเงื่อนไขสร้างวงวนผ่านสองโหนด.

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

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

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

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

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

ที่เกี่ยวข้องกับ parallel computing คือ distributed computing ซึ่งการคำนวณเกิดขึ้นผ่านการสื่อสารระหว่างเอเจนต์ที่ปฏิสัมพันธ์กัน ตัวอย่างเช่น เมื่อ Phil Connors และทีมของเขาสร้างรายงานเกี่ยวกับการพยากรณ์ของ groundhog พวกเขาต้องประสานงานการทำงานของกล้องกับการพูดของ Phil Connors อัลกอริทึมสำหรับอธิบายการประสานงานนี้จึงต้องมี control structures ของตัวเอง โดยเฉพาะสำหรับการส่งและรับข้อความ

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

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

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

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

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

while condition do step

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

แม้จะมีพฤติกรรมที่ดูต่างกันอย่างชัดเจน เราสามารถแสดง repeat loop ด้วย while loop ได้ และในทางกลับกันได้เช่นกัน โดยต้องทำการปฏิเสธเงื่อนไข กล่าวคือ แปลงเงื่อนไขให้เป็นจริงเมื่อกรณีเดิมเป็นเท็จ ตัวอย่างเช่น เงื่อนไขการสิ้นสุดสำหรับลูป Groundhog Day ที่ว่า “เป็นคนดี” จะกลายเป็นเงื่อนไขการเข้า (entry condition) ว่า “ไม่เป็นคนดี” หรือ “เป็นคนไม่ดี” สำหรับ while loop ที่สอดคล้องกัน นอกจากนี้ต้องระมัดระวังให้จำนวน iteration เท่ากัน เช่น repeat loop ให้ Phil Connors สัมผัส Groundhog Day อย่างน้อยหนึ่งครั้งเสมอ ในขณะที่ while loop จะทำเช่นนั้นก็ต่อเมื่อเขาเป็นคนไม่ดี เนื่องจากในเรื่องเขาเป็นคนไม่ดี ทั้งสองลูปจึงมีพฤติกรรมเหมือนกัน

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

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

ทำซ้ำ ค้นหาก้อนกรวด จนกว่า จะถึงบ้าน

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

อีกวิธีหนึ่งในการอธิบายลูปคือการใช้ recursion ผมจะอธิบาย recursion อย่างละเอียดใน [chapter 12] แต่แนวคิดพื้นฐานเข้าใจได้ง่าย (จริงๆ แล้ว recursion ถูกอธิบายในบริบทของ divide-and-conquer ใน [chapter 6] ) สำหรับการอธิบายแบบ recursive ของอัลกอริทึม เราต้องตั้งชื่อนิยามก่อน แล้วใช้ชื่อนั้นในคำนิยามของตัวมันเอง ดังนั้น Groundhog Day loop จึงสามารถอธิบายได้ดังนี้:

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

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

ลักษณะร่วมของคำอธิบายลูปต่างๆ (repeat, while, recursion) คือการที่การสิ้นสุดถูกควบคุมโดยเงื่อนไขซึ่งถูกประเมินใหม่ก่อนหรือหลังแต่ละครั้งที่ body ถูกปฏิบัติ การสิ้นสุดของลูปขึ้นอยู่กับ body ว่ามีผลอย่างไรต่อโลกจนทำให้เงื่อนไขการสิ้นสุดเป็นจริง (หรือทำให้เงื่อนไขการเข้าเป็นเท็จ ในกรณีของ while) ซึ่งหมายความว่าไม่ทราบล่วงหน้าว่าลูปจะวนกี่ครั้ง; บางครั้งไม่แน่ชัดด้วยซ้ำว่าลูปนั้นจะสิ้นสุดหรือไม่ ความไม่แน่นอนนี้เป็นส่วนสำคัญของ Groundhog Day loop ที่ Phil Connors พบเจอ

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

for number times do step

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

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

ถึงแม้ for loop จะดูคาดการณ์ได้กว่าลูปอื่นๆ ทำไมจึงไม่นำ for loops มาใช้ทั้งหมด เหตุผลคือ for loops มีความสามารถในการแสดงผล (expressiveness) น้อยกว่า while และ repeat (รวมถึง recursion) กล่าวคือมีปัญหาบางอย่างที่แก้ได้ด้วย while หรือ repeat แต่ไม่สามารถแก้ได้ด้วย for loop Groundhog Day loop เป็นตัวอย่างที่เราไม่ทราบตอนเริ่มต้น (อย่างน้อยสำหรับ Phil Connors) ว่าต้องใช้กี่ iteration จะเห็นได้ง่ายว่า for loop ใดๆ สามารถแทนด้วย while (หรือ repeat) ได้โดยการดูแล counter ของ for loop อย่างชัดเจน แต่กลับกันไม่เป็นจริงเพราะเราไม่สามารถรู้ทันทีว่าลูป while หรือ repeat ต้องการกี่ iteration ก่อนจะสิ้นสุด

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