1051 1363 1076 1865 1788 1290 1754 1657 1343 1098 1136 1146 1270 1221 1631 1618 1526 1025 1547 1482 1755 1693 1709 1128 1140 1064 1392 1614 1603 1283 1277 1351 1558 1313 1842 1810 1589 1347 1579 1465 1900 1055 1925 1506 1570 1652 1488 1028 1120 1029 1020 1947 1687 1239 1112 1492 1176 1706 1289 1365 1148 1831 1287 1451 1590 1402 1252 1725 1320 1794 1804 1697 1017 1711 1243 1428 1399 1758 1853 1504 1317 1238 1394 1714 1998 1238 1506 1109 1194 1438 1064 1729 1665 1070 1204 1797 1542 1057 1297 Stack Machines: Calls | PHPnews.io


Stack Machines: Calls

Written by igorw / Original link on Aug. 24, 2019

Stack Machines: Calls

fundamentals << rpn-calculator << shunting-yard << io << jumps << conditionals << comments << calls << variables << stack-frames << heap << compilers

Hey I just met you
And this is crazy
But here's my number
So call me maybe

— Carly Rae Jepsen

We have been talking about stack machines (this is a series of posts, go back and read the other posts if you feel lost right now) without ever talking about calls. This is rather odd, as most of the time when discussing stacks in programming, we only talk about the call stack.


A call, sometimes refered to as procedure call, subroutine call or function application, is a means of transfering control to an other sub-program. This implies that we have sub-programs to begin with.

By breaking programs into procedures the execution context or scope can be reduced, which makes reasoning about a particular piece of code easier. In other words, you get modularity.

Once a procedure has completed its task, it is able to return control back to the caller.


What is a procedure, really? A procedure is just a piece of code that follows a certain "interface" or pattern, allowing it to be called by other code.


Calling conventions

The anatomy of a procedure call will vary by language, operating system and CPU architecture. There will usually be standard conventions for the instructions involved in performing them, known as calling conventions.

This generally means having some sort of "call stack" that stores the execution context of the caller, so that control can be returned back later on. The most important part of program state representing the execution context is the instruction pointer.

In most actual architectures, the data stack and the call stack are combined. In this machine, we will afford ourselves the luxury of separating them. The calling convention will have two parts: argument passing and state storage.

Argument passing

Arguments are passed via the stack. The caller pushes the arguments for the procedure onto the stack, the procedure pops them off.

In this forth-like stack machine, the data stack holds arguments implicitly. In other words, procedures can consume as many values as they need from the stack, and they can also produce as many "output" values as they want. This means that unlike traditional calling conventions, a procedure can return many values.

State storage

The only state we will store for now will be the instruction pointer $ip. It will be stored in the call stack which will be a separate stack next to the data stack. There are two instructions involved with procedure calls.

The first is call(procedure), which takes a procedure name to call. This call will simply push the instruction pointer onto the call stack, then jump to the memory address referenced by the label that is the procedure name. That's right, a procedure is just a piece of code identified by a label.

The second instruction is ret, which will allow returning from a procedure call. Ideally every procedure will have a ret at the end. What this instruction does is just pop the previous instruction pointer from the call stack and jump back to it.


That's it!


What this means in practice is that you can take some code containing jumps, replace the jmp with a call and put a ret at the end of the labeled code, and get modular code that can be separated and shipped as a library!

Let's take the output loop example from the conditionals post:

0 10 100 108 114 111 119 32 44 111 108 108 101 104
    dup jz(end)

The loop can be extracted out into a printstr procedure, but we must also jump over the library code to the actual application code, which will then set up the data and call printstr:


        dup jz(end)

    0 10 100 108 114 111 119 32 44 111 108 108 101 104

Of course, procedures can call other procedures. Or they can call themselves recursively.



First we need a call stack to store the return addresses.

$calls = new SplStack();

Next, we need a call instruction that stores $ip on the call stack and jumps to the address of the procedure.

if (preg_match('/^call\((.+)\)$/', $op, $match)) {
    $label = $match[1];
    $ip = $labels[$label];

And finally, we need a ret instruction that pops the return address from the call stack and jumps back to it.

switch ($op) {
    // ...
    case 'ret':
        $ip = $calls->pop();


Adding calls to an RPN calculator allows code to be made modular, reusable and independent from the caller.

fundamentals << rpn-calculator << shunting-yard << io << jumps << conditionals << comments << calls << variables << stack-frames << heap << compilers


« Why Steve Jobs Killed the Newton - Stack Machines: Comments »