4 ms·

This quote stood out as sounding quite far-fetched: "on many CPUs the interpreter consists of two or three machine instructions". Can someone point to an exampl

by it 7y ago

This quote stood out as sounding quite far-fetched: "on many CPUs the interpreter consists of two or three machine instructions". Can someone point to an example?

stevekemp 7y ago
The previous reply explained things pretty much - many implementations have "Words" (i.e. functions) be invoked by just jumping from one to the next. If you have some spare time reading this implementation is very enlightening: https://github.com/nornagon/jonesforth/blob/master/jonesforth.S https://github.com/nornagon/jonesforth/blob/master/jonesfort... Though I appreciate it is a little low-level it explains things very well, and is readable if you have only a hazy grasp of assembly language. The specific documentation I was thinking about is this section on calling sequential functions: https://github.com/nornagon/jonesforth/blob/4f853252f715132e7716cbd44e5306cefb6a6fec/jonesforth.S#L235 https://github.com/nornagon/jonesforth/blob/4f853252f715132e...
DonHopkins 7y ago
FORTH has both an "inner interpreter" and an "outer interpreter" (aka the compiler, but that also works interactively like an interpreter). The inner interpreter is the thing that threads between words, and is typically an assembly function named "NEXT", which can be just a few instructions. Here is the FIG-FORTH 6502 implementation of "NEXT" (which is a bunch of instructions since the 6502 has 8 bit registers and simple addressing modes): https://ksquiggle.neocities.org/ff6502.htm https://ksquiggle.neocities.org/ff6502.htm 0122 0244 ; 0123 0244 ; NEXT is the address interpreter that moves from 0124 0244 ; machine level word to word. 0125 0244 ; 0126 0244 A0 01 NEXT LDY #1 0127 0246 B1 AE LDA (IP),Y Fetch code field address pointed 0128 0248 85 B2 STA W+1 to by IP 0129 024A 88 DEY 0130 024B B1 AE LDA (IP),Y 0131 024D 85 B1 STA W 0132 024F 20 6F 02 JSR TRACE Remove this when all is well 0133 0252 18 CLC Increment IP by two 0134 0253 A5 AE LDA IP 0135 0255 69 02 ADC #2 0136 0257 85 AE STA IP 0137 0259 90 02 BCC L54 0138 025B E6 AF INC IP+1 0139 025D 4C B0 00 L54 JMP W-1 Jump to an indirect jump (W) (This is actually self-modifying code that write the indirect address to jump to into W, the operand of an indirect JMP instruction at W-1, then does an absolute JMP to W-1 to jump indirect through W.) Some CPUs can implement "NEXT" in one or only a few instructions, and FORTH implementations can use "indirect threading" (like the above 6502 implementation that indirectly jumps through each word's CFA (Code Field Address)) or "direct threading" where the word pointers refer directly to code, or they can even compile words directly to machine language instructions instead of threaded pointers (so there's effectively no inner interpreter, just direct machine language calls), and in that case they can even inline "NEXT" at the end of every word definition for speed, instead of jumping to a global "NEXT" implementation (subroutine threaded machine code). https://en.wikipedia.org/wiki/Threaded_code#Threading_models https://en.wikipedia.org/wiki/Threaded_code#Threading_models And there are other possible variations and hybrid combinations, like "subroutine threading" or "token threading", which you might want to use to implement FORTH systems in C or other higher level languages, using function pointers (like CForth) or switch statement tokens for built-in primitives (like machine-independent OpenFirmware byte code): https://github.com/MitchBradley/cforth https://github.com/MitchBradley/cforth https://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Direct-or-Indirect-Threaded_003f.html https://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Dir... The outer interpreter is the parser and compiler, which is written in FORTH, and includes a bunch of words, but is extremely simple (and extremely extensible) compared to other language interpreters. The outer interpreter can be in interpret or compile mode (controlled by a variable called "STATE"): when you're typing expressions interactively in interpret state, it executes them immediately, but when you start a word definition (with ":") it goes into compile state and compiles the words instead of executing them. Except that in compile mode it does execute specially marked "immediate" words, with which you can implement control flow and macros. There are immediate words [ and ] that switch between compile/interpret states, so in the middle of a word definition you can pop out into interpret mode and execute arbitrary computations (like macros or meta programming), then pop back into compile mode. For example you could compute a number, and then compile it as an inline literal! And then there's <builds and does>, which are word defining words, that let you do certain kinds of meta-programming, implement your own domain specific languages, data types, object systems, and extend the FORTH interpreter and compiler in FORTH. http://www.forth.org/svfig/Len/definwds.htm http://www.forth.org/svfig/Len/definwds.htm >It has been said that one does not write a program in Forth. Rather, one extends Forth to make a new language specifically designed for the application at hand. An important part of this process is the defining word, by which it is possible to combine a data structure with an action to create multiple instances that differ only in detail. One thinks of a cookie-cutter; all the cookies are the same shape but have different-colored icing.
- DonHopkins 7y ago
  Here's a cool dynamic WebAssembly based Forth: https://el-tramo.be/blog/waforth/ https://el-tramo.be/blog/waforth/ >The Interpreter >The interpreter runs a loop that processes commands, and switches to and from compiler mode. >Contrary to some other Forth systems, WAForth doesn’t use direct threading for executing code, where generated code is interleaved with data, and the program jumps between these pieces of code. WebAssembly doesn’t allow unstructured jumps, let alone dynamic jumps. Instead, WAForth uses subroutine threading, where each word is implemented as a single WebAssembly function, and the system uses calls and indirect calls (see below) to execute words. >The Compiler >While in compile mode for a word, the compiler generates WebAssembly instructions in binary format (as there is no assembler infrastructure in the browser). Because WebAssembly doesn’t support JIT compilation yet, a finished word is bundled into a separate binary WebAssembly module, and sent to the loader, which dynamically loads it and registers it in a shared function table at the next offset, which in turn is recorded in the word dictionary. >Because words reside in different modules, all calls to and from the words need to happen as indirect call_indirect calls through the shared function table. This of course introduces some overhead. >As WebAssembly doesn’t support unstructured jumps, control flow words (IF/ELSE/THEN, LOOP, REPEAT, …) can’t be implemented in terms of more basic words, unlike in jonesforth. However, since Forth only requires structured jumps, the compiler can easily be implemented using the loop and branch instructions available in WebAssembly.
  - arethuza 7y ago
    Someone has done a port of PostScript (GhostScript) to WebAssembly: https://chrome.google.com/webstore/detail/postscript-viewer/ebpiondkhkldijolgmhfenknngkkjola https://chrome.google.com/webstore/detail/postscript-viewer/... I wonder if NeWS, or something similar, could be resurrected in-browser?
- deleted 7y ago
  [deleted]
- JdeBP 7y ago
  One can get a 6502 to do NEXT in a single instruction and have an IP register in hardware ... if one sticks a coprocessor onto it. Witness the KimKlone. * http://laughtonelectronics.com/Arcana/KimKlone/Kimklone_short_summary.html http://laughtonelectronics.com/Arcana/KimKlone/Kimklone_shor... (https://news.ycombinator.com/item?id=16564257 https://news.ycombinator.com/item?id=16564257)
Gracana 7y ago
See "Moving Forth": https://www.bradrodriguez.com/papers/moving1.htm https://www.bradrodriguez.com/papers/moving1.htm The "interpreter" is just the macro that handles execution of the next subroutine in a threaded program. As in: https://en.wikipedia.org/wiki/Threaded_code https://en.wikipedia.org/wiki/Threaded_code It might only be a call instruction, or a pointer increment and a jump. If you have to move the pointer to the working register to increment it, that's three instructions.
TruffleLabs 7y ago
The book “Threaded interpretive languages” by R. G. Loeliger has details on how Forth & Forth like languages are built re: core interpreter & threading of words.
- russh 7y ago
  That is the best book anyone has ever loaned me and some day I plan on returning it.
mikekchar 7y ago
In FORTH there is a distinction between the compiler and the interpreter. Each function in FORTH is called a "word". You define a word by giving it a name (historically only the first X characters counted -- often 8). The compiled words are stored in a "dictionary" which is essentially a key value pair with the name of a compiled word and a pointer to its compiled code. When you are compiling a word, you add a new entry to the dictionary. Then for each word contained in the new word you are defining, you look it up in the dictionary and store the pointer to its compiled code. So essentially, the compiled code consists of a list of pointers -- one for each function call you are making. It's a little more complicated than that, but not much. Numerical literals need to be added to the stack rather than being treated as a pointer to a function, but there are a variety of ways you can tag the information you are putting in the list. The interpreter works by taking a pointer to the function, and running it. This will essentially jump you to another pointer to a function which you will run. That will jump you to another pointer to a function which you will run. Eventually you will end up pointing to a function that was hand implemented in assembly language (part of the kernel for the language). This technique is known as a "threaded interpreted language" (TIL). I haven't really explained it very well, but essentially it's just either pushing a literal onto the stack or jumping to a subroutine. The actual code for the interpreter is insanely small because it does virtually nothing (either jump to a subroutine or push a value onto the stack). While the entire thing is not 2 or 3 machine instructions, the actual running functionality would just be looping through something of that size. One of the nice things about this setup is that it's pretty easy to write an entire FORTH kernel in 16 or 32K. So all of the actually executing code will fit in the cache of even a small processor. The rest of the code is literally lists of addresses and integer literals. They are super easy to fetch and you can also be tricky about optimising how you fetch them. The end result is that you barely ever hit main memory when talking about the code part of the system. And since you prefer working on the stack to working on the heap, you get really good locality on the working memory as well. This can give you insanely good performance with very little cognitive overhead as a programmer.
- mycall 7y ago
  It the kernel and interpreter typically single threaded? I'm curious how it handles UARTs, IRQs and atomics.
boygobbo 7y ago
https://github.com/nornagon/jonesforth/blob/4f853252f715132e7716cbd44e5306cefb6a6fec/jonesforth.S#L501-L505 https://github.com/nornagon/jonesforth/blob/4f853252f715132e...

by it 7y ago

This quote stood out as sounding quite far-fetched: "on many CPUs the interpreter consists of two or three machine instructions". Can someone point to an example?

stevekemp 7y ago

The previous reply explained things pretty much - many implementations have "Words" (i.e. functions) be invoked by just jumping from one to the next. If you have some spare time reading this implementation is very enlightening: https://github.com/nornagon/jonesforth/blob/master/jonesforth.S https://github.com/nornagon/jonesforth/blob/master/jonesfort... Though I appreciate it is a little low-level it explains things very well, and is readable if you have only a hazy grasp of assembly language. The specific documentation I was thinking about is this section on calling sequential functions: https://github.com/nornagon/jonesforth/blob/4f853252f715132e7716cbd44e5306cefb6a6fec/jonesforth.S#L235 https://github.com/nornagon/jonesforth/blob/4f853252f715132e...

DonHopkins 7y ago

FORTH has both an "inner interpreter" and an "outer interpreter" (aka the compiler, but that also works interactively like an interpreter). The inner interpreter is the thing that threads between words, and is typically an assembly function named "NEXT", which can be just a few instructions. Here is the FIG-FORTH 6502 implementation of "NEXT" (which is a bunch of instructions since the 6502 has 8 bit registers and simple addressing modes): https://ksquiggle.neocities.org/ff6502.htm https://ksquiggle.neocities.org/ff6502.htm 0122 0244 ; 0123 0244 ; NEXT is the address interpreter that moves from 0124 0244 ; machine level word to word. 0125 0244 ; 0126 0244 A0 01 NEXT LDY #1 0127 0246 B1 AE LDA (IP),Y Fetch code field address pointed 0128 0248 85 B2 STA W+1 to by IP 0129 024A 88 DEY 0130 024B B1 AE LDA (IP),Y 0131 024D 85 B1 STA W 0132 024F 20 6F 02 JSR TRACE Remove this when all is well 0133 0252 18 CLC Increment IP by two 0134 0253 A5 AE LDA IP 0135 0255 69 02 ADC #2 0136 0257 85 AE STA IP 0137 0259 90 02 BCC L54 0138 025B E6 AF INC IP+1 0139 025D 4C B0 00 L54 JMP W-1 Jump to an indirect jump (W) (This is actually self-modifying code that write the indirect address to jump to into W, the operand of an indirect JMP instruction at W-1, then does an absolute JMP to W-1 to jump indirect through W.) Some CPUs can implement "NEXT" in one or only a few instructions, and FORTH implementations can use "indirect threading" (like the above 6502 implementation that indirectly jumps through each word's CFA (Code Field Address)) or "direct threading" where the word pointers refer directly to code, or they can even compile words directly to machine language instructions instead of threaded pointers (so there's effectively no inner interpreter, just direct machine language calls), and in that case they can even inline "NEXT" at the end of every word definition for speed, instead of jumping to a global "NEXT" implementation (subroutine threaded machine code). https://en.wikipedia.org/wiki/Threaded_code#Threading_models https://en.wikipedia.org/wiki/Threaded_code#Threading_models And there are other possible variations and hybrid combinations, like "subroutine threading" or "token threading", which you might want to use to implement FORTH systems in C or other higher level languages, using function pointers (like CForth) or switch statement tokens for built-in primitives (like machine-independent OpenFirmware byte code): https://github.com/MitchBradley/cforth https://github.com/MitchBradley/cforth https://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Direct-or-Indirect-Threaded_003f.html https://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Dir... The outer interpreter is the parser and compiler, which is written in FORTH, and includes a bunch of words, but is extremely simple (and extremely extensible) compared to other language interpreters. The outer interpreter can be in interpret or compile mode (controlled by a variable called "STATE"): when you're typing expressions interactively in interpret state, it executes them immediately, but when you start a word definition (with ":") it goes into compile state and compiles the words instead of executing them. Except that in compile mode it does execute specially marked "immediate" words, with which you can implement control flow and macros. There are immediate words [ and ] that switch between compile/interpret states, so in the middle of a word definition you can pop out into interpret mode and execute arbitrary computations (like macros or meta programming), then pop back into compile mode. For example you could compute a number, and then compile it as an inline literal! And then there's <builds and does>, which are word defining words, that let you do certain kinds of meta-programming, implement your own domain specific languages, data types, object systems, and extend the FORTH interpreter and compiler in FORTH. http://www.forth.org/svfig/Len/definwds.htm http://www.forth.org/svfig/Len/definwds.htm >It has been said that one does not write a program in Forth. Rather, one extends Forth to make a new language specifically designed for the application at hand. An important part of this process is the defining word, by which it is possible to combine a data structure with an action to create multiple instances that differ only in detail. One thinks of a cookie-cutter; all the cookies are the same shape but have different-colored icing.

DonHopkins 7y ago
Here's a cool dynamic WebAssembly based Forth: https://el-tramo.be/blog/waforth/ https://el-tramo.be/blog/waforth/ >The Interpreter >The interpreter runs a loop that processes commands, and switches to and from compiler mode. >Contrary to some other Forth systems, WAForth doesn’t use direct threading for executing code, where generated code is interleaved with data, and the program jumps between these pieces of code. WebAssembly doesn’t allow unstructured jumps, let alone dynamic jumps. Instead, WAForth uses subroutine threading, where each word is implemented as a single WebAssembly function, and the system uses calls and indirect calls (see below) to execute words. >The Compiler >While in compile mode for a word, the compiler generates WebAssembly instructions in binary format (as there is no assembler infrastructure in the browser). Because WebAssembly doesn’t support JIT compilation yet, a finished word is bundled into a separate binary WebAssembly module, and sent to the loader, which dynamically loads it and registers it in a shared function table at the next offset, which in turn is recorded in the word dictionary. >Because words reside in different modules, all calls to and from the words need to happen as indirect call_indirect calls through the shared function table. This of course introduces some overhead. >As WebAssembly doesn’t support unstructured jumps, control flow words (IF/ELSE/THEN, LOOP, REPEAT, …) can’t be implemented in terms of more basic words, unlike in jonesforth. However, since Forth only requires structured jumps, the compiler can easily be implemented using the loop and branch instructions available in WebAssembly.
- arethuza 7y ago
  Someone has done a port of PostScript (GhostScript) to WebAssembly: https://chrome.google.com/webstore/detail/postscript-viewer/ebpiondkhkldijolgmhfenknngkkjola https://chrome.google.com/webstore/detail/postscript-viewer/... I wonder if NeWS, or something similar, could be resurrected in-browser?
deleted 7y ago
[deleted]
JdeBP 7y ago
One can get a 6502 to do NEXT in a single instruction and have an IP register in hardware ... if one sticks a coprocessor onto it. Witness the KimKlone. * http://laughtonelectronics.com/Arcana/KimKlone/Kimklone_short_summary.html http://laughtonelectronics.com/Arcana/KimKlone/Kimklone_shor... (https://news.ycombinator.com/item?id=16564257 https://news.ycombinator.com/item?id=16564257)

Gracana 7y ago

See "Moving Forth": https://www.bradrodriguez.com/papers/moving1.htm https://www.bradrodriguez.com/papers/moving1.htm The "interpreter" is just the macro that handles execution of the next subroutine in a threaded program. As in: https://en.wikipedia.org/wiki/Threaded_code https://en.wikipedia.org/wiki/Threaded_code It might only be a call instruction, or a pointer increment and a jump. If you have to move the pointer to the working register to increment it, that's three instructions.

TruffleLabs 7y ago

The book “Threaded interpretive languages” by R. G. Loeliger has details on how Forth & Forth like languages are built re: core interpreter & threading of words.

russh 7y ago
That is the best book anyone has ever loaned me and some day I plan on returning it.

mikekchar 7y ago

In FORTH there is a distinction between the compiler and the interpreter. Each function in FORTH is called a "word". You define a word by giving it a name (historically only the first X characters counted -- often 8). The compiled words are stored in a "dictionary" which is essentially a key value pair with the name of a compiled word and a pointer to its compiled code. When you are compiling a word, you add a new entry to the dictionary. Then for each word contained in the new word you are defining, you look it up in the dictionary and store the pointer to its compiled code. So essentially, the compiled code consists of a list of pointers -- one for each function call you are making. It's a little more complicated than that, but not much. Numerical literals need to be added to the stack rather than being treated as a pointer to a function, but there are a variety of ways you can tag the information you are putting in the list. The interpreter works by taking a pointer to the function, and running it. This will essentially jump you to another pointer to a function which you will run. That will jump you to another pointer to a function which you will run. Eventually you will end up pointing to a function that was hand implemented in assembly language (part of the kernel for the language). This technique is known as a "threaded interpreted language" (TIL). I haven't really explained it very well, but essentially it's just either pushing a literal onto the stack or jumping to a subroutine. The actual code for the interpreter is insanely small because it does virtually nothing (either jump to a subroutine or push a value onto the stack). While the entire thing is not 2 or 3 machine instructions, the actual running functionality would just be looping through something of that size. One of the nice things about this setup is that it's pretty easy to write an entire FORTH kernel in 16 or 32K. So all of the actually executing code will fit in the cache of even a small processor. The rest of the code is literally lists of addresses and integer literals. They are super easy to fetch and you can also be tricky about optimising how you fetch them. The end result is that you barely ever hit main memory when talking about the code part of the system. And since you prefer working on the stack to working on the heap, you get really good locality on the working memory as well. This can give you insanely good performance with very little cognitive overhead as a programmer.

mycall 7y ago
It the kernel and interpreter typically single threaded? I'm curious how it handles UARTs, IRQs and atomics.

boygobbo 7y ago

https://github.com/nornagon/jonesforth/blob/4f853252f715132e7716cbd44e5306cefb6a6fec/jonesforth.S#L501-L505 https://github.com/nornagon/jonesforth/blob/4f853252f715132e...