Using Forth/Copilot/FreeRTOS With the Arduino

After over a year of absence, I'm back to blogging. This time its about the Arduino and my continued quest to program it with something other then C. I've written multiple Forth-like languages for it, but I am yet to actually reprogram it with something like amforth. Instead, I've been investigating other languages one can use.

  The program I've been playing with is to get the Arduino to control RGB LEDs where each color's brightness is controlled with PWM. The setup only requires a handful of pins since the outputs are through shift registers. The point of this is to create cool light shows. My first attempt worked pretty well, but that was many months ago. I decided to try start over with the Forth approach, alongside a Haskell DSL to compile an array of opcodes that are stored in flash and run by a C program.

Forth:
   The C program can allocate "fibers" (cooperative threads) so each LED is handled by a separate task. This makes programming in this language pretty easy, and you can control different outputs this way (I also had a 7 segment display working with this scheme at one point).
  This whole scheme was fine, but it has a definite limit- on the Arduino you can't program flash (without changing the bootloader). This makes writing a Forth interpreter difficult. You can use RAM if you use a case-threaded interpreter, but you can't save words across resets unless you want to use the tiny 512 bytes of EEPROM. Using flash is okay if you are willing to accept a static program, but anything slightly dynamic (like allocating variables) would be awkward and clunky. Despite these limitation, I've been pretty happy with the simple light shows that I've been able to create. I'm definitely a much better embedded systems programmer, and I can see the difference in ability and understanding that my professional life has brought to these hobby projects.

 Copilot:
  My next attempt was with to use Copilot, a Haskell DSL for stream programming that can generate C code. You can do several other things with your programs, like verify their properties or interpret them, but I didn't look into those aspects of the Copilot project. The point is really about formal methods and software correctness, which is interesting stuff.
  Copilot programs specify a stream of values and tie them to your hardware with a little C, and the Copilot compiler takes care of generating most of the code and generating a schedule that updating everything at the required rates.
  This is pretty cool, and I managed to put together a program that does in fact blink LEDs. I eventually got PWM working, although there is something visibly jittery about it. I found that the schedule was meeting the 1ms timing, however, so it is probably a problem with my own code, not the efficiency of the generated code.
  Some cool things are- writing a latch (stream that holds the value of another stream whenever a boolean stream goes "true" and holds that value while it is false, figuring out how to divide down streams to slow the LEDs down so you can see them, and tying the languages together to add capabilities to both.
  Programming a little DSL like this is a fun puzzle (like puzzle-script) and I can appreciate the added safely of using a constrained language. The concept of a stream is a pretty accurate model of a lot of embedded systems, and I love being able to describe things directly rather then building up the same concept indirectly in C.

FreeRTOS:
  My next attempt was to use a port of FreeRTOS (http://code.google.com/p/rtoslibs/). This was fun, as the application structure can be made much nicer and we can express things like blocking directly. Its also fun to have a little operating system on my Arduino. I have an ISR giving a semaphore, a high priority task taking that semaphore, shifting out an output and periodically giving a semaphore, and a low priority take blocking on a semaphore and calculating a new output. This structure works well, and I would like to play around with it more.
  The problem with the Arduino Uno is its tiny tiny memory. Tasks and semaphores and scheduling and other mechanisms take up space, and there is not much to be had here. So far I still have 1343 bytes left, which is (relatively) good. A couple more tasks, a message queue, and a data structure and I'll use it all up, though.


 There is more to come with my Arduino. I have lots of plans.

Vault Library

The Vault packet on Hackage by Heinrich Apfelmus is quite cool. Type-safe, persistent storage of arbitrary values!

A vault is a map from keys to values, but the keys are parameterized by the type they return. This allows one to retrieves values from the vault that have any value without specializing the type of things the vault stores. How this works behind the scenes is quite interesting, but basically the keys are what store the values in a sense- they store an IO action of type IO () that stores a value in an IORef when it is run. The key keeps a unique value indicating to the vault which IO action to run, and the IORef that is updated. The is possible through the "scary action at a distance" described here: http://apfelmus.nfshost.com/blog/2011/09/04-vault.html.

I think this may be a good choice to implement a modular evolutionary algorithm framework, since it lets individual components (genetic operators for example) set and retrieve configuration information without having to add their desired configuration to the type of the configuration structure (which otherwise seems inevitable).

Discrete Optimization Course at Coursera

I've just started a Discrete Optimization course on the Coursera website. It looks interesting, and I would like to have a firmer understanding of more traditional optimization, given my interest in biologically inspired optimization algorithms.

I'm also looking at a course on analytic combinatorics. My understanding of combinatorics is weaker than I would like, and my understanding of analysis is much weaker then I would like. I'm hoping a class like that would do me some good.

I am hoping this class provides some topics for this blog. Looks like the first problem they talk about is the knapsack problem.

Haskell, Netwire, Gloss, and Swarms

I've been playing around with the Haskell libraries Netwire and Gloss. They are both very nice- Gloss is an incredibly easy way to get something graphical up and running, and its been easy to integrate it with Netwire to get an FRP style simulation going. I've been playing with swarming mechanics, trying to figure out what makes a good looking swarm (and trying to make sure that swarm looks good even when its doing something like following your mouse cursor).

In case your wondering, my choice of Netwire vs some other library for FRP in Haskell was mostly motivated by it being simple. I understand how it works, and I've not had too much trouble getting something small written with it. I'm not going to comment on how it compares to other libraries in any other way but to say that I found it approachable.

The concept behind the program is that a swarm is a list of boids, each with a position and velocity. The position is the sum of the velocity at each time step, and the velocity is the sum of each acceleration at each time step. The accelerations are produces by operators that are given the current swarm, and produce an acceleration for each individual. For example, the cohesion operation takes the centroid of the positions, and produces an acceleration for each individual in the direction of that centroid. The random operation simply produces random accelerations.

This is admittedly not the easiest way to program this kind of thing, but I like the idea of FRP and I want to incorporate it into something larger. Getting started on something small like this has helped me understand how to use FRP (to specify the value of something over time) and familiarized me with Netwire, the FRP library I'm currently using. Hopefully on a larger scale this approach will pay off by letting the components be more modular (including having local state) and the overall flow of control more clear since it is specified by a single abstraction (a flow network).

Good times are ahead, and I think the time has come to wake this blog up.

Idris is Pretty Cool

I've been reading recently about a programming language called Idris. Its similar to Haskell, but with dependent types. It is intended to be a practical programming language rather then a theorem proving language or a proof of concept, and there are papers about applying it to systems programming. That is one of my interests in dependent types- increasing the safety of complex programs that involve things like communicating with hardware. I use C to do this professionally, and I find that it is difficult to get this kind of programming correct every time with all the complicating factors. There are often times that I could express more about the structure of data or the flow of the program with a better type system. Dependent types have a lot of potential, and I would love to see them make their way into the kind of work that I do.

I may have to post about dependent types in the future, as they are probably the biggest thing that I know about in the functional programming community right now. They represent a real change in the use of programming languages and how one thinks about programming, and I for one am in favor of this change.

Arduino LED Language, part 2

The LED language for the Arduino is still changing quite a lot. I've gotten rid of the whole cooperative multitasking thing in favor of a simpler interpreter that is now just a switch threaded Forth. As it gets more advanced I'm faced with some problems- whenever one designs a domain specific language there is the problem of how much power to give it. Right now it does not support variables (constants are supported but not built in) or any sort of parsing words or anything interesting like that. I'm running into the problem that Forths have on the Arduino, which is the problem of having your program stored in flash and running it out of RAM. I will probably just add some simple hacky variable system to keep things from getting out of hand complexity-wise (indices into an array that get expanded to accesses at compile time or something).

In terms of progress it has conditionals and loops, and supports execution tokens (the Forth term for this idea) aka function pointers aka almost higher order functions (with no combinators to construct new ones at runtime). Unfortunately it does not support getting the execution token of built in words, which is a pretty arbitrary distinction.

Incidentally, I have it working with a full 5 RGB leds, controlling all 15 pins nicely. More things need to be added to the language to get complex animations, but as it is one can fade leds, set colors, and having sequences of blinking lights.

Thats all the updates I can think of for now.

LED Arduino Language

A friend of mine has come up with a project involving RGB LEDs where it would be cool to be able to "script" their color, possibly animating them over a longish period of time, with multiple possible animations. To do this, I've come up with a system that is essentially 15 cooperative multitasking threads interpreting a stack-based language that I've also embedded into Haskell for some meta-programming goodness. Together, these threads control the intensity of each color of each led (we plan to have 5 of them, 3 colors * 5 leds = 15 pins to control (intensity is controlled by pulse-width modulation controlled through an interrupt attached to a timer)). This post merely records the fact that this idea actually does work, and I can control the color of the first RGB LED attached to my Arduino on my desk here.

Pretty neat, though there is much work to do. I need to make sure the idea scales, possibly optimize a bit, get the embedding into Haskell nicer, make some more complex animations, add more to the language itself, and possibly write a parser and make it a standalone language to make the scripts look nicer. I would also like a mode that allows the user to control the colors, so I need to figure out how to do some input 9the programs are read from flash with no input from the user at the moment).