Forth - gregorymorrison/euler1 GitHub Wiki

Forth is a fascinating language. Introduced in the 1970's, it is the oldest of the Concatenative languages, a stack-based paradigm. It is known for its brutally efficient syntax that can compile down to a smaller code size than non-stack-based languages can. Yoda-like postfix notation, it uses. And it doesn't use a stack to manage scope like most languages. Instead, there is just one scope and a stack to manage data.

It is said that there are more instances of Forth than any other language. It is also said that Forth is typically the first language ported to any architecture. It is likely that there is a version of Forth for every single platform.

Toss out your existing programming preconceptions - experience with other languages  is not relevant here. Instead of the procedural operations of Imperative languages, class and object operations of OOP, or the list operations of Functional languages, Forth is written using stack manipulation operations. The language is structured, having subroutines and flow control, but there is no concept of parameters or namespaces - just a stack for managing state.

It took me a few days to wrap my head around how this odd language works. Curl up with a manual for a while, starting at the beginning. Here's a good one - Starting Forth. It is a minimalist language with few constructs that should take you only a few days to learn, once you understand what's going on. The mind expansion is well worth the effort.

Forth is a minimal language, like Scheme and Assembly - a metalanguage in which you construct your own elements. It is so minimal that it has no immutable syntax! The compiler does have keywords and operators supplied with initial definitions, but really this is just a convenience - every single element can be redefined. All the language really has is a parser and a stack. And the parser is brain-dead simple - just tokenizes on spaces, so any Unicode garbage can be a syntax element.

Once I put the time into understanding the language, it took me maybe an hour to write my first Forth program, this version of Euler1. The runtime didn't seem to help me out much with its error messages, but the code's brevity and that old standby, the print statement, was all I needed to crank this out:

1.   ( Euler1 in Forth )
2.  
3.   : Euler1 ( n -- r )
4.       0
5.       SWAP
6.       1 DO
7.           I 3 MOD 0= I 5 MOD 0= OR
8.           IF
9.               I + THEN
10.      LOOP ;
11.  
12.  1000 Euler1
13.  .
14.  BYE

Let's break it down. I'll draw the stack contents at each step, as a list with the top at the right:

  1. Line 3: the declaration of subroutine Euler1, which is commented to use one stack variable and add one stack variable. When called, S will contain one value, n, the iteration size. S =>n
  2. Line 4: Initialize an accumulator variable - add 0 to the stack. S =>n 0
  3. Line 5: We need n available for the loop, so swap the top two stack values. S =>0 n
  4. Line 6: A do loop expects two arguments, start and end. The parser finds one hardcoded argument, 1, so it looks on the stack for the other. It finds and pops n. Remember - this is postfix, so it will be looping from 1 up to n. S =>0
  5. Line 7: Our postfix Mod3/Mod5 test. I is the implicit loop index. These operations have all the arguments they need, so nothing is read from the stack. The end result is pushed onto it. S =>0 false
  6. Line 8: The IF test expects a boolean. None is provided in the code, so it looks for one on the stack. S =>0
  7. Line 9: When Mod3/Mod5 is true, this is executed. The addition operator expects two arguments. One is provided, so the other is popped from the stack. The result is pushed onto the stack. S => 3
  8. Line 10: Keep looping. The semicolon completes the subroutine declaration.
  9. Line 12: Push an iteration size onto the stack, then call Euler1. S => 1000
  10. Line 13: Pop and print the stack top, which is the result. S =>
  11. Line 14: Bye exits the runtime.

Here's a recursive version. It took me a couple hours to write this. I thought after doing the previous example that I would fly through this, but such was not the case. I found I tripped on the postfix quite a bit, and I actually had to diagram in comments what was in the stack at all times. Forth actually has a large number of stack manipulation operations, but for purpose of illustration I am limiting myself to only the bare minimum - DUP, DROP, SWAP, and OVER. The current stack contents are included as comments following each line:

( Euler1 in Forth )

: Euler1 RECURSIVE   ( acc n -- r )
    DUP              ( acc n n )
    0= IF            ( acc n )
        DROP         ( acc )

    ELSE
        DUP          ( acc n n )
        3            ( acc n n 3 )
        MOD 0=       ( acc n tf )
        OVER         ( acc n tf n )
        5            ( acc n tf n 5 )
        MOD 0=       ( acc n tf tf )
        OR           ( acc n tf )
        IF           ( acc n )
            SWAP     ( n acc )
            OVER     ( n acc n )
            +        ( n acc+n )
            SWAP     ( acc+n n )
        THEN
        1 -          ( acc n-1 )
        Euler1       ( acc n-1 )
    THEN ;

0 999 Euler1 . BYE

If you want to play around with Forth without any installation, there is a JavaScript interpreter available that is hosted here - http://forthfreak.net/jsforth80x25.html. To run this code, I've used GNU's gforth. Just run gforth, passing it your file as an argument:

$ gforth euler1.forth
233168