# 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.

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,

we'll call the `fib` function with argument `3`

`fib` isn't defined yet which gives an error. We'll create `fib` and retry the call.

`fib` will take one argument, which we'll name `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)`.

Since this calls `fib` recursively, let us follow the execution. First, we manually let a few instructions execute

until we need to intervene. In this recursive call `i = 1` so we do need the base case now.

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.

Now that we've evaluated `fib(3 - 2)`, we can evaluate `fib(3 - 1)`.

and let it run for a bit.

Now add the result and return it.

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.

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:  <assign:> <str i> <prim pushi:> <int 2> <prim -> <mem 100 fib>
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:  <newfunc1> <assign:> <str i> <prim pushi:> <int 3> <prim <> <mem 200 anonymous> <prim if>
address: 100        101       102     103           104     105      106                 107
memory:  <prim pushi:> <int 2> <prim -> <mem 100 fib>
memory:  [...] <prim breakpoint> <prim breakpoint> <prim breakpoint>
``````

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:  <newfunc1> <assign:> <str i> <prim pushi:> <prim 3> <prim <> <mem 200 anonymous> <prim if>
address: 100        101       102     103           104      105      106                 107
memory:  <prim pushi:> <int 2>  <prim -> <mem 100 fib>
memory:  [...] <prim pushi:> <int 1> <prim return>
``````

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:  <newfunc1> <assign:> <str i> <prim pushi:> <prim 3> <prim <> <mem 200 anonymous> <prim if>
address: 100        101       102     103           104      105      106                 107
memory:  <prim pushi:> <int 2>  <prim -> <mem 100 fib>
memory:  <prim pushi:> <int 1>  <prim -> <mem 100 fib> <prim +> <prim return>
address: 112           113      114      115           116      117
memory:  [...] <prim pushi:> <int 1> <prim return>
``````

### 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