For anyone who likes playing with small experimental projects, I once made a minimal, esoteric canvas colouring language inspired by Forth and Tixy: https://susam.net/fxyt.html
I'm always interested in hearing people's reactions to Forth though and every now and then you get a cool new story on these threads, so I'm not complaining.
Well, I don't know if this qualifies as useful, but I wrote a minimal roguelike in one page of Forth last year: https://asciinema.org/a/672405
vdupras is here in the comments today. He's written a self-hosting interactive operating system in Forth, including a FAT16 filesystem and everything, and a compiler for a useful subset of C: https://duskos.org/
As I like to say: "C is a language that solves a million problems. Forth is a million languages that solve almost nothing." :-P
I've been reading about Forth for 30-40 years. The dual stack is easy to understand. My problem is that I cannot see how control flow works in Forth, e.g. a simple if-then-else.
I think that something as fundamental as an if-then-else should be obvious in a useful language. Heck, it's obvious in assembly language. But not in Forth.
It's funny that you say that, because from my point of view, control flow in Forth is one of its strong points over assembly language, because it has properly nesting control-flow structures. The syntax is a little strange; the literal translation of
if (siz != 0) *d = '\0';
is (untested)
siz @ 0<> if 0 d @ c! then
when what you'd normally expect is something like
if siz @ 0<> then 0 d @ c! fi
but that's sort of a question of RPN. At least else comes where you expect it, even though that makes then even stranger; we can translate
if (key < tree->key) {
tree++;
} else {
tree = tree->right;
}
literally as (untested)
key @ tree ->key @ <
if kvpairsize tree +!
else tree ->right @ tree !
then
Now, if you were comparing Forth to Lua or C here, I would agree: this is far less obvious, in the sense that it's completely unfamiliar and requires you to learn Forth's idiosyncratic way of writing things. But in assembly language? GCC generates, in context, the following assembly code for the C if-else statement above:
addhi r0, r0, #8
bhi .L5
ldr r0, [r0, #4]
b .L6
This is using the flags from a preceding equality comparison, and the branch target labels are earlier in the enclosing loop. You can not tell me that this is "obvious" if you don't know ARM assembly!
From a certain point of view, Forth is just what you get if you take assembly language and look for the simplest way to add properly nesting expressions, properly nesting control structures, subroutines with arguments and return values, arbitrary compile-time computation, an interactive debugging environment, a scripting language, disk storage, and multithreading.
I kinda know how it works at the user-level, I meant to write that I don't understand how control-flow is implemented in Forth. I say more about that in my reply to a sibling comment: https://news.ycombinator.com/item?id=45334556
> My problem is that I cannot see how control flow works in Forth, e.g. a simple if-then-else.
What made it click for me was http://www.exemark.com/FORTH/eForthOverviewv5.pdf, specifically sections 2.3 "Loops and Branches" and 5.3 "Structures". With a slight simplification, if/else/then branching is defined in 7 words.
Two primitive words, branch and ?branch (in python because I know it better than assembly):
def branch():
""" branch is followed by an address, which it unconditionally jumps to."""
ip = code[ip] # Get address from next cell in code, jump to it.
def branch_if_zero():
""" ?branch is followed by an address. ?branch either jumps to that address,
or skips over the address & continues executing, depending on the value on the
stack."""
if stack.pop() == 0: # Pop flag off stack
ip = code[ip] # Branch to address held in cell after ?branch
else:
ip += 1 # Don't branch, skip over address & keep executing
Two helper words for forward branching. >MARK adds a placeholder branch address to code and pushes the address of the placeholder. >RESOLVE resolves the branch by replacing the placeholder with the address from the stack.
: >MARK ( -- A ) HERE 0 , ;
: >RESOLVE ( A -- ) HERE SWAP ! ;
And then the actual IF, ELSE, and THEN words. IF puts ?branch and a placeholder address in code. ELSE puts branch and a placeholder address in code, then updates the preceding branch address (from an IF or ELSE) to land after the ELSE. THEN updates the preceding branch address to land after the THEN.
: IF ( -- A ) COMPILE ?branch >MARK ; IMMEDIATE
: ELSE ( A -- A ) COMPILE branch >MARK SWAP >RESOLVE ; IMMEDIATE
: THEN ( A -- ) >RESOLVE ; IMMEDIATE
Thanks for that. I kinda know how it "works" at the user-level. I meant to say, I don't know how it is implemented.
My mental model of Forth is that there is a simple parser that consumes space-delimited keywords. The interpreter looks up that keyword in a dictionary, which gives the address of the machine code that handles that word. The interpreter either makes a subroutine call to that address (subroutine threaded), or jumps to that address (called "direct threaded" if I recall, where the handler jumps back to the interpreter instead of executing a RET).
But that's where my mental model of Forth breaks down, because IF-THEN-ELSE cannot be implemented in that model. So there must be something else fundamental in the Forth interpreter that I don't understand.
> So there must be something else fundamental in the Forth interpreter that I don't understand.
The missing bit is IMMEDIATE mode. Words can be tagged as IMMEDIATE, which means that they get executed at compile time (or parse time, for an interpreter), rather than a call to them getting compiled (executed at run time, for an interpreter). IF/ELSE/THEN are then "just" IMMEDIATE mode words -- but you can add your own. The "special sauce" is that IF compiles (easier to talk about for a compiler; generalize as needed) a conditional branch to an unknown address, and puts the address of that branch instruction (or an equivalent) on the /compile time/ data stack; THEN then looks at the address on the /compile time/ data stack and patches that instruction to branch to the correct address. Plenty of subtlety possible, but the basic primitive of IMMEDIATE mode is the key.
Ah I see, this is peeling back a few layers of obscurity about the Forth interpreter for me. Let's stick with a Forth interpreter because that seems easier to think about for me.
Are you saying that the Forth interpreter is a 2-pass interpreter? Or does the interpreter go into a special IMMEDIATE mode upon hitting the IF keyword, then it just consumes subsequent tokens without doing any dispatching, until it hits the THEN token? It sounds like nested IF-THEN-ELSE becomes tricky to handle.
How does the FORTH interpreter handle loops? Does the interpreter hit the WHILE token, goes into IMMEDIATE mode, remembers the location of the WHILE, then dispatches all the subsequent code, until it hits the REPEAT token, then branches back to the WHILE?
Oh, and because I didn't address it directly in the longer answer...
> Does the interpreter hit the WHILE token, goes into IMMEDIATE mode, remembers the location of the WHILE, then dispatches all the subsequent code, until it hits the REPEAT token, then branches back to the WHILE?
Yes. The beauty is that, in the context of a threaded code compiler (which, again, I encourage you to use as your default model for Forth, even though other options are possible), WHILE just pushes the address of the output code stream onto the compile-time stack. REPEAT expects the address to be on the compile-time stack and compiles a conditional jump to that address. This obviously and trivially provides support for nested control structures of all types; as long as the word that pushes compile-time data onto the stack is correctly paired with the word the pops it, we have stack semantics for nested control, which is exactly the expectation. So while your description is completely correct, "remembers" is almost trivial here -- "puts data on stack" is the primitive operation of remembering anything in Forth, and that's all that's needed here, no fancy data structures or look-aside buffers or anything. (Note that the compiler does require at least two non-stack data structures, the symbol table and the output code stream, but those reflect real domain complexity.)
I've actually never worked with a "pure" interpreter in Forth, only compilers of various levels of complexity. Threaded code compilers are (in my experience) by far the most common way to deal with forth -- and they are very much 2-pass. Even when used as an "interpreter," they generate (trivial, usually) machine code, then jump to it.
Consider a definition (in some ill-defined Forth variant) like
: abs-sqr ( n -- |n^2| ) * 0 < if neg then ;
We can categorize things:
IMMEDIATE words used here are : ( if then ;
Normal words are * < neg
Literals are 0
Tokens that are not seen by the compiler directly (!) are abs-sqr, the contents of the comment, and )
So the compiler goes through one token (that it sees) at a time.
First up is `:`. `:` is an IMMEDIATE word, so the compiler just calls it now. `:` then consumes a symbol (`abs-sqr`) from the token stream so the compiler won't see it (think of calling next() on an iterator in python or equivalent), then creates a symbol table entry from that symbol to the /current compiled code output stream pointer/ -- that is, just after the last piece of code that was compiled.
Next up is `(`, since we already consumed `abs-sqr`. This is an IMMEDIATE word again -- and it just consumes tokens until one of them is exactly `)`, discarding them -- that is, it defines a comment.
Finally we get to the "easy" case, `*`. The compiler finally compiles! It looks up this symbol in the symbol table, sees that it is /not/ IMMEDIATE, and compiles a call to this address.
Now the compiler sees `0`. This is a literal token, so we don't even bother with the symbol table; we special-case code to push this value on the stack.
'<' is a non-IMMEDIATE symbol, we already know this case.
We've already discussed `if`, `neg`, and `then`. And `;` is an IMMEDIATE word that just puts a return instruction into the code stream.
Clear as mud?
There's one more step from here that's important to make, which is that the choice of what's IMMEDIATE or not is not strictly defined. Some words must be IMMEDIATE for correctness, if they interact with the compiler in interesting ways, like consuming tokens or back-patching instructions. But suppose we want to be clever... `<` works fine as a non-IMMEDIATE word. If we want to inline it, we /could/ have the compiler generalize by looking at the instructions pointed to by it, seeing how long they are (or tracking that in the symbol table), and deciding whether to inline... or we can just re-implement `<` as an immediate word that adds the appropriate instructions directly into the code stream. Combined with assembly words, this can be pretty trivially expressed, and it really changes the paradigm a bit.
> We can categorize things:
> IMMEDIATE words used here are : ( if then ;
`:` normally isn’t immediate
> First up is `:`. `:` is an IMMEDIATE word, so the compiler just calls it now
`:` gets executed because the interpreter, when it isn’t compiling, goes through a loop:
1) read a token until the next space in the input
2) look up that token in the dictionary
3a) if a word is found: call it
3b) if no word is found: try interpreting the token as a number
4a) if it can be interpreted such: push that number on the stack
4b) if it cannot: bail out with an error message
So, `:` gets called in step 3a.
> Now the compiler sees `0`. This is a literal token, so we don't even bother with the symbol table; we special-case code to push this value on the stack.
As indicated above, that’s not how ‘normal’ forths work. A lookup is done for a word named `0`, and if it exists, a call to it is compiled.
Many forths had words named after small constants such as `0`, `1`, `2` or `-1` because compiling a call to a function took less memory than compiling a call to the “LIT” function and compiling the constant value.
> I've actually never worked with a "pure" interpreter in Forth, only compilers of various levels of complexity. Threaded code compilers are (in my experience) by far the most common way to deal with forth -- and they are very much 2-pass. Even when used as an "interpreter," they generate (trivial, usually) machine code, then jump to it.
Lots of good info, thank you. I don't think I will fully understand what you wrote until I implement a Forth interpreter myself.
So a side question: If most Forth "interpreters" are compilers, how does a Forth interpreter work in a Harvard architecture microprocessor (with separate memory space for data and instructions) instead of a Von Neumann architecture with a unified memory layout? In other words, in a Harvard architecture (e.g. AVR microcontrollers), the Forth compiler will live in read-only flash ROM, and it cannot generate machine code into RAM and execute it, because the data memory is not executable.
> how does a Forth interpreter work in a Harvard architecture microprocessor
You compile to "direct threaded code" in data memory; direct threaded code represents a sequence of calls as a sequence of addresses to call. So while "normal" threaded code (what Wikipedia calls "subroutine threading") would just have
call word_a
call word_b
call word_c
And then executing that means jumping to the first instruction, direct threaded code would have
&word_a
&word_b
&word_c
And then there's a suuuuper tiny runtime (like four of five instructions, literally) that has a "runtime instruction pointer" or whatever you want to call it, and just increments that and does an indirect call through to the next word whenever it's returned to.
No, that's not it. It's much simpler than that, yet has much deeper implications than you think. You don't see it in other languages. The closest thing would maybe be compile-time macros in Zig? But in Forth, the power it unlocks comes in its purest form, without any fluff around it.
As @addaon writes, your missing ingredient is immediateness. This is one of the most powerful, yet mind-boggling aspects of Forth. I encourage you to check it out, it will make you grow as a developer.
If understanding this special IMMEDIATE mode is required to understand the Forth interpreter for something as fundamental as control-flow, it seems fair to say that Forth is not a simple language. It's not just an advanced programmable RPN calculator An RPN calculator has a program counter, which makes control-flow easy to understand.
In comparison, C is a high level language, but the mapping from C code to assembly language is relatively simple. (Yes, compiler optimizations against the C "abstract machine" can make the resulting code completely obscure. But if we turn off optimization, the resulting assembly code matches the C code fairly directly.)
Very much the contrary! In C all the syntax and control structures have to be built into the language; this makes C a much more complex language than Forth, because in Forth the language and interpreter don't even have to support things like comments, string literals, variables, and control flow. Because of immediate words, all of that can be built on top of the base language in high-level Forth, and almost always is. This allows the language itself to be enormously simpler.
It's also generally the case that in a native-code-compiling Forth the mapping from the Forth source to the machine code emitted is very much simpler and more direct than in C; as Virgil implicitly pointed out, the machine code is generally more or less in the same order as the source code, which in C it is not, and you don't have a bunch of implicit type conversions, ad-hoc polymorphic arithmetic operators, and so on. (It doesn't have to be more direct, since you can do arbitrary computation at compile time, but it usually is.)
> If understanding this special IMMEDIATE mode is required to understand the Forth interpreter for something as fundamental as control-flow, it seems fair to say that Forth is not a simple language. It's not just an advanced programmable RPN calculator An RPN calculator has a program counter, which makes control-flow easy to understand.
"Simple" is not a well-defined threshold but rather a continuum, so it's hard to agree or disagree with this. I think it's perfectly valid to observe that Forth is more complex than an RPN calculator, though.
But think of it this way: An RPN calculator has two types of tokens, literals and symbols. When seeing a literal, it evaluates a push of that literal to the stack. When seeing a symbol, it evaluates an immediate call to the behavior associated with that symbol.
Forth adds exactly one more concept: non-IMMEDIATE words. Everything an RPN calculator can do can be done as IMMEDIATEs in Forth. But by adding one metadata bit to the symbol table (IMMEDIATE or not), and adding a threaded call to any non-IMMEDIATE words to the output code stream, Forth gains function definition, full generic control flow support, compiler extensibility, support for embedding domain-specific languages (just IMMEDIATE words that consume the interesting tokens), and more.
I don't know if this counts as "simple" compared to C, but it surely counts as "parsimonious." It's hard to think of a more cleanly defined single semantic change that adds as much power to a language.
(And of course in C, once you understand the language understanding the runtime library is mostly about understanding runtime behavior, some macros not withstanding; but in Forth, the runtime library and the language are conflated through IMMEDIATE symbols, so this separation is much less clear; totally accept that this could be considered less "simple", although in practice most Forths have about as many pre-defined IMMEDIATE words as C has keywords.)
I understand that to the newcomer, it might not appear that way, but implementing a Forth is really eye-opening in that regard.
If I might allow myself a bit of promotion, I wrote https://tumbleforth.hardcoded.net/ as such an eye-opening process. It's less "gentle" than Easy Forth here, but it digs deeper.
From the comments in this thread, it seems that to understand how Forth implements a simple IF-THEN-ELSE control-flow, I have to understand the difference between non-immediate and immediate words. I also have to understand the difference between outer and inner interpreter. And I have to understand how Forth generates snippets of machine code (where does that get stored? I thought Forth only has 2 stacks, does it also have a general heap?). Then understand how the THEN token goes back and patches the placeholder address generated by the IF token. And understand the difference between the parsing phase and the interpreted phase of the Forth interpreter/compiler.
But you are saying that the Forth version is simpler than C version which will kinda look like this after it's compiled (Z80 assembly code, it's in my head right now):
It's fine, I can't force you in either. Maybe one day you'll dive into the subject. From the look of the comments here, you have all the hints you need.
You're describing the outer interpreter in interpretation state; Forth control flow words don't work properly in interpretation state, only in compile state.
They're immediate words, so they execute at compile time instead of run time, so they can do arbitrary things to the code being compiled. Here's Mike Perry and Henry Laxen's implementation of the main control-flow words from F83, which is an indirect-threaded Forth:
\ Run Time Code for Control Structures 04OCT83HHL \ \ Run Time Code for Control Structures 05MAR83HHL
CODE BRANCH (S -- ) \ BRANCH Performs an unconditional branch. Notice that we
LABEL BRAN1 0 [IP] IP MOV NEXT END-CODE \ are using absolute addresses insead of relative ones. (fast)
CODE ?BRANCH (S f -- ) \ ?BRANCH Performs a conditional branch. If the top of the
AX POP AX AX OR BRAN1 JE IP INC IP INC NEXT END-CODE \ parameter stack in True, take the branch. If not, skip
\ over the branch address which is inline.
\ Extensible Layer Structures 03Apr84map \ \ Extensible Layer Structures 03Apr84map
: ?CONDITION (S f -- ) \ ?CONDITION
NOT ABORT" Conditionals Wrong" ; \ Simple compile time error checking. Usually adequate
: >MARK (S -- addr ) HERE 0 , ; \ >MARK Set up for a Forward Branch
: >RESOLVE (S addr -- ) HERE SWAP ! ; \ >RESOLVE Resolve a Forward Branch
: <MARK (S -- addr ) HERE ; \ <MARK Set up for a Backwards Branch
: <RESOLVE (S addr -- ) , ; \ <RESOLVE Resolve a Backwards Branch
: ?>MARK (S -- f addr ) TRUE >MARK ; \ ?>MARK Set up a forward Branch with Error Checking
: ?>RESOLVE (S f addr -- ) SWAP ?CONDITION >RESOLVE ; \ ?>RESOLVE Resolve a forward Branch with Error Checking
: ?<MARK (S -- f addr ) TRUE <MARK ; \ ?<MARK Set up for a Backwards Branch with Error Checking
: ?<RESOLVE (S f addr -- ) SWAP ?CONDITION <RESOLVE ; \ ?<RESOLVE Resolve a backwards Branch with Error Checking
: LEAVE COMPILE (LEAVE) ; IMMEDIATE \ LEAVE and ?LEAVE could be non-immediate in this system,
: ?LEAVE COMPILE (?LEAVE) ; IMMEDIATE \ but the 83 standard specifies an immediate LEAVE, so they
\ both are for uniformity.
\ Extensible Layer Structures 01Oct83map \ \ Extensible Layer Structures 27JUL83HHL
: BEGIN ?<MARK ; IMMEDIATE \ These are the compiling words needed to properly compile
: THEN ?>RESOLVE ; IMMEDIATE \ the Forth Conditional Structures. Each of them is immediate
: DO COMPILE (DO) ?>MARK ; IMMEDIATE \ and they must compile their runtime routines along with
: ?DO COMPILE (?DO) ?>MARK ; IMMEDIATE \ whatever addresses they need. A modest amount of error
: LOOP \ checking is done. If you want to rip out the error checking
COMPILE (LOOP) 2DUP 2+ ?<RESOLVE ?>RESOLVE ; IMMEDIATE \ change the ?> and ?< words to > and < words, and
: +LOOP \ all of the 2DUPs to DUPs and the 2SWAPs to SWAPs. The rest
COMPILE (+LOOP) 2DUP 2+ ?<RESOLVE ?>RESOLVE ; IMMEDIATE \ should stay the same.
: UNTIL COMPILE ?BRANCH ?<RESOLVE ; IMMEDIATE
: AGAIN COMPILE BRANCH ?<RESOLVE ; IMMEDIATE
: REPEAT 2SWAP [COMPILE] AGAIN [COMPILE] THEN ; IMMEDIATE
: IF COMPILE ?BRANCH ?>MARK ; IMMEDIATE
: ELSE COMPILE BRANCH ?>MARK 2SWAP ?>RESOLVE ; IMMEDIATE
: WHILE [COMPILE] IF ; IMMEDIATE
When the interpreter is toodling along in compile state, compiling a colon definition by stowing pointers one after another (at the pointer here) into the definition of some word you're compiling, and it encounters an if, it sees that if is immediate, and so instead of stowing a pointer to if it just runs it immediately. The definition of if is compile ?branch ?>mark. compile is also an immediate word [correction, no, it's not, see below comment, though the following is still correct]; compile ?branch stows a pointer to ?branch into the colon definition being compiled, and then ?>mark writes a 0 into the entry following the ?branch and pushes true and the address of the 0 on the operand stack, at compile time, with the sequence true here 0 ,. The interpreter toodles along compiling the body of the if and eventually gets to, for example, then, which is also immediate, and is defined as ?>resolve, which overwrites the 0 into the address of the indirect-threaded code that will be compiled following the then. It does this with swap ?condition here swap !. The swap ?condition part aborts with an error if there isn't an unresolved if or similar on the stack to resolve, consuming the true, leaving only the address of the 0 that ?>mark had pushed. So then here swap ! overwrites that 0 with the current value of here.
?branch is a word written in assembly which does a conditional jump in the inner interpreter (the one that interprets the indirect-threaded code); when it's executed, it pops a value off the stack and checks to see if it's zero, and if so, it changes the interpreter's execution pointer ip (which is defined elsewhere as the register si) to the number stored in the threaded code following the pointer to ?branch. If, on the other hand, the value it popped was nonzero, it increments ip twice to skip over that number. (Note that Laxen's comment on ?branch is incorrect in that it reverses the sense of the test.)
All the forward jumps work in pretty much the same way: when you begin a control structure you call ?>mark to write a zero placeholder and push its address, and later on you "resolve" that placeholder by popping its address off the stack and overwriting it with the correct address. leave (break) and ?leave (if (...) break) work slightly differently, but mostly the same.
Backward jumps work the other way around: when you begin a control structure, as in begin, you call ?<mark to save the current address on the stack so that you can jump to it later, which ends up just being true here. Then, to actually compile the jump, for example in until or again, you call ?<resolve, which ends up just being swap ?condition ,—the , pops the jump target address off the stack and compiles it into the indirect threaded code, serving as an argument the ?branch or branch instruction compiled immediately before it.
begin ... while ... repeat is handled, as you can see, by treating the while ... repeat part as an if ... then with an unconditional jump back to the begin jammed in right before the then.
The most interesting one is Able forth
https://github.com/ablevm
which uses flow control to defer execution, aka quotations. I find using quotations instead of immediate modes easier to understand.
With both of these, they always compile expressions before executing them, so IF/THEN/ELSE can be used at any time.
Thanks for this expansion of the ideas involved. My question here is what does the COMPILE word do? What is the state of the VM / compiler / repl or whatever after it encounters that word?
That "IF" is implemented in terms of other more fundamental operators is fine, but can we write a program that just uses the fundamental operators that demonstrates IF-like behavior but doesn't introduce any intermediate words?
Actually compile is not an immediate word (at least in F83). I was wrong about that. Here's the F83 definition:
: COMPILE (S -- ) R> DUP 2+ >R @ , ; \ COMPILE Compile the following word when this def. executes
This takes its return address (which points to the following word in the colon definition that called it), dups it, adds 2 to it, and puts that back on the return stack as its new return address. Then, it fetches from its original return address with @ (thus getting the address of the word that followed it in the colon definition, such as ?branch in my if example above) and compiles it with , into whatever is currently being compiled. Then, when it returns, having added 2 to the return address means that we don't actually execute ?branch or whatever; we've skipped over it.
So it doesn't change the state of the interpreter at all!
I think you're asking if you can use things like ?branch usefully without writing any immediate words. In some sense I think the answer is yes in F83 but no in standard Forth. I think you can put a code sequence like ?branch [ here 0 , ] into a colon definition to do what if does, and then later on say [ here swap ! ] to do what then does. I just typed this definition into F83, and it seems to work†:
: is3 3 = ?branch [ here 0 , ] ." yes" [ here swap ! ] ;
You could sort of think of if and then as being macros for ?branch [ here 0 , ] and [ here swap ! ] respectively (although I'm omitting the checks they use for proper control structure nesting).
On the other hand, this is only possible because [ is an immediate word, and because ?branch is exposed, and happens to take an absolute address in the next word in the colon definition (as opposed to a byte delta or something). As it happens, exactly the same definition of is3 appears to work in GForth 0.7.3 and PFE 0.33.71, but it definitely will not work on, for example, any native-code-compiling Forth.
The standard way to invoke things like ?branch is using if, while, and so on. And you don't have to define any immediate words to do that, either.
In assembly language, the thing that plays the role of these definitions like if and then and ?<resolve is the assembler's symbol table and relocation logic, which goes back and changes your jump instructions (etc.) to jump to the places where it finds that your labels have been defined to point. Typically this involves things like hash functions, hash table collision resolution, various operand encodings for things like short jumps and long jumps, and so on.
Although you can write an assembler that does all this in an afternoon, I don't think you will ever find an assembler whose implementation of all this functionality is easier to understand than the above 30 lines of code. It might be easier to understand per line of code but there will be a lot more lines of code to understand, like 10× or 100×.
Hint: IF, THEN, and ELSE are words that are partially evaluated at compile time.
IF remembers its own location and reserves space for a jump; THEN compiles a conditional jump if NOT true to its location, in the place where IF was, unless there was an intervening ELSE, in which case it will compile such a conditional jump to ELSE's location at IF, and an unconditional jump to then just before ELSE. So a full use might look like:
: TEST > IF ." greater" ELSE ." less or equal" THEN ;
In my opinion, a language that requires a programmer to have a "revelation" to understand basic control flow is not a language that is useful or practical for solving real world problems.
I would prefer to write in assembly language than write in Forth. Which is what I have done with one of my current projects.
With assembly language, there is a good chance that a random person with some minimal programming skills would understand my program if I were hit by a bus. With Forth, I think the chances of that are close to zero.
If you're coding, you don't have to understand how to implement control flow. The average C programmer hasn't a clue how the underlying control flow is implemented. It's an _implementor_ of an interpreter or compiler who needs to understand this. Forth is no different from C or any other language in this regard, except that, in Forth, control flow can be implemented directly rather than relying on the compiler or interpreter to understand them.
Immediate words are essentially a kind of macro, if it makes things easier for you.
It's a revelation to understand how basic control flow is implemented in any compiler. From your described preference to not learn things that aren't generally known, it's a safe bet that you don't understand CPS or SSA either, or know what a basic block is.
I remember, many years ago, when I was learning programming. When I grokked recursion, it was a revelation to me. Could I be a programmer without that revelation? Yeah, kind of, but I'd be a lesser one.
Effectively IF compiles a 0= ie. If false and then a dummy target address. THEN (aka ENDIF) compiles the real target address over the dummy one, which is the address after THEN.
A million times this. The syntax is not difficult to see, but the action seems mysterious.
The article gives an example
> : buzz? 5 mod 0 = IF ." Buzz" THEN ;
Seems to work okay.
What about immediate mode?
> 10 5 mod 0 = IF ." Buzz" THEN ;
action is not a function
Well, I guess that does it for me.
Factor, another stack-based languages, has a more legible version of this, where you can push an anonymous lambda onto the stack. As I recall from my days of programming HP-48's, that used a similar mechanism. (Not checking my syntax here)
> 5 mod 0 = << "buzz" print >> if
Would have a similar effect. Each entry makes sense -- the << switches from immediate mode to store mode (or some similar concept), and everything ends up on the stack. "If" is just a function that takes a boolean and a closure:
Forth control structures don't work in interpret state because control structures involve executing code out of order: jumping from the end of a loop back to its beginning, etc. In interpret state there's nowhere to jump to. So you have to put control structures inside a colon definition for them to work. Also true of strings in traditional Forths, but GForth just dynamically allocates some memory and leaks it instead.
The hard part I think is grokking the fact that the FORTH can compile and interpret inside the same definition. Also one must understand the operation of the Forth primitives HERE and comma (,)
I will take a run at explaining IF ENDIF
(endif is the Fig Forth term, used here to avoid confusion)
?BRANCH is an instruction in the virtual machine. It jumps if top of stack=0 .
The offset (or address)that it jumps to is the memory word right after the ?BRANCH token. Like this: <?BRANCH><number>
Forth definition of IF
: IF COMPILE ?BRANCH HERE 0 , ; IMMEDIATE
At compile time IF "compiles" the token for ?BRANCH but then interprets "HERE 0 ,"
(IF is an IMMEDIATE word that executes even if the compiler is turned on)
HERE is like $ in Assembler, ie: the address where code is being laid down.
It is simply left on the data stack. HERE is the address where the <number> will be stored... later.
0 is a zero, that is pushed onto the data stack.
"Comma" (,) pops the zero and puts it in memory address HERE but! it advances the system memory pointer 1 integer width.
The zero is now a place holder in memory to be filled in by ENDIF.
: ENDIF( addr -- ) HERE OVER - SWAP ! ; IMMEDIATE
ENDIF needs that address left behind by IF shown in comment as addr.
ENDIF gets the new value of HERE which of course is different because we will have compiled some code after the IF keyword.
All we need to do is do NEWHERE-OLDHERE to get the offset for ?BRANCH.
That is covered by the forth code ( oldhere-on-stack) HERE OVER -
This will make the data stack be: ( OLDHERE offset )
If we do a SWAP we just need the store operator '!' to put the offset into memory.
For the morbidly curious here is the definition of ELSE. :-)
Forth was invented around 1970 for controlling equipment in an astronomical observatory, running on a PDP-11, a 16-bit computer with up to 64 Kbytes of memory. Its heyday was the 1970s and 80s, when it was mostly used for
small embedded systems on 8- or 16- bit processors with 8 kb -- 64 kb of memory.
It was possible to run an entire Forth development system along with the application on these small targets without resorting to a bigger computer for cross-development.
The usual alternative to Forth on those systems was assembly language.
I was dropped into one such system after it failed after like 20 years and learned forth on the fly while managers breathed down my neck lol. Not a fun experience, and it took about 3X as long as I thought it would take, so Forth is not my favorite language, but I do see why it was useful at the time, and as an exercise in a way of thinking about languages rather than the mode I usually operate in c/c++/rust/little javascript
Forth started as Chuck Moore’s solution to the problem of how to bring up an interactive programming environment on hardware with limited memory. The base of the system used a small number of primitives written in assembler or machine code upon which more complex functions were built. The genius of the system was that you could easily bring it up on different hardware by translating the primitives, which was quite helpful at a time when software was frequently customized to the hardware (which itself was not as standardized as today). Nowadays Forth is probably most useful on embedded systems.
> Nowadays Forth is probably most useful on embedded systems.
Nowadays almost nothing is written in Forth. That's the problem with Forth. Even on 8-bit Arduino microcontrollers with 2kiB of RAM, we write programs in C++ (with a little bit of C, on top of hand-coded AVR assembly).
The Starflight role-playing game for DOS [0] was written in its own Forth dialect. Even today, it remains one of the games with the strongest Star Trek feeling.
Yes, my comment came across a bit harsh, and it’s fine to pick up a few negative karma points. But I keep seeing Forth posts every two weeks where everyone has just built yet another interpreter.
Actually I did a few projects with Forth and I find it very cool:
I like that way of thinking about it - now I want my negative karma points separated into their own bucket even if the final summary is presented out, I think its an interesting signal.
Dang & Co. doubtless see such things - but I'd bet it'll never be shown to regular users. Too little utility, vs. too tempting for a small minority to game in unhealthy ways.
Additionally, check basis/ and extra/ on https://github.com/factor/factor. You will find A LOT of goodies there. They even have a framework for Discord bots using latest Discord API version, if you are into that. In any case, you really ought to check, there are too many things to list here.
As someone else pointed out, it is 0.100 which was released not that long ago, and if you compile now, it is 0.101 anyways, but regardless of their versioning, it has been actively maintained ever since, they just did not bump the version for a long time.
I didn't say it was forth, I said it was concatenative.
Forth itself is hard to categorize since it refuses to standardize but we all know what it looks like, I'd say its a low level language/VM that manages everything through stacks (usually 2) there's forthlike languages and also concatenative languages. concatenative languages can be far removed from forth, I don't mean that the shell itself is concatenative, but only the shell pipelining aspect, which you can imitate in any forth. take an object and keep passing it to subsequent functions without popping that know s how to handle that object, that's a shell pipeline to me, all of unix can be passed the /dev/std* objects and they can all modify it and pass it along to the next function/program.
Well, I agree that Forth is concatenative (like stack languages in general), and so are shell pipelines.
But you said, "Just because you don't specifically use forth does not mean forth is dead," and unless I misread your intent, you included your shell-scripting point on the theory that it was relevant to that question: whether or not Forth was dead. The implication seemed to be that, as long as people were using shell pipelines, Forth wouldn't be dead. But that's wrong; Forth could be totally dead while other forms of concatenative programming were alive and well.
BASIC, especially the Microsoft dialect, became the dominant language for microcomputers because it would fit in a tiny space, e.g. 4k. For that matter it was big in the minicomputer age because it was used in multitasking systems that weren't that big. Circa 1980 my high school had a PDP-8 which had three terminals and could run a three user BASIC with just 32k 12 bit words.
There weren't a lot of languages which would fit in a tiny space, but FORTH was one of them. Like LISP it's a language where you can (1) implement the language without any kind of recursive parser and (2) write control structures in the language itself because each "word" in forth has both a run-time and compile-time interpretation.
Original BASIC did not fit into tiny space, that is why while Dartmouth BASIC always compiled into machine code before execution, everyone that learnt BASIC in 8 bit systems thinks it was originally interpreted and compilers only came later, which was the compromise to make it fit into a few KB.
Jupiter ACE had its followers, and it was common to see ads on Your Sinclair and similar magazines for ROM replacements using Forth instead of BASIC.
That PDP-8 BASIC was a miracle of shoehorning as was everything else on the PDP-8.
My favorite minicomputer BASIC that I got to use was on RSTS/E on the PDP-11 which had split 64k address spaces for code and data and used fairly advanced compilation techniques. Roughly the RSTS/E experience was like having your own Apple ][ but with a hard drive and a little more oomph. I grew up in New Hampshire right next door to DEC's headquarters in Massachusetts and there were DEC minicomputers everywhere.
Microsoft had a compiled BASIC (like run a compiler, not compile interactively like Microware's BASIC09) on CP/M for the Z-80 which was a much better compiler target than the popular 6502.
I wrote a FORTH for the TRS-80 Color Computer using the OS-9 operating system which had maybe 2000-3000 lines of assembly code. FORTHs at the time often did block I/O directly to the disk but OS-9 had an API to access files that was pretty similar to Unix and my FORTH exposed that.
I don't agree at all. They do have something in common: they're stack-based. But what they don't have in common is everything else. RPL is a dynamically-typed, bounds-checked, memory-safe, garbage-collected language similar to PostScript or Python. Forth is an untyped, unsafe language with arbitrary compile-time compilation and without even a heap, traditionally. It's the minimal veneer on top of assembly language to give it arbitrary compile-time metaprogramming and nested expressions and control structures. RPL doesn't even have compile-time metaprogramming at all.
These two languages represent diametrically opposed approaches to programming language design.
Bitcoin’s scripting / smart contracting language is Forth.
Were there anything in the crypto space is actually solving a problem is up to your own biases and prejudices. But if you pick one thing as actually trying to solve a real problem, payments over lightning is probably that. Lightning, at its core, is a state machine composed of Forth spend scripts.
No, Bitcoin Script is not Forth. Bitcoin Script is designed to guarantee termination, so no Turing-complete programming language was permitted. Like BPF, Bitcoin Script doesn't have subroutine definitions or backward jumps, so each opcode executes at most once.
They're akin to Forth, but they're not Forth, and they're not implemented in Forth.
By contrast, assembly language underpins most software people run today: perhaps it's written in Python, which is interpreted by CPython (using a bytecode which is considerably more Forthlike than Wasm, incidentally), which is written in C, which is usually compiled by GCC or LLVM to textual assembly language in order to generate the executable.
Forth really shines in microcontroller or esoteric computation machines, but further more, people don't realize their C compilers are billions of dollars of development, and they'd never be able to do it in the first place. A Forth on the other hand can be developed in a month (I'm being honest-to-god realistic here. A lot of people would say "a weekend", but let's be real, anything useful will be more than a weekend. I'm trying to convince you this isn't bullshit :)).
If you have any more questions let me know. I was bit by Forth about 2 years ago but had read about it long ago when I was like 16 and passed it off as too hard. It's the same shit as when FP took off: it's a different mental model, so it will take time to morph your mind.
Edit: read the larger comment below, and they are totally correct:
> most Forth tutorials today are written by people who don't really know Forth
One day I might write a small Forth novella teaching how to actually think about Forth programs. In these 2 years I've had to just practice and write programs to see common patterns or idioms - kind of exactly like when I was learning Haskell years ago.
I don't think it takes billions of dollars in development to write a C compiler, but it does seem like everyone's first C compiler does take at least a year, so US$100k is a good ballpark. I agree that Forth is about an order of magnitude easier. You probably shouldn't consider https://github.com/kragen/stoneknifeforth to actually be a Forth (it's not interactive and doesn't have immediate words) but it did compile itself into a working ELF executable and it did take me almost exactly a month to write (October 02008, specifically). I could probably write a real Forth now in a month.
I would be very excited to read your small Forth novella. Or your small Haskell novella.
Forth is very enjoyable, and it's always exciting to see someone new discovering it, but it has three big problems.
The first is a technical problem: the forte of Forth is self-hosted developer tooling in restricted environments: say, under 256KiB of RAM, no SSD, under 1 MIPS, under 10 megabytes of hard disk or maybe just a floppy. In that kind of environment, you can't really afford to duplicate mechanism very much, and programmers have to adapt themselves to it. So you end up using the same mechanism for fairly disparate purposes, with the attendant compromises. But the results were amazing: on an 8080 with 64KiB of RAM and CP/M you could run F83, which gave you virtual memory, multithreading, a somewhat clumsy WYSIWYG screen editor, a compiler for a language with recursion and structured control flow, an assembler, and a CLI and scripting language for your application.
That chip's resources are pretty limited. In a money economy, we measure resources in money; the reason to use a chip with limited resources is to avoid spending money, or to spend less money. That chip costs US$7.40. For US$5.59 you could instead get https://www.digikey.com/en/products/detail/stmicroelectronic...: 100 megahertz, 512MiB of flash, 256KiB of RAM, 50 GPIOs, CAN bus, LINbus, SD/MMC, and so on. And according to Table 33 of https://www.st.com/content/ccc/resource/technical/document/d... it typically uses 1.8μA in standby mode at 25° at 1.7V. That's more than the MSP430's headline 0.1μA from https://www.ti.com/lit/ds/symlink/msp430f248.pdf but it's still low enough for many purposes. (A 220mAh CR2032 coin cell could theoretically supply 1.8μA for 13 years, but only has a shelf life of about 10 years, so the STM32 uses less than the battery's self-discharge current.) That is to say, the niche for such small computers is small and rapidly shrinking.
Also, while the microcontroller might have only 2KiB of RAM, the keyboard and screen you use to program it are almost certainly connected to a computer with a million times more RAM and a CPU that runs a thousand times faster. So you could just program it in C or C++ or Rust and run your slow and bloated compiler on the faster computer, which will generate more efficient code for the microcontroller. The cases where you have to build the code on the target device itself are few and far between.
Forth was designed to make easy things easy and hard things possible. The second problem is a social one: as a result of the first problem, the people who used Forth for that have mostly fled to greener pastures. The Forth community today consists mostly of Forth beginners who are looking for an artificial challenge: instead of making hard things possible, they want to make easy things hard. There are a few oldtimers left who keep using Forth because they've been using it since it did make hard things possible. But even those oldtimers are a different population from Forth's user base in its heyday, most of whom switched to C or VHDL. Most of us have never written a real application in Forth, and we've never had the religious-conversion experience where Forth made it possible to write something we couldn't have written without Forth.
The third problem is also a social one: as a result of the second problem, most Forth tutorials today are written by people who don't really know Forth. I've only briefly skimmed this tutorial, but it seems to be an example of this. For example, I see that it doesn't explain immediate words, much less when to not use immediate words. (If it's ever easier to write something in Forth than in C, it's probably because you can define immediate words, thus extending the language into a DSL for your application in ways that are out of reach of the C preprocessor.) And it doesn't talk about string handling at all, not even the word type, even though string handling is one of the things that Forth beginners stumble over most when they start using Forth (because it doesn't inherently have a heap).
So, I hope the author continues to learn Forth, and I hope they extend their tutorial to cover more aspects of it.
Forth has always intrigued me as one of those languages (APL and Mumps also come to mind) that appears to have a superpower, for example expressing somewhat complex systems compactly, while at the same time also being flawed enough so that this superpower only appears to be applicable to a small niche.
Given the somewhat sorry state of (lack of) expressiveness and accompanying bloat in programming in general, it would be really interesting to see if that is inevitable, so if the superpower is in fact also the flaw, or if it's possible to extract the superpower from the flaw.
The way you express Forth's superpower is one I haven't seen so far and seems to point a possible way:
> So you end up using the same mechanism for fairly disparate purposes, with the attendant compromises.
Can you tell more about those mechanisms that are used for disparate purposes?
> If it's ever easier to write something in Forth than in C, it's probably because you can define immediate words, thus extending the language into a DSL for your application in ways that are out of reach of the C preprocessor.
So compile-time metaprogramming is not just available as an add-on, but very much "how things are done"?
I agree about Forth being a fatally flawed language with superpowers, although I think we could easily have ended up in a world where Forth played the role of C, which has its own fatal flaws.
Yes, compile-time metaprogramming is very much "how things are done". This is simplified by not having syntax, but I don't think they're inseparable; you could imagine building up a compiler in the same way from an almost-as-minimal base using something like https://jevko.org/, S-expressions, a Prolog-like extensible infix parser, or a Smalltalk-like non-extensible infix parser with an open set of operators. I think most of these would be improvements. PostScript has an only slightly more elaborate syntax than Forth, but uses Smalltalk-style lightweight lambdas (called "quotations" in several other stack languages) to provide control-flow operators through runtime metaprogramming instead of compile-time metaprogramming.
As for "mechanisms used for disparate purposes", for example, the outer (text) interpreter in typical Forths plays the role of the Unix shell, the C-level systems programming language, the assembler syntax, and the user interface to applications such as, traditionally, the interactive text editor. And in https://news.ycombinator.com/item?id=45340399 drivers99 reports using it to parse an input file. The Forth language is not a very good shell command language, not a very good high-level programming language, and not a very good text editor user interface language, but it's adequate for all of these purposes.
The dictionary, similarly, serves to hold definitions for all those purposes. But it also allocates memory in a region-allocator-like way—a byte at a time, if need be. You can use the same words like , to store data into the dictionary directly, in interpretation state:
create myarray 3 , 4 , x ,
Or in a constructor:
: throuple create , , , ; 3 4 x throuple myarray
In traditional Forths like F83, , is also the mechanism for adding an xt to a colon definition, but in ANS Forth compile, was added as a possible synonym which would also permit writing Forth code that was portable to non-threaded-code implementations. https://forth-standard.org/standard/core/COMPILEComma
The operand stack serves to pass arguments and return return values, as well as to hold temporaries, but you can often use it to store a local variable as well, and space on it is dynamically allocated, so it's possible to use it to pass or return variable-sized arrays by value. At compile time, it's used to keep track of the nesting of control-flow structures.
The return stack serves to store return addresses, but also to store loop counters or maybe another local variable. And return-stack manipulation provides you with a relatively flexible form of runtime metaprogramming for things like stackless coroutines, shallow-bound dynamic scoping, and exception handling. Here's an implementation of dynamic scoping (which cannot be used inside a do loop or when you have other stuff on the return stack):
0 value old 0 value where : co 2r> >r >r ;
: let! dup to where where @ to old ! co old where ! ;
Example usage:
decimal : dec. 10 base let! . ;
This temporarily sets base to 10 before calling ., but then restores base to whatever value it had before upon return. A better implementation that uses the return stack instead of old and where to save and restore the values is
(This is probably not very understandable, but I've written an 1800-word explanation of it elsewhere which you can read if you like.)
Pointer arithmetic and integer arithmetic are the same operation, as they are in most untyped languages. This is different from C, where they are done with the same operators which are implemented differently for integers and for different types of pointers.
The "filesystem" in traditional Forths simply exposes the disk as an array of 1024-byte blocks which could be mapped into memory on demand. Conventionally you would divide your code into 1024-byte screenfuls, each space-padded out to 64-character lines, 16 of them. In effect, each screen was a different "file", identified by number rather than name. It's reasonable to argue that this is not a very good filesystem, and not a very good format for text files, but to implement any filesystem on top of a disk or SSD, you need a layer that more or less provides that functionality; all that's required to make it usable for code blocks is to use 1024-byte blocks instead of 128-byte or 512-byte or whatever.
Multitasking in traditional Forths is cooperative. In some sense this eliminates the need for locking; for example, to ensure that the block buffer you've mapped your desired block into doesn't get remapped by a different task before you're done using it, you simply avoid calling anything that could yield. Unfortunately, Forth doesn't have colored functions, so there's no static verification that you didn't call anything that calls something that yields. Cooperative multitasking is sort of not very good multitasking (since an infinite loop in any task hangs the system) and not very good locking, but it does serve both purposes well enough to be usable.
Scheme is sort of like this too; famously, Scheme's lambda (roughly Forth's create does>) is semantically an OO object, a statement sequencing primitive, a lazy-evaluation primitive, etc., while S-expressions are a similar syntactic cure-all, and call/cc gives you multithreading, exception handling, backtracking, etc. See https://research.scheme.org/lambda-papers/. In practice a small Lisp is about the same amount of code as a small Forth.
BTW, I still have a paper of yours in my queue to read!
Well said. I love Forth an I think it’s worth learning, but almost nobody programs workstation-level applications with it, and as you say, even in embedded environments the level of resources have grown such that there’s very little reason to choose Forth anymore. Which makes me a bit sad because Forth is brilliant.
Reading lines from a file and handling the strings in memory is what made me stop using it after a 3rd day of advent of code one year. I simply couldn't find a good solution, without a massive excursion into how to use the pad. Such a supposedly simple thing like reading a complete line from a file, yet it stopped me completely. Of course I could have "cheated" and put the input right into the program, but I wanted to learn Forth, so I thought I should be able to do this ...
Later I read, that GForth 1.0 should have more string handling words, but then I already had lost hope to find an easy solution. Don't get me wrong, learning the little bit of Forth that I did learn, it was quite interesting, and I would have liked to progress more. I think I also lost hope, because I couldn't see how this stack system would ever be able to handle multi-core and persistent data structures. Things that I have come to use in other niche languages. Also that some projects/libraries are one-man shows/bus factor 1, and the maintainers have stopped developing them. They are basically stale and made by people, which significantly more understanding than any beginner will have for a long time.
I guess to really learn it, one has to read one of the often recommended books and have a lot of patience, until one gets to any parts, where one learns simple things like reading a file line by line.
I think mostly learning Forth is like learning any other programming language (or, better said, programming environment): you learn by doing it. Books can be a useful complement to practice, but practice is how you learn to do things. You can't learn to do things by reading.
As for string handling, in my limited experience, string handling in Forth is a lot like string handling in C; you have to allocate buffers and copy characters between them. memcpy is called move, and memset is called fill. You can use the pad if you want, but you can just as well create inbuf 128 allot and use inbuf. There are two big differences:
1. Forth doesn't have NUL-terminated strings like C does, because it's just as easy to return a pointer and a length from a subroutine as it would be to return just a pointer. This is generally a big win, preventing a lot of subtle and dangerous bugs. (Forth is generally more error-prone than C, but this is an exception.)
2. Forth unfortunately does have something called a "counted string", where the string length is stored in the byte before the string data. You can create them with C" (https://forth-standard.org/standard/core/Cq), and Forth beginners often wonder whether to use counted strings. The answer is no: you should never use counted strings, and they should not have been included in the standard. Use normal strings, created with S" (https://forth-standard.org/standard/core/Sq), unless you are calling word or find. https://forth-standard.org/standard/rationale#rat:cstring goes into some of the history of this.
If you want to allocate strings on the heap, which is often the simplest way to handle strings, malloc is called allocate, realloc is called resize, and free is called free: https://forth-standard.org/standard/memory
With respect to multicore and persistent data structures (I assume you mean FP-persistent, as in, an old pointer to a data structure is a pointer to the old version of the data structure), stacks aren't really related to them. Each Forth thread has its own operand stack and its own return stack (and sometimes its own dictionary), so they don't really create interactions between different cores.
I think there is another problem for me: The last time I have done any manual memory management a la C, before using Forth was some >10y ago. And immediately the next question would pop up in my head: "What if that line is longer than 128 bytes? Is there no general function to read a whole line?" And I guess then I would reinvent the whole machinery to read a whole line, determining at which byte the newline appears. And then I would have doubts like: "Uh, but what if someone puts some unicode characters in there?". While actually all I wanted was to read a single file, to get working on an AoC puzzle.
So I think I lacked the manual memory management basics as well at that point, and any haphazardly implemented hack like "assume the longest line is at most 128 ASCII characters long" would not have made me happy with my code.
Well, to bake an apple pie from scratch, you must first create the universe.
In any programming language, to read an arbitrarily long line into memory, you need an arbitrarily large computer, so your software may need to pause to convert more Temu orders, continents, asteroids, or star systems into computronium. If you're not willing to go that far, you have basically two choices:
1. Process the line in a streaming fashion rather than holding all of it in memory at once.
2. Only handle lines up to some maximum length.
If you select option 2, the only remaining questions are:
2a. What is that maximum length?
2b. What happens if you hit it?
Maybe 128 bytes is not a limit you're happy with, but it's just as easy to use 1048576 or 1234567890. Your code may be easier to understand and easier to get right if you use a dynamically-allocated string type (I suggest studying stralloc from qmail 1.03), but don't fool yourself into thinking that that means there's no limit on input line length. Dismayingly often, the answer to 2b in that case is "Linux starts thrashing and becomes unusably slow until you reboot it."
(If your input is UTF-8, the line-reading function doesn't have to worry about whether the bytes represent Unicode characters or not, because byte 0x0a will never occur inside a non-ASCII character.)
The point is, I don't want to spend lots of time solving these essential problems, when I actually want to learn the language through solving puzzles. It seems, that Forth does not lend itself to be learned that way, since even very basic things are not provided and require in-depth knowledge of Forth and developing manual memory managed solutions to problems, that are solved in almost every programming language in their standard libraries. If I used Python it would literally be 2 lines of code, and with file.readlines() or so, I don't have to think about how long a line can be and then develop ad-hoc brittle half-solutions.
Perhaps readlines() has a limit somewhere too though. Just not aware of it and so far have not needed to deal with that kind of thing. But then again Forth and Python are 2 very different languages and act on another level of abstraction in many cases, so maybe that comparison is not fair.
Forth was sort of designed by and for people who did want to solve these essential problems anew for each application. Chuck Moore claimed many times that a tailored ("ad hoc") solution that solves only the part of the problem you need to solve for a particular application would be 10× smaller and simpler than a generalized solution that has to balance the needs of all possible applications. He considered it preferable to not have a lot of library code in your application to solve problems you don't actually have. Maybe your ad-hoc solution is brittle, but it's brittle precisely in ways you know about, not in ways you don't.
But you don't have to use Forth that way just because Chuck did. You can totally use a generalized string library in Forth. I don't know which one to recommend, but http://turboforth.net/resources/string_library.html seems to be one possibility.
You can be sure that Python's file.readlines()† will have trouble if you try to read a line that is much longer than your RAM size.
You can get pretty far with just built-in standard functionality, though:
Gforth 0.7.3, Copyright (C) 1995-2008 Free Software Foundation, Inc.
Gforth comes with ABSOLUTELY NO WARRANTY; for details type `license'
Type `bye' to exit
128 constant len create buf len allot ok
: greet ." Name? " buf len accept ." Hello, " buf swap type ." !" ; ok
greet Name? Zelphir Hello, Zelphir! ok
† ever since Python 2.0, I'd recommend using list(file) instead of file.readlines(), or just iterate over the file directly, like [line.strip() for line in file if line.startswith('zel')]
One year (2022) I could see, on an early problem (day 2), that I could define a handful of words in forth such that I could execute the (modified) input file itself as code (there were only 9 possible combinations since it was rock-scissor-paper, although I did have to alter the input by removing the spaces first, like "A X" was changed to "AX") to get the answer. I defined words that matches the 9 inputs and had those do whatever the problem said to do. https://adventofcode.com/2022/day/2
> Most of us have never written a real application in Forth, and we've never had the religious-conversion experience where Forth made it possible to write something we couldn't have written without Forth.
Perhaps someone will upload some Forth source code for a few larger systems e.g. "Fmacs", an Emacs-like editor written in mostly Forth with Forth instead of ELISP being the embedded language.
Then it would be interesting to compare speed and readability (important today and every day) as well as memory requirements in RAM and on disk etc. (not so important anymore, used to be very important in the past).
I had a look at the little Forth-based operating system's source code and of course couldn't comprehen much, which is obvious because looking at the code doesn't tell you, you need to imagine what's going on with the stack.
Very much this. Even when programming for constrained environments, it's almost never necessary to self-host anymore. It's easy to use host-side tools to crunch code down to something that'll work on whatever the target is.
From a practical standpoint, one of the few modern uses where FORTH shines is as a REPL for new chips/SOCs so you can play around with the hardware and see how things actually work/debug the databook.
Sure, I git cloned my copy from https://github.com/ForthHub/F83, and it runs fine under DOSBox. If you have Git and DOSBox installed, I think you can just type
git clone https://github.com/ForthHub/F83
cd F83
dosbox .
f83
: fish 0 do i . ." fish" cr loop ; 7 fish
>> The thing that separates Forth from most other languages is its use of the stack. In Forth, everything revolves around the stack
I mean, that's pretty much every language. The main difference is that the programmer's access to it is unconstrained by things like method call definitions.
Unlike most languages, Forth has two stacks. It sounds trivial, but it changes many things. It allows for a leaner call convention. With a single stack, every function call has to "shovel forward" its arguments over the function return address, where Forth "glides" through its arguments, making function calls significantly lighter.
Like Forth, Ada has two stacks. Unlike Forth, which uses two stacks to simplify the language, Ada uses two stacks to complexify the language. This generalizes to other language features.
Ada's auxiliary stack is used to permit the returning of runtime-variable-sized objects from subroutines, which is also a thing you can use the operand stack for in most Forths.
Most languages don't have an explicit stack, and even their implicit stack is only for subroutine calls. If you're not making subroutine calls, your compiled code might not access the stack at all. So, for example, here's the strlcpy function from OpenBSD, lightly edited:
size_t strlcpy (char *dst, const char *src, size_t siz) {
register char *d = dst;
register const char *s = src;
register size_t n = siz;
if (n != 0 && --n != 0) {
do { if ((*d++ = *s++) == 0) break; } while (--n != 0);
}
if (n == 0) {
if (siz != 0) *d = '\0';
while (*s++)
;
}
return(s - src - 1);
}
GCC 12.2.0 compiles this to the following 18 ARM instructions, with -mcpu=cortex-a53 -Os -S:
If you're not familiar with ARM assembly, I'll tell you that nothing in this entire function uses the stack at all, which is possible because strlcpy doesn't call any other functions (it's a so-called "leaf subroutine", also known as a "leaf function") and because ARM, like most RISCs, puts the subroutine return address in a register (lr) instead of on the stack like amd64, or in the called subroutine like the PDP-8, which doesn't have a stack at all. And the calling convention puts arguments and return values in registers as well. So the function can just move data around between memory and registers and decrement its loop counter and increment its pointers without ever touching the stack.
FORTRAN up to FORTRAN 77 didn't support recursion, including indirect recursion, so that you could implement it without a stack.
By contrast, in Forth, instead of registers you use the operand stack. For loop counters you use the return stack. Sometimes you can use the operand stack instead of variables as well, although I think it's usually a better idea to use variables, especially when you're starting to learn Forth—it's much easier for beginners to get into trouble by trying too hard to use the stack instead of variables than to get into trouble by trying too hard to use variables instead of the stack.
Glad to see Forth on HN today!
For anyone who likes playing with small experimental projects, I once made a minimal, esoteric canvas colouring language inspired by Forth and Tixy: https://susam.net/fxyt.html
This is fun!
I was going to try to draw a circle but was missing sin/sqrt. Then I thought of using a lookup table but got stumped.
Do you have any pointers for drawing a circle?
I'm looking at demo #4 (https://susam.net/fxyt.html#XYpTN1srN255pTN1sqD) to see where the circular shapes are coming from.
Have you seen Forth Haiku? https://forthsalon.appspot.com/
doesn't need to be accurate, could do something like this (distance + treshold) :
https://susam.net/fxyt.html#XN128dXN128dpYN128dYN128dpsN4096...
smaller with dup :
https://susam.net/fxyt.html#XN128dDpYN128dDpsN4096lN255pC
circles pattern : https://susam.net/fxyt.html#XDpYDpsN8qN3riN255pC
PS: fun tool !
Oh, thanks!
X^2 + y^2 > z^2 ? 1 : 0
Was also gonna jump in with the old way of doing circle boundaries, which can be done all integer: https://en.m.wikipedia.org/wiki/Midpoint_circle_algorithm
Very cool! It would be even better if you had a Library of preset demo programs for people to hack and see the power of your tool
Edit: I saw them on GitHub. But I've also seen some tools that put them in the main interface. That would be an improvement IMHO. Great work!
Thank you! Glad you liked it! There are a few demos at the bottom of the help screen, which can be invoked by typing '?'.
You are right that that they could be better linked directly from the main interface.
In any case, here are the direct links to the demos available in the help screen:
https://susam.net/fxyt.html#XYxTN1srN255pTN1sqD
https://susam.net/fxyt.html#XYaTN1srN255pTN1sqN0
https://susam.net/fxyt.html#XYoTN1srN255pTN1sqDN0S
https://susam.net/fxyt.html#XYpTN1srN255pTN1sqD
https://susam.net/fxyt.html#XYN256sTdrD
Community demos are available here:
https://susam.github.io/fxyt/demo.html
For those who haven’t seen it before, Jones Forth is a wonderful implementation written in literate programming style.
It’s well worth reading through, even if you don’t know any assembly.
[1] https://github.com/nornagon/jonesforth/blob/master/jonesfort...
This is a great resource and running in the browser is great for fast feedback. Thanks for sharing!
I just started learning Forth a month or so ago, and I found this video from Andreas Wagner[1] fun to watch.
If anyone goes through OP's book and find yourself wanting to see Forth in action, I recommend the video.
[1]: https://youtu.be/mvrE2ZGe-rs
This has showed up here a few times before (example):
https://news.ycombinator.com/item?id=10634918
I'm always interested in hearing people's reactions to Forth though and every now and then you get a cool new story on these threads, so I'm not complaining.
Right. And once again, you’ll also notice that no one is actually coding anything useful in Forth.
Well, I don't know if this qualifies as useful, but I wrote a minimal roguelike in one page of Forth last year: https://asciinema.org/a/672405
vdupras is here in the comments today. He's written a self-hosting interactive operating system in Forth, including a FAT16 filesystem and everything, and a compiler for a useful subset of C: https://duskos.org/
As I like to say: "C is a language that solves a million problems. Forth is a million languages that solve almost nothing." :-P
I've been reading about Forth for 30-40 years. The dual stack is easy to understand. My problem is that I cannot see how control flow works in Forth, e.g. a simple if-then-else.
I think that something as fundamental as an if-then-else should be obvious in a useful language. Heck, it's obvious in assembly language. But not in Forth.
It's funny that you say that, because from my point of view, control flow in Forth is one of its strong points over assembly language, because it has properly nesting control-flow structures. The syntax is a little strange; the literal translation of
is (untested) when what you'd normally expect is something like but that's sort of a question of RPN. At least else comes where you expect it, even though that makes then even stranger; we can translate literally as (untested) Now, if you were comparing Forth to Lua or C here, I would agree: this is far less obvious, in the sense that it's completely unfamiliar and requires you to learn Forth's idiosyncratic way of writing things. But in assembly language? GCC generates, in context, the following assembly code for the C if-else statement above: This is using the flags from a preceding equality comparison, and the branch target labels are earlier in the enclosing loop. You can not tell me that this is "obvious" if you don't know ARM assembly!From a certain point of view, Forth is just what you get if you take assembly language and look for the simplest way to add properly nesting expressions, properly nesting control structures, subroutines with arguments and return values, arbitrary compile-time computation, an interactive debugging environment, a scripting language, disk storage, and multithreading.
I kinda know how it works at the user-level, I meant to write that I don't understand how control-flow is implemented in Forth. I say more about that in my reply to a sibling comment: https://news.ycombinator.com/item?id=45334556
Oh! I see. I've commented there.
> My problem is that I cannot see how control flow works in Forth, e.g. a simple if-then-else.
What made it click for me was http://www.exemark.com/FORTH/eForthOverviewv5.pdf, specifically sections 2.3 "Loops and Branches" and 5.3 "Structures". With a slight simplification, if/else/then branching is defined in 7 words.
Two primitive words, branch and ?branch (in python because I know it better than assembly):
Two helper words for forward branching. >MARK adds a placeholder branch address to code and pushes the address of the placeholder. >RESOLVE resolves the branch by replacing the placeholder with the address from the stack. And then the actual IF, ELSE, and THEN words. IF puts ?branch and a placeholder address in code. ELSE puts branch and a placeholder address in code, then updates the preceding branch address (from an IF or ELSE) to land after the ELSE. THEN updates the preceding branch address to land after the THEN.> My problem is that I cannot see how control flow works in Forth, e.g. a simple if-then-else.
Hopefully this is helpful: https://www.forth.com/starting-forth/4-conditional-if-then-s...
Thanks for that. I kinda know how it "works" at the user-level. I meant to say, I don't know how it is implemented.
My mental model of Forth is that there is a simple parser that consumes space-delimited keywords. The interpreter looks up that keyword in a dictionary, which gives the address of the machine code that handles that word. The interpreter either makes a subroutine call to that address (subroutine threaded), or jumps to that address (called "direct threaded" if I recall, where the handler jumps back to the interpreter instead of executing a RET).
But that's where my mental model of Forth breaks down, because IF-THEN-ELSE cannot be implemented in that model. So there must be something else fundamental in the Forth interpreter that I don't understand.
> So there must be something else fundamental in the Forth interpreter that I don't understand.
The missing bit is IMMEDIATE mode. Words can be tagged as IMMEDIATE, which means that they get executed at compile time (or parse time, for an interpreter), rather than a call to them getting compiled (executed at run time, for an interpreter). IF/ELSE/THEN are then "just" IMMEDIATE mode words -- but you can add your own. The "special sauce" is that IF compiles (easier to talk about for a compiler; generalize as needed) a conditional branch to an unknown address, and puts the address of that branch instruction (or an equivalent) on the /compile time/ data stack; THEN then looks at the address on the /compile time/ data stack and patches that instruction to branch to the correct address. Plenty of subtlety possible, but the basic primitive of IMMEDIATE mode is the key.
Ah I see, this is peeling back a few layers of obscurity about the Forth interpreter for me. Let's stick with a Forth interpreter because that seems easier to think about for me.
Are you saying that the Forth interpreter is a 2-pass interpreter? Or does the interpreter go into a special IMMEDIATE mode upon hitting the IF keyword, then it just consumes subsequent tokens without doing any dispatching, until it hits the THEN token? It sounds like nested IF-THEN-ELSE becomes tricky to handle.
How does the FORTH interpreter handle loops? Does the interpreter hit the WHILE token, goes into IMMEDIATE mode, remembers the location of the WHILE, then dispatches all the subsequent code, until it hits the REPEAT token, then branches back to the WHILE?
Oh, and because I didn't address it directly in the longer answer...
> Does the interpreter hit the WHILE token, goes into IMMEDIATE mode, remembers the location of the WHILE, then dispatches all the subsequent code, until it hits the REPEAT token, then branches back to the WHILE?
Yes. The beauty is that, in the context of a threaded code compiler (which, again, I encourage you to use as your default model for Forth, even though other options are possible), WHILE just pushes the address of the output code stream onto the compile-time stack. REPEAT expects the address to be on the compile-time stack and compiles a conditional jump to that address. This obviously and trivially provides support for nested control structures of all types; as long as the word that pushes compile-time data onto the stack is correctly paired with the word the pops it, we have stack semantics for nested control, which is exactly the expectation. So while your description is completely correct, "remembers" is almost trivial here -- "puts data on stack" is the primitive operation of remembering anything in Forth, and that's all that's needed here, no fancy data structures or look-aside buffers or anything. (Note that the compiler does require at least two non-stack data structures, the symbol table and the output code stream, but those reflect real domain complexity.)
I've actually never worked with a "pure" interpreter in Forth, only compilers of various levels of complexity. Threaded code compilers are (in my experience) by far the most common way to deal with forth -- and they are very much 2-pass. Even when used as an "interpreter," they generate (trivial, usually) machine code, then jump to it.
Consider a definition (in some ill-defined Forth variant) like
We can categorize things: So the compiler goes through one token (that it sees) at a time.First up is `:`. `:` is an IMMEDIATE word, so the compiler just calls it now. `:` then consumes a symbol (`abs-sqr`) from the token stream so the compiler won't see it (think of calling next() on an iterator in python or equivalent), then creates a symbol table entry from that symbol to the /current compiled code output stream pointer/ -- that is, just after the last piece of code that was compiled.
Next up is `(`, since we already consumed `abs-sqr`. This is an IMMEDIATE word again -- and it just consumes tokens until one of them is exactly `)`, discarding them -- that is, it defines a comment.
Finally we get to the "easy" case, `*`. The compiler finally compiles! It looks up this symbol in the symbol table, sees that it is /not/ IMMEDIATE, and compiles a call to this address.
Now the compiler sees `0`. This is a literal token, so we don't even bother with the symbol table; we special-case code to push this value on the stack.
'<' is a non-IMMEDIATE symbol, we already know this case.
We've already discussed `if`, `neg`, and `then`. And `;` is an IMMEDIATE word that just puts a return instruction into the code stream.
Clear as mud?
There's one more step from here that's important to make, which is that the choice of what's IMMEDIATE or not is not strictly defined. Some words must be IMMEDIATE for correctness, if they interact with the compiler in interesting ways, like consuming tokens or back-patching instructions. But suppose we want to be clever... `<` works fine as a non-IMMEDIATE word. If we want to inline it, we /could/ have the compiler generalize by looking at the instructions pointed to by it, seeing how long they are (or tracking that in the symbol table), and deciding whether to inline... or we can just re-implement `<` as an immediate word that adds the appropriate instructions directly into the code stream. Combined with assembly words, this can be pretty trivially expressed, and it really changes the paradigm a bit.
> We can categorize things: > IMMEDIATE words used here are : ( if then ;
`:` normally isn’t immediate
> First up is `:`. `:` is an IMMEDIATE word, so the compiler just calls it now
`:` gets executed because the interpreter, when it isn’t compiling, goes through a loop:
So, `:` gets called in step 3a.> Now the compiler sees `0`. This is a literal token, so we don't even bother with the symbol table; we special-case code to push this value on the stack.
As indicated above, that’s not how ‘normal’ forths work. A lookup is done for a word named `0`, and if it exists, a call to it is compiled.
Many forths had words named after small constants such as `0`, `1`, `2` or `-1` because compiling a call to a function took less memory than compiling a call to the “LIT” function and compiling the constant value.
> I've actually never worked with a "pure" interpreter in Forth, only compilers of various levels of complexity. Threaded code compilers are (in my experience) by far the most common way to deal with forth -- and they are very much 2-pass. Even when used as an "interpreter," they generate (trivial, usually) machine code, then jump to it.
Lots of good info, thank you. I don't think I will fully understand what you wrote until I implement a Forth interpreter myself.
So a side question: If most Forth "interpreters" are compilers, how does a Forth interpreter work in a Harvard architecture microprocessor (with separate memory space for data and instructions) instead of a Von Neumann architecture with a unified memory layout? In other words, in a Harvard architecture (e.g. AVR microcontrollers), the Forth compiler will live in read-only flash ROM, and it cannot generate machine code into RAM and execute it, because the data memory is not executable.
> how does a Forth interpreter work in a Harvard architecture microprocessor
You compile to "direct threaded code" in data memory; direct threaded code represents a sequence of calls as a sequence of addresses to call. So while "normal" threaded code (what Wikipedia calls "subroutine threading") would just have
And then executing that means jumping to the first instruction, direct threaded code would have And then there's a suuuuper tiny runtime (like four of five instructions, literally) that has a "runtime instruction pointer" or whatever you want to call it, and just increments that and does an indirect call through to the next word whenever it's returned to.No, that's not it. It's much simpler than that, yet has much deeper implications than you think. You don't see it in other languages. The closest thing would maybe be compile-time macros in Zig? But in Forth, the power it unlocks comes in its purest form, without any fluff around it.
As @addaon writes, your missing ingredient is immediateness. This is one of the most powerful, yet mind-boggling aspects of Forth. I encourage you to check it out, it will make you grow as a developer.
I will definitely look into that.
If understanding this special IMMEDIATE mode is required to understand the Forth interpreter for something as fundamental as control-flow, it seems fair to say that Forth is not a simple language. It's not just an advanced programmable RPN calculator An RPN calculator has a program counter, which makes control-flow easy to understand.
In comparison, C is a high level language, but the mapping from C code to assembly language is relatively simple. (Yes, compiler optimizations against the C "abstract machine" can make the resulting code completely obscure. But if we turn off optimization, the resulting assembly code matches the C code fairly directly.)
Very much the contrary! In C all the syntax and control structures have to be built into the language; this makes C a much more complex language than Forth, because in Forth the language and interpreter don't even have to support things like comments, string literals, variables, and control flow. Because of immediate words, all of that can be built on top of the base language in high-level Forth, and almost always is. This allows the language itself to be enormously simpler.
It's also generally the case that in a native-code-compiling Forth the mapping from the Forth source to the machine code emitted is very much simpler and more direct than in C; as Virgil implicitly pointed out, the machine code is generally more or less in the same order as the source code, which in C it is not, and you don't have a bunch of implicit type conversions, ad-hoc polymorphic arithmetic operators, and so on. (It doesn't have to be more direct, since you can do arbitrary computation at compile time, but it usually is.)
> If understanding this special IMMEDIATE mode is required to understand the Forth interpreter for something as fundamental as control-flow, it seems fair to say that Forth is not a simple language. It's not just an advanced programmable RPN calculator An RPN calculator has a program counter, which makes control-flow easy to understand.
"Simple" is not a well-defined threshold but rather a continuum, so it's hard to agree or disagree with this. I think it's perfectly valid to observe that Forth is more complex than an RPN calculator, though.
But think of it this way: An RPN calculator has two types of tokens, literals and symbols. When seeing a literal, it evaluates a push of that literal to the stack. When seeing a symbol, it evaluates an immediate call to the behavior associated with that symbol.
Forth adds exactly one more concept: non-IMMEDIATE words. Everything an RPN calculator can do can be done as IMMEDIATEs in Forth. But by adding one metadata bit to the symbol table (IMMEDIATE or not), and adding a threaded call to any non-IMMEDIATE words to the output code stream, Forth gains function definition, full generic control flow support, compiler extensibility, support for embedding domain-specific languages (just IMMEDIATE words that consume the interesting tokens), and more.
I don't know if this counts as "simple" compared to C, but it surely counts as "parsimonious." It's hard to think of a more cleanly defined single semantic change that adds as much power to a language.
(And of course in C, once you understand the language understanding the runtime library is mostly about understanding runtime behavior, some macros not withstanding; but in Forth, the runtime library and the language are conflated through IMMEDIATE symbols, so this separation is much less clear; totally accept that this could be considered less "simple", although in practice most Forths have about as many pre-defined IMMEDIATE words as C has keywords.)
The mapping to assembly of:
42 = if ."hey!" then
is much more straightforward than
if (n == 42) printf("hey!");
I understand that to the newcomer, it might not appear that way, but implementing a Forth is really eye-opening in that regard.
If I might allow myself a bit of promotion, I wrote https://tumbleforth.hardcoded.net/ as such an eye-opening process. It's less "gentle" than Easy Forth here, but it digs deeper.
From the comments in this thread, it seems that to understand how Forth implements a simple IF-THEN-ELSE control-flow, I have to understand the difference between non-immediate and immediate words. I also have to understand the difference between outer and inner interpreter. And I have to understand how Forth generates snippets of machine code (where does that get stored? I thought Forth only has 2 stacks, does it also have a general heap?). Then understand how the THEN token goes back and patches the placeholder address generated by the IF token. And understand the difference between the parsing phase and the interpreted phase of the Forth interpreter/compiler.
But you are saying that the Forth version is simpler than C version which will kinda look like this after it's compiled (Z80 assembly code, it's in my head right now):
I find that hard to believe, but I accept that you believe that.It's fine, I can't force you in either. Maybe one day you'll dive into the subject. From the look of the comments here, you have all the hints you need.
You're describing the outer interpreter in interpretation state; Forth control flow words don't work properly in interpretation state, only in compile state. They're immediate words, so they execute at compile time instead of run time, so they can do arbitrary things to the code being compiled. Here's Mike Perry and Henry Laxen's implementation of the main control-flow words from F83, which is an indirect-threaded Forth:
When the interpreter is toodling along in compile state, compiling a colon definition by stowing pointers one after another (at the pointer here) into the definition of some word you're compiling, and it encounters an if, it sees that if is immediate, and so instead of stowing a pointer to if it just runs it immediately. The definition of if is compile ?branch ?>mark. compile is also an immediate word [correction, no, it's not, see below comment, though the following is still correct]; compile ?branch stows a pointer to ?branch into the colon definition being compiled, and then ?>mark writes a 0 into the entry following the ?branch and pushes true and the address of the 0 on the operand stack, at compile time, with the sequence true here 0 ,. The interpreter toodles along compiling the body of the if and eventually gets to, for example, then, which is also immediate, and is defined as ?>resolve, which overwrites the 0 into the address of the indirect-threaded code that will be compiled following the then. It does this with swap ?condition here swap !. The swap ?condition part aborts with an error if there isn't an unresolved if or similar on the stack to resolve, consuming the true, leaving only the address of the 0 that ?>mark had pushed. So then here swap ! overwrites that 0 with the current value of here.?branch is a word written in assembly which does a conditional jump in the inner interpreter (the one that interprets the indirect-threaded code); when it's executed, it pops a value off the stack and checks to see if it's zero, and if so, it changes the interpreter's execution pointer ip (which is defined elsewhere as the register si) to the number stored in the threaded code following the pointer to ?branch. If, on the other hand, the value it popped was nonzero, it increments ip twice to skip over that number. (Note that Laxen's comment on ?branch is incorrect in that it reverses the sense of the test.)
All the forward jumps work in pretty much the same way: when you begin a control structure you call ?>mark to write a zero placeholder and push its address, and later on you "resolve" that placeholder by popping its address off the stack and overwriting it with the correct address. leave (break) and ?leave (if (...) break) work slightly differently, but mostly the same.
Backward jumps work the other way around: when you begin a control structure, as in begin, you call ?<mark to save the current address on the stack so that you can jump to it later, which ends up just being true here. Then, to actually compile the jump, for example in until or again, you call ?<resolve, which ends up just being swap ?condition ,—the , pops the jump target address off the stack and compiles it into the indirect threaded code, serving as an argument the ?branch or branch instruction compiled immediately before it.
begin ... while ... repeat is handled, as you can see, by treating the while ... repeat part as an if ... then with an unconditional jump back to the begin jammed in right before the then.
Hopefully this is helpful!
BTW, for the above, I reformatted the block files from the F83 distribution with http://canonical.org/~kragen/sw/dev3/blk2unix.py, which you may find useful if you want to do the same thing.
Oof, I forget that most forths are a bit mind bending with the compiler STATE. There are 2/3 alternatives to using compiler state aka IMMEDIATE.
https://github.com/dan4thewin/FreeForth2 This uses a two-pass search, for macros` and after that immediate words.
The most interesting one is Able forth https://github.com/ablevm which uses flow control to defer execution, aka quotations. I find using quotations instead of immediate modes easier to understand.
With both of these, they always compile expressions before executing them, so IF/THEN/ELSE can be used at any time.
Thanks for this expansion of the ideas involved. My question here is what does the COMPILE word do? What is the state of the VM / compiler / repl or whatever after it encounters that word?
That "IF" is implemented in terms of other more fundamental operators is fine, but can we write a program that just uses the fundamental operators that demonstrates IF-like behavior but doesn't introduce any intermediate words?
Actually compile is not an immediate word (at least in F83). I was wrong about that. Here's the F83 definition:
This takes its return address (which points to the following word in the colon definition that called it), dups it, adds 2 to it, and puts that back on the return stack as its new return address. Then, it fetches from its original return address with @ (thus getting the address of the word that followed it in the colon definition, such as ?branch in my if example above) and compiles it with , into whatever is currently being compiled. Then, when it returns, having added 2 to the return address means that we don't actually execute ?branch or whatever; we've skipped over it.So it doesn't change the state of the interpreter at all!
I think you're asking if you can use things like ?branch usefully without writing any immediate words. In some sense I think the answer is yes in F83 but no in standard Forth. I think you can put a code sequence like ?branch [ here 0 , ] into a colon definition to do what if does, and then later on say [ here swap ! ] to do what then does. I just typed this definition into F83, and it seems to work†:
You could sort of think of if and then as being macros for ?branch [ here 0 , ] and [ here swap ! ] respectively (although I'm omitting the checks they use for proper control structure nesting).On the other hand, this is only possible because [ is an immediate word, and because ?branch is exposed, and happens to take an absolute address in the next word in the colon definition (as opposed to a byte delta or something). As it happens, exactly the same definition of is3 appears to work in GForth 0.7.3 and PFE 0.33.71, but it definitely will not work on, for example, any native-code-compiling Forth.
The standard way to invoke things like ?branch is using if, while, and so on. And you don't have to define any immediate words to do that, either.
______
† By "work" I mean it seems to behave the same as
Wow, that's going to take some time and effort to digest, but thank you.
Yes, I think control-flow is easier to understand in assembly language than the implementation you showed in Forth. :-)
Happy to help!
I think you're mistaken about assembly language.
In assembly language, the thing that plays the role of these definitions like if and then and ?<resolve is the assembler's symbol table and relocation logic, which goes back and changes your jump instructions (etc.) to jump to the places where it finds that your labels have been defined to point. Typically this involves things like hash functions, hash table collision resolution, various operand encodings for things like short jumps and long jumps, and so on.
Although you can write an assembler that does all this in an afternoon, I don't think you will ever find an assembler whose implementation of all this functionality is easier to understand than the above 30 lines of code. It might be easier to understand per line of code but there will be a lot more lines of code to understand, like 10× or 100×.
Hint: IF, THEN, and ELSE are words that are partially evaluated at compile time.
IF remembers its own location and reserves space for a jump; THEN compiles a conditional jump if NOT true to its location, in the place where IF was, unless there was an intervening ELSE, in which case it will compile such a conditional jump to ELSE's location at IF, and an unconditional jump to then just before ELSE. So a full use might look like:
Which is the equivalent of: THEN works differently in Forth than in, like, BASIC. It marks the end of the whole conditional block, not the start of the consequent.> My problem is that I cannot see how control flow works in Forth, e.g. a simple if-then-else.
figuring this out for my own FORTH interpreter was a moment i still remember, nearly 50 years later. quite a revelation
In my opinion, a language that requires a programmer to have a "revelation" to understand basic control flow is not a language that is useful or practical for solving real world problems.
I would prefer to write in assembly language than write in Forth. Which is what I have done with one of my current projects.
With assembly language, there is a good chance that a random person with some minimal programming skills would understand my program if I were hit by a bus. With Forth, I think the chances of that are close to zero.
If you're coding, you don't have to understand how to implement control flow. The average C programmer hasn't a clue how the underlying control flow is implemented. It's an _implementor_ of an interpreter or compiler who needs to understand this. Forth is no different from C or any other language in this regard, except that, in Forth, control flow can be implemented directly rather than relying on the compiler or interpreter to understand them.
Immediate words are essentially a kind of macro, if it makes things easier for you.
It's a revelation to understand how basic control flow is implemented in any compiler. From your described preference to not learn things that aren't generally known, it's a safe bet that you don't understand CPS or SSA either, or know what a basic block is.
I remember, many years ago, when I was learning programming. When I grokked recursion, it was a revelation to me. Could I be a programmer without that revelation? Yeah, kind of, but I'd be a lesser one.
Have you tried looking at Sectorforth?
In most languages branching is a fundamental construct, it's created here (with comments)
https://github.com/cesarblum/sectorforth/blob/master/example...
Effectively IF compiles a 0= ie. If false and then a dummy target address. THEN (aka ENDIF) compiles the real target address over the dummy one, which is the address after THEN.
A million times this. The syntax is not difficult to see, but the action seems mysterious.
The article gives an example
Seems to work okay.What about immediate mode?
Well, I guess that does it for me.Factor, another stack-based languages, has a more legible version of this, where you can push an anonymous lambda onto the stack. As I recall from my days of programming HP-48's, that used a similar mechanism. (Not checking my syntax here)
Would have a similar effect. Each entry makes sense -- the << switches from immediate mode to store mode (or some similar concept), and everything ends up on the stack. "If" is just a function that takes a boolean and a closure: But I don't understand what Forth is doing.Forth control structures don't work in interpret state because control structures involve executing code out of order: jumping from the end of a loop back to its beginning, etc. In interpret state there's nowhere to jump to. So you have to put control structures inside a colon definition for them to work. Also true of strings in traditional Forths, but GForth just dynamically allocates some memory and leaks it instead.
The hard part I think is grokking the fact that the FORTH can compile and interpret inside the same definition. Also one must understand the operation of the Forth primitives HERE and comma (,)
I will take a run at explaining IF ENDIF (endif is the Fig Forth term, used here to avoid confusion)
?BRANCH is an instruction in the virtual machine. It jumps if top of stack=0 . The offset (or address)that it jumps to is the memory word right after the ?BRANCH token. Like this: <?BRANCH><number>
Forth definition of IF
: IF COMPILE ?BRANCH HERE 0 , ; IMMEDIATE
At compile time IF "compiles" the token for ?BRANCH but then interprets "HERE 0 ,"
(IF is an IMMEDIATE word that executes even if the compiler is turned on)
HERE is like $ in Assembler, ie: the address where code is being laid down. It is simply left on the data stack. HERE is the address where the <number> will be stored... later.
0 is a zero, that is pushed onto the data stack.
"Comma" (,) pops the zero and puts it in memory address HERE but! it advances the system memory pointer 1 integer width.
The zero is now a place holder in memory to be filled in by ENDIF.
: ENDIF( addr -- ) HERE OVER - SWAP ! ; IMMEDIATE
ENDIF needs that address left behind by IF shown in comment as addr.
ENDIF gets the new value of HERE which of course is different because we will have compiled some code after the IF keyword.
All we need to do is do NEWHERE-OLDHERE to get the offset for ?BRANCH.
That is covered by the forth code ( oldhere-on-stack) HERE OVER -
This will make the data stack be: ( OLDHERE offset )
If we do a SWAP we just need the store operator '!' to put the offset into memory.
For the morbidly curious here is the definition of ELSE. :-)
: ELSE COMPILE BRANCH HERE 0 , SWAP [COMPILE] ENDIF ; IMMEDIATE
So loops are just more of the same... (all loops jump back to BEGIN. BRANCH is an unconditional jump instruction)
: BEGIN HERE ; IMMEDIATE
: AGAIN COMPILE BRANCH HERE - , ; IMMEDIATE
: UNTIL COMPILE ?BRANCH HERE - , ; IMMEDIATE
: WHILE [COMPILE] IF SWAP ; IMMEDIATE
: REPEAT [COMPILE] AGAIN [COMPILE] ENDIF ; IMMEDIATE
>>Forth is a million languages that solve almost nothing." :-P
That brings us to the question, when it was invented and people did use it. What kind of problems were they solving with it?
Forth was invented around 1970 for controlling equipment in an astronomical observatory, running on a PDP-11, a 16-bit computer with up to 64 Kbytes of memory. Its heyday was the 1970s and 80s, when it was mostly used for small embedded systems on 8- or 16- bit processors with 8 kb -- 64 kb of memory. It was possible to run an entire Forth development system along with the application on these small targets without resorting to a bigger computer for cross-development.
The usual alternative to Forth on those systems was assembly language.
I was dropped into one such system after it failed after like 20 years and learned forth on the fly while managers breathed down my neck lol. Not a fun experience, and it took about 3X as long as I thought it would take, so Forth is not my favorite language, but I do see why it was useful at the time, and as an exercise in a way of thinking about languages rather than the mode I usually operate in c/c++/rust/little javascript
Forth started as Chuck Moore’s solution to the problem of how to bring up an interactive programming environment on hardware with limited memory. The base of the system used a small number of primitives written in assembler or machine code upon which more complex functions were built. The genius of the system was that you could easily bring it up on different hardware by translating the primitives, which was quite helpful at a time when software was frequently customized to the hardware (which itself was not as standardized as today). Nowadays Forth is probably most useful on embedded systems.
> Nowadays Forth is probably most useful on embedded systems.
Nowadays almost nothing is written in Forth. That's the problem with Forth. Even on 8-bit Arduino microcontrollers with 2kiB of RAM, we write programs in C++ (with a little bit of C, on top of hand-coded AVR assembly).
The Starflight role-playing game for DOS [0] was written in its own Forth dialect. Even today, it remains one of the games with the strongest Star Trek feeling.
[0] https://en.wikipedia.org/wiki/Starflight
It's a cool little niche language. If you're neither interested in the coolness, nor its little niche - there's no need to be dismissive.
Yes, my comment came across a bit harsh, and it’s fine to pick up a few negative karma points. But I keep seeing Forth posts every two weeks where everyone has just built yet another interpreter.
Actually I did a few projects with Forth and I find it very cool:
[0] https://github.com/s-macke/Forthly
[1] https://github.com/s-macke/starflight-reverse
[2] https://s-macke.github.io/concepts-of-programming-languages/...
I like that way of thinking about it - now I want my negative karma points separated into their own bucket even if the final summary is presented out, I think its an interesting signal.
Dang & Co. doubtless see such things - but I'd bet it'll never be shown to regular users. Too little utility, vs. too tempting for a small minority to game in unhealthy ways.
Heh, I see you linked StoneKnifeForth there!
In Factor though, they do.
https://factorcode.org/
It looks like it's still being developed, but I feel like the 0.1 version number hasn't changed in 10 years. What cool projects are people making?
Check out the website (I linked it) for examples.
Additionally, check basis/ and extra/ on https://github.com/factor/factor. You will find A LOT of goodies there. They even have a framework for Discord bots using latest Discord API version, if you are into that. In any case, you really ought to check, there are too many things to list here.
As someone else pointed out, it is 0.100 which was released not that long ago, and if you compile now, it is 0.101 anyways, but regardless of their versioning, it has been actively maintained ever since, they just did not bump the version for a long time.
Its version seems to be 0.100, not 0.1. And it was released last year: https://downloads.factorcode.org/releases/
If I can find a Forth for a new chip I'm learning, I use it as a way to explore the chip with a REPL.
Micropython can be similar this way, but it's more constrictive.
Every single coder that uses chaining operators is using concatenative programming concepts. Shell piping is also a form of concatenative programming.
Just because you don't specifically use forth does not mean forth is dead.
Shell piping isn't Forth.
I didn't say it was forth, I said it was concatenative.
Forth itself is hard to categorize since it refuses to standardize but we all know what it looks like, I'd say its a low level language/VM that manages everything through stacks (usually 2) there's forthlike languages and also concatenative languages. concatenative languages can be far removed from forth, I don't mean that the shell itself is concatenative, but only the shell pipelining aspect, which you can imitate in any forth. take an object and keep passing it to subsequent functions without popping that know s how to handle that object, that's a shell pipeline to me, all of unix can be passed the /dev/std* objects and they can all modify it and pass it along to the next function/program.
https://concatenative.org/
Well, I agree that Forth is concatenative (like stack languages in general), and so are shell pipelines.
But you said, "Just because you don't specifically use forth does not mean forth is dead," and unless I misread your intent, you included your shell-scripting point on the theory that it was relevant to that question: whether or not Forth was dead. The implication seemed to be that, as long as people were using shell pipelines, Forth wouldn't be dead. But that's wrong; Forth could be totally dead while other forms of concatenative programming were alive and well.
What about openfirmware?
Unfortunately we aren't in the 1980's glory days of Forth in 8 bit home computers, and many students don't know what HP-48GX stands for.
BASIC, especially the Microsoft dialect, became the dominant language for microcomputers because it would fit in a tiny space, e.g. 4k. For that matter it was big in the minicomputer age because it was used in multitasking systems that weren't that big. Circa 1980 my high school had a PDP-8 which had three terminals and could run a three user BASIC with just 32k 12 bit words.
There weren't a lot of languages which would fit in a tiny space, but FORTH was one of them. Like LISP it's a language where you can (1) implement the language without any kind of recursive parser and (2) write control structures in the language itself because each "word" in forth has both a run-time and compile-time interpretation.
Original BASIC did not fit into tiny space, that is why while Dartmouth BASIC always compiled into machine code before execution, everyone that learnt BASIC in 8 bit systems thinks it was originally interpreted and compilers only came later, which was the compromise to make it fit into a few KB.
Jupiter ACE had its followers, and it was common to see ads on Your Sinclair and similar magazines for ROM replacements using Forth instead of BASIC.
That PDP-8 BASIC was a miracle of shoehorning as was everything else on the PDP-8.
My favorite minicomputer BASIC that I got to use was on RSTS/E on the PDP-11 which had split 64k address spaces for code and data and used fairly advanced compilation techniques. Roughly the RSTS/E experience was like having your own Apple ][ but with a hard drive and a little more oomph. I grew up in New Hampshire right next door to DEC's headquarters in Massachusetts and there were DEC minicomputers everywhere.
Microsoft had a compiled BASIC (like run a compiler, not compile interactively like Microware's BASIC09) on CP/M for the Z-80 which was a much better compiler target than the popular 6502.
I wrote a FORTH for the TRS-80 Color Computer using the OS-9 operating system which had maybe 2000-3000 lines of assembly code. FORTHs at the time often did block I/O directly to the disk but OS-9 had an API to access files that was pretty similar to Unix and my FORTH exposed that.
RPL isn't Forth.
Technically you are right, in practice they are close enough in concepts, exploring stack based languages.
I don't agree at all. They do have something in common: they're stack-based. But what they don't have in common is everything else. RPL is a dynamically-typed, bounds-checked, memory-safe, garbage-collected language similar to PostScript or Python. Forth is an untyped, unsafe language with arbitrary compile-time compilation and without even a heap, traditionally. It's the minimal veneer on top of assembly language to give it arbitrary compile-time metaprogramming and nested expressions and control structures. RPL doesn't even have compile-time metaprogramming at all.
These two languages represent diametrically opposed approaches to programming language design.
Bitcoin’s scripting / smart contracting language is Forth.
Were there anything in the crypto space is actually solving a problem is up to your own biases and prejudices. But if you pick one thing as actually trying to solve a real problem, payments over lightning is probably that. Lightning, at its core, is a state machine composed of Forth spend scripts.
While bitcoin script is a stack language, it doesn't really qualify as Forth as it doesn't allow you to define any new words.
No, Bitcoin Script is not Forth. Bitcoin Script is designed to guarantee termination, so no Turing-complete programming language was permitted. Like BPF, Bitcoin Script doesn't have subroutine definitions or backward jumps, so each opcode executes at most once.
This is like saying JSON is C++.
It's more like saying JSON is Javascript, which it is to a degree.
I considered that analogy and consciously rejected it.
Eh, that's sort of like saying that nobody's coding anything useful in assembly language. Both the JVM and WASM are stack machines akin to Forth.
They're akin to Forth, but they're not Forth, and they're not implemented in Forth.
By contrast, assembly language underpins most software people run today: perhaps it's written in Python, which is interpreted by CPython (using a bytecode which is considerably more Forthlike than Wasm, incidentally), which is written in C, which is usually compiled by GCC or LLVM to textual assembly language in order to generate the executable.
I've done:
- Accounting system used for real life taxation in my self-employment: https://gist.github.com/lf94/fcdf41776e14fcc289bac652ea8cb4f...
- Software shader rasterizer for image generation: https://gist.github.com/lf94/f74c927e59b4010d9de001fa2ba8791...
- PS4 controller macro system via an RP2040 & ZeptoForth: https://youtu.be/exayMSQfyqk, https://gist.github.com/lf94/2d64917728594516dee6caf7667d2e4...
- Iambic paddle tap interpreter for morse code practice (once again running RP2040 & ZeptoForth): https://gist.github.com/lf94/95516fa39c3339b685e0fde10f17c97...
- Fixed-point number library to run computations on pretty much any CPU in existence: https://gist.github.com/lf94/ca622ebac14d48915ea976f665f832c...
- 1-bit music synthesis experiments to learn how to make music with a beeper (useful in products, such as Tile): https://www.youtube.com/watch?v=IjTihhFG03o, https://www.youtube.com/watch?v=_6f8PURcPEE
And that's all in my rare spare time.
Forth really shines in microcontroller or esoteric computation machines, but further more, people don't realize their C compilers are billions of dollars of development, and they'd never be able to do it in the first place. A Forth on the other hand can be developed in a month (I'm being honest-to-god realistic here. A lot of people would say "a weekend", but let's be real, anything useful will be more than a weekend. I'm trying to convince you this isn't bullshit :)).
If you have any more questions let me know. I was bit by Forth about 2 years ago but had read about it long ago when I was like 16 and passed it off as too hard. It's the same shit as when FP took off: it's a different mental model, so it will take time to morph your mind.
Edit: read the larger comment below, and they are totally correct:
> most Forth tutorials today are written by people who don't really know Forth
One day I might write a small Forth novella teaching how to actually think about Forth programs. In these 2 years I've had to just practice and write programs to see common patterns or idioms - kind of exactly like when I was learning Haskell years ago.
This is pretty impressive!
I don't think it takes billions of dollars in development to write a C compiler, but it does seem like everyone's first C compiler does take at least a year, so US$100k is a good ballpark. I agree that Forth is about an order of magnitude easier. You probably shouldn't consider https://github.com/kragen/stoneknifeforth to actually be a Forth (it's not interactive and doesn't have immediate words) but it did compile itself into a working ELF executable and it did take me almost exactly a month to write (October 02008, specifically). I could probably write a real Forth now in a month.
I would be very excited to read your small Forth novella. Or your small Haskell novella.
The automatic scrolling makes the page basically unusable on Safari.
With js disabled, it's perfectly usable in FF.
It's not usable because the Forth interpreter doesn't work for the interactive examples.
Same on Firefox.
I think Forth is well worth learning just for the mind expansion.
It also makes a nice starting point for building your own interpreters / designing your own languages.
Forth is very enjoyable, and it's always exciting to see someone new discovering it, but it has three big problems.
The first is a technical problem: the forte of Forth is self-hosted developer tooling in restricted environments: say, under 256KiB of RAM, no SSD, under 1 MIPS, under 10 megabytes of hard disk or maybe just a floppy. In that kind of environment, you can't really afford to duplicate mechanism very much, and programmers have to adapt themselves to it. So you end up using the same mechanism for fairly disparate purposes, with the attendant compromises. But the results were amazing: on an 8080 with 64KiB of RAM and CP/M you could run F83, which gave you virtual memory, multithreading, a somewhat clumsy WYSIWYG screen editor, a compiler for a language with recursion and structured control flow, an assembler, and a CLI and scripting language for your application.
Those environments almost don't exist today. But if you're programming, say, an MSP430 (consider as paradigmatic https://www.digikey.com/en/products/detail/texas-instruments...), you have only 2KiB of RAM, and you could use Mecrisp-Stellaris https://mecrisp.sourceforge.net/
That chip's resources are pretty limited. In a money economy, we measure resources in money; the reason to use a chip with limited resources is to avoid spending money, or to spend less money. That chip costs US$7.40. For US$5.59 you could instead get https://www.digikey.com/en/products/detail/stmicroelectronic...: 100 megahertz, 512MiB of flash, 256KiB of RAM, 50 GPIOs, CAN bus, LINbus, SD/MMC, and so on. And according to Table 33 of https://www.st.com/content/ccc/resource/technical/document/d... it typically uses 1.8μA in standby mode at 25° at 1.7V. That's more than the MSP430's headline 0.1μA from https://www.ti.com/lit/ds/symlink/msp430f248.pdf but it's still low enough for many purposes. (A 220mAh CR2032 coin cell could theoretically supply 1.8μA for 13 years, but only has a shelf life of about 10 years, so the STM32 uses less than the battery's self-discharge current.) That is to say, the niche for such small computers is small and rapidly shrinking.
Also, while the microcontroller might have only 2KiB of RAM, the keyboard and screen you use to program it are almost certainly connected to a computer with a million times more RAM and a CPU that runs a thousand times faster. So you could just program it in C or C++ or Rust and run your slow and bloated compiler on the faster computer, which will generate more efficient code for the microcontroller. The cases where you have to build the code on the target device itself are few and far between.
Forth was designed to make easy things easy and hard things possible. The second problem is a social one: as a result of the first problem, the people who used Forth for that have mostly fled to greener pastures. The Forth community today consists mostly of Forth beginners who are looking for an artificial challenge: instead of making hard things possible, they want to make easy things hard. There are a few oldtimers left who keep using Forth because they've been using it since it did make hard things possible. But even those oldtimers are a different population from Forth's user base in its heyday, most of whom switched to C or VHDL. Most of us have never written a real application in Forth, and we've never had the religious-conversion experience where Forth made it possible to write something we couldn't have written without Forth.
The third problem is also a social one: as a result of the second problem, most Forth tutorials today are written by people who don't really know Forth. I've only briefly skimmed this tutorial, but it seems to be an example of this. For example, I see that it doesn't explain immediate words, much less when to not use immediate words. (If it's ever easier to write something in Forth than in C, it's probably because you can define immediate words, thus extending the language into a DSL for your application in ways that are out of reach of the C preprocessor.) And it doesn't talk about string handling at all, not even the word type, even though string handling is one of the things that Forth beginners stumble over most when they start using Forth (because it doesn't inherently have a heap).
So, I hope the author continues to learn Forth, and I hope they extend their tutorial to cover more aspects of it.
Forth has always intrigued me as one of those languages (APL and Mumps also come to mind) that appears to have a superpower, for example expressing somewhat complex systems compactly, while at the same time also being flawed enough so that this superpower only appears to be applicable to a small niche.
Given the somewhat sorry state of (lack of) expressiveness and accompanying bloat in programming in general, it would be really interesting to see if that is inevitable, so if the superpower is in fact also the flaw, or if it's possible to extract the superpower from the flaw.
The way you express Forth's superpower is one I haven't seen so far and seems to point a possible way:
> So you end up using the same mechanism for fairly disparate purposes, with the attendant compromises.
Can you tell more about those mechanisms that are used for disparate purposes?
> If it's ever easier to write something in Forth than in C, it's probably because you can define immediate words, thus extending the language into a DSL for your application in ways that are out of reach of the C preprocessor.
So compile-time metaprogramming is not just available as an add-on, but very much "how things are done"?
https://www.forth.com/starting-forth/11-forth-compiler-defin...
And having a bit of compile-time metaprogramming also be the compiler is enabled by effectively not having syntax?
I agree about Forth being a fatally flawed language with superpowers, although I think we could easily have ended up in a world where Forth played the role of C, which has its own fatal flaws.
Yes, compile-time metaprogramming is very much "how things are done". This is simplified by not having syntax, but I don't think they're inseparable; you could imagine building up a compiler in the same way from an almost-as-minimal base using something like https://jevko.org/, S-expressions, a Prolog-like extensible infix parser, or a Smalltalk-like non-extensible infix parser with an open set of operators. I think most of these would be improvements. PostScript has an only slightly more elaborate syntax than Forth, but uses Smalltalk-style lightweight lambdas (called "quotations" in several other stack languages) to provide control-flow operators through runtime metaprogramming instead of compile-time metaprogramming.
As for "mechanisms used for disparate purposes", for example, the outer (text) interpreter in typical Forths plays the role of the Unix shell, the C-level systems programming language, the assembler syntax, and the user interface to applications such as, traditionally, the interactive text editor. And in https://news.ycombinator.com/item?id=45340399 drivers99 reports using it to parse an input file. The Forth language is not a very good shell command language, not a very good high-level programming language, and not a very good text editor user interface language, but it's adequate for all of these purposes.
The dictionary, similarly, serves to hold definitions for all those purposes. But it also allocates memory in a region-allocator-like way—a byte at a time, if need be. You can use the same words like , to store data into the dictionary directly, in interpretation state:
Or in a constructor: In traditional Forths like F83, , is also the mechanism for adding an xt to a colon definition, but in ANS Forth compile, was added as a possible synonym which would also permit writing Forth code that was portable to non-threaded-code implementations. https://forth-standard.org/standard/core/COMPILECommaThe operand stack serves to pass arguments and return return values, as well as to hold temporaries, but you can often use it to store a local variable as well, and space on it is dynamically allocated, so it's possible to use it to pass or return variable-sized arrays by value. At compile time, it's used to keep track of the nesting of control-flow structures.
The return stack serves to store return addresses, but also to store loop counters or maybe another local variable. And return-stack manipulation provides you with a relatively flexible form of runtime metaprogramming for things like stackless coroutines, shallow-bound dynamic scoping, and exception handling. Here's an implementation of dynamic scoping (which cannot be used inside a do loop or when you have other stuff on the return stack):
Example usage: This temporarily sets base to 10 before calling ., but then restores base to whatever value it had before upon return. A better implementation that uses the return stack instead of old and where to save and restore the values is (This is probably not very understandable, but I've written an 1800-word explanation of it elsewhere which you can read if you like.)Pointer arithmetic and integer arithmetic are the same operation, as they are in most untyped languages. This is different from C, where they are done with the same operators which are implemented differently for integers and for different types of pointers.
The "filesystem" in traditional Forths simply exposes the disk as an array of 1024-byte blocks which could be mapped into memory on demand. Conventionally you would divide your code into 1024-byte screenfuls, each space-padded out to 64-character lines, 16 of them. In effect, each screen was a different "file", identified by number rather than name. It's reasonable to argue that this is not a very good filesystem, and not a very good format for text files, but to implement any filesystem on top of a disk or SSD, you need a layer that more or less provides that functionality; all that's required to make it usable for code blocks is to use 1024-byte blocks instead of 128-byte or 512-byte or whatever.
Multitasking in traditional Forths is cooperative. In some sense this eliminates the need for locking; for example, to ensure that the block buffer you've mapped your desired block into doesn't get remapped by a different task before you're done using it, you simply avoid calling anything that could yield. Unfortunately, Forth doesn't have colored functions, so there's no static verification that you didn't call anything that calls something that yields. Cooperative multitasking is sort of not very good multitasking (since an infinite loop in any task hangs the system) and not very good locking, but it does serve both purposes well enough to be usable.
Scheme is sort of like this too; famously, Scheme's lambda (roughly Forth's create does>) is semantically an OO object, a statement sequencing primitive, a lazy-evaluation primitive, etc., while S-expressions are a similar syntactic cure-all, and call/cc gives you multithreading, exception handling, backtracking, etc. See https://research.scheme.org/lambda-papers/. In practice a small Lisp is about the same amount of code as a small Forth.
BTW, I still have a paper of yours in my queue to read!
Well said. I love Forth an I think it’s worth learning, but almost nobody programs workstation-level applications with it, and as you say, even in embedded environments the level of resources have grown such that there’s very little reason to choose Forth anymore. Which makes me a bit sad because Forth is brilliant.
Yeah :-(
Reading lines from a file and handling the strings in memory is what made me stop using it after a 3rd day of advent of code one year. I simply couldn't find a good solution, without a massive excursion into how to use the pad. Such a supposedly simple thing like reading a complete line from a file, yet it stopped me completely. Of course I could have "cheated" and put the input right into the program, but I wanted to learn Forth, so I thought I should be able to do this ...
Later I read, that GForth 1.0 should have more string handling words, but then I already had lost hope to find an easy solution. Don't get me wrong, learning the little bit of Forth that I did learn, it was quite interesting, and I would have liked to progress more. I think I also lost hope, because I couldn't see how this stack system would ever be able to handle multi-core and persistent data structures. Things that I have come to use in other niche languages. Also that some projects/libraries are one-man shows/bus factor 1, and the maintainers have stopped developing them. They are basically stale and made by people, which significantly more understanding than any beginner will have for a long time.
I guess to really learn it, one has to read one of the often recommended books and have a lot of patience, until one gets to any parts, where one learns simple things like reading a file line by line.
You should be able to dive in quickly using the very nice forthkit, which finishes with a working shell / REPL:
https://github.com/tehologist/forthkit
It is an implementation of eforth, a portable forth:
http://www.exemark.com/FORTH/eForthOverviewv5.pdf
I think mostly learning Forth is like learning any other programming language (or, better said, programming environment): you learn by doing it. Books can be a useful complement to practice, but practice is how you learn to do things. You can't learn to do things by reading.
As for string handling, in my limited experience, string handling in Forth is a lot like string handling in C; you have to allocate buffers and copy characters between them. memcpy is called move, and memset is called fill. You can use the pad if you want, but you can just as well create inbuf 128 allot and use inbuf. There are two big differences:
1. Forth doesn't have NUL-terminated strings like C does, because it's just as easy to return a pointer and a length from a subroutine as it would be to return just a pointer. This is generally a big win, preventing a lot of subtle and dangerous bugs. (Forth is generally more error-prone than C, but this is an exception.)
2. Forth unfortunately does have something called a "counted string", where the string length is stored in the byte before the string data. You can create them with C" (https://forth-standard.org/standard/core/Cq), and Forth beginners often wonder whether to use counted strings. The answer is no: you should never use counted strings, and they should not have been included in the standard. Use normal strings, created with S" (https://forth-standard.org/standard/core/Sq), unless you are calling word or find. https://forth-standard.org/standard/rationale#rat:cstring goes into some of the history of this.
If you want to allocate strings on the heap, which is often the simplest way to handle strings, malloc is called allocate, realloc is called resize, and free is called free: https://forth-standard.org/standard/memory
With respect to multicore and persistent data structures (I assume you mean FP-persistent, as in, an old pointer to a data structure is a pointer to the old version of the data structure), stacks aren't really related to them. Each Forth thread has its own operand stack and its own return stack (and sometimes its own dictionary), so they don't really create interactions between different cores.
I think there is another problem for me: The last time I have done any manual memory management a la C, before using Forth was some >10y ago. And immediately the next question would pop up in my head: "What if that line is longer than 128 bytes? Is there no general function to read a whole line?" And I guess then I would reinvent the whole machinery to read a whole line, determining at which byte the newline appears. And then I would have doubts like: "Uh, but what if someone puts some unicode characters in there?". While actually all I wanted was to read a single file, to get working on an AoC puzzle.
So I think I lacked the manual memory management basics as well at that point, and any haphazardly implemented hack like "assume the longest line is at most 128 ASCII characters long" would not have made me happy with my code.
Well, to bake an apple pie from scratch, you must first create the universe.
In any programming language, to read an arbitrarily long line into memory, you need an arbitrarily large computer, so your software may need to pause to convert more Temu orders, continents, asteroids, or star systems into computronium. If you're not willing to go that far, you have basically two choices:
1. Process the line in a streaming fashion rather than holding all of it in memory at once.
2. Only handle lines up to some maximum length.
If you select option 2, the only remaining questions are:
2a. What is that maximum length?
2b. What happens if you hit it?
Maybe 128 bytes is not a limit you're happy with, but it's just as easy to use 1048576 or 1234567890. Your code may be easier to understand and easier to get right if you use a dynamically-allocated string type (I suggest studying stralloc from qmail 1.03), but don't fool yourself into thinking that that means there's no limit on input line length. Dismayingly often, the answer to 2b in that case is "Linux starts thrashing and becomes unusably slow until you reboot it."
(If your input is UTF-8, the line-reading function doesn't have to worry about whether the bytes represent Unicode characters or not, because byte 0x0a will never occur inside a non-ASCII character.)
The point is, I don't want to spend lots of time solving these essential problems, when I actually want to learn the language through solving puzzles. It seems, that Forth does not lend itself to be learned that way, since even very basic things are not provided and require in-depth knowledge of Forth and developing manual memory managed solutions to problems, that are solved in almost every programming language in their standard libraries. If I used Python it would literally be 2 lines of code, and with file.readlines() or so, I don't have to think about how long a line can be and then develop ad-hoc brittle half-solutions.
Perhaps readlines() has a limit somewhere too though. Just not aware of it and so far have not needed to deal with that kind of thing. But then again Forth and Python are 2 very different languages and act on another level of abstraction in many cases, so maybe that comparison is not fair.
Forth was sort of designed by and for people who did want to solve these essential problems anew for each application. Chuck Moore claimed many times that a tailored ("ad hoc") solution that solves only the part of the problem you need to solve for a particular application would be 10× smaller and simpler than a generalized solution that has to balance the needs of all possible applications. He considered it preferable to not have a lot of library code in your application to solve problems you don't actually have. Maybe your ad-hoc solution is brittle, but it's brittle precisely in ways you know about, not in ways you don't.
But you don't have to use Forth that way just because Chuck did. You can totally use a generalized string library in Forth. I don't know which one to recommend, but http://turboforth.net/resources/string_library.html seems to be one possibility.
You can be sure that Python's file.readlines()† will have trouble if you try to read a line that is much longer than your RAM size.
You can get pretty far with just built-in standard functionality, though:
And, as you said, GForth comes with a heap-allocated string library https://gforth.org/manual/String-words.html#String-words which you can use if you first say ______† ever since Python 2.0, I'd recommend using list(file) instead of file.readlines(), or just iterate over the file directly, like [line.strip() for line in file if line.startswith('zel')]
One year (2022) I could see, on an early problem (day 2), that I could define a handful of words in forth such that I could execute the (modified) input file itself as code (there were only 9 possible combinations since it was rock-scissor-paper, although I did have to alter the input by removing the spaces first, like "A X" was changed to "AX") to get the answer. I defined words that matches the 9 inputs and had those do whatever the problem said to do. https://adventofcode.com/2022/day/2
That's a great idea!
> Most of us have never written a real application in Forth, and we've never had the religious-conversion experience where Forth made it possible to write something we couldn't have written without Forth.
Perhaps someone will upload some Forth source code for a few larger systems e.g. "Fmacs", an Emacs-like editor written in mostly Forth with Forth instead of ELISP being the embedded language.
Then it would be interesting to compare speed and readability (important today and every day) as well as memory requirements in RAM and on disk etc. (not so important anymore, used to be very important in the past).
I had a look at the little Forth-based operating system's source code and of course couldn't comprehen much, which is obvious because looking at the code doesn't tell you, you need to imagine what's going on with the stack.
Very much this. Even when programming for constrained environments, it's almost never necessary to self-host anymore. It's easy to use host-side tools to crunch code down to something that'll work on whatever the target is.
From a practical standpoint, one of the few modern uses where FORTH shines is as a REPL for new chips/SOCs so you can play around with the hardware and see how things actually work/debug the databook.
Have you been using it for that? Which Forths and which chips have you been using?
The description of F83 sounds interesting - any way I can see it in action, or use it on my own?
Sure, I git cloned my copy from https://github.com/ForthHub/F83, and it runs fine under DOSBox. If you have Git and DOSBox installed, I think you can just type
Thanks! I'm using this as a guide https://www.forth.org/OffeteStore/1003_InsideF83.pdf. See you in the next forth thread :)
Dr. Ting's book is indeed excellent, but I've learned more from experimentation and from digging into the code than from reading it.
>> The thing that separates Forth from most other languages is its use of the stack. In Forth, everything revolves around the stack
I mean, that's pretty much every language. The main difference is that the programmer's access to it is unconstrained by things like method call definitions.
Unlike most languages, Forth has two stacks. It sounds trivial, but it changes many things. It allows for a leaner call convention. With a single stack, every function call has to "shovel forward" its arguments over the function return address, where Forth "glides" through its arguments, making function calls significantly lighter.
> Unlike most languages, Forth has two stacks.
Like Forth, Ada has two stacks. Unlike Forth, which uses two stacks to simplify the language, Ada uses two stacks to complexify the language. This generalizes to other language features.
Ada's auxiliary stack is used to permit the returning of runtime-variable-sized objects from subroutines, which is also a thing you can use the operand stack for in most Forths.
Most languages don't have an explicit stack, and even their implicit stack is only for subroutine calls. If you're not making subroutine calls, your compiled code might not access the stack at all. So, for example, here's the strlcpy function from OpenBSD, lightly edited:
GCC 12.2.0 compiles this to the following 18 ARM instructions, with -mcpu=cortex-a53 -Os -S: If you're not familiar with ARM assembly, I'll tell you that nothing in this entire function uses the stack at all, which is possible because strlcpy doesn't call any other functions (it's a so-called "leaf subroutine", also known as a "leaf function") and because ARM, like most RISCs, puts the subroutine return address in a register (lr) instead of on the stack like amd64, or in the called subroutine like the PDP-8, which doesn't have a stack at all. And the calling convention puts arguments and return values in registers as well. So the function can just move data around between memory and registers and decrement its loop counter and increment its pointers without ever touching the stack.FORTRAN up to FORTRAN 77 didn't support recursion, including indirect recursion, so that you could implement it without a stack.
By contrast, in Forth, instead of registers you use the operand stack. For loop counters you use the return stack. Sometimes you can use the operand stack instead of variables as well, although I think it's usually a better idea to use variables, especially when you're starting to learn Forth—it's much easier for beginners to get into trouble by trying too hard to use the stack instead of variables than to get into trouble by trying too hard to use variables instead of the stack.