Cliff Hacks Things.

LPCxpresso: nice hardware made useless by bad software

2010-01-29T18:17:00.000-08:00

Remember back in the mid-90s, when many of us used Microchip PICs for embedded control? Remember having to use a shoddy closed-source compiler, which only ran on one operating system/architecture? Remember having to use a particular set of tools, instead of whatever tools you were most comfortable with?

Fast-forward to 2010, and you can re-experience all these limitations with the NXP LPCxpresso board! This evaluation board for the NXP LPC ARM chips is...well, I'll let them speak for themselves:

The LPCXpresso evaluation board is meant to be used only with the Code Red LPCXpresso, or Red Suite IDEs.

This runs only on Windows, of course. Yes, folks, it's like 1995 all over again. ~~Consensus among reverse engineers I've contacted is that the programming/debugging interface is cryptographically secured, to keep you from using it the way you want.~~ (Edit: I've decided there's not enough evidence to support this claim.)

Not that Digikey tells you this before you buy, of course! At the time of this writing, even the LPCxpresso web site makes no mention of this, unless you drill down into the PDF Getting Started Guide. Fortunately, competing parts from both Atmel and ST Microelectronics have support for GCC and cross-platform programmers and debuggers. I'll be using these in my next design and sending the LPCxpresso back to the factory.

Update: Someone claiming to be from Code Red commented below, noting that they do have GCC support, but didn't address the other points (cross-platform compatibility being the main one). I based my initial complaints of "no command line compiler" and "no GCC support" on other users' summaries, since (not having Windows) I couldn't test that. My bad; these claims have been removed.

If Code Red does indeed provide cross-platform support (or OSS tools that could become cross-platform) I'll update this post!

Update 2: They do not, though they suggest I could run Windows in a VM. Missing the point, guys.

To be clear, I'm not a complete noob to embedded ARM systems, or Cortex-M3. Once I decided not to return this proprietary piece of circuit (because I'm terribly stubborn), I tried putting together a toolchain based on CS2009q3, writing a linker script, soldering on a USB connector, implementing the proprietary NXP checksum algorithm, chopping off the debug circuitry that I paid for and would sure like to use, etc. Never quite worked right - got consistent firmware corruption. My point is that I shouldn't have to do any of this stuff, or troll through forums trying to decide which contradictory answer is correct. I'm currently rather enamored with the mbed eval board, which, unlike the LPCxpresso, explicitly supports Mac and Linux out of the box.

Linear-scan register allocator adapted

2008-12-09T21:32:00.000-08:00

I've adapted the SSA Linear-Scan allocator, originally designed by Mössenböck and Pfeiffer for Hotspot, for my Propeller Java compiler.

It has some advantages:

It's simple.

It's fast.

It does a pretty good job.

It can deal with destructive arithmetic ops (as in the Propeller) and pre-colored registers (as in calling conventions) easily.

Handling pre-colored registers well is particularly important to me, since I'm trying to do all lowering and allocation without leaving SSA. This includes the calling conventions. With this algorithm, it's a matter of

Before each call, insert extra movs to clone each argument value. Pre-color these clone values with the appropriate registers in the calling convention.

After each call, rewrite the return value to go into a temporary, which is pre-colored with the returned-result register, and which gets immediately mov-d to the right value.

Rely on the phi-equivalence coalescing algorithm (still adapted from Pereira) to merge the non-interfering values and eliminate the copies.

I've altered Pereira's algorithm to deal with the "join families" that Mössenb&oml;/Pfeiffer generate. (Arguably in doing so I've recreated their coalesce algorithm, but hey.)

Here's a new test function with some interfering values:


  public int function(int x) {
    int y = 1;
    int z = 0;
    
    while (y < x) {
      z = y;
      y++;
    }
    
    return z;
  }

And here's the new output with the new register allocator and dramatically better interference analysis. Note that I don't actually build an interference graph at any point; not sure if this is going to come back to bite me.

Remember that the code runs backwards.


method$:L27312399
  IF_ALWAYS JMPRET prim_return_ret, #prim_return

  long @method$:L27312399
  long @method$:L11631043
  IF_ALWAYS JMPRET prim_jmplt_ret, #prim_jmplt
method$:L10840700
  IF_ALWAYS CMPS lmmr10, lmmr1

  long @method$:L10840700
  IF_ALWAYS RDWORD PC, PC
  IF_ALWAYS ADD lmmr10, #1
  IF_ALWAYS MOV lmmr10, lmmr10
method$:L11631043
  IF_ALWAYS MOV lmmr0, lmmr10

  long @method$:L10840700
  IF_ALWAYS RDWORD PC, PC
  IF_ALWAYS MOV lmmr0, #0
method
method$:L29315749
  IF_ALWAYS MOV lmmr10, #1

lmmr0 and lmmr1 are the two function arguments (x and this). We smash this almost immediately, reusing lmmr0 to hold z, since it's the register used to return values from functions.

One of these days it would be fun to take a class in this stuff, I think. These are neat problems.

Adapting propasm for the Pilgrim LMM

2008-12-07T13:02:00.000-08:00

Last night, I replaced my Java compiler's hacked code generator with one based around propasm.

Unfortunately, propasm had some baked-in assumptions that gave me some trouble, so I had to rewrite it. The rewrite will go into SVN as soon as it reaches feature-parity. It's a lot simpler now and provides an API for extensible image generation -- which is the feature I needed today.

You see, I'm targeting Phil Pilgrim's adaptation of the LMM, which is the only one with 16-cycle constant execution for register-register instructions. (I developed it independently at Hobee's one night, but it looks like Phil did it first, so as far as I'm concerned it's the Pilgrim LMM.)

The Pilgrim LMM has an unusual property that lets it achieve its speed: it lays code out backwards, from high addresses to low, and uses djnz to update the native and LMM PCs simultaneously. This completely broke poor propasm's brain -- it was designed for single-pass assembly, which of course means that instructions get laid out in the order they're input.

To support this, propasm now generates images in two passes. First, it builds a tree of object describing the image's contents. Second, it walks the tree and generates output. This has the side-effect of allowing optimizations on machine code without requiring a separate object model -- I've implemented a couple simple scalar optimizations over propasm's image objects in my compiler.

My Java compiler plugs a class called rlmm.CodeSegment into propasm's image generation code, which lets it generate the code in execution order (by a CFG walk) but lay it out backwards in memory. Thus, for the sample input from my last post, we now get the following output:


' Start of segment rlmm.CodeSegment@1004901
  IF_ALWAYS JMPRET prim_return_ret, #prim_return
method$:L10840700
  IF_ALWAYS MOV r0, r2

  long @method$:L10840700
  long @method$:L15980197
  IF_ALWAYS JMPRET prim_jmplt_ret, #prim_jmplt
method$:L29181730
  IF_ALWAYS CMPS r2, r1

  long @method$:L29181730
  IF_ALWAYS RDLONG PC, PC
method$:L15980197
  IF_ALWAYS ADDS r2, #1

  long @method$:L29181730
  IF_ALWAYS RDLONG PC, PC
method$:L15006066
method
  IF_ALWAYS MOV r2, #0

Remember to read bottom-to-top! (Pardon the excessive IF_ALWAYS and expansion of calls, this output was disassembled with a naïve algorithm.)

Compiling Java for the Propeller

2008-12-06T01:12:00.000-08:00

My spare time is pretty limited these days -- work takes up a lot of it. On the up-side, I got promoted.

Over the past few months, some of my spare time has been spent designing a Java compiler that targets the Parallax Propeller. A few hand-coded mockups have convinced me that it's feasible -- the only thing between that and making it a reality are the past 50 years of compiler research, which I never learned. :-)

So, I've spent time surfing Citeseer and gathering data. Between what I've learned and my Propeller experience, I've set some parameters for the first version: it will compile to Large Memory Model code rather than a custom interpreter, and will consume Java class files.

As of this evening I've got a prototype working, and have compiled/assembled/uploaded my first binary. The bullet points are as follows:

Converts Java 6 JVML to n-address linear IR using abstract evaluation. Assumes input is verifiable, which lets me skip some checking. (Why Java 6? Because it generates nice frame attributes and doesn't use jsr.)

Operates almost exclusively in SSA (actually CSSA).

Performs register allocation in SSA form, using a crippled-but-developing version of Pereira's algorithm. I've modified it to deal more gracefully with the Propeller's CISC-like two-address architecture.

Provides limited scalar optimizations -- the ones I've gotten around to writing. Copy folding, constant propagation, jump-to-flow-control elimination, etc.

Fantastically crappy code generator for now -- literally printf-based with no intelligent layout or peephole optimizations, as you'll see in the samples below.

None of the fun stuff, like garbage collection, works yet.

Here's sample input and output from one of my test suites


public class Input0 {
  public int function(int x) {
   int y = 0;
    while (y < x) {
      y ++;
    }
    return y;
  }
}

And the output, in propasm syntax (a superset of Parallax):


method_function
L12893404
  mov r2, #0
  rdlong PC, PC  ' inlined jmp
  long @@L23063136
L26210109
  add r2, #1
  rdlong PC, PC  ' inlined jmp
  long @@L23063136
L23063136
  ' [int r2:1] <- phi ssa.BasicBlock@c4bcdc:[int c0:0] ssa.BasicBlock@18fef3d:[int r2:2]
  cmps r2, r1 wc wz
  call #prim_lt
  long @@L26210109
  long @@L25763215
L25763215
  mov r0, r2
  call #prim_return

The "call #prim_foo" instructions are calls to LMM kernel traps; plenty of other people have explained Propeller LMM in detail elsewhere, I won't repeat it. My code generator inlines LMM primitives in some cases, as it's done with jump here.

Some details of the calling conventions are apparent in the output: incoming arguments start at r0, and the returned value comes back in r0. These registers are real-live Propeller registers inside the LMM kernel, and I suspect I'll have room for a lot of them -- 32 or more -- so I'm using a RISC-like register calling convention, with link register.

Assuming work doesn't interfere, I'll post more as it develops.

Ubuntu 8.10 on the Acer Aspire One

2008-11-27T13:10:00.000-08:00

I've replaced my eee 701 with an Acer Aspire One. Ubuntu works quite well on it, without a lot of the trickery I needed on the eee, and the battery life is stunning (I get upwards of 7 hours after tweaks).

I've created a site with tutorials on getting Ubuntu working optimally on the Aspire One. It includes a complete step-by-step guide for going from installation to awesome, based on the detailed notebook I kept in the first two days I had the machine.

The machine, incidentally, is smaller than the notebook. :-)

Amazon wrong; Acer Aspire One has no free mini-PCIe slot.

2008-11-24T12:09:00.001-08:00

Amazon's product page for the Acer Aspire One claims that the machine has an available mini-PCIe slot for WWAN.

I'm holding it in my hands, and it does not -- the connector isn't soldered in place, just like earlier ones.

This is the first time Amazon's product descriptions have had a significant error in my experience, and I'm pretty pissed.

PropellerForth issue tracker

2008-05-26T23:19:00.000-07:00

I've gotten a few blog comments from folks who are using PropellerForth. Yay!

A few comments have reported bugs.

I don't closely follow comments on my blog (though I respond when I have time) -- but I do get a email when someone reports a bug at the PropellerForth issue tracker over on Google Code!

If you're using PropellerForth and find a problem, please report it there. (Please don't post "bugs" like "You haven't released a binary in a few months" or "You haven't imported your Subversion repo." I assure you I'm working on both as time permits, but this isn't my day job.)

Of course, if you're using PropellerForth and haven't found a problem, I'd love to hear about that too! Blog comments are a fine place for that, or send me an email if you can track down my address. ;-)

Trig in PropellerForth

2008-05-19T21:16:00.000-07:00

Among many other nice features, the Parallax Propeller microcontroller has a single-quadrant sine table in ROM. This makes implementing sine and cosine fast and simple, for medium-precision (13-bit) work.

Here's a simple port of Parallax's routines to PropellerForth.


hex

\ Address of table in ROM
E000 constant sin-base

\ Computes the sign of an angle.
\ The angle is a 13-bit number (0x1FFF = almost 360 degrees).
\ The result is a 16.16 fixed-point signed integer.
: sin  ( angle13 -- n16_16 )
  dup 1000 and >R   \ Stash a flag for Quadr.3/4 onto the rstack
  dup 0800 and if  negate  then  \ Invert angle for Quadr.2/4
  2* sin-base or  H@   \ Compute word address and fetch
  R> if  negate  then ;  \ Negate result for Quadr.3/4

: cos  ( angle13 -- n16_16 )  0800 + sin ;

With PropellerForth v8.05 this gives a runtime of 1088-1152 cycles for sin, and an additional 240 cycles for cos -- 31x slower than a native implementation. (v8.02 will be slower.)

It can be made slightly faster by (1) replacing the numbers with CONSTANTs and (2) inlining 2*, which is not a primitive, as "1 lshift", for a runtime of 993-1056 cycles -- 28x slower than native, at the cost of a 22 more bytes of space.

Update: Huh. Through some optimizations to the kernel, I can shave off another 100 cycles -- for a runtime of 896-926 cycles. However, it costs 248 bytes in the kernel, and eliminates a hook I was hoping to use for single-step and breakpoints. I'll have to weigh this.

Another PFcam teaser

2008-05-17T00:23:00.000-07:00

With the help of the new scope, I wrote a new OV6620 driver that includes chroma support. With the camera reconfigured to run at 25fps, it records 88x72 YUV images at full rate. It's 210 bytes, and integrated into a custom build of PropellerForth.

A few lines of Forth later, I had code to generate PPM images. (PPM is possibly the world's easiest format to produce.) Here are some samples. Forgive the yellow cast and the chroma noise -- my new workbench doesn't have lights yet, and the camera's low-lum performance is poor. That, and I probably have bugs in my YUV matrix code.

Once I'm confident in the design, I'll post the driver and Gerbers for the PCB (and if anyone actually wants one, we can go in on a BatchPCB order).

I've got 8 spare Propeller I/O pins...gotta figure out what to do with 'em. Servo connectors? Debug LEDs? Audio?

Edit: Yes, I did indeed have bugs in my matrix code! They're fixed now.

Better chroma makes engineer happy.

I can see clearly now, the waves are gone

2008-05-13T22:00:00.000-07:00

I'm a pretty hardcore guy when it comes to debugging software. I pride myself on my automated tests, I routinely sling debuggers and disassemblers around, and so forth.

When it comes to hardware, though, I've been stuck firmly in the printf era. The printf era is pretty damn powerful, of course, when you've got Forth at your side -- the PropellerForth VGA and NTSC display drivers, for example, were written using only a multimeter and ancient HeathKit frequency counter.

However, I'm not a big fan of making my own life difficult. After many years of fondling scopes at Fry's, I finally gave in and picked up a Tektronix TDS1012B. It's at the high-end of the extreme low-end: decent sampling rates for embedded work and so forth.

A couple weekends ago I taught myself printed circuit board and built the PFcam, the Propeller-based image processing board I mentioned in my last post. I'm not an analog electronics whiz, so the first thing I did with my scope was test the new board.

Sure enough -- here's a capture of some I2C traffic between the Propeller and the camera:

Notice the square waves are wearing hats? The regulator's output was bouncing between 3.3v (the goal) and 5v (the input). A decoupling cap later, my SCCB code (Omnivision-speak for I2C) is much more reliable:

Now all the I2C/SCCB chips play nice together, and nobody wigs out and sees a stop condition where there ain't one.

I'm happy with the scope so far. I'll most more details on the PFcam board later on.

Got tired of my CMUcam.

2008-05-07T22:37:00.000-07:00

What embedded machine vision system...

is easier to interface (and more powerful) than a CMUcam2;

has eight cores at 96MHz, six of which can perform user-defined image processing;

can be programmed and debugged interactively in-system using Forth or assembler;

runs open-source code built using open-source tools;

costs less than $100 in parts; and

can be built in an evening with only basic through-hole soldering?

Yeah, I couldn't find one either.

Mmm, 192 MIPS of pixel-devouring goodness. I love my overclocked Propellers.

Edit: What kind of image processing, you ask? How about realtime ASCII art!

I hope to get middle-mass and edge tracking working shortly.

PropellerForth tidbit: running a word at boot time

2008-02-10T23:08:00.001-08:00

By default, PropellerForth v8.01 starts up by running the built-in word INTERACTIVE. This displays the version screen, enables multitasking, and drops into the Forth interpreter by calling the standard word QUIT.

Once you've built an application and burned it to EEPROM using savemem, you may not want PropellerForth to be interactive anymore! Alternatively, you might define a new version of INTERACTIVE that does some additional setup -- SD card initialization, for example -- and then calls the old INTERACTIVE.

I neglected to provide an easy way to run your own words on boot in v8.01, so here it is:


decimal
\ The address of a variable containing the first word to run.
140 constant 'boot

\ Sets a word to run at startup.
\ Example: BOOT MYSTARTUP
: boot ( "name" -- )
  '  'boot ! ;

You can simulate a reboot -- assuming you haven't started any other tasks -- by invoking an arcane Propeller machine instruction:


32 0 coginit

Once you're satisfied, savemem and reboot!

PropellerForth tidbit: changing the console speed

2008-02-10T22:53:00.000-08:00

PropellerForth 8.01, by default, sets the console at 19,200 baud.

This is mostly for compatibility, and doesn't tax the serial driver; in practice, the I/O routines spend most of their time sleeping. At 80MHz the kernel I/O routines have no trouble doing 230kBps. Increasing the speed can really make a difference when moving a bunch of data to the console, such as when dumping a block of RAM or listing a block of source.

Currently the speed is hardcoded, but that doesn't mean we can't change it. :-)


\ Set the console I/O speed in bits per second.
\ Takes effect immediately.
\ Example:  115200 console-speed
decimal
: console-speed  ( u -- )
  second swap /    \ get # of cycles per bit
  176 L! ;         \ change the kernel's constant bit time

The magic number there, 176, is the location of the bit time constant inside the kernel -- we use L!, local-store, to override it in the running kernel image. 176 is valid for 8.01 and early alphas of 8.02, but may change in the future -- eventually there will be a supported way of doing this.

Have fun!

Java 6 try/finally compilation without jsr/ret

2008-02-10T22:20:00.000-08:00

My day job requires me to be a bit of a JVM geek, so I was poring over the Java Virtual Machine spec recently when I remembered something: In Java 6 and later, the old jsr and ret instructions are effectively deprecated. These instructions were used to build mini-subroutines inside methods. While Java doesn't support nested functions or anything fun like that, it does have the try/finally construct, and these instructions were quite handy for implementing it.

I saw no "official" instructions for compiling finally without jsr, so I investigated it, and thought I'd post the results -- mostly in case I forget them later.

For non-Java folks, some background: a chunk of code that might fail at runtime can be wrapped in a try block. You can then attach handlers for specific types of exceptions/errors to the try block using catch clauses, if you want to respond to specific failure cases. You can also attach a finally block, which will be run at the end, failure or no. You can think of finally as a sort of cleanup block -- which, in practice, is how it's used.

As a result, you wind up with multiple control flow paths that can execute the finally code:

try block, successful completion, finally block executes before moving on

try block, failure, one or more catch blocks, finally block executes before moving on

try block, unhandled failure, finally block executes before unwinding the stack and throwing the error out to a higher level

Java originally compiled this the way most folks would write it by hand: code that gets used multiple places goes in a subroutine. In this case, it's a nested subroutine accessed using jsr.

This unfortunately makes dataflow analysis and type inference of the Java code considerably more complex, for reasons I won't go into here.

So while Java 6 and later JVMs can still understand jsr, tools no longer generate it. Instead, they duplicate the code of the finally block along each path (a transform I've always called tail duplication, but there may be other names). Let's look at a quick example.

This totally contrived Java class plays with an array:


class TryFinally {
  public static void main(String[] args) {
    int[] a = new int[2];
    try {
      a[16] = 2;
    } catch (ArrayIndexOutOfBoundsException e) {
      a[0] = 2;
    } finally {
      a[1] = 2;
    }
  }
}

It will always follow the longest code path, because it's written to fail: the try block will execute, followed by the handler, followed by the finally clause.

The disassembled JVM instructions for this method are as follows:


public static void main(java.lang.String[]);
  Code:
   0:   iconst_2       // Create the array
   1:   newarray int
   3:   astore_1       // Store it in local 1
   4:   aload_1        // Set element 16 to 2 (throws)
   5:   bipush  16
   7:   iconst_2
   8:   iastore
   9:   aload_1        // Begin 'success' finally code
   10:  iconst_1
   11:  iconst_2
   12:  iastore
   13:  goto    35     // End 'success' finally code
   16:  astore_2       // Catch block, save the exception...
   17:  aload_1        // and set a[0] = 2
   18:  iconst_0
   19:  iconst_2
   20:  iastore
   21:  aload_1        // Catch copy of finally code
   22:  iconst_1
   23:  iconst_2
   24:  iastore
   25:  goto    35
   28:  astore_3       // A third copy of finally code!
   29:  aload_1
   30:  iconst_1
   31:  iconst_2
   32:  iastore
   33:  aload_3
   34:  athrow
   35:  return
  Exception table:
   from   to  target type
     4     9    16   Class java/lang/ArrayIndexOutOfBoundsException
     4     9    28   any
    16    21    28   any
    28    29    28   any

As you can see in my annotations, we have three copies of the finally code! Why three? The answer is in the three code paths I discussed above, and in the exception table.

In the table we see four exception handlers defined -- but, of course, we only defined one! Why so many?

The first is the one we defined as a catch. The second is an invisible additional catch on the try block for type 'any' -- so any unexpected exceptions are sent to the third copy of the finally code. The third guards the catch block itself; the fourth guards the generated exception handler.

In other words, the compiler has rewritten the Java code into something resembling:


  public static void main(String[] args) {
    int[] a = new int[2];
    try {
      a[16] = 2;
      a[1] = 2;
    } catch (ArrayIndexOutOfBoundsException e) {
      a[0] = 2;
      a[1] = 2;
    } catch (* e) {
      a[1] = 2;
      throw e;
    }
  }

As you can see, the finally block has disappeared -- instead, its contents have been duplicated along each code path.

New features for PropellerForth 8.02

2008-02-07T20:14:00.000-08:00

I'm fleshing out the feature set for PropellerForth 8.02, due out in a couple weeks. This is just a teaser post describing what I've been working on; no code yet. :-)

The main new features at this time:

Block word set for reading/writing block devices and loading source code from storage
EEPROM Block backend, for treating the program EEPROM as a block device
SPI-mode SD/MMC card Block backend

The SD support is a traditional Forth disk layer: it doesn't implement FAT or any other filesystem. Instead, it lets you directly address blocks on the disk. By default you can use this to save and edit source code directly on the card, but it could also allow an enterprising individual to implement filesystem support.

Because source is stored in raw disk sectors instead of files, getting at it from a "real" computer will require a tool like dd. Since this is an embedded system, that doesn't bother me too much, but I wouldn't complain if someone implemented FAT16! :-)

The actual interface code is a direct port of Tom Rokicki's FSRW SPIN implementation. It's about 1KiB and currently gets about 5-6KiBps at 80MHz, twice the throughput of the SPIN version, despite being a pretty literal port. I hope to optimize it further before release.

Now, to work on a target compiler -- so that users of 8.02 can recompile their whole system from sources stored on EEPROM or SD.

You keep using that word.

2008-01-20T22:47:00.001-08:00

Poking around on the internet this evening, I ran across an ad for a product intended to help manage "really, really big" server deployments. I was intrigued, since that's what I do for a living, so I kept watching.

Then this screen came up:

*cough* "Big." You keep using that word. I do not think it means what you think it means.

PropellerForth v8.01 alpha; HYDRA tidbit

2008-01-01T13:18:00.000-08:00

After my winter sprint, PropellerForth v8.01 alpha has been posted on the project page. (I'm using Ubuntu-style version numbers, so 8.01 is the January 2008 release.)

Release Notes

Supported target boards

Getting Started guide

As it says in the release notes, the version currently available there is an alpha release. It's been tested, it works, and it's probably close to the final release, but I reserve the right to make changes in the near future before pronouncing it official. In particular, the docs are not nearly complete -- I'm working on it.

Source hasn't been posted yet; still trying to figure out how best to do that.

A HYDRA PropellerForth Tip

The HYDRA board is one of PropellerForth's officially supported targets. One of its slick (but undocumented) features is how it handles the on-board EEPROM when a cartridge is inserted: it gets remapped to a higher address space, but remains accessible.

PropellerForth's EEPROM words (included in the v8.01 'full' release) support addressing multiple EEPROMs on the I2C bus, using Atmel-style device and page addressing. The visible address space is:

No cartridge: onboard EEPROM at 0x00000 - 0x1FFFF

Cartridge: onboard EEPROM at 0x20000 - 0x3FFFF, cartridge at 0x00000 - 0x1FFFF

This opens some interesting possibilities:

Programs could use both EEPROMs together, for 256KiB of bulk data storage.

A reasonably simple Forth word could copy one EEPROM to the other, to clone a cartridge or back up the on-board software.

I'll leave those as exercises to the reader; for now, here's a word, ?cart, that checks whether a cartridge is currently inserted in the HYDRA.


hex   \ the base of champions
: ?cart  ( -- flag )
  \ Try to read base of remapped on-board EEPROM.
  20000 ['] eeread catch  \ Guard with catch to intercept failure
  nip   \ Discard the address (if failed) or the result (if succeeded), leaving exception
  0= ;  \ If the exception is 0 (none caught), return 'true', otherwise 'false'.

To help you test it, here is the cartridge monster. (Hey, I can only type in so many dry source examples before I try to make one funny.)


: O_O  \ See, it's a face.  ... well, I thought it was funny. :-P
  ?cart  if exit  then  \ Don't bug the user if a cartridge is present
  begin  \ Loop and complain...
    ." CARTRIDGE MONSTER WANT CARTRIDGE" cr
    1 seconds wait
  ?cart until  \ ... until a cartridge appears
  ." NOM NOM NOM BURP" cr ;

(Hot-swapping cartridges on the HYDRA should work fine as long as the EEPROM is not being accessed when it happens -- just be careful to insert the cartridge straight.)

PropellerForth I2C EEPROM driver

2007-12-27T22:03:00.000-08:00

This afternoon, I curled up with the datasheets for Atmel's I2C EEPROMs, like the one the Propeller uses to boot. I haven't written any I2C code in a while, so I had to relearn the protocol.

Then, I went out for phở. The place down the street is quite tolerant of me sitting for half an hour drawing state diagrams.

Noodles completed, I set to work interfacing PropellerForth to the boot EEPROM. It's been a resounding success. The sources are below; they should work on the old 20061124 image, if anyone still has a copy. Otherwise, they'll work on the 20080101 image once I make it available.

Executive summary: these words implement a hardcoded interface to an EEPROM on pins 29:28. This lets you access data stored in EEPROM (using ee@ and ee!). For the first time, you can save a bootable image of your current PropellerForth system to EEPROM, using the saveforth word.

The emphasis there shows how excited I am about this. Bootstrapping my NTSC display driver requires me to carefully type in Forth code for several minutes, each time I reboot! The words are factored so I can test as I go, but it's still painful. This is about as revolutionary as when I got cassette storage working with my TRS-80 Model 100 and no longer had to type in BASIC listings.

The interface is not spectacularly fast; page reads can stream data at about 20kbps, and page writes aren't implemented yet. saveforth can take a minute or two. It is, however, pretty simple and readable, assuming you read Forth.

If you don't read Forth, it's worth taking a glance at the code anyway. It's not the best Forth code -- I'm rusty -- but casual observers may notice that code toward the top of the listing tends to be low-level (written in terms of machine registers like OUTA). As you progress through the listing, the language changes: first to a physical-level description of I2C, then to a layer-2 description of how to talk to the EEPROM. In my day job we refer to this as a domain-specific language. Forth programmers didn't coin this term, because they didn't need one: it's the natural way to build systems in Forth.

So: the code! I've hand-escaped this, and may have introduced errors in the process.

Update: sneaky bug fixed by addition of mkboot word. Details below the source listing for anyone who doesn't want to figure it out for themselves. :-)


hex  \ my dad will surely rib me for not using octal

\ Sets the value of an output pin (identified by 'mask').
\ Output is 0 if 'f' is false, 1 otherwise.
: pin! ( f mask -- )
  swap if
    OUTA L@ or
  else
    OUTA L@ swap -and
  then OUTA L! ;

\ Sets a pin (identified by 'mask') to output.
: pin> ( mask -- )
  DIRA L@ or DIRA L! ;

\ Sets a pin (identified by 'mask') to input.
: <pin ( mask -- )
  dira L@ -and dira L! ;

\ I2C pin masks.  Workaround for CONSTANT bug (CONSTANTs are 16-bit).
: eesdamask 20000000 ; \ pin 29
: eesclmask 10000000 ; \ pin 28

\ Words for working with the EEPROM SDA line.
: eesda! ( f -- )  eesdamask pin! ;
: eesda@ ( -- f )  INA L@  eesdamask and ;
: eesda>  eesdamask pin> ;
: <eesda  eesdamask <pin ;

\ Words for working with the EEPROM SCL line.
: eescl! ( f -- )  eesclmask pin! ;
: eescl>  eesclmask pin> ;
: <eescl  eesclmask <pin ;

\ Initializes the bus; useful for resetting a b0rked chip
: eeinit
  \ SCL high/output, SDA input
  1 eescl!  eescl>  <eesda

  \ Drain the device until we get an ACK, or we try 9 times
  9 0 do
    0 eescl!  1 eescl!
    eesda@  if  unloop exit  then
  loop ;

\ I2C start condition
: eestart
  1 eescl!  eescl>
  1 eesda!  eesda>  0 eesda!
  0 eescl! ;

\ I2C stop condition
: eestop
  1 eescl!
  1 eesda!
  <eescl
  <eesda ;

: eerxbit ( -- bit )   1 eescl!  eesda@  0 eescl! ;

\ Transmits a byte, MSB first.  Returns ack bit.
: eetx ( byte -- ackbit )
  8 0 do
    dup 80 and  eesda!
    1 lshift
    1 eescl! 0 eescl!
  loop drop
  \ Read ack bit
  <eesda eerxbit
  0 eesda! eesda> ;

\ Receives 8 bits, sending 'ackbit' in response
: eerx ( ackbit -- byte )
  <eesda
  0 8 0 do
    1 lshift
    eerxbit if 1 or then
  loop
  swap eesda! eesda>
  1 eescl!  0 eescl! ;

\ Like eetx, but throws file error if not acked.
: eetx? ( byte -- )
  eetx  if -25 throw then ;

\ Sends a two-byte big-endian address.
: eetxaddr? ( addr -- )
  dup  8 rshift  FF and  eetx?
  FF and  eetx? ;

\ Reads a byte out of EEPROM.  Throws on failure.
\ If you're feeling cryptic you could rename this
\ eec@.
: eeread ( addr -- byte )
  eestart  A0 eetx?  eetxaddr?
  eestart  A1 eetx?  1 eerx
  eestop ;

\ Writes a byte to EEPROM.  Throws on failure.
: eewrite ( byte addr -- )
  eestart A0 eetx? eetxaddr? eetx? eestop ;

\ Reads a little-endian 32-bit integer from EEPROM.
\ Throws on failure.
\ Eventually this should use page read.
: ee@ ( addr -- x )
  0 4 0 do
    8 rshift
    over eeread  18 ( hex ) lshift or
    swap 1+ swap
  loop nip ;

\ Waits for the EEPROM to become available.  Required
\ after a write operation unless you're damn sure you're
\ going to be busy for a while.
: eewait   begin  eestart A0 eetx eestop  0= until ;

\ Writes a little-endian 32-bit integer into EEPROM.
\ Throws on failure.
: ee! ( x addr -- )
  4 0 do
    2dup eewrite
    1+  swap 8 rshift  swap
    eewait
  loop 2drop ;

\ Reads 'count' bytes from the EEPROM starting at 'addr'
\ into a buffer at 'dest'.
: eereadpage ( dest count addr -- )
  over 0= if  drop drop drop exit  then
  eestart A0 eetx? eetxaddr?
  eestart A1 eetx?
  ( count ) 1- 0 do
    0 eerx over c!
    1+
  loop
  1 eerx swap c!
  eestop ;

\ Updates fields in the image preamble to allow
\ us to boot properly.
: mkboot
  here      08 H!
  here 08 + 0A H!
  here 0C + 0E H!
  here 10 - 10 H! ;

\ The word that made my evening: saves the
\ current dictionary, kernel, and bootloader
\ as a bootable image in EEPROM.  Takes a
\ while, but prints cute little status updates.
\ The resulting image will boot to the interpreter
\ running the standard startup vector.
\ 
\ CAVEAT HACKER: this will erase whatever's in
\ EEPROM, in case that wasn't apparent.
: saveforth
  ." Saving 0 to "  here aligned . cr
  mkboot
  here aligned  0 do
    i @ i ee!
    i FF and 0= if
      ." ..." i . cr
    then
  4 +loop
  ." Done." ;

Update about mkboot: the original listing I posted contained a subtle bug. When booting the saved EEPROM image, 12 bytes in the middle of your first user-added colon definition were destroyed. I didn't notice this because my first def was some test word that I didn't use after boot.

As described in my article on reverse-engineering the Propeller's image format, the SPIN interpreter needs some RAM to start. My image preamble (as used in propasm, and by extension PropellerForth) uses 12 bytes of RAM for the initial SPIN stack before the machine code is loaded.

The preamble tells SPIN where to put its stack; propasm indicates that it should go right after the end of the code. But if you've added code at runtime and saved Forth, the preamble needs to be updated -- otherwise SPIN will clobber an area just past the end of the original image, which is probably in the middle of a definition.

So, mkboot updates the preamble.

PropellerForth stirrings

2007-12-27T00:00:00.001-08:00

A few weeks ago, I was poking around on the Silicon Valley Forth Interest Group webpage. I was surprised to see this in their minutes:

There has been no success in contacting the author of Propeller Forth - written locally by Cliff L. Biffle

As of about February 2007, my email got so clogged with spam that I simply stopped checking it. (Apologies to anyone who's been trying to contact me.) So, I had no idea that the SVFIG was interested in PropellerForth. I've had isolated inquiries from a couple people, but all in all, my original posts (here and on the Parallax forums) were met with general disinterest.

So, I've resurrected the project. Not much progress yet -- mostly, I'm cleaning up the sources so I can release them without sullying my good name. :-) People poking around the PropellerForth site on code.google.com might notice some documentation appearing in preparation for the source release.

Ever since I moved out of my folks' house, I've gone back and spent a few nights there for Christmas. Since my sleep schedule is rather different from theirs, I wind up having a lot of free time -- and since I'm away from work and distraction, it's traditionally been a great opportunity to hack. (Projects that got their start or reached significant milestones over Christmas include Mongoose, Cesta, PropellerForth -- and, 15 years earlier, WebElite.)

This year I learned the NTSC spec, the US analog television standard. The existing NTSC drivers for the Propeller are cryptic and don't build with propasm, so I wrote a very simple one with more lines of comment than code. It generates a 40x16 B&W text display, uses the ROM font to save space (compressing it on the fly to 8x16 pixels), and requires 336 bytes of code space and 640 bytes of framebuffer. As an experiment, I've tied it into PropellerForth.

It probably won't be part of the base image I release -- it bloats the image beyond my 8KiB target -- but between it and my PS/2 driver from Christmas 2006, I've nearly got a standalone console working.

(NTSC, incidentally, is a pain compared to VGA -- but most of the complexity, as my dad pointed out, is a result of sending all the data amplitude-modulated on a single channel, instead of VGA's five. It's kind of impressive that they got this to work in the 30s.)

So, if anyone following my blog is interested in PropellerForth, let this at least indicate that your interest may not be in vain.

ASUS eeePC: some sources posted.

2007-11-27T11:19:00.000-08:00

Looks like ASUS has posted some source archives on their FTP site. On initial inspection, the asus_acpi module sources are not the ones that compiled the module that ships on the machine, but are very close. Gonna try 'em out this evening -- as long as they work, I can chalk the previous binary release up to an error on ASUS's part and forge ahead.

Edit (2007-11-30): I've pored over ASUS's source release and extracted their changes into patches. Everything seems to work -- they even released some packages that they weren't technically obligated to, like their on-screen display code for the volume and wifi buttons.

I'm delighted to report that this situation is resolved, as far as I'm concerned. ASUS has reacted admirably and swiftly, and I'm proud to have given them my money (with the small exception of the arbitrary and potentially illegal restrictions they've placed on upgrades).

Gonna go back to my enjoying my laptop now, and hopefully not get viciously attacked on Slashdot and my own blog for a while. Happy hacking!

eeebuntu tip: unloading/reloading the wifi drivers

2007-11-25T10:16:00.001-08:00

The eee's wifi does not survive a suspend: the hardware and drivers get into different states, and things quit working. The wifi control scripts in ASUS's Linux distribution hold the key.

There's a particular sequence of rmmod/insmod calls that will force the system to rediscover the wifi, and (for me at least) fixes all the various b0rked states it can get into. I call it the "Magic Wifi Dance," because it's a ritual that I don't completely understand.

My control script is below. You'll need the Atheros drivers and the ASUS ACPI module.


#!/bin/sh

# The sequence here *may* be important.
# (It seems to fail intermittently if you deviate.)
unload_modules() {
   rmmod wlan_scan_sta
   rmmod wlan_tkip
   rmmod wlan_wep
   rmmod wlan_ccmp
   rmmod wlan_acl
   rmmod ath_pci
   sleep 1
   rmmod ath_rate_atheros
   rmmod ath_hal
   rmmod wlan
   rmmod ath_dfs
}

# At least this one's straightforward.
load_modules() {
   modprobe ath_pci
}

wifi_on() {
   # Force PCI Express Hotplug to reinit
   rmmod pciehp
   sleep 1
   # pciehp_force may be unnecessary; Xandros did it.
   modprobe pciehp pciehp_force=1
   sleep 1
   # Switch on the hardware
   echo 1 >/proc/acpi/asus/wlan
   sleep 1
   load_modules
}

wifi_off() {
   unload_modules
   echo 0 >/proc/acpi/asus/wlan
}

case $1 in
   on)
      wifi_on
      ;;
   off)
      wifi_off
      ;;
   toggle)
      STAT=`cat /proc/acpi/asus/wlan`
      if [ "$STAT" = "1" ];
         then wifi_off;
         else wifi_on;
      fi
      ;;
esac

When executed on an "eeebuntu" machine with ASUS's binary modules, that script should be capable of shutting down and bringing up the Atheros wifi card. The on and off arguments do what their names imply; the toggle argument checks the card's status in proc and responds appropriately. (I use toggle to make the keyboard's wifi key work, which I'll demonstrate in my upcoming post on ACPI events.)

For those playing along at home, this resulting control script is a good one to call from /etc/acpi/suspend.d and /etc/acpi/resume.d, with off and on arguments, respectively. (Just make sure it's called after the interfaces are shut down on suspend, and before they're brought up on resume. On default Ubuntu, calling the suspend script "56-eee-wifi-off" and the resume script "60-eee-wifi-on" gets the order right.)

eeebuntu tip: ifup/down for NetworkManager

2007-11-24T23:39:00.000-08:00

By switching to NetworkManager, I lost the use of the Linux ifup/ifdown scripts for quickly bringing network interfaces up and down. (These scripts rely on the information in /etc/network/interfaces, which I've stripped bare to transfer control to NetworkManager.)

Now, with nm-applet and kin, I have no real need or desire to control my network interfaces from the shell. However, some of my other scripts do -- in particular, when suspending and resuming the machine, I need to remove/reload the Atheros kernel modules, and I can't do that while the interface is up.

Also, my keyboard has a cute little "Wifi On/Off" button that I want to work. (More info on that in a later post.)

Fortunately, the solution turns out to be dead-simple: NetworkManager's dbus API exposes methods for bringing the network up and down.

To bring all NetworkManager-controlled interfaces down:


dbus-send --system --type=method_call \
  --dest=org.freedesktop.NetworkManager \
  /org/freedesktop/NetworkManager \
  org.freedesktop.NetworkManager.sleep

(Yes, all those switches are necessary.)

To bring 'em back up:


dbus-send --system --type=method_call \
  --dest=org.freedesktop.NetworkManager \
  /org/freedesktop/NetworkManager \
  org.freedesktop.NetworkManager.wake

In my case, I dropped these into scripts in /etc/acpi/suspend.d and /etc/acpi/resume.d, respectively, alongside their old-school ifup/down counterparts. Works great, assuming the drivers come back up; I'll post the trick for that in a subsequent post. (I'm transcribing my porting notes as fast as I can here.)

eeebuntu tip: wireless with hal and NetworkManager

2007-11-24T22:58:00.000-08:00

I've been away from Linux for quite a while, off in Mac-land, where things generally just work. I was delighted to notice, upon my return, that the community (and RedHat in particular) noticed that manually configuring your wireless interfaces is lame, and built a solution: NetworkManager.

NetworkManager is built atop hal, a daemon that interrogates hardware and makes the information available over a dbus interface. (dbus is a simple mechanism for interprocess messaging and procedure call, similar to DCOP, but more general.)

If you install Ubuntu and subsequently bring up your network using a panel applet, you're using NetworkManager -- and boy, is it nice. Unfortunately, most instructions for getting the eee's wireless working on Ubuntu revolve around the "old-world" configuration mechanism in /etc/network/interfaces. While Ubuntu has graphical configurators that generate this file, using it prevents you from applying the full power of NetworkManager. (Fun fact: NetworkManager will silently ignore any interfaces that are configured in /etc/network/interfaces.)

NetworkManager and hal are really poorly documented. (No offense to the authors intended; the tech is impressive, and I understand that sometimes precious little time is left over to write a design document.) I don't understand the system well enough to write a general tutorial, so here's a specific one: how to get NetworkManager and hal playing nice with the binary Atheros drivers on "eeebuntu" -- Ubuntu 7.10 using the ASUS-compatible 2.6.21.4 kernel I described in my last post.

Getting hal to create ath0 automatically

The Atheros wireless drivers create two network interfaces: wlan0 by default, which seems to be good for very little, and ath0 on demand, which is what you actually use to speak to the intarweb. You have to explicitly request creation of the ath0 interface like so:

wlanconfig ath0 create wlandev wlan0 wlanmode sta

hal, by default, sees the wlan0 interface as an 802.e interface, and does not see ath0 at all. What we want is for hal to ignore wlan0 and treat ath0 as an 802.11 interface. hal supports policy files (written in XML, which surprised me in a Linux tool) that rewrite its view of devices -- and that's what we'll use to fix this.

But first -- we need ath0 created automatically when wlan0 appears. A simple script suffices. I've put mine in a file called /etc/hal/callouts/eee-wifi for reasons that will become apparent in the next step. The script need only contain:


#!/bin/sh

case $HALD_ACTION in
  add)
    sleep 1  # May be unnecessary, experiment
    /sbin/wlanconfig ath0 create wlandev wlan0 wlanmode sta
    sleep 1
    ;;
  remove)
    /sbin/wlanconfig ath0 destroy
    ;;
esac

Notice that the script takes its input, not from a command-line parameter, but from an environment variable named HALD_ACTION. This will make sense in a minute. For now, you can test the script thusly:


# Should create ath0 if wlan0 exists and drivers are loaded
env HALD_ACTION=add /etc/hal/callouts/eee-wifi
# Should remove ath0
env HALD_ACTION=remove /etc/hal/callouts/eee-wifi

Now, we convince hal to invoke our script when wlan0 appears or disappears. Create a file named /etc/hal/fdi/policy/10-networking-ath0.fdi containing the following:


<?xml version="1.0" encoding="ISO-8859-1"?>
<deviceinfo version="0.2">
 <device>
  <match key="net.interface" string="wlan0">
   <append key="info.callouts.add" type="strlist">/etc/hal/callouts/eee-wifi</append>
  </match>
 </device>
</deviceinfo>

This adds our script as a "callout" for wlan0 -- hal's notion of an event handler. hal will invoke our script when wlan0 comes or goes, and set HALD_ACTION appropriately.

Restart hal (or killall -HUP hald) and try loading or unloading the Atheros drivers. ath0 should be created and destroyed automatically. (Make sure the ath0 interface is down when you do this.)

Letting NetworkManager configure ath0

For NetworkManager to configure an interface, a few conditions must be met:

hal must see the interface and recognize it correctly (e.g. seeing ath0 as a wired Ethernet connection is not good);

The interface must not be configured in /etc/network/interfaces. If you currently have a stanza configuring ath0 or wlan0, remove it.

First things first. Modify the 10-networking-ath0.fdi policy we created in the last step by adding the code marked below:


<?xml version="1.0" encoding="ISO-8859-1"?>
<deviceinfo version="0.2">
 <device>
  <match key="net.interface" string="wlan0">
   <append key="info.callouts.add" type="strlist">/etc/hal/callouts/eee-wifi</append>
   <merge key="info.capabilities" type="strlist">net</merge>
   <append key="info.capabilities" type="strlist">net.80211</append>
   <merge key="info.category" type="string">net.80211</merge>
   <merge key="net.interface" type="string">ath0</merge>
   <merge key="net.80211.mac_address" type="copy_property">net.80203.mac_address</merge>
   <remove key="net.80203.mac_address"></remove>
   <merge key="linux.sysfs_path" type="string">/sys/class/net/ath0</merge>
  </match>
 </device>
</deviceinfo>

Note: special thanks to "Triarm" on the eeeuser forums for pointing out this approach.

Line by line, this does the following:

Replaces wlan0's info.capabilities property with the single item "net", indicating that it's a network interface.

Appends "net.80211", indicating that it's a wireless interface.

Changes the device's category, again to indicate that it's a wireless interface.

Switches the entry to refer to ath0, instead of wlan0.

Copies the 802.3 (wired Ethernet) MAC address to the 802.11 MAC address (I'm surprised that these are separate).

Removes the old 802.3 MAC address.

Rewrites the entry's sysfs path to point to ath0's.

To sum up, at this point we have:

Instructed hal to invoke our callout when wlan0 is added or removed, thereby automagically creating/destroying ath0.

Rewritten the device descriptor for wlan0 to describe ath0 (which is unfortunately not picked up automatically by hal).

Removed wlan0/ath0 configuration from /etc/network/interfaces. (You remembered that, right?)

Bring NetworkManager down, restart or HUP hald, and bring NetworkManager back up. (The control script for NetworkManager on Ubuntu 7.10 is at /etc/dbus-1/event.d/25NetworkManager.)

Assuming I haven't forgotten anything, NetworkManager should now offer to configure your wireless, and the interface should show up in configurators like nm-applet.

If it doesn't work, try rebooting. (I know it's lame to say that, but the Atheros drivers are incredibly sensitive and can get into weird states that make your interface stop working, usually after you remove/readd them or suspend/resume. I have a magic dance that repairs the driver, but it's lengthy so I'll post it in a followup.)

eeebuntu tip: using a custom kernel with ASUS's modules

2007-11-23T11:16:00.000-08:00

I like the eee hardware but dislike the software. Personal preference; when I can't use a Mac I use Ubuntu. Readers will surely like some other distro (I know I used to be big on Gentoo), but this tip should not be distro-specific.

I wanted to put Ubuntu 7.10 on my eee without sacrificing any features. I've largely pulled it off, but it's a long journey down a narrow, undocumented road (sigh, Linux). The journey starts with the proverbial single step, which in this case is replacing the kernel with a largely identical one built from source. (If you're going to do anything cool to the kernel, you've got to be able to build it.)

I started out by installing Ubuntu 7.10 off a live stick. This isn't strictly necessary -- the kernel we're building will probably work in Xandros -- but since Ubuntu is my eventual goal, I aimed high. The live stick boots without a hitch (into Compiz, no less!) and the install was uneventful. Note before installing: there are files on the eee's filesystem you will need to complete this tutorial! It is worth your time to make a backup in an accessible form, such as dd'ing the filesystem to somewhere you can loop-mount it.

(Caveat lector: I actually installed onto an SD card, leaving the internal flash disk unmodified, but doing this requires a bunch of extra steps that are not documented here. It's sufficiently involved that I'll have to describe it in a followup.)

The install was largely uneventful and is not the topic of this post.

Ubuntu 7.10 does not, out of the box, support the following hardware on the eee:

The Atheros wireless card. (The madwifi drivers ASUS ships are not the 9.3.3 drivers, and a freshly built set from SVN trunk doesn't work either.)

The ASUS ACPI features for controlling backlight and powering PCIe devices on and off. The mechanism is conceptually similar to the kernel's asus_acpi module, but as I noted in a previous post, ASUS ships a modified driver.

(Those of you who have been in the Linux/FreeBSD laptop community for some time may notice how incredibly short that list is, and the fact that it does not include multihead 3D accelerated graphics, audio, and USB 2. How far we've come.)

As a result of the botched ACPI support, suspend/resume doesn't work quite right. Suspend-to-RAM will work sometimes, kinda, after a few VT switches to thunk the display adapter. Not good enough! I want instant suspend/resume and working wireless! Waaaah, the Mac has spoiled me! :-)

The pragmatic solution, if not the most FSF-friendly one, is to build a kernel with the exact version string from ASUS's so their binary modules will work. (If you care, note your kernel will be tainted! Danger Will Robinson!)

The recipe below skips some steps and is not intended for Linux or Unix newbies. Sorry; I've been immersed in Unix long enough that I'm not the right guy to write the newbie tutorial. Feel free to steal my instructions to make one!

Prereq: a Linux machine with a working set of devtools and the 2.6 version of depmod. This might be the eee, I suppose, but I used a much faster machine. (Specifically, an Ubuntu 7.10 virtual machine under VMware Fusion.)

Download the sources for the matching Linux kernel version -- in this case, 2.6.21.4. (For the kernel-impaired, it comes from kernel.org's 2.6 site.)

Untar.

Nab the ASUS kernel configuration, helpfully shipped right on your eee. It lives in /boot/config-2.6.21.4-eeepc. Copy it into your untarred kernel sources as a file named .config .

If you tried to build the kernel now, you'd notice some errors about missing unionfs. Unionfs isn't in the 2.6.21.4 mainline kernel, but ASUS uses it. If you want it, download the version for 2.6.21.7 and apply it in the kernel tree with
```
patch -p1 </path/to/patch
```
If you don't want it, simply delete or comment out all lines in the config containing the word UNIONFS.

ASUS's config in place, build a replacement kernel by issuing
```
make oldconfig && make
```

Create a directory to hold your new kernel and modules, and issue
```
make INSTALL_PATH=/your/directory install
make INSTALL_MOD_PATH=/your/directory modules_install
```
You do not need to (and should not!) run these commands as root.

In your directory are a bunch of files: a kernel and associated files at the root, and a lib/modules/2.6.21.4-eeepc directory with your modules in it.

Copy the files out of the directory into /boot on your eeepc. Note at this point that, if you are still running Xandros, you have just overwritten your kernel. Hope you had a backup. (If you're running Ubuntu 7.10 you have installed an additional kernel alongside the main one. This is safe.)

Copy the contents of the /lib... directory, not into /boot with the others, but into /lib/modules/2.6.21.4-eeepc.

Try booting your eee. You will need to get to the grub menu and change the "kernel=" parameter. (How to do this is beyond the scope of this article.) If it does not work, I'm afraid I am not the man to help you; I make Linux work through sheer dumb luck and a lot of Unix engineering experience, but a Linux guru I'm not.

If it seems to work, simply copy the atheros and acpi. directories from /lib/modules/2.6.21.4-eeepc on your eee backup filesystem into the same locations on the new one, and run (as root) depmod -a.

At this point, if it worked, you have a booting Ubuntu (or ${YOUR_DISTRO}) system running on a reasonable facsimile of ASUS's 2.6.21.4 kernel. If you issue modprobe asus_acpi or modprobe ath_pci, the modules should load (and put some control files in /proc/acpi/asus, or create wlan0, respectively).

You may find that suspend/resume to RAM works with the asus_acpi module loaded. Edit your /etc/modules as you see fit.

Getting from "loading the Atheros modules" to "reading Slashdot" is unfortunately involved -- but the process is no different than the normal madwifi drivers. (Hint: until I post my scripts, search on Google for "wlanconfig ath0 create".)

Happy hacking!

ASUS eeePC: First impressions and GPL violations

2007-11-22T10:49:00.000-08:00

Most recent edit (2007-11-30): please see my more recent post for updates. ASUS has released the sources for some of the applications and drivers on the eee. I can't say whether it's complete and accurate yet, but it's a great sign from ASUS.

Edit: This post has gotten wider circulation than I was expecting (I rarely get readers, much less comments!). I've been clarifying some points in the comments, but people don't seem to be reading them before posting (and some of the posts have been hostile in tone). So:

Yes, I've downloaded and poked around in the 1.8GB archive ASUS insists is the source, from both the US and Taiwan sites. It does not contain the sources in question, or at least did not when I retrieved it. I tend to assume incompetence before malice, and I really do believe they just messed up. (Even the asus_acpi stripping seems more like a botched search-replace job by some overworked driver author than a malicious act. Doesn't make it legit, of course.)

I realize that blogging about a GPL violation doesn't fix it. My purpose in writing this article was to document the violation; I have neither the inclination nor the time to press a complaint or (god forbid) file a lawsuit! If others want to do that in response to this post, I'm happy to serve as an expert witness and provide the evidence I've collected, but for now, I'm enjoying my laptop and a cup of coffee.

I either suck at using ndiswrapper (I freely admit this) or it's my Airport base station causing the problems there. More on wireless drivers in a followup post.

Now on to the original post:

For my birthday, I bought myself an ASUS eeePC. Now, I've been lusting after very-small-form-factor laptops for some time (ever since I saw the Zaurus C series), and this is quite the small one. It also ships with Linux, which (I thought) was a good indication that the hardware is well supported by Linux. (Not so; read on.)

I'm very pleased with the hardware with a few exceptions, which I'll detail in the latter two thirds of this post. The screen is bright and clear, the keyboard is surprisingly usable (even with my giant hands), etc. I'm really happy with it, now that I've bent it to my will. Obligatory laptop porn below.

The eee on a sheet of 8.5x11 paper:

The eee next to a coffee mug:

The eee atop my 15" MacBook Pro:

Now then.

Proprietary Hardware Woes

ASUS ships the eee with a variant of Xandros Linux, which in turn is a variant of Debian. It also ships with binary modules for much of the hardware, and some of the hardware won't work without 'em. Specifically,

The wireless works with the madwifi version that ships on the machine, but not with HEAD or 9.3.3, and

The ACPI does not work with the Linux kernel's asus_acpi module, but does with ASUS's variant of it.

Several folks have gotten the wifi working with ndiswrapper, but this just tells me that those folks don't run WEP. (I need to figure out where they live.) I've gotten both wifi and ACPI working in Ubuntu, but only by loading ASUS's binary modules. Instructions in a subsequent post, once I'm done ranting.

(Edit (2007-11-23): Folks have posted saying they got ndiswrapper working with WPA. They're clearly 1337er than I am; turning on any encryption at all would spike it to 50%+ CPU. Lame!)

Proprietary Software Woes

The system is set to update itself and add packages from a repository at ASUS's site (specifically this one), where the little machine can fetch new kernels, Linux userland, KDE updates, and optional packages.

What you won't find on that site are sources. ASUS is bound by the GPL to make the sources for the software they're distributing available, even if they have not modified them. (Check the license if you don't believe me.) ASUS has posted a 1.8GB ZIP file on their website that they claim is the sources, but it's not -- it contains a few .debs (not even the versions that ship on the machine) and some kernel headers. (Perhaps they figured nobody would pull 1.8GB from their slow-as-molasses site and find out.)

Through disassembly (I can do that, the software is GPL'd), it appears that ASUS has extensively modified the asus_acpi kernel module from Linux 2.6.21.4, so that it now works with the eee's hardware. This would be good except that

They appear to have stripped out all attribution. (Kernel modules contain information about the module name, version, and author. This has been removed.)

They appear to have attempted to hide what they were doing. (All references to "asus_acpi" have been removed, but other identifying features remain.)

They are not distributing their modified sources, or even a patch.

I have not contacted the author of asus_acpi, and it's possible that he has worked out a copyright licensing deal with ASUS -- but I was under the impression that the copyright of contributions to the Linux kernel were assigned to Linus or an agent thereof, which would not leave him with this right.

The madwifi drivers that ship on the machine are also a version never before seen in the wild, but as madwifi is dual-licensed GPL/BSD, modifying it is within ASUS's rights.

It's worth noting, from a legal perspective, that ASUS is also distributing BusyBox inside the system's initramfs image. (They do not appear, at first glance, to have stripped the attribution out of this one.) This is interesting because someone else distributing BusyBox without complying with the GPL is currently getting themselves sued in the first US civil suit over GPL violations.

Also worth noting: this is not the first time that ASUS has stolen from the community in this way. They were caught in 2004 stealing code from iptables/netfilter. They're also trying to cover their ass: they include the GPL in the box with the product, and state

This product includes copyrighted third-party software licensed under the terms of the GNU General Public License. ... ASUSTeK COMPUTER Inc. has exposed the full source code of the GPL licensed software, including any scripts to control compilation and installation the object code ... For more information how you can obtain our open source code, visit our website (http://support.asus.com.tw/download/).

...that website, for reference, is Home of the Giant Zip File I mentioned above.

Sigh.

(Edit (2007-11-23): To be fair, as commenters have pointed out, this may very well be simple negligence on ASUS's part. Yes, I and others have contacted ASUS about this with no response yet. Let's hope they just say "Whoops!" and fix the ZIP.)

Warranty Void If Removed

The last annoyance about the eee PC is the bright yellow "Warranty void if seal is broken or removed" sticker over the RAM upgrade slot.

Yes, you read that right: a computer manufacturer has decided that it voids your warranty to replace a DIMM.

The door in question also hides an available mini-PCI-Express slot, so needless to say, people would like to open it. For me, until I get out of the front of the bathtub curve and verify that the hardware works with Ubuntu, that sticker stays intact.

However, since I'm already pretending to be a lawyer in this post, allow me to discuss the Magnuson-Moss Act, what it says about tie-ins, and what exactly ASUS is doing here.

The Magnuson-Moss Act is a 1975 Federal law that lays down some rules for how consumer warranties work. One of the specific things it prohibits are "tie-ins," additional items or services you must buy from the manufacturer to make your warranty work. (This is why for-pay warranties these days are euphemistically termed 'service contracts.')

Examples of tie-ins are provided on the FTC's site. There's the unacceptable tie-in:

In order to keep your new Plenum Brand Vacuum Cleaner warranty in effect, you must use genuine Plenum Brand Filter Bags. Failure to have scheduled maintenance performed, at your expense, by the Great American Maintenance Company, Inc., voids this warranty.

...and the acceptable one:

While necessary maintenance or repairs on your AudioMundo Stereo System can be performed by any company, we recommend that you use only authorized AudioMundo dealers. Improper or incorrectly performed maintenance or repair voids this warranty.

Specifically, it's acceptable to void someone's warranty if maintenance is screwed up. (I'm paraphrasing the FTC's page, which was clearly paid by the word.)

Here are snippets from ASUS's warranty:

The warranty only covers failures or malfunctions occurred during the warranty period and in normal use conditions as will as for any material or workmanship defect. The warranty will not apply if: (a) the product has been tampered, repaired, or modified by non-authorized personnel; ... (c) the warranty seals have been broken or altered; ...

(Yes, those typos were in the original.)

Clause (a) above is clearly unenforceable under Magnuson-Moss -- it's one of the specific cases that the FTC cites as illegal.

Clause (c) follows as unenforceable: repairs (even normal upgrades) of the system cannot be performed without breaking the warranty seal. I'm not a lawyer, but I trust the judgment of judges; I doubt that a warranty stating "You can get this repaired by any qualified person but they can't look at it!" would be upheld. This is no different.

Edit (2007-11-23): One more note on my tie-in point: ASUS will be selling a "higher model" of the eee in the US, with more RAM and 8GB of Flash, starting at the end of this month. Someone will open this model up and post pictures. If the model is simply the original with a different DIMM and, say, a PCIe SSD dropped in, then what ASUS is saying is "These socketed, consumer-upgradeable parts will void your warranty if you touch them -- but if you pay us another $150 we'll change them for you." That's a bit more blatant than what I'd cited above.

Experimenting with LLVM

2007-03-31T14:58:00.000-07:00

My oldest live projects are Mongoose and Cesta, both in intermittent development since 2003. I'm doing a bit of hacking on both right now.

In the case of Mongoose, writing my own VM (or, thus far, four of them) was fun, but it's not viable in the long term. I'd like to target the language to an existing VM, but earlier attempts with the JVM and CLR bore little fruit. (Neither VM is well-suited to dynamic languages with serious metaprogramming facilities.)

In the case of Cesta, I need a way to speedily evaluate filter expressions, and a way to "cross-breed" decoders for parallel fuzzy decoding.

Research on both topics kept leading me back to LLVM, which is many things:

It's a compiler, with frontends for C, C++, and several other languages;

It's a library for designing and implementing transformations on code;

It's a framework for building the backends of new compilers;

It's a well-defined low-level virtual machine;

It's an embeddable code generator, suitable for use in Just-In-Time compilers.

Initially, I was scared of LLVM. I did some hacking on the GCC family of compilers a few years ago, and the code is abjectly terrifying — not to mention the deliberately obfuscated intermediate representations. However, every research lead I followed kept pointing back to LLVM. Eventually, I got up the gumption to download it and try it out.

In short: I am floored. LLVM is almost absurdly easy to work with, thanks to the best-designed C++ API I've ever seen outside of Qt. Within minutes of downloading it, I had built and tested some of my C code using llvm-gcc, their drop-in replacement for GCC.

An hour, two source examples, and 120 lines of code later, I had written a program that generates a Fibonacci function in RAM, JITs it to native x86, and executes it in process, printing the results. (It might have taken longer if the LLVM guys hadn't provided an example that does exactly that, which I was able to learn from.)

This is when I started to notice something: the JIT is impressively fast, considering that I had not activated any of LLVM's impressive suite of optimizations. I coded up two version of the Fibonacci sequence (naïve and hand-optimized) and ran some benchmarks.

The first is the naïve recursive version:


int fibonacci(int x) {
  if(x <= 2) return 1;
  return fib(x - 1) + fib(x - 2);
}

Compiled in a test harness, the times are as follows (suitably averaged and scrubbed of outliers):
fib(24)

GCC 4.0.1, -O0: 1136us

GCC 4.0.1, -O3: 397us

LLVM JIT: 771us

fib(40) (note that units are now milliseconds)

GCC 4.0.1, -O0: 1866ms

GCC 4.0.1, -O3: 618ms

LLVM JIT: 1578ms

Generating this recursive Fibonacci function at runtime (which takes some milliseconds at startup, not included in this benchmark) produces code that runs faster than GCC at -O0. Neat.

Next, the iterative transform of the function:


int iterative_fibonacci(int x) {
  if(x <= 2) return 1;
  int a = 1, b = 1, c;
  while(x > 2) {
    c = a + b;
    b = a;
    a = c;
    x--;
  }
  return c;
}

(The code to generate this at runtime is substantially more complex, since I'm assembling the SSA intermediate representation by hand in C++.)

This algorithm is vastly faster than the previous version, so note that our units below are now nanoseconds.
fib(24)

GCC 4.0.1, -O0: 170 ns

GCC 4.0.1, -O3: 30 ns

LLVM JIT: 51 ns

fib(40)

GCC 4.0.1, -O0: 299 ns

GCC 4.0.1, -O3: 51 ns

LLVM JIT: 93 ns

On this version, LLVM shows an impressive performance gain over GCC at -O0, and is within a factor of 2 of GCC's output at -O3. (Edit: As noted in the comments, running GCC at -O0 is effectively tying both of its hands behind its back. I understand this; I'm comparing to -O0 here because I've not aggressively optimized my LLVM code here and I wanted to try a non-JIT compiler with its optimizations turned off. It's still faster than the M3VM threaded interpreter.)

To try this for yourself, here's where to find the sources:

The LLVM naïve Fibonacci code is in the LLVM distribution at examples/Fibonacci.

The iterative LLVM Fibonacci code.

The recursive C Fibonacci code (for GCC).

The iterative C Fibonacci code (for GCC).

Cocoa Bindings: more on NSArrayController

2007-03-18T15:38:00.000-07:00

After my post on NSArrayController's performance yesterday, Scott rightly pointed out that the behavior I was seeing might be a result of how I was using the class, rather than the class's implementation.

I've boiled down the scenario into a bare-minimum project: ArrayGrowDemo.zip (47k)

I've kept the use of Bindings to the textbook case, illustrated below:

All in all, the only unusual thing I'm doing in the code (a slightly simplified version of the Cesta algorithm) is populating the array continuously from a backing thread, but coalescing the KVO notifications in a foreground thread. For what it's worth, I see the same overall pattern by populating from a perform from the main run loop -- the trends just show faster when the population isn't throttled by the performance of the UI.

The application, when run, will write stats in CSV format to /tmp/arraygrow.log. Run it from Xcode, because you'll need that Terminate button handy: the UI becomes totally nonresponsive very quickly. (This replicates the freeze I saw in the Cesta UI when processing a loaded gigabit link, when I was using NSArrayController.)

Here's a graph from one of my test runs, leaving the NSTableView unsorted. The blue line is the amount of time required to distribute KVO notification that the property has changed size (i.e. that the "array" has grown); from Shark profiles, this is where the NSArrayController code tends to slow down.

(More specifically, the blue line is the time spent in didChange:valuesAtIndexes:forKey: per invocation. Its willChange: brother appears to be constant-time. The red line is the time spent in didChange: divided by the number of items actually changed, showing that — fortunately — the NSArrayController isn't linear with regard to the number of changed items...in Tiger....)

I've run a few variations on this, which you can try by editing the Nib. If you change the model key of either table column to "value.value.value.value", you can see the results of binding to a (pathologically) deeply nested property. This appears to slow things down very slightly, and boosts the time spent in the KVO register/unregister code. (I included this because I expected it to slow things down significantly; it doesn't.)

When sorting the table view on either column, each update remains effectively O(n), but the actual time taken increases substantially. (The sort operation, presumably O(n log n), is lost in the O(n) noise.)

Oh kind readers, please take a look at this source and let me know what I'm doing wrong. I would love to switch back to NSArrayController for my packet view in Cesta -- it would reduce the lines of code I have to maintain.

Edit: Updated the images to fit better.

Cocoa Bindings: mmm, crow

2007-03-17T17:25:00.000-07:00

I should have learned this long ago: when I make a glowing blog post about something, I'm about to learn far more about it than I ever wanted to.

I've been collecting Shark profiles of Cesta all day, as my own personal performance-fixit. I've learned two things.
1. My new decode logic is much faster than I anticipated. (Good!)
2. As a result, all of the CPU Cesta's been chewing up has been -- yes, Cocoa Bindings.

The Bindings framework is not to blame. It's the built-in Controller objects (Edit: or, as Scott points out in the comments, the way I'm using them). Specifically, NSArrayController seems to very aggressively make copies of the multi-valued property it controls. I haven't decompiled it for specifics, but I see enormous NSArrays being allocated -- and that's a class that I specifically avoid. (Granted, NSArrayController was probably not designed to be stuffed with thousands of rows per second. Copying the array makes sense for smaller datasets.)

Moreover, for some reason, it keeps invoking indexOfObject:, which is almost by definition O(n/2) for an unsorted array. When my captures start getting large (hundreds of thousands of packets), indexOfObject: and its partner in crime, CFEquals, start creeping up in my profiles.

This is, of course, nonsense. I've been very careful to only append objects to the end of my capture -- it's a time-series data recording, after all. Unless I'm running a "Find" operation, there should be no reason to run around comparing things.

After lunch today I started running into some really odd bugs with NSTreeController, where it appears to be allocating internal NSArrays to keep track of children, and then reading right off the end of them. I know I'm handling my retains and KVO correctly, so this seems to be a flaw in NSTreeController.

So, I've stripped out all the NS*Controller objects. More trouble than they're worth for this application. I've replaced them with lightweight custom implementations that don't call indexOfObject: or crash. I now have an NSTableDataSource and NSOutlineDataSource again -- but they're both very thin, because I had already designed the data model to be presented in tables and trees.

In subsequent profiling, I noticed something odd. Removing NSArrayController and unbinding my packet table resulted in a 400% overall speedup, which I was expecting, but I got another boost in speed from removing NSTreeController, which I was not. It seems to create an NSArrayController-like object behind the scenes, with all its attendant overhead. (Not to mention that both NS*Controllers create callstacks of 40 or so frames, greatly boosting the use of objc_msgSend.)

Thus, my previous post (which read something to the effect of "OMG BINDINGS ARE FAST") has not proven entirely accurate. I would now rephrase that as follows:
1. Bindings, themselves, are fast. I'm still using them extensively to keep my controllers and data sources in sync.
2. NSControllers, the typical use of Bindings, don't seem to scale well to large update frequencies.

(Edit: After discovering someone actually reading this blog, I cleaned up a couple cases of language that may have been overly pointed.)

Cocoa Bindings: @sum is O(n), even if you're nice to it.

2007-03-17T10:58:00.000-07:00

My last post was very positive toward Cocoa Bindings. A week later, you might say the honeymoon is over.

They still do most of what I need, don't get me wrong -- it's the performance. In profiles, whenever Cesta starts using an entire core on my MackBook Pro, Bindings is responsible for 80-90% of it. (The harder stuff, like capturing, decoding, and constraint-checking a loaded ethernet link, is 2% or less.)

I'm working on isolating each part of the problem, but here's a tidbit for today -- not from Bindings specifically, but from the Key-Value Coding system on which they're built (thanks for the correction, Scott). (Update: I Sharked my way to some of the other Bindings issues in my next post.)

The performance of @sum may surprise you. Specifically, the @sum function is O(n) for the total size of your array, even if you distribute incremental updates using KVO.

This will come as no surprise if you're familiar with how KVC is implemented, but for those of us (me) hoping for a free ride, it's a bit of a downer.

The backstory:

I wanted a nice label on Cesta's summary view showing the number of bytes captured. Lazy as I am, I decided to use Bindings: I created an NSTextField and bound it to the aggregate property "@sum.capturedSize" on my Capture Events NSArrayController.

Now, I put a lot of work into distributing only incremental updates when new packets are captured. My code diligently calls willChange:valuesAtIndexes:forKey and didChange:valuesAtIndexes:forKey with only the changed packets, so that observers don't have to reevaluate the whole array each time. Hell, I even maintain separate state for each thread so that nobody sees new packets before they've received willChange:.

In short, I expected that any observer update that doesn't rely on all the data (like @max would) would be, at worst, O(n) for the number of changes.

I was incorrect, as my debug traces show. @sum is calling capturedSize on every packet, every time.

This is one of three hotspots that cause Cesta's screen refreshes to be O(n) to the number of events captured. The fix? Drop the aggregate function and bind to a scalar property. It's nearly trivial, but I'll include the code here for completeness.

First, we add an ivar for the property, and a getter/setter pair:


@interface CSCaptureDocument : NSDocument {
  ...
  uint64_t _bytesCaptured;
}
...
- (uint64_t)bytesCaptured;
- (void)setBytesCaptured: (uint64_t)bytes;
@end

Then, we add the code for that getter and setter. I won't post it here; there's a button to generate it.

Then, we hook into the packet delivery code:


- (void)frameSource: (CSFrameSource *)source receivedFrame: (CSFrame *)frame
{
    [_capture appendCaptureEvent: frame];
    [self setBytesCaptured: _bytesCaptured + [frame capturedSize]];
}

Then we simply re-bind the "Bytes Captured:" label to the bytesCaptured property of the document, rather than an aggregate property on the NSArrayController. Voila -- instant 15% performance savings.

(Edit: as Scott points out in the comments, this behavior makes sense for @sum since there's nowhere to store the accumulator. I've updated some of the text above to clarify that I'm not attacking @sum here, just pointing out my own very inappropriate use of it -- just in case someone else does the same thing and goes Googling for an explanation.)

Cesta lives!

2007-03-09T20:49:00.000-08:00

I've been putting in a lot of work on Cesta, my network analyzer, due in no small part to continual goading from clee. (He has a Mac now, and is trying to load it up with shiny Mac software.)

I hadn't touched Cesta's code in over a year, and it was getting pretty crufty even then, so I didn't bother trying to modernize it. Instead, I'm applying a marvelous technique I learned from John Brewer: TONSO, or Take Off and Nuke the Site from Orbit.

(It's the only way to be sure.)

The interesting thing is how fast it's come along. I bootstrapped the core system (with an Ethernet decoder) in an evening of work, while distracted by clee and Ben-from-Apple. Starting from a clean slate really helps you reduce a system to its essentials -- and working in Objective-C didn't hurt either. (Still one of my favorite languages of all time.)

I've rebuilt most of what the last Cesta generation could do, and killed off a number of ingrained-but-incorrect assumptions in the old domain model. We should have feature-parity with Wireshark in the not-too-distant future, which is not a slam against the Wireshark devs by any means -- they're very smart. No, it's a tribute to how easy developing Mac software in Objective-C has become.

We're targeting Tiger-and-later with this rev, whereas the original Cesta worked all the way back to 10.2. This makes things a lot cleaner: Mac OS X really is evolving at a breakneck pace, and while all the old APIs are still supported (and much faster), there are new ways of doing everything that are so much better.

Case in point: Cocoa Bindings. Much of the code in Cesta Of Old was dedicated to shuttling pieces of data onto, and off of, the screen. I'm a user-interface geek, so it had to be blindingly fast, absolutely intuitive, and as fluid as Mac apps are expected to be -- and I paid for my high standards in code.

Now? There is no code.

Using Cocoa Bindings, I wire up my UI widgets to my underlying domain model using Interface Builder, and the runtime figures out how best to move and cache the data. The new Cesta UI is entirely Bindings-driven, leaving the whole user interface as a thin projection of the underlying objects -- from the chooser that lets you pick the network interface(s) to capture from, right up to the three-paned packet list and dissector.

If I have to, I can drop in optimizations where needed (Objective-C's category mechanism keeps it clean) -- but thus far, it hasn't been necessary. Cocoa Bindings is fast; far faster than I expected, and they say it'll only get faster with time. It doesn't break a sweat displaying hundreds of thousands of decoded packets in a table. I am impressed.

(I met the folks behind the Bindings API at a recent Cocoaheads meeting, and not only do they produce great things, they're also very friendly and tolerant of n00b questions.)

Not having to hand-code the user interface has freed me up to work on more interesting parts of the application. In the two weeks that this Cesta codebase has been under development, we've added features that I only dreamed of in the last rev. For example, Cesta can now integrate data from any number of network interfaces in a single capture, and can attach and detach interfaces on the fly. (These changes are even recorded inline, right in the capture, for future reference.)

It's also grown a general framework for finding, highlighting, and explaining problems in packets. If an IP checksum is wrong, for example, it's highlighted in the UI, and the user can see a localized explanation of the issue.

We have found one issue, however. clee is totally new to Cocoa, just having cracked open the Hillegass book, and the Cesta codebase is total greek to him -- even though he's a very sharp programmer, fluent in half a dozen languages.

I can't blame him. The main difference between this Cesta and the last is that I now fully grok the Cocoa application/document architecture. It took me a couple years of diligent study to get everything right (because some important parts of it are not terribly well-documented -- and I didn't have the Hillegass book). To a newcomer, the control flow is almost entirely opaque. Sure, you can see that CSCaptureDocument seems to be some sort of document that holds a capture, but it's never created anywhere -- and neither are most of the other classes! How on earth do they talk to each other?

The answer, of course, is that a good chunk of the application logic is effectively hidden. It's not in the source code; it's in property list files, in the Interface Builder nibs, in interactions with closed-source frameworks. To a programmer used to programming, well, code, and accustomed to fully open-source systems, Cocoa can be pretty mysterious. To really understand a Cocoa application, particularly one that has drank as deeply of the Kool-Aid as Cesta has, one must understand all these non-code resources -- and, in some cases, read the API docs on every dependent class, trying to figure out who calls what delegate method and why.

Ironically, the loose coupling that makes control flow hard to understand is also one of Cocoa's greatest strengths. (Though part of the problem -- possibly a large part -- is Xcode, which is firmly lodged about six years behind the IDE state-of-the-art. From a Java perspective, it feels like my 1999 work in Forte, rather than my 2007 work in Eclipse.)

To diverge even further from the alleged topic of this post, this also worries me on my applications at work. Us loosely-coupled object systems guys are leaning pretty heavily on dependency injection and event-driven applications these days, and it may come to the point where the only way to understand the flow of control is to step through the app in a debugger. Not an ideal solution.

Anyway. Coming back around to Cesta, there's one other point of interest: we'll be open-sourcing this version, most likely under a BSD license. I've been out of real open source development for too long. It'll be good to be back.

The wheel of hobbies spins on.

2007-02-24T13:14:00.000-08:00

This is a sort of omnibus update for all my various projects, in case anyone's watching. :-)

My spare-time projects tend to be fueled by interest from others. If I'm doing them just for me, I'll hack on it to solve some interesting set of problems, and then leave them unfinished. The partially-finished systems are useful to me, and solve my problems; packaging and publishing them is only worth it if they'll be useful to others. I do enough software-polishing in my day job that I have a hard time making it a hobby unless I'm helping people in the process.

Speaking of the day job, my workload has increased dramatically since about October. My team has shrunk, but our responsibilities haven't. I'm enjoying it, but it cuts into my spare time.

PropellerForth has stalled due to profound lack of interest from the Propeller community, though I've suddenly (past week or so) gotten a bunch of emails about it. Thus, I may pick it back up, or at least publish the sources so others can carry the torch. (I never got around to publishing before.) I still don't know of anyone using propasm, which is ironic, since I actually packaged it -- the sources are available, and have near-100% test coverage.

I've done a lot of rethinking of Mongoose. I've been working with some of the new batch of next-generation multi-paradigmatic languages, like Scala, but none of them are heading in the direction I want. I'm still using Mongoose primarily to prove some points, and not intending it to be the "next big thing" -- but at the same time, I've been looking at targeting it to existing VMs, with the hopes of achieving interoperability with some last-gen languages. (And not having to maintain my own VM. I hate C++.)

The robots have been dormant lately, but DPR still boots and works (imagine, a Linux system that still works after several months of inattention). I've been learning a lot about machine learning lately in my day job, and I'm hoping to rewrite some of DPR's personality using new techniques like fuzzy associative memories. I'll post here if I get around to it.

So, what have I been hacking on? Strangely enough, Cesta -- my network analyzer, which I've left untouched for nearly a year. My brain keeps coming back to it, because it lets me do the sort of stuff I don't get to do at work (like UI and interaction design), while still presenting a lot of juicy hard problems (like my fuzzy protocol decoding ideas). I'm applying what I learned from the Mongoose compiler to reworking Cesta's protocol decoding layer, enabling it to synthesize new decoders on the fly.

For example, take TCP. TCP connections contain no indication of the protocol they're carrying -- sure, the connection is to port 80, but that's not a guarantee that it's carrying HTTP.

Previously, my solution was brute-force: try to decode every known TCP protocol, eliminating them one by one as they reject the data as malformed. Two years ago I was already looking at more efficient ways to do this, but got caught up in the fun stuff like graph rendering and UI design.

In my reworking of the protocol decoding, I came across a better way. Protocols are defined declaratively using a protocol definition file, which Cesta compiles into decoder code -- and by synthesizing the constraints and layouts of all protocols known to be carried in TCP connections, it can generate a state machine that allows quick and efficient payload-type detection. (And, thanks to the dynamic code generation techniques I learned for Mongoose, I think I can compile the code on the fly without e.g. calling out to gcc.)

If this sounds like massive overkill, you're right -- which is where the machine learning comes in. Using the fuzzy associative memory techniques I've learned recently, Cesta can learn what protocols are most likely to be sent over a given port, and optimize the decoder appropriately. For example, a TCP connection to port 80 is pretty likely to be HTTP, so we can try decoding it as such until proven wrong -- a technique I call speculative decoding. If the guess proves wrong, we can try the next-most-likely protocol, or fall back to the synthetic every-protocol decoder I described above.

As a side effect, we get service-type identification. If Cesta learns that a port on a particular host seems to be speaking HTTP or SSHv2, it records this in the fuzzy memory, and we can present this to the user.

Multiplexed ports or changes in service don't present a problem for this either: it has no difficulty describing a port as "80% HTTP, 20% SSH" if something weird is going on (such as dynamic port mappings on a NAT).

This is complicated -- rather more complicated, in fact, than any network analyzer I've ever used -- but I understand all the techniques involved, and I think I can pull it off. Once there's code, I'll post it here.

Helicam v1.1 initial flight

2007-01-15T22:06:00.000-08:00

I've rebuilt the camera rig and done a lot of tuning to the helicopter, so I'm a bit more confident flying in wind -- but still skittish, as this video shows.

New in this video: the on-board mic is working, and I have remote control of the camera's tilt angle. (I MacGuyver'd an articulating mount out of some corrugated cardboard, a paperclip, a spare 6-gram servo, and some mylar from a Teavana bag.)

CX-Cam flight test video

2007-01-13T10:38:00.000-08:00

Over the holidays, I was working on something rather different. After much experimentation, tuning, and part-hunting, I now have a small aerial camera platform. This is something I've wanted to do since at least middle school, and technology has finally caught up.

The neat part, to me, is that it's nearly off-the-shelf hardware. It's based around a small radio-controlled helicopter and a commercially available wireless camera. (Both are modified, but not extensively.)

Perhaps most importantly, this is something that I'm having fun with, and that others are interested in — a nice vacation from my language/Forth work, which nobody ever comments on. :-)

Here's a video.

More on PropellerForth

2006-11-08T08:40:00.000-08:00

I mentioned in my last post that I hoped to optimize PropellerForth, and get it running faster than 1.7 million (small) words per second (MWPS). Well, this may not be possible. Here's my thinking:

Executing any word requires at least two memory reads: reading the word out of the instruction thread, and reading that word's code field.

Most interesting words require at least one additional memory read (such as pulling a second argument off the parameter stack, or reading an inline argument from the instruction thread). Memory writes are less common, since the top of stack is in a register.

A memory read can only occur once every 16 cycles.

At 80MHz, we get 5 million memory reads per second.

At 2-3 memory accesses per word, we max out at 1.67-2 million words per second.

Thus, for an indirect-threaded interpreter on the P8X32 (the current Propeller incarnation), I'm already nudging up against the theoretical maximum.

Of course, each core can only access memory every 16 cycles — so the Propeller can support eight simultaneous 1.7MWPS Forth kernels.

On a traditional architecture, the next step would be to ditch indirect threading for either direct or subroutine threading — either of which potentially eliminates a memory access from every word. However, on the Propeller this won't work:

Executable code can live only within the 2KB "cog-local" RAM attached to each core. Thus, all CFAs point into this region, not into shared RAM where the dictionary lives. As a result, a single jump instruction cannot target both a machine code word and a user word — so subroutine threading is out.

Likewise, I cannot simply jump to the CFA of a word — first it would have to be loaded into cog-local RAM. Thus, direct threading would probably incur more overhead, not less, from moving each word across address spaces.

I'm investigating other ways of cutting my memory access frequency. Stay tuned.

If the Propeller folks were to ask me for advice on their next architecture (which they haven't), I would make the following suggestions:

Indirect addressing of cog-local RAM. The current architecture treats local RAM as a register file, and (as with most register files) won't indirectly address it through a register. This means all task stacks have to live in shared RAM, slowing things down tremendously. (The stacks can actually live in local RAM, but it requires self-modifying code and ends up more expensive than just using the slow RAM.)

Make the local and shared RAM address spaces disjoint. Combined with the indirect addressing, this would allow a single instruction to read from either local or shared RAM (possibly incurring greatly increased latency). This would make direct-threaded interpreters possible.

Include sign-extending variants of rdword and rdbyte.

Orthogonality is all well and good, but I really miss auto-increment addressing. Being able to auto-increment/decrement a register after a rdlong or wrlong would cut the size of my Forth kernel by nearly 25%, and keep me from missing some hub access windows.

PropellerForth

2006-11-06T08:57:00.000-08:00

Regular readers know my take on the Parallax Propeller microcontroller: neat, 8-core silicon hampered by a platform-specific, very limited IDE (really more of an editor with a Load button) and a programming language I don't much care for.

In the hopes of solving both these issues in one swell foop, I've started work on an ANS Forth for the Propeller — creatively titled PropellerForth. For folks who haven't used Forth, it is simultaneously the most bewildering and liberating programming environment you'll ever use — a computational boot-to-the-head of the same degree as Lisp or Smalltalk. Like these languages, Forth is generally written entirely in itself, and the user can modify even the fundamental operations at runtime in an interactive environment.

The main difference: even modern Forths tend to fit happily in 8K of RAM. (Mine's a little larger than this, now, because I've added in some luxurious libraries.)

Currently, my system image comes in at 8,372 bytes, including all buffers and stacks for the bootstrap task. It executes 1.7 million words (small words) per second at 80Mhz — not a speed demon, but I've still got a lot of room for optimization. It was at 1.4 milion wps yesterday.

The oddities of the Propeller architecture have made this a little interesting:

It's an old-style, string-of-addresses indirect threaded Forth. This is necessary because the more modern styles such as direct or subroutine threading assume you can jump to instructions in the dictionary's data space; the Propeller can't.

The Propeller has no hardware stacks, or indirect addressing of its fast (local) RAM. Thus, the stack is emulated with slow (shared) RAM, entirely in software. This has required a lot of careful tuning.

The Propeller has no hardware peripherals, other than some counters. All I/O, including the serial console, is implemented by the Forth kernel.

Forth was designed for multiuser multitasking on single-core machines, and later expanded to multiuser multitasking on SMP machines. As an embedded system, the Propeller needs single-user multitasking on an eight-core chip — eight cores sharing a dictionary and data space. This means things like semaphores all of a sudden appear in the standard library.

Forth is intoxicating. Once the system is bootstrapped (which required a couple kilobytes of assembler, most of which I generated with some scripts — as I am wont to do), development proceeds exponentially, by defining each layer in the system in terms of the previous.

I believe that every aspiring (or experienced) computer programmer should write a Forth at some point, as a sort of rite of passage. It's challenging, but not because it's hard: because it requires some pretty fundamental paradigm shifts. Writing a Forth will bring you many Aha! moments, and watching the language define itself is quite a trip.

propasm, the Propeller Assembler

2006-10-22T19:01:00.000-07:00

I've released propasm, my assembler for the Parallax Propeller eight-core microcontroller. Unlike the Parallax-provided assembler, it:

Runs on practically anything;

Can be automated from scripts or Makefiles;

Provides really good feedback;

Supports characters outside of US English;

Is written in Java;

Will be open-sourced shortly.

This was an interesting project for me, because it involved a number of separate areas of my brain. This was my first hand-written traditional parser; I've written plenty of parsers before, but this one is broken into a traditional scanner/lexer and recursive-descent parser. Since I was writing the parser by hand, I was able to make the error messages clear and specific — something generated parsers often lack.

I also had to reverse-engineer the binary format and parts of the instruction set, as Parallax's documentation on both is spotty.

Since it's in Java, rather than x86 assembler (like Parallax's), it's somewhat slower. It takes all of 10ms to load, parse, wire, and write out a decent-sized program.

...of course, to use Parallax's, I have to boot Windows, start an IDE, open my text file, and click four times in a menu. I think propasm wins overall. :-)

Update: I'm already on my first point release; I'd made an error on the I/O code that caused UTF-8 to be mangled on some platforms. Fortunately, my test case using ウーロン茶 as a variable name failed. If only I'd had the tests written when I released... :-)

Mongoose Reborn

2006-10-12T20:27:00.000-07:00

In any other context, this would probably be a bad thing:


Mnemosyne:~/Projects/m3/vm cbiffle$ ./vmtest test.mgm 
HEAP: 0x2800400 - 0x2801400
HALT

But in this case, coming to a screeching halt is exactly what I wanted.

M3VM, the third virtual machine for Mongoose, has officially booted some code (even if that code was a single halt-catch-fire instruction). This is the third time in two years that I've rewritten the VM from scratch, proving hands-down that I have very weird hobbies.

This time, it's in C++, which has been trippy. I haven't written any large C++ apps in three years, and I really dislike the language — but it happens to be ideal for this, so I'm ignoring the nasty bits and making do. M2VM was written in GNU C, and M3VM isn't much different — but I can bundle my functions into classes now. For an object-head like me, that's a big plus.

Working with a higher level of abstractions has also let me focus less on the details, and more on the goal. I've built the object model the way I wanted it, and I'm working on the neat Self-like optimizations I've had planned.

To get to the triumphant HALT, the machine had to

Load the base module, in the new Mongoose Module format;

Wire all the objects together, including the ones that have to exist in phantom form (like Object, Class, and Array) before they are loaded;

Start the interpreter, written in Mongoose and translated by Ruby to C++;

Resolve the entry-point method by name;

Fall over screaming.

The rewrites are quicker each time. Not only is the line count of M3VM significantly lower than M2VM, it took less than a week (part-time) to write. It's also considerably smarter — the garbage collector, my fourth, has learned a lot of neat tricks, and runs in milliseconds even for fragmented 64MB heaps.

Soon, I'll have the compiler working, so I can quit writing code in a hex editor. :-)

(P.S. If you, too, are authoring files in a hex editor, you need to go download Hex Fiend. Seriously. It is, hands down, the best hex editor I've ever used — including the ones I've written.)

Type Inferencing for Mongoose

2006-09-12T09:34:00.000-07:00

After a few months of meditation, Mongoose's type system has finally come together. It lives in a several-dozen-page VoodooPad document right now, but I'll summarize it here.

Protocol-based, the OO equivalent of structural typing. A "type" describes an object's externally-visible operations, not where it gets its code.

Pragmatic. Supports both "subclass-to-specialize" (as in Eiffel) and "subclass-to-extend" (as in every other OO language), without the holes in Eiffel's type system.

Simple. All the safety and flexibility of Java's generics, the loose hierarchy of duck-typed languages like Python or Ruby, but with very thorough static checking (if you so desire) — and yet, far simpler to learn than Java's type system.

Optional. 'Nuff said.

Some of the problems I've managed to solve recently include:

How substitutability (in the Liskov sense) works in a protocol-typed language, with an adaptation of co-contravariance.

How to handle union and intersection types.

How to run an inferencer over the whole shebang.

This post is really focused on that last point: I got the inferencer working for simple cases.

Take the following code snippet, which defines a simple stream class that produces the Fibonacci numbers. To fill in for the standard library, this snippet also defines a protocol Integer (the protocol of numeric literals), and stubs out a protocol Boolean (the protocol of the literals true and false).

When reading, remember that, like Smalltalk, the caret character ^ means "return."


protocol Integer {
 (* A method named "+", which takes and returns an Integer *)
 method + other (Integer) ^ (Integer).
}
protocol Boolean {
}
class FibonacciStream {
 var a := 1.
 var b := 1.

 method hasNext [
  ^true.
 ]

 method next [
  var c := self twoValuesAgo + b.
  a := b.
  b := c.
  ^c.
 ]

 (* This method is here only to introduce some indirection. *)
 method twoValuesAgo [
  ^a.
 ]
}

(Long-time readers will note that, yes, the syntax has changed yet again.)

Of note: the FibonacciStream (the actual user code here) has no type annotations at all.
Also of note (at least because it confused the early inferencer): The types of a, b, and c all depend on one another.

Despite the lack of user type declarations, the inferencer actually has a lot to work with: it knows that a and b begin life as Integers, and it knows the signature of Integer's "+" method. This is sufficient to derive all the types in this class, as you can see in the output from the inferencer:


protocol Integer {
  method + other (Integer) ^(Integer)
    
}
protocol Boolean {}
class FibonacciStream {
  var a (Integer) := 1.
  var b (Integer) := 1.
  method hasNext ^(Boolean)
  [
    ^true.
  ]
  method next ^(Integer)
  [
    var c (Integer) := self twoValuesAgo + b.
    a := b.
    b := c.
    ^c.
  ]
  method twoValuesAgo ^(Integer)
  [
    ^a.
  ]
}

The inferencer has different formatting tastes than I do; it seems to use two spaces instead of tabs, and put its brackets on their own line. I'll fix this egregious error later. :-)

The inferencer has some other neat tricks, not shown here (because they mostly crop up in really weird designs). It can handle variables that change type over their lifetime, either by synthesizing a union-type or by splitting the variable, SSA-style. It also does all sorts of neat things with Mongoose's generics system, but I'll write more on that once I get the damn thing working. :-)

Update: The case I cite above, where a variable changes type over time, is now a warning. You can use a type declaration to express your intention if you really want it to happen, but I find that (in Ruby, at least, which is the most similar language I work in) it's almost always a bug.

ASCIIvision

2006-06-26T11:43:00.000-07:00

After a lot of tinkering, I've got the Gumstix talking to my CMUcam2.

I started out working with CMU's Java interface code, but it's abysmal. It's like an exercise in how not to write Java. So, scratch that.

I worked in C for a bit, thinking that it would be nice to eliminate the JVM from my cramped root filesystem. Then, I remembered how much IO programming in C can suck, and went back to Java.

So, now, I've written my own interface library for the CMUcam. I quickly got tired of printing numbers and guessing whether or not I had configured the camera properly; I wanted an image, dammit. But on a tiny device, with no display, how do you generate images?

Using ASCII, of course!

Gumstix -- first experiences

2006-06-22T19:47:00.000-07:00

I've finally given in and bought a single-board computer from Gumstix. It's amusingly dinky.

That thar's a 400MHz RISC machine, with 16MB of on-board Flash, 64MB of RAM, and Bluetooth (with antenna attached). It comes out of the box running Linux. I have daughterboards that add RS-232-level serial ports, USB client, and a CompactFlash slot for disk or WiFi.

I've been working with the board for a few days now, and thought it time to post my first experiences.

All in all, I am damn pleased. I haven't had this much fun with an embedded system in years. However, there's a topic that deserves an initial rant.

The Support Rant

First thing: if you want solid support or well-organized technical information, look elsewhere. Gumstix, the company, has no obvious contact information; when I finally tracked down an email address, they redirected me to a public mailing list.

Ah, yes, I remember what running Linux is like.

The good news is, the mailing list is very helpful. I'm sure my questions had been asked a dozen times before, but I received not a single RTFM.

Which is fortunate, as there's no M to FR -- there is no manual. All documentation on the Gumstix and accessories, from features and drivers to pinouts and compatibility matrices, is hidden in a Wiki. And hidden it is. This is one of the worst-organized Wikis I have ever seen, with several pages on any given topic, each of which claims to be canonical and all of which are wrong.

Example: there are pages in the Wiki that discuss setting up the Gumstix development environment on Mac OS X. Don't try it. They're out of date by nearly two years, and will have you check out a branch of the repository that's about that old. Not only do the directions not work, you'll be stuck with an ancient system with very few of the optional packages available.

Example: the PXA255, the processor at the heart of this board, has four UARTs. I remembered this from hacking Linux on my PXA255-powered iPaq years back. You can get various combinations of these UARTs on various daughterboards, sometimes with level-shifters, sometimes at TTL level. However, the actual online store, where you would go to buy such things, doesn't have this information. No, you must dredge the Wiki.

This is includes pretty damn basic details, like which UART the onboard Bluetooth is attached to. (It's the BTUART pins, for those arriving here by Google, but the HWUART driver, routed to the BTUART pins. So, by default, both the HWUART and BTUART are occupied. You can, however, route the HWUART to auxiliary pins.) Likewise, I had to trace schematics to determine which UART their optional GPS would occupy. (It's the STUART, routed through the FIR pins.)

And, here's the kicker: my original board configuration wouldn't have worked, though there's no information on the website to indicate this. Enabling both Bluetooth and the CompactFlash board means the HWUART can no longer be used for anything but Bluetooth. Add the GPS module and I'm down to a single serial port -- not enough for what I'm doing.

Fortunately, I'm pretty familiar with the PXA255 and can trace schematics. Otherwise, this would have been a rude surprise.

Okay, now that that's out of the way:

The Good Stuff

Getting into the Gumstix via Bluetooth from my Mac was trivial. I had a wireless console in well under five minutes. It goes a little something like this:
1. Pair with the Mac from the Gumstix side, since the Gumstix (by default) can't interactively request a PIN. Use hcitool scan to find your Mac, hcitool cc [ your address ]; hcitool auth [ your address ] to pair; the default PIN is 1234.
2. On the Mac, open Bluetooth Preferences, find the Gumstix in the Devices tab, and click Edit Serial Ports.
3. Accept the defaults it offers you.
4. Connect from your favorite terminal emulator; the port is named (by default) Gumstix-1, or /dev/tty.Gumstix-1, to you Unixy types.

All in all, the quality of the Bluetooth support (via BlueZ) blows my mind.

The Gumstix guys have also put together a very nice Linux distribution. It smells like it's based on Familiar -- which is fine by me, having used it in the past. If you have a recent Linux box, you are a Subversion-checkout away from cross-compiling your own images to the board.

They've even got interactive menus for selecting what packages and options to compile into the image; their scripts will go out and fetch the requisite sources and compile everything automatically. Very slick, and it works far better than the buildroot for Familiar did. I had JamVM for Java and the GNU Classpath libraries installed with almost no work at all.

Now I just need the parts to interface this bad boy to the robot....

The Mongoose syntax evolves, with a comparison to Java

2006-05-27T20:29:00.000-07:00

I'm tinkering on a new syntax for Mongoose, which incorporates the type system I've spoken of in the past.

As an example, let's look at a simple Java class, and how we would implement the same class in Mongoose.

This class is called Filter, and comes from some dataflow-style processing code of mine. Basically, this code constructs a pipeline of producers and consumers, each of which does some processing or conversion of the data. Producers will finish when they have completed processing and will produce no further output. This finished status propagates forward through the other stages, and is used at the terminal stage(s) to trigger report generation or aggregation.

The Filter can sit between some number of Producers and some number of Consumers. It tests its input, and if it matches some condition, passes it on.

First, the groundwork. These interfaces implement the Producer/Consumer pattern, with some additional signalling for when processing at each stage has completed.


interface Producer<E> {
  void addConsumer(Consumer<E> consumer);
  void removeConsumer(Consumer<E> consumer);
  boolean isFinished();
}
interface Consumer<E> {
  void consume(Producer<E> source, E input);
  void producerFinished(Producer<E> producer);

Pretty straightforward. Now, I have a lot of different implementations of Producer, some of which need to inherit from existing classes (generally for legacy reasons). Thus, I package up the basic Producer functionality in a ProducerSupport class, to which Producers can delegate most operations. It has two utility methods, emit and finish, that the owning Producer can call to control its operation.


class ProducerSupport<E> implements Producer<E> {
  final Producer<E> owner;
  final Set<Consumer<E>> consumers = new CopyOnWriteArraySet<Consumer<E>>();
  volatile boolean finished = false;

  ProducerSupport(Producer<E> owner) { this.owner = owner; }

  void addConsumer(Consumer<E> consumer) { consumers.add(consumer); }
  void removeConsumer(Consumer<E> consumer) { consumers.remove(consumer); }
  boolean isFinished() { return finished; }

  void emit(E output) {
    for(Consumer<E> consumer : consumers) consumer.consume(owner, output);
  }

  void finish() {
    finished = true;
  }
}

Now, the Filter class. I've cut some corners in this example — for example, it supports only one producer — but bear with me.


class Filter<E> implements Consumer<E>, Producer<E> {
  final ProducerSupport<E> ps = new ProducerSupport<E>(this);
  final Predicate<E> predicate;

  Filter(Predicate<E> predicate) {
    this.predicate = predicate;
  }

  void consume(Producer<E> source, E input) {
    if(predicate.matches(input)) emit(input);
  }

  void producerFinished(Producer<E> producer) {
    ps.finish();
  }

  void addConsumer(Consumer<E> consumer) { ps.addConsumer(consumer); }
  void removeConsumer(Consumer<E> consumer) { ps.removeConsumer(consumer); }
  boolean isFinished() { return ps.isFinished(); }

  static interface Predicate<E> {
    boolean matches(E input);
  }
}

And we're done. Nowadays, the good news is that most IDEs will write delegate methods (like those above) automatically.

To use Filter, one would write code like the following:


Filter<Foo> filter = new Filter<Foo>(
  new Predicate<Foo>() {
    boolean matches(Foo input) {
      return foo.name.equals("bob");
    }
  });
previousStage.addConsumer(filter);
filter.addConsumer(nextStage);

Now, the Mongoose version. I'll go through two iterations, the first closer to the Java version.

A couple quick notes on this syntax:

For generic types, the formal parameters and invocation type parameters are given in [square brackets].

Type annotations are given in <angle brackets>. They follow the argument or slot that they describe. Methods may have an additional annotation describing the return type; if present, it follows the argument list and is separated by the return symbol ^.

If this reminds you of Strongtalk, you're a geek.

Yes, there are two types of brackets in these definitions. Square brackets surround blocks of code; curly brackets surround structural definitions. This may seem annoying, but there's actually a good reason for this (which unfortunately doesn't come up in this example).


protocol Producer[E] {
  method addConsumer: consumer <Consumer[E]>.
  method removeConsumer: consumer <Consumer[E]>.
  method finished ^ <Boolean>.
}
protocol Consumer[E] {
  method consume: input <E> from: source <Producer[E]>.
  method producerFinished: producer <Producer[E]>.
}

No big difference here. Moving along:


class ProducerSupport[E] {
aspect class:
  constructor for: owner [
    _owner := owner.
  ]

aspect instance:
  implements Producer[E].

  slot _owner <Producer[E]>;
    constant.
  slot _consumers := Set[Consumer[E]] new;
    constant.
  slot _finished <Boolean> := false.

  method addConsumer: consumer <Consumer[E]> [
    _consumers include: consumer.
  ]

  method removeConsumer: consumer <Consumer[E]> [
    _consumers remove: consumer.
  ]

  method finished [ ^_finished ].

  method emit: output <E>;
    private
  [
    _consumers each: [ :c | c consume: output from: owner ].
  ]

  method finish;
    private
  [
    _finished := true.
  ]
}

The interesting bits, starting from the top:
Behavior and state in Mongoose classes are separated into two aspects, class and instance. This is equivalent to the static/member divide in languages like Java or C++. The main difference, in Mongoose, is that the two can actually be defined separately, though I haven't done that here.

The method #for: is implemented as a constructor, which is analogous to Java and C++ again, but a bit more rigorously defined and flexible. A constructor, in Mongoose, is a method that is invoked on a class, but executes on an object. More importantly, a constructor is invoked like any other method on the class; callers don't know they're invoking a constructor, and you can change the implementation — for example, to return a singleton instance, or delegate to another class — without changing the callers.

Notice that the owner argument to #for: lacks a type annotation. This is an implementation shortcut; because the argument is being directly stuffed into the slot _owner, which has a type annotation, the type can be inferred. (Callers would see the type annotation when inspecting the class.)

The rest is pretty simple. The words constant and private following slot and method definitions (after the semicolon) are attributes. constant says that a slot, once initialized, will never change; this also allows you to omit the type annotation. As with final fields in Java, the slot must have an explicit initializer, or be set in a constructor. private says that a method is only available to other code within the class or subclasses thereof.

Now, to Filter:


class Filter[E] {
aspect class:
  constructor using: predicate <Block[E, Boolean]> [
    _predicate := predicate.
  ]

aspect instance:
  implements Producer[E] via _ps.
  implements Consumer[E].

  slot _ps := ProducerSupport[E] for: self;
    constant.
  slot _predicate <Block[E, Boolean]>;
    constant.

  method consume: input <E> from: source <Producer[E]> [
    (_predicate evaluate: input)
      ifTrue: [ _ps emit: input ].
  ]

  method producerFinished: producer <Producer[E]> [
    _ps finish.
  ]
}

Most of this you've seen above; we have a basic constructor and some instance behavior and state. However, a few points here merit further explanation.

The constructor takes the predicate, which performs the actual filtration. It's typed as a Block, which is a standard Mongoose class describing a block of code (as in Smalltalk).

Notice, in the instance aspect, that we're missing most of the code from the Java implementation. The key is the second line in the aspect:
implements Producer[E] via _ps.

This is called a via, and allows us to explicitly delegate all messages in the Producer protocol to another object — in this case, the object in the slot _ps. Variations on vias allow you to delegate only a portion of a protocol, or a few named messages, but those aren't applicable here.

In our case, the contents of _ps are constant, but we might choose to switch out the object; any messages in the Producer protocol would automatically be forwarded to the new object.

So, we've reimplemented the Java version without some tedious, boilerplate code. How would we use such a class?


filter := Filter[Foo] using: [ :foo | foo name = "bob" ].
previousStage addConsumer: filter.
filter addConsumer: nextStage.

Simply passing in a Block that performs our test is a lot simpler, not to mention more concise, than Java's anonymous class mechanism.

So, we've eliminated a chunk of boilerplate code, and made the class easier to use. However, we can do better. Delegation is all well and good, but in this case, we're delegating to a single object that was specifically designed for delegation.

This pattern smells like Java. There's a better way to do this in Mongoose.


trait ProducerSupport[E] {
  implements Producer[E].

  slot _consumers := Set[Consumer[E]] new;
    constant.
  slot _finished <Boolean> := false.

  method addConsumer: consumer <Consumer[E]> [
    _consumers include: consumer.
  ]

  method removeConsumer: consumer <Consumer[E]> [
    _consumers remove: consumer.
  ]

  method finished [ ^_finished ].

  method emit: output <E>;
    private
  [
    _consumers each: [ :c | c consume: output from: self ].
  ]

  method finish;
    private
  [
    _finished := true.
  ]
}

ProducerSupport, in Java, was designed as a reusable unit to provide Producer behavior through delegation. Here, we've reimplemented ProducerSupport as a trait — a reusable chunk of state and behavior that classes can include. The code in ProducerSupport will run within the class that includes it, so we've eliminated the concept of "owner" and the accompanying code — now, the ProducerSupport is the owner, and vice versa.

Let's reimplement Filter using this new trait.


class Filter[E] {
aspect class:
  constructor using: predicate <Block[E, Boolean]> [
    _predicate := predicate.
  ]

aspect instance:
  includes ProducerSupport[E].
  implements Consumer[E].

  slot _predicate <Block[E, Boolean]>;
    constant.

  method consume: input <E> from: source <Producer[E]> [
    (_predicate evaluate: input)
      ifTrue: [ self emit: input ].
  ]

  method producerFinished: producer <Producer[E]> [
    self finish.
  ]
}

I've highlighted the changes. By including the ProducerSupport trait, we've automatically gained all its behavior — so we no longer need to keep track of a ProducerSupport instance, or delegate using the via. Filter also automatically implements the protocols exposed by its included traits — in this case, Producer.

Filter, at this point, has degenerated into a basic Adapter pattern, converting the language's Block construct for use in the producer-consumer architecture. The class is nearly trivial.

I've tried to demonstrate the utility of the following Mongoose features:

Linguistic support for delegation through via.

Blocks.

Traits.

This new syntax is a work in progress; all the concepts described here work in my current Mongoose implementation, but the compiler is evolving as I work. Any comments, suggestions, or questions are welcome.

Resuming exceptions in Mongoose

2006-04-01T16:40:00.000-08:00

Since the initial rev of Mongoose's Signal framework (the basis for its exception handling), exceptions have supported resumption. You can send the message #resume to an exception and, if it supports resumption, execution will continue as though the exception had not been signaled.

Generally, of course, this is a bad thing, and most exceptions don't support resumption. There are a few that do, however; one of these is EncodingException.

EncodingException is signaled by a CharacterDecoder object when it encounters invalid data in its input. For example, the UTF8Decoder will signal an EncodingException if it encounters truncated, invalid, or overlong sequences in the input.

CharacterDecoders agree (in their interface) that if the EncodingException is resumed, they will insert the Unicode replacement character (U+FFFD) in their output and attempt to continue decoding.

So, let's look at two ways of handling a malformed UTF-8 byte sequence, taken from the UTF8Decoder test suite:


| fragment |
(-- Malformed sequence; the initial 0xC2 is missing a byte, and 0xA2 is spurious --)
fragment := #( 0xC2, 0xC2, 0xA1, 0xA2, 0x48, 0x65, 0x6C, 0x6C, 0x6F, 0x21 ).

UTF8Charset decode: fragment.

This code will die with an EncodingException (with a message reading "Truncated form at 1"). Now, we want our decoder to be more tolerant, so let's have it gloss over these issues.


| fragment |
(-- Same byte sequence as before --)
fragment := #( 0xC2, 0xC2, 0xA1, 0xA2, 0x48, 0x65, 0x6C, 0x6C, 0x6F, 0x21 ).

| characters |
[
  characters := UTF8Charset decode: fragment.
] on: EncodingException do: [ :ex |
  (-- Replace invalid sequence with U+FFFD and attempt to continue. --)
  ex resume.
].

characters do: [ :c |
  Console writeCharacter: c.
].
Console writeCharacter: Character newline.

So, rather than dying, this fragment prints:

�¡�Hello!

In an upcoming revision, you'll be able to provide a character or character sequence to use in place of invalid input, and have some control over overlong encodings specifically.

(Readers might note some subtle syntax changes in the code fragments above. The Mongoose syntax is evolving as we build out the standard libraries; stay tuned.)

Update: god, I love this language. The enhancements are in place, in under a dozen lines of code.

If you catch an EncodingException ex, your options are as follows:

ex resume will resume decoding. If the exception was signaled due to an invalid byte sequence, it becomes the Unicode REPLACEMENT CHARACTER U+FFFD in the output. If the exception was signaled due to an overlong encoding, it is decoded as if it were valid. (This replicates the behavior of most (broken) UTF-8 decoders.)

ex resumeAndSkip will resume decoding; whatever input caused the exception will simply be ignored, and decoding will resume after it.

ex resumeAndSubstitute: someCharacter does exactly what it sounds like: substitutes a character of your choosing for the invalid input. So, to be like most Unix libraries, you can substitute '?'.

Nutshell: my thoughts on static type checking

2006-03-20T21:51:00.000-08:00

I've been giving a lot of thought to static type checking in Mongoose — for three years now, in fact.

Static type checking has a bad name these days, with programmers advocating fully dynamically-typed languages for productivity reasons, or to avoid complexity.

I agree with the gist of the argument, but I feel it's based on bad data. Here are my arguments. (I'm not making the "static type systems allow for more optimizations" argument, since Self proved that one wrong 13 years ago.)

1. The popular static type systems are the worst examples.

Ask one of these programmers for an example of a static type system that holds them back. I will virtually guarantee the answer is likely to be C, C#, C++, Java, Pascal, or Delphi.

I will also virtually guarantee the answer is not Ocaml, ML, or Haskell, three strongly-typed languages — stronger even than the C family or Java, as they lack pointer aliasing, casts, and other ways to accidentally goof up your types at runtime. And yet they don't get in the way (though the lack of operator overloading in ML is unfortunate).

There are a number of reasons for this. The ML family provides incredibly good type-inference support: the compiler looks at the operations you're performing on a value and where it came from, and deduces what type you wanted. (In most interactive environments, it will report the types it deduces, so you can see if you screwed up. Yes, the errors are yours, the compiler knows its stuff.) As a result, the ML family (including Ocaml) doesn't require you to pedantically type every variable, like the C family.

Microsoft added a sort of type-inference to C# in the latest version, but it only saves you from declaring your variable types — instead of int x you get to write var x. Woohoo. Compared to ML, this is a toy feature, and it's a really bad fit for the language, in my uneducated country-boy opinion.

2. Type declarations — or type annotations, or whatever you want to call them — are excellent documentation.

Maybe I'm just a bad programmer, but in Ruby, I find myself passing Strings when I really wanted to pass Integers all the damn time. The program usually doesn't die until runtime — but it usually does die, all because I forgot a to_i somewhere in my parsing code.

This is exacerbated by the fact that Strings, in Ruby, overload most arithmetic operators. Rather than dying as soon as I try to add or shift a String, I just get a weird String. (I do like it better than the transparent conversions in Perl, I'll say.)

I have the same issues with Smalltalk. Sometimes, it's just really nice to have documentation on what the expected type of a parameter is, what a function will return, or whether or not something can be null. A lot of Smalltalk code fakes this, by naming the parameters after their expected type — aSmallInteger, for instance. This is really just an overgrown Hungarian notation, and violates one of my basic principles of software design: values should be named for their roles, not their types.

3. Having a tool to check the accuracy of your documentation rocks.

When writing Java in an IDE, I always leave Javadoc checking enabled.

For those of you fortunate enough to have avoided Java, Javadoc-checking in an IDE verifies that your parameters are documented, their declared types are correct, and so forth — in your comments. It verifies that your comments are in sync with the source. This is wonderful, since in Java, comments duplicate the information in the method signatures. It keeps them from getting out of sync.

Type declarations on parameters and results are a form of documentation — and, in a static type system, they're checked by a tool called the compiler.

4. A sufficiently expressive static type system doesn't bind your hands.

On this point, I must return — as I so often do — to Strongtalk.

Strongtalk is a descendant of Smalltalk, a totally dynamic language. One of the real powers of Smalltalk is its genericity: a parameter can be of any type at all, and as long as it responds to the set of messages you send it, your algorithm will work. Pass it an integer, pass it a user-defined currency type, pass it a complex number — it doesn't care, and neither do you.

Strongtalk sports a static type system that preserves this power. First, it's optional: if you honestly want a parameter to accept any type of object, that's fine.

Second, it doesn't confuse "class" with "type." Sure, you can say "this parameter must be a SmallInteger" — but you can also say "this parameter must respond to this set of messages with these types" In other words, you can describe the type in the same way that Smalltalk does (and Ruby does, and Python does, and...) — but in an explicit fashion, and one that the compiler can check for you!

Strongtalk's type system is by far the most powerful and expressive that I've used. It, single-handedly, convinced me that static typing was not a dead end — but rather the path of least resistance.

Something that Strongtalk, near as I can tell, didn't do is infer the types and write the type declarations for you — but there's really nothing preventing that. This is one of the features I'm working into Mongoose, albeit slowly.

5. Explicitness is good.

I like explicit code. (Yeah, I've worked for porn sites, but no jokes, please.) I like explictness of intent, both on the part of the programmer, and on the part of third-party components.

Static type systems are only one step in that direction. Pre/postconditions and loop and class invariants are another. (Really, type systems are a specific case of this, but I feel they're best expressed separately.)

I'm in the very early stages of a contract-inference engine for Mongoose code, which will save the programmer the grunt work of writing pre/postconditions. Stay tuned.

M2VM status report

2006-03-19T16:26:00.000-08:00

M2VM is coming along. It's proving as flexible as I'd hoped — even changes to pretty fundamental structures, like the layout of an activation record, go off without a hitch.

Hooray for metaprogramming, I say.

Some notes:

- My strict adherance to standard C (the GNU99 dialect, anyway, which I consider a standard) has kept portability simple. The current codebase works great on all combinations of {Linux, Mac OS X} x { PPC32, PPC64, x86 }, without any architecture-specific defines or conditional compilation. Of course, it also forces me to fight GCC's decisions in some areas, but I'm working on that.

- Holy crap the Core Duos are fast.

- Basically all of my development right now is in Mongoose; the C layer is mostly finalized, for now. Even metaprogramming stuff like exception handling (which has to interact with the callstack), reflection, and dynamic loading is in Mongoose. It's fun like Forth, but with better abstractions.

- My Module abstraction seems to be good. Modules contain classes and/or other modules, and serve as the largest granule of access control and scoping. You can provide a filter when you load a Module, to prevent it from accessing, say, the reflection classes.

The exception-handling facilities are coming along. I've put together a brief (and possibly cryptic) slide stack explaining the Mongoose exception mechanisms (244k PDF), explaining the various nuances. (It supports Java-style unwind-and-abort handling, PL/1-style resumption, and a few other options.)

Indirect threading is...slower?

2006-03-14T20:46:00.000-08:00

Well, that was unexpected.

M2VM so far has been using the switched-interpreter mode of my VM generator.

As of yesterday, my profiler no longer says the GC is the bottleneck — now, it's the interpreter loop. So, logically, I've started to optimize it.

As a first step, I switched the VM generator to produce indirect-threaded code — simply looking up the address of each bytecode's code, using an array of addresses (one for each bytecode). I expected this to be faster.

It's about 10% slower on my benchmarks. (It's about the same speed at -O1, but at higher levels it gets slower and slower.)

I'll drill down with some profiling to see if I can find the cause, but this kinda blows my mind. The generated code for the switch statement was the hottest in the module, so I assumed that, by getting it out of the way, things would speed up.

Hrm.

Update: This is only true on the G4/G5. On an Intel Core Duo system, the indirect threaded interpreter is an instant 10% speed boost. However, I've found an issue with GCC's code generation that's ruining my indirect branch prediction rate — which may explain the issues on the G5.

Politeness

2006-03-13T23:45:00.000-08:00

I've been thinking more about the Politeness Principle I mentioned in the last entry, and I think it's pretty descriptive. In this post, I'll illustrate it with an extended metaphor: food service.

First, let's start with a procedural/imperative food service.

Assume for the moment that, in some sort of bizzare Zamyatin fantasy, everyone is identical. The food service folks come to your little cubicle three times a day and stuff food down your throat. You have no say in how much or what you're fed — it is literally stuffed down your throat.

This, as I think we all can agree, is the least polite level of foodservice. It's also basically how most imperative programming styles work: a single process is in control (the program) and it directly modifies data.

Everyone doesn't have to be exactly the same; there can be some variation, as long as it's evident to the program. When people arrive at work, they could receive a colored card, stuck to their forehead, indicating the type of eater they are. A red card, say, might indicate lots of food, while a blue card indicates less food. The food service folks come by, look at the card, and stuff food down your throat.

Now, say you want an amount of food in between the two extremes — or say you're fasting or not hungry that day. You stick a purple card to your forehead.

The food service folks come by, look at your card, and have no well-defined response. If you're lucky, they might get confused and move on to the next person — if you're unlucky, they might stuff all the food down your throat, or remove you from your cube and replace you with a human-shaped stack of mashed potatoes. The foodservice person might even commit ritual suicide at your feet. The behavior, either way, is undefined. In programming, this is called a "tagged type" — it has a tag indicating how it should be dealt with. As in foodservice, a program must be warned of all the possible tags in advance, or undefined (read: usually bad) things may result. Generally this is either lost data, or corrupted data (replaced with mashed potatoes) — or a program crash.

So, we define some new tags for new types of eaters. Say, green for vegetarian, black for fasting, white for no-gluten. Then we need a new color for vegetarian-heavy-eater, no-gluten-heavy-eater, etc. — every combination we want to handle. This will quickly spiral out of control, with the foodservice people needing to carry tomes explaining what to do in any given case. The foodservice job has gotten very complex, because the people are treated as dumb: they are given a tag, and that's the only communication.

At this point, some bright young foodservice luminary might suggest a revolutionary idea: "Why don't we ask the people?" This is basically the paradigm shift that Smalltalk brought to programming: don't put all the intelligence in the process, let the data itself be intelligent. But a first crack at this is almost always wrong.

The foodservice worker arrives at your cube one morning and, without even looking at your tag, says "Would you like one or two helpings of meat?" "Oh, no thanks," you say, and the foodservice worker shoves one helping down your throat. (The vegetarian next door is even less happy about this.) The question was wrong, and you gave an unexpected answer. This is usually what procedural programmers do when let loose in an object-oriented language like Smalltalk: they let the data be intelligent in all the wrong ways.

It's still not very polite. You're not given freedom of choice, and you certainly don't get to eat at your own pace. Sure, you get to answer a question now, but your eating is still being micromanaged.

As a next crack, the foodservice fellow says "Pick one of the items from this list." If one of them suits you, great, and he shoves it down your throat. If none of them are appropriate, well, too bad, you don't get to eat.

A lot of software systems are half-polite. By analogy, the fellow would roll up a buffet of eats, with some prepared dishes and some raw ingredients, perhaps with a small array of cooking utensils. He would wait patiently while you prepared a dish to perfectly suit your liking, or allow you to refuse if you weren't hungry.

And then he would shove it down your throat.

In a slightly more refined system, he would wait until you had prepared the dish, and then move your arm to the fork and guide it into your mouth for each bite. If he were really nice, he would watch for cues (bloating, vomiting) and stop feeding you, but don't count on it.

All this throat-shoving and force-feeding is starting to make you feel a wee bit violated, and that's exactly the term used in software: specifically, this is "violation of encapsulation." Your eating procedures — and, for that matter, your gastrointestinal tract — are your business, and are encapsulated away from the foodservice procedures.

This allows each eater to have variations. Some folks eat slower; some folks (the author included) tend to just tilt the plate back and let the entire meal plummet to its digestive doom. Just as a polite procedure lets you pick and choose your own ingredients, a really polite procedure would just let you freakin' eat.

So, ideally, the buffet would wait as you consumed your meal (or didn't) at your own pace, let you take another helping if required, and then bid you adieu. This would be polite.

The essence of the principle is this:
1. Don't micromanage.
2. Don't poke around in peoples' privates.
3. The easiest way to allow individual variation is to let people do things for themselves.

This can be applied to software design, as I'm doing with Mongoose, by replacing "people" with "software components." In the LinkedList I described in a previous post, I noted that the program doesn't forcefully grab some elements of the list and do actions on them; the process is closer to "Hey, element x, do this, and ask your neighbors to do it too."

As for individual variation, I dropped in an alternative Link implementation, RunLink, that can represent multiple identical elements with a single node. It required no changes to LinkedList, because LinkedList didn't care about the internals of the links — it only sent them messages and worked with their responses.

This is the real power of object-oriented design, and unfortunately it's lost on a lot of folks working in OO. I think it's that they haven't had it explained well. This blog post is off the top of my head, so it continues to be explained poorly, but you get the idea, I hope.

Tail recursion, micromanagement, and naughty bits

2006-03-12T17:18:00.000-08:00

On this fine Sunday afternoon, I've been assembling a LinkedList class for the Mongoose standard library (in the Collections module). It's a pretty standard doubly-linked list — a freshman-level chore that I've done in at least a dozen languages through the years. Recently, good high-level languages have saved me the work by bundling an implementation — but when you create your own language, the giants' shoulders are smaller and less comfortable.

So, let's take the task of getting a particular link within the list. (A Link is an object that knows who its neighbors are, and holds a reference to some value.) Once you can get a link, you can get its value, or navigate around it.

In C, Java, and other procedural languages, you would probably do this with a loop and at least one scratch variable. Loops and scratch variables smell funny to me.

Mongoose calls this method linkAt:, and it's implemented like this:


(-- ... in LinkedList ... --)
@method self linkAt: index [
  (_count = 0) ifTrue: [ ^nil ]. (-- no links to return? --)
  ^_head seekForwardBy: index.
].

It checks if the list contains no elements (as indicated by an instance slot named _count), and returns nil if this is so. Otherwise, it tells the head of the list (a Link named _head) to peek ahead some number of elements and return the neighbor it finds.

Of course, _head, like other Links, only knows its immediate neighbors, so it delegates.


(-- ... in Link ... --)
@method self seekForwardBy: offset [
  (offset = 0) ifTrue: [ ^self ]. (-- that's me! --)
  ^_next seekForwardBy: offset - 1.
].

It checks if the offset is zero, and if so, doesn't do any work at all: it simply returns itself. Otherwise, it pawns the work off on its next neighbor (named, appropriately, _next).

When I wrote this code (with the exception of a couple poor name choices), it just felt good, and I wanted to know why. I think it comes down to one thing:

There is no micromanagement.

In a normal LinkedList implementation (and, I admit, in the first draft of my Mongoose class), the list itself examines each Link, checking who its neighbors are. It controls the navigation; it interrogates every Link, leaving it feeling confused and violated.

This implementation does nothing of the sort: it asks the Link to find out a bit of data. Each Link can then ask its neighbors as appropriate. It comes back to one of the principles espoused by Smalltalk, which I refer to as the Politeness Principle: don't micromanage, or, alternatively, ask objects to do things; don't peek at their naughty bits and decide for them. (On that note, it could be considered the gender equality principle as well.)

As I iteratively refactored LinkedList to make it Polite, I tried to improve politeness while still using a traditional while-loop, thinking it would be more readable for most programmers.

I failed.

Which brings me to my next thought on the matter: tail calls are really the only Polite way to do iteration. There's no one object or routine managing the process; instead, each stage successively asks the next, "Do whatever you think we should with this data," and it can decide whether or not to continue.

Mongoose has optimized tail calls since M1 as its fundamental iteration primitive, but I didn't add them because they were Polite — I added them because they were less conceptually nasty than a goto, which is how most other languages iterate.

On the other hand, Smalltalk, the origin of the Politeness Principle, does not mandate tail-call optimization. In my tests on some current Smalltalks, it doesn't seem common. This blows my mind: it's only proper!

Update: I had misstated the Politeness Principle; I'm looking for a concise yet correct definition now.

Runtime type information and exception handling

2006-03-12T03:22:00.000-08:00

The design of Mongoose includes a number of 'little experiments.'

For example, Mongoose doesn't provide a standard way to determine an object's class. This is on purpose; the class of an object is an implementation detail. You can use the reflection API to find out if you really need to know, but chances are, you don't. Instead, you can check an object for conformance to a certain protocol (a set of messages), and the object may very well change its conformance at runtime.

I've managed to implement most of the Mongoose standard library in this fashion, but I've hit a bit of a roadblock: structured exception handling.

Specifically, it's really nice to be able to define a number of exception handlers, specialized on the type of exception encountered. The traditional way to do this in languages like Java is to specialize on the exception's class.

Sure, I could do this other ways — say, check some 'exception type' parameter — but it feels like a workaround, and requires another layer of namespace to avoid collisions.

This will require some thought.

Mongoose syntax

2006-03-07T21:16:00.000-08:00

As a brief followup to my last post, here's the entire Mongoose language syntax. It's not in a single paragraph for clarity, but it's still quite concise.

Literals

Strings are enclosed in double-quotes. Any double-quotes within the string are escaped with backslash.

Characters are enclosed in single-quotes. A single-quote must be escaped.

Integers can be base 10 (42), base 16 (0x2A), or base 2 (0b101010).

Symbols (used to name messages) begin with a hash mark (#) and can contain any legal message (see below).

Arrays can contain any sequence of expressions, contained in #( ... ).

A normal set of control characters can be used in strings and characters using backslash (\n, \t, \e, etc.), plus Unicode hex escapes (\u002A).

Sending Messages

All messages are sent to a receiver. There are three types of message sends: unary, binary (operator), and keyword.
receiver unaryMessage sends #unaryMessage to receiver.
receiver + argument sends #+ to receiver with an argument (where + can be any sequence of Unicode operator characters)
receiver do: this with: that sends #do:with: to receiver (where this and that are arguments)

Precedence

Unary->Binary->Keyword.
Thus,
4 squared + 2 to: 12 + 8 factorial
is equivalent to
((4 squared) + 2) to: (12 + (8 factorial))
All operators have equal precedence.
Precedence can be overridden using parentheses.

Statements

A statement takes one of three forms: normal, assignment, and return.
A normal statement is simply a message send (which can have message sends as its receiver or arguments, recursively).
An assignment statement consists of a variable, the assignment symbol :=, and a message send, like
foo := bar value.
A return statement consists of the return symbol ^, and a message send, like
^bar value.
Statements are separated by a full stop.

Declaring Variables

Identifiers

Any non-whitespace, non-punctuation Unicode character (plus the underscore) is legal in an identifier. Identifiers must not start with a digit.

Blocks

A block is a set of statements enclosed in square brackets ( [ ... ] ). Blocks may contain any mix of statements and variable declarations. A block can define arguments, which must appear in a declaration at the start of the block; arguments are indicated with colons, eg
[ | :x | x + 2]

Scoping

Scoping is entirely lexical. There are no global variables. Specifically, scopes at this point nest as follows:
class variables -> method arguments -> method locals > block arguments/locals (-> block arguments/locals...)

Reserved Words

Mongoose has three reserved words. self refers to the object whose method is currently executing. super is an alias for self that starts method lookup at the parent class. Self (capitalized, like a class) is a placeholder for the class of self, whatever it may be (in descendants and the like).

self is not a reserved word per se; it can be bound to any identifier within a method, but the compiler currently enforces self. Self (capitalized) is likely to be renamed, due to the potential for confusion with self.

I'm considering a couple additional literal forms, but that's the entire language at the moment.

For writing classes in text format, there's a declarative format that lays out methods and such, but it's extrasyntactic right now.

On Unicode.

2006-03-07T21:05:00.000-08:00

I'm a big fan of Unicode.

Well, not Unicode specifically, but character sets that aren't annoyingly limited. Watching software at my last job fumble around with accented characters — much less Kanji — really clubbed this into my head.

Mongoose, since M1 in 2004, has supported Unicode throughout. I'm continuing this in the M2 implementation.

Mostly, it's for clarity. I consider ≠ to be a lot clearer than != or /= or .ne. or whatever other hacks other languages have used. Same with ≤ and the like. As of tonight, the current compiler and runtime support all this — Object understands the ≠ message and does the right thing, and so on. Unicode handles such characters quite well: there's a reserved block (U+2200 through U+22FF) for operators. Any of these characters are now legal Mongoose operators, from the compiler on up.

This gets a lot of grumbling from the old guard, but I'm not really open to grumbling on such matters. Any Mac user can type all these symbols directly from their keyboards, without having to enter hex codes or some nonsense. I've included message synonyms for the keyboard-impaired (!=, <=, etc.), but they're just that: synonyms for the real message.

I've been thinking, over the past few years, about ALGOL syntax. ALGOL originally defined a 'pretty' syntax — the print syntax, iirc — that used subscripts for array access and the like. This was well outside the capability of machines at the time, of course, so the syntax that lived on in its descendants used A[2] instead of A₂.

I think we're getting to the point where such print syntaxes could be made official. A List might use any subscripted expression as an element accessor; a Number might use a superscripted expression as an exponent. As long as it's easy to enter (which, right now, it's not), I think this could be a win.

But that's because I'm insane.

Mongoose is unlikely to support any such thing, since it's the dreaded "orthogonal syntax feature" I'm avoiding. I like that the entire language syntax can be described in a paragraph, including every possible way a method might be invoked.

Reinventing the wheel!

2006-03-01T21:57:00.000-08:00

I never thought I'd say this, but I kinda wish I were writing in C++.

Seriously. As I write my own hashmap implementation in C, I'm wishing I had access to the STL. Fortunately, this is for the bootstrap loader in M2VM, so it only needs to index the bootstrap classes. There are 14 (see footnote), so if I take a shortcut and make lookups O(n), nothing will catch fire.

M1 avoided this whole issue by hardcoding the bootstrap classes, creating them directly from the C code. This is rather icky and makes development a pain. It's also silly in terms of M2VM, since none of these classes have any distinguished role from the VM's perspective.

Footnote: to start the userspace classloader, written in Mongoose, the M2VM needs the following classes: Object, Class, Nil, Boolean, True, False, SmallInteger, Character, String, Method, Array, ByteArray, MethodContext, and BlockContext. Character is technically optional, but I'm including it to ensure that Strings are fully functional. Object is also technically optional, as Mongoose has no distinguished root class, but it makes the class graph complete.

Unlike most Smalltalk-derived VMs, the Symbol class — which represents unique, interned Strings, for message sends and the like — is not distinguished. It's implemented entirely in userspace using a pretty standard GoF flyweight pattern.

Excellent GC papers

2006-02-26T19:13:00.000-08:00

As some of my past blog entries have implied, I dislike needlessly long, convaluted CS papers.

Now, my experience in formal writing is primarily in psychology, and I know that APA style dictates a certain wordiness — extensive citations of prior related work, etc. At ASU, at least, APA papers were actually prohibited from using quotations, so any referenced material had to be restated or paraphrased. So, I imagine some of the wordiness in CS papers is purely stylistic.

However, every so often I find really to-the-point papers.

My favorite example is Hölzle's 1993 paper on write barriers in Self. I came across this a couple years ago, when I was studying Self. It explains its purpose, summarizes prior work (including concise code snippets), and presents its results in just 6 pages — and the idea it's presenting is non-trivial. Marvelous. (Dr. Hölzle is not in my line of direct supervisors at work, either, so this isn't brown-nosing.)

I'm currently reading a 2001 paper by Fridtjof Siebert discussing root scanning in garbage collectors. It's also delightfully punchy, at 15 pages. I came across it during my research today, and it made me both happy and sad.

Happy, because it lays out (rather more formally) some of the techniques I'm using in M2VM's collector. (Because of M2VM's Smalltalk origins, all trace roots are in heap at well-defined points during execution.)

Sad, because I thought I was all cool for coming up with this idea. According to the paper, I'm at $StateOfTheArt - 4 years. :-)

The good news: Siebert's scheme is tailored to uniprocessor systems, where having a single active thread is acceptable — whereas my variation is explicitly designed for multiprocessor machines (like mine). I'm sure this leap has already been made in the literature, but it's nice to know I'm not entirely insane.

For any interested parties: my approach has threads check a global condition variable at certain synchronization points. If any thread would like a collection to occur, it sets the variable and waits for other threads to reach a synchronization point; each thread flushes registers to heap and decrements a countdown semaphore when they reach synchronize. Once all threads have synchronized, the collector traces the roots and marks reachable objects, and all threads resume while the collection completes.

Because each thread's context information is accessible through a reference in global scope (actually from a pthread TLS slot), finding and tracing the roots is O(n) for n threads. (The full trace phase is still linear for the number of reachable objects, as usual.)

I'm looking at a couple enhancements for parallel tracing and scavenging, and trying to find a good way to apply this to full collections (currently, it's limited to minor, new-gen collections). We'll see.

Developer: 1; Garbage Collector: 0

2006-02-26T02:23:00.000-08:00

Garbage collector bugs are some of the hardest I've ever debugged (with the possible exception of massive concurrency or distributed systems). "Y'know that memory address you were just PEEKing at? Yeah, it moved. See if you can find it now, sucker."

However, I've beaten this one, and the M2VM garbage collector is working again. Found a number of oversights in my implementation; I knew the initial mark-compact collector was a stopgap measure, and boy, did I write it like a stopgap measure. :-)

I've also gained a real appreciation for gdb. At some point in the last few years, it's learned to reload single functions from a modified binary on the fly, as well as dynamically reloading and relinking shared libraries. I can switch windows, recompile my GC, rebind the entry point, and resume execution. Pretty sweet. (These might be Apple-specific enhancements, not sure.)

So, the GC is creeping right along — emphasis on the creeping. Like any naïve mark-compact collector, it causes nasty pauses — as much as 1s on a 40MB heap. Hand it a heavily fragmented 1GB heap, and not even my 2.5GHz G5 can make the experience pleasant.

I've found some creative ways to optimize it, but it raises the question of how much to tune throwaway code.

Update: corrected "mark-sweep" to say "mark-compact." I had actually forgotten that non-moving tracing collectors existed.

Update 2: in answer to my final question, I modified the mark-compact collector to use a simple generational strategy. Work required: 2 lines of code. Speedup: 100x.

Night and Day

2006-02-25T13:54:00.000-08:00

The Day Programmer vs. The Night Programmer

There are those who program to make money, and there are those who program because it captivates them. This is a point I've come across many times through the years, but this fellow elucidates it particularly well.

My interviewing style, for example, is specifically designed to weed out the former type. (Which, I suspect, is why I didn't do more interviews at Choice. They were frightened and confused by the latter type.)

Not sure which I am. *goes back to spending Saturday tuning his virtual machine*

IT'S ALIIIIIVE!

2006-02-22T22:09:00.000-08:00

Since Saturday, I've been hacking on M2VM, my next-generation Mongoose VM. It uses the VM-generation utility I described in my last post.

As of tonight, it works. I have:

1. Designed a class-file format, similar to Java's but better suited. (This is a stopgap measure; M2VM will load classes a module-at-a-time using a yet-to-be-defined format based on the class-file format.)
2. Written a set of utilities (in Java) for building up M2VM code, in preparation for a compiler. (At this point, it generates class files from a tree-based IR, so the compiler layer will be very thin and probably entirely ANTLR.)
3. Written the VM generator (in Ruby) that transforms 151 lines of very manageable domain-specific code into 334 lines of VM inner loop.
4. Written a rudimentary memory manager and garbage collector (in C) with the fundamentals of my eventual zone-based scheme.
5. Written a stopgap class loader (in C) that works with the object memory API to build classes in RAM.
6. Written a test framework that creates objects and sends messages to them.

So, having fed it the equivalent (in pseudocode) of:


sample() {
   return self.
}

...I now get a correct return value!

Nested and recursive calls also work.

I'm using my generator in switched mode, so I need to kick it into direct-threading and test that. (It works for some limited test input, and most of the code is boilerplate in the Ruby.) I also need to test some fundamentals — argument passing comes to mind — and flesh out some error handling, but...

... it works!

Virtual machine generators are a fun way to spend Saturday night!

2006-02-19T03:04:00.000-08:00

Last night, I started work on a new version of the Mongoose VM. The previous implementation (M1) was a testbed for a bunch of competing ideas, many of questionable value — so the code was pretty hairy.

The new implementation (M2) uses a simplified bytecode, has a Java-like classfile format for separate compilation (M1 was image-based), and is starting life as a coalescing threaded interpreter.

Once I'd made it a bit into the implementation, I realized how much boilerplate code was involved in writing a VM. So, I assembled some tools (in Ruby, of all languages) to help me out. I now have a domain-specific language for describing VMs, which includes
- Describing the logical register set;
- Describing bytecode functions and formats;
- Providing C implementations for operations;
- Describing the calling conventions for invoking the VM itself from C code.

Short example:


// Bring in some C headers for the operation bodies
include <stdio.h>;
include <stdint.h>;

// Declare us a register
register uint32_t $accumulator;

// Bytecode 0x00 with a single 8-bit argument
op increment(00, amount:8) {
  $accumulator += amount;
}

// Bytecode 0x01 with no arguments
op print(01) {
  printf("%lu\n", $accumulator);
}

// Current implementations can stop execution with return
op halt(FF) {
  return;
}

The initial tools generated a dead-simple switched VM from my bytecode descriptions, as well as some header files for manipulating the instruction set.

Newer revisions generate direct-threaded code, including functions to translate the bytecode format to threaded form on load. I'm working on very simple stream-rewrite capabilities, for use in instruction coalescing (combining several sequential ops into one) and specialization (replacing an op with a variant depending on context).

A few examples of each:

Self sends: by coalescing send-to-self sequences into a virtual self-send instruction, we can take advantage of the lack of polymorphism. In particular, self-send has an inline parameter that points to the body of the method to call — reducing the method dispatch process to a GOTO.
Tail sends: by coalescing a send-return sequence into a special tail-send instruction — unavailable in the raw bytecode — we can perform tailcall elimination.
Tail recursion: by further specializing the instruction when (a) the receiver is self and (b) the message is the same that invoked the current method, we can perform tail recursion elimination using a particularly lightweight sequence. (M1 optimized both tail sends and tail recursion through dedicated bytecodes.)
Hot sends: by specializing sends into a virtual cached-send instruction — which has a 3-deep polymorphic inline cache — we can drastically reduce method lookups for the general case.

You've probably noticed that those examples all involve message sends, and there's a reason for that: Smalltalk-style languages spend most of their time sending messages around, and it tends to be a slow process. It's low-hanging fruit for optimization.

One more:
Opening closures (ha ha): the relatively expensive block instruction, which creates a literal Block, can be specialized to a contained-block instruction. This requires that the block be entirely self-contained: no references to the enclosing context's variables, and no non-local return instructions. In this case, the enclosing activation records need not be reified onto the heap.

Some of these virtual-instruction transformations are working now; I hope to have the rest in place shortly.

(Incidentally, the entire system is under 1000 lines of Ruby, plus a 134-line description of the virtual machine.)

Reinventing Forth

2006-02-14T22:36:00.000-08:00

There's a saying to the effect that any sufficiently complex program or runtime will wind up reimplementing most of Common Lisp. (I mostly hear that from Lispers, so add salt to taste.)

Well, you can imagine how surprised I was to see someone reinventing Forth.

In an indirect threaded interpreter, each op — let's call them words, for the hell of it — is represented by an index into some table holding an address to the code. (Or, in Forth, an address of a word definition, which contains an address of the code to run.)

In a direct-threaded interpreter, each words is represented by the address of the code itself, so the interpreter — which we'll call NEXT — is basically a repeated indirect jump.

At least one Forth saw the obvious next step in performance: replace each reference to a compiled word with a CALL instruction to its address, instead of the address. (This isn't a huge leap for Forth. Direct-threaded Forths usually have a CALL instruction in the word definition's code slot anyway.) On the machine in question (I don't remember which), they used a within-segment jump instruction, and were able to squeeze it the same space that would have been required for the direct-threaded address.

Evidently, this approach has been rediscovered, under the name "context threading."

Context threading does bring a few significant advancements to the table: it generates the calls at runtime from the original bytecode, and inlines basic flow control among all those CALL instructions. This isn't possible in Forth without a lot of trickery, for the same reason it's difficult in Smalltalk: there are no built-in flow control mechanisms. However, high-performance subroutine-threaded Forths will inline short, common words — and you don't get much shorter or more common than IF/ELSE/THEN.

Speaking of which, context threading seems to rely on the original bytecode to resolve flow control operations, where Forth would simply modify the return address.

(Incidentally: yes, this is one of the two tricks I used in the Mongoose interpreter to improve indirect branch prediction. Forth has a lot of good ideas to steal.)

It seems the Mongoose interpreter wasn't half bad.

2006-02-14T20:21:00.000-08:00

I worked on the interpreter for my Smalltalk-like language, Mongoose, through 2004 and the first bit of 2005. I eventually abandoned it, mostly because work became too stressful for me to sustain a major side project, but also because I had always looked at the interpreter as throwaway code on the way to JIT compilation.

(I actually had basic JIT working on PowerPC, using a dastardly hack involving memcpy and GCC's address-of-label operator. Never got it working on x86, where all non-academic languages must run, and I didn't know enough x86 at the time to debug it.)

However, I've come 'round on since then, and have realized three things.
1. There's a place in the world for interpreted languages. Even the large enterprise systems, which I was explicitly targetting with Mongoose, aren't CPU-bound in most cases, and interpreters can often run in a fraction of the RAM of native code — look at Forth.
2. Even if I had a working runtime compiler, putting the JIT in "JIT compiler" requires a good interpreter. You don't want to compile all your code, only the code that needs it — the vast majority of the system will probably remain interpreted. (My Mongoose "JIT" compiled at class load time, which is less than optimal.)
3. My interpreter wasn't half bad.

More on that last point, because it surprised the hell out of me.

Lacking any formal CS education, I tend to come across concepts in the field in a different order than most. For example, SSA form is intuitively obvious to me, and was how I implemented my prototype type-inference system for Mongoose — so I was pretty confused when I finally bought a book on compilers a few months ago. All the inital techniques they were describing seemed unnecessarily complex, dealing with changing values for names and the like. (They were building up to SSA, which they covered in chapter 9.) On the other hand, some of the really fundamental stuff — like basic blocks and optimizing out common cases on the control-flow graph — I had approximated, but hadn't nailed in the way they described.

So, I grade my performance by tracking down interesting papers online, and figuring out how far behind them I am. I do okay in some areas (Bracha and Unger's 2004 paper on OO metamodels pretty much describes Mongoose) and really poorly in others — as is expected, for us liberal arts types.

In the past week or so I've been collecting papers on interpreter design, and in some areas I seem to be close to the state-of-the-art.
- The technique I call instruction coalescing — converting common sequences of VM ops into larger meta-ops that can be more easily optimized — seems to be called superinstructions and specialization in the literature. (Strangely, I haven't found anyone using my technique for reducing indirect branch misprediction — but I'm sure somebody beat me to it.)
- There are a few interpreters floating around that use my dastardly hack for compilation; most call it catenation, which makes sense: I'm using GCC's optimizer at build time, and simply stringing sections of its output together.
- The techniques I used for stack-allocating objects when context permits will be in Java 6. (This may have been around for years, though.)

There's a great report called Optimizations for a Java Interpreter Using Instruction Set Enhancement that covers the techniques I've been using in Mongoose, so I'm glad I'm not totally off-base. They don't use my technique for optimizing indirect branch prediction, which may very well mean it sucks — I haven't done enough profiling.

I'm working on the interpreter again, having found some neat techniques I hadn't derived. We'll see where it goes; the old Mongoose interpreter beat the pants off Ruby 1.8 in most benchmarks, but my error handling wasn't nearly as well-developed, and I didn't test any of the higher-performance Ruby VMs that are available.

(...yes, this is what I do on Valentine's Day.)

Variable-arity parameterized types

2006-02-12T14:00:00.000-08:00

Language geek that I am, I've been reading up on all sorts of type systems in the past few years.

Mostly, I've been interested in ways to statically typecheck dynamic OO languages, like Self — but I've also been interested in how different OO languages implement parameterized types.

I've noticed a common problem: most languages cannot even describe the types of their own methods. (Strongtalk makes an exception for typing Smalltalk-style blocks, but it's not a general solution.)

Before tackling methods, let's take a reasonably common case. We want a class called Tuple, instances of which contain a fixed number of objects of different, specific, types. So, the base Tuple class could be specialized to represent key-value pairs in a map, or (*gag*) multiple return values from a function. (The astute reader sees another obvious use, but we'll get to that shortly.)

How could we define this Tuple in a generic way? In C++, Java, Eiffel, and most other languages (possibly including Strongtalk, though I'd love to be proven wrong), you can't. The closest you can come is to define a different Tuple class for each length — say, Tuple1<A>, Tuple2<A, B>, Tuple3<A, B, C>, etc. I don't think I'm the only one who looks at this solution and says, "Ewww."

Having learned and rejected Python shortly before I started work on Mongoose, tuples struck me as a useful abstraction, and I wanted Mongoose's type system to describe them. Here's a pseudocode Tuple in pseudo-Mongoose. (Brief syntax note: a generic class is applied to parameters as Class(Parameters), just as a function is applied as function(parameters).)


class Tuple(T+) {
  method get(index : Integer) : T[index] { ... }
  method set(index : Integer, element : T[index]) { ... }
  method positionType(index : Integer) : Class(T[index]) { T[index] }
}

Tuple's formal parameter T+ indicates that the class can be specialized on 1..n classes. The value of T is available as an ordered list, both for typechecking at development time, and for access by specialized subclasses at runtime (as shown in the body of positionType). (Implementation of a variable number of slots to store the elements is hairier, and I've omitted it.)

I went to all this nasty work so that Mongoose could statically type its closures and methods. We wind up with something like the following for the Block object (equivalent to a lambda function with environment closure):


class Block(A*, R) {
  method argumentType(position : Integer) : Class(A[position]) { A[position] }
  method returnType() : Class(R) { R }
  method invoke(parameters : A) : R { ... }
}

The formal parameter A* specifies zero or more classes. These variable-arity parameters are bound to Tuples at runtime (and handled through trickery at compile time). For example, for the type application Block(Integer, Integer, String), A within an instance would have the type Tuple(Integer, Integer).

So, say you have an anonymous block like the following, which takes an Integer and tells you if it's bigger than some constant.


{ x : Integer | x > 42 }

Blocks like this are frequently used in Mongoose and Smalltalk to filter collections and the like. I've typed the block's parameter explicitly here; normally, this can be inferred from context. Integer's published ~~contract~~ — sorry, Mr. Meyer — specification for > says it returns a Boolean, so the return type of the block can be inferred.

So, the type of this expression is Block(Integer, Boolean). If anyone were to inspect its class, they'd find that the return type is Boolean and the parameter list is «Integer» (using the Tuple literal syntax that Americans can't type).

The real key here is that this isn't a special feature for standard library classes like Block — this is a generic mechanism (pun intended) applicable to user classes.

Now, after I designed this section of Mongoose, I learned Dylan. Dylan's ludicrously expressive type system — particularly the notion of restricted types, like "Integers between 2 and 12" — really impressed me. I'm looking at ways to integrate this flexibility into Mongoose's parameterized types, preferably in an elegant fashion. (Fortunately, like C++, the parameter bindings are not necessarily restricted to classes, and are available at runtime.)

Edit in response to comments: yes, restricted types would help me constrain the type-array references in that Mongoose code up there at compile time. This is why I want them (among many other reasons).

Commutative arguments

2006-02-11T23:27:00.000-08:00

Had a sick thought today.

In considering the binary operator problem (mentioned in my post on multimethods a few days back), I thought, "What if certain functions could define themselves as order-insensitive?"

The canonical example seems to be a function for testing if two objects are equal, which we'll call equals(a, b). Equality, in my mind, is commutative, like addition: equals(a, b) should always have the same result as equals(b, a). (Thus, equals(equals(a, b), equals(b, a)).)

In a lot of situations, you don't want objects of two different classes to ever be equal. I would argue that numeric types are an exception: if I have the number 5 represented as a base-2 integer, and as an arbitrary-precision decimal type, they can be interconverted without a loss of data, and thus should be equal.

Now, people wanting to compare Integers and Decimals might write the comparison either way — or even not know which value is which type when the comparison is written. Traditionally, if you wanted to define variants of equals to cover this case, you'd have to write two functions — if your language even allows it:
equals(Integer, Decimal)
equals(Decimal, Integer)

What if, instead, the equals function would reorder its arguments as necessary? (Assume the runtime order of evaluation is fixed, in case you have side effects in your argument expressions.) Only one of these two declarations would be necessary — and, in fact, declaring both would be an error.

Addition and any other commutative operation would also benefit.

Now, of course, this doesn't solve the binary-operator problem for non-commutative operations like division, but it might be food for thought.

More on multimethods

2006-02-11T23:06:00.000-08:00

Ran across Millstein and Chamber's 2002 paper, Modular Statically Typed Multimethods. Based on Chambers' work on Cecil, it presents a much cleaner, logically-consistent way of doing multimethods.

As a result, I am far less suspicious of them than I was a few days ago.

<aside>
Computer science papers have an amazing knack for being opaque. Perhaps that's why good programming books are so prized. The entire meat of this paper could have been covered in a couple pages of source examples and discussion, with an appendix for the formal definitions — as is, it's 47 pages long.

(Literally. I use "forty-seven" like the Hebrew scriptures use 40, as an unspecified but ludicrous length, like "enter your forty-seven digit extension after the beep." This paper, however, is actually 47 pages long.)

But of course, a nicely tech-written summary wouldn't have made ECOOP.

Anyway.
</aside>

Their system, System E, still strikes me as iffy in the face of runtime-loaded code. Java's ability to load and unload code on the fly is the source of a lot of its power — it's the feature that allows application servers and really-well-integrated IDEs — and I intend to preserve it in Mongoose.

However, I think System E can be easily adapted for runtime loading. It does some link-time typechecking to verify consistency, and if linking happens to occur during execution, no biggie.

It still bothers me that calling a function foo might get me two different code paths before and after loading a module, depending on the (surprise) types of the arguments. This is mostly a security issue for me: if a module is able to stub-out some hasPrivilegedAccess function on load, all hell breaks loose.

System E defines inter-module restrictions that could be used to control some of this; the rest could be left to the language security model, perhaps marking some functions as non-overrideable (Java's final).

Alternatively, if the language can partition loaded code off in its own little sandbox (a la Java's pending Partition feature), perhaps function overloads could be prevented at the partition level.

I'm tinkering on a design for Mongoose that leverages these ideas. More to come.

Prototypes and Classes

2006-02-07T23:39:00.000-08:00

Class- and Prototype-based OO languages are equivalent. I don't just mean equivalent like any two Turing-complete systems — they're equivalent through a simple transformation, like tail recursion and iteration.

Prototype-based languages are distinguished by the fact that objects can have their own unique behavior and structure. You can add a method or slot to an individual object instance, rather than having to modify some class that defined it. (The benefits in UI programming are obvious — hint: no more action listeners, just redefine a method on that particular button.)

Under the hood, however, prototype-based runtimes usually have behavior objects that back the object instances. An instance will contain some number of data slots, and a reference to its behavior, where the actual methods are stored, along with references to its delegates (similar to parent-types in class-based languages). Multiple instances can share a single behavior object, which dramatically reduces memory requirements.

Now, the methods are stored on the behavior, which may be shared by many instances, but you can still add a method to a particular instance — because the behavior is copy-on-write. When you add a slot or a method to an instance with a shared behavior, it creates a new behavior containing your modification, which delegates back to (read: inherits from) the original. The modified instance is switched to use the new behavior, and voila.

This preserves the prototype semantics of the language, while reducing memory footprint and improving cache performance.

It also looks a lot like a class-based object system — and, in fact, a sufficiently flexible class-based object system can achieve exactly the same behavior.

Translating from the prototype world to the class world, adding a method or slot to an instance creates a new class (behavior) containing the new method/slot, inheriting from (delegating to) the original class, and changes the instance's class to the new subtype.

Very few class-based object systems are this flexible — Java, for example, cannot change the class of an object on the fly. (In fact, only Smalltalk and Ruby spring to mind, though I'm sure someone will pipe up and insist it can be done in CLOS.) I'd like to see this sort of thing become widely available; I'm not a fan of prototype-based languages in general, but this would be a very powerful feature in a class-based language.

Multi-method dispatch, operators, and typecasting

2006-02-07T23:14:00.000-08:00

I am suspicious of multi-method dispatch.

In a language like Smalltalk, when you send a message like

foo process: bar with: baz

...you know that foo will respond to the message, generally executing some method identified with process:with:. bar and baz have no direct say.

In a language with multi-method dispatch, bar and baz — the arguments to the message — can also provide methods for handling the message. Generally, the most specific one is chosen at runtime: if foo has a method for dealing with arguments of any two types, but baz offers one that accepts the precise runtime types of all three objects, it is not foo's code which will execute, but baz's.

As I said, I'm suspicious of this.

I like the ease of reasoning that single-dispatch gives me, knowing that a given object's code will execute when I call a method. Particularly if the code for baz was loaded at runtime, the method may be effectively hijacked with a result I didn't intend.

However, I can think of two cases that are dramatically more elegant with MMD: operators, and casting (which is effectively an operator).

Smalltalk lets you name a method '+', to be called in the normal infix fashion, a + b. In that fragment, it is of course a's + method that will execute.

But let's say you define a new type to represent, say, money — we'll name it Money. You teach it to add integers, floats, or other numbers using a + method. This is all well and good, so long as you write it like this:

myMoneyAmount + someInteger

Great. The + method you defined for all objects of type Money runs, adds the integer, returns a Money. All is well.

However, if you write it

someInteger + myMoneyAmount

(which is, thanks to the commutative property, mathematically equivalent), what happens? The + method on the built-in class Integer fires up, and it may not know how to act on your Money object — and almost certainly will not return a new Money in response!

The traditional Smalltalk solution to this is, in my opinion, a hack. It's called double-dispatch. The code in Integer would notice that the other addend isn't a known type, so it passes control into the addend using some other method. Effectively, it converts that fragment into something like

myMoneyAmount addedWithInteger: someInteger

(Why doesn't it flip it around and call the + method on the argument? Because that could quickly become an infinite loop of back-and-forth message sends. addedWithInteger:, or whatever it's called, is defined as not performing double-dispatch.)

That's a simple solution for the built-in types, but if you've got two third-party types you want to add, each must sport an addedWithWhatever: method for the other — when the third-party types are probably not aware of one anothers' existence. The situation can spiral out of control.

In Smalltalk, specifically, this problem is mitigated by the fact that you can add methods to other peoples' classes once they're loaded into the system. You can construct this web of adding methods to ensure your types play nice.

This is not, to me, a solution, but a workaround.

You'll run into similar problems if you try to implement a generic cast method. Smalltalks frequently have asString or asArray methods to convert objects to some other type. If you wanted a generic method, like

foo as: Bar

you'd wind up having to resort to double-dispatch again. Your Money class can easily handle "as: Integer", but having Integer handle "as: Money" is more difficult.

Multi-method dispatch eliminates this problem entirely, by allowing your Money class to introduce an as: method that is used when a Money object is the argument, not just the receiver. (Yes, pedants, in MMD there is no receiver per se.)

This is one situation where I would like the dispatch of the method to be determined at runtime.

C++ solves it a little differently, by having both member functions for operators, and free-floating functions that overload operator+ depending on the argument types, but the result is the same as MMD.

So, for this sort of problem, MMD is appealing. I've been thinking about this for a while, and there's an obvious place in the Mongoose language to hook MMD if necessary (namely, by providing implementations directly for the Class-independent Method Contract Identifier — effectively, C++'s approach).

I suspect there's a compromise, or perhaps an alternative technique.

Update: no updates.

2006-02-05T20:33:00.000-08:00

In case anyone's actually reading this, yes, I will post stuff soon.

Since I created this blog, I haven't been able to discuss most of what I'm doing. I'm starting to get settled, so I'll be doing more personal hacking soon.

Currently, I'm playing with Facelets, and I'm awfully tempted to write up a JSF tutorial that eschews JSP. So much easier!

Making those 'Universal Binaries' a bit more universal

2006-01-21T11:17:00.000-08:00

Some of you may be familiar with Cesta, my network analyzer. I'm starting to get settled in California, so I'm beginning to hack on it again.

Like any Mac developer in January of 2006, I'm interested in having my app be a Universal Binary, so it will run on both PowerPC and x86. Apple provides pretty good support for this. However, there's one minor gap:

Tiger (10.4) uses GCC 4.0. Panther (10.3.x) uses GCC 3.3. There are minor incompatibilities and feature gaps between these — for example, on Tiger, I can use an accelerated dispatch routine for Objective-C message sends. The C++ ABI is also subtly different, and tends to break some routine language features.

Building a Universal Binary for 10.3 PPC and 10.4 x86 is straightforward, but there's no Apple-supported way to build a three-way binary: 10.3 PPC, 10.4 PPC, 10.4 x86. Sure, I could use weak linking to use the 10.4 API from a 10.3 binary — but that doesn't get me the compiler and ABI changes I want from GCC 4.0, which will only run on 10.4. (With some of the C++ changes, the binary won't even get past dyld.)

Now, I've been developing for Unix a lot longer than Mac OS X has been around, and Unix has this marvelous family of system calls, exec(3). They allow you to replace your current process image with another — you keep the same process, with the same PID and RUID, but the running program changes. This is used all over Unix, particularly in the time-honored fork/exec sequence. Of course, these are available in OS X.

"So I realize," I realized, "that I could use this to effectively change ABIs on the fly."

Here's how it works.
The official binary (Contents/MacOS/$APPNAME) is a Mach-O fat^H^H^HUniversal binary, containing code for ppc (compiled against 10.3.9 using gcc 3.3) and x86 (compiled against 10.4 using gcc 4.0.1).

However, using an auxiliary target, I also include a non-fat copy, containing only ppc code, compiled using gcc 4.0.1 against the 10.4 SDK.

Normal developers would, at this point, have their users download one version or the other — and if I wanted my app to feel like a crappy Windows package, I would do just that.

Instead, I've dropped the following code fragment into the main function. It ain't pretty, because it's a first crack that I wrote some fifteen minutes ago, but it works.

It
1. Checks for GCC 3.3. This means it's the PowerPC 3.3 binary.
2. Checks for Tiger.
3. Tries to construct a path to the Tiger-optimized PPC binary.
4. execs it, thereby replacing the current process.
5. If anything goes wrong, the PPC 3.3 binary is used.


int main(int argc, char *argv[])
{
#if __GNUC__ == 3
  // We're the gcc3.3 PPC binary.  Check for Tiger.
  // If any error occurs, simply fall back to running this version.
  SInt32 MacVersion;
  if(Gestalt(gestaltSystemVersion, &MacVersion) == noErr) {
    if(MacVersion >= 0x1040) {
      
      // On 10.4 or above.  Let's do nasty things to the runtime.
      char *lastSlash = strrchr(argv[0], '/');
      if(lastSlash != NULL) {
        // Build a path to the Tiger binary.
        char binaryPath[lastSlash - argv[0] + 1 + 13 + 1];
        strncpy(binaryPath, argv[0], lastSlash - argv[0] + 1);
        strncpy(binaryPath + (lastSlash - argv[0]) + 1, "TigerExecTest", 14);
        fprintf(stderr, "%s\n", binaryPath);
        char *execArgs[argc + 1];
        memcpy(execArgs, argv, argc * sizeof(char *)); 
        execArgs[argc] = 0;
        execv(binaryPath, execArgs);

        // Oh crap.  I guess we'll stick with the 3.3 version.
        perror("Exec failed");  
      }                 

    }           
  }     
#endif
  return NSApplicationMain(argc,  (const char **) argv);
}

Error handling could be better, but there you have it.