A Threaded Language

A Thread

The core concept of a threaded language is, as may be assumed from the name, threads. These threads are not a synonym for processes but rather a metaphor for a list of subroutine addresses. The list of addresses can be traversed to create a low overhead interpreter. Each address can point to either a subroutine written in the implementing language (commonly assembly) or to another thread, allowing for the creation of complex routines.

Inner Interpreter

The inner interpreter is named as such from a convention where the REPL is often called the outer interpreter. The job of the inner interpreter is to traverse the thread and call each subroutine. This is a very short routine that fetches the next address and increments an internal instruction pointer. In ARM64 this would look like:

RUN:
    ldr A, [IP], #8
    br A

This routine needs to be inlined or called at the end of every subroutine used within a thread.

Words

There are multiple models for how to structure the threads and therefore for how to accomplish the calls. The variant I will focus on is Indirect Threading.

So far the threads have been presumed to hold addresses pointing immediately to machine code. This structure is somewhat limiting and makes it difficult to allow for the nesting of threads. A conceptually simple way of adding this is to bookend the threads with some entry- and exit routines. The addresses that the threads hold are also changed by adding a level of indirection. This new structure I want to call a word to differentiate it from the more fundamental thread.

The entry routine moves the instruction pointer to point to the first address in the thread, storing the old instruction pointer in the process. The exit routine simply restores the previous instruction pointer. To store the intermediate instruction pointers a stack is often used. These routines along with the modified inner interpreter look like this:

NEXT:
    ldr WA, [IP], #8
RUN:
    ldr A, [WA], #8
    br A
    
ENTER:
    str I, [RSP, #-8]!
    mov I, WA
    b NEXT
    
EXIT:
    ldr I, [RSP], #8
    b NEXT

Dictionary