Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Easy Forth (2015)

skilldrick.github.io

Post reply on HN
Print view View original

51–60 of 128 posts

Re: Easy Forth (2015)

#51

Post by andrewla »

bxparks wrote: post #19
s-macke wrote: post #7

Earlier quoted context omitted.

Right. And once again, you’ll also notice that no one is actually coding anything useful in Forth.

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 obviou…

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 = > if
Would have a similar effect. Each entry makes sense -- the 
    > 10
    level: 0 ; stack: [10]
    > 5
    level: 0 : stack: [10 5]
    > mod
    level: 0 ; stack [0]
    > 0
    level: 0 ; stack [0 0]
    > =
    level: 0 ; stack [true]
    >  "buzz"
    level: 1 ; stack [true] ["buzz"]
    > print
    level: 1 ; stack [true] ["buzz" print]
    > >>
    level: 0 ; stack [true pointer_to_function]
    > if
    "buzz"
    level: 0 ; stack []
But I don't understand what Forth is doing.

Re: Easy Forth (2015)

#52

Post by kragen »

bxparks wrote: post #41
andsoitis wrote: post #32

Earlier quoted context omitted.

> 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 threade…

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 -- 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
    : ?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    ; IMMEDIATE   \ change the ?> and ? and RESOLVE    ; IMMEDIATE   \ should stay the same.
    : UNTIL   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 ? 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 ?, 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.

Re: Easy Forth (2015)

#53

Post by jonjacky »

kamaal wrote: post #31
bxparks wrote: post #19

Earlier quoted context omitted.

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 obviou…

>>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.

Re: Easy Forth (2015)

#54

Post by bxparks »

vdupras wrote: post #49
bxparks wrote: post #41

Earlier quoted context omitted.

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 threade…

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.)

Re: Easy Forth (2015)

#55

Post by andrewla »

kragen wrote: post #52
bxparks wrote: post #41

Earlier quoted context omitted.

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 threade…

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 Fo…

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?

Re: Easy Forth (2015)

#56

Post by adastra22 »

s-macke wrote: post #7
7thaccount wrote: post #2

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.

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.

Re: Easy Forth (2015)

#57

Post by bell-cot »

hobs wrote: post #27
s-macke wrote: post #23

Earlier quoted context omitted.

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.

Re: Easy Forth (2015)

#58

Post by addaon »

bxparks wrote: post #48
addaon wrote: post #46

Earlier quoted context omitted.

> 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.…

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…

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
We can categorize things:

    IMMEDIATE words used here are : ( if then ;
    Normal words are *
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.

'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.

Re: Easy Forth (2015)

#59

Post by failingforward »

kamaal wrote: post #31
bxparks wrote: post #19

Earlier quoted context omitted.

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 obviou…

>>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 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.

Re: Easy Forth (2015)

#60

Post by bxparks »

kragen wrote: post #52
bxparks wrote: post #41

Earlier quoted context omitted.

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 threade…

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 Fo…

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. :-)

Post reply on HN