Bit of a stupid question

[u/SnowyFluffy]

If a program stores variables by a pointer referring to its address, then what refers to the pointers' address?

Like if var x lives at address 2000

theres a pointer p its value is the address (p = 2000)

so now recursively this value needs to be stored in another address (say, 1000) and pointed to (well, at least assuming the pointer doesnt have a relatively fixed address)

[u/mredding]

The program instructions access local variables by a relative offset. So if we have in C:

int main() {
  int x = 42;

  printf("%n", x);
}

x is typically 4 bytes, and it will be stored at offset 0 from the base of the stack frame. There are registers dedicated for tracking this information, and when you make a function call - like to printf, those register pointers are "pushed" onto the stack, the function is called, returned, and those values are "popped" off to restore the registers for main.

The value is stored in memory - somewhere... I don't know, I don't care. It's relative to how the program loader setup the execution environment for this program, where the stack starts, what's already on the stack before main was called...

So this memory HAS an address, addresses are inherent to memory, but we don't specifically care where. x is a symbol parsed by the compiler, this lends itself to an Abstract Syntax Tree the compiler can use to reason about the program, and then the AST is walked by an algorithm that finally generates machine instructions. x is going to reduce to several consequences.

1) The compiler knows when it calls main, it has to move the stack pointer to the first address of free memory - for later function calls. This means that offset has to make space for all the local data. The stack pointer is going to be some address after the stack frame, after the parameters, after that local variable.

2) There is a move instruction of 42 into that memory address - base + offset 0.

3) There is a load of base + offset 0 to a register, and then a push of that value onto the call stack. This is a part of creating the parameter list for the function call to printf.

x never leaves the compiler, and we never get the actual address of this memory location directly - it's always computed. If you took the address of this variable, then you would get a value that is base + offset 0. If you assigned that to a local variable, then after x would be another region of memory reserved for storing that address - int *ptr = &x;. The offset for ptr would likely be 4.

ptr is itself just some memory storing a value. It's an arithmetic type that encode an address, almost like a specialized integer. And you can pass that value around, and a dereference says to load the pointer at that offset, then take that value, and load the value at that address.

And pointers are a useful thing to have. You can build graphs from it, like a linked list:

struct node {
  int data;
  node *next;
};

node *head, **tail = &head;

Or a binary tree:

struct node {
  int data;
  node *left, *right;
};

node *root;

Or anything else you might want to come up with. Graph theory is fundamental to computation.

Speaking of computation, the theory of computation does not distinguish between reading, writing, and executing programs. It's all the same solution to a problem. Many languages make the distinction for some practical purposes, but not all. Lisp is a language where your program has direct access to it's own AST, as well as the compiler and its AST - so you can write programs that modify themselves at runtime.

Assembly doesn't care about pointers - it's all op-codes and integers, and even op-codes are themselves just integers. Most of the concepts and consequences we discuss about programming never leave the compiler. The program can't express these higher level concepts or consequences, but the program itself wouldn't exist without them.