Now a brief word in praise of my programming language implementation of choice. I decided three or four days ago that if I'm serious about the whole studying-language-interoperability thing, which it appears I am, I really ought to know something about actual language interoperability systems. So I picked for myself a modest little project: implement a standard CLR-style binary heap in C, where heap elements were abstract pointers and when you create a heap you've also got to pass in a less-than function with respect to which the heap will remain balanced. The heap algorithms are all dead simple, so I figured that even though there's a little rust on my C programming skills it wouldn't be too bad.

I did the code yesterday and was able to write make-heap, insert and extract-min functions pretty quickly. There was one maddening oddity, though: in my test harness, if I printed out each number as I inserted it, everything went along fine and I could insert as many numbers as I wanted to and then suck them all out, no problem. If I didn't print the numbers as I inserted them, things went all crazy and I'd end up with nonsense in my heap. Now, I haven't forgotten enough C to not realize that this was a classic memory problem, but the particular manifestation was driving me crazy: I couldn't watch what was happening at all because whenever I put a printf statement anywhere interesting the problem disappeared. I stepped through the algorithm in my head over and over again, and couldn't find anything wrong in any of the three algorithms I'd implemented even after extensive staring. So I gave up.

But it ate at me, and so today I came back to the problem. I didn't even care about interoperability anymore, I just wanted to figure out where this bug could be coming from. Long story short, after about three hours I discovered it: suffice it to say, despite their amazing visual similarity sizeof(void) and sizeof(void *) are not the same thing, and if you malloc the first and mean to malloc the second you may end up getting surprised.

That fixed, the library snapped into shape and after a rather-longer-than-it-should've-been digression on how to build dynamic libraries in OS X (gcc -dynamic -g -c yourfile.c && libtool -dynamic -o libyourfile.dylib yourfile.o, in case you're curious), I was ready to try bringing the library into DrScheme and calling it from Scheme code. Ten minutes later:

> (define h (heap 20 <))
> (insert h 10)
> (insert h 9)
> (insert h 8)
> (insert h 7)
> (extract-min h)
7
> (extract-min h)
8
> (extract-min h)
9
> (extract-min h)
10
>

This even though I'd only ever used the PLT foreign interface once before, and never with higher-order functions or C functions that made callbacks or any of that stuff. I was very impressed.