Christopher Allan Webber

Registers vs stacks vs heaps

Christopher Allan Webber at

I'm very slowly continuing to improve my computer science / engineering background. Recently watching the "register machine" episode of SICP I hit an aha moment and emailed my brother (Stephen Webber):

I wonder how close my understanding of how registers vs stacks vs heaps are to reality now...

  • registers: data being used during some operation, generally, a very very temporary place to hold data while computing

  • stacks: grow and shrink with the application's execution; each let for instance will add things on the stack and remove them when you step out of it; most "purely functional" data will be allocated an deallocated from here in a sense

  • heap: data that's going to be accessed and mutated from all sorts of places; needs to more explicitly be allocated and deallocated than the logical append and pop off nature of the stack is this mostly right?

Steve's reply:

All correct.

Said in a different way: Registers are stores of data with unrelated addresses. Carl, Bob, Dave for instance as names/addresses, for example. The names of the registers don't necessarily imply any ordering or spacial relationship.

Stacks are the closest to the Turing machine tape. All addresses are relative by integer offsets.

Heap space is a more complicated model for partitioning, that leaves space for mutation of structures.

Maybe helpful for someone else trying to work their way through this stuff?

pingi, Sven Drieling, bthall, Claes Wallin (韋嘉誠) and 1 others likes this.

Claes Wallin (韋嘉誠), Claes Wallin (韋嘉誠) shared this.

Mostly right from a practical perspective, although the terms are technical terms and the technical details depend on how your particular language implementation chooses to do things.

Some LISPs put all cons cells in heap, some put all enclosure environments (activation records) in heap, some use a complicated "cactus stack", which contains ARs and may or may not contain certain cons cells.

Claes Wallin (韋嘉誠) at 2016-03-27T08:42:54Z

Christopher Allan Webber likes this.

And then there's of course levels of abstraction to all this as well. What's "stack" on a language level may be stack or heap on the implementation level. And bytecode VMs and such adds levels as well.

Claes Wallin (韋嘉誠) at 2016-03-27T08:46:47Z

Christopher Allan Webber likes this.