https://blog.asrpo.com/jit_programming Instruction level just-in-time programming Just-in-time programming is a workflow for creating a program top-down, while a program is running. This is typical in Smalltalk environments like Squeak. In this post, I want to describe an instruction level variant of this. Fibonacci I think the best way to describe instruction level just-in-time programming (IL-JIT programming) is by showing how it works. I'll start with the classic Fibonacci example (Rosetta code has many implementations). We'll implement Fibonacci while evaluating fib(3). Language model The example that follow are in a concatenative language that is a simplified version of FlpcForth. The main things to know are that it has * a global function argument/parameters stack, * memory where instructions are written. And all functions are formally nullary, but have an implicit arity defined by how many elements they remove from the top of the global parameters stack. Their return value are pushed to the top of this stack. Fibonacci implementation Here's the whole video of the implementation that we'll go through step-by-step. Click on it to play. Full video of the Fibonacci implementation. Memory is displayed left to right, wrapping around to the next row. Each memory cell holds either a function, string or label (that executes as a no-op). The input stack is drawn above the program counter. Only the top of the call stack is shown. Each time we write an instruction, the program counter takes a step. We can also advance the program counter without writing any instruction. Step by step Starting with the empty program, Empty program we'll call the fib function with argument 3 Call fib fib isn't defined yet which gives an error. We'll create fib and retry the call. Create fib fib will take one argument, which we'll name i. Name argument i Normally, we may want to check for some base case. However, since we have the argument 3 in hand, let's only write the i > 2 case for now. We should return fib(i - 2) + fib(i - 1). Compute the first part fib (i - 2). fib(i - 2) Since this calls fib recursively, let us follow the execution. First, we manually let a few instructions execute recursive call to fib(i - 2) until we need to intervene. In this recursive call i = 1 so we do need the base case now. check base case Like for fib, 'base' refers to a function that doesn't exist yet. As before, create the function and call it again. When i < 3, we'll just return 1 so that is what base will do. create base case function and return 1 Now that we've evaluated fib(3 - 2), we can evaluate fib(3 - 1). fib(3 - 1) and let it run for a bit. evaluate fib(3 - 1) Now add the result and return it. add and return We got 2, which is the right result. Difference from regular JIT programming Typical JIT programming restarts frames on error. That is, it unwinds a number of frames (decided by the user). For example, if we called f1 which called f2 which called f3 which called f4, the stack will look like f4(x) f3(x) f2(x) f1(x) Then we rewind it to, say, just f1(x) and we call f2(x) again [side-effects]. With instruction level JIT programming, no stack in unwound and in fact, most of the time, nothing is undone. The instruction counter is merely paused until it is asked to step again. Even for missing function, we could pause, wait for the function to be created and attempt to call it again. Though I think IL JIT programming would benefit from being supplemented with frame restarts, for when larger chunks of code needs to be corrected. Advantages Some advantages of either kind of JIT programming * You have access to the full state of current program, like variables. This frees your mind as you don't need to think as abstractly and avoids errors like off-by-one errors. * You can write the parts of the program for simple cases first and fill in more complex cases later. This lets you test your overall design before committing more effort to it. * You can program top down instead of bottom up or all in one shot. JIT programming for Flpc I think I could get something like this to work for Flpc, even writing in the high level FlpcPython language. Here's how it would work. 1. When the bytecode-to-memory compiler/transcriber encounters an unknown function name when writing the body of some caller, instead of writing (to memory) a pointer to that function (which doesn't exist), it writes the string for the function name as a string and a "not-yet-implemented" primitive to memory. 2. When the body is executed and the "not-yet-implemented" primitive is encountered, that primitive 1. checks if a function with that name is now defined and if not add a fixed size empty function to memory and defines it as such 2. overwrites the body with a pointer to the function with that name. 3. Empty function bodies just contain all breakpoint instructions. 4. When a block is created (for example a if ... : or repeat: block), an anonymous fixed size empty function is added to memory and a pointer to it written as part of the body of the caller. 5. If someone inserts and instruction into memory, shift every future instruction in that function body to the right in memory. Since function bodies are fixed size and inserting to memory needs human interaction, this should be fast enough. Example Here's what the code and memory may look like, following the same Fibonacci example as before. At first the code looks like fib <- fun[i]: fib(i - 2) and memory looks like names dict: fib -> 100 memory: address: 100 101 102 103 104 105 We run the program for a bit and after fib is called a second time we insert base case checking fib <- fun[i]: if i < 3: fib(i - 2) names dict: fib -> 100 memory: address: 100 101 102 103 104 105 106 107 memory: address: 108 109 110 111 memory: [...] address: [...] 200 201 202 and once the program counter reaches the inside of the if block, we add fib <- fun[i]: if i < 3: return(1) fib(i - 2) names dict: fib -> 100 memory: address: 100 101 102 103 104 105 106 107 memory: address: 108 109 110 111 memory: [...] address: [...] 200 201 202 After we return from the recursive call, we can add the rest of the function body. fib <- fun[i]: if i < 3: return(1) fib(i - 2) + fib(i - 1) return() names dict: fib -> 100 memory: address: 100 101 102 103 104 105 106 107 memory: address: 108 109 110 111 memory: address: 112 113 114 115 116 117 memory: [...] address: [...] 200 201 202 Implementation This design seems to work but I don't know if I will add it to Flpc yet. Naming I didn't find any canonical name for the workflow used in Squeak Smalltalk so I called it JIT programming here. There's a C2 wiki page that named it this as well. Some other possible names: top-down programming, incremental programming. Footnote [side-effects] If some functions already performed side-effects like reading from a file or a network request then these are not undone and the program may end up in an inconsistent state. In this case, more needs to be restarted, up to the entire program. However, we can usually locally (i.e., on a per functionality basis) separate side-effects from pure or "pure enough" functions. And then only restart on the pure portions (or a larger groups that reperform all side-effects). This separation is something you might want in your code anyways Posted on May 6, 2021 Blog index RSS feed Contact