Project 8, the second half

[Lozminda]

Have been thinking a while, and i appreciate that the authors don't want to hand you everything on a plate..

I'm surmising that the global stack (fig 8.8) is going to start at RAM[500] (for arguments sake, that gives you space for a hundred lcl vars and 100 args), as there wouldn't be room between R[256] and R[300], the beginning of LCL.
Starting at address 500, this gives you 2500 addresses before you hit THAT or THIS ? Should I be using say 3200 onwards ?

Thanks in advance for your help.

As just a general aside (a moral booster perhaps for the 50% of us that are below average intelligence) I am finding this jump (as in the conceptual leap i have to make to get the project done specifically function call and return) large. Assuming that my assumption above is correct i think i'm making some headway, so don't worry y'all keep at it, you'll get it eventually.  I had this flash(?) over breakfast. Naturally if the above assumption is wrong it's back to the drawing board! Cheers

Lozminda

[WBahn]

Lozminda wrote

I'm surmising that the global stack (fig 8.8) is going to start at RAM[500] (for arguments sake, that gives you space for a hundred lcl vars and 100 args), as there wouldn't be room between R[256] and R[300], the beginning of LCL.

I'm having a hard time following this. I don't see anything in Fig 8.8 that would imply anything starting at RAM[500]. Are you just throwing that out as a "let's assume" case?

The stack (you only have one, so no need to qualify it as a 'global' stack) starts at RAM[256]. The Heap (unallocated, but allocatable, memory) starts at RAM[2048]. Everything from RAM[256] up through and including RAM[2047] is allocated for the stack. The stack grows and shrinks automatically as functions are called. Each time a function is called, additional memory on the stack is reserved for that function's arguments and local variables. There is no explicit limit on the number of arguments or local variables that a function may have, but the combined total of all of the stack memory needs of all running functions can not push the stack beyond RAM[2047] otherwise the stack will start overwriting objects located in the heap.

Most real systems adopt a convention that the stack starts at one end of memory and the heap starts at the other and they grow toward each other. This allows for flexibility since either one can be large enough to consume nearly all the memory provided it doesn't walk into space that the other one is actually using at that moment. The Hack could have don't that, but the authors apparently believed that having both grow upward in memory would be easier for most people to understand.

Starting at address 500, this gives you 2500 addresses before you hit THAT or THIS ? Should I be using say 3200 onwards ?

THIS and THAT are simply pointers used to point to specific objects that reside in the heap. The heap itself starts at RAM[2048].

[Lozminda]

Dear WBahn

Thanks for your answer. I think I understand what's going on, possibly, but here's some reasons why I've come to the (wrong) conclusions I have. Firstly in answer to your question:-

"I'm having a hard time following this. I don't see anything in Fig 8.8 that would imply anything starting at RAM[500]. Are you just throwing that out as a "let's assume" case? "

Yes (The book lets us come to our own conclusions (or at least our own implementations)
 (I was just assuming this was another one we had to come to, as it were)
--------------------------------------------------------------------------------------------------------------------------

Next re Stack(s)
The book does talk about a global stack in fig 8.8 and 8.4, which would imply there are other stacks to be used. And to quote page 184 :
"These two stack notions are closely related, since the working stack of the current subroutine is located at the very tip of the global stack."
would imply there are at least two stacks, one global and another working stack ?
 --------------------------------------------------------------------------------------------------------------------------

Re LCL at RAM[300] and ARG at RAM[400]
p164 A Typical Arithmetic Task
"Let us focus on the virtual segments depicted at the bottom of figure 7.9. We see that when a VM
function starts running, it assumes that (i) the stack is empty, (ii) the argument values on which it is
supposed to operate are located in the argument segment, and (iii) the local variables that it is supposed
to use are initialized to 0 and located in the local segment."

The book has been indicating (or implying at least) for several chapters that LCL starts at RAM[300] and ARG at R[400] and with that in mind, the local variables aren't now stored at 300 onwards and args at 400 onwards?
I know you've  said "No" but that "seems" to be in contradiction to the book, as some of the various quotes hopefully show.

Your reply would imply that we discard the previous idea that locals are stored at 300 and arguments at 400 ?

Thanks again for your help !

Lozminda

Ps I don't know whether the formatting for clarity has worked, if no, apologies.

[Lozminda]

PPs Re My first message: Back to the drawing board !

[WBahn]

Lozminda wrote

Next re Stack(s)
The book does talk about a global stack in fig 8.8 and 8.4, which would imply there are other stacks to be used. And to quote page 184 :
"These two stack notions are closely related, since the working stack of the current subroutine is located at the very tip of the global stack."
would imply there are at least two stacks, one global and another working stack ?

Ah, I see what you are referring to (although it isn't on page 184 in my printing). The authors are trying to create the illusion that there is a "working stack" that is somehow different from the physical stack (what they call the "global stack"). There's really only one stack, but I can see the utility in thinking of a working stack as being a different entity that just happens to reside on the global stack. I had forgotten that the authors took this approach.

Re LCL at RAM[300] and ARG at RAM[400]
p164 A Typical Arithmetic Task
"Let us focus on the virtual segments depicted at the bottom of figure 7.9. We see that when a VM
function starts running, it assumes that (i) the stack is empty, (ii) the argument values on which it is
supposed to operate are located in the argument segment, and (iii) the local variables that it is supposed
to use are initialized to 0 and located in the local segment."

We definitely have different printings. In my book this is on page 135. So let's specify section numbers. This is in Section 7.2.6. Hopefully these are consistent between printings.

The book has been indicating (or implying at least) for several chapters that LCL starts at RAM[300] and ARG at R[400] and with that in mind, the local variables aren't now stored at 300 onwards and args at 400 onwards?
I know you've  said "No" but that "seems" to be in contradiction to the book, as some of the various quotes hopefully show.

I'm still not seeing anyplace that implies that LCL always starts at RAM[300] and ARG always starts at RAM[400]. Could you provide a reference to where this is stated or implied? My guess is that you are looking at simply an example where they are effectively saying, "Let's assume that the value that happens to be in LCL (RAM[1]) happens to be 300 and the value that happens to be in ARG (RAM[2]) happens to be 400."

In Chapter 7 they are ignoring the details of how the actual locations of these two memory segments is determined (i.e., how the values stored in LCL and ARG get set) because, for the commands you need to implement in Chapter 7 the only thing you need to know is that these two memory locations store the base addresses of these two memory segments. So for discussion in specific examples, they can pick any suitable random values for them.

In Chapter 8 you have to deal with the mechanics of actually determining where these segments reside in memory and you learn that they reside on the stack and that each active call of a function has it's own local and argument memory segment located there. So if we have main() that called fred() that called sue(), there are three functions active and each one has a local and an argument segment. The LCL and ARG registers store the base addresses of the most recently called function, which is sue() in this case. If sue() then called bob(), the LCL and ARG registers will point to bob's memory segments. When bob returns, the LCL and ARG registers will again point to sue's segments and, when sue returns, they will point to fred's. Making this happen is the chore of the function calling and return commands that you implement in Chapter 8.

[Lozminda]

Thank you !

[Lozminda]

The following is just for reference,  (if anyone's that interested).
I've been rereading the chapter in order to get my "function" sorted out and as I've been having a conversation about "two" stacks....
The book also mentions in section 8.2.3 "The called function view"

To quote: "The static segment that the called function sees has been set to the static segment
of the VM file to which it belongs, and the working stack that it sees is empty."

Again this seems to perhaps imply there's more than one stack....one it doesn't see maybe.

As I say just an addendum to my original post, I require no reply, unless someone wishes too.

L

[Lozminda]

I promise this is the last one, I've found another

8.3.1 Standard VM Mapping on the Hack Platform, partII

The Global Stack The memory resources of the VM are implemented by maintaining a global stack. Each
time a function is called, a new block is added to the global stack. The block consists of the arguments
that were set for the called function, a set of pointers used to save the state of the calling function, the
local variables of the called function (initialized to 0), and an empty working stack for the called function.

Figure 8.4 shows this generic stack structure. etc

Again once you know what you're doing it's obvious it's one stack, however I think it's also fairly clear how someone (like me for example) might think more than one stack needs to be implemented a global one and one for the function. Just in case anyone else thinks they might need two stacks please see WBahn's answer, you don't !

All the best L

[linuxford]

Hi Lozminda,
Your comments made perfect sense to me as I'm in the same state of confusion. Thanks for posting.
The function call and return is a tough hurdle.

Work has kept me very busy, and finally I have some more time after several weeks to get back to it.
I'm reviewing the posts and more importantly going back over all the lectures and the book.

It seems like the key is that for each function call, there is a new frame. I'm trying to figure out
how I get a new base address for the frame (callee's ARG, LCL) so I don't overwrite the caller's base address for ARG and LCL.
Looking at some of these posts and the book, it looks like this may be accomplished through use the
current value of SP. There is a section in the book that has a table that seems to confirm this, for instance,

call f n

ARG = SP-n-5
LCL = SP

So I think I'm on the back on the right track, however, I think I fell off the train a few miles back
so I'm playing catchup.

[WBahn]

The key is, indeed, the stack pointer. Remember, the value in the stack pointer represents the first memory cell on the stack that is available. So your if function calling routine places the stack frame for the callee starting at the current location of the stack pointer, the stack frames and any data associated with previous function calls that are still active is safe.

[linuxford]

Thank you. I think I'm understanding better on how to implement the function call and return.

However, what has caused some confusion is the memory segmenting and how/why it works. It seems like when starting the beginning of the program, the base of addresses of LCL and ARG are set by the values in the RAM[1] and RAM[2] respectively. Then as the program progresses, when a function call occurs, the callee does not consider the RAM[1] and RAM[2] locations, but instead uses an offset of the SP.

[WBahn]

Each function invocation has its own LCL, ARG, THIS, and THAT memory segments. The LCL and ARG memory segments physically exist on the stack and the base addresses for those segments are what are stored in LCL and ARG. The THIS and THAT memory segments are constantly shifting because, at any given time, they refer to the memory block for some kind of object. The THIS memory segment usually refers to a memory segment containing an object instance's field variables while the THAT memory segment is usually used to refer to an array.

When the function Fred() is running, the base addresses for its versions of these memory segments are contained in RAM[1] through RAM[4]. This is important because the VM code uses push and pop commands on these memory segments, and the assembly code that gets generated only knows to look in those specific registers to find out where the segments are located.

When Fred() calls Sue(), it is understood that Sue is going to, possibly, need to use those four registers to access HER memory segments. So as part of the function calling process, the base addresses that Fred() was using are stored on the stack (so that they can be restored later) and the base addresses for Sue() are put in LCL and ARG. The THIS and THAT are not touched -- if Sue() needs them, she can just overwrite what is there, because they will get restored later.

Now Sue() is running and she accesses her memory segments, using the push/pop commands, via the LCL, ARG, THIS, and THAT segments.

Now Sue() returns. As part of the function return process, the Fred()'s values of LCL, ARG, THIS, and THAT are copied from their safe storage place on the stack back into the RAM[1] through RAM[4] registers so that when control is returned to Fred(), he is never the wiser that anything changed as far as the location of his memory segments.

[linuxford]

That makes sense, thank you so much!!