A different stack discipline

A different stack discipline

[Mikael Djurfeldt]

[-- Attachment #1: Type: text/plain, Size: 1088 bytes --]

I've looked a little at the Guile vm and compiler.

What a beautiful work! It also has very nicely written documentation. Very
impressive!

Here's an idea/question:

SICP describes a register machine with a stack discipline which is
different from most machine models in that it doesn't have a call
instruction which pushes the PC onto the stack and a return instruction
which pops it. Instead it has a continue register: When calling a
subroutine, you load the continue register with the continuation of the
subroutine (as described here:
https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-31.html#%_sec_5.1.4
). A subroutine ends with a branch to its continuation (stored in the
continue register).

It seems to me that this 1. is natural to scheme since tail recursion
doesn't need to be handled differently than ordinary calls, 2. that it fits
the Guile compiler nicely with its CPS soup and 3. that it possibly could
save vm instructions and stack space.

Could it be a good idea to switch over to the SICP stack discipline in the
vm?

Best regards,
Mikael D.

[-- Attachment #2: Type: text/html, Size: 1435 bytes --]

Re: A different stack discipline

[Hugo Hörnquist]

The section, as far as I can see, just describes a machine
which pushes continuation instead of the PC counter to the
stack.

Also, while in theory quite nice it has the problem that
Guile is really slow in restoring continuations, due to the
fact that we have complete C interoperability.

On Wed, Oct 31, 2018 at 09:55:06PM +0100, Mikael Djurfeldt wrote:
> I've looked a little at the Guile vm and compiler.
> 
> What a beautiful work! It also has very nicely written documentation. Very
> impressive!
> 
> Here's an idea/question:
> 
> SICP describes a register machine with a stack discipline which is
> different from most machine models in that it doesn't have a call
> instruction which pushes the PC onto the stack and a return instruction
> which pops it. Instead it has a continue register: When calling a
> subroutine, you load the continue register with the continuation of the
> subroutine (as described here:
> https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-31.html#%_sec_5.1.4
> ). A subroutine ends with a branch to its continuation (stored in the
> continue register).
> 
> It seems to me that this 1. is natural to scheme since tail recursion
> doesn't need to be handled differently than ordinary calls, 2. that it fits
> the Guile compiler nicely with its CPS soup and 3. that it possibly could
> save vm instructions and stack space.
> 
> Could it be a good idea to switch over to the SICP stack discipline in the
> vm?
> 
> Best regards,
> Mikael D.

-- 
hugo

Re: A different stack discipline

[Mikael Djurfeldt]

[-- Attachment #1: Type: text/plain, Size: 1769 bytes --]

On Sat, Nov 3, 2018 at 4:30 PM Hugo Hörnquist <hugo@lysator.liu.se> wrote:

> The section, as far as I can see, just describes a machine
> which pushes continuation instead of the PC counter to the
> stack.
>
> Also, while in theory quite nice it has the problem that
> Guile is really slow in restoring continuations, due to the
> fact that we have complete C interoperability.
>

There's some misunderstanding here. The SICP register machine model is not
very different from common register machine models. There's just a
difference in how to handle subroutine calls. A short example:

Let's first write out all operations involved in a call in a conventional
register machine:

        [...]
        ; The following three micro operations consitute "call foo ()"
        (sp) <- pc + offset(L1) ; NOTE the external memory access
        sp <- sp - 1
        pc <- pc + offset(foo)
L1:    [...]

foo:   [...]
        ; the following two micro operations constitute "ret"
        sp <- sp + 1
        pc <- (sp) ; NOTE the external memory access

Now look at the call in the SICP register machine:

        [...]
        continue <- pc + offset(L1)
        pc <- pc + offset(foo)
L1:   [...]

foo:  [...]
        pc <- continue

It is fewer operations and every operation is immediate with no memory
access. I *have* cheated since I omit a need to push the continue register
onto the stack, but while this is needed at *every* call for the
conventional machine, this is only required once at the beginning of a
function in the SICP machine *unless* the function has a tail call, in
which case we don't need to push anything. So, while one can say that we
only "push around the pushes", we make gains for every tal call.

[-- Attachment #2: Type: text/html, Size: 2496 bytes --]

Re: A different stack discipline

[Mikael Djurfeldt]

[-- Attachment #1: Type: text/plain, Size: 2417 bytes --]

Den lör 3 nov. 2018 19:16 skrev Mikael Djurfeldt <mikael@djurfeldt.com>:

> On Sat, Nov 3, 2018 at 4:30 PM Hugo Hörnquist <hugo@lysator.liu.se> wrote:
>
>> The section, as far as I can see, just describes a machine
>> which pushes continuation instead of the PC counter to the
>> stack.
>>
>> Also, while in theory quite nice it has the problem that
>> Guile is really slow in restoring continuations, due to the
>> fact that we have complete C interoperability.
>>
>
> There's some misunderstanding here. The SICP register machine model is not
> very different from common register machine models. There's just a
> difference in how to handle subroutine calls. A short example:
>
> Let's first write out all operations involved in a call in a conventional
> register machine:
>
>         [...]
>         ; The following three micro operations consitute "call foo ()"
>         (sp) <- pc + offset(L1) ; NOTE the external memory access
>         sp <- sp - 1
>         pc <- pc + offset(foo)
> L1:    [...]
>
> foo:   [...]
>         ; the following two micro operations constitute "ret"
>         sp <- sp + 1
>         pc <- (sp) ; NOTE the external memory access
>
> Now look at the call in the SICP register machine:
>
>         [...]
>         continue <- pc + offset(L1)
>         pc <- pc + offset(foo)
> L1:   [...]
>
> foo:  [...]
>         pc <- continue
>
> It is fewer operations and every operation is immediate with no memory
> access. I *have* cheated since I omit a need to push the continue register
> onto the stack, but while this is needed at *every* call for the
> conventional machine, this is only required once at the beginning of a
> function in the SICP machine *unless* the function has a tail call, in
> which case we don't need to push anything. So, while one can say that we
> only "push around the pushes", we make gains for every tal call.
>

(consitute -> constitute; tal -> tail; also, when saying "this is needed"
above, I was referring to the *stack pushes*, not the push of the continue
register specifically)

In addition to not having to push continue in functions with tail calls, we
also gain for every function that do not call a subroutine.

For C compatibility, we can do an ordinary call when calling C.

None of this affects the restoration of continuations. Also, it does not
slow down but speeds up!

>

[-- Attachment #2: Type: text/html, Size: 3778 bytes --]