Lời gọi subroutine trong thế giới cổ đại: Trước khi máy tính có stack hay heap

Lời gọi subroutine thời cổ đại khi máy tính chưa có stack và heap

• Trong điện toán hiện đại, stack và heap được xem là điều hiển nhiên, nhưng ở những ngày đầu của điện toán, máy tính vẫn hoạt động mà không có stack hay heap.
• Không khó để hình dung việc tính toán không có cấp phát bộ nhớ động. Bạn phải dùng các bộ đệm bộ nhớ kích thước cố định cho mọi thứ.
• Khi cần xử lý dữ liệu có kích thước biến đổi, người ta sẽ dành trước một bộ đệm kích thước cố định đủ lớn để chứa dữ liệu có thể dự đoán được.
• Có thể cung cấp các thiết lập lúc biên dịch để phía khách hàng điều chỉnh dung lượng tối đa, hoặc viết một bộ cấp phát tùy chỉnh có thể "cấp phát" và "giải phóng" bộ nhớ từ các bộ đệm kích thước cố định.

Gọi hàm mà không có stack

• Trình biên dịch định nghĩa các biến toàn cục bí mật cho tham số đầu vào, địa chỉ trả về và biến cục bộ của từng hàm.
• Để tạo một lời gọi hàm, trình biên dịch gán giá trị tham số vào các biến toàn cục bí mật tương ứng, gán địa chỉ trả về vào "biến địa chỉ trả về" bí mật của hàm, rồi nhảy đến phần đầu của hàm.
• Hàm sẽ đọc tham số từ các biến toàn cục bí mật và dùng những biến toàn cục bí mật đã được định nghĩa sẵn, về mặt logic tương ứng với các biến cục bộ.
• Khi hàm kết thúc, nó sẽ nhảy tới địa chỉ nằm trong "biến địa chỉ trả về" bí mật của hàm.

Tối ưu hóa ABI

• Để tối ưu ABI, một số giá trị được truyền qua thanh ghi thay vì biến toàn cục.
• Hầu hết các bộ xử lý đều có thanh ghi "link" và lệnh "branch with link", tự động đặt thanh ghi link thành địa chỉ ngay sau lệnh "branch with link".
• Quy ước gọi hàm được tối ưu để truyền hai tham số đầu tiên qua thanh ghi.

Sự bất khả thi của đệ quy

• Lời gọi đệ quy không hoạt động. Nó sẽ ghi đè biến địa chỉ trả về bằng địa chỉ trả về của lần gọi đệ quy, khiến lời gọi bên ngoài nhảy sai vị trí khi hoàn tất.
• Các ngôn ngữ lập trình thời đó giải quyết vấn đề này bằng cách tuyên bố không hỗ trợ đệ quy.

Đoạn trao đổi thêm

• Một số trình biên dịch còn vận hành khéo léo hơn bằng mã tự sửa: biến địa chỉ trả về đặc biệt thực ra chính là trường địa chỉ của lệnh nhảy ở cuối hàm.
• Nếu bộ xử lý không hỗ trợ nhảy gián tiếp thì đây là một nhu cầu thực tế khiến cách này được sử dụng.
• Sau khi giá trị thực tiễn của subroutine được công nhận, nhiều bộ xử lý đã bổ sung lệnh gọi subroutine để lưu địa chỉ trả về vào từ đầu tiên của subroutine và bắt đầu thực thi từ từ thứ hai của subroutine.
• Để quay về từ subroutine, hệ thống thực hiện một lệnh nhảy gián tiếp thông qua nhãn bắt đầu của subroutine.

Ý kiến của GN⁺

• Bài viết này giúp hiểu rõ sự phát triển của các kỹ thuật quản lý bộ nhớ dùng trong phát triển phần mềm hiện đại bằng cách giải thích cách lập trình đã diễn ra trong thời kỳ đầu của điện toán khi chưa có stack và heap.
• Cách lập trình của thời chưa có stack và heap có thể rất xa lạ và kém hiệu quả trong mắt các lập trình viên hiện đại, nhưng nó cung cấp kiến thức nền quan trọng để hiểu công nghệ đã tiến hóa như thế nào qua lịch sử điện toán.
• Những ràng buộc lập trình trong thời kỳ đệ quy là điều không thể cũng mang lại một sự thật lịch sử thú vị cho các nhà phát triển ngày nay đang sử dụng thuật toán đệ quy.
• Nhìn từ góc độ phê bình, các phương thức lập trình ban đầu này cho thấy chúng từng rất hạn chế khi phải đáp ứng những yêu cầu phức tạp và đa dạng của hiện đại.

[GN⁺]

Ý kiến trên Hacker News

• Đánh giá tích cực về cuốn sách "The Art of Computer Programming"

  • Dù cuốn sách có vẻ đã cũ, nó bàn về nhiều thuật toán để thay đổi mảng động và cấu trúc dữ liệu từ thời trước khi có heap hay stack.
  • Sách cũng giải thích về garbage collection và cách triển khai danh sách Lisp, đồng thời mang đến kiểu kiến thức bách khoa khiến người đọc kỳ vọng ở Knuth.

• Giải thích về cách hai mảng cùng chia sẻ động một không gian duy nhất

  • Một mảng tăng trưởng bình thường từ vị trí #0, còn mảng kia tăng trưởng ngược từ vị trí #End, nhờ đó hai mảng chia sẻ hiệu quả không gian được cấp phát tĩnh.
  • Cách này có thể mở rộng cho nhiều mảng hơn, nhưng đến mức đó thì có lẽ dùng Malloc và Realloc sẽ tốt hơn.

• Chia sẻ liên kết đến một câu chuyện thú vị về việc đưa hàm đệ quy vào ngôn ngữ ALGOL từng là vấn đề gây tranh cãi

  • Chia sẻ qua liên kết một câu chuyện thú vị về lịch sử đệ quy đã được đưa vào ngôn ngữ lập trình như thế nào.

• Chia sẻ kinh nghiệm viết trình thông dịch Forth cho máy SUBLEQ và máy bit-serial

  • Cả hai loại máy này đều không có stack gọi hàm, vốn là thành phần thiết yếu của Forth.
  • SUBLEQ không cho phép nạp và lưu gián tiếp, nên cần đến mã tự sửa đổi để thực hiện các tác vụ không thông thường.
  • Xây dựng một máy ảo để thực hiện các chức năng này và hỗ trợ cooperative multithreading.
  • Khi cần, heap được viết bằng Forth, và cũng bao gồm các phép toán dấu phẩy động được triển khai dưới dạng hàm phần mềm.

• Giải thích về quá trình tiến hóa kỹ thuật liên quan đến gọi chương trình con trên bộ xử lý PDP-8

  • Ban đầu, lệnh JMS lưu địa chỉ trả về vào từ đầu tiên của hàm.
  • Về sau, người ta dùng các vị trí tự tăng để tạo một stack đơn giản, còn phần mở đầu/kết thúc hàm sẽ tự quản lý stack này bằng tay để cho phép đệ quy đầy đủ.
  • Sau nữa, stack phần cứng được thêm vào các bản triển khai vi xử lý để cải thiện hiệu năng.

• Chia sẻ sở thích dùng đệ quy của một người đã có thời gian dài làm việc với lập trình hàm

  • Dù biết cách chuyển thuật toán đệ quy sang thuật toán lặp, họ vẫn thích đệ quy hơn.
  • Trong đa số trường hợp, đệ quy đủ nhanh, và càng đúng hơn nếu trình biên dịch hỗ trợ tail recursion.
  • Họ đang hack game trên Commodore 64 để tìm hiểu cách người ta đã lập trình trong quá khứ.

• Chia sẻ kinh nghiệm thiết kế bộ ghép kênh nối tiếp RS232 vào khoảng năm 1991

  • Thiết kế phần cứng dùng bộ xử lý Z80, EPROM và thiết bị nối tiếp Z80-SIO.
  • Do không có stack, họ dùng cách nạp trước địa chỉ trả về vào các cặp thanh ghi để gọi hàm.

• Nhắc đến bối cảnh trước khi heap có thể mở rộng, khi lập trình viên phải cân nhắc phân bố khả dĩ của đầu vào và đặt kích thước vùng đệm trung gian cho phù hợp

  • Điều này dẫn đến "lỗi và giới hạn".

• Giải thích rằng vào thời chưa thể dùng đệ quy, tail recursion vẫn khả thi

  • Ngoại trừ branch_with_link dùng cho lời gọi ban đầu, các nhánh thông thường phải được dùng.

• Giải thích cách Enhanced GNU Awk để trình biên dịch gán các biến toàn cục bí mật cho các khối @let nằm ngoài hàm

  • Các biến này được tái sử dụng nhiều nhất có thể.

• Nhắc đến một bài viết mô tả thế giới của bài báo "Goto considered harmful"

  • Đa số mọi người chỉ biết tiêu đề, còn bài báo thực sự lập luận về việc cung cấp một điểm vào duy nhất cho chương trình con.
  • Đôi khi người ta viết mã assembly để nhảy sang chương trình con khác, nhưng không ai muốn toàn bộ mã assembly đều trở thành như vậy.