An elevator description for Forth's threaded code models?

[SirWumpus]

Had an online job interview yesterday and the interviewer clearly studied my recent GitHub activity asked a question about Post4's description:

Post4 is an indirect threaded Forth dialect written in C. 

And asked What is indirect threading?. While I've studied and implemented "indirect threading" compared to "direct threading" or others, I was caught off guard and my face / mind fell blank as how to quickly describe this implementation choice in simple terms. The audience was technically savvy, but their understanding of threads fell along the lines of POSIX, Java, CPU threads.

Without diagrams in the space of an elevator ride, how does one explain this technique succinctly to non-Forth people? Or any of the other popular designs. Is it even possible without becoming a mini lecture?

[frenchie68]

You had a job interview for a Forth position? Consider yourself blessed by the gods! I think it is always tricky to claim to adhere to a specific Forth implementation model. I also like to stay clear from buzzwords like '*domain-specific language*(*DSL*)'. It is trendy and might place you in the upper conceptual spheres but it remains a risky proposition. All the best.         Francois Laagel

…

On 12/6/24 14:51, Anthony Howe wrote: Had an online job interview yesterday and the interviewer clearly studied my recent GitHub activity asked a question about Post4's description: |Post4 is an indirect threaded Forth dialect written in C. | And asked |What is indirect threading?|. While I've studied and implemented "indirect threading" compared to "direct threading", I was caught off guard and my face / mind fell blank as how to quickly describe this implementation choice in simple terms. The audience was technically savvy, but their understanding of threads fell along the lines of POSIX, Java, CPU threads. Without diagrams in the space of an elevator ride, how does one explain this technique succinctly? Or any of the other popular designs. Is it even possible without becoming a mini lecture? — Reply to this email directly, view it on GitHub <#187>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AIH3QJKNKJ5APMLFYL5BWWT2EGTXBAVCNFSM6AAAAABTEWS3ZCVHI2DSMVQWIX3LMV43ERDJONRXK43TNFXW4OZXGYZDGNBWGA>. You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[SirWumpus]

You had a job interview for a Forth position? Consider yourself blessed by the gods! I think it is always

No. Not for a Forth related position. But it was interpreter, compiler, VM related.

tricky to claim to adhere to a specific Forth implementation model. I also like to stay clear from buzzwords like 'domain-specific language(DSL)'. It is trendy and might place you in the upper conceptual spheres but it remains a risky proposition. All the best. Francois Laagel

I've heard it said If you need a Domain Specific Language - just say no.

[SirWumpus]

Shady character (trench coat, hat, dimly lit street corner): Pssst, do you want a DSL?

[ruv]

I've heard it said If you need a Domain Specific Language - just say no.

Some examples of DSL: HTML, JSON, Makefile, SQL, PostScript. Why not use them?

[SirWumpus]

Well I meant don't invent yet another DSL as there are plenty about.

[frenchie68]

I love it! A valuable reference about threaded implementation models "might" be "Threaded Interpretive Languages" by R. G. Loelinger. It was published in 1981, originally by BYTE. My copy comes from Mc Graw Hill (still hard to find) and I have to admit I haven't read it. I implemented my own 79-STANDARD native beast in 1984 for he Z80 and ported it to the Hitachi 6309 about six years ago. It works well. I made it ANS94 compliant. I do peddle a hardware kit and I do have a few satisfied customers. For some odd reasons, none of them reside in the US. I suspect an antiquated banking system is the reason why this is. All the best.         Francois

…

On 12/6/24 15:12, Anthony Howe wrote: Shady character (trench coat, hat, dimly lit street corner): Pssst, do you want a DSL? — Reply to this email directly, view it on GitHub <#187 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AIH3QJOMP5COPD2ZDO2J3AD2EGWE5AVCNFSM6AAAAABTEWS3ZCVHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTCNBYGU2TEMI>. You are receiving this because you commented.Message ID: ***@***.***>

[SirWumpus]

I love it! A valuable reference about threaded implementation models "might" be "Threaded Interpretive Languages" by R. G. Loelinger. It was published in 1981, originally by BYTE. My copy comes from Mc Graw Hill

https://archive.org/details/R.G.LoeligerThreadedInterpretiveLanguagesTheirDesignAndImplementationByteBooks1981

[alextangent]

Thank you. A delightful book on a par with Brad Rodriguez’ Moving Forth, which was the first document that clearly explained to me what a TIL was. https://www.bradrodriguez.com/papers/moving1.htm . A clear exposition of ITC, DTC, STC and TTC on one page. From: Anthony Howe ***@***.***> Sent: Friday, December 6, 2024 3:14 PM To: ForthHub/discussion ***@***.***> Cc: Subscribed ***@***.***> Subject: Re: [ForthHub/discussion] An elevator description for Forth's threaded code models? (Discussion #187) I love it! A valuable reference about threaded implementation models "might" be "Threaded Interpretive Languages" by R. G. Loelinger. It was published in 1981, originally by BYTE. My copy comes from Mc Graw Hill https://archive.org/details/R.G.LoeligerThreadedInterpretiveLanguagesTheirDesignAndImplementationByteBooks1981 — Reply to this email directly, view it on GitHub <#187 (reply in thread)> , or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAOB6OVEM4XBCG2R3WA2TYL2EG5NJAVCNFSM6AAAAABTEWS3ZCVHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTCNBYGYYTSOI> . You are receiving this because you are subscribed to this thread. <https://github.com/notifications/beacon/AAOB6OUTYNYDZOSCJ5RESC32EG5NJA5CNFSM6AAAAABTEWS3ZCWGG33NNVSW45C7OR4XAZNRIRUXGY3VONZWS33OINXW23LFNZ2KUY3PNVWWK3TUL5UWJTQAV5B7O.gif> Message ID: ***@***.*** ***@***.***> >

[SirWumpus]

Thank you. A delightful book on a par with Brad Rodriguez’ Moving Forth, which was the first document that clearly explained to me what a TIL was. https://www.bradrodriguez.com/papers/moving1.htm . A clear exposition of ITC, DTC, STC and TTC on one page.

I've read Brad Rodriguez’ Moving Forth series. It was excellent. But its longer than an elevator pitch, more mini lecture. Still great work and I'd recommend for any class covering the topic.

[ruv]

What is indirect threading?

Without diagrams in the space of an elevator ride, how does one explain this technique succinctly to non-Forth people? Or any of the other popular designs. Is it even possible without becoming a mini lecture?

I think it's impossible to explain the difference between different kinds of threaded code in the space of an elevator ride.

In short. Indirect threading is a kind of threaded code. Threaded code is an approach to representing/encoding subroutines in a virtual machine. Different kinds of threaded code are like different types of stitches in sewing.

[MitchBradley]

First level explanation, for a short elevator ride:

Threaded code is a compact binary representation of a computer program as a list of pointers. In direct threaded code, the pointers point directly to machine code. In indirect threaded code, they point to object structures, the first field of which is a pointer to machine code.

Secondary explanation, for taller buildings:

Direct threading can be a bit faster, while indirect threading has size and implementation advantages for objects that contain data.

Tertiary explanation, for the walk through the lobby:

Indirect threading also has advantages for architectures with strict segregation of code and data.

Any competent programmer should be able to understand that instantly. Non-programmers have no chance.

[SirWumpus]

And if you come from the parking garage? 😁

[SirWumpus]

That's pretty nice and concise explanation.

[ruv]

@MitchBradley writes:

Threaded code is a compact binary representation of a computer program as a list of pointers. In direct threaded code, the pointers point directly to machine code. In indirect threaded code, they point to object structures, the first field of which is a pointer to machine code.

Very nice and concise! And yes, this is probably enough for a lift ride.

But going further, what about literals and control-flow? It seems this list actually contains more than just pointers to subroutines (and it probably an array rather than a list). And similarly for subroutine-threaded code. The devil is in the details 😉

[alexshpilkin]

Assuming the interlocutor has some sort of background in implementing programming languages, I’d arrange the explanations in this order:

---

Take a conventional bytecode VM and consider how to optimize calls. You could remove the call instruction and instead make the dispatch table extensible. That’s called token threading.

Take once again a conventional bytecode VM and consider how to optimize dispatch. You could sacrifice some code density and replace the opcodes with code addresses you can then jump to / tail-call directly. But then it’s not clear how to combine this with the previous technique, because a non-primitive procedure needs both a code pointer (to a piece of code that creates a nested interpreter context) and a data pointer to the “byte”code; that is to say a closure. There are two fairly standard ways to do closures when the ABI doesn’t have them:

You don’t want to generate any native code at all. Represent closures as opaque objects with the native-code entry address at offset zero; pass it a pointer to self as one of the arguments. Non-native procedures will then store the stream of closure pointers after that first address. That’s indirect threading.

[Not a short elevator ride, but still, you could stop here.]

You are willing to generate the tiniest bit of native code. Then you can represent closures as trampolines that load the data address and then call the real implementation. Given you control where your data comes from and are willing to store it next to the code of the trampoline, this scheme can be simplified a bit to avoid storing that data address explicitly. That’s direct threading.

Finally, the next step on the journey of optimizing dispatch would be to generate lists of actual call instructions instead of lists of closure addresses. Welcome to subroutine threading, a proper native-code compiler is not that far away.

[ruv]

@alexshpilkin writes:

consider how to optimize calls. You could remove the call instruction and instead make the dispatch table extensible. That’s called token threading.

It should be probably added that you consider minimizing the size.

a non-primitive procedure needs both a code pointer (to a piece of code that creates a nested interpreter context) and a data pointer to the “byte”code; that is to say a closure.

Apparently the term "closure" is inappropriate here, because it is not a lexical closure.

pass it a pointer to self as one of the arguments.

Don't you typically pass it through the instruction pointer (the register IP) of the virtual machine?

Finally, the next step on the journey of optimizing dispatch would be to generate lists of actual call instructions

That were removed at the first step 😂
(well, at the first step you remove the VM call instructions, but now insert the call instructions of the host machine)

[MitchBradley]

For the parking garage:

There is also a "token threaded" variant where the pointers are not full addresses, but instead some extra-compact representation like indices into an array, or variable-length identifiers.

[jwoehr]

http://www.bradrodriguez.com/papers/moving1.htm

[ruv]

Thank you! This link was also mentioned in the initial question, and in one of the comments. 🙂

[MitchBradley]

But going further, what about literals and control-flow? ... The devil is in the details

The original question said "succinctly". Going down every rathole detail (like this thread seems to be doing) is a master class, not an "elevator explanation" per the topic line of the issue. But if someone were to insist, one could say:

"There are a few cases where literal values need to be interspersed in the list of pointers."

[SirWumpus]

"succinctly" you did.

The exercise was to avoid tangents and describe a concept/design sufficiently in a time frame (at which I failed). @MitchBradley so far has done so admirably. I thank you for that. Didn't think it was possible to condense the subject.

Details are not required unless you get invited off the elevator and asked to expand. But that is the point of an elevator pitch, catch the imagination.

[MitchBradley]

Take a conventional bytecode VM

It seems to me that this is a circular explanation, since a bytecode VM is essentially a token-threaded system. If one understands bytecode VMs, all you have to say is that threaded code is like bytecode except that you use lists of pointers instead of bytes that need a lookup step to find the code.

[alextangent]

Anton Ertl and I had a brief discussion on comp.lang.forth many years ago about having literals as first class citizens; that is, “findable” and “definable” in a pseudo wordlist and hence treatable in the same way as predeclared named CONSTANTs.  — Alex Sent from my iPhone On 8 Dec 2024, at 02:04, Mitch Bradley ***@***.***> wrote:

But going further, what about literals and control-flow? ... The devil is in the details

The original question said "succinctly". Going down every rathole detail (like this thread seems to be doing) is a master class, not an "elevator explanation" per the topic line of the issue. But if someone were to insist, one could say: "There are a few cases where literal values need to be interspersed in the list of pointers."

[ruv]

@alextangent wrote:

about having literals as first class citizens; that is, “findable” and “definable” in a pseudo wordlist and hence treatable in the same way as predeclared named CONSTANTs.

Technically, it is possible to generate a primitive definition for each numeric literal, and compile one item instead of two items for each numeric literal. But then you have to do the same for jumps and branches (if the purpose is a uniform list of pointers).

---

BTW, a significant difference of these "constants" from normal constants is that recognizing of these "constants" shall depend on the numeric BASE.

The dependency on BASE is also why one should not define a constant for a number in the form 123 constant 123 if the name is more than one digit long (and does not have a radix prefix).

[alextangent]

The idea is not to treat the constant as text for lookup purposes, but to convert the text to a number and CREATE or FIND-NAME that instead. Neither CREATE nor FIND-NAME should care that the string of length 2 (or 4 for 32 bit systems or 8 for 64 bit systems) is a number that doesn’t represent a printable string. This neatly sidesteps any issues with BASE or prefixes.

It introduces a potential issue that a 2/4/8 byte number that is also a string might match a normal text name; but since we are in the part of the interpreter/compiler where we’ve already decided that the text we saw wasn’t a name that could be found in the search order, that too is easily sidestepped by using a specific wordlist for constants that doesn’t appear in the normal search order.

To do the same for branches (if a uniform wordlist is required) requires moving the primitives BRANCH and ?BRANCH out of line and treating them much like CONSTANTs to be jumped to. The main benefit I saw from this was in optimization; it is easier moving code blocks and optimizing away if the lists are uniform. And if the branch targets are out of line, particularly when ELSE and THEN are compiled to definitions that have back-pointers to the source of the branch; fiddling around with the generated lists of pointers is much simplified. The same applies to DO/?DO/LOOP etc. But I digress; it is a separate subject.

[ruv]

The idea is not to treat the constant as text for lookup purposes, but to convert the text to a number and CREATE or FIND-NAME that instead. Neither CREATE nor FIND-NAME should care that the string of length 2 (or 4 for 32 bit systems or 8 for 64 bit systems) is a number that doesn’t represent a printable string. This neatly sidesteps any issues with BASE or prefixes.

Ah, I see now. Yes, you are right!

An alternative solution is to use a separate hash-table instead of create and find-name-in in the recognizer for numeric literals. This hash-table maps binary strings to execution tokens (xt) of anonymous definitions.

[MitchBradley]

Here's a slightly more accurate version, but requiring more attention from the listener:

Threaded code compactly represents an executable program as nested lists of numeric "threads" and interspersed literal values. Each thread refers to either a machine code primitive, another thread list, or a data object. The primitives often implement operations on a stack-based virtual machine. The code to traverse the lists is typically very simple, consisting of just a few machine instructions.

There are many variants with names like "direct threaded", "indirect threaded", "subroutine threaded", "token threaded", and "byte-coded". They refer to differences in the ways that the thread numbers are encoded to both "point" to their referents and to distinguish between code, thread lists, and data. They have different tradeoffs for size, speed, ease of implementation, relocation, cross-platform portability, and interactions with machine architecture details like memory models and caching.

[noqsi]

There are more domains than DSLs. If your domain would benefit, invent one.

On Dec 8, 2024, at 5:52 PM, Anthony Howe ***@***.***> wrote: Well I meant don't invent yet another DSL as there are plenty about. — Reply to this email directly, view it on GitHub <#187 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AADC2QLVCD273IRN2LA4AT32ETER5AVCNFSM6AAAAABTEWS3ZCVHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTCNJQGIZDOMQ>. You are receiving this because you are subscribed to this thread.

John Doty ***@***.***