Controlling an Arduino from GForth

I have been working recently on a way to control my Arduino Uno from GForth, and it is turning out pretty awesome. I've written a sketch for the Arduino that reads simple commands over the serial bus, performs their action (using a large switch statement) and returns a result. From the computer one can type something like "13 HIGH digitalWrite" to turn the LED on, or "10 arduinoMalloc" to allocate memory and get the address of the allocated block.

This project has come out of my failed attempts to write a Forth to run *on* the Arduino. Instead of accepting that the limited resources on the device restrict what you can do, I decided that it would be nicer to use a much more powerful computer and a fully general programming language and treat the Arduino as a peripheral that can be commanded. This lead me to the command-reponse protocol I've implemented.

Of course, you have the full power of Forth, so you can do anything you want, but the functionality that the Arduino currently exposes this way is: reading and writing SRAM, reading and writing EEPROM, allocating and freeing memory, setting the mode of a pin, reading and writing digital pins, reading and writing analog pins, delaying by a given number of microseconds, generating random numbers and random numbers from a given range, and setting the baud rate of the usb connection. This is pretty much all the functionality I can test right now without finding some hardware, but it is really easy to add new commands so I certainly will expand this set when I can think of something to add (suggestions?).

The tool as its stands only works in Linux (I had some trouble on Windows, but I may come back to it) and can take a device name and baud rate on the commands line. There is also a command line switch to compile and upload the current version of the command interpreter to the Arduino. Once started it is simply the GForth interpreter with some words for sending the commands mentioned above, as well as error handling on both the Arduino and the GForth side of things.

The Arduino sketch will currently reject invalid commands, invalid command lengths, and invalid arguments with an error code. The GForth side throws an exception explaining the problem and printing the result given (the length received by the Arduino in the case of an invalid length, for example). The Forth words that send commands will also check if the command has been defined yet, and will complain if it doesn't understand the result the Arduino sends back.

There are at least two ways I can think of this program being useful. First is to command the Arduino to do something complex or that may change over time or depends on information available to a laptop, say, but not the device. I'm hoping to think of a project like this to demo. The second use is in the fact that the whole thing occurs in the serialEvent function. This means that if you have a main loop that does something with the Arduino, but you would like to debug you program at runtime with a full interactive programming language that can peek and poke memory and sample inputs and outputs, then you can send commands at any time to do this. I feel like this might even be the most useful application, but I don't have anything right now that needs this kind of interactivity.

Things I would like to add- 32 bit arguments (currently everything is 16 bits), saving commands to eeprom to read at startup, control structure commands, grouping commands to send all at once instead of one at a time, some way to register commands to run repeatedly so you don't have to keep sending them, and an assembler that uploads to flash or eeprom and reads the uploaded program at startup. I think this might be one of the cooler applications- you could program in assembly on the Arduino and still use sketches, and without overwriting the bootloader. This relies on being able to write to pages of flash, and I don't know how to do that yet, but still a cool idea.

Thats it for now. This project so far has been very pleasant and opened me up to how nice Forth can be if you use the Forth Foundation Library. I have had some bugs, but interactive debugging and a quick testing cycle has made them much easier to track down then I would have expected. As usual with my posts- I hope to write more about this soon!

Forth Foundation Library

I've been writing a lot of Forth code recently, and I've discovered that using the Forth Foundation Library has been incredible boost in productivity and simplicity for me. It raises the level of abstraction beyond what I'm used to in C, and makes Forth really pleasant to program in. Anyone interested in using Forth beyond basic toy programs needs to consider this library. I'm currently using the linked list, cell array, argument parsing, enumeration, and format string modules, but I have plans to use at least the random number generation one and possible n-ary tree ones as well. I may even consider playing around with their GTK module, which looks interesting, and the finite state machine ones (there is both deterministic and nondeterministic).

Forth Interpreters and the C Stack

I haven't been working on my Forth project for a while, but I'm coming back around to it recently, and there are some things I want to change. One of these things is to start using a variation on a technique I saw in the paper "Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine". In this paper they give a single line interpreter for their machine: "while (TRUE) { cont = (*cont)(); }" which simply calls the function pointer cont, and expects the function to return a new function pointer. This has the advantage of always cleaning the stack up after every function call, preventing it from overflowing or from having to throw it away occasionally.

The plan as of right now is that instead of always returning the next thing to call, the looping interpreter will simply do the action of "next"- it will copy the current IP (Instruction Pointer) onto the return stack, copy W into IP, increment IP, and call the function W points too. All functions will return nothing and the threading will be taken care of for them- they do not have to each have the code of "next" as I've done in the past.

I'm also going to change how the original dictionary is compiled. Before I was doing some pretty tedious manipulation of an array of cells (integers) for some reason. Instead of this, I will use a word struct of fixed length (the name will be a pointer to a character string rather then the string itself- this makes finding the xt of a word easier). I don't know why I didn't do this before, but it should be simpler and cleaner now.

I've been thinking about what I'm going to do for structures in this Forth. I don't want to use objects particularly, so I'm going to be thinking about how to do reasonable algebraic datatypes in Forth. It will probably involve runtime checking of types. I've devised a scheme for doing classes in the Haskell sense which I will post about, but its in the planning stage and I may abandon the idea at any moment.

I'm looking forward to cleaning up the implementation and getting it actually running so I can start exposing hardware functionality and adding threading, interrupts, etc.

Breaking the Forth Wall

I've made yet more progress on my stand-alone Forth for the x86. I wanted to mention some interesting things about forth real quick while I work out some problems with the call-gate style of key handling and add DOES> words to the language.

There is some very interesting things about Forth as a language. It can very easily support simplified versions of some very powerful features from other languages such as coroutines, continuations, exception handling, closures, and object-orient features. Often these sorts of things are implemented in a similar spirit to other features in a Forth like memory management- the programmer takes more responsibility for her code than usual and the implementation is a simple one that has good enough characteristics to work for what the programmer needs. I could certainly program in Haskell and get all of the power I want in a language for most tasks, but Forth is interesting because it does these things in such a low level context, where we have access to every part of the system and can play with them as needed for whatever we want. For example, we can use the return stack to implement coroutines with a word as simple as ": yield r> r> swap >r >r ;". This will continue the word that called us, which can do the same thing to continue the word called. We might not get everything we want out of this type of implementation, and we have to be very careful to not mess things up, but its pretty good considering we are just above assembly language in terms of abstraction and we have to build everything ourselves.

Another thing I wanted to mention is that there seems to be some relationship between stack languages and functional programming. It is very natural for concatentive language to be seen as functional language where the main operation is composition rather than application. Notice that whitespace represents application in Haskell, but represents composition in Factor, Cat, Joy or Forth. Also, the concept of a graph reduction machine (which is used to give operational semantics to functional programming languages) apparently has found fast and very natural implementations on stack machines where the graph is compiled code (rather then traversing the graph structure with separate code).

In addition, I've been reading Moving Forths section about DOES>, explaining probably the most complex part of Forth, and they mention that the use of code fields in some ways anticipates object oriented programming. This reminded me of the STGM (Spineless Tagless Graph-Reduction Machine) which is Haskell's abstract machine and is implemented as its run-time system. I remember reading that they used essentially a code field to determine what to do with their objects (in the more general sense of entities in a program's memory) rather then tagging them with types and switching on the type (the tag is just a pointer to code that does the Right Thing). This is exactly how variables, constants, does words, and regular words are implemented in Forth. Its probably a well known technique, but Forth must have pioneered it.

Hopefully next time I will have an actual progress update and won't have to resort to a pun for a title.

Forth Progress Update

My standalone Forth for the x86 is coming along nicely. I make little bits of progress every time I work on it. Right now it can compile new words, variables, and constants, as well as do simple arithmetic. The command line interface needs work, but it already displays the system state (compile = 0, interpret = 1) in the bottom right corner of the screen, and shows the top 5 items on the stack on the bottom left corner (with the top of the stack on the right).

The next things I want to tackle is to factor out the screen information, the command line information (to which I want to add a command history so I can press down and up to cycle through commands), and so attach to each key a forth word call-back. I want to talk a little bit about that in this post.

I want different keys to do different things, and I would like to be able (when the system is better developed) to attach an arbitrary forth word to a key. When I say attached I mean that the each key gives you a fixed integer value, which I use as the index into an array of characters to get the character value (the keyboard doesn't just give an ASCII value). In addition to this use of the key as an index, I want to also index the integer given into an array of execution tokens (which are basically forth's equivalent of function pointers). The interpreter would read in a single character from the keyboard and call the word (function) in the character's index. This would allow me to customize the keyboard easily, and may help when I (waaay in the future) add a text editor. Most of the time keys will be attached to a word that calls putch (put the character on the top of the stack to the screen and move the cursor one position over), but keys like enter, the arrows, backspace, and possibly other will need special handling that is done as part of the outer interpreter right now and can't be configured easily.

One interesting use of this is to have many threads, each with a piece of memory for a screen and their own command line information, and to tie one to each of the function keys (F1-F12) to get virtual terminals. This would be a fun feature even while this is still a single threaded system. Way in the future I will read the APIC documentation (possibly HPET also?) to get a preemptive round robin going, but I would like at least a simple memory manager going before I allocate much fixed stuff on the heap (which is everything above the 3 MB mark right now, with the kernel at 1 MB and the system dictionary at 2 MB).

Well, that is enough for today- I have lots of fun things to work on! I love the response you get from adding features to a system like this with quick turnaround and useful results.

Inner Interpreter Works!

Progress update on my standalone forth- the inner interpreter works! I can compile primitive words and the threaded interpreter will run them to completion. If I start out with QUIT on the return stack, with some word's execution token (the location of its array of function pointers) in the IP register of the virtual machine (meaning the IP variable of a struct) and call next then the word will run and the program will block waiting for user input. This is because QUIT clears the return stack and starts the outer interpreter. The outer interpreter needs work, and I'm trying to get word lookup, compilation, and interpretation working.

Right now a word is arranged in memory like so- last_word, flags, length, characters..., function pointers..., exit.

The last_word is a pointer to the previous word in the dictionary of words. This means that each definition is linked to the last, up to the very first, which is linked to NULL. The characters are actually held in a cell length (4 bytes) for convenience. I'm willing to throw away memory for this system because I expect to use less than a single percent of my 2 gigs, so space is not a problem. If I packed them tighter than I would want to align the function pointers to 4 bytes, which would mean calculation the length of the word's name mod 4 and adding that many unused bytes at the end of the characters part of the definition. This is simply more work to save some bytes.

I'm working on getting numbers and words to be recognized and for words to be looked up and compiled or run. After that I will be able to extend the dictionary beyond a couple of single words and get this project on its feet. I'm hoping to also look into doing a preemptive round robin threading mechanism, as well as multiple terminals, a block file system, and a text editor. Big plans!

Forth Indirect Threading

Every time I want to remember how the inner interpreter works in Forth, I have to read the first part of Moving Forth again, so I thought I would record my thoughts this time for future reference. This is going to be in the context of my current project- YMMV.

The Forth inner interpreter consists of: next, exit, and docol (aka enter). There are two types of words- primitives and higher words. Primitives are machine code (C for my project) and higher order words are lists of other words (possibly also higher order). In ITC all words start with the location of some primitive functions. For primitives this is the code to execute the word, which must end in a call to next. For higher order words the first pointer is to the function docol, and the last a pointer to exit. The forth vm has an instruction pointer, IP, and a working register W (I plan on also having registers A and B, and possibly X and Y for indexing). When the outer interpreter has a word it needs to execute (entered by the user and looked up in the dictionary) it places the quit word on the return stack, sets IP to the execution token of the looked up word, and calls next.

Next copies what IP points to into W, and moves IP to the next cell over. It then calls the function that W now contains a pointer too. If this is a primitive then that function is the primitive itself, which executes some function. It must end with a call to next, which starts the process again. If all words where primitives, this would move the IP along the array of pointers until hitting exit. If a word is higher order, however, then the first function is docol. This function pushes IP unto the return stack, copies W to IP (as W contains the pointer to the docol pointer) and moves IP over one. It then calls next, which starts executing the current word just as before.

When exit is reached, the top of the return stack is popped into IP, and next is called to continue executing the next word up in the call tree.

If the return stack reaches the very bottom, where the outer interpreter places the pointer to quit, then the last exit will call the function quit. This function will clear the return stack (in case it is called in some nested context) and will clear the C frame stack (in my case) with some inline assembly. It will then call the outer interpreter to start up again, which will wait for user input.

Forth Threading Models

In the last post I gave one possible motivation for threading. Now I would like to go over a couple of techniques that can be used to achieve this affect. For more detail, see "Moving Forth" at http://www.bradrodriguez.com/papers/index.html, which is an amazing reference.

The first model is Direct Threaded Code (DTC). In this model, each subroutine (word) contains machine code. If the word is a primitive, this code is just the implementation as an assembly subroutine. If this is a high level word, and therefore only contains calls to other words, then the machine code is a push of the next instruction and a jmp to a subroutine that will start calling each address, one after the next. This would look like:

call DOCOL; a; b; c; NEXT;

Where DOCOL is the subroutine that calls each of a, b, and c (addresses of subroutines) in turn. NEXT is the address of the instruction that keeps this whole process moving- if we have entered a word from another word it will leave the current word and move one step outwards in the nesting. I will be explaining the various stack in a later post, so just know that NEXT handles cleaning up at the end of a word.

Another model is Indirect Threaded Code (ITC). In this model, a word must always contain a list of addresses of other words. This means that even the most primitive words must contain a pointer. Such a word might like (assuming the word starts at address 0x8000 with 32 bit cell sizes):

0x8004; add r1, r0, r1; call NEXT

This word simply jumps to the next instruction, as its require to jump somewhere. The actual action is to add two registers, and then call NEXT.

Another technique is Subroutine Threaded Code (STC). This one is a little bit ironic, as it "threads" the address by simply making each one a call. The disadvantage is that it may take up more space then other techniques as each address is actually the call instruction. Remember, however, that the original motivation here was to remove these redundant calls. While at one time it made sense to save that little bit of memory, now it may make more sense to increase speed by removing this extra level of indirection and just make all jumps subroutines calls. Another advantage here is that primitives can just be machine code- we always jump to a word like DTC. The word NEXT may literally be just "ret" or return as we are just doing the usual jumping to an address while storing the instruction pointer call we can do the usual return to the last subroutine by popping the return stack to the instruction pointer.

Yet another technique is token threading. In this technique a word is an array of values that aren't themselves addresses to other words, but are rather indices into another array of addresses of words. The only real advantage to this technique is that it can be used to get very very small compiled words- a table of only 256 words can fit each "token" (index) in a single byte. The problem is we have yet another level of indirection to wade through, and the number of words is limited to the size of the table. I don't like this technique very much as it also makes the structure of the dictionary particularly fixed (we will get to the dictionary later) and that makes some interesting things much harder.

While there are more forms of threading, I'm only going to discuss one more- switch threading. This technique is basically what a lot of bytecode interpreters do- they have a massive switch statement that determines what do with a compiled bytecode.

Well, thats it for now. I believe I will be doing a ITC interpreter for my new Forth, simply because it is easy to place pointers to functions in C. I'm considering playing around with the C stack a bit, but for now I'm looking at each word as an array of pointers to void functions with no arguments.

Forth Threading Models, motivation

I will be posting a lot more about Forth nowadays, as I work on my standalone Forth for the x86. First off I would like to talk about threading models, starting with some motivation.

Many languages have some abstract machine model that gives them some sort of semantics (sometimes rigorously, as an the operational semantics of Haskell in the STG Machine, and sometimes informally, as in Java's JVM). Forth has such a machine, which gives a basic idea of the things that a Forth system should do without specifying implementation details. This post, and hopefully many more in the future, is about that abstract machine as I understand it.

When writing a program in assembly, we may write a large number of subroutines to do trivial tasks, and to reuse these simple subroutines to define higher level routines. The higher level routines will consist largely of calls to other routines. Imagine we have a pretty resource constrained machine, and we are looking at a program that looks like this:

call a

call b

call c

ret

Which uses some "call" instruction, or if there is no "call" then it must push the instruction pointer (so we can return to it later), and then jump to the subroutine. We are imagining that a major concern is memory usage, so we immediately notice that there are a lot of calls. Why keep all of the instructions around if we are just going to call each address anyway? Instead of having these explicit calls, we could just have

call run

a

b

c

end

This requires a little explanation, especially as I've just made up "run" and "end". What this code is suppose to suggest is that we call a subroutine called "run", which is written once and used many times, which will look at the instruction pointer on the stack (pushed by the call instruction) and run that code. When that code returns, run will call b, than c, than end. The subroutine "end" is another one that is defined only once, and it will do any clean up necessary, which may just be a ret like a normal subroutine.

So we added a little wrapping around the bunch of calls, with the call to a special function to start and the address of a special function to end it off. If your program consists mostly of such lists of calls, then there is some savings of memory here, but that turns out to be a side note today. Now we have plenty of memory, often even in embedded systems. This technique turns out to have other advantages, however, and gives rise to the basic notions of the Forth language.

Okay! Thats enough for now I guess. I was hoping to get into threading techniques, but maybe next time!

First Ever Successful Boot!

I'm restarting a project that I tried a few years ago- to write a stand-alone forth operating system. The complexity of the x86 processor has stopped me in the past, but this time I am more prepared. Another thing that has stopped me is getting a kernel to actually boot on a real computer. I've gotten them to boot on emulators, but for some reason I could never do it on my desktop. Well, this has finally changed! I got grub2 to boot a kernel image using tutorials from osdev, where the kernel simply prints NOAH to the screen (the hello world of hobby os development seems to be to print your own name to the screen).

This is great news! All the starting up stuff has been keeping me back for a while, and I still have a lot to get worked out (interrupts, memory model, memory protection, and keyboard controlling) but now I can start actually working on it and not have that nagging worry that I won't be able to boot it even if it works in an emulator.

I am trying to keep everything simple here- there will be no restrictions to memory, it will be mono-tasking at first (forth multitasking isn't super hard, but I need something to work with first before I go there), and I don't intend to support anything but a keyboard. One major difficultly is disk access- I would like to support a block file system, possible with largish block (4KB rather than the usual 80*25 to store a screen) or maybe not, I don't know. The problem is accessing the hard disk- a possibly complex operation that I don't know anything about. I would be okay with a partition that is organized into blocks, or a file on another file system that is loaded as a full block files system- which would be really neat because I could edit it in Linux as a text file, and load it as part of the operating system. The problem of course is I don't know how to do this either.

So in conclusion- YAY! I finally started this project! Its been forever! I'm planning on using it mostly for fun, but also as a way of getting more comfortable with C, which I will be using a lot in the future. I was going to just use assembly, to take complete control of the system and make the Forth registers the actual machine registers and all that like in my previous forth system for the z80 of my ti-83 calculator, but I decided it would be easier, and possibly more instructive for me to use C to learn about using it as a systems programming language.