&& The Forth Programming Language Forth is generally considered to be an obsolete programming language which has a brief period of glory in the early eighties. Nevertheless there are many remarkable features about forth which are not found in other languages or computer systems. Forth can be implemented in a tiny size (maybe 30K), and can be used as an operating system for embedded systems. Forth, in a sense is not even a language because it has no syntax (apart from words separated by space characters). This booklet is oriented to using forth on a linux computer. PHILOSOPHY AND IDEAS The philosophy behind forth is an extremely small and efficient interpreter and language based on a 2 stack virtual machine and a dictionary of 'words' or functions. INSTALLATION * see what software is available for the forth language on debian linux >> apt-cache search forth | less * install the gforth system on a debian/ubuntu linux >> sudo apt-get install gforth * see what files were installed as part of the gforth system >> dpkg -L gforth OPENFIRMWARE Apple Mac computers at one stage used a forth based system for booting. This was the 'openfirmware' system which uses 'fcode' which is an ans compliant version of forth. * install fcode utilities on linux >> sudo apt-get install fcode-utils THE VIRTUAL MACHINE The forth language is based on a virtual machine. This machine can be implemented in a very efficient manner. The machine has a data stack and a return stack. The return stack is used for holding the return address of functions as well as for temporary storage. DICTIONARY Forth words are stored in a dictionary in computer memory. This dictionary has a particular structure, which may vary slightly from one implementation to another. IMPLEMENTATION METHODS @@ direct threaded @@ indirect threaded @@ subroutine threaded Each call to a word is implemented as a subroutine @@ token threaded STANDARD WORDS This section documents common or traditional forth words bye exit the forth interpreter ! stores the value in the memory location @ fetches the value at the memory location create creates a new dictionary entry ' looks up the word in the dictionary and prints something like 'ok' if found or 'Undefined word' if not dump dumps the contents of memory locations words show all words currently defined in the system variable : '\n' 10 ; : BL 32 ; \ BL (BLank) is a standard FORTH word for space. * print 1 space character to stdout : SPACE BL EMIT ; * leave the negative of the number on the stack >> : NEGATE ( n -- -n) 0 SWAP - ; ( jonesforth ) * jonesforth implementation of IF >> : IF IMMEDIATE ' 0BRANCH , HERE @ 0 , ; : decimal 10 base ! ; : hex 16 base ! ; : octal 8 base ! ; : allot here + here! ; : NIP ( x y -- y ) SWAP DROP ; : TUCK ( x y -- y x y ) SWAP OVER ; * print n spaces to output ( jonesforth ) : SPACES ( n -- ) BEGIN DUP 0> WHILE SPACE 1- REPEAT DROP ; * my x86 implementation of spaces, but fails if n=0 : spaces ( n -- / type n spaces *) begin space 1- dup 0 = until drop ; if char is BL (32) then all whitespace and control characters are usually matched. This allows multiline input to be tokenised. : parse ( c -- ) ... ; * from theForth.net minimal ----- : 0< ( n -- f ) 0 < ; : 1+ ( x1 -- x2 ) 1 + ; : 2+ ( x1 -- x2 ) 2 + ; : 1- ( x1 -- x1 ) 1 - ; : MIN ( n1 n2 -- n3 ) OVER OVER > IF SWAP THEN DROP ; : MAX ( n1 n2 -- n3 ) OVER OVER < IF SWAP THEN DROP ; : 2! ( d addr -- ) SWAP OVER ! CELL+ ! ; : 2@ ( addr -- d ) DUP CELL+ @ SWAP @ ; : +! ( x addr -- ) SWAP OVER @ + SWAP ! ; : CMOVE ( c-addr1 c-addr2 u -- ) BEGIN ( c-addr1 c-add2 u ) DUP WHILE ( c-addr1 c-addr2 u ) >R OVER C@ OVER C! SWAP CHAR+ SWAP CHAR+ R> 1 - REPEAT ( c-add1 c-add2 u ) DROP DROP DROP ; \ defer creates a function pointer : DEFER ( "Name" -- ) CREATE 0 , DOES> @ EXECUTE ; : ?dup ( x1 -- 0 | x2 x2 ) dup if dup then ; : bounds ( addr1 u -- addr2 addr3 ) over + swap ; ,,,, * from openbios -------- : +! tuck @ + swap ! ; : off false swap ! ; : on true swap ! ; \ fills a memory area with space chars : blank bl fill ; : erase 0 fill ; : type bounds ?do i c@ emit loop ; ,,,, COMMON WORDS ( check if a word is alpha numeric ) : IS-ALNUM ( char -- flag ) DUP IS-ALPHA DUP 0= IF DROP DUP IS-DIGIT THEN NIP ; DATA STRUCTURES ARRAYS .... : Array ( n -- ) CREATE CELLS ALLOT DOES> ( i -- x ) CELLS + ; : Field ( u1 u2 -- u3 ) CREATE OVER , + DOES> ( addr -- ) @ + ; CONTROL STRUCTURES : begin here ; immediate : again ; : until ... ; orif A control structure from Will Baden. -if ( n -- ) branch if n is not negative DATA STACK WORDS .... >> .s display the contents of the data stack >> depth show how many items are on the data stack * set the text input buffer location to just above the stack >> sp0 @ 'tib ! RETURN STACK WORDS .... >> >r push the top value of the data stack onto the return stack >> r> push the top value of the return stack onto the data stack >> rp0 @ rp! INPUT BUFFER WORDS .... >> >in leave on the stack the position in the input buffer >> blk the input source block value * turn the block value off (set input to keyboard) eg: blk off PARSING WORDS .... @@ word (s: delimiter - address) get a word from the input stream * get the next word and print it >> word this count type INTERPRETING WORDS .... >> quit the main forth interpreter * an example quit loop >> : quit blk off begin rp0 @ rp! query interpret state @ not >> if ." ok" then again ; >> evaluate execute code stored in a text string >> tib terminal input buffer, where text typed by the user is stored >> rp0 >> query get 80 characters into the text input buffer DOCUMENTING CODE == documenting words .. \ - start a one line comment .. ( ) - start and end a comment in brackets .. BASIC CODE Print a single star (s:- ) 42 is the ASCII code for * : star 42 emit ; print n stars. loop n times (0 up to n-1) and execute star (s: n -- ) : stars 0 do star loop ; : square ( n -- ) \ print an n-line square of stars dup 0 do \ loop n times, keeping (dup-licating) n on the stack dup stars cr \ each time, print n stars then print cr loop drop ; \ after loop is done, drop the n from the stack : triangle ( n -- ) \ print an n-line triangle 1 + 1 do \ loop n times from 1 to n (instead of 0 to n-1) i stars cr \ this time use the inner loop index i loop ; : tower ( n -- ) \ print a "tower" with an base of size n dup \ dup-licate n (since it is used twice below) 1 - triangle \ print a triangle 1 size smaller than n square ; \ print a square base of size n MATHS * find the hypotenuse of a right triangle with sides x, y >> : magnitude (x y—vector magnitude) dup * swap dup * + sqrt ; OUTPUT == output words .. . - pop a number from the stack and print .. emit - print the character on the stack .. ; This square root method is very cool and gets a good ; approximation within about 6 or so iterations. ; gets the next approximation to the square root, from ron geere. ; based on newtons method : approx ( n x -- n x' ) over over / + 2 / ; ; return b, the approximate square root of a (maximum 32767 if the / ; division operator is signed, or else 64K if not), ; this just does the iterations of the "approx" word. : sqrt ( a -- b ) 60 5 0 do approx loop swap drop ; LOOPS * print 20 star characters >> 20 0 [do] 42 emit [loop] The words 'do' and 'loop' can only be used in the compile context (within a colon ':' definition). Use [do] and [loop] in interpret mode Charles Moore seems to reduce all his looping constructs in his later forths to FOR ... NEXT VARIABLES * add variables a and b and store in c >> a @ b @ + c ! The c equivalent of this is: c=a+b; * define a new variable 'x' >> variable x * define a variable and store the value '3' in it >> variable x 3 x ! * COMPILING http://www.forth.org/lost-at-c.html the forth compile flow chart GFORTH Gforth does not seem very helpful or simple to use. == error messages @@ stack underflow - The word just executed expected one or more values to be on the data stack IMPLEMENTATIONS == forth implementations .. gforth - a gnu forth .. yforth - a small ansi c forth (~27K) not actively developed .. from clf some looping words. Leaving out the constants that allow correctness checking: 'BRANCH , is the same as [COMPILE] BRANCH : IF '0BRANCH , (FORWARD ; IMMEDIATE : THEN FORWARD) ; IMMEDIATE : ELSE 'BRANCH , (FORWARD SWAP FORWARD) ; IMMEDIATE : BEGIN (BACK ; IMMEDIATE : WHILE '0BRANCH , (FORWARD SWAP ; IMMEDIATE : REPEAT 'BRANCH , BACK) FORWARD) ; IMMEDIATE : AGAIN 'BRANCH , BACK) ; IMMEDIATE : UNTIL '0BRANCH , BACK) ; IMMEDIATE : AHEAD 'BRANCH , (FORWARD ; IMMEDIATE (FORWARD and friends can be reused in assembler looping and conditionals. from dx forth. : BEGIN here ; immediate : THEN here swap ! ; immediate : >MARK postpone begin 0 , ; : mark ; immediate : AHEAD postpone branch >mark ; immediate : ELSE postpone ahead swap postpone then ; immediate : UNTIL postpone ?branch