4 ms·

As a dev who has never really got into the low-level parts of programming, I don't really understand yet how this is stackless. I thought the stack had more to

by hughes 12y ago

As a dev who has never really got into the low-level parts of programming, I don't really understand yet how this is stackless. I thought the stack had more to do with the depth of function calls than with the passing of function parameters. Can anyone here explain it?

ekr 12y ago
Haven't read all of it, but the author assumes the availability of a return stack, which somehow makes this approach not really stack-free. Most modern calling conventions (x86) use a register(eax/rax) for returning values. But his approach does in fact conserve stack space.
- LukeShu 12y ago
  A little bit further down, he shows how to avoid using the return stack also, to use no stack at all. Also, by "return stack", he isn't referring to the mechanism for returning values, he is referring to the mechanism for knowing which address to jump (return) to when a function is finished. In x86, this is still done with a stack, but the stack modifications are done "behind the scenes" by the call/ret instructions.
barrkel 12y ago
There are two approaches described - one a further extension of the other. The first approach still relies on a call stack (but not parameters or locals). Instead of calling a function like this: f(x) = // ... f(x + 1) It's called like this: f = x = x + 1 f() x = x - 1 The return address from the function call references the code that undoes modification to global state (all locals and parameters have static storage when there is no recursion support), rather than relying on copies of parameters being made as in a modern language. The second is an extension of the first, using goto and labels instead of function calls, but it only works if you don't need to distinguish between different call sites. If the recursive function only ever calls itself in one place, and the mutation it needs to make in order to "recurse" is always the same (so it can be consistently undone), then the call stack can be eliminated too.
andrewstuart2 12y ago
Mildly educated answer here. A stack in low level terms is just a first-in-first-out record of what context the CPU needs to reload when it's done with the current line of execution. If you can stay in the same context and just increment or decrement some variables, you'd probably call that stackless. When you pass function parameters you usually need to push onto the stack or risk overwriting the value of the named variable in the current execution context, since it has the same name or register in the new execution context. Again, mildly educated answer so if somebody can correct me, please do.
- gorhill 12y ago
  > A stack in low level terms is just a first-in-first-out record I think you meant last-in-first-out.
  - andrewstuart2 12y ago
    Ah, yes I did.
chad_oliver 12y ago
As you probably know, the stack is made up of stack frames, and a stack frame is added each time you go 'deeper' by calling another function. A stack frame is removed every time you get to the end of a function and return. So, yes, the stack is closely linked to the depth of function calls. However, in modern systems (or basically anything you'll ever see today, including the cheapest microcontrollers), the stack doesn't just keep track of where to return to after each function completes. It also stores all the local variables used by the function. This is vital because it allows the variables to be restored after you return from a 'deeper' function. A convenient side effect is that when the function completes and the frame is popped off the stack, the references to the local references are destroyed and the data can be garbage-collected. In this sense, local variables are directly related to stack frames. If your system doesn't store local variables in the stack frame, it almost certainly doesn't store them anywhere else (stack frames are the natural place for them), and you've only got globals to work with.

by hughes 12y ago

ekr 12y ago

Haven't read all of it, but the author assumes the availability of a return stack, which somehow makes this approach not really stack-free. Most modern calling conventions (x86) use a register(eax/rax) for returning values. But his approach does in fact conserve stack space.

LukeShu 12y ago
A little bit further down, he shows how to avoid using the return stack also, to use no stack at all. Also, by "return stack", he isn't referring to the mechanism for returning values, he is referring to the mechanism for knowing which address to jump (return) to when a function is finished. In x86, this is still done with a stack, but the stack modifications are done "behind the scenes" by the call/ret instructions.

barrkel 12y ago

There are two approaches described - one a further extension of the other. The first approach still relies on a call stack (but not parameters or locals). Instead of calling a function like this: f(x) = // ... f(x + 1) It's called like this: f = x = x + 1 f() x = x - 1 The return address from the function call references the code that undoes modification to global state (all locals and parameters have static storage when there is no recursion support), rather than relying on copies of parameters being made as in a modern language. The second is an extension of the first, using goto and labels instead of function calls, but it only works if you don't need to distinguish between different call sites. If the recursive function only ever calls itself in one place, and the mutation it needs to make in order to "recurse" is always the same (so it can be consistently undone), then the call stack can be eliminated too.

andrewstuart2 12y ago

Mildly educated answer here. A stack in low level terms is just a first-in-first-out record of what context the CPU needs to reload when it's done with the current line of execution. If you can stay in the same context and just increment or decrement some variables, you'd probably call that stackless. When you pass function parameters you usually need to push onto the stack or risk overwriting the value of the named variable in the current execution context, since it has the same name or register in the new execution context. Again, mildly educated answer so if somebody can correct me, please do.

gorhill 12y ago
> A stack in low level terms is just a first-in-first-out record I think you meant last-in-first-out.
- andrewstuart2 12y ago
  Ah, yes I did.

chad_oliver 12y ago

As you probably know, the stack is made up of stack frames, and a stack frame is added each time you go 'deeper' by calling another function. A stack frame is removed every time you get to the end of a function and return. So, yes, the stack is closely linked to the depth of function calls. However, in modern systems (or basically anything you'll ever see today, including the cheapest microcontrollers), the stack doesn't just keep track of where to return to after each function completes. It also stores all the local variables used by the function. This is vital because it allows the variables to be restored after you return from a 'deeper' function. A convenient side effect is that when the function completes and the frame is popped off the stack, the references to the local references are destroyed and the data can be garbage-collected. In this sense, local variables are directly related to stack frames. If your system doesn't store local variables in the stack frame, it almost certainly doesn't store them anywhere else (stack frames are the natural place for them), and you've only got globals to work with.