solution

Mở rộng máy ảo dựa trên ngăn xếp để hỗ trợ chương trình con (subroutine) — cơ chế nền tảng để trình biên dịch hiện thực lời gọi hàm. Ngoài các lệnh PUSH x, ADD, SUB, MUL, DIV (chia làm tròn về 0), DUP, POP, PRINT (in đỉnh ngăn xếp, không xoá), HALT như máy ảo cơ bản, bổ sung:

• JMP nhãn: nhảy vô điều kiện tới lệnh có nhãn.
• JZ nhãn: lấy ra (pop) phần tử đỉnh ngăn xếp; nếu bằng 0 thì nhảy tới nhãn, ngược lại thực hiện lệnh kế tiếp.
• CALL nhãn: đẩy địa chỉ lệnh kế tiếp (sau CALL) vào một ngăn xếp lời gọi (call stack) riêng biệt với ngăn xếp dữ liệu, rồi nhảy tới nhãn.
• RET: lấy ra một địa chỉ từ ngăn xếp lời gọi và nhảy tới đó (tiếp tục thực thi ngay sau lệnh CALL tương ứng); nếu ngăn xếp lời gọi rỗng, RET coi như HALT.

Nhãn gắn ở đầu dòng lệnh theo cú pháp nhan: lệnh .... Chương trình con có thể gọi lồng nhau (một chương trình con gọi chương trình con khác) — ngăn xếp lời gọi phải hoạt động đúng nguyên tắc vào-sau-ra-trước (LIFO) để quay về đúng vị trí.

Nếu ngăn xếp dữ liệu không đủ phần tử cho một lệnh, hoặc DIV chia cho 0, in thêm dòng ERROR rồi dừng ngay. Nếu chương trình thực hiện quá $200000$ bước mà chưa dừng, in thêm dòng TIMEOUT rồi dừng.

Ví dụ:

PUSH 3
PUSH 4
CALL addsub
PRINT
HALT
addsub: ADD
DUP
ADD
RET

thực thi CALL addsub để tính $3+4=7$ rồi nhân đôi thành $14$, quay về in ra 14.