How to write a stack organized program with MARIE

Question

I am writing a program that will evaluate the statement below, but I have to do it with a stack organized computer. This means that only pop and push can access memory.

How would I do this while using this program as a sample for my program?:

    Load    A           
    Store   Stack0      
    JnS Push        
    Load    B       
    Store   Stack0      
    JnS Push        
    JnS PopS        
    Load    C       
    Store   Stack0      
    JnS Push        
    Load    D       
    Store   Stack0      
    JnS Push        
    Load    E       
    Store   Stack0      
    JnS Push        
    JnS PopM        
    Load    F       
    Store   Stack0      
    JnS Push        
    JnS PopS        
    JnS PopM        
    JnS PopA        
    Load    G       
    Store   Stack0      
    JnS Push        
    Load    H       
    Store   Stack0      
    JnS Push        
    Load    K       
    Store   Stack0      
    JnS Push        
    JnS PopM        
    JnS PopA        
    JnS PopD        
    JnS Pop     
    Halt            
Push,   Hex 0       
    Load    Stack4      
    Store   Stack5      
    Load    Stack3
    Store   Stack4
    Load    Stack2
    Store   Stack3
    Load    Stack1
    Store   Stack2
    Load    Stack0
    Store   Stack1
    JumpI   Push
Pop,    Hex 0       
    Load    Stack1      
    Store   Stack0      
    Load    Stack2      
    Store   Stack1
    Load    Stack3
    Store   Stack2
    Load    Stack4
    Store   Stack3
    Load    Stack5
    Store   Stack4
    Load    Zero
    Store   Stack5
    Load    Stack0
    JumpI   Pop
PopA,   Hex 0       
    JnS Pop     
    Add Stack1      
    Store   Stack1      
    JumpI   PopA
PopS,   Hex 0       
    JnS Pop
    Load    Stack1      
    Subt    Stack0      
    Store   Stack1      
    JumpI   PopS
PopM,   Hex 0       
    JnS Pop
    Store   Calc1       
    Store   Calc3       
    JnS Pop
    Subt    One
    Store   Calc2
    Skipcond    400 
    JnS Mult        
    Store   Stack0
    JnS Push        
    JumpI   PopM
Mult,   Hex 0
LoopM,  Load    Calc3       
    Add Calc1
    Store   Calc3
    Load    Calc2
    Subt    One     
    Store   Calc2
    Skipcond    400 
    Jump    LoopM
    Load    Calc3       
    JumpI   Mult
PopD,   Hex 0       
    JnS Pop
    Store   Calc2       
    Load    Zero        
    Store   Calc3       
    JnS Pop
    Store   Calc1       
    Load    Calc2
    Skipcond    400 
    JnS Divs
    Store   Stack0
    Jns Push        
    JumpI   PopD
Divs,   Hex 0
LoopD,  Load    Calc1       
    Subt    Calc2       
    Store   Calc1       
    Load    Calc3
    Add One     
    Store   Calc3       
    Load    Calc1
    Skipcond    800 
    Jump    EndD
    Jump    LoopD
EndD,   Load    Calc3       
    JumpI   Divs
One,    Dec 1           
Zero,   Dec 0           
Calc1,  Dec 0           
Calc2,  Dec 0           
Calc3,  Dec 0
A,  Dec 9       
B,  Dec 8
C,  Dec 7
D,  Dec 6
E,  Dec 5
F,  Dec 4
G,  Dec 3
H,  Dec 2
K,  Dec 1
Stack0, Dec 0           
Stack1, Dec 0           
Stack2, Dec 0           
Stack3, Dec 0           
Stack4, Dec 0
Stack5, Dec 0

Any help would be appreciated. I am new to MARIE, and have received next to no help so far whatsoever. Thank you! =)

Answer 1

This is not possible with MARIE. Although MARIE offers indirect addressing, this is not enough to perform arithmetic with just Push and Pop subroutines.

Neither Push nor Pop functions perform the arithmetic you need, so whatever stack manipulations you do, to perform an addition in MARIE you need somewhere to do:

Add <memory address>

or:

AddI <memory address>

...and this accesses memory outside of a Push/Pop function, so you'll violate the constraints.

Note that your sample program violates the rules you have stipulated, as it accesses lots of memory locations outside of the push and pop functions, such as Stack0, Stack1, ... Calc1, Calc2, ...etc.

Relaxing the conditions

We could agree to relax the constraints as follows:

• Some other basic stack functions beside Push/Pop can be implemented which also access stack memory, including:

  • Empty: to reset the stack to an empty stack. This is needed when the program is restarted without reassembling the code: in that case the stack could be in any state, so resetting is needed.
  • Peek: to get the top of the stack without popping it. A shortcut to calling Pop and then Push again.
  • Update: to replace the top of the stack with a given value, instead of first saving that value somewhere, then performing a Pop, reading that value, and finally performing a Push.
  • UnPop: to increase the stack pointer to include a value that was left outside the stack after a recent call to Pop. This allows to navigate through the stack much like a Turing Machine's head.

• Two more functions are allowed to access the stack directly so to work around the limitation explained above (i.e. Add and Subt need a target memory address):

  • Sumup: to take a value from the stack, and add it to the value that is now at the top of the stack.

  • Negate: to toggle the sign of the value that is on the top of the stack.

• Increasing and decreasing can be done with access to a constant One (which also counts as a memory access), and could be used in two functions that either increase or decrease the value on the top of the stack.

If we allow for that, we can think of this data model for the stack:

/ Constants
One,        Dec 1
StackBase,  Adr Stack
/ Variables
StackValue, Dec 0         / Copy of the value on top of stack
StackTop,   Adr StackPtr  / Address of value on top of stack
StackPtr,   Adr Stack     / Target of next Push call
Stack,      Dec 0         / Start of stack area
/ Nothing should be put below this point as it is used by the stack

There is some redundancy here, but it is necessary to make it work if we aim to not use any other (temporary) variables.

Implementation

We can then aim for a main program that would look like this:

JnS StackInit  / Stack: empty
JnS PushInput  / Stack: A
JnS PushInput  / Stack: A, B
JnS Subtract   / Stack: A-B
JnS PushInput  / Stack: A-B, C
JnS PushInput  / Stack: A-B, C, D
JnS PushInput  / Stack: A-B, C, D, E
JnS Multiply   / Stack: A-B, C, D*E
JnS PushInput  / Stack: A-B, C, D*E, F
JnS Subtract   / Stack: A-B, C, D*E-F
JnS Multiply   / Stack: A-B, C*(D*E-F)
JnS Sumup      / Stack: A-B+C*(D*E-F)
JnS PushInput  / Stack: A-B+C*(D*E-F), G
JnS PushInput  / Stack: A-B+C*(D*E-F), G, H
JnS PushInput  / Stack: A-B+C*(D*E-F), G, H, K
JnS Multiply   / Stack: A-B+C*(D*E-F), G, H*K
JnS Sumup      / Stack: A-B+C*(D*E-F), G+H*K
JnS Divide     / Stack: (A-B+C*(D*E-F))/(G+H*K)
Output
Halt

It accesses no memory itself, but relies completely on stack-aware functions. Each of these subroutines leaves the result value both on the stack and in the accumulator, so that an intermediate result can always be Output.

Here is the complete program:

JnS StackInit  / Stack: empty
JnS PushInput  / Stack: A
JnS PushInput  / Stack: A, B
JnS Subtract   / Stack: A-B
JnS PushInput  / Stack: A-B, C
JnS PushInput  / Stack: A-B, C, D
JnS PushInput  / Stack: A-B, C, D, E
JnS Multiply   / Stack: A-B, C, D*E
JnS PushInput  / Stack: A-B, C, D*E, F
JnS Subtract   / Stack: A-B, C, D*E-F
JnS Multiply   / Stack: A-B, C*(D*E-F)
JnS Sumup      / Stack: A-B+C*(D*E-F)
JnS PushInput  / Stack: A-B+C*(D*E-F), G
JnS PushInput  / Stack: A-B+C*(D*E-F), G, H
JnS PushInput  / Stack: A-B+C*(D*E-F), G, H, K
JnS Multiply   / Stack: A-B+C*(D*E-F), G, H*K
JnS Sumup      / Stack: A-B+C*(D*E-F), G+H*K
JnS Divide     / Stack: (A-B+C*(D*E-F))/(G+H*K)
Output
JnS Pop
Output
Halt


///////////////////////////////////////////////////////////
/ PushInput()                                             /
/    Get Input and push it on the stack                   /
/    In: --                                               /
/    Return (via stack):                                  /
/        the pushed value                                 /
/    Out: AC = the pushed value                           /
///////////////////////////////////////////////////////////
PushInput,  Hex 0
            Input
            JnS     Push
            JumpI   PushInput
///////////////////////////////////////////////////////////
/ Subtract(a, b)                                          /
/    The two values (on the stack) to take the difference /
/        from                                             /
/    In (via stack):                                      /
/        a: the first operand of the subtraction          /
/        b: the second operand of the subtraction         /
/    Return (via stack):                                  /
/        the value of a - b                               /
/    Out: AC = a - b                                      /
///////////////////////////////////////////////////////////
Subtract,   Hex 0
            JnS     Negate
            JnS     Sumup
            JumpI   Subtract
///////////////////////////////////////////////////////////
/ Multiply(factor, multiplier)                            /
/    The factor times the multiplier                      /
/    In (via stack):                                      /
/        factor: the value to mulitply                    /
/        multiplier: the times to multiply it by          /
/    Return (via stack):                                  /
/        the value of factor * multiplier                 /
/    Out: AC = factor * multiplier                        /
///////////////////////////////////////////////////////////
Multiply,   Hex 0
            JnS     Shift      / Move Multiplier
            JnS     Shift      / Move Factor
            Clear
            JnS     Push       / Insert Product (= 0)
            JnS     UnPop      / Restore Factor
            JnS     UnPop      / Restore Multipler
            SkipCond 000       / Multiplier < 0?
            Jump    EntryMul2  / No: PositiveMul
            / Yes: negate both Factor and Multiplier
            JnS     Negate     / Negate Multiplier
            JnS     Pop        
            JnS     Negate     / Negate Factor
            Jump    EntryMul1

LoopMul,    JnS     Pop        / Put Factor on top
            JnS     Sumup      / Adapt Product by repeated addition
            JnS     UnPop      / Put Factor on top again
EntryMul1,  JnS     UnPop      / Put Multiplier on top
EntryMul2,  JnS     Decrease   / Decrement Multiplier
            SkipCond 000       / Multiplier < 0 ?
            Jump    LoopMul    / No: repeat
            JnS     Pop        / Discard Multiplier (0)
            JnS     Pop        / Discard Factor
            JnS     Peek()     / Get Product
            JumpI   Multiply
///////////////////////////////////////////////////////////
/ Divide(dividend, divisor)                               /
/    The dividend is divided by the divisor               /
/    In (via stack):                                      /
/        dividend: the value to divide                    /
/        divisor: the value to divide by                  /
/    Return (via stack):                                  /
/        the value of dividend / divisor                  /
/    Out: AC = dividend / divisor                         /
///////////////////////////////////////////////////////////
Divide,     Hex 0
            JnS     Pop         / Pop Divisor
            JnS     Peek        / Read Dividend
            SkipCond 000        / Dividend < 0?
            Jump    PositiveDiv / No: PositiveDiv
            / Yes: negate both Dividend and Divisor
            JnS     Negate      / Negate Dividend
            JnS     UnPop       / Restore Divisor
            JnS     Negate      / Negate Divisor
            Jump    ShiftDiv 
PositiveDiv,JnS     UnPop       / Get Divisor
ShiftDiv,   JnS     Push        / Duplicate Divisor as Sign (for sign check at end)
            JnS     Shift       / Shift Sign
            SkipCond 000        / Divisor < 0?
            JnS     Negate      / No: Make Divisor negative (as we want to subtract)
            / Now dividend is positive (or 0) and divisor is negative (or 0)
            JnS     Shift       / Shift Divisor
            JnS     Shift       / Shift Dividend
            Clear               / Initialise Result
            JnS     Push        / And stack it (below the parameters)
LoopDiv,    JnS     UnPop       / Restore Dividend
            JnS     UnPop       / Restore Divisor
            JnS     Sumup       / Add the negative divisor   
            Skipcond 000        / Dividend is negative?
            Jump    StepDiv     / No: continue
            / Yes: we're done: find sign, push quotient and return
            JnS     UnPop       / Restore Divisor
            JnS     UnPop       / Restore Sign
            JnS     Pop         / Pop it (to get it in AC)
            Skipcond 000        / Sign is minus?
            Jump    DoneDiv     / No: just return the quotient
            JnS     Pop         / Pop Divisor
            JnS     Pop         / Pop Dividend
            JnS     Negate      / Make Quotient negative
            JumpI   Divide      / ...and return
DoneDiv,    JnS     Pop         / Pop Divisor
            JnS     Pop         / Pop Dividend
            JnS     Peek        / Get Quotient
            JumpI   Divide      / ...and return
StepDiv,    JnS     Pop         / Pop Dividend
            JnS     Increase    / Increment Quotient
            Jump    LoopDiv
///////////////////////////////////////////////////////////
/ Shift(value)                                            /
/    The value (on the stack) is pushed again on the      /
/        stack, and then the stack pointer is decremented /
/        twice so the given value is outside the stack    /
/    In (via stack):                                      /
/        value: the value to duplicate                    /
/    Return (via stack):                                  /
/        Nothing. The given value is popped, but future   /
/        UnPop() calls could restore these values         /
/    Out: AC = value                                      /
///////////////////////////////////////////////////////////
Shift,      Hex 0
            JnS     Peek
            JnS     Push
            JnS     Pop
            JnS     Pop
            JumpI   Shift
///////////////////////////////////////////////////////////
/ Increase(value)                                         /
/    The value (on the stack) is increased by 1           /
/    In (via stack):                                      /
/        value: the value to increase                     /
/    Return (via stack):                                  /
/        the increased value                              /
/    Out: AC = value + 1                                  /
///////////////////////////////////////////////////////////
Increase,   Hex 0
            JnS     Peek
            Add     One
            JnS     StackRepl
            JumpI   Increase
///////////////////////////////////////////////////////////
/ Decrease(value)                                         /
/    The value (on the stack) is decreased by 1           /
/    In (via stack):                                      /
/        value: the value to decrease                     /
/    Return (via stack):                                  /
/        the decreased value                              /
/    Out: AC = value - 1                                  /
///////////////////////////////////////////////////////////
Decrease,   Hex 0
            JnS     Peek
            Subt    One
            JnS     StackRepl
            JumpI   Decrease
///////////////////////////////////////////////////////////
/ Sumup(a, b)                                             /
/    The two values (on the stack) are added together     /
/    In (via stack):                                      /
/        a: the first operand of the addition             /
/        b: the second operand of the addition            /
/    Return (via stack):                                  /
/        the value of a + b                               /
/    Out: AC = a + b                                      /
///////////////////////////////////////////////////////////
Sumup,      Hex 0
            JnS     Pop
            AddI    StackTop   / Access to memory managed by the stack. Could be Alternative
            JnS     StackRepl
            JumpI   Sumup
///////////////////////////////////////////////////////////
/ Negate(value)                                           /
/    The value (on the stack) is negated                  /
/    In (via stack):                                      /
/        value: the value to negate                       /
/    Return (via stack):                                  /
/        the negate value                                 /
/    Out: AC = negated value                              /
///////////////////////////////////////////////////////////
Negate,     Hex 0
            Clear
            Subt    StackValue
            JnS     StackRepl
            JumpI   Negate
///////////////////////////////////////////////////////////
/ Push()                                                  /
/    Pushes a value on the stack                          /
/    In: AC = the value to push                           /
/    Out: AC = same                                       /
///////////////////////////////////////////////////////////
Push,       Hex 0
            StoreI  StackPtr
            JnS     UnPop
            JumpI   Push
///////////////////////////////////////////////////////////
/ Pop()                                                   /
/    Pops a value from the stack                          /
/    In: --                                               /
/    Out: AC is the popped value                          /
///////////////////////////////////////////////////////////
Pop,        Hex 0
            Load    StackPtr
            Subt    One
            Jns     StackSync
            LoadI   StackPtr
            JumpI   Pop
///////////////////////////////////////////////////////////
/ UnPop()                                                 /
/    Moves the stack pointer to include a stored value    /
/    In: --                                               /
/    Out: AC is the new value at the top of the stack     /
///////////////////////////////////////////////////////////
UnPop,      Hex 0
            Load    StackPtr
            Add     One
            JnS     StackSync
            JumpI   UnPop
///////////////////////////////////////////////////////////
/ StackRepl()                                             /
/    Replace the top of the stack without moving the      /
/       stack pointer                                     /
/    In: AC is the value to replace                       /
/    Out: AC = same                                       /
///////////////////////////////////////////////////////////
StackRepl,  Hex 0
            Store   StackValue
            StoreI  StackTop
            JumpI   StackRepl
///////////////////////////////////////////////////////////
/ Peek()                                                  /
/    Get the value at the top of the stack without moving /
/       the stack pointer                                 /
/    In: --                                               /
/    Out: AC = the retrieved value                        /
///////////////////////////////////////////////////////////
Peek,       Hex 0
            Load    StackValue   // Could be Pop + Push
            JumpI   Peek
///////////////////////////////////////////////////////////
/ StackInit()                                             /
/    Reset the stack to an empty stack                    /
/    In: --                                               /
/    Out: AC = address of the stack                       /
///////////////////////////////////////////////////////////
StackInit,  Hex 0
            Load    StackBase
            JnS     StackSync
            JumpI   StackInit
///////////////////////////////////////////////////////////
/ StackSync()                                             /
/    Helper function to adapt the stack pointer and       /
/       stack variables dependent on it                   /
/    In: AC = the new value of the stack pointer          /
/    Out: AC = the value on top of the stack              /
///////////////////////////////////////////////////////////
StackSync,  Hex 0
            Store   StackPtr
            Subt    One
            Store   StackTop
            LoadI   StackTop
            Store   StackValue
            JumpI   StackSync
///////////////////////////////////////////////////////////
/ Constants
One,        Dec 1
StackBase,  Adr Stack
/ Variables
StackValue, Dec 0         / Copy of the value on top of stack
StackTop,   Adr StackPtr  / Address of value on top of stack
StackPtr,   Adr Stack     / Target of next Push call
Stack,      Dec 0         / Start of stack area
/ Nothing should be put below this point as it is used by the stack

You can copy this program to MARIE.js.org, assemble and run it. Example input could be (for A...H, K):

10
1
3
2
4
9
-1
2
2

Which outputs 2.

Answer 2

A stack and the subroutines to leverage a stack can be implemented in MARIE with the indirection instructions.

Consider

|             LOAD ONE             
|             STOREI STACKBASE     
|             HALT                 
|                                
|  STACKBASE, HEX FFF              
|  ONE,       HEX 1       

In the MARIE Simulator, once you run the program above and scroll all the way down in the memory window to the very last row, you can see 0001 in the very rightmost position on the lowest row, memory position FFF (since MARIE has 4k 16-bit words, the last word position is 0x1000 - 1 = FFF). With this it is clear any arbitrary memory location can be written to.

Now all a programmer has to do is create and manage an OFFSET, and combine OFFSET with STACKBASE to effectively create a STACKPOINTER.

MARIE's JNS/JUMPI instructions allow us to implement subroutines, so we can make PUSH and POP subroutines that decrement/increment OFFSET and STOREI or LOADI at STACKPOINTER.