Memory Allocation and Garbage Collection

Memory Allocation

In the real world, data is stored on a finite tape cells that each contain a single bit, not an infinite cube of cells which contain varying numbers of bits. This means that, in order to write an compiler, we have to map an infinitely large 3D data structure onto a finitely sized, one dimensional data structure: RAM. However, due to this being an esolang being developed for fun, not for extreme efficiency, we don't have to solve that mapping problem on our own. Instead, we can write an interpreter in any language that supports nested lists and objects.

The first problem to solve is relatively straight forward. In BrainCube, the cells on each sheet increase in maximum size each time you go to the next sheet, so cells contain 1 bit on sheet 0, 2 bits on sheet 1, 3 bits on sheet 2, 4 bits on sheet 3, and so on.
Therefore, the problem is How do you store a arbitrary, varying number of bits in a single data type?
The best solution (using C++) that I've come up with is using a custom class that stores a number's bits in a std::vector<bool> object, and has custom ++ and -- operators that appropriately twiddle the bits.

Great, that's one problem down! Now we can just go into C++ and write Datum MemoryCube[∞][∞][∞]! Except when you do that, the compiler has no idea what an array of ∞ elements even means, let alone how to pre-allocate the infinite amount of RAM it would take. That's the next problem: How do you store a theoretically infinite amount of data?
Answer: You don't! You only store the data you actually need, and dynamically allocate memory when you need to store more data. To achieve this, you could use a list of lists of lists of Datum objects, and only increase the size of each list when you need to change a non-allocated cell from 0 to a non-zero number.

To do: write pseudocode for memory allocation

To better illustrate the way this would work, imagine a sheet S that has cells with values of 1 at the following locations:

[S][0][3]
[S][2][6]
[S][5][2]

Expanding only the lists needed to store these numbers, the sheet's allocated memory can be visualized like this, with [S][0][0] in the lower left corner, T increasing as you move up, and C increasing as you move left:

0 0 1  
0  
0  
0 0 0 0 0 0 1  
0  
0 0 0 1  

As you can see, memory for a structure (a sheet, tape, or cell) is only allocated when it directly precedes a structure of the same dimension (Cell is 0D, tape is 1D, sheet is 2D) that holds non-zero data.

Garbage collection

What happens when you set a set a cell to zero if that cell has been requiring the interpreter to allocate a large number of 0 valued cells? Without garbage collection, all these now unnecessary cells would still clog up system RAM.
Fortunately, garbage collection in BrainCube is a rather simple algorithm.

For each tape
	While the tape's right-most exists and has a value of 0
		Delete the right-most cell of the tape
For each sheet
	While the sheet's upper-most tape exists has a length of 0
		Delete the upper-most tape
While the furthest-away sheet has no tapes
	Delete the furthest-away sheet 

Despite the simplicity of the algorithm, it would be a waste of CPU cycles for the interpreter to perform garbage collection every time there might be garbage to collect. Therefore, garbage collection will only ever occur if the program being executed tells the interpreter to perform garbage collection via the ? command.