Memory
Rather than dive into exactly OCaml handles the memory allocation of values and at runtime (you can find some detail here, here and here), I'll be making some notes about the stack and heap more generally.
First and foremost, a review of the Stack and the Heap. I'll just copy SwankyLegg's post on Stack Overflow here. More can be found here.
Stack is the memory set aside as scratch space for a thread of execution. When a function is called, a block is reserved on the top of the stack for local variables and some bookkeeping data. When that function returns, the block becomes unused and can be used the next time a function is called. The stack is always reserved in a LIFO (last in first out) order; the most recently reserved block is always the next block to be freed. This makes it really simple to keep track of the stack; freeing a block from the stack is nothing more than adjusting one pointer.
Heap is memory set aside for dynamic allocation. Unlike the stack, there's no enforced pattern to the allocation and deallocation of blocks from the heap; you can allocate a block at any time and free it at any time. This makes it much more complex to keep track of which parts of the heap are allocated or free at any given time; there are many custom heap allocators available to tune heap performance for different usage patterns.
Stack is the memory set aside as scratch space for a thread of execution. When a function is called, a block is reserved on the top of the stack for local variables and some bookkeeping data. When that function returns, the block becomes unused and can be used the next time a function is called. The stack is always reserved in a LIFO (last in first out) order; the most recently reserved block is always the next block to be freed. This makes it really simple to keep track of the stack; freeing a block from the stack is nothing more than adjusting one pointer.
Heap is memory set aside for dynamic allocation. Unlike the stack, there's no enforced pattern to the allocation and deallocation of blocks from the heap; you can allocate a block at any time and free it at any time. This makes it much more complex to keep track of which parts of the heap are allocated or free at any given time; there are many custom heap allocators available to tune heap performance for different usage patterns.
This diagram shows us that when we map out memory, from 0 at the bottom to the higher addresses, we can typically find the following layout. We have the stack that starts near the top that grows down and we have the heap that starts at the low addresses and grows up. When the stack and heap collide in the middle, we get a stack overflow error.
|
So let's take a look take another look at the stack when we don't use tail recursion in our factorial function.
When we first call factorial 4, we add the first stack frame to the stack. It says to do 4 * factorial 3. To get the value of factorial 3, we need to call factorial again with the value 3. We can't replace the stack frame here because we store the number 4 in the first stack frame. Then we continue. We need to find the return value of factorial 2. Again, we can't replace the stack frame because we store the value 3 there. And finally, when we can return, we can pop off the stack frames once we don't need them. This is a fine way to recurse, until we build so many stack frames that we overflow the stack. This is why we use tail recursion.
Because memory is so incredibly important to programmers, here are some introductions to memory that are worth taking a look at.