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

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,

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

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>
address: 108           109     110      111
memory:  [...] <prim breakpoint> <prim breakpoint> <prim breakpoint>
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:  <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>
address: 108           109      110      111
memory:  [...] <prim pushi:> <int 1> <prim return>
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:  <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>
address: 108           109      110      111
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>
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