WRITE LC3 ASSEMBLER

If we implement a runtime stack using an array, we dont need a dynamic link pointer to the activation record, so all we need are spaces for parameters, the return value, the return address, and local variables.

A sketch of the program from Problem 1 into low-level pseudocode follows. You are to implement the pseudocode in LC3 assembler. (You dont have to stop at locations A and B in Problem 1.)

When calling RecSum, the stack should have S as the top element and N just below it. (Ill write this as ... N S [top to the right].) RecSum should begin by completing the activation record (stack = ... N S [space for result] R7) *. When RecSum returns, the stack should be ... N S result (because R7 was popped off to restore it).. The top-level call to RecSum is done by Sum, which is called by the main program. Sum should initialize the stack, set it to R7 N 0 and call RecSum. When RecSum returns, Sum should pop the returned value off the stack and return it (after clearing out the stack). Note: RecSum is written as a tail-recursive routine: Once the base case figures out what it wants to return, all of the recursive calls just return that same value.

Pseudocode

; ; 

; recursively calculate sum(N) = 1 + 2 + ... + N ; 

.ORIG x8000

; main calls sum(N), stores result in S ; 

LD R0, N JSR SUM ST R0, S HALT 

; prep for sum(N) ; R0 = sum(N) ; S = sum(N) 

; N is a constant, S is space for result ; N .FILL 100 S .BLKW 1 

; Top-level SUM retrieves N from R0, sets up the stack, and ; makes the 1st-level call to RecSum. On return we save the ; result, restore R7, clean up, and return. ; ; Sum and RecSum share register *** STUB ***, which points to the ; top of the stack. ; *** STUB *** (Any registers destroyed?) ; RecSum 

SUM Init stack Push R7 

 Push N Push 0 JSR RecSum Save result into R0 

stack = empty stack = R7 stack=R7N stack=R7N0 On return, stack = R7 N 0 result

stack = ... N S [top] 

Restore R7

 Clean up stack Return (JMP R7) 

; RecSum(N, S) = S if N <= 0, else = RecSum(N-1, S+N) ; ; RecSum expects stack: ... N S [top], returns with ... N S result ; Relies on *** STUB *** = & top of stack ; *** STUB *** (Any registers destroyed?) ; ; In comments below, [result] means result has not yet been calculated ; RecSum 

Push result space Push R7 if N <= 0 then .setresult=S else

. Calculate N-1 . Push N-1 . Calculate S+N . Push S+N 

. JSR RecSum

stack = ... N S stack = ... N S [result] stack = ... N S [result] R7 

. Get the recursive result (rec_res) . Set our result = recursive result . Pop off recursive result, S+N, and N-1 

 endif Restore R7 Return 

stack .BLKW big number .END 

 stack = ... N S result R7 stack = ... N S result 

; array holding stack 

stack = ... N S result R7 

stack = ... N S [result] R7 N-1 

stack = ... N S [result] R7 N-1 S+N on return, stack = ... N S [result] R7 N-1 S+N rec_res 

Implementing the stack: You get to decide how to implement your array stack.

Is top is at higher address? Lower address?

Does top point to next space to fill with a push? Or the value last pushed?

Recommended: Use a register to hold the address of the top of the stack. That way you can use LDR

and STR to access locations near the top of the stack.

Grading Scheme [35 points total]

[25 points] Roughly one point for each line of pseudocode in Sum and RecSum above.

[10 points] Comments with your assembler program (extremely important!). Use the lines of

pseudocode as the starting point for figuring out what to write for comments.