Skip to content

Instantly share code, notes, and snippets.

@sohang3112

sohang3112/forth-notes.md

Last active January 6, 2024 04:18
Show Gist options
  • Save sohang3112/4e652fcf9b60fbab5ac8e7ad7348bd6c to your computer and use it in GitHub Desktop.
Save sohang3112/4e652fcf9b60fbab5ac8e7ad7348bd6c to your computer and use it in GitHub Desktop.
Download ZIP
Notes on the programming language Forth
Raw
forth-notes.md

Forth

Forth is an old stack-based language, primarily used in embedded / resource-constrained environments. I watched this Forth intro talk.

Resources - Books / Tutorials / Videos, etc.

Install & Setup

Using Swift Forth IDE

  • Swift Forth is a proprietary IDE for Forth - it can be used free of cost for non-commercial use.
  • Calling it an IDE might be an over-statement - I just tried it, and it doesn't even have syntax hightlighting in its REPL! I am definitely not impressed - it is very little improvement over just using gforth in the terminal!

Using gforth and jupyter notebook

  • Install the REPL - sudo dnf install -y gforth. (Obviously, replace dnf with the package manager of your distro. For example, use apt for Debian based distros.)
  • gforth by itself is quite bare bones - the usage experience can be vastly improved by using Jupyter Notebook. The Forth kernel for Jupyter can be installed like this:
pip3 install jupyter forth_kernel

...or if you want to use the development version of forth_kernel:

git clone https://sohang3112/iforth.git
cd iforth
pip install jupyter .

Now, jupyter kernelspec list should include IForth kernel.

Note: All the below code was tested to work in gforth 0.7.3 - it may or may not work exactly like this in any other REPL.

Running a Forth Script

  • Run multiple Forth scripts with gforth file1.fs file2.fs.

OR

  • Start gforth, then type the command s" file-location.fs included (where file-location.fs should be replaced by your Forth script's location - this will run the script and then return back to REPL, where all the state (stack, words) of script is available.) Issue: Didn't work for me in GForth in WSL 2

Types

  • Numbers: (example: 5, -42)
  • Booleans: are represented by -1 (TRUE) and 0 (FALSE)
  • Strings:
    • Print a string like this: ." Hello World!" (it prints Hello World!). Note that there is a space after starting ." - that is because ." is a word that prints until it reaches ".
    • Store a string using word s" like this:
s" 123"     ok                           \ a string - note space after s"
.s          <2> 93888287649920 3 ok      \ string's address, number of characters were pushed on the stack
type        123 ok                       \ print the string whose address, no. of characters are on top of the stack

Individual characters in string can be accessed using word C@ (char-fetch). This Reddit comment shows an example of iterating through all characters in a string.

Common Words

Forth Words are case insensitive. They are equivalent to functions / procedures in other languages.

Unless otherwise mentioned, Forth words always consume (remove from stack) their inputs, and place their output (if any) on top of stack.

Stack Operations

  • .s prints whole stack with length (example: <3> 1 2 3 where <3> indicates length of stack)
    Note: Only the top 9 items of the stack are shown. However, the length is always shown accurately.
  • clearstack clears stack
  • swap swaps top 2 elements of stack
  • dup copies top of stack
  • ?dup copies top of stack if it is non-zero
  • over copies second top of stack
  • rot rotates top 3 entries of stack to the right (example: 4 5 6 becomes 6 5 4).
  • -rot rotates in the opposite direction (example: 6 5 4 becomes 4 5 6).
  • drop removes top of stack.
  • nip removes second of stack.
  • tuck ( a b -- b a b ) copies top of stack below the second top of the stack.
  • Similar operations for 2 elements: 2dup, 2drop, etc.
  • roll moves nth element of stack to top of stack.
  • pick copies nth element of stack to top of stack.
  • depth shows depth of stack

Notes:

  • The default stack can only hold integers.
  • The operations mentioned so far are all on the Parameter Stack. But the Return Stack can also be manipulated using the words R>, >R, R@. See more about the Return Stack here.

Arithmetic

  • Normal Math Operators: +, -, *, /
  • For Convinience: 1+, 1-, 2+, 2-, 2*, 2/
  • max, min: work using top 2 numbers of stack

Logic Operations

  • <, <=, <> (not equal), =, >, >=, 0<, 0<=, 0<>, 0=, 0>, 0>=, within
  • Versions of these operations also exist for: doubles d, unsigned u, floats f.
Notes
  • These boolean operations output 0 for FALSE, and -1 for TRUE. (not sure why -1 !)
  • Higher level operations (like on complex numbers or matrices) can be done using Forth Scientific Library.

I/O and ASCII Operations

  • . prints top of stack (and removes it from stack).
  • page clears the screen.
  • emit prints character corresponding to ASCII code (example: 65 emit prints A).
  • char converts next character in input stream to ASCII code (example: char A . prints 65).
  • spaces prints number of specified spaces (example: 15 spaces prints 15 spaces).
  • cr prints a newline (AKA carriage return).
  • key waits for user to press a character and immediately returns. It doesn't print the character, and also doesn't wait until Enter is pressed.
  • ms sleeps for specified number of milliseconds - eg. 5000 ms sleeps for 5 seconds.

User Defined Words

  • Wait for a single character, print it, then return: : read-char key dup emit ;

Commenting Words

  • \ comments until end of line.
  • ( comments until closing parenthesis ).

Commenting Convention: ( x -- description of x )

Note: Whitespace is necessary around \, ( and ) since they are normal verbs.

Defining Words

  • Point Free Style (arguments not explicitly named): : NEW-WORD ( ... everything until ; ) ; creates a word NEW-WORD.
  • Explicitly named arguments: : NEW-WORD { a b } ... ; defines word NEW-WORD which uses arguments a, b from the stack. An example of more advanced usage (including local variables in word) is in this Stack Overflow question.

Examples

  • : square ( x -- x^2 ) defines a square word, that can be used like this: 5 square . (which prints 25).
  • : dot ( x1 y1 x2 y2 -- z ) rot * rot * + ; defines dot product of 2d vectors. Use it like this: 1 2 3 4 dot . i.e., $(\hat{i} + 2\hat{j}) \cdot (3\hat{i} + 4\hat{j})$
  • TODO: 2d vector cross product

Output Modes

  • hex switches to hexadecimal mode, i.e., memory locations will now print in hexadecimal.
    Similarly, decimal, binary switch to decimal and binary modes, respectively.

Constants

3.14 constant PI            \ define constant
PI .                        \ print constant

Variables

Define (using VARIABLE) & set (using !) a variable memory-location:

hex                          \ print all memory locations in hexadecimal
VARIABLE memory-location     \ define variable - this basically defines a word that pushes its own address on the stack
200 memory-location !        \ set variable to 200 (& remove from stack)
memory-location .            \ prints address of memory-location
memory-location @ .          \ fetch and print value at address `memory-location`

Note: Instead of fetch-and-print (@ ., as in last statement of the above code), the word ? can be used to directly print the variable's value. So, the last line of the above code can also be written as memory-location ?.

Loops

  • END START do INSTRUCTIONS-HERE loop is equivalent to:
for _ in range(START, END):
    # INSTRUCTIONS-HERE

The loop index can be accessed using the word I. For example:

: DECADE  10 0 DO  I .  LOOP ;
DECADE

Custom step in the loop can be used by using the word +loop instead of loop. +loop expects the step on the top of the stack. The following Forth and Python codes are equivalent:

: RANGE-STEP 10 0 DO I . 2 +LOOP ;
RANGE-STEP
for i in range(0, 10, step=2):
   print(i)
  • Indefinite Loop (example copied from learnxinyminutes.com):
\ Indefinite loops with `begin` <stuff to do> <flag> `until`:
: death ( -- ) begin ." Are we there yet?" 0 until ;    \ ok

Note: Loop words cannot be interpreted directly - that is why we have defined a word DECADE that uses do .. loop and then called the word.

TODO: Words while, again, repeat, leave, unloop

Higher Order Functions / Words

Words can be passed to other words like this:

  • Quoting a word gives the address of the word (example: ' negate places the address of word negate on the stack).
  • A word can be run from its address using its address using execute. So we can pass an address of a word to another word, which can then run it using execute. (example: 5 ' negate execute is same as 5 negate).
  • Annonymous words can be created using :noname (example: :noname dup * ; 5 execute . prints 25).

Other Stack Types

Forth has multiple built-in stacks - the one discussed now was actually the most commonly used, Parameter Stack.

Other stack types also exist:

  • Return Stack: Forth internally uses the Return Stack to store return addresses while calling words. Read about it here in the section titled The Return Stack.
  • Floating Point Stack: It stores floating point numbers (default stack can only store integers).

Inspecting Environment

  • see WORD shows source code of WORD.
  • WORDS word prints all the words from the top (pre-defined) vocabulary.
  • VOCS word prints all defined vocabularies.

Note: This Stack Overflow answer details other ways of inspecting words and vocabularies.

Clarify / Didn't Understand

  • Marker mark a spot in the stack. Later, any words after the marker can be deleted by executing the marker. Didn't understand syntax
  • <ADDR> <SIZE> dump - never tried!
  • Words CREATE, DOES> - don't understand what they do!
  • String Indexing
  • Arrays - Interesting explanation in Stack Overflow
  • How to read input from STDIN?? Tried to understand by reading this, but it's too complicated!
  • C FFI (Foreign Function Interface) - how to call C functions from Forth code?
  • Number Formatting (as string):
  • How to create words like char, which wait for input after the word, not before??

Code Snippets from other sources

  • Find value of quadratic $ax^2 + bx + c$ for given $x$ (see source):
: quadratic  ( a b c x -- n ) >r swap rot r@ * + r> * + ;
clearstack 4 -7 3 10 quadratic .s           \ example usage

This prints <1> 333 ok

  • Area of a circle $\pi r^2$ (source here):
: circle ( r -- pi*r^2, decimal truncated ) dup * 355 113 */ ;
2 circle .                                  / example usage - area of a circle of radius 2

This prints 12, whereas the exact answer is 12.566 - so only the fraction part has been truncated.
Note: Here, we have utilized the fact that 355/113 is a very good approximation of pi (accurate upto 6 decimal places).

My Practice Exercises

  • $x \pm y$
: +- ( x y -- x+y x-y ) 2dup + -rot - ;
clearstack 6 5 +- .s             \ 11 1 -- (6+5) (6-5)
  • Print n Fibonacci Numbers:
: fibonacci ( x y n -- x,y <- starting numbers, n <- how many to print ) 0 do over . tuck + loop ;  
0 1 10 fibonacci                   \ example usage

This prints 0 1 1 2 3 5 8 13 21 34 ok

  • Sum of first n natural numbers using formula $n(n+1)/2$:
: sum-nat ( n -- sum of first n natural numbers ) dup 1+ 2 */ ;
clearstack 10 sum-nat .s           \ example usage

This prints <1> 55 ok - 55 is sum of first 10 natural numbers.

  • Determinant of Quadratic Equation a*x^2 + b*x + c = 0:
: determinant ( a b c -- b^2 - 4ac ) rot -4 * * over dup * + nip ;
clearstack 4 -7 3 determinant .s      \ example usage - for equation 4x^2 - 7x + 3

This prints <1> 1 ok - the inputs a, b, c have been removed from the stack, and the output 1 is now on top of stack.

  • Factorial:
: factorial ( n -- n! = product of 1 to n ) 1 over 1+ 2 do i * loop nip ;
clearstack 6 factorial .s             \ example usage - 6! = factorial of 6

This prints: <1> 720 ok

  • Puts digits of a number on the stack:
: print-digits ( num ) begin 10 /mod over 0= until 2drop ;
12345 print-digits .s

This prints <5> 5 4 3 2 1 ok

  • Multiplication Table:
: multiples ( lim n -- lim n ; prints n, 2*n, 3*n .. upto limit*n ) over 1+ 1 do dup i * . loop ;
: mul-table ( lim -- lim ; prints multiplication table from 2 to lim ) dup 1+ 2 do cr i multiples drop loop ;
clearstack 5 mul-table .s            \ example usage

This prints:

2 4 6 8 10 
3 6 9 12 15 
4 8 12 16 20 
5 10 15 20 25 <1> 5  ok
  • Swap second and third items on the stack:
: swap-skip1 ( a b c -- b a c ) -rot swap rot ;
clearstack 2 3 1 swap-skip1 .s         \ example usage

This prints <3> 3 2 1 ok

  • Fizz Buzz
: fizz-buzz ( n -- ; Prints Fizz | Buzz | FizzBuzz )
    dup 15 mod 0 = if 
       ." FizzBuzz" drop 
    else 
        dup 3 mod 0 = if
            ." Fizz" drop
        else 
            dup 5 mod 0 = if
                ." Buzz" drop
            else .
            then
        then
    then ;
    
: fizz-buzz-upto 1+ 1 do cr i fizz-buzz loop ;

100 fizz-buzz-upto

TODO: Simplify fizz-buzz

  • Is it a leap year?
: true -1 ;
: false 0 ;
: leap-year? ( y -- is y a leap year? )
    dup 400 mod 0 = if                   \ if y mod 400 == 0
        true                             \ ans = true
    else 
        dup 100 mod 0 = if               \ else if y mod 100 == 0
            false                        \ ans = false
        else
            dup 4 mod 0 =                \ ans = y mod 4 == 0
        then
    then nip ;                           \ remove y from stack
2016 leap-year?         \ example usage - outputs -1 (TRUE) or 0 (FALSE)

Note: Here, dup has been used before all conditionals (eg. dup 400 mod 0 =) to preserve a copy of y for subsequent operations (since only 400 mod 0= would consume y on the stack). In the end, y is removed from the stack using nip.

  • Print Hello in an infinite loop, until user presses q to quit.
: inf-loop ( c -- c ; keep printing Hello, until given character is pressed )
  begin cr ." Hello" dup key = until ;
char q inf-loop                   \ start infinite loop, with 'q' as the exit character
  • Print sign of a number:
: sign ( n -- ; prints sign )
    dup 0> if ." POSITIVE"
    else dup 0< if ." NEGATIVE"
    else ." ZERO" then then ;
  • GCD (Greatest Common Divisor), LCM (Least Common Multiple):
: gcd ( m n -- ans ) 
   2dup < if swap then 
   begin tuck mod dup 0= until 
   drop ;
clearstack 30 40 gcd .s       \ <1> 10  ok

: lcm ( m n -- ans ) 2dup gcd */ ;
clearstack 66 121 lcm .s      \ <1> 726  ok
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment