Stack Programming

[zhulien]

I have created a small POC of a stack program.  This is looking at it from the point of view as code generated from a possible BASIC compiler or other similar language.

Programming on the stack has some interesting behaviour and side effects.  Code could be ROMable but some RAM workspace would be required.

Restrictions, while stack logic is executed, you cannot use PUSH or it will basically be modifying code (you'd have to be pretty careful if you want to modify the logic that way).  Because you can't generally use push, you cannot have interrupts enabled.  CALL cannot be used either as it will modify the stack.

But I have put in the code below a way to enable interrupts and disable them too. 

From a BASIC compilation perspective, imagine each keyword was compiled into a statement, such as kw_printsp (for a variant of PRINT), in this example, printing a string that is pointed to on the stack.  Note: in this examle, I didn't code the char out function, only the string print loop. 

So, can you code without PUSH or CALL?  Absolutely.  I got this idea actually from a totally unrelated code which was the SID player for Z80, it doesn't use the stack, it just jumps around a lot. So I thought, what if you did the opposite. And what happens with this, you end up with a LOT of cycles saved from not having to call and return to the caller.  You can still jump around easily by modifying SP, you can go to the next function conditionally, you can create lots of alternate keyword stacks.

But the main reason I posted this was to get some opinions on the interrupt side of things.  If you were to code a CPC game in assembler without using firmware, from what I can see you can get away with not using interrupts at all, but... you might lose some benefits of making e.g. music play easily in the background.  Keyboard scanning? Did I miss anything?

Code Select Expand

ADDR_ISR equ #0038

        org #4000

        jp fn_execute

        ; program logic

line10:    dw kw_printsp
        dw msg_helloworld
line20:    dw kw_printsp
        dw msg_helloworld
line30:    dw kw_printsp
        dw msg_helloworld

        dw fn_ei            ; give interrupts a chance to execute (they disable again by themselves)
       
        dw kw_goto10        ; we get here at the end of fn_isr
       
msg_helloworld:
        db "Hello, World!", 0

        ; supporting functions

        ; keyword print
        ;
kw_printsp:
        pop hl
kw_printsp_1:
        ld a,(hl)
        or a
        ret z
        ;inline printa code
        inc hl
        jr kw_printsp_1
       
        ; keyword goto 10
        ;
kw_goto10:
        ld sp, line10
        ret

        ; disable interrupts & continue logic execution
        ;
fn_di:    di
        ld (temp_hl), hl
       
        ld hl, (logic_stack_ptr)    ; restore logic stack
        ld sp, hl                    ;
       
        ld hl, (temp_hl)
        ret                            ; invoke logic stack next statement
       
        ; preserve logic stack and reenable hardware interrupts
        ;
fn_ei:    ld (temp_hl), hl

        ld hl, 0                    ; preserve logic stack
        add hl, sp
        ld (logic_stack_ptr), hl
       
        ld hl, (hw_stack_ptr)        ; restore hardware stack
        ld sp, hl

        ld hl, (temp_hl)
        ei

fn_ei_wait:                            ; wait after reenabling hardware interrupts for an interrupt to occur
        jr  fn_ei_wait

        ; preserve the hardware stack and start execution
        ;
fn_execute:   
        di
        call fn_isr_patch
        ld hl, 0                    ; preserve hardware stack
        add hl, sp
        ld (hw_stack_ptr), hl

        ld sp, line10                ; start logic here
        ret                            ; invoke logic next statement
       
        ; patch the system ISR
        ;
fn_isr_patch:
        ld hl, (ADDR_ISR+1)
        ld (fn_isr+1), hl
       
        ld a, #c3
        ld (ADDR_ISR), a
        ld hl, fn_isr
        ld (ADDR_ISR+1), hl
        ret

        ; new ISR
        ;
fn_isr:    db #cd, 0, 0                ; first call whatever the system ISR used to do
                                   
                                    ; put custom ISR code here
                                   
        jp fn_di                    ; disable interrupts again and continue execution of logic

temp_hl: dw 0                        ; temporary store for hl
logic_stack_ptr: dw 0                ; preserved logic stack pointer
hw_stack_ptr: dw 0                    ; preserved hardware stack pointer

[zhulien]

typical calls (register passing):

tstates bytes
10 3 ld hl, msg
17 3 call printmsg
10 1 ret

37 tstates
7 bytes

typical calls (stack passing):

tstates bytes
10 3 ld hl, msg
11 1 push hl
17 3 call printmsg
10 1 ret

48 tstates
8 bytes

stack based logic:

tstates bytes

10 1 ret
10 1 pop
4 <stack>

20 tstates
6 bytes

Multiply that by 3 if you want to print Hello, World 3 times as per the POC above

[Bread80]

This is both interesting and a total mind freak.

And it feels like it might be an interesting method for implementing FORTH.

[zhulien]

I had forgotten the pop below which adds another 10ts and byte

typical calls (stack passing):

tstates bytes
10 3 ld hl, msg
11 1 push hl
10 pop hl
17 3 call printmsg
10 1 ret

58 tstates
9 bytes

I will give some examples of different constructs soon such as IF THEN... WHILE WEND 

Forth would pose some challenges but maybe not impossible. Often on a z80 forth implementations use 2 software stacks. Given this situation it could be possible to use 1 hardware stack to make (forth with limitations) or perhaps 1 software stack (less limitations).  If no software stacks, then a limited forth-like, could conceptually be programmed as though they are stack operations but instead be using temporary variables. I think it would be a challenge to make it strictly forth. 

For BASIC or another language that isnt freely extensible, it is straight forward. For an extensible language, I have some ideas on constructs.

I have long hated the code that is typically generated by compilers for z80s. I believe that the most optimal language to be compiled is BASIC because it can be optimal per keyword.  

I am looking now to code this BASIC compiler instead of the JS one I have made the POC of.  I think the audience is different but also BASIC suits z80 more, laser basic  pandora for example have proven these can work quite well.  It won't be locomotive BASIC compatible but will open source it so whoever wants to add new keywords can.

Memory map I plan to be CPM Plus-like.  Maybe I can give 2 alternative maps. 64k and 128k or more.

I somewhat don't want to deal with the 64k option though.  Because...

We are not using interrupts, i will have full main memory availability to have overacan and 16:9 options, maybe also a vertical option like DK and Arkanoid.   They work well for arcade games. I'm hoping rhe 16x9 option will zoom nicely on modern TVs to reduce unused screen for larger chunky sprites.  A typical gameloop might wait for frame flyback then do a series of things like update PSG, scan keys, sprite locations etc... racing time before the next frame.  So interrupts for most part may not be required.  

[zhulien]

Here are conditionals.

Code Select Expand

  dw doBlahIfTrue

doBlahIfTrue:
      ret NZ
      Blah...
      ret


  dw doBlahIfNotTrue

doBlahIfNotTrue:
      ret Z
      Blah...
      ret


  dw doBlahIfTrue
  dw doBlahIfNotTrue

[andycadley]

That only works for very limited conditional processing. Anything too complicated and the call path becomes very difficult to represent using Return Oriented Programming.

[zhulien]

That only works for very limited conditional processing. Anything too complicated and the call path becomes very difficult to represent using Return Oriented Programming.

Actually it works for all branching.  The functions are not supposed to be reusable, they are supposed to be generated statements from a 3GL.  To make Z or NZ requires an expression to be evalutated that would be called from the stack prior to the conditional.

[andycadley]

It's not the conditional code that's the problem, it's that the overall control flow has to exist on the stack in the first place. It's one thing if you have a reasonably consistent flow with a few optionally executed segments (although you have to be careful about statefulness) but as the complexity of routes through the code increases it becomes more difficult to represent execution order as a linear stack.

[lightforce6128]

It's not the conditional code that's the problem, it's that the overall control flow has to exist on the stack in the first place. It's one thing if you have a reasonably consistent flow with a few optionally executed segments (although you have to be careful about statefulness) but as the complexity of routes through the code increases it becomes more difficult to represent execution order as a linear stack.

What about a function that updates the stack pointer? This could jump to other parts of the stack, skipping parts of the code. This would be similar to the BASIC construct IF-THEN-GOTO.

[zhulien]

It's not the conditional code that's the problem, it's that the overall control flow has to exist on the stack in the first place. It's one thing if you have a reasonably consistent flow with a few optionally executed segments (although you have to be careful about statefulness) but as the complexity of routes through the code increases it becomes more difficult to represent execution order as a linear stack.

What about a function that updates the stack pointer? This could jump to other parts of the stack, skipping parts of the code. This would be similar to the BASIC construct IF-THEN-GOTO.

The original post example does just thst for the goto.

[lightforce6128]

What about a function that updates the stack pointer? This could jump to other parts of the stack, skipping parts of the code. This would be similar to the BASIC construct IF-THEN-GOTO.

The original post example does just thst for the goto.

Oh, sorry, I did not see this. I should have read the source code more carefully.

With this structure it should not be too difficult to compile e.g. a Locomotive BASIC program to assembler. And it will spare much of the analysis code normally used to understand the byte code of the compreter. This will speed up program execution.