Consider the basic pipeline of programming under Unix: source code S is compiled into a binary B, which is then loaded into a process R, which then runs for the length of its run time.
(Note: this would induce a parallel analysis via the Unix-Smalltalk connection, where method source S is compiled into a CompiledMethod M which is then invoked as an activation context C, which then runs for the length of its run time.)
(Typographic note: I was advised by feedback for my PhD dissertation to disambiguate the following:
- Runtime: adjective/noun. Short for “runtime library”, i.e. a set of software modules that support running programs.
- Run time: noun. The time during which a program (process) is running. “The runtime’s performance at run time is terrible”.
- Run-time: adjective. The hyphenated adjectival form of “run time”. “The run-time performance of the runtime is terrible”.
I tend to use this scheme nowdays.)
Many common commitments (e.g. types, variable addresses, variable values, …) can be expressed as invariances past one of these stages. Something that is committed in this way is often called “static”.
By default, the term “static” means: invariant over the life of the process, and over different instantiations of the process, and even over different binaries compiled from the same source. A “static” property is something that is allowed to vary across different programs and anything that causally contributed to their form, e.g. source code, config files etc. Without loss of generality, we can probably subsume all compiler inputs under the term “source code”. The compiler can’t stop you from changing the constant in the source code. It might complain about the new value if it’s outside the allowed range, but there is at least a wide range of different values that the compiler would accept.
However, it may be worth distinguishing different degrees of staticness:
- A “constant” is a symbol that is guaranteed to have the same value across compilations (and hence, across loading of any such binaries, and hence across the run time of those processes). We could say something with this property is “static from the source”, or “constant-static” (static like a constant).
- If something is not constant-static, then something further down the line (the compiler, or the loader, or the running process’ code) is permitted to change it. For example, the compiler allocates the address of a global variable and writes this to the binary. This address will remain the same across different processes loaded from the same binary, and across their run times. However, if the code is re-compiled, it is possible that (say, due to non-determinism), the binary may include a different address. Something with this property could be “static from the compilation” or “static from the binary”.
- If the loader decides some property which is then fixed for the run time of the process (e.g. the layout of the address space under ASLR) then such a property could be called “static from the load” or “static from the process”.
If none of these degrees of staticness apply, we call the property dynamic: whether or not the property is true can change over run time. Perhaps it has a single value, perhaps it doesn’t; we can’t assert any constraints either way.
Formalising “constant-static”
We can make the above statements more precise via first-order logic. Given some source code S, a property P is constant-static iff “For all binaries B compiled from this specific source code S, for all processes R loaded from B, for all times t in R, the property P holds.”
For example, in some C source code we might have const int MAX_PLAYERS = 255;. Take property P to be “the value of MAX_PLAYERS is 255″. When we say P is constant-static, we mean “For all binaries B compiled from source code S containing such a statement, and for all processes R loaded from B, and at all times t during R, P holds (as determined e.g. through the symbol table or addresses of reference sites).”
Technically, this condition only holds if we exclude certain contrivances, such as hex-editing the binary or process memory to change MAX_PLAYERS (whether at a single storage location, or at every immediate usage site). We’re concerned with 99% “business as usual” programming here. If we discover knowledge that applies in 99% of cases, our contribution is very relevant even though it is not always applicable.
In (more) symbols:
“MAX_PLAYERS is 255″ is constant-static ⬄ ∀ B = compile(S, cC), R = load(B, cL), t in rt(R). MAX_PLAYERS is 255 at time t in R.
In annoying, less-readable symbols:
constant-static(P) ⬄ ∀ cC ∀ B = compile(S, cC) ∀ cL ∀ R = load(B, cL), t ∈ rt(R). P(R, t)
where P(R, t) = “symbol-value(MAX_PLAYERS, R, t) = 255″
We include cC as a “compile-time context” to model possible non-determinism in compiling the same source code S multiple times: e.g. the resulting binary might have a different internal layout. We similarly include cL as a “load-time context” to reflect the fact that different processes loaded from the same binary may not be identical. cC and cL are implicitly universally quantified over.
In this example, even if we couldn’t see the specific value 255, we would know from the fact of the const that MAX_PLAYERS, as a symbol, is constant-static: what the const means is that the compiler will refuse to output any code that appears to overwrite the symbol. Thus, the symbol has the same value across the run time of all process loaded from all binaries compiled from this source code. This means we can generalise from a boolean P to the value of an arbitrary function f (e.g. f could be “the value of MAX_PLAYERS“) by setting Pf=V to be “f has the value V” for some V. So “f is constant-static” means “There exists a value V such that Pf=V is constant-static”.
In symbols:
MAX_PLAYERS is constant-static ⬄ ∃ V. ∀ B = compile(S, cc), R = load(B, cl), t in rt(R). (MAX_PLAYERS at time t in R) = V
This statement is true for any source code S which marks MAX_PLAYERS as const.
Formalising “binary-static”
Consider a global int x. Property P is “the address of x is base + 0x1000″. P is “less” static than the previous example, because the source code cannot fix it to a single value (assuming no pragma hints, etc). The address of x is decided (committed!) by the compiler, so P is static from the binary. Formally: “For all processes R loaded from the specific binary B, for all times t during R, P holds”.
We generalise to the function “address of x“. This function is binary-static. By which we mean: given a binary compiled from the source, there exists a value for that function which is constant over the run time of all processes loaded from it. Formally:
address(x) is binary-static ⬄ ∀ B = compile(S, cC), ∃ V. ∀ R = load(B, cL), t in rt(R). address(x, R, t) = V.
Formalising “process-static”
Property P is “the process base address is 0x400000”. Assume address-space layout randomisation. Then P is even less static than the previous example, because whether or not P is true depends on the base address, which is determined by the loader at load time. P is process-static. “For all times t during the specific process R instantiated by the loader, P holds.”
For the function “process base address”, we formalise:
base-address is process-static ⬄ ∀ B = compile(S, cC), R = load(B, cL) ∃ V. ∀ t in rt(R). base-address(R, t) = V.
We can note that the difference between constant-, binary- and process-static is the location of the existential quantifier in an otherwise unchanged formula. For constant-static, ∃ V across all binaries; for binary-static, ∃ V across all processes; for process-static, ∃ V across the run time of each process.
(Another example of a process-static property might be the address of a loaded DLL/shared object … at least provided that the process does not unload and load it again?)
Formalising “dynamic”
Finally, consider int x = 0. Property P is “the value of x is 0″. x is a straightforward example of “mutable state”, i.e. state that is allowed (or expected) to vary over the run time of a process. In full generality, we cannot claim that P is static at all. P is fully dynamic: its truth value may vary over the lifetime of the process. “For all times t during R, maybe P holds or maybe it doesn’t”.
This is harder to formalise. It’s a statement that we can’t assert a constraint like the one in our previous examples. If we try negating the previous constraint:
value(x) is dynamic ⬄ ¬ ( ∀ B = compile(S, cC), R = load(B, cL) ∃ V. ∀ t in rt(R). value(x, R, t) = V )
Then sadly this is wrong; it’s asserting that that x definitely does change over run time. But the whole point is that we don’t know whether it does or doesn’t: the lack of a const in front of the int is a simple lack of constraint, reducing the number of things we can assert about the program.
Perhaps this could be formalised in a modal logic for knowledge (When static, something is known, while when dynamic, it is not known)?
Our knowledge vs. the compiler’s knowledge vs. reality
Given enough additional constraints, such as a specific program or specific inputs or other conditions, we could perhaps prove that in such a context x is always 0, and thus assert P to be process-static. However, from the point of view of the compiler and its restricted reasoning capabilities, it would still regard P as fully dynamic. Such a discovery of ours might prompt us to make the variable const and thus make our extra knowledge available to the compiler. The compiler would treat this as a “promise” on our part and commit us to it by rejecting any source modifications that attempt to mutate x. Under const int x = 0, P is static in the default sense (i.e. constant-static); the mere addition of const brought it a long way from fully-dynamic. (In other words: I don’t know of any keywords like const to make a variable binary- or process-static).
Here, staticness is epistemic rather than ontic: it’s about what we (or an automated reasoning agent, like a type checker) know about when a behavioural property is true. Suppose we had a very complicated program involving int x = 0 and we are simply at a loss to prove anything from its source code. We run the program and it seems to run for a very long time, never changing x from 0… but we still cannot be mathematically certain that it will stay this way (halting problem, Rice’s theorem, etc). So we cannot safely say that P is static at all: P is epistemically dynamic for us. Suppose that, in actuality, P really is true for all time, i.e. x remains 0 forever. Then P is ontically static, in itself, even though we have not proved it yet.
In the easy case where a simple visual inspection of the program allows us to conclude P is static, our knowledge matches reality but the compiler’s knowledge does not. P is ontically static, and epistemically static to us, but epistemically dynamic to the compiler. When we add the word const, we align the compiler’s state of knowledge with ourselves and reality.
We technically did more than this – we concluded P was process-static at minimum – and then made it even more static (constant-static) by adding a hint in the source code. Contrived example: deep in the weeds of some function, x gets its value updated from the loader; in the process we analysed, the loader just happened to give the value 0; this was the same as x‘s initial value so the assignment had no effect. But in a different run of the same binary, the loader gives 2452545 so this limits the possible staticness. This time, we cannot mark the variable const and delete spurious assignment statements, because actually the assignments are necessary for the behaviour of the program. So we can’t add const without changing the behaviour of the program; it would be an overreach for our discovery. We’d be telling the compiler something that isn’t actually true. Similarly if e.g. we proved x = 0 forever as long as some file didn’t exist: an example of a conditionally static property.
As part of enforcing our promise that P is static, the compiler complains about some assignment statements to x, forcing us to remove them. They were nested inside some if statements with very complicated conditions. On our own, we worked out that these conditions never trigger, so the assignments never happen. Thus, removing them doesn’t change the behaviour of the program, but it does bring the source code – i.e. the initial state – closer to describing the actual behaviour (in a form that’s easier for humans to understand).
Furthermore, we (or the compiler) can make further code transformations as a result of this promise/commitment. For example, any if statements of the form if (x == 0) can be deleted leaving their bodies, and any of the form if (x != 0) can be deleted along with their bodies. This can be seen as propagating the new knowledge throughout the code, and is related to “partial evaluation and program slicing” (cite)
When fully qualified, staticness is relative to a given scope. A constant-static property can be changed by changing the source code, a binary-static property can be changed by re-compiling, etc. We could even have conditionally static within the run time of a process, e.g. static given that a certain file exists. Staticness is a measure of how invariant a property can be expected to be with respect to common programming activities (feedback loops?).
Premature commitment vs. late-binding
Constant-staticness is special because it represents a commitment that you, the programmer, must decide to make while writing the program. This commitment easily runs the risk of being premature. After all, the point of programming is to offload certain types of work or decision-making to the computer. When some property of the program can simply be read off its source code, this necessarily represents a decision that you (or whatever generated the source code) had to make.
Put it this way: the program can use all sorts of varying run-time conditions to make its decision. Meanwhile, you, as a programmer, have only two choices:
- Write code (i.e. cleverly set up the initial state of the process) such that the program will make this decision at run time (i.e. dynamically, and all relevant properties are dynamic)
- Make the decision yourself (or with the help of some other computer program, etc) while writing the program, and embed your decision in the source code (i.e. statically, and relevant properties are static)
There is technically a third possibility, which we barely ever see: you pause the running process in a debugger, inspect various values, make the decision yourself and then alter the control flow of the program to go in the right direction. This is so impractical that even though it exists, the other two options are the only ones in practice.
It follows as a basic logical consequence that, if you ponder the decision while writing the code and conclude “I can’t possibly know, it would depend on run-time values such as user input”, then you must take option 1 and make the behaviour dynamic. In other words, option 2 embeds the assumption “This decision shall be static”, i.e. “this decision shall remain constant over the entire lifetime of the process.”
Making a property static is equivalent to taking it “out of the process” – it’s a strict input to the program, it can’t be affected by anything the program does, and it can’t be determined by the program as an output.
When something is late-bound, it can be taken as user input during the running process, or decided by the running process based on run-time conditions.
Unix Is Late-Bound
Given any “static” commitment of a program, provided I have its source code, I can use a text editor to change the source code, and a compiler to re-create the binary. Done! Unix as a whole, like Smalltalk, has few commitments; individual programs, languages and programming systems within Unix are frequently heavily committed.
I understand that the kernel cannot be changed while Unix is “running”. But I think we should view Unix primarily as an evolving tree of files on persistent storage; in this sense, it’s never “off”, only frozen until re-heated. One can use text editors and compilers to create a hacked kernel in the filesystem. One can then reboot into the new kernel. I am not sure this Unix is committed to anything other than its hardware. In this respect, if we zoom out, it is pure software, as malleable as it ought to be. It’s just that this malleability is not evenly distributed within it.
We could say that the “hot” or “power-on” state of Unix is committed to the kernel it booted with. This is the state of the evolving sub-system consisting of RAM and processor registers. (The computer’s “on” state is one giant method activation.) Even so, the “hot” state does not seem committed to anything else. It’s designed to have a live, two-way view of the filesystem. The filesystem is evolved using itself (but only in the hot state).
Commitments to Where Data Lives (formalised)
Let’s make my informal thoughts more precise…
Edit-Time Memory Allocation
Edit-time: writing machine code in a hex editor, every concrete address I write commits my future self to a set of byte layout assumptions. As soon as I wish to go back and insert or remove an instruction, I violate the underlying assumptions and must rewrite the addresses to satisfy the newly operative constraints.
For simplicity, instead of machine code instructions, we’ll analyse a BASIC-like language where line numbers must be consecutive. Let’s write the loop-based Factorial function. I’ll adapt from Rosetta Code:
0 INPUT "N="; N: GOSUB 3
1 PRINT N; "! ="; F
2 GOTO 0
3 F = 1
4 I = 1
5 IF I == N THEN GOTO 8
6 F = F * I
7 GOTO 5
8 RETURN
Intuitively, what happens when we wish to make a small change to the program – say, have it print “Finished!” between lines 1 and 2?
0 INPUT "N="; N: GOSUB 3 <<<
1 PRINT N; "! ="; F
2 PRINT "Finished!"
3 GOTO 0
4 F = 1
5 I = 1
6 IF I == N THEN GOTO 8 <<<
7 F = F * I
8 GOTO 5 <<<
9 RETURN
Well, all later lines are shifted and their line numbers (addresses) increment. But every single reference to any one of these lines is now wrong; the line’s name changed, but the name in the reference didn’t. I’ve highlighted these with <<<. We have to tediously go through and fix them up.
OK, but at a deeper level, why did this happen? The very first line contains a reference to another part of the program. In my head, that part of the program is called loop_init, and in this program it happened to fall on line 3. It would still be loop_init no matter which line it was on. Yet the language (in this toy example) forces me to commit to a specific line number. The original program embeds the assumption “loop_init is on line 3″, as well as “loop_condition is on line 5″ and “loop_end is on line 8″. When we insert a line before line 3, all three of these assumptions become false, and our program is broken. In order to fix it, we must locate all parts of the program that directly or indirectly depend on these assumptions, and update them appropriately. The result is a new set of assumptions “loop_init is on line 4″, and so on, which reflect the new program. In turn, they represent new commitments and will break very easily in the same way.
I call this “edit-time memory allocation”. It is an example of a commitment/violation/repair cycle that occurs entirely within the source code, though admittedly this is through a mental prediction that the program will run incorrectly (so for a very Dim BASIC programmer, it could end up being a cycle similar to the ordinary write/compile/execute/debug cycle).
Notice that the properties P1 “the first statement refers to loop_init” and P2 “the first statement refers to statement no. 3” are both constant-static: they are true over the whole run time of all processes loaded from all binaries compiled from the source. Intuitively, P2 represents a premature commitment on our part: the number 3 is not particularly meaningful to us, it’s just a deterministic(!!) consequence of where our loop_init code ended up relative to the other code. And yet we are telling the compiler: “you shall goto line 3, and no other! That is my intent!”.
In truth, our real intent is only to goto line 3 because of some logical relationship to the rest of the program. This relationship is so logical and deterministic that … the number 3 could easily have been calculated by a computer program.
Thus we improve the programming system (whether by modifying the compiler, adding a preprocessor, or something else) to support string names:
INPUT "N="; N: GOSUB loop_init
PRINT N; "! ="; F
GOTO 0
:loop_init:
F = 1
I = 1
:loop_condition:
IF I == N THEN GOTO loop_end
F = F * I
GOTO 5 loop_condition
:loop_end:
RETURN
What happened to the properties P1 and P2? P1 – “the first statement refers to loop_init” – is still constant-static: it can be read off the source code. But P2 – “the first statement refers to statement no. 3” – is now less static; it can’t be read off the source code. Which precise statement number the first statement refers to, is now a decision that we have deferred to the programming system. Generalising P2 to a function F2 – “the number of the statement referenced by the first statement” – the value of F2 is determined by the programming system, and hence so is the truth value of any predicate (such as P2) that relies on F2. We could say that P2 and F2 are static from the preprocessor, or static from the compiler, but no longer static from the source code (a.k.a. constant-static). We have made P2 relatively more dynamic or “late-bound”.
A string name is a level of indirection (LOI). By replacing the number 3 with the name loop_init, we’ve still committed to P1, but we no longer prematurely commit to P2. The assumptions “loop_init is on line 3″ etc. are no longer relevant to our edits: whether they are true or false, they don’t constrain our actions. In other words, no property of our source code depends on those assumptions. We have relaxed those commitments.
In general, a LOI preserves a desired commitment (P1) while relaxing a premature commitment (P2). This yields a little insight into why “all problems in computer science are solved by adding another level of indirection”.
Because the dependent variables of our new commitments – such as loop_init in P1 – are meaningful to us, they are a lot harder to break; breaking them feels less like an annoying limitation of the programming system, and more like a change in requirements of what the program should do.
Design-Time Memory Allocation
The mechanics of Edit-Time Memory Allocation only really apply in hex editing (for both code, and data) and explicitly line-numbered languages like BASIC (just for code). If you’re not hex editing, then instead of directly tying the location of your data to the character offsets in your source code, you’re just declaring a name as a symbolic synonym for some address.
Suppose you’re writing a bootloader or the firmware for a washing machine: you probably just have free rein over a few KB or MB of memory and don’t have malloc (or can’t afford its overhead). Moreover, for some reason the compiler technology isn’t yet very good for this platform, or the hardware platform expects specific addresses to be used for specific purposes (e.g. memory-mapped IO). So you allocate 256 bytes for each variable string, a few KB for the monochrome pixels of the tiny display, and place each data item at a fixed memory address hardcoded in the source code (or assembler, or machine code). Perhaps you use symbolic constants, but they’re all #defined to numeric literals at the top.
#define BUF_SIZE 0x100
#define DISPLAY_WIDTH 300
#define DISPLAY_HEIGHT 100
char *current_display_charbuf[BUF_SIZE] = 0x1000;
char *personalized_username[BUF_SIZE] = 0x1100;
char *framebuf = 0x2000;
const size_t bytes_per_row = (DISPLAY_WIDTH + 7) / 8;
char *framebuf_end = framebuf + bytes_per_row * DISPLAY_HEIGHT;
Pretty much every value here is constant-static. In some cases, the compiler doesn’t know this; for example, it cannot enforce the fact that current_display_charbuf has the constant-static value 0x1000 (i.e. it will always point there) against future source code edits, because it is not marked const. (In this case, it would need to be char *const – the pointer value is const, but the char buffer is mutable – not const char *, a mutable pointer to a const char). The only semi-interesting values that aren’t constant-static are the addresses of the pointers themselves (i.e. where is the value 0x1000 stored?), which can’t be deduced from the source code. These are “static from the binary”, an example of compile-time allocation to be discussed in the next section. In order to do truly hardcore design-time memory allocation, we’d have to use some compiler pragma or address literals to force the variables to live at specific addresses:
#define p_current_display_charbuf ((char **) 0x800)
*p_current_display_charbuf = 0x1000;
#define p_personalized_username ((char **) 0x810)
*p_personalized_username = 0x1100;
// etc... (I Am Not A C Programmer, may be invalid)
This can be seen as defining what would’ve been the compiler’s symbol table in the source code, via #define‘s. However, we’ll stick with the previous code listing.
To summarise: we have a bunch of properties like “current_display_charbuf has value 0x1000″ which are constant-static, and those like “current_display_charbuf has address X” which are binary-static.
These commitments come from the following assumptions:
- A1: Every data item will remain the same size over the lifetime of the process
- A2: Every data item will remain in the same place over the lifetime of the process
- A3: I, the programmer, know best what these values should be.
Notice that A1 and A2 only mandate staticness from the loading. However, because of A3, the size and location of each data item becomes a constant in the source code, making these properties more static than strictly required by A1 and A2 (not merely static from the loading, nor static from the compilation, but static from the source code).
Result: data items are committed to live at the same addresses and occupy a fixed amount of space, even across different compilations.
Compile-Time Memory Allocation
Suppose we refine assumption A3 to give up our power over the pointer values. That is: I believe a computer program (the compiler) can make a better decision than me, on where to situate the data items in the program. (Perhaps we could simplify this to: “I believe that a computer program should decide where to situate the data items”.) However, I still wish to decide the sizes, and I still have no reason to allow these values to change during run time.
- A4: Every data item will remain the same size over the lifetime of the process
- A5: Every data item will remain in the same place over the lifetime of the process
- A6: I, the programmer, know best what the sizes should be.
char *current_display_charbuf[BUF_SIZE];
char *personalized_username[BUF_SIZE];
const size_t bytes_per_row = (DISPLAY_WIDTH + 7) / 8;
char framebuf[ bytes_per_row * DISPLAY_HEIGHT ];
There are no more explicit addresses. In the “hardcore design-time allocation” example, the symbol table existed as #define‘s in the source code. With compile-time allocation, the symbol table exists as a data structure during the run time of the compiler process (a.k.a. the “compile time” of the program).
The address of each data item is decided by the compiler – hence, how could it possibly appear in the source code? – so the addresses are static from the binary. Any logical properties that depend on them are constrained to be no more static than this (the addresses induce an upper bound on the staticness of dependent properties).
Result: data items continue to occupy a fixed amount of space, even across different compilations. Data items live at the same address across the lifetimes of all processes instantiated from a binary, but this address may vary between compilations.
Load-Time Memory Allocation
I can’t think of many properties that are specifically process-static. The main one is Address Space Layout Randomisation (ASLR). In the old days, the process Base Address was binary-static, decided by the compiler. These days, it’s randomly decided by the loader.
Another example is shared library loading: even before ASLR, shared libraries were loaded wherever they fit, and the loader applies relocations throughout the code to propagate the new base address.
Dynamic Memory Allocation
Consider a global char str[256];. which we can mentally rewrite as char *str. This embeds the following assumptions:
- A7:
strwill remain at the same address across run time. - A8:
strwill contain the same value across run time (the address of the array). (This is because arrays are not assignable lvalues in C!) - A9:
strwill remain the same size (element count) across run time. - A10: I, the programmer, know best what that size should be.
Now suppose that requirements change and A10 is revoked: the size of str now depends on run-time input. This has the knock-on effect that A9 is no longer assertible. If str is local to some function scope, we can use a variable-length array allocated on the stack: char str[dynamic_val];. Note, however, that str is no longer global; its address is now dynamic, and A7 is violated. The array elements to which it points are (I think) allocated right after it on the stack, so A8 is also violated.
If we wish to keep str global, we can use malloc and get an address on the heap. Note that A7 is preserved; str as a pointer still has a binary-static address, by virtue of being a global variable. However, A8 is no longer assertible; perhaps later code points str at somewhere else.
However, there’s probably something static that we can assert about the lifetime of str. As a human programmer I have made decisions about when str gets freed, depending on which function we’re in and on run-time values (control flow within the function). Somehow, this is dynamified into garbage collection (todo: also analyse reference counting as intermediate stage).
Result (assuming global): both the value and size of the str array are unknowable before running the process.
Programming, Made Complicated 