Apologies in advance for the naivety of this question. I am a 50 year old artist trying to properly understand computers really for the first time. So here goes.

I have been trying to understand how data types and variables are handled by a compiler (in a very general sense, I know there is a lot to it). I'm missing something in my understanding of the relationship between storage in "the stack" and value types, and storage on "the heap" and reference types (the quotation marks are meant to signify that I understand that these terms are abstractions and not to be taken too literally in such a simplified context as the way I am framing this question). Anyway, my simplistic idea is that types like Booleans and integers go on "the stack" because they can, because they are known entities in terms of storage space, and their scope is easily controlled accordingly.

But what I don't get is how variables on the stack are then read by an application- if I declare and assign x as an integer, say x = 3, and storage is reserved on the stack and then its value of 3 is stored there, and then in the same function I declare and assign y as, say 4, and then following that I then use x in another expression, (say z = 5 + x) how can the program read x in order to evaluate z when it is below y on the stack? I am clearly missing something. Is it that the location on the stack is only about the lifetime/ scope of the variable, and that the whole stack is actually accessible to the program all the time? If so, does that imply there is some other index that holds the addresses only of the variables on the stack to allow the values to be retrieved? But then I thought the whole point of the stack was that values were stored in the same place as the variable address? In my puny mind it seems that if there is this other index, then we are talking about something more like a heap? I'm clearly very confused, and I'm just hoping there is a simple answer to my simplistic question.

Thanks for reading this far.

  • 7
    @fade2black I disagree -- it should be possible to give an answer of reasonable length that summarizes the important points. – David Richerby Jun 16 '17 at 10:36
  • 8
    You are making the extremely common error of conflating the kind of value with where it is stored. It's simply false to say that bools go on the stack. Bools go in variables, and variables go on the stack if their lifetimes are known to be short, and on the heap if their lifetimes are not known to be short. For some thoughts on how this relates to C#, see blogs.msdn.microsoft.com/ericlippert/2010/09/30/… – Eric Lippert Jun 16 '17 at 16:54
  • 7
    Also, don't think of the stack as a stack of values in variables. Think of it as a stack of activation frames for methods. Within a method you can access any variable of the activation of that method, but you cannot access the variables of the caller, because they are not in the frame that's on top of the stack. – Eric Lippert Jun 16 '17 at 16:55
  • 5
    Also: I applaud you for taking the initiative to learn something new, and to dig into the implementation details of a language. You're running into an interesting stumbling block here: you understand what a stack as an abstract data type is, but not as an implementation detail for reifying activation and continuation. The latter does not follow the rules of the stack abstract data type; it treats them more as guidelines than as rules. The whole point of programming languages is to ensure that you don't have to understand these abstracted-away details to solve programming problems. – Eric Lippert Jun 16 '17 at 23:39
  • 3
    Thank you Eric, Sava, Thumbnail, those comments and references are all extremely helpful. I always feel like people like you must groan inwardly when they see a question like mine, but please know the enormous excitement and satisfaction in getting answers! – Celine Atwood Jun 17 '17 at 9:41

Storing local variables on a stack is an implementation detail – basically an optimization. You can think of it this way. When entering a function, space for all local variables is allocated somewhere. You can then access all variables, since you know their location somehow (this is part of the process of allocation). When leaving a function, the space is deallocated (freed).

The stack is one way of implementing this process – you can think of it as a kind of "fast heap" which has limited size and so is only appropriate for small variables. As an additional optimization, all local variables are stored in one block. Since each local variable has known size, you know the offset of each variable in the block, and that is how you access it. This is in contrast to variables allocated on the heap, whose addresses are themselves stored in other variables.

You can think of the stack as very similar to the classical stack data structure, with one crucial difference: you are allowed to access items below the top-of-stack. Indeed, you can access the $k$th item from the top. This is how you can access all your local variables with pushing and popping. The only pushing being done is upon entering the function, and the only popping upon leaving the function.

Finally, let me mention that in practice, some of the local variables are stored in registers. This is since access to registers is faster than access to the stack. This is another way of implementing a space for local variables. Once again, we know exactly where a variable is stored (this time not via offset, but via the name of a register), and this kind of storage is only appropriate for small data.

  • 1
    "Allocated in one block" is another implementation detail. It doesn't matter, though. The compiler knows how memory is needed for the local variables, it allocates that memory it one or more blocks, and it then creates the local variables in that memory. – MSalters Jun 16 '17 at 11:56
  • Thanks, corrected. Indeed, some of these "blocks" are just registers. – Yuval Filmus Jun 16 '17 at 12:03
  • 1
    You only really need the stack to store the return addresses, if that. You could implement recursion without a stack quite easily, by passing a pointer to the return address on the heap. – Yuval Filmus Jun 16 '17 at 23:17
  • 1
    @MikeCaron Stacks have almost nothing to do with recursion. Why would you "blow away the variables" in other implementation strategies? – gardenhead Jun 17 '17 at 1:07
  • 1
    @gardenhead the most obvious alternative (and one that actually is/was used) is to statically allocate each procedure's variables. Fast, simple, predictable... but no recursion or reentrancy allowed. That and the conventional stack aren't the only alternatives of course (dynamically allocating everything is another), but they're usually the ones to discuss when justifying stacks :) – hobbs Jun 17 '17 at 5:50

Having y on the stack doesn't physically prevent x from being accessed, which, as you pointed out, makes computer stacks different from other stacks.

When a program is compiled, the positions of variables in the stack are also predetermined (within the context of a function). In your example, if the stack contains an x with a y "on top of" it, then the program knows in advance that x will be 1 item below the top of the stack while inside the function. Since the computer hardware can explicitly ask for 1 item below the top of the stack, the computer can get x even though y also exists.

Is it that the location on the stack is only about the lifetime/ scope of the variable, and that the whole stack is actually accessible to the program all the time?

Yes. When you exit a function, the stack pointer moves back to its previous position, effectively erasing x and y, but technically they will still be there until the memory is used for something else. Additionally, if your function calls another function, x and y will still be there and can be accessed by intentionally going too far down in the stack.

  • 1
    This seems like the cleanest answer so far in terms of not talking beyond the background knowledge that OP brings to the table. +1 for really targeting OP! – Ben I. Jun 16 '17 at 18:45
  • @BenI. Thanks. I tried – acbabis Jun 16 '17 at 18:49
  • 1
    I also agree! Although all of the answers are extremely helpful and I am very grateful, my original post was motivated because I sense(d) that this whole stack/heap thing is absolutely fundamental to understanding how the value/reference type distinction arises, but I couldn't see how if you could only ever view the top of "the stack". So your answer frees me from that. (I get the same feeling I got when I first realised all the various inverse square laws in physics simply fall out of the geometry of radiation coming out of a sphere, and you can draw a simple diagram to see it.) – Celine Atwood Jun 17 '17 at 9:23
  • I love it because it is always enormously helpful when you can see how and why some phenomenon at a higher level (eg. in the language) is really due to some more basic phenomenon a little further down the abstraction tree. Even if it is kept pretty simple. – Celine Atwood Jun 17 '17 at 9:28
  • 1
    @CelineAtwood Please note that trying to access variables "by force" after they've been removed from the stack will give you unpredictable/undefined behavior and should not be done. Notice I didn't say "can't" b/c some languages will allow you to try it. Still, it'd be a programming mistake and should be avoided. – code_dredd Jun 19 '17 at 5:08

There are two special registers: ESP (stack pointer) and EBP (base pointer). When a procedure is invoked the first two operations are usually

push        ebp  
mov         ebp,esp 

The first operation saves the value of the EBP on the stack, and the second operation loads the value of the stack pointer into the base pointer (to access the local variables). So, EBP points to the same location as ESP does.

Assembler translates variables names into EBP offsets. For example, if you have two local variables x,y, and you have something like

  x = 1;
  y = 2;
  return x + y;

then it may be translated into something like

   push        ebp  
   mov         ebp,esp
   mov  DWORD PTR [ ebp + 6],  1   ;x = 1
   mov  DWORD PTR [ ebp + 14], 2   ;y = 2
   mov  eax, [ ebp + 6 ]
   add  [ ebp + 14 ], eax          ; x + y 
   mov  eax, [ ebp + 14 ] 
   ...  

Offset values 6 and 14 are computed at compile time.

This is roughly how it works. Refer to a compiler book for details.

  • 14
    This is specific to the intel x86. On ARM, register SP (R13) is used, as well as FP (R11). And on x86, the lack of registers means that aggressive compilers will not use EBP as it can be derived from ESP. This is clear int he last example, where all EBP-relative addressing can be translated to ESP-relative, with no other change needed. – MSalters Jun 16 '17 at 11:51
  • Aren't you missing a SUB on ESP to make room for x,y in the first place? – Hagen von Eitzen Jun 19 '17 at 5:57
  • @HagenvonEitzen, probably. I just wanted to express idea how variables allocated on stack are accessed using hardware registers. – fade2black Jun 19 '17 at 9:36
  • Downvoters, comments please!!! – fade2black Aug 5 '17 at 23:10

To provide a concrete example of how a compiler manages the stack and how values on the stack are accessed, we can look at visual depictions, plus code generated by GCC in a Linux environment with i386 as the target architecture.

1. Stack frames

As you know, the stack is a location in the address space of a running process that is used by functions, or procedures, in the sense that space is allocated on the stack for variables declared locally, as well as arguments passed to the function (space for variables declared outside any function (i.e. global variables) is allocated in a different region in virtual memory). Space allocated for all of a function's data is referred to a stack frame. Here is a visual depiction of multiple stack frames (from Computer Systems: A Programmer's Perspective):

CSAPP stack frame

2. Stack frame management and variable location

In order for values written to the stack within a particular stack frame to be managed by the compiler and read by the program, there must be some method for calculating the positions of these values and retrieving their memory address. The registers in the CPU referred to as the stack pointer and the base pointer help with this.

The base pointer, ebp by convention, contains the memory address of the bottom, or base, of the stack. The positions of all of the values within the stack frame can be calculated using the address in the base pointer as a reference. This is depicted in the picture above: %ebp + 4 is the memory address stored in the base pointer plus 4, for example.

3. Compiler-generated code

But what I don't get is how variables on the stack are then read by an application- if I declare and assign x as an integer, say x = 3, and storage is reserved on the stack and then its value of 3 is stored there, and then in the same function I declare and assign y as, say 4, and then following that I then use x in another expression, (say z = 5 + x) how can the program read x in order to evaluate z when it is below y on the stack?

Let us use a simple example program written in C to see how this works:

int main(void)
{
        int x = 3;
        int y = 4;
        int z = 5 + x;

        return 0;
}

Let us examine the assembly text produced by GCC for this C source text (I cleaned it up a bit for the sake of clarity):

main:
    pushl   %ebp              # save previous frame's base address on stack
    movl    %esp, %ebp        # use current address of stack pointer as new frame base address
    subl    $16, %esp         # allocate 16 bytes of space on stack for function data
    movl    $3, -12(%ebp)     # variable x at address %ebp - 12
    movl    $4, -8(%ebp)      # variable y at address %ebp - 8
    movl    -12(%ebp), %eax   # write x to register %eax
    addl    $5, %eax          # x + 5 = 9
    movl    %eax, -4(%ebp)    # write 9 to address %ebp - 4 - this is z
    movl    $0, %eax
    leave

What we observe is that variables x, y and z are located at addresses %ebp - 12, %ebp -8 and %ebp - 4, respectively. In other words, the locations of the variables within the stack frame for main() are calculated using the memory address saved in the CPU register %ebp.

4. Data in memory beyond the stack pointer is out of scope

I am clearly missing something. Is it that the location on the stack is only about the lifetime/ scope of the variable, and that the whole stack is actually accessible to the program all the time? If so, does that imply there is some other index that holds the addresses only of the variables on the stack to allow the values to be retrieved? But then I thought the whole point of the stack was that values were stored in the same place as the variable address?

The stack is a region in virtual memory, whose use is managed by the compiler. The compiler generates code in such a way that values beyond the stack pointer (values beyond the top of the stack) are never referenced. When a function is called, the position of the stack pointer changes to create space on the stack deemed to be not "out of bounds", so to speak.

As functions are called and return, the stack pointer is decremented and incremented. Data written to the stack does not disappear after it is out of scope, but the compiler does not generate instructions referencing this data because there is no way for the compiler to calculate the addresses of these data using %ebp or %esp.

5. Summary

Code that can be directly executed by the CPU is generated by the compiler. The compiler manages the stack, stack frames for functions and CPU registers. One strategy used by GCC to track the locations of variables in stack frames in code intended to execute on i386 architecture is to use the memory address in the stack frame base pointer, %ebp, as a reference and write values of variables to locations in the stack frames at offsets to the address in %ebp.

  • Mine if I ask where that image came from? It looks suspiciously familiar... :-) It might've been in a past textbook. – The Great Duck Jun 18 '17 at 5:50
  • 1
    nvmd. I just saw the link. It was what I thought. +1 for sharing that book. – The Great Duck Jun 18 '17 at 5:51
  • 1
    +1 for the gcc assembly demo :) – flow2k Apr 12 at 5:14

You are confused because the local variables stored in stack are not accessed with the access rule of stack: First In Last Out, or just FILO.

The thing is that the FILO rule applies to function call sequences and stack frames, rather than to local variables.

What is a stack frame?

When you enter a function, it is given some amount of memory on the stack, called stack frame. Local variables of the function are stored in the stack frame. You can imagine that the size of stack frame varies from function to function since each function has different numbers and sizes of local variables.

How local variables are stored in the stack frame has nothing to do with FILO. (Even the order of appearance of your local variables in your source code does not ensure that local variables will be stored in that order.) As you properly deduced in your question, "there is some other index that holds the addresses only of the variables on the stack to allow the values to be retrieved". The addresses of local variables are typically calculated with a base address, such as the boundary address of the stack frame, and offset values specific to each local variable.

So when does this FILO behavior appear?

Now, what happens if you call another function? The callee function must have its own stack frame, and it is this stack frame that is pushed in the stack. That is, the callee function's stack frame is placed on top of the caller function's stack frame. And if this callee function calls another function, then its stack frame will be pushed, again, on the top of the stack.

What happens if a function returns? When a callee function returns to the caller function, the callee function's stack frame is popped out from the stack, freeing space for future use.

So from your question:

Is it that the location on the stack is only about the lifetime/scope of the variable, and that the whole stack is actually accessible to the program all the time?

you are quite correct here because the local variable values on the stack frame are not really erased when the function returns. The value just stays there, although the memory location where it is stored doesn't belong to any function's stack frame. The value is erased when some other function gains its stack frame which includes the location and writes over some other value to that memory location.

Then what differenciates stack from heap?

Stack and heap are same in the sense that they are both names that refer to some space on memory. Since we can access any location on memory with its address, you can access any location in stack or heap.

The difference comes from the promise that the computer system makes about how it's going to use them. As you said, heap is for reference type. Since the values in heap have no relation to any specific stack frame, the scope of the value is not tied to any function. A local variable, however, is scoped within a function, and although you can access any local variable value that is located out of current function's stack frame, the system will try to make sure that this kind of behavior doesn't happen, by using stack frames. This gives us some kind of illusion that the local variable is scoped to a specific function.

There are many ways to implement local variables by a language runtime system. Using a stack is a common efficient solution, used in many practical cases.

Intuitively, a stack pointer sp is kept around at runtime (in a fixed address, or in a register -- it does really matter). Assume that every "push" increments the stack pointer.

At compile time, the compiler determines the address of each variable as sp - K where K is a constant which only depends on the scope of the variable (hence can be computed at compile time).

Note that we are using the word "stack" here in a loose sense. This stack is not accessed only through push/pop/top operations, but is also accessed using sp - K.

For instance consider this pseudocode:

procedure f(int x, int y) {
  print(x,y);    // (1)
  if (...) {
    int z=x+y; // (2)
    print(x,y,z);  // (3)
  }
  print(x,y); // (4)
  return;
}

When the procedure is called, arguments x,y can be passed on the stack. For simplicity, assume the convention is the the caller pushes x first, then y.

Then, the compiler at point (1) can find x at sp - 2 and y at sp - 1.

At point (2), a new variable is brought in scope. The compiler generates code that sums x+y, i.e. what's pointed by sp - 2 and sp - 1, and pushes the result of the sum on the stack.

At point (3), z is printed. The compiler knows it is the last variable in scope, so it's pointed by sp - 1. This is no longer y, since sp changed. Still, to print y the compiler knows that it can find it, in this scope, at sp - 2. Similarly, x is now found at sp - 3.

At point (4), we exit the scope. z is popped, and y is again found at address sp - 1, and x is at sp - 2.

When we return, either f or the caller pops x,y from the stack.

So, computing K for the compiler is a matter of counting how many variable are in scope, roughly. In the real world, this is actually more complex since not all variables have the same size, so the computation of K is slightly more complex. Sometimes, the stack also contains the return address for f, so K must "skip over" that as well. But these are technicalities.

Note that, in some programming languages, things can become even more complex if more complex features must be handled. E.g. nested procedures require a very careful analysis, since K now has to "skip over" many return addresses, especially if the nested procedure is recursive. Closures / lambdas / anonymous functions also require some care to handle "captured" variables. Still, the above example should illustrate the basic idea.

The easiest idea is to think of variables as fix names for addresses in memory. Indeed, some assemblers display machine code that way ("store value 5 in address i", where i is a variable name).

Some of these addresses are "absolute", like global variables, some are "relative", like local variables. Variables (i.e. addresses) in functions are relative to some place on the "stack" which is different for every function invocation; that way the same name can refer to different actual objects, and circular calls to the same function are independent invocations working on independent memory.

Data items that can go on the stack are put on the stack - Yes! It is a premium space. Also, Once we pushed x into stack and then pushed y into the stack, ideally we cannot access x until y is there. We need to pop y to access x. You got them correct.

The stack is not of variables, but of frames

Where you got it wrong is about the stack itself. On the stack it is not the data items that are directly pushed. Rather, on the stack something called stack-frame is pushed. This stack-frame contains the data items. While you cannot access the frames deep within the stack, you can access the top frame and all data items contained within it.

Lets say we have our data items bundled in two stack frames frame-x and frame-y. We pushed them one after the other. Now as long as frame-y sits on top of frame-x, you cannot ideally access any data item inside frame-x. Only frame-y is visible. BUT given that frame-y is visible, you can access all the data-items bundled in it. The whole of the frame is visible exposing all the data items contained within.

End of answer. More (rant) on these frames

During compilation, a list of all functions in the program is made. Then for each function a list of stackable data items is made. Then for each function a stack-frame-template is made. This template is a data structure which contains all those chosen variables, space for function's input data, output data etc. Now during runtime, whenever a function is called, a copy of this template is put on stack - along with all the input and intermediate variables. When this function calls some other function, then a fresh copy of that function's stack-frame is put on stack. Now as long as that function is running, this function's data items are preserved. Once that function ends, its stack-frame is popped out. Now this stack-frame is active and this function can access all its variables.

Do note that the structure and composition of a stack-frame varies from programming language to programming language. Even within a language there could be subtle differences in different implementations.


Thank you for considering CS. I am a programmer now a days taking piano lessons :)

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.