การเรียกซับรูทีนในโลกยุคโบราณ: ก่อนที่คอมพิวเตอร์จะมีสแตกหรือฮีป

 (devblogs.microsoft.com)
2 คะแนน โดย GN⁺ 2024-04-04 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

การเรียกซับรูทีนในยุคโบราณที่คอมพิวเตอร์ยังไม่มีสแตกและฮีป

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

การเรียกฟังก์ชันโดยไม่มีสแตก

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

การปรับแต่ง ABI

  • เพื่อเพิ่มประสิทธิภาพของ ABI ค่าบางส่วนจะถูกส่งผ่านรีจิสเตอร์แทนตัวแปรโกลบอล
  • โปรเซสเซอร์ส่วนใหญ่มีรีจิสเตอร์ "ลิงก์" และคำสั่ง "branch with link" ซึ่งจะตั้งค่ารีจิสเตอร์ลิงก์ให้เป็นที่อยู่ถัดจากคำสั่ง "branch with link" โดยอัตโนมัติ
  • มีการปรับแต่ง calling convention ให้ส่งพารามิเตอร์สองตัวแรกผ่านรีจิสเตอร์

ความเป็นไปไม่ได้ของการเรียกซ้ำแบบรีเคอร์ซีฟ

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

บทสนทนาโบนัส

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

ความเห็นของ GN⁺

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

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-04-04
ความคิดเห็นจาก Hacker News

  • รีวิวเชิงบวกต่อหนังสือ "The Art of Computer Programming"

    • หนังสือเล่มนี้แม้จะดูเก่า แต่ครอบคลุมอัลกอริทึมที่จัดการอาร์เรย์แบบไดนามิกและโครงสร้างข้อมูลต่าง ๆ ตั้งแต่ก่อนมี heap หรือ stack
    • หนังสือยังอธิบายเรื่อง garbage collection และการติดตั้งใช้งาน Lisp list พร้อมมอบความรู้เชิงสารานุกรมแบบที่ Knuth ทำให้ผู้อ่านตั้งตารอ

  • คำอธิบายเกี่ยวกับวิธีที่อาร์เรย์สองชุดแชร์พื้นที่เดียวกันแบบไดนามิก

    • อาร์เรย์หนึ่งขยายตามปกติจากตำแหน่ง #0 และอีกอาร์เรย์หนึ่งขยายย้อนกลับจากตำแหน่ง #End ทำให้อาร์เรย์ทั้งสองแชร์พื้นที่ที่จัดสรรแบบคงที่ได้อย่างมีประสิทธิภาพ
    • วิธีนี้สามารถขยายไปใช้กับหลายอาร์เรย์ได้ แต่เมื่อถึงจุดนั้น การใช้ Malloc และ Realloc อาจจะดีกว่า

  • แชร์ลิงก์เรื่องเล่าสนุก ๆ ว่าการนำ recursive function เข้าสู่ภาษา ALGOL เคยเป็นประเด็นถกเถียง

    • มีการแชร์ลิงก์เรื่องราวประวัติศาสตร์ที่น่าสนใจเกี่ยวกับการที่ recursion ถูกนำเข้าสู่ภาษาโปรแกรมอย่างไร

  • แชร์ประสบการณ์การเขียน Forth interpreter สำหรับเครื่อง SUBLEQ และเครื่อง bit-serial

    • เครื่องทั้งสองแบบนี้ไม่มี function call stack ซึ่งเป็นองค์ประกอบสำคัญของ Forth
    • SUBLEQ ไม่อนุญาต indirect load และ store และต้องใช้ self-modifying code เพื่อทำงานที่ไม่ปกติ
    • มีการสร้าง virtual machine ขึ้นมาเพื่อทำหน้าที่เหล่านี้ และรองรับ cooperative multithreading
    • หากจำเป็น heap จะถูกเขียนด้วย Forth และยังมีการคำนวณ floating point ที่ติดตั้งใช้งานเป็นฟังก์ชันซอฟต์แวร์ด้วย

  • คำอธิบายเกี่ยวกับวิวัฒนาการทางเทคนิคของการเรียก subroutine บนโปรเซสเซอร์ PDP-8

    • ในช่วงแรก คำสั่ง JMS จะเก็บ return address ไว้ในคำแรกของฟังก์ชัน
    • ต่อมามีการใช้ตำแหน่ง auto-increment เพื่อสร้าง stack แบบง่าย ๆ และให้ function prologue/epilogue จัดการ stack นี้ด้วยตนเองเพื่อรองรับ recursion เต็มรูปแบบ
    • หลังจากนั้นมีการเพิ่ม hardware stack เข้าไปในการติดตั้งใช้งานไมโครโปรเซสเซอร์เพื่อปรับปรุงประสิทธิภาพ

  • แชร์ความชอบเรื่อง recursion จากผู้ใช้ที่มีประสบการณ์กับ functional programming มาอย่างยาวนาน

    • แม้จะรู้วิธีแปลงอัลกอริทึมแบบ recursion ให้เป็นแบบ iteration แต่ก็ยังชอบ recursion มากกว่า
    • ในกรณีส่วนใหญ่ recursion เร็วพออยู่แล้ว และจะยิ่งดีขึ้นหากคอมไพเลอร์รองรับ tail recursion
    • เจ้าตัวพยายามเรียนรู้ว่าในอดีตมีการเขียนโปรแกรมกันอย่างไรผ่านการแฮ็กเกมบน Commodore 64

  • แชร์ประสบการณ์ออกแบบ RS232 serial multiplexer ราวปี 1991

    • เป็นการออกแบบฮาร์ดแวร์โดยใช้โปรเซสเซอร์ Z80, EPROM และอุปกรณ์ serial Z80-SIO
    • เนื่องจากไม่มี stack จึงใช้วิธี preload return address ไว้ใน register pair สำหรับการเรียกฟังก์ชัน

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

    • สิ่งนี้นำไปสู่ "bugs and limitations"

  • คำอธิบายเกี่ยวกับยุคที่ไม่สามารถใช้ recursion ได้ แต่ยังใช้ tail recursion ได้

    • นอกจาก branch_with_link ที่ใช้สำหรับการเรียกครั้งแรกแล้ว จะต้องใช้ branch ปกติ

  • อธิบายวิธีที่คอมไพเลอร์ของ Enhanced GNU Awk จัดสรรตัวแปร global ลับให้กับบล็อก @let ที่อยู่นอกฟังก์ชัน

    • ตัวแปรเหล่านี้จะถูกนำกลับมาใช้ซ้ำให้มากที่สุดเท่าที่ทำได้

  • กล่าวถึงโพสต์ที่บรรยายโลกของบทความ "Goto considered harmful"

    • คนส่วนใหญ่รู้จักแค่ชื่อเรื่องเท่านั้น และตัวบทความโต้แย้งเรื่องการให้ subroutine มีจุดเข้าเพียงจุดเดียว
    • บางครั้งก็มีการเขียน assembly code ให้กระโดดเข้าไปยัง subroutine อื่น แต่ก็ไม่ได้อยากให้ assembly code ทุกชิ้นเป็นแบบนั้น