2

When I started learning C programming a few years ago, my tutor taught me similar to most of the tutors around the world. She said me the very basic things like any int datatype is of 2 bytes memory. If the following is my code,

#include"stdio.h"
#include"conio.h"
void main()
{
    clrscr();
    int i,n;
    n = 0;
    for(i=0;i<3;i++)
        n = n + i;
    printf("%d",n); //obviously it prints 3
    getch();
}

she will explain like what I have written below. Here my teacher starts off her class yet again. . .

Listen students. Here we have two integer values. So let us draw two boxes each of 2 bytes memory.The first box be the memory space of i and the second box be that of n. At n = 0; 0 gets stored into the box n. As the control gets into the loop, 0 gets stored into the box i intially.

0 0

Now the condition is checked. i < 3. Condition gets true. So now the value of n changes from 0 to n+i i.e., 0+0=0. The first iteration then ends after the increment statement. Now i gets incremented to 1. So our picture becomes like this.

1 0

And now i < 3 again. Condtion gets true. n changes from 0 to n + i i.e., 0+1=1. Don't forget the increment my dears. Only then our iteration gets completed. i++ makes our i to 2 now. And the picture will now look like

2 1

She will go on similarly step by step and will complete when both the boxes get 3, 3 values.

So thats it kids. After we get our boxes like this

3 3

the value of n gets printed on the screen.

3

By that time, I was merely like a kid nodding its head when a teacher claims earth as a circular mass. I never asked her any questions. I felt logically she was perfect. But now I am plentiful of queries. If there is a statement like n = n + i;, won't there be a conflict as both the destination space and the operation space is the same n box? Will the operations be done with the help of any default temporary space for calculations? What will happen if I use a recursive code like the following snippet.

int factorial(int n)
{
    if(n < 2)
    {
        return n;
    }
    else
    {
        n = n * factorial(n - 1);
        return n;
    }
}

How could it be possible to use a single n box as my tutor taught? Won't a new n box be created whenever factorial(n - 1) is called? If I am right, how could the computer know which n box value to be returned? Somebody help me please. I am pulling of hairs from ma head!

  • 1
    Have you asked your instructor? The instructor's job is to try to take you down a particular path of understanding. While we may be able to explain it to you, it may make it more difficult to learn the material the instructor is trying to present. – user40980 Jun 21 '14 at 19:21
  • 2
    note that int datatypes are not always 2 bytes! – mc110 Jun 21 '14 at 22:35
  • 1
    @mc110 I'm sure it was for demonstration purposes rather than actually trying to say that ints are two bytes. – user40980 Jun 21 '14 at 23:15
  • @MichaelT: No problem for me if you explain it to me. I am very much awaiting for your explanations. And the fact is that my teacher is no more here with me for I have completed my schooling. She was my school teacher. – Ramvignesh Jun 22 '14 at 4:51
  • I am shocked to learn that your tutors (or so you say most tutors) would teach programming this way. At the time when I started, both the books and the introduction to programming course I took wouldn't go any where near implementation details. We use graph, charts to visualize pseudocode. At my university, they even changed the syllabus from teaching Java in first programming course to teaching Python to make it easier to focus on the pseudocode and the flow of the program. – InformedA Jun 24 '14 at 12:22
3

How could it be possible to use a single n box as my tutor taught? Won't a new n box be created whenever factorial(n - 1) is called?

Yes, exactly. Each time you call a function, additional memory is set aside for the function arguments and local variables.

Let's drop a couple of levels below C and talk about how a compiled program is laid out in memory1. We're going to assume a 32-bit, x86-like system for this discussion.

While the details vary from platform to platform, the general concepts are the same for most systems you're likely to work on. When a compiled program is loaded into memory, it's usually divided up into several logical segments; one segment contains the machine code, another contains constant (read-only) data items, another contains space for non-constant, global data items, another contains space for the stack, another contains the space for the heap, etc. The general layout looks something like the following (taken from this page):

              +------------------------+ 
high address  | Command line arguments |   
              | and environment vars   |  
              +------------------------+
              |         stack          |
              | - - - - - - - - - - -  |
              |           |            |
              |           V            |
              |                        |
              |           ^            |
              |           |            |
              | - - - - - - - - - - -  |
              |          heap          |
              +------------------------+
              |    global and read-    |
              |       only data        |
              +------------------------+
 low address  |     program text       |
              |    (machine code)      |
              +------------------------+      

As your program runs, it uses the stack to store function arguments and local variables, along with some program state (previous frame pointer, address to the next instruction). On x86-like systems, the stack grows "downwards", towards decreasing addresses. Among the registers2 provided, there are usually two to keep track of what's on the stack. There's the stack pointer, which points to the most recent item on the stack, and the frame pointer3, which points to the current stack frame. A stack frame is a region of the stack that contains the arguments and local variables for the current function, along with any saved program state:

             + - - - - - - - - -  +
high address |  previous stack    |
             |       frame        |
             + - - - - - - - - -  +
             |  previous stack    |
             |       frame        |
             +--------------------+  ----------------------+
             | function arguments |                        |
             |        ...         |                        |
             +--------------------+                        |
             |   return address   |                        |
             +--------------------+                        +-- current stack frame
             | old frame pointer  | <-- frame pointer      |
             +--------------------+                        |
             |  local variables   |                        |
             |        ...         | <-- stack pointer      |
             +--------------------+ -----------------------+  
 low address |  available memory  |       
             + - - - - - - - - -  +  

On the systems I'm familiar with, the function arguments and program state are stored "above" the location stored in the frame pointer, and local variables are stored "below" it. Within the generated assembly code, arguments and variables are referred to by their offset from the address stored in the frame pointer. On x86. it would look something like

cmpl  $1, 8(%ebp)   ;; compare the literal value 1 to the first function argument
movl  $1, -4(%ebp)  ;; write the literal value 1 to the first local variable

The first function argument is stored 8 bytes "above" the address value stored in the frame pointer %ebp, while the first local variable would be 4 bytes "below" it (note that this assumes a 32-bit system).

The exact size of the frame depends on how many arguments and local variables need to be stored, although the platform may also require it to be aligned to certain boundary (IOW, the size of the frame must be a multiple of some number of bytes, usually 4 or 8, sometimes 16; for the purposes of this discussion, we're not going to worry about alignment).

Suppose your factorial function is called with an argument value of 3:

x = factorial( 3 );

A new stack frame will be set up that looks something like this:

 +--------------------+
 |         3          | <-- n
 +--------------------+
 |   return address   |
 +--------------------+
 |  old frame pointer | <-- frame pointer, stack pointer
 +--------------------+

where the "return address" is the address of the instruction immediately following the function call in the caller (in this case, it would be the instruction that assigns the result of factorial(3) to x).

Since there are no local variables, no space is allocated for them in the stack frame. Now, since n is not less than 2, you execute the line

n = n * factorial( n - 1 );

This means factorial is called again, this time with an argument value of 2. A new stack frame is created

 +--------------------+
 |         3          | <-- n
 +--------------------+
 |   return address   |
 +--------------------+
 |  old frame pointer | 
 +--------------------+
 |         2          | <-- n
 +--------------------+
 |   return address   |
 +--------------------+
 |  old frame pointer | <-- frame pointer, stack pointer
 +--------------------+

n is still not less than 2, so we call factorial again with an argument of 1:

 +--------------------+
 |         3          | <-- n
 +--------------------+
 |   return address   |
 +--------------------+
 |  old frame pointer | 
 +--------------------+
 |         2          | <-- n
 +--------------------+
 |   return address   |
 +--------------------+
 |  old frame pointer | 
 +--------------------+
 |         1          | <-- n
 +--------------------+
 |   return address   |
 +--------------------+
 |  old frame pointer | <-- frame pointer, stack pointer
 +--------------------+

1 is less than 2, so we execute the line

return n;  

The common convention for returning values from functions is to write the value to a particular register. On x86, integer values are returned through register %eax, so the compiled code will do something like

movl  8(%ebp), %eax

Now register %eax will contain the value 1.

When the function returns, the stack and frame pointers are restored to their previous values (the stack contents are left as-is):

 +--------------------+
 |         3          | <-- n
 +--------------------+
 |   return address   |
 +--------------------+
 |  old frame pointer | 
 +--------------------+
 |         2          | <-- n
 +--------------------+
 |   return address   |
 +--------------------+
 |  old frame pointer | <-- frame pointer, stack pointer
 +--------------------+
 |         1          | <-- n
 +--------------------+
 |   return address   |
 +--------------------+
 |  old frame pointer | 
 +--------------------+

So now we need to execute the remainder of

n = n * factorial( n - 1 );  

which will look something like4

movl %eax, %edx     ;; save the value returned from factorial(1) to register %edx
movl 8(%ebp), %eax  ;; move the value of n (2) to %eax
imull %eax, %edx    ;; multiply the values in %eax and %edx, save the result in
                    ;; %eax

Once again, we return n and exit the function, bringing us back to the previous call:

 +--------------------+
 |         3          | <-- n
 +--------------------+
 |   return address   |
 +--------------------+
 |  old frame pointer | <-- frame pointer, stack pointer
 +--------------------+
 |         2          | <-- n
 +--------------------+
 |   return address   |
 +--------------------+
 |  old frame pointer | 
 +--------------------+
 |         1          | <-- n
 +--------------------+
 |   return address   |
 +--------------------+
 |  old frame pointer | 
 +--------------------+

Lather, rinse, repeat. The value returned in %eax (2) is multiplied by the value in the argument 8(%ebp) (3), and we write 6 back to %eax.

Now, the C language definition says nothing about stacks, or stack frames, or registers, or anything like that; it only specifies the behavior of variables within a program, not how to implement that behavior. However, much of C's design is based on what most computer systems already provide (this is what people mean when they say that C is "close to the hardware"), so this is a very natural way of implementing that behavior. If you were working on a machine that had no stack, C programs would be somewhat more difficult to implement.


1. By which I mean a virtual address space, which is an idealized model of memory that your program sees; the OS and memory controllers will map this idealized model to physical RAM.

2. A register is a memory cell on the CPU itself. There are usually several special-purpose registers (program counter, stack pointer, frame pointer) and some number of general-purpose registers. Reading and writing to registers is faster than reading and writing to RAM.

3. On 32-bit x86, the stack pointer register is esp and the frame pointer register is ebp (a.k.a. the base pointer). On 64-bit x86, they're named rsp and rbp.

4. This is how the compiled code on my system does it, anyway.

7

This is a very good question -- to ask your instructor. She no doubt has a plan (or syllabus) of what she's going to teach and the order she's going to teach it in.

The first example you show with the for loop might come of of chapter 1 in a text book, while recursion and the factorial example might come from chapter 5. We don't know what's in chapters 2 - 4, and might accidentally cause more confusion than we'd fix.

To try to answer your initial question:

If there is a statement like n = n + i;, won't there be a conflict as both the destination space and the operation space is the same n box?

Think of any variable (such as n) as a bucket that can hold exactly one number at a time. Let's assume that number is 0 for now.

The teaching language BASIC used to have a slightly more verbose way of expressing your statement:

LET n = n + i

The idea is to find the bucket n, get the number from it, do some math (i.e., add the number from the other bucket i), then store that number back into the original bucket n.

The trick is to remember that n = n + 1 is not algebra, but a command to a computer to do something. Using LET was a way to help beginners get past the idea that "=" sometimes means "mathematical equality" and sometimes means "assignment" or "put a copy of the right bucket's stuff into the bucket on the left".

  • +1 for explaining it simply. I was still struggling how to best explain without saying that n is picked up from memory and pushed in a register in ALU, 1 goes in another register, ALU does some coolness, and result goes from another register back to the memory to which n points :-) – Omer Iqbal Jun 22 '14 at 3:23
  • @DanPichelman: Thanks. I was imagining very same like the answer of yours. I have passed out my schooling and I don't know where my instructor lives by now. So, no problem if you fix up the recursion query as well. I am much hungry to learn about it. Also, can you suggest me a book that teaches C technically precise with some pictorial examples if possible? Sorry for the picture demand. My teacher has moulded me so :-) – Ramvignesh Jun 22 '14 at 12:58
  • @Ramvignesh - it's best if you ask a second question for the recursion bit. P.SE works best if we avoid multi-part questions. It's OK to include a link back to this question. – Dan Pichelman Jun 22 '14 at 19:08
  • @Ramvignesh - resource recommendations are off topic here (see Help center for more info - the answers aren't very useful to others and they don't age well). For example, I learned C about 25 years ago - the books I used may well be obsolete by now. – Dan Pichelman Jun 22 '14 at 19:10
  • @DanPichelman: P.SE ? Did you mean Programmers Stack Exchange ? Won't my question be tagged as duplicate ? – Ramvignesh Jun 23 '14 at 15:23
1

The = in C does not mean mathematical equality. For mathematical equality, in C you could write, for example:

n == n + i

This is a logical expression whose value will be true when the value of i is zero, and false at any other time.

The expression n = n + i means, "Modify n so that the new value of n will equal the sum of i added to the old value of n." In some other computer languages this operation is given a symbol different from =; for example, := or <-. It just so happens, however, that in C the symbol for this operation is =.

In the case where you call factorial(n - 1) from within the factorial function, the computer uses an area of memory called the "stack". Within the stack, there may be many "frames". Each frame contains all the little boxes of memory that the computer has allocated for the use of just one invocation of a function. The first time you call factorial, a stack frame is allocated and a box for the variable n is created there. When that invocation of factorial calls factorial(n - 1), a new stack frame is created and a new box for the variable n is created. So there are now two stack frames, each of which contains a box named n. Since at this point the first invocation of the function hasn't actually executed the = operation yet (because it has to finish evaluating factorial(n - 1) first), the n box in its stack frame still contains the same value you originally passed to that function. The n box in the second stack frame contains a value that is (initially) 1 less than the value in the first frame's n box.

Of course, that assumes you are able to compile the program so that the computer will execute any of it.

  • Thanks for your answer. Got almost what I wanted. Where will the stack reside? Inside the RAM? – Ramvignesh Jun 23 '14 at 15:59
  • Technically the stack is in virtual memory, so it is wherever the underlying system decides to put it, but usually I'd expect the part of the stack that's actually in use to be in RAM. From the point of view of a typical C programmer, this is not something you have a lot of control over or should spend too much time worrying about. – David K Jun 23 '14 at 17:15
  • More than a C programmer I am turning out a computer lover now-a-days. :) And now, I don't really believe in something called virtual memory. Do look my recent query in the superuser. Your answers are welcome. – Ramvignesh Jun 25 '14 at 12:31
  • "Virtual memory" is simply what we call the mechanism by which commonly-used operating systems find a place to store the memory allocated by programs. The fact that we can read and write data from a C program proves that a mechanism exists (but doesn't tell us exactly how it works). It just happens that typical computers often put some program memory on a disk and makes it "look like" RAM. When you write your own operating system and C compiler, however, you may choose to use only directly-addressed physical RAM if you like, and I won't insist on calling it "virtual" memory. – David K Jun 25 '14 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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