An avian carrier's blog – Forth

I'll follow Dave Ray and will try to say something nice about a bunch of programming languages I use or have used seriously:

• Ada – The only language I would trust my life to.

• C – It gets things done easily in a controlled space when resources are scarce. I use it in many embedded situations, often with FreeRTOS.

• C++ – Its templating system with specialization beats everything I know. When I worked on Urbi at Gostai, I had a lot of pleasure using it.

• Erlang – The language to use to develop distributable parallel applications. I wrote many programs for research projects with it.

• Factor – One of the languages I feel the most comfortable with. I really like the reverse polish notation and the powerful combinators. I use it for many personal and teaching projects.

• Forth – Forth is one of the languages that I have been liking since the first time I heard about it. Its conciseness, simplicity, grammar and ease of implementation beats almost everything when it comes to size on very small embedded systems. I used it to write a Forth compiler targetting the Microchip PIC16Fxxx microcontrollers family.

• Haskell – I started using it when I had to send patches for Darcs. I really love monads, and I also love explaining them in class. My window manager configuration is also written in Haskell.

• J – It is unbeatable if you have RSI and need to type as little characters as possible for a task that can be applied to a whole array. I use it mostly to solve Project Euler problems.

• Java – Well, everyone knows it so it may be used to explain a simple concept. Is that nice enough?

• Javascript – Javascript lets us do things in the browser I would not have imagined five years ago. For example, this web page is static but includes Twitter updates and comments, thanks to Javascript. On the server side, I use it within a CouchDB database where I store a whole web application; it dynamically generates iCalendar views for multiple people from data gathered at TVrage.com using their XML API.

• Python – I can hack anything in a few minutes and still be able to read it later. I wrote a Forth compiler for the Microchip PIC18Fxxx microcontrollers family with it.

• Ruby – Feels like Python, only more functional and cleaner. I would use it more if I had not been bitten by threading unstability on Sparc64Linux in the past (for the will-spam-for-food.eu.org service we ran with Pierre Beyssac and Thomas Quinot). Ruby helps me run this blog.

• Scala – There comes a useful, powerful and pleasant to use language targetting the Java virtual machine. I used it to write my HarassMe Android application.

I probably forgot some languages in the list. However, if I use them, I am sure I can tell something nice about them.

A friend of mine challenged me today to the number game. This is a classical one, where you have to guess a number between 0 and 999, and the computer will tell you whether you were right on or if you were above or below the chosen number.

Instead of doing dichotomy by hand or with a calculator, I wrote the following Forth snippet using the gforth interpreter:

: guess 2dup + 2/ dup . ;
: init 0 999 guess ;
: big nip guess ;
: small -rot big ;

Here is the transcript of an interactive session (what I typed is in black, what was printed by gforth is in red):

init 499 ok
small 749 ok
small 874 ok
big 811 ok
big 780 ok
big 764 ok
small 772 ok
big 768 ok
big 766 ok
big 765 ok

For those not well-versed in Forth, here is how it works:

• guess takes the low bound and the high bound from the stack, put them back there and adds the middle value as well, and prints it.
• init starts a session by putting 0 and 999 on the stack and calls guess to print the initial value to be entered.
• big removes the high bound from the stack, leaving only the low bound and the previous middle value, then calls guess to get a new value.
• small replaces the low bound on the stack by the previous middle value, and calls guess. The stack manipulation and the call of guess would be done using -rot nip guess, and I took advantage of big by factoring it into -rot big.

That’s it. Who could now pretend that small isn’t beautiful?

I was watching an Alias episode when I saw Jennifer Garner set a bomb clock to 4 minutes. At that time, I thought about my rforth1 compiler and realized that the code that writes a constant value into a timer register was probably doing things in the wrong order regarding the PIC timers internal latches.

It was an easy thing to fix. Thank you Jennifer for making me think about it.

I worked a lot on rforth1 lately, a Forth compiler targetting the PIC 18f family of microcontrollers. I have added many new optimizations in order to generate smaller and more efficient code.

Let's take an example. The Forth code below cycles through the 8 possible states of 3 leds connected to ports B5, B6 and B7 of a PIC:

\\ Define three words led0, led1 and led2 designating the leds

LATB 5 bit led0
LATB 6 bit led1
LATB 7 bit led2

\\ Use timer 0 to wait for 100ms (with a 40MHz crystal)

: tmr0-init ( -- ) $84 T0CON c! ;    \\ Enable timer, 16 bits, prescaler = 32
: 100ms ( -- ) -31250 TMR0L ! TMR0IF bit-clr begin TMR0IF bit-set? until ;

\\ Move leds -- when led0 goes to 0, switch led1. When led1 goes to 0, do
\\ the same thing with led2

: leds-init ( -- ) 0 LATB c! $1F TRISB c! ;   \\ B5, B6 and B7 are outputs
: switch-led2 ( -- ) led2 bit-toggle ;
: switch-led1 ( -- ) led1 bit-toggle led1 bit-clr? if switch-led2 then ;
: switch-led0 ( -- ) led0 bit-toggle led0 bit-clr? if switch-led1 then ;

\\ Loop indefinitely with a pause between each led change

: mainloop ( -- ) begin switch-led0 100ms again ;

\\ Main program: initialize the timer and the leds then run the main loop

: main ( -- ) tmr0-init leds-init mainloop ;

Here is the assembly code with the default compiler switches: (in order to keep it relatively short, I've omitted the declaration of constants such as LATB, which are included automatically, as well as the assembly file header)

; main: defined at example.fs:26
main
        call tmr0_init
        call leds_init

; mainloop: defined at example.fs:22
mainloop
        call switch_led0
        call _100ms
        bra mainloop

; switch-led0: defined at example.fs:18
switch_led0
        btg LATB,5,0
        btfsc LATB,5,0
        return

; switch-led1: defined at example.fs:17
switch_led1
        btg LATB,6,0
        btfsc LATB,6,0
        return

; switch-led2: defined at example.fs:16
switch_led2
        btg LATB,7,0
        return

; tmr0-init: defined at example.fs:9
tmr0_init
        movlw 0x84
        movwf T0CON,0
        return

; 100ms: defined at example.fs:10
_100ms
        movlw LOW(-31250)
        movwf TMR0L,0
        movlw HIGH(-31250)
        movwf (TMR0L+1),0
        bcf INTCON,2,0
_lbl___197
        btfsc INTCON,2,0
        return
        bra _lbl___197

; leds-init: defined at example.fs:15
leds_init
        clrf LATB,0
        movlw 0x1f
        movwf TRISB,0
        return
END

The assembly code is almost a one-to-one mapping to the Forth one. However, you may notice that the compiler chose to reorder the various parts so that fallbacks can be used between Forth words. For example, switch-led0 potentially falls back through switch-led1 because of the btfsc (test one bit and skip next instruction [return in this case] if bit is clear).

However, here we have not used a nice feature of rforth1 which is the automatic inlining of words if the generated code is either smaller or more efficient. With the automatic inlining turned on, we now get:

; main: defined at example.fs:26
main
        movlw 0x84
        movwf T0CON,0
        clrf LATB,0
        movlw 0x1f
        movwf TRISB,0
_lbl___219
        btg LATB,5,0
        btfsc LATB,5,0
        bra _lbl___220
        btg LATB,6,0
        btfss LATB,6,0
        btg LATB,7,0
_lbl___220
        movlw LOW(-31250)
        movwf TMR0L,0
        movlw HIGH(-31250)
        movwf (TMR0L+1),0
        bcf INTCON,2,0
_lbl___222
        btfsc INTCON,2,0
        bra _lbl___219
        bra _lbl___222
END

Isn't that nice? You can identify the various parts of the code: between main and _lbl___219, you get the timer and ports initialization. Between _lbl___219 and _lbl___220 is the whole logic of led switching. Between _lbl___220 and _lbl___222, the timer is reset in order to wait for 100ms, and the last three lines loop until the timer fires and then goes back to the led switching logic.

If you want to try rforth1, get it here, it is free and distributed under the GNU General Public Licence version 2. At this time, it has no documentation at all but comes with several examples that you can use as a template. And people who can understand French can read this tutorial written by one of the rforth1 users.

For the 2006 French robotics cup, I wrote two utility packages for GNAT, the GNU Ada compiler:

• areadline: access the readline library from Ada;
• aforth: embeddable Forth interpreter written in Ada (uses the areadline library).

I haven’t put a license file in them yet, but you can get them under the GNU General Public License version 2.

I feel quite ashamed of the pun on the name and the logo of my new Forth compiler…