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).

Category of Stacks

In the usual category of types as objects with morphisms the terms of some language, the types are the usual base types and all types constructable from a set of type constructors. It seems that we would need a different kind of category for a concatenative language- one where the types are stacks with basics types, perhaps polymorphic types, and always ending in "Stack variables" indicating a "rest of the stack". This seems to be the usual way to consider type systems for these language, but I've never seem an investigation of the category this would form. Unfortunately, since I understand only the basics of even elementary category theory, all I can do is make some basic observations.

First off- The stack consisting of only a stack variable is terminal. It is terminal because you can always pop off anything from the defined part of a stack until you get to its stack variable. At first I thought it was initial too, because you can always add to the empty stack to get to a given type, but what would you add? At the least there is no unique term, and with polymorphic stack elements there is nothing reasonable to add at all. I don't believe that there is an initial object, unless there is some sense in which we can bind the "rest of the stack" to a given type, instantiating at any type we want. I'm not sure if this really makes sense, however.

Secondly- a stack with the elements of two stacks, the first stacks elements followed by the seconds elements, seems to form a product. We can always drop the elements of one of the two stacks to get the other one, which form the projections. Just as with regular type products there is an arbitrary order and an isomorphism swapping that order. Note that the terminal stack does seem to be the identity of the product, so that encouraging.

Thirdly- sums are a bit tricky. The only reasonable way I can think to form a sum is to take two stacks and push them as a single element of a sum type of stacks. This makes it a stack of stacks. Otherwise you would need to somehow "tag" parts of a stack that may be different lengths, and I don't seem how this would work. Its not a big deal to make this a stack of stacks, and I believe that has been done before, but it is interesting that if we don't do it that way then there are no sum types that I can think of. If we do allow this, it also seems like a similar product of stacks exists, But then we need a separate unit type as its identity as the empty stack would become the identity of the sum and the zero of the product.

A similar situation appears to occur with pushout and pullbacks, and limits and colimits. I can't make any of this rigorous, but it does seems to behave differently then regular categories of types, and is perhaps worth some study.

Monads on the Stack

What would a monad look like in a concatenative language? It seems that each of the usual suspects from Haskell have some sort of interpretation in this context, and may provide a useful addition to programs in such a language. However, so far I have not be able to see how to show that my interpretation actually forms a monad over a suitable category. So- how to formalize this and what does it look like?

Working somewhat backwards, I think I know what I want this to look like. Hopefully this will lead either to an understanding of how to formalize this or to some other formalization that is more suited to a concatenative language. I imagine that syntactically the space character is overloaded and is the equivalent of >>= in Haskell. The default monad is Id and has no extra properties, but you can select a particular monad, perhaps using the technique in the blog article (or blarticle) Scrap Your Type Classes.

To fmap a word into the state monad simply use Factor's dip or [ id swap | ] if "|" is the vertical composition operator I discussed in a previous post. The function "return" is slightly harder- it may be a word that take the top of the stack and returns a closure that puts that item under the top of the stack ( s -- a s ). The problem with this is that it seems to imply that while we are using the state monad we can only use the state and one item, which is a bit of a restriction if you are used to having a stack to manipulate. I was hoping this would be a way to have a state if you wanted it but otherwise to write normal words, but to do that it seems like you have to make the state monad "stack polymorphic" taking an arbitrary number of items from the stack. but then what does "return" look like? Does it save an arbitrary number of items? Or am I completely on the wrong track here?

Moving on for now, the reader monad is pretty simple. It simply provides a top of stack that you don't have to use, and will not change through a computation. For fmap we have "id swap |" again, but for return we have "drop ." if "." is the composition of words on the stack.

The writer monad should consist of words that leave elements of some monoid on the stack that are combined by the action of the monoid and are no visible to the next word. Simple enough, fmap is "0 ." if 0 is the identity of the monoid, and return simply puts an item on the stack followed by the monoid's identity element.

Maybe is also easy if we focus on the top of the stack- it is just like Haskell where you adjoint an element to a type and the presence of this element, in this case having it on the top of the stack, short circuits the computation. Otherwise the top of the stack is a Just value and is used as normal.

Thats all for now I think- I hope to write next time about an attempt to investigate what this means and in what category we are. Maybe then it will Just illuminate itself, or maybe I will have Nothing. Tune in next time to find out.

Vertical Composition

I've been thinking lately about designing a pure concatenative language influenced by Haskell to explore an idea I have about concatenative programs as diagrams. It would involve investigating how monads would work out in this type of language, as well as optimization and reasoning in terms of diagrams. I would probably try embedding it in Haskell and perhaps one day compiled to C. As part of this I've noticed an operator that I haven't seen in any concatenative languages (not even Factor, with all its awesome combinators) but seems like it might be useful. I call this operators "vertical composition".

Vertical composition is similar to the product of functions- if f:a->b and g:c->d then fxg : axc -> bxd (also written as fxg : (a,c) -> (b,d)). If these functions effect the stack, then their usual composition (which I'm calling horizontal composition and is written for f:a->b and g:b->c as g.f:a->c or f;g:a->c) creates a function that performs the the first function, and then the second. This means that the composition is valid if the stack after the first operator is a valid input to the second (possible requiring extra items deeper in the stack then the first function used). Vertical composition, on the other hand, is always valid just as the pointwise action of a pair of functions is always valid. Instead of operating sequentially, vertical composition acts in parallel (at least, conceptually) by performing the first function on the part of the stack that it needs, and the second function on the part of the stack just under that part used by the first function. The resulting stack is the result of the first function followed by the result of the second. I will write vertical composition as f|g, though I'm considering f/g, so we pronounce it "f over g". I will try to clarify this below, but the point is that you can reach under part of the stack without rearranging it. This would involve some amount of rearranging to arrange so the stack ends up with no "holes" where, for example, if f has stack effect ( a b - ) and g has stack effect ( c - c ) then f|g has stack effect ( a b c - c ). This would mean that the value c should be two places lower after f|g, which can't be known beforehand in a language like forth. If implemented naively as a stack this is a problem but the diagrams I mentioned earlier should remove any overhead of that kind. I hope to post about this strategy soon.

Something interesting about this operator is that the operations it composes could be performed in parallel. This isn't something I expect to see, but it is interesting that the horizontal form of composition is sequential and the vertical form is parallel.

Note that the vertical composition has the empty word as its identity and is associative, just like horizontal composition.

So, this operator is definable. Is it useful? I will write about that in a future post. The point is that this is the first step to a postfix program as a diagram.