The Transterpreter Project

Concurrency, everywhere.


Regarding Timers

We ran into something interesting the other day on the LEGO Mindstorms. In particular, something to do with time.

You see, the LEGO is a 16-bit machine. This means the largest number it can represent is 2^16 - 1, or 65535. This is OK in most cases, but I want to note that the LEGO's clock runs at millisecond speed. That means that it ticks over once per millisecond. The number of milliseconds we can count before the clock rolls over is... 65,535.

If there are 1000 milliseconds in a second, that means that we can only count up to 65 seconds before the world ends. Now, this is fine for James Bond movies (where the hero always has one minute to accomplish his death-defying task), but we kinda want to be able to measure longer amounts of time than that.

In occam-pi, we can do this in some very cool ways. So, consider this a brief introduction to timers in occam-pi, and more specifically, how we can neatly create timers that 'tick' at arbitrary intervals without too much effort. I'll continue this later in another post that explores how I build up to having timers that let me measure hours, days, weeks, and even months on the LEGO Mindstorms. For the moment, I'll start with some basics about timers.

To start, occam-pi has a notion of a TIMER built into the language. This is kinda cool. If I wanted to write a process that would delay for some number of milliseconds, it would look like this:

PROC delay (VAL INT timeout)
  TIMER t:
  INT the.time:
  SEQ
    t ? the.time
    t ? AFTER timeout
:

The process takes one argument, which is a timeout value given in milliseconds. The timeout value has a type, which is VAL INT. This means that it is an integer, and furthermore, we cannot change it---any attempt to modify this value will result in a compile-time error. In other words, we're saying it is a constant within this PROC.

We then declare two local variables: one of type TIMER and one of time INT. In sequence, we then read the current time into the variable 'the.time', and then use a funny bit of syntax to do our delay:

t ? AFTER timeout

This is some ugly stuff---something I wish they had done differently in the language. However, occam is over 20 years old, so we'll cut it some slack. This syntax says "delay until timeout milliseconds have passed."

And that's it. What's nice about this PROC is that it does not block other processes from doing their stuff. So, it effectively says "sleep, but let other people run around and do things." Very cool.

Now, we can't use this process to delay for more than 60 seconds or so, because the LEGO Mindstorms is limited by a maximum of roughly 65K milliseconds. Since I want to be able to do nifty things that involve timing out for more than 60 seconds, I want to start by writing a 'ticker' process that will generate clock ticks that I can listen for at intervals other than milliseconds.

PROC tick.generator (VAL INT delay, CHAN BOOL tick!)
  TIMER t:
  INT timeout:
  SEQ
    t ? timeout
    WHILE TRUE
      SEQ
        timeout := timeout PLUS delay
        t ? AFTER timeout  
        tick ! TRUE
:

This is only slightly bigger than the previous PROC. The tick.generator has two arguments---a constant (VAL INT), and a channel that carries booleans (CHAN BOOL). The channel is an output channel because it has been decorated with a !. (The compiler can figure this out for itself, but good style dictates that we put the ! on the channel end in the PROC definition.)

Again, I declare the local variables t and timeout, read the current time, and then drop into an infinite loop. This loop increments the timeout value, delays, and then outputs a signal on the boolean channel. Now, I can put this and a few other things together to create a complete program. This will execute just fine on your desktop, so if you paste it into your JEdit window, save it as "ticker.occ", compile, and run, you can see what it does. (Note that I've defined constants for SECONDS and MILLIS; on the LEGO, you would redefine MILLIS to be 1.)

VAL INT MILLIS IS 1000:
VAL INT SECONDS IS 1000 * MILLIS:


PROC delay (VAL INT timeout)
  TIMER t:
  INT the.time:
  SEQ
    t ? the.time
    t ? AFTER timeout
:

PROC tick.generator (VAL INT delay, CHAN BOOL tick!)
  TIMER t:
  INT timeout:
  SEQ
    t ? timeout
    WHILE TRUE
      SEQ
        timeout := timeout PLUS delay
        t ? AFTER timeout  
        tick ! TRUE
:

PROC tick.seconds (CHAN BOOL tick!)
  tick.generator(1 * SECONDS, tick!)
:

VAL BYTE flush IS 255:
PROC show.seconds.tick(CHAN BYTE kyb, scr, err)
  CHAN BOOL ticker:
  PAR
    tick.seconds(ticker!)
    WHILE TRUE
      SEQ
        BOOL tmp:
        ticker ? tmp
        scr ! 'x'
        scr ! flush
:

The last process, 'show.seconds.tick', demonstrates how we don't always have to name our processes to run them in parallel. First, I declare a channel to carry boolean values (remember, channels are like wires---channels carry information from one process to another.) Then, in parallel, I want to run the process 'tick.seconds' and an infinite loop that I've written. The process 'tick.seconds' gets one end of the channel 'ticker'---in particular, it gets the end of the channel that will be written to.

In the infinite loop, I do a few things in sequence. First, I declare a temporary variable that is only valid for one line of code. That is, it exists just long enough to read from the ticker channel into the variable 'tmp'. This is because I don't actually care about keeping that value, but I have to read from the channel into something. After reading from the channel, I output an 'x' to the screen, and then I flush the screen, so that the output is actually shown.

Remember that occam-pi channels are blocking channels. That means that my infinite loop will stop every time it hits the line 'ticker ? tmp'. It will wait until the process 'tick.seconds' has written a value, and then the loop can continue. Also, it is important to remember that every time you see a channel read (eg. 'ch ? var') or a channel write (eg. 'ch ! var'), the Transterpreter deschedules the currently executing process, and goes and runs something else. This way, everyone gets a turn to execute. This is why the delay process I introduced earlier does not block everything running on the system, and why we can write infinite loops as casually as I have here... because each one contains a channel communication.

In my next post, I'll follow up with how to extend this into timers that can last for days or even weeks on something as small as the LEGO Mindstorms. Also, I still need to follow up on our subsumption code for the Surveyor---but that will come, perhaps, after this timer exploration. In fact, this came up because we were trying to run our code from the Surveyor on the LEGO, and we discovered that having a 32-bit timer (like on the Surveyor SRV-1) is very handy, while having a 16-bit timer (like on the LEGO Mindstorms RCX) is a bit annoying... where "annoying" means "Hey! Our code doesn't work!"



Metadata

  • Posted: May 5, 2007
  • Author: Matthew Jadud
  • Comments: None
  • Tags: None