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

101–110 of 128 posts

Re: Easy Forth (2015)

#101

Post by lebuffon »

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…

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:

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

Re: Easy Forth (2015)

#102

Post by addaon »

bxparks wrote: post #100
addaon wrote: post #58

Earlier quoted context omitted.

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…

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

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

Re: Easy Forth (2015)

#103

Post by vdupras »

bxparks wrote: post #99
vdupras wrote: post #61

Earlier quoted context omitted.

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

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.

Re: Easy Forth (2015)

#104

Post by zovirl »

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…

> 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

Re: Easy Forth (2015)

#105

Post by bxparks »

kabdib wrote: post #82
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…

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

Re: Easy Forth (2015)

#106

Post by Someone »

addaon wrote: post #58
bxparks wrote: post #48

Earlier quoted context omitted.

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…

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

Re: Easy Forth (2015)

#107

Post by bitwize »

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…

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 ;
Which is the equivalent of:

    void test(x,y) {
        if(x > y) {
            printf("greater");
        } else {
            printf("less or equal to");
        }
    }
THEN works differently in Forth than in, like, BASIC. It marks the end of the whole conditional block, not the start of the consequent.

Re: Easy Forth (2015)

#109

Post by talideon »

bxparks wrote: post #105
kabdib wrote: post #82

Earlier quoted context omitted.

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

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.

Re: Easy Forth (2015)

#110

Post by vdupras »

bxparks wrote: post #105
kabdib wrote: post #82

Earlier quoted context omitted.

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

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.
Post reply on HN