Extending Tamarin Tracing with Forth

My previous article on extending Tamarin Tracing with native methods described how to implement the native methods in C. It's also possible to implement native methods in Forth.

Methods implemented in JavaScript are compiled to ABC bytecode by a compiler (currently the asc.jar provided by the Flex SDK). These are compiled to the basic Forth instructions by the Tamarin Tracing engine and those Forth instructions are run by the interpreter. 'Hot' areas of the Forth instructions are traced and compiled to native machine code as needed.

Methods implemented in Forth don't need to be compiled from ABC to Forth. They are immediately available for interpreting and JITing via the tracing mechanism. I'm a little unsure of the exact pros and cons of implementing things in Forth vs C vs JavaScript and would be interested in comments if anyone can help.

As an example of a method in Forth I'm going to use the same fibonacci function in my previous article. A Forth method is marked 'native' just like a method implemented in C. But it has some metadata associated with it to say it is implemented in Forth, and to give the name of the Forth word (in Forth terminology a 'word' is a 'function'):

package testing {
  public function fib(n) {
    if( n <= 1)
      return 1;
    else
      return fib(n-1)+fib(n-2);
  }
 
  public native function fib2(n:int):int;

  [forth(word="forth_fib3")]
  public native function fib3(n:int):int;
}

Notice the 'forth(word="forth_fib3")' metadata annotation. This tells the asc.jar compiler that the following native function is implemented in Forth by the word 'forth_fib3' rather than in JavaScript or C. I placed this code in 'fib.as' in the 'shell' subdirectory and modified 'shell.py' to build it in exactly the same manner as my previous article.

The 'forth_fib3' word needs to be written. The Tamarin Tracing Forth compiler is implemented in 'utils/fc.py'. It is a 'whole program' compiler in that it needs to have all Forth files listed on the command line so it can analyse and compile everything. The invocation of this compiler is done in 'core/builtin.py'. This means any Forth extensions really need to be added to the 'core' subdirectory and build files. I added a 'core/fib3.fs' as follows:

: fib3 ( n -- n )
  DUP 1 <= IF DROP 1 ELSE DUP 1 - fib3 SWAP 2 - fib3 + THEN ;

EXTERN: forth_fib3 ( obj n argc=1 -- int )
  DROP NIP fib3 ibox ;

The 'forth_fib3' word is implemented using EXTERN:. This marks it as a word that is an available entry point by external code. The arguments it receives on the stack will be ( obj arg1 arg2 argn argc=n -- result ). In the fibonacci case there is one argument, the number passed to fib. The argc argument is the count of the number of arguments provided, in this case 1. The bottom argument on the stack is the object the method is called on. Since our fib function is 'global' and not part of an object this is not used hence the NIP to remove it.

Note that the stack effect names (the obj, n, argc=1, etc) are for documentation purposes and are not used by the compiler at all - just like most other Forth systems).

So 'forth_fib3' removes the argc and obj arguments and uses just 'n'. It calls a helper function 'fib' which does the actual fibonacci calcuation, leaving the result of that on the stack. The call to 'ibox' tags the final result as an integer number.

'fib' is a pretty standard Forth implementation of fibonacci. It uses IF/ELSE/THEN to do the testing of the number. IF/ELSE/THEN is implemented by the Forth compiler directly (fc.py) since the Tamarin Tracing Forth system doesn't have parsing words.

'core/builtin.py' needs to be modified to include 'fib3.fs' as an argument to the compiler:

 os.system("../utils/fc.py -c vm_fpu prim.fs fpu.fs vm.fs e4x.fs fib3.fs")

There are multiple invocations of the compiler for different variants of the virtual machine (without fpu, minimal VM, full VM, etc). Each of these should be changed.

Running 'core/builtin.py' will compile the Forth code and generate the necessary code. Follow this up with running 'shell/shell.py' to compile the fib.as and other code and build Tamarin Tracing as per my previous article.

Some simple test code:

import testing.*;
print("fib3 30 = " + fib3(30));

With equivalent test functions for the other implementations of fib you can compare the different runtimes:

$ time shell/avmshell fib.abc
fib 30 = 1346269

real    0m0.298s
user    0m0.252s
sys     0m0.032s

$ time shell/avmshell fib2.abc
fib2 30 = 1346269

real    0m0.063s
user    0m0.024s
sys     0m0.028s

$ time shell/avmshell fib3.abc
fib3 30 = 1346269

real    0m0.192s
user    0m0.144s
sys     0m0.024s

As can be seen in the times the C implementation smokes the other two with the Forth code being faster than the JavaScript code.

The Forth implementation has features I haven't explored in this article. This includes different ways of declaring words to take advantage of various optimisations and automatic generation of superwords. It is a 'static' Forth compiler in that it doesn't allow the execution of Forth words at parse or compile time so features like parsing words, CREATE DOES>, interactive development, etc are not available. This makes the implementation of Forth words a bit more verbose than in more full featured Forth implementations.

If you have any tips on using Forth in Tamarin Tracing please leave a comment. I'm keen to see more features of the Forth system is use.

Categories: tamarin, forth