Close

Recursive functions in Forth with STC

A project log for eForth for cheap STM8S gadgets

Turn cheap modules from AliExpress into interactive development kits!

thomasThomas 10/19/2016 at 21:330 Comments

STC, or Subroutine Threaded Code, is a Forth coding technique that implements the Inner Interpreter through simple CALL instructions. This convenient coding technique, used by STM8EF, comes at a price:

  1. increased code size: CALL + word address,
  2. some of the more nifty Forth features don't longer 'just work'

The code still is compact, no problem with that. It's the nifty features not working what bugs me ;-)

The Forth decoder SEE I fixed early on (mostly). The lack of the "Pearl of Forth" DOES> (which allows things akin to object oriented programming) bugs me much more.

In pursuit of perfection (and of code compilation to Flash) I experimented with fixing RECURSE, which, unsurprisingly, allows for writing recursive routines. Fixing it isn't difficult though: injecting CD, the opcode for a CALL instruction, into the generated code is sufficient.

The following snippet extends adds recursion to our humble STM8S Forth implementation. With the help of the new word RECURSE (which puts a call to the currently defined word into the generated code) we then define the well known recursive implementation of the Fibonacci function. Lastly, we call the function for the numbers 9 through 0, and print the result.

HEX
: RECURSE last @ NAME> CALL, ; IMMEDIATE
: fibonacci DUP 2 < IF DROP 1 ELSE DUP 2 - RECURSE SWAP 1 - RECURSE + THEN ;
 ok
: fibnums FOR R@ fibonacci . NEXT ;
 ok
9 fibnums
 55 34 21 13 8 5 3 2 1 1 ok

By the time I wrote these lines, I noticed that the STM8EF sources already contain a word "CALL,", which is actually implemented as ": CALL, CD C, , ;". However, due to a bug in the original sources it appeared as "CALL" in WORDS. This is fixed now. I also decided to replace "I" with "R@", which is idiomatic in eForth.

One hack more (recursive programming on a humble µC), and one bug less (pushed to GitHub).

Discussions