Praise, Curse, and Recurse

MacPorts, Snow Leopard, and GHC == Sadness

2009-09-09T23:44:00.003-04:00

Wow, it has been a long time since I've had anything to say on this particular blog. Another baby (we're at four now) will do that to a guy, I guess.

I was going to do a little exploratory coding tonight, and so installed XCode, then MacPorts, then tried to install GHC. MacPorts tells me (after installing most of the components) that "ghc is not yet supported on Mac OS X 10.6.x (SnowLeopard)."

I know it hasn't been out very long, but the APIs have supposedly been frozen since May, so I'm a bit surprised.

I guess I'll see if the package installer works, but I was hoping to go a little more cutting-edge.

Reading Real World Haskell

2008-11-17T17:31:00.001-05:00

I've sort of let this blog lie fallow while my attention was distracted by having a new baby, playing shiny guitars, twittering, making podcasts and YouTube videos, and other distracting things.

I am excited to see that Real World Haskell has gone to press, and so I am reading the electronic edition while waiting for the print edition to arrive. I had read some of the draft chapters, but it has changed considerably!

For those interested, I recorded audio during the birth of my newest child, Joshua Gregory Potts, born just under three weeks ago. I am turning this into a series of podcasts along with the tweets I sent out during the birth. I won't spam you with a lot of links, but here is a link to The Potts House General Purpose Podcast. Over on Geek Like Me Too you can find baby pictures, some serious and some silly.

I am learning to live with sleep deprivation again! So, these days, Twitter seems like a more appropriate medium for the short attention span which is pretty much all I'm capable of at the moment. If you are so inclined, you can find me on twitter as "paulrpotts."

Summer's Over

2008-09-02T13:39:00.002-04:00

My son Isaac started high school today, so it must be true.

Here is my first YouTube video: the Potts family vacation in Grand Marais, Michigan and other points north this past week, set to Jonathan Coulton's Creative Commons-licensed song "Summer's Over."

Cross-Blog Information and Introductions

2008-07-22T11:26:00.000-04:00

In order to try to avoid boring people with material they aren't interested in, I have divided my writing up into five separate blogs. The downside to this is that I have a tendency to wander from one area of interest to another over the course of a typical year, so it may look like I've dropped off the face of the earth. In case anyone is interested in following what is going on in one of my other blogs, I thought it might be useful to post this road map once in a while.

Geek Like Me Too is my general-purpose personal blog. The most recent postings are about a recent Jonathan Coulton concert in Pontiac that I attended and recorded. I have provided recordings of the show as a set of MP3 files, of interest to geeks who like music.

Geek Like Me is its predecessor, done in Blosxom, now still up only for archival purposes.

Geek Versus Guitar is about guitar playing. Recently I've recorded a few Jonathan Coulton songs myself. It will also be about learning to produce songs with my home studio.

Praise, Curse, and Recurse is about programming topics, mostly Haskell, Python, and Scheme. My free time has been devoted to other things but I will no doubt be back around to programming before too long.

The Marcella Armstrong Memorial Collection is about my family history, and the big task of scanning, restoring, preserving, and archiving family photos and documents. Of interest to any family members, but also of possible interest to people doing their own similar projects.

Tales from the Potts House: William Hope Hodgson contains information about the "Hodgecast" podcast available on iTunes, in which I record classic William Hope Hodgson novels and stories. I have more podcasts planned in both this series and possibly others in the near future.

Anyway, there it is... please join me on any of these blogs that might catch your interest. I always have far too many projects going at once!

Snakes on the Wing

2008-04-03T21:58:00.001-04:00

So far, Wing IDE gets the nod as the best Python editor I've tried. I had a very productive day with Wing IDE on Windows, and it worked great, with no crashes, and very nice debugging functions.

WIng IDE for MacOS X is an XWindows app. This makes it very slightly un-Mac-like, but it makes up for it by having some nice GUI themes. I haven't yet exercised the Mac version very hard, but it seems quite nice so far.

I'm grateful for all the recommendations!

Beware the IDEs of April

2008-04-03T01:15:00.001-04:00

My post on Python IDEs got a huge number of comments, including recommendations for Eclipse with plug-ins, Visual Studio with plug-ins, and Emacs.

One of the two highest-recommended options was Komodo IDE. I've had some success with a trial of Komodo IDE on Windows, with only one major crash, which I was unable to reproduce. However, the same code brought over to run under the same version of Komodo for MacOS X produces a strange syntax error. I've filed this as bug 76114. It seems quite strange, especially given that the same code runs fine using the command-line Python under MacOS X. Despite this issue it seems overall to be a pretty usable environment.

I've also had several recommendations for WingIDE, which I will check out as well. Thanks to everyone who responded!

The program mostly reads an XML file, does a little validating and destructuring of the nodes into dictionaries, and then generates some C++ using a template. About as "real-world" a program as they come. Even as boiled-down as I can make it, it still seems awfully wordy and full of functions whose behavior is extremely dependent on my intermediate data representation. In Common Lisp, I'd be trying to use s-expressions instead of XML for the starting data, and using destructuring macros to turn the input data into data structures. With NewtonScript, I might try to find a way to do it by writing accessors that used path expressions. Is there a better way in Python? How about Haskell? I'll have to give it some thought.

The Abysmal State of Python IDEs

2008-04-01T00:10:00.000-04:00

In the past few weeks I've sampled numerous Python IDEs for Mac OS X. Without exception, every one of them has major problems.

Without exception, they have crude GUIs, with drawing problems.

Without exception, every one of them has had either lacked completely, or had broken, the kind of source-level debugging that has been commonplace since the mid-1980s, such as visually setting breakpoints.

Most of them have the look of personal hobby projects, where the developer put in a little effort, and then abandoned the project. Menu items do nothing, help commands say "no help available." Documentation? Don't make me laugh, it hurts too much.

Even the allegedly polished products work really erratically. On Windows, I have to restart the ActiveState environment every time I want to re-run my program after making a change and saving the program, because it doesn't seem to ever realize that the file has been updated. Except sometimes it starts detecting changes for a while. It won't save my window layout. Except once in a while it does. However, breakpoints do work for me, and I'm able to do some debugging. But ActiveState for Mac seems to install completely different tools than ActiveState for Windows: no IDE whatsoever. Huh?

I'm having to do most of my debugging with print statements. I'm horrified. There is some kind of primitive debugger, but it requires modifying my source code, and that just seems stupid. The program I'm trying to debug is not unusual nor particularly complex; it just works over some XML and transforms some files.

My download log for tonight reads like a litany of failure: drpython, SPE, ScrIDE, and ActivePython.

DrPython: no interactive debugging. SPE: allegedly some kind of debugger, but it doesn't seem to work. ScrIDE: weird issue handling basic import statements that work on the other IDEs and with the command-line python without any trouble; other users are reporting this on the message board. ActivePython: claims to have some kind of IDE, but the Mac OS X package doesn't have it.

Is there one that would be as useful as, oh, Lightspeed Pascal circa 1985, if I were willing to pay for it?

As the song goes, is this all there is?

Smug Newton Weenie

2008-03-16T20:05:00.002-04:00

This past week I've been wallowing in nostalgia as I re-familiarize myself with the Newton's development environment and take a fresh look at code I wrote for the platform a dozen years ago. It's got me thinking more about the joys of small languages, and the clever hacks that enabled such an advanced GUI and applications to run on such a lightweight platform. Also, at the runtime implementation for dynamic language like this, compiled as byte codes.

I'm happy to say that I I have wireless e-mail working via my home wireless network on two MessagePad 2100s, using Simon Bell's excellent Mail V, an IMAP/POP client that integrates nicely with the Newton's built-in Inbox/Outbox program, and a couple of Lucent WaveLan cards running Hiroshi Noguchi's driver. I can even send myself big JPEG files. This is my extremely geeky equivalent of carrying around family photos in my wallet, although the 2100 only displays a few gray levels:

Interestingly, after ten days of experimentation the 4 AA batteries powering my 2100 unit still have juice left, although they are starting to fade. The 2000/2100 were a very interesting advance, because they were far faster than their predecessors the 110/120/130, yet lasted longer on the same batteries.

I hope you find this at least marginally interesting. Not everyone around me is as interested as I am in the joys of old technology, as this doodle illustrates...

Looking for a NewtonScript Book

2008-03-12T11:30:00.000-04:00

I know it is available in PDF form, but for nostalgia purposes I am looking for a paper copy of the book "The NewtonScript Programming Language." There were a couple of versions of this book; it was not sold separately but included in packaged versions of the Newton Toolkit sold to developers. And thus, most of them have probably been discarded. The older version of the book can be seen in bottom row, just left of center in this picture from the Newton Museum. The later version, if I recall correctly, was white with yellow typography and a picture of a toolbox on the cover. I will pay (some reasonable amount, plus shipping cost) for either or both books reasonable condition.

All that is Solid Melts into Air

2008-03-06T16:24:00.004-05:00

I've been moody this week. It's been just about ten years since Apple's Newton project was canceled, the products discontinued, and the staff of the project began their exodus. I hope readers will forgive me if I wax a little autobiographical.

In 1993 I attended, along with a couple of friends, the launch of the original Apple Newton. I nearly melted my credit cards into slag by buying an original MessagePad and a copy of the Newton Toolkit. Both products were over-hyped (see this impressive and slightly utopian video), and promised far more than they could deliver on that hardware, but to me the technical innovation and potential were far more interesting than the actual practicality; I was excited about some kind of platonic ideal Newton device, not the actual stubby greenish device that crashed and locked up and wouldn't boot in cold weather and ate batteries like candy and turned my handwriting into word salad. Developing with beta-this and 1.0-that was a struggle, but within a few weeks I had sent my first Newton freeware application out into the world, an ugly, misshapen little utility called Strainer, best forgotten. But it was a start -- and a doorway into a whole world of dynamic typing, closures, garbage collection, prototype-based programming, byte codes, garbage collection, and even "eval" and "apply."

My co-worker Mike and I dove into it. He created the Usenet newsgroups for Newton. I developed and maintained the early FAQ list. I did so much testing and analysis of the behavior of the built-in applications that I wound up getting calls from developers within Apple to discuss the bugs I was finding. I got to know the Newton developer tech support engineers. I wanted to be one of them. I published articles, most of them likely best forgotten, but overflowing with my enthusiasm for the new architecture. I exchanged e-mail messages with Walter Smith, the very smart guy behind NewtonScript, talking about the implementation of NewtonScript itself; he explained closures. Which got me into Dylan. Which got me into Scheme. Which (ultimately) got me into Haskell. And so forth.

The Newton was a big part of my career, on and off, for the next six years or so. I got paid to write Newton applications -- not consistently, and not just Newton applications, and not end-user, shrink-wrapped applications, but a lot of NewtonScript nonetheless. I developed a kind of DSL, in NewtonScript, built into the package by executing NewtonScript code at build time. That package acted as a kind of script itself that ran on a NewtonScript engine capable of presenting a variety of nicely-formatted question types. The survey engine had a kind of transactional semantics, even across branching, so that the data it was recording always remained consistent. It could do all kinds of post-processing and analysis on the fly, with little embedded function objects, and basically ran as a big state machine to administer surveys. It was code-as-data; it was higher-order programming. NewtonScript was, at least for me at the time, an Acceptable Lisp. For several research projects, that's how the Health Media Research Lab at the University of Michigan collected data from study participants. There were several other parts to the process -- built around AppleScript, Quark XPress, WebObjects (Java), C++, and even Visual BASIC and Perl and Scheme and Macromedia Director, and I was involved to some extent in most of them, but the Newton survey engine was my particular baby.

Apple released Newton hardware in two more form factors, ultimately culminating in the MessagePad 2000 and 2100, which pretty much _were_ that platonic ideal of a Newton device, a local maximum as far as design, usability, and features per watt, and that product hasn't had a serious contender in user-interface design prior to the arrival of the iPhone. And it came crashing down, rather abruptly, just a few months after the release of the MessagePad 2100. There was no one left to fix bugs. Because of one particular bug in the 2100, we had to scramble to stockpile the earlier MessagePad 2000, so that we would have enough units on hand to complete our research study.

A couple of years ago I discarded my original MessagePad, with its original case and "Getting Started" card and cute little power adapter and a press kit from the Newton launch -- just tossed it in the dumpster. I shouldn't have done that. Original MessagePads -- not upgraded -- are scarce on the ground, and though they are not terribly usable, the design remains interesting. A few years ago I picked up a 2100, and just recently bought 3 more Newtons on eBay, one of each form factor, but I miss the neat leather-journal feel of the rubberized original MessagePad and its snug-fitting, book-like case.

Interestingly, the Newton architecture has proved to be flexible past the point of Apple's involvement. In the box of scuffed-up Newton MessagePads was a wireless modem card. Some enterprising hackers actually got support for these devices working; I have not yet gotten it working, but I'm told that it's possible to get it working on a modern WiFi network, albeit with a somewhat minimalist web browser. I wonder if I can get the Webmail interface working via a web browser on the Newton?

I gave my wife a short demo, and she wants one, so she's going to be a rather late beta tester herself. That's good; I'd rather see them get used, than just sit on the shelf and corrode. Me, I'm going to fire up the development tools and see what it looks like to me now with ten year's more perspective.

But more broadly, the history of this technology is causing me to think seriously about what just what exactly it is that I've been doing since I got my first computer in 1977, at the age of ten.

One of the famed Alan Perlis Epigrams in Programming reads:

Is it possible that software is not like anything else, that it is meant to be discarded: that the whole point is to see it as a soap bubble?

The Vanishing Hard Drive

2008-03-01T13:07:00.000-05:00

8 inches, 5.25 inches, 3.5 inches, 2.5 inches, 1.8 inches, and 1 inch.

I predict that hard disk drives will be entirely invisible to the naked eye by 2019.

Is Python an Acceptable Haskell?

2008-02-18T11:49:00.001-05:00

So I struggled with some Python this weekend. I'm taking over a piece of code that is written in Python, but the original is very imperative, with a lot of for loops. It was giving me a headache. It just looked way too long and tedious. I'm too old to spend my life debugging off-by-one errors in for loops.

After staying up half the night struggling with a malfunctioning IDLE on MacOS X, I finally discovered the cure for the headache was -- more Python!


# This gives us a "curry" equivalent
from functools import partial

# Reduce a list of strings to a single string by concatenation
reduce_stringlist = partial( reduce, str.__add__ )

# Given a list of XML elements, return a list of only the data from only the text nodes
# (ignores any non-text nodes)
def get_text_data( nodelist ):
    return map( lambda node: node.data,
                filter( lambda node: node.nodeType == node.TEXT_NODE, nodelist ) )

# Now, combined: reduce a list of nodes to the concatenated text extracted out of only
# the text node data
def extract_text( nodelist ):
    return reduce_stringlist( get_text_data( nodelist ) )

# Given a portion of the parsed XML tree and a name, extract a single string. Expect
# only one element.
def get_one_text_element( node, name ):
    elt_list = node.getElementsByTagName( name )
    assert elt_list.length == 1
    return extract_text( elt_list[0].childNodes )

# Given a starting node and a list of tag names, retrieve one text string each and
# put them in a newly created dictionary using the tag name as a key
def make_text_element_dict( node, namelist ):
    return dict(
        zip( namelist,
             map ( partial( get_one_text_element, node ),
                   namelist ) ) )

Ahhh, I feel much better! All that excess hairy boilerplate seems to be just melting away!

The only thing I did not like is that there did not seem to be a nice way to specify keyword arguments to "reduce" so that I could create a partial (curried) application that supplied the first and optional third parameter, leaving the second as the one to be supplied at runtime.

I experimented with writing the above with Python's list comprehension idiom, generators, and various permutations on join(). The above just seems to make more sense to me. Haskell has apparently ruined me for other languages.

Apparently Guido would like to ban reduce() from Python. I say -- prefer the standard idiom to the offbeat, and avoid the Not Invented Here syndrome. Python's comprehensions and generators are nice, but apparently I've been ruined by seeking more and more expressive languages, seeking truth and beauty on my wandering but inexorable path from Dylan to NewtonScript to Scheme to Haskell. Lambda, map, curry, reduce, and zip now seem to me to be fundamental primitives that any reasonable dynamic language ought to provide, and it seems to me that they ought to be preferred to an obscure language-specific trick. As long as I have to use Python, Guido will have to pry the curried functions from my cold, dead hands!

A Pet Peeve -- Proprietary Fasteners

2008-02-14T17:20:00.002-05:00

As if it wasn't hard enough to keep tools on hand for the following screws:

- Flat blade

- Hex (in metric and fractional inch sizes)

- Philips

- Torx

- Tamper-resistant Torx (with a post in the middle)

- Torx Plus (with wider holes)

- Tamper-resistant Torx Plus (hard to come by -- with wider holes, a post in the middle, and five points instead of six)

- TTAP (a six-point variation with a deep hole in the middle, also hard to come by)

- Tamper-resistant TTAP (which I've never seen)

- Several other unusual fastener heads, such as square, two-pin, etc.

I've found that certain hard drive screws use a five-pointed variant of the six-pointed Torx star shape, which corresponds to "none of the above" and which doesn't seem to be available, anywhere. I found this out the hard way after buying a very nice set of Torx bits. The screws in question are so small it is very hard for my 40-year-old eyes to distinguish the five-pointed star from the six. They are roughly the size of a Torx T3 or T4.

The only reason I can imagine that manufacturers would use a fastener like this is sheer perversity. It isn't to make the devices tamper-proof -- the screws can be turned with a flat-head screwdriver of just the right width, although this is not ideal for either fastener or tool. Or, I could always just drill them out, as I've done on more than one occasion with a very stripped or damaged screw.

To the best of my knowledge the correct tool is not available for purchase _anywhere_ for a nobody like me, although I think you can sometimes find tools for larger versions of the bits for sale on eBay.

Several of these fasteners are apparently actually patented, and several apparently can't be legally sold except to properly licensed OEMs or other authorized personnel. Wiha sells, but will not sell to me, tamper-resistant Torx Plus tools, for example. And even if they would, they don't seem to have any this small.

As far as I'm concerned, such restrictions should be illegal. I'm sure there is an analogy here to be made to software APIs. I'm reminded of a talk I saw by Stallman, in which he drew puzzle pieces representing APIs, and talked about the evils of proprietary APIs. I bought it, I ought to have the right to take it apart!

By the way, the device in question is an iPod hard drive, made for Apple by Toshiba. But I'm sure there are many other variants of the same thing going on.

Trying Programming Environments for Children

2008-02-13T15:06:00.002-05:00

I am home sick today, feeling terrible and feverish, and should be sleeping, but can't sleep, so I thought I would try out some of the programming environments for kids. A while back I set up my son with the Haskell tools used for The Haskell School of Expression and Thompson's Craft of Functional Programming book, hoping my son would work his way into one of the texts a bit. He didn't get that far, so I thought I'd try out some other options for him.

I started learning when personal computers came with BASIC interpreters built-in, so I am looking for something equally as easy to start with, although I think teaching my son BASIC might be considered child abuse.

I thought I'd try to set him up with Hackety Hack, a Ruby environment found here. On Ubuntu Gutsy, I found that it segfaults immediately upon launch. According to the forum this issue has been reported for close to a year, with no patch.

OK, the next one on my list to try is Greenfoot. Greenfoot is Java-based, and requires a JDK. I haven't been a Java hacker since the dot-com crash, but at one point knew it pretty well, so how hard could it be for a feverish software engineer? My install of Gutsy tells me its java is "java version "1.7.0, IcedTea Runtime Environment (build 1.7.0-b21), IcedTea Client VM (build 1.7.0-b21, mixed mode, sharing)." So I'll try installing the IcedTea JDK. That looks promising, although the notes indicating it is a "temporary fork" make me a little nervous; Ubuntu lives up to its ease-of-use repuation, the JDK installs, and the Greenfoot installer now seems to be able to figure out for itself where the JDK is. The Greenfoot executable launches, and looks at least moderately interesting, so I'll call that a qualified success for now, and see if he can get his head around it.

I had it on my list to check out Nodebox, but that's for MacOS X only, and today I'm on the Linux box, so we'll save that for another sick day.

Finally, I wanted to take a shot at setting up Sugar, the Python-based environment that was designed for the One Laptop Per Child system. I'm not hugely keen on Python; having used Python and Ruby, I harbor a slight preference for Ruby, and I've got a laundry list of things I don't like about both of them. However, I'm being asked to use and get comfortable with extending several tools in my workplace that are based on Python, so for better or worse I'm getting myself re-familiarized with Python. It's quite a mature language with lots of libraries. My son could do worse, so let's see what Sugar has to offer.

There are various ways to get Sugar going on Ubuntu. See the Wiki pages here. To begin, I'm going to try the emulated route, where my Linux PC will literally emulate an OLPC laptop. The other options look considerably more complicated and error-prone; in particular, there is an absolute rat's nest of required packages. So let's see how painful setting up emulation is. First, we download a bzip'ed image file. While it is downloading, I install QEMU, which is not difficult. For now I'm not going to attempt to install the kernel support for accelerating QEMU; we'll see if it is really painfully slow. This machine is "only" a Pentium 4 2.8 GHz system that I built from parts a few years ago; pretty obsolete, but usually plenty fast.

So, image is done downloading, unzip it, and try running QEMU on it -- it works! Although it does indeed take a very long time to launch. I still find it quite surreal to watch Linux boot on top of Linux!

That's all for now -- I am still home sick, after all -- it's time to have some hot lemon tea and try to get a nap!

Followup: installing the kqemu acceleration tools does make the OLPC image run _significantly_ faster -- it is quite tolerable now, although I have no idea how it compares to how the image runs on the target hardware itself.

I Voted. I Think. Probably. Maybe.

2008-01-16T12:15:00.000-05:00

So, I don't know if you have been following news of Michigan's primaries, but they seem to be an utter farce this year. There is some kind of a dispute between the national Democratic party and the state party. The side effects are:

- Several of the biggest-name Dem candidates (Edwards and Obama among them) are not listed on the primary ballot.

- There's a write-in option, but if you write in one of these missing candidates, your vote will not be counted for that candidate(!)

- One of the candidates (Dodd) was listed, but he actually dropped out of the race earlier. (According to the results he still received 1% of the vote).

The recommendation was that if you wanted to vote for someone else, you should vote uncommitted. According to the results on Wikipedia, a whopping 40% followed this recommendation.

My precinct uses paper ballots with optical scanners. These are generally considered to be pretty reliable, and there is a paper trail in event of a recount. But this year, when I approached the scan machine, its counter read 466. After scanning my ballot, it still read 466. I asked the staff member about this -- she told me that it should read 466 and that if the machine took in the ballot and didn't spit it out, my vote was counted. Me, I'm not so sure. But the kids were in the car and my wife was late for a class so I didn't have time to stand there and try to determine exactly what was happening. But I left feeling somewhat uncertain that I had actually cast my vote. This just does not seem like democracy as it should be practiced!

A Bank Tries to Help Out

2008-01-14T15:35:00.000-05:00

I got a call from Midwest Financial Credit Union -- it seems that someone in management read my blog post. We had a long and interesting conversation and I ended the conversation a much happier customer. For now, we are going to keep our accounts, and I am happy that they are doing some things to try to keep our business.

Among the details:

The hold on deposits was part of their anti-fraud measures in place automatically for the first 30 days of a new account. Apparently this is when they get hit with the most fraudulent deposits. A warning at the time we deposited the check would have helped us out.

The $100 limit of check card transactions applies only when using the card like a credit card, as opposed to a debit card. So I can still use it as a debit and make reasonable-sized purchases. The staff member I spoke to agreed that the $100 limit is unreasonable for any real-world use and is going to try to get it raised. It would have been really helpful to be warned at the time the cards were issued, or better, beforehand, that this limit was going to be in force.

So, why such a low limit?

The conversation was illuminating. In recent years I have put in some effort and a lot of money to try to clean up my credit report. This included starting payment on some debts that were dormant for many years.

The largest of these was a medical bill for a single night in the hospital. I was fully insured at the time, or so I believed; the hospital I presented my cards to told me that they accepted my insurance; but yet I would up owing somewhere north of $5,000 because my insurer did not want to pay what the hospital wanted to bill. The hospital was not one of the insurer's "preferred" providers.

Ultimately my insurance provider paid almost nothing, but also revealed to me the collusion that goes on between hospitals and insurers -- the individual line item fees the hospital charges to their supported insurers are in some cases as low as 10% of the same item as it is billed to someone with no health insurance. But that is a rant for another day.

I ignored this bill for many years more out of disgust and anger at the insurer and hospital than out of the inability to pay, but last year contacted the credit agency that owned the debt and started paying it down. It's now about 3/4 gone.

I also had the interesting experienced of getting sued for an ancient phone bill. The bill was real, but I had become so disgusted at AT&T's refusal to accept any payment plan other than immediate payment in full, and their dogpile of additional fees and charges, that I vowed they would not get a penny from me.

Well, they did, but not willingly. The debt was sold, and sold again. I wound up paying an attorney to come up with a settlement for me, and paid the settlement. It was again highly illuminating to find out that the agency in question completely ignored several written settlement offers that I tendered, but as soon as an attorney's letterhead was involved, settled for less than I had offered. I have a piece of paper in my file that says the bill is paid.

They say that no good deed goes unpunished, and it appears that settling one debt and nearly paying off another has damaged my credit rating, because both debts are now listed as currently "in dispute" instead of just hanging on as old debts. So, it is time to write some letters. There are procedures to go through to get items on a credit report corrected. But I refuse (again, on those damned principles of mine) to pay to receive my credit scores, so instead I will have to rely on the free annual reports I'm entitled to. Paying the rating agency for my scores seems too much like extortion, as if I had to pay eBay to improve my seller rating.

So, on balance, I'm much happier with the Credit Union, but much less happy with the creditors who are screwing with my life. And I have more crap to deal with. But I guess that's what you need to do in order to play the banking game.

Banks that Suck

2008-01-07T14:03:00.000-05:00

Sorry, still no Haskell content. Please don't delete my blog! I'm working on it.

So, we were in the process of migrating our finances to a new bank, after our old bank, Republic, was pwned by Citizen's Bank and stopped doing all the things we liked about it, and started doing all the things we don't like (killing off our overdraft protection arrangement, stopping our various automatic repayment arrangements, removing access to our overdraft account from their online site, charging ludicrous fees, taking 3 days to clear electronic transactions, back-dating checks to try to hit is with more overdraft fees).

Based our on readings of their various rates and policies, we chose Midwest Financial Credit Union, here in Ann Arbor.

Less than a month later, we're now planning to close the accounts we just set up and continue our hunt for a decent bank that doesn't treat our accounts like an opportunity to slam us with fees at every opportunity -- just like Republic Bank didn't. I had my Republic account for about fifteen years and they helped me through many difficult times. Does such a place exist?

Midwest Financial got on our bad side immediately by taking ten calendar days to process a deposited $3,000 check -- while we were out of town. They finally managed to clear it (I think they took it to the originating bank in Erie, Pennsylvania by riding a mule along the old Erie Canal). It's in the fine print that they're allowed to do such things, apparently. (It's in the fine print that they can do just about anything they want, apparently).

Yesterday I tried to make a fairly large purchase (about $600) using a check card on the account -- it has a VISA logo). We have similar cards for our Citizen's Bank account and they function as either debit cards (with a PIN) or credit cards; they work fine, and we've never had an issue like this.

Anyway, the transaction was denied. Today I got word in my e-mail that a much smaller purchase (about $125) that I made online was also denied. Which is odd, because according to our most recent statement we had just shy of $3,000 in that account.

My wife went to the bank to talk to them and apparently someone's credit rating (possibly hers, since she opened the account) is rather low (we already knew that, thanks; that's old news, mostly from her days, now seven years gone, as an under-emplyed single mother), and therefore there is a $100 limit on transactions. Even though there is $3,000 in that account. Now, for a family of 5, $100 is not even a largish grocery store run. Some of these transactions could go through as debits, I guess, although there is probably some relatively low limit on the debit transactions as well. And we _have_ a card with a VISA logo because not everyone is setup to handle PIN-based debit transactions.

They told her she can apply for a 48-hour waiver to make a large purchase, or in four months we can apply to have our "credit" limit raised.

This is all too much. We're going to do neither; we're going to fire this goddamn bank and get our money back. I'm giving serious thought to turning our money into gold, silver, and platinum bars and burying them in undisclosed locations! Maybe we'll just keep our old accounts; we're starting to get used to the exact ways they screw us, as opposed to all these new ways! We are very fortunate in that here in 2008 we are finally getting ourselves to the point where we have a little bit of a safety margin in our accounts, which kept us from getting stranded while we were out-of-state on vacation. But if we didn't have that margin -- if we were still living close to the edge -- we'd have been absolutely screwed. And having been that indebted slob for most of my life, I'm only going to do business with institutions whose policies are designed to be fair to that person, not to make their problems far worse.

The Potts Vacation 2007

2008-01-04T13:31:00.000-05:00

So, we are back and the holiday trauma is over. We took the family to visit my cousins in the Washington, DC area and saw various friends along the way. I have just a touch of ranting I have to get off my chest before I can write anything else!

The trip, on Amtrak, went well for the most part. It is not easy, though, getting a disobedient pre-schooler, an infant, a teenager, two car seats, and a lot of unchecked luggage around.

The train from Toledo to Rockville, MD was only late getting into Toledo by about an hour. I was rather surprised!

We stayed in Gaithersburg with my cousin. We had planned to stay there each night, but things became more complicated. My cousin has just been diagnosed with a thyroid illness called Graves disease. This was making her unable to sleep and prone to a racing heart and anxiety attacks. This isn't good for a hostess who has to cope with two babies, so I really sympathized. We spent a couple of days staying out of her hair as much as we could, going to some of the Smithsonian Institution museums.

To top it off, our hostess was scheduled to take a dose of radioactive iodine. We had to find another place to stay for the last couple of nights because our hostess was literally about to become radioactive, and her instructions advised her to avoid people, and especially children, as much as possible! So we had to scramble a bit.

Another complication -- I deposited a check, which was going to cover some of the expenses for the latter part of our vacation, the Friday before we left, thinking that it would clear in a few days. A week later, though, acting on a hunch, I asked Grace to call the bank, and she found out that the check had not cleared, and in fact the funds would not be available until the tenth calendar day after making the deposit.

We had just set up these new accounts because we were unhappy with our old bank, which was acquired, unilaterally cancelled our overdraft protection arrangement, instituted ridiculously punitive fees, and put in place various floats and back-dating of checks apparently designed specifically to absolutely maximize said fees.

Granted, the ten calendar days, during the holidays, was only five banking business days, but in the world of Check 21 and electronic check clearing it seems just insane to me that an institution would hold a deposit that long. We were able to convince them to make enough of the funds available to cover several check card transactions we had just made, but our old bank -- the one I'm planning to leave -- clears all deposits overnight. It seems that this was technically legal under the Expedited Funds Availability Act, but I am distinctly unhappy with this, and contemplating whether or not I want to close these new accounts immediately and find another bank. (Do any of them not suck?)

Fortunately, I had set aside a little bit of extra money in a savings account at our old bank. Using my other cousin's iPhone, was able to log in to the bank and move that money into checking. Did I mention the iPhone is very cool?

We were able to stay with family friends for the last couple of days in Richmond, Virginia. Along the way I got to make Christmas better for two of their three sons. They had both gotten iPod Shuffles for Christmas. (I wonder how many people got iPod Shuffles for Christmas? It must be in the millions!) iTunes would not run correctly on their Windows XP box. They had taken it to a local Staples and the guru there had spent a whole afternoon trying to get it to work, and failed. The symptoms were this: iTunes apparently installed successfully, but would crash immediately after launching, with the usual "tell Microsoft about the problem" message. QuickTime player would also crash upon launch, with one of several error messages, including a security warning about stack overflow in a Visual C++ library. The uninstall process for iTunes and QuickTime always failed.

Despite a distinct lack of expertise with Windows system administration, I decided to take a crack at it. I had to putz around for a long time. I Googled myself into a frenzy looking for notes from people with similar problems. I downloaded and ran several virus and trojan detectors. I installed every recommended Windows XP update I could find, and cleaned out a bunch of unused software. Nothing seemed to help. Finally, I forcibly uninstalled iTunes and QuickTime (removing everything Apple-related from the registry, and deleting the program directories). I then downloaded a whole series of earlier versions of iTunes, starting with 6.10. This one installed and ran without a hitch, so I started going version-by-version. At some point, I found an installer which said that it could not run properly because the VBScript service was not enabled. This led me to an Apple support article on enabling VBScript, which had probably been turned off by a security product. After that all the installers seemed to work and I was able to get the latest iTunes installed.

The problems seems to be that one of the more recent iTunes installers silently fails if VBScript is not enabled. It runs and seems to believe that it has succeeded, but leaves behind an unusable QuickTime configuration. iTunes needs QuickTime and thus crashes on startup. Somewhere along the way Apple's installers lost the ability to verify that the necessary VBScript service is available.

After finally getting iTunes working, I thought it was all going to come to nothing, because the iPod Shuffle itself was not working. iTunes could see it, and fill it up with music, but when it came time to turn it on and push play, it would just flash a series of alternating green and orange lights and do nothing. A complete reinstall of the Shuffle's firmware didn't help. Running Apple's separately available iPod Shuffle utility designed to fix this problem didn't fix it. I thought we might have to just send the iPod back. But then apparently just toggling the little switch between continuous play and shuffle made it suddenly work. This does _not_ fill me with confidence about the device's firmware, but it was working.

Anyway, I spent a ridiculous five or six hours messing with this, but got a number of hugs in return when it finally worked. I can attribute my success only to being tenacious. Age and tenacity beats the 18-year-old Staples employee FTW!

We also got the opportunity to meet up with my friend Antonio, and had a great chat with him.

Although we gave ourselves what I thought was a sufficient safety margin, planning to arrive at the train station an hour and 45 minutes prior to scheduled departure, we had a couple of delays. We got slightly lost getting back to the train station, and so arrived only 20 minutes before the train was scheduled to arrive. While we were waiting at the light to turn into the station parking lot, it arrived. Then, under two minutes later, before we could even get inside the building, it left. Without us.

So we had another night in Gaithersburg, at a Holiday Inn. That wasn't so bad. It meant I got to watch Iron Chef and soak in the tub. We had to get a hotel shuttle to the nearest metro station, then carry the car seats on the metro, while a friend of my cousin drove our luggage to the train station. He was a huge help.

We spent New Years' Eve on the train. No one got much sleep, and we got back to Toledo on time (about 5 in the morning on the 1st). Then we had a drive back up to Ann Arbor. The drive turned into blizzard conditions. We had to crawl along moving at times just 25 mph, nervously looking at quite a few cars that had slid of the road. But we all made it back safely.

Oh, we did nearly lose one of the babies. At the end of of our train, at the last door, where you could stand and watch the tracks retreating, Grace and I had come back and stood there and looked out the window. "I wonder if that door would open if I pushed the button?" she asked. "No way," I said. "I'm sure there is a security interlock of some kind so if it isn't connected to another car, it won't open. That would be a huge liability issue if there wasn't."

Well, Veronica proved me wrong. We were walking up and down the train and she pushed the button to open the door. Fortunately, I was holding her hand. There is a kind of cage to prevent someone falling out, but it was really just a couple of metal bars and they were spaced far too widely to keep a child from pitching right out the door onto the tracks, from the upper level of a speeding train.

Grace mentioned to the conductor that the rear door was unlocked. She saw, as she described it to me, "a black man turn white." Yes, it was supposed to be locked. He _ran_ back to lock it.

So, that was our Christmas vacation. No casualties but my sanity. Now I just need a vacation from my vacation!

Brussels Sprouts with Toasted Cashews

2008-01-03T19:42:00.001-05:00

I made up this recipe after being inspired by an episode of Iron Chef I happened to see on vacation. That was a venison battle, but one of the dishes involved brussels sprouts. My family tells me it is one of the tastiest dishes I've ever concocted. I served it on New Year's Day. It seemed like a very new-year-ish dish.

If you don't like brussels sprouts, it could be because if you cook them by steaming or boiling, they tend to turn into nasty, bitter, sulfurous little cabbages. Cooking them in a dry method with high heat caramelizes them and releases wonderful complex nutty flavors and aromas.

A warning: if you are not used to eating a lot of cruciferous vegetables, this dish may be a bit challenging to digest. You may need to sleep with the windows open!

Serves 8, or me and three other people : )

I served this with mixed greens (collards, kale, and mustard greens) cooked with sage-flavored bulk pork sausage and a loaf of challah with unsweetened butter. We had a Shiraz with it, but that was all wrong; it would have gone much better with a very cold Charonnay or Riesling.

You will need:

3 or 4 lbs. fresh brussels sprouts
1 cup raw cashews
Hard cheese (parmesan reggiano, aged gouda, etc) -- enough to yield 1/2 cup grated
3 Tbs grapeseed oil
2 tsp allspice or pumpkin pie spice mix (allspice, nutmeg, cinammon, cloves)
1 tsp red pepper flakes (optional)
Salt to taste

For the spices, I actually used a leftover pumpkin pie spice mix that my wife made for Thanksgiving. I tend to cook by sniffing and tasting the spices and the raw food and deciding what seems like it would go well together. Trust your instincts!

A heatproof bowl
A large frying pan

Prep: grate the cheese. The sprouts should be dry, so if you washed them, dry them completely with paper towels. Cut off the stem ends and make them into 1/4" slices. (Don't worry if some of them fall apart and you have loose bits -- the goal is to give the vegetables a lot of surface area).

Heat half the oil to medium heat and throw in the cashews. Fry until nicely browned, turning constantly to avoid burning (perhaps 3 minutes). Scoop the cashews out into the heatproof bowl (make sure you get all the pieces of nut, or they will burn in the pan and ruin the flavor). Leave some of the nut-flavored oil in the pan. Add the cheese to the hot cashews and stir quickly. Set the nut mixture aside.

Add the remaining oil to the pan and increase the heat to high. Before the oil starts to burn, toss in the brussels sprouts. You want to cook them quickly, turning several times to lightly brown the cut surfaces, until they are softened slightly and a bit brightened in color. They should release a nutty aroma. You don't want them to start cooking down and releasing a lot of liquid. On my stove this took 3 minutes or so, but your stove may vary. Add the allspice and red pepper flakes about halfway through cooking. Add the cashew/cheese mixture and mix. Add salt to taste (I threw in only a small amount, perhaps a quarter-teaspoon). Serve immediately.

If you try this recipe, I'd be interested to know what you think!

Security Warnings with Ubuntu 7.10 (Gutsy) Updates

2008-01-03T19:32:00.000-05:00

The most recent updates to Ubuntu suddenly started generating warning messages saying that the patches could not be authenticated.

This is apparently a known bug in package bookkeeping. The procedure for fixing it seemed to be:

1. sudo mv /etc/apt/sources.list /etc/apt/sources.list.backup
2. sudo touch /etc/apt/sources.list
3. Run the package manager and check for updates. You should see none; quit the package manager.
4. sudo rm /etc/apt/sources.list
5. sudo mv /etc/apt/sources.list.backup /etc/apt/sources.list
6. Run the package manager again; this time you should be able to install the updates without warnings.

Weird!

Newegg Makes Good

2007-12-21T12:46:00.000-05:00

Newegg is refunding me the camera and case and I was able to find the camera elsewhere in time, so it is all working out OK. They have excellent customer service, so I will no doubt be buying from them again in the future.

Today is the shortest day of the year. It takes a lot of caffeine and St. John's Wort to keep me functioning this time of year. I think the barista at the local Caribou Coffee realized I needed a triple espresso and so I got a free upgrade. Either that or she was thinking "you know, we don't see you in here often enough... you're just not quite as addicted as we'd like you to be!"

This year really was a challenge -- illness, death, and mayhem all around us. Let's hope 2008 is better!

Newegg Screws Up

2007-12-19T12:27:00.000-05:00

So, I decided rather late in the season to get my son an inexpensive digital camera for Christmas. I ordered it from Newgg, a company I've had great service from in the past. I bought a motherobard and CPU from them a few years ago; I've ordered various little things like flash drives and hard drives.

They took the order for a camera, case, memory cards, and card reader. I paid with PayPal; everything went through normally. The package went out; it is supposed to be delivered today. I wanted to make sure of that, since we're obviously getting pretty close to Christmas, and my family is also planning on going out of town. In fact, we're taking the train out of town to see family. The plan was for my son to enjoy taking pictures of the trip. So it has to be here, or there wasn't much point.

Today, the day that my UPS package I've been tracking is scheduled for delivery, I got a note saying that it was all just a joke... the package I've been tracking doesn't actually have a camera in it, and I should get a refund in two or three days. Oh, it does have a cheap little camera case in it, which I threw in just because they were shipping me the camera anyway. Which means I just paid $5.24 to ship a $10 camera case.

I'm scrambling to try find the camera locally. I'm fortunate in that my finances aren't that tight right now, but if they were, I'd be completely screwed, because i wouldn't be able to charge the replacement camera on my debit card until the PayPal refund went through.

I can't recall any company I've ever ordered from screwing up an order in quite this way. I mean, I've had items cancelled on me at the last minute, or delayed, but I've never, ever been charged for an item that was not actually shipped. I'm a bit boggled by just what kind of a failure in their IT infrastructure allowed the charge to go through. Wow!

The SOE

2007-12-18T00:32:00.000-05:00

I have been looking at Paul Hudak's book The Haskell School of Expression. My first barrier was getting the sample code to work under Ubuntu "Gutsy Gibbon." While I highly recommend Graham Hutton's book, which I think of as the K&R of Haskell, SOE is more of a tutorial and may be more useful to people who learn by doing. I got a bit of assistance from Paul Liu. It turns out that in addition to installing ghc using sudo apt-get install ghc, I needed to install libghc6-opengl-dev.

Without this, when I tried to configure GLFW using runhaskell Setup.hs configure, I got an error that said Setup.hs: cannot satisfy dependency OpenGL>=2.1. I went down a dead end of trying to figure out what kind of package I needed to install to give me the right OpenGL libraries, but the key was realizing that it is looking for the Haskell OpenGL library, not the system library.

This is not specifically mentioned in any of the docs I found online -- the only place I found it mentioned was on the Debian package list -- so I am mentioning it here! Maybe if someone with the same issue is Googling for the answer, they will now find it quicker.

Getting Back Online with Music Theory

2007-12-17T20:50:00.000-05:00

Well, this hellacious year is almost over. Most of my spare time has been spent on the archiving and family history project, which I'm documenting at The Marcella Armstrong Memorial Collection. That project is bearing fruit in that I have almost a thousand images scanned, and so I'll be giving some of the originals to family members. I've created some beautiful prints, as well, and over Christmas I'm hoping to share some of the images with family members in the form of slideshows.

Meanwhile, in the back of my mind I'm thinking about how to get back into Haskell programming. Music theory keeps coming to mind.

The problem with music theory is that it is really a collection of ad hoc convenient rules and relationships in the guise of a coherent theory. The various named entities have completely inconsistent nomenclatures. You kind of get used to this when you learn to play chords and transcribe songs, but it is easy to forget how inconsistent it is and thus confusing for students.

For example, intervals. A major second is an interval also known as a whole step. If you start on the root note of a scale, say, a C major scale, the C is known as the root or "first." If you add a major second to a first, you might imagine that you'd get to a third note of the scale. But, no, you have a second note.

Does that mean the steps in the scale are off by one in their naming (that is, the first is really the zeroth?) No, because if you add two major seconds to the root, you have a third, not a fourth. It is the naming of the intervals that are off.

So can you just start the intervals at zero instead of one? Well, kind of. A minor second is a half-step, or the difference between adjacent keys on a piano. Call that 0.5. A major second is then 1.0. But this still doesn't explain intervals, because a "fourth" is actually three whole steps and a half step. And if you add a third and a third, you don't have a sixth, you have a flat seventh!

So it keeps coming back to me that I should try to codify the rules of intervals and chords in some bits of Haskell code. It might even be of use to geeks trying to understand music theory.

Don't even get me started on time signatures or tuning!

Memento Mori

2007-10-30T10:53:00.000-04:00

So, I have been falling behind on all sorts of commitments -- I was excited by the prospect of working through a bunch of Haskell exercises and get more serious about learning Haskell; I was learning all kinds of new jazz chord voicings in my guitar lessons; I had plans to record another podcast with original music.

Instead life intervened, and my mother died after a brief, unexpected illness, and then Grace's father died just under two weeks later. We've had a lot of death recently -- my grandmother died two years ago, at the age of 102, and Grace's brother died at the age of 40 just last year.

"Memento Mori" means roughly "remember, you will die." There's nothing quite like sitting in a room with the dead body of your mother to make this clear. It has been my task this year to think pretty hard about this, and to try to start planning for it, beginning what I hope will be my "ars moriendi" -- the art of dying well. And, I hope, a lot later.

I've been living on a kind of "split screen" for the last few months -- on the one hand, working on retirement plans and investments for my children's education and imagining what Grace and I are going to do for the next five, ten, twenty, or forty years, and on the other hand preparing our wills and making sure we are properly insured. It's been a strange combination of unnerving and reassuring. My grandmother made it to 102, and I have her genes, so I could have 60 years or more to live. Or I could take after my mother, and have 30.

Or none.

On the way to work this morning, as often happens, the light changed for me to make a left turn. I did my usual deep breath, look both ways, count slowly to five -- to wait for whoever was going to blast through the red light to go ahead and do so -- and then started to enter the intersection. At the ten second mark a woman in an SUV blasted through the red light, going way over the speed limit, talking on her cell phone. Missing me by only a few feet.

Memento, mori.

A year ago someone did this and I was hit by such an attack of road rage I actually chased him down, cut him off and forced him over to the side of the road, then got out of the car and chewed him out for nearly leaving my children fatherless. I can't advocate that behavior. Today I took a deep breath and let it go.

It would be a stupid way to die. But so is cancer, or heart disease. And we don't have control over everything. And believing that we do is a recipe for a heart attack.

There is good news in our lives too -- we just celebrated our sixth wedding anniversary and baby Sam's first birthday and baby Veronica's third birthday -- but these celebrations have all been kind of subdued.

There have been a whole bunch of miscellaneous estate issues -- fortunately my stepfather and the estate attorney have been managing most of this -- but my stepfather wants to sell the house he and my mother shared in the very short term, and so is trying to dispose of my mother's personal effects very quickly.

This means a house full of furniture, clothes, and personal effects. Since I'm the son that lives a mere 250 miles away, instead of 2,000, I'm the one that has to figure out how to triage everything and move anything we want to save into our rather cramped and cluttered apartment. Which means a major purge of our existing clutter, and also coming to terms with letting go of almost all of my mother's personal effects.

Along the way I discovered that my mother and my grandmother had amassed a huge collection of family photos and documents, going back several generations. In addition, hundreds of documents: letters, journals, autobiographies, even short stories.

We have pictures of people I think are my son's great, great, great, great grandparents. I have not identified everyone yet, but there may even be pictures of a five-greats grandparent. My grandmother was a member of the Daughters of the American Revolution, which means she can trace her ancestry back to 1776. Which means my daughter can, too. That's good, because it appears from the organization's somewhat controversial history that they could use more black members!

There are Civil-war era photos. Cyanotypes from around 1900. Thousands of photographs -- perhaps 10,000. The oldest ones are mostly in pretty good shape, but many of the color photos, for example instant photographs from the 1970s, are fading badly. And there are some serious preservation issues -- photos that were recently annotated in ballpoint pen ink, which is acidic and eats through the paper until it stains the emulsion. Photos torn from albums and scotch-taped into new albums, or bundled together with paper clips or rubber bands and stuffed into acidic paper envelopes and shoe boxes.

I decided, and Grace concurred, that I was going to engage on a preservation and archiving project. We can't let the collection of family history end with my generation. So I have embarked on that project, which will consist of organizing, cataloging and propagating both the original artifacts and digital derived works.

So, for the immediate future, this project is now my highest priority. My other projects, blogs, and commitments are largely at a standstill. I apologize to everyone who I've ignored or failed to follow up with on some promise or another. But I think my children and grandchildren will approve.

Anyone interested can follow my progress on my blog, The Marcella Armstrong Memorial Collection.

Another Death in the Family

2007-08-31T19:55:00.001-04:00

We just received word that Grace's father, my father-in law, died today at about 6:10 p.m. He died just 13 days after my mother.

This means that this month we lost both my mother and my wife's father. Our children just lost two of their four grandparents in a span of just under two weeks. Isaac, at 13, was old enough to get to know them a little bit, but Veronica and Sam, at 2 years 10 months and 10 months, respectively, will never really get to know them.

It's been a hell of a month. Since bad things usually come in threes, it makes me wonder what we're facing next! Maybe it's my turn?

Eulogy for My Mother

2007-08-22T14:40:00.001-04:00

(This is not about Haskell or even programming per se, but it is, in part, about the interaction between technology and human lives and the limits of that technology, and about focusing on what is important in life. So I thought the Haskell community might forgive me for posting it in this forum. I hope to get back to writing about Haskell soon).

Dear Mom,

In the past few years, whenever something happened in my life, good or bad, I always got the urge to call you and bring you up-to-date, reassure you, and get your reassurance and advice. For the past few weeks, I've had that urge to call you constantly, because a lot of big changes have been happening. Now I can't call you, but I can still write you a letter. I can't mail it to you, but here is what it says.

The big news is that you have died. This was quite a shock to everyone. It happened very fast. You had a lot of things going on -- oxygen masks, IVs, tests, pain medication, sedatives, all kinds of doctors and nurses, and lots of family members with worried expressions on their faces. It must have been very confusing, especially in the last few days, so I thought I would explain to you what happened in case you were confused.

About two years ago you were treated for breast cancer with a combination of surgery, chemotherapy and radiation. I know that was very hard on you, but the treatment seemed to be quite successful. You recovered some energy and were able to spend quite a bit of time in the last two years traveling with your husband. You were getting regular follow-up care to make sure the cancer did not come back.

About three weeks ago, after a short trip to Chataqua, New York, you were exercising with your friends at the YMCA. Things didn't feel right, though; you had been complaining about a feeling of bloating and pain in your abdomen. You said that you must have eaten something that didn't agree with you. You were only a few days away from your regular follow-up visit with your doctor. But when you called and told him about the problem, he suggested you go to the Emergency Room immediately.

From that point everything started moving with frightening speed. You had a CAT scan, and it showed tumors in your abdomen. It isn't exactly clear whether these might have been caused by cancer cells from the breast cancer or whether it was another, separate case of ovarian cancer. It doesn't really matter much at this point.

It would be easy to get very angry at your doctors and blame them. I find it a bit hard to believe that oncologists screening someone regularly for cancer would fail to detect such an advanced case of cancer. It isn't like you came down with a rare tropical disease that was outside their specialty. If anything I would have expected them to suspect cancer and do extra tests to rule it out even when it wasn't there. However, it is important to note that this kind of cancer, in the abdominal cavity, often has no detectable symptoms at all until it is very advanced. And I remind myself that the treatment you got two years ago did restore your health and give you two good and enjoyable years you would not have had otherwise.

Anyway, the next thing was that you went down to the Magee-Womens hospital in Pittsburgh for some tests. The plan then was to find out what was going on and make a treatment plan. But your pain got rapidly worse. You were admitted. I spoke to you on the phone each day for a couple of days. I was making plans to come and trying to arrange with my father and brother to come too. We got the word that you had been moved to the intensive care unit, and so everything went into high gear. We moved up our visit. My brother and my father arranged to fly out. We all got into Pittsburgh the evening of Thursday the 9th of August, just after a series of severe storms had produced tornadoes and flooding. When my father and brother got in by plane around midnight they immediately went to the hospital. Grace and the children and I all came to visit too, in the middle of the night.

You were miserable and frightened in the ICU. You were curled up on your side, wearing an oxygen mask, with your eyes tightly closed. You were able to talk, but mostly we just wanted to hold your hand. It took a while for us to figure out exactly what was going on. You had a a partially collapsed lung, and fluid building up around your lung. It was hard for you to breathe. You had pneumonia in one lung. You also had some sort of kidney infection. But with tubes and antibiotics and a lot of moral support over the next day or so you improved. You got your eyes opened and we were able to sit and talk with you. We talked about how you were doing, what we knew and didn't know about your condition. We told you about our families and how well everyone was doing. We talked about dying and what we thought it might be like, and what you believed and we believed would happen to you after you died. We told you we loved you.

You were moved back into a regular hospital room. This was still not a very comfortable environment but it was a far less frightening place than the ICU. Over the next couple of days you had a lot of visitors -- your husband Dick, your daughter-in-law Carolyn, my father Richard, my brother, your niece Linda, your nephew David, and Grace and the kids. We arranged for people to stay with you round-the-clock. Often one of us would be with you in your room while another one of us caught a quick nap in the waiting room next door.

One night while my brother was sitting with you during the middle of the night you began fighting to get out of bed. My brother tried to use the call button to get help but it didn't work. He had to run out into the hall and yell for help. You managed to get partly out of bed and it is a miracle you didn't tear out an IV. But you had a breathing crisis and you had to go back onto the high-pressure oxygen mask. You hated that mask because it was painful; it rubbed your face raw and dried out your lips and mouth terribly. For a few days it went back and forth like that. You'd improve a little bit; you got a transfusion and some new drugs and that seemed to help. But you'd get worse in the middle of the night.

The CAT scan and biopsy was postponed again and again. The doctors found that you had blood clots in your leg and also that something had gone wrong with your heart. It was very weak and it appears that you may have had a heart attack, or maybe it was damage from your previous chemo or radiation. The radiation in particular may have been poorly administered. Or maybe it was all three. They put you on heparin to thin your blood. They decided they could not do a biopsy. At one point the doctors were considering putting you back into the ICU but you did not want to go back. What you wanted was to leave the hospital, and to go up to a nursing home in Erie so that you could die in comfortable surroundings.

This brings me to the point of talking about your wishes. You made clear both in your written directives that if there was no chance of recovery, you did not want invasive procedures or extreme measures taken that would just serve to prolong your life. You told these things to the doctors as well -- no tubes for breathing or feeding, and no zapping your heart with electricity if it stopped. It is one thing to check some boxes on a form, but I think it is quite another thing to realize that it is time for these directives to be carried out. I was, in fact, awed by your bravery in sticking to your principles.

So, we next focused all our attention on trying to get you moved to Erie. I have to confess that I was terrified that you would die before we could carry out your wishes. But there was only one day's delay, and on the morning of Tuesday, August 14th, the ambulance crew came to take you to Erie. I rode in the front of the ambulance with the driver while you were in the back with the nurse. For me it was the longest chunk of uninterrupted quiet time I had gotten since leaving for Pittsburgh and I finally broke down crying for a while.

I thought that the stress on the family was going to let up and that you would be in good care. But apparently hospice care in Michigan and Nevada and California is much different than the hospice care arrangement we had in Erie. They got you settled comfortably into a room at the Manchester Presbyterian Lodge. The social worker and hospice nurses and nursing home administrator and head nurse greeted us. But things did not go quite like we planned.

All of your IVs and needles and big heavy oxygen masks were removed. Instead you just had a simple cannula in your nose for oxygen. Your pain medication was changed to liquid morphine by mouth. But after 24 hours it became clear that things weren't quite right. You went from being able to communicate to sleeping around the clock. You were over-medicated. It also became clear that without some orders from the doctor, guidance from the hospice organization, or specific requests from family, the nursing staff at the home was not going to give you special care. For example, they still had you on a regular diet. They would plunk down a meatball sub on your table and take it away an hour later. Because you were so heavily drugged they would not even try to get fluids into you. You asked for pen and paper to write some notes but you were so sedated that we could only read a few words of what you wrote. You wanted to communicate but you couldn't. The system was failing you again.

So once again the family went into high gear. We started a round-the-clock visiting schedule with you. We had to feed you because the nurses were not trying hard enough. We got your diet changed to food that you were better able to eat. We started trying to get your doctor to change your prescription, but we were unable to get the doctor out to examine you in person and change your orders until the evening of your third day there. Your condition was changing for the worse so rapidly that we found this completely unacceptable. I began refusing part of your medication on your behalf.

This was probably the most nerve-wracking experience of my life, because above all I did not want you to be in any pain, but I thought that you deserved to share your last days with your family and friends. I think it was the right decision, though. You became alert again, while reporting that you were not in any pain. You were able to visit with family and friends. We got round-the-clock visitation going again. Carolyn came back, and brought her daughter Alicia. You had live music. You had grandchildren visit. You had a couple of good days.

We still felt like we had to watch over everything. Even after your doctor came back and changed your medication orders, although my father followed him down to the nurses station to see what he wrote, what he wrote was not what he had just agreed to write. Your doctor was literally attempting to euthanize you -- not to help you live out your last days as well as possible, but to drug you up and ignore you until you died.

I felt like we were having to act as doctor and nurse and social worker ourselves, all the time. Between the lack of sleep and the nervousness, I completely exhausted myself, to the point where I could not walk and began having hallucinations from lack of sleep. I developed an ulcer. The rest of us were also exhausted. It was the single most stressful week of my life to date.

You gradually became weaker. Your heart rate went up and your blood pressure went down. You began to accumulate more fluids in your lungs. We got your medication raised again so that there was no possibility you would be in any pain. The decision was made that you could not receive anything more by mouth to eat or drink. On Saturday evening at about 6:30 p.m. you died. It was as peaceful and graceful a death as we could make it. I was not there, but your husband and his daughter Alicia were there. Alicia was playing music.

I just want to say a couple more things.

First, that the way you faced your death was an inspiration to me and to everyone around you.

Second, when my father and I were visiting you in the ICU, you said that you were very proud that you had always had the ability to forgive everyone who had harmed you. I would like to ask you one last favor. I want you to forgive the doctor in Erie who displayed such indifference to your condition. I want you to forgive the other doctors that failed to detect your cancer. I even want you to forgive the doctor in Pittsburgh who had such terrible bedside manner that he burst into your hospital room, explained loudly that your heart was failing and that there was nothing more they could do, and left. I will forgive all these people. It might take me a while longer, though. I'm not quite as good at it as you were.

Third, I'd like you to remember that we had our share of doctors with poor bedside manner and nurses who treated you like an annoyance, there were also quite a few people who were very kind to you. The hospice nurse who was with you on your last day was wonderful. The palliative care physicians in Pittsburgh were wonderful. They spoke very calmly to you and asked you if you had any unfinished business. You said that you wanted everyone to know that you loved them.

And last, I just want to thank you. You were a single mother in a difficult time. You had a hard and complicated life. You raised me and my brother. You did a great job. You re-married and brought new fathers into our lives. You cared for my stepfather Wence, and you cared for your mother, and you cared for your husband Dick. You enriched the lives of everyone around you. You had a lot of friends and you were well-loved, and you still are.

We'll go on. We'll miss you terribly. I wish you had gotten more time to enjoy your grandchildren. I wish we had gotten more time to spend with you. You said that you were concerned about the state of the world. The world will go on. It will be OK. We'll be OK. And we know that you are OK now too.

I'll see you again, before too long. And I'll be in touch.

Love,

Paul

A Hard Dive Headache

2007-05-07T00:42:00.000-04:00

This isn't exactly programming-related per se, but I present henceforth my story demonstrating how hardware compatibility issues trump software compatibility any day!

I have a PC and a Mac on my desk at home.

I have a small handful of spare hard drives I use to back up these computers plus two laptops.

I try to buy hard drives when they hit a price bang-for-buck "sweet spot" -- this year, that is in the 250G range; a couple of years ago, it was in the 40G range. So I have a couple of 250G La Cie enclosures. I also have a couple of fanless "Mad Dog Multimedia" enclosures which I bought empty and filled with Seagate 40G drives. They're both USB/FireWire, which is ideal for moving things around between Macs and PCs.

All of them come with external power bricks. The power bricks for all four drives are nearly identical, physically, black boxes with removable AC cables and attached DC cables. The boxes have little green LEDs. They all have identical DIN-4 round 4-pin connectors. These have a little notch on one side and a flat spot on the other, to make sure you orient them correctly when you plug them in, and identical DIN-4 connectors that plug into the drives.

They're all plugged in to power strips on my desk.

The "Sunpro Powmax" bricks that came with the Mad Dog enclosures have a little diagram on them that looks like this (sorry, I don't have a digital camera that will zoom in close, or I'd take a picture).

            _____ 
          /       \
GND ---- | *     * | ---- GND
+12V --- | *     * | ---- +5V
          \       /
           --__--

On the diagram above, the flat side of the connector is shown at the top, and the little "notch" is not shown, but it goes at the bottom.

The LaCie bricks, on the other hand, made by "Sunfone" instead of "Sunpro," have a little diagram that look like this:

     --  ---
    /  \/   \
2  | *     * | 1  PIN 1:5VDC
4  | *     * | 3  PIN 2:12VDC
    \_______/     PIN 3:GND
                  PIN 4:GND

Where the flat part of the circle is at the bottom and the little notch is at the top, although this is actually pretty hard to distinguish in the diagram.

I'll flip them around for you so the orientation of the circular connectors is the same, and label the pins more clearly:

    __-----__           __-----__
  /           \       /           \
 |   G     G   |     |    G    G   | 
 |  +12V  +5V  |     |   +5V  +12V |
  \           /       \           /
    -___/\__-           -___/\__-

Just let that sink in for a moment.

It took me a while to guess why my hard drive, a 250G La Cie drive, wouldn't mount. Finally I started looking at the power bricks. You know that feeling you get when you find out that you've just broken something expensive?

I guess it could have been worse; it could have fried the PC's motherboard too, via the USB port. Who designs this crap? (I know who builds it, but I can't very well blame this on the manufacturers in China; it appears they both did a wonderful job manufacturing exactly what was specified).

Both power supplies have all the appropriate regulatory agency approvals: CE, FCC, UL, and some others I don't recognize. But, of course, they don't actually conform to any particular wiring standard.

After determining that the La Cie drive was out of warranty, and given that the warranty was unlikely to cover this kind of idiocy, I decided to try opening up the enclosure in the hopes that it might have some kind of fuse that I could replace, and that the drive itself was OK.

Surely they must have some kind of fuse in the enclosure's circuitry, right?

I'll bet you a new hard drive that they don't.

Well, the La Cie enclosure is a pretty nice enclosure, but it isn't designed to come apart. They have part of the drive covered with an easily torn (yes, I should know) adhesive foil, and mounted on some kind of sticky silicone anti-vibration pad. I could try stuffing a new drive in it at some point.

The dead drive smells like burning plastic. There's one little surface-mount component on the back that is visibly burnt. If this were 1980, with my knowledge I gained putting together Radio Shack 250-in-one electronic experiment kits, I would be able to tell you if it is a resistor or a capacitor or a diode. If this were 1980, I could probably even solder on a new part. But it is 2007 and all the little black parts look the same, and even if I could find a replacement component I doubt I could solder it on.

Needless to say, the drive would not spin up when I put it in the "Mad Dog" enclosure.

So I put the 40G drive back into the "Mad Dog" enclosure, and powered it up.

I'll give you two guesses which kind of power brick I plugged it into.

My office smells like burning surface-mount components. There's a nearly identical little burnt component on the other drive. It's in a slightly different place on the 40G drive.

I had some files on those drives that I wanted. The 250G drive had mostly unimportant stuff, but a few gigabytes of important stuff.

I'm no fool. I kept a backups of that handful of important files.

On another hard drive. Guess which one?

I've got a headache.

I can't in good conscience ask Seagate to fix them under warranty. Can this kind of thing even be repaired any more? It seems like it should be possible. But I'll have to look into that later.

I'm going to bed. Ever feel like you want to yell at someone for being an idiot, but the only one you can find is between your own chair and keyboard?

A Wonderful Waste of Time

2007-04-09T23:11:00.000-04:00

I just encountered this great toy to challenge your three-dimensional geometry skills. The game in effect asks you to pretend you're creating an Escher-like puzzle, producing a an object that only looks right from three precise vantage points. Ever wanted to pretend to be a 3D rendering optimizer function? Now's your chance!

Warning: if you start it, you won't be able to stop until you complete all the puzzles. Which I did, although it took me an embarassingly long time.

Haskell for the Short Attention Span: A Simple File Filter

2007-04-09T21:28:00.000-04:00

Well, there is more to say about run-length encoding and other interesting examples I was sent in response to my last article, but today I've been working on another little real-world problem. I've been able to spend a little bit of time on #haskell and the gang there has been extremely helpful. The task: filter a binary log file, turning it into a text representation, and do some stateful validation. I'm not going to show you all the code (it is pretty boring), but here are the minor pitfalls and helpful suggestions I encountered along the way. First, I started with a very basic file filter example from the Haskell 98 report:

main = do
        putStr "Input file: "
        ifile <- getLine 
        putStr "Output file: "
        ofile <- getLine 
        s <- readFile ifile 
        writeFile ofile (filter isAscii s)
        putStr "Filtering successful\n"

Pretty simple. As a sanity check, I wanted to run this example on a data file. The first thing I found is that isAscii is not in the default namespace. To use this program in GHC you'll need to import the module Char. You can learn this via Hoogle. I've started using Hoogle quite a bit; it is a great little tool! You can find Hoogle here. You can also get to it directly through #haskell via LambdaBot. Or you can put it right in your GHCi. Lambdabot lives here.

Anyway, the next thing I found was that, at least under Cygwin, unless you explicitly open a file in binary mode, you might encounter problems. One I should have anticipated -- you might see line feed translation. But there are apparently others -- like silent truncation of the data! Somewhere in the guts of Cygwin, or maybe Windows, control codes designed back in the Jurassic days of computing are still being honored. Input was terminating on (apparently) an EOF character in my binary file. Another suggestion from one of the very smart folks on #haskell.

I'll just use readBinaryFile instead of readFile, right? Well, no, readBinaryFile is part of MissingH, a third-party library. Back to #haskell, where I was advised that I could roll my own. Importing System.IO, I use the following snippet:

readBinaryFile s = System.IO.openBinaryFile s System.IO.ReadMode >>= System.IO.hGetContents

This works fine, although I would humbly suggest that GHC's standard library should provide easy access to binary files; while the solution is pretty trivial, it is a wart.

I next stubbed my toe on printf. Printf is available in module Text.Printf and provides a type-safe version of C's printf. As a long-time C and C++ programmer, you'd think I'd know just about everything there is to know about printf. So, I rapidly gave it a format string "%02X" and passed it a char. Apparently the uppercase X to produce a hex representation with uppercase A-F is not supported (grrr). Another minor wart -- if you provide printf, it should behave like printf -- but we'll move on.

Per more chatting on #haskell I was given this one liner to dump binary data in a nicely formatted way:

writeFile ofile (concat $ zipWith (printf "%02x %s") s (cycle $ replicate 19 "" ++ ["\n"]))

I want to take a moment to talk about how it works. First, cycle $ replicate 19 "" ++ ["\n"]. The replicate function gives us a list of 19 empty strings, which we then concatenate with a newline. Applying cycle to this list treats it as an infinitely repeating circular list of strings, where every twentieth is a newline. These arguments are then fed to printf using zipWith. zipWith is an interesting function: while zip takes two lists and generates a list of pairs produced by assembling the list elements into tuples, zipWith doesn't tupleize the elements; instead it feeds the elements to the provided function, and makes a list of the results.

While this worked, it was interesting enough that I wanted to play with it using GHCi. But I had to give up on that; I kept tripping over the type checker. While I appreciate the masochistic joys of programming and the safety that comes with it, it can be frustrating for programmers with experience in, say, Ruby, or even C.

For example:

let xs = [1..100]
let ys = take 100 (cycle $ replicate 19 "" ++ ["\n"])
zipWith (printf "%02x %s") xs ys

GHC replies:

Ambiguous type variable `c' in the constraint:
`PrintfType c' arising from use of `printf' at :1:9-24
Probable fix: add a type signature that fixes these type variable(s)

Ugh. Using the ":t" command in GHC it is easy to see that GHC thinks the type of xs is [Integer] and ys is [[Char]] (a list of list of chars, also known as a list of strings). If I put roughly the same code in a Literate Haskell source file and ask GHC to load it, I get:

  Ambiguous type variable `a' in the constraints:
    `Enum a'
      arising from the arithmetic sequence `1 .. 100'
      at E:\toy.lhs:3:5-12
    `Num a' arising from the literal `100' at E:\toy.lhs:3:9-11
    `PrintfArg a' arising from use of `printf' at E:\toy.lhs:5:18-33
  Possible cause: the monomorphism restriction applied to the following:
    xs :: [a] (bound at E:\toy.lhs:3:0)
  Probable fix: give these definition(s) an explicit type signature
                or use -fno-monomorphism-restriction

followed immediately by:

  Ambiguous type variable `c' in the constraint:
    `PrintfType c' arising from use of `printf' at E:\toy.lhs:5:18-33
  Possible cause: the monomorphism restriction applied to the following:
    result :: [c] (bound at E:\toy.lhs:5:0)
  Probable fix: give these definition(s) an explicit type signature
                or use -fno-monomorphism-restriction
Failed, modules loaded: none.

Wow. I'd say that is not really a newbie-friendly error message. However, this printf works fine in my real program. I'm not certain why, and I'm not going to dive into it too deeply right now. But here's a simpler type checking example: while C is strongly typed, you can treat numbers as chars and vice-versa, as long as you keep integral promotion and sign extension in mind. GHC is a harsher mistress. Let's say we want to pattern-match on our binary data. The value 16 in my binary data is DLE, which stands for Data Link Escape; it is often used in serial data to indicate packet boundaries, while inside the payload, it will be escaped (doubled). So here's a little pattern to remove doubled DLEs:

de_dle (16:16:xs) = ...

Simple enough, right? No, to Haskell a number and a Char are not interchangeable. Back to #haskell, where I got a quick explanation of the type checker's error messages. I turned the numbers into chars:

de_dle ('\16':'\16':xs) = ...

And that works just beautifully.

Anyway, to make a long story shorter, I was able to write my file filter, which does some nice pattern matching and formatted out. The problems I had while developing that were the kind I like: problems choosing my algorithm properly, not problems fighting with the language. The runtime was quite helpful here; while processing the file, if I hit a case at runtime which my patterns did not handle, I got a runtime warning about non-exhaustive patterns. That led me to reorganize my patterns, and the result was much clearer.

There was one more minor pitfall remaining. I compiled my program using GHC, but when I ran it, instead of my prompts for input and output filenames, I got nothing! Haskell was silently waiting for input. Back to #haskell. To make the output show up, I had to import System.IO and do hSetBuffering stdout NoBuffering. (Alternately, I could flush stdout immediately after each putStr, but that seems even uglier). I hope that saves someone a little aggravation.

Speaking of aggravation, how did it all come out? Well, the original binary log file is about six megabytes. Since I was doing this by hand, I was more concerned that the program ran correctly than that it ran fast; I would have been satisfied with anything under a half-hour. In fact, without any attempts at optimization at all, my filter ran in under thirty seconds, which is more than fast enough for an ad hoc little tool. I started out trying to do this task using some regular expressions in vi, and that was quickly going nowhere, and taking forever to do it. The vi that came with Cygwin doesn't support some of the more advanced regular expressions features (there is no {x,y} syntax for specifying the number of repeats of a pattern). Notepad++, my workhorse Windows text editor, also doesn't support this syntax. Without this the regexes were becoming hideous, although in (say) Perl they would have been rather simple. But I was able to use Haskell instead, thanks to GHC and the kind folks on #haskell!

Haskell for the Short Attention Span: Run-Length Encoding, Part 3

2007-03-07T17:02:00.000-05:00

This isn't a big improvement, but it occurs to me that my implementation from last time:

>deRLE :: [Integer] -> Bool -> Integer -> [Integer]
>deRLE [] False _ = []
>deRLE points False max = deRLEHelper points max
>deRLE points True max = deRLEHelper (0 : points) max

>deRLEHelper :: [Integer] -> Integer -> [Integer]
>deRLEHelper [] max = []
>deRLEHelper [unmatched] max = [unmatched..max]
>deRLEHelper (start:end:rest) max = [start..end - 1]
>  ++ deRLEHelper rest max

can be yet shorter; since deRLEHelper handles the empty list specially, deRLE doesn't need to:

>deRLE :: [Integer] -> Bool -> Integer -> [Integer]
>deRLE points False max = deRLEHelper points max
>deRLE points True max = deRLEHelper (0 : points) max

That way only the function that actually recurses down to the empty list has to explicitly handle it.

Can we make it even more concise and still retain the self-documenting aspects of the code? I'll have to come back to that question. It's time to respond to comments. When I first mentioned my triplify function, which breaks a string into strings of three characters, I wrote "I'm sure there is a very clever one-line fold that applies take 3 in an mind-expanding manner, but I was unable to find it." I got some great suggestions. The first, due to Cale Gibbard, was:

map (take 3) . takeWhile (not . null) . iterate (drop 3)

Let's look at it piecewise as a pipeline, from right to left.

First, our list/string (for example, "ABCDEFG") is fed to the function iterate along with (drop 3). Iterate is an interesting function. I tried to understand it a few months ago by reading the description at zvon.org, which says that iterate;

creates an infinite list where the first item is calculated by applying the function on the secod [sic] argument, the second item by applying the function on the previous result and so on.

They give the following example:

Input: take 10 (iterate (2*) 1)

Output: [1,2,4,8,16,32,64,128,256,512]

Note that if the behavior followed the description, the output would be [2,4,8,16,32,64,128,256,512,1024]. Their description is wrong, although the output matches GHCi's output. What does iterate really do? I'll describe it in the form of a poem.

iterate takes a function and a value, and returns a list consisting of:

  the value

  followed by
    the value of applying the function to the value

  followed by
    the value of applying the function to
      the value of applying the function to the value

  followed by
    the value of applying the function to
      the value of applying the function to
        the value of applying the function to the value

  it will keep talking
    even when
      it has nothing
        new to say
          so please don't
            ask it any
              open-ended
                questions...

That is, I can't evaluate

iterate (drop 3) "ABCDEFG"

because even though the input is finite, the output isn't; there's no termination to the recursion. However, I can evaluate part of the result:

take 4 (iterate (drop 3) "ABCDEFG")

["ABCDEFG","DEFG","G",""]

And because of Haskell's lazy evaluation, we can feed this infinite result "upstream" to be used in the remainder of our calculation, and it will work fine as long as it doesn't evaluate the complete result. The next stage in our "points-free" pipeline is:

takeWhile (not . null)

The takeWhile function operates on a list, returning a list made up of its values as long as they match the predicate supplied. This has the effect of squashing the overly talkative iterate, because we stop evaluating its results as soon as it returns the first null value. Lazy evaluation is so cool!

Now, our finite list of strings is handed off to map (take 3), which generates a list of 3-character prefixes. Here's the whole process:

iterate (drop 3) "ABCDEFG"

yields an infinite list beginning ["ABCDEFG","DEFG","G",""];

takeWhile (not . null)

applied to the above will take elements from the list until it hits the first null: ["ABCDEFG","DEFG","G"]

map (take 3)

applied to the above will give us ["ABC","DEF","G"]. Note that the short remainder is preserved.

That seems so useful, I'm surprised it isn't a function in the Standard Prelude, called groupsOf. Although it would also be nice to have a version which didn't keep the short remainder, perhaps groupsOfOnly.

I got another suggestion from a user called "kirby." He suggested the function

takeWhile (\="") . List.unfoldr (Just . splitAt 3)

Wow, my first unfoldr! I'm going to have to stop there for today, while I learn a little something about Just, Nothing, and the Maybe warm fuzzy thing. My first funster!

English Majors as Programmers

2007-03-06T11:02:00.000-05:00

The Embedded Muse is an e-newsletter edited by Jack Ganssle; see the Ganssle Group home page. In Issue 142 he writes:

I've found that some of the best developers of all are English majors. They'll often graduate with no programming experience at all, and certainly without a clue about the difference between DRAM and EPROM.

But they can write. That's the art of conveying information concisely and clearly. Software development and writing are both the art of knowing what you're going to do, and then lucidly expressing your ideas.

The worst developers, regardless of background, fail due to their inability to be clear. Their thoughts and code tend to ramble rather than zero-in on the goal...

Too many engineering-trained developers have a total disregard for stylistic issues in programming. Anything goes. Firmware is the most expensive thing in the universe, so it makes sense to craft it carefully and in accordance with a standard style guide. Make sure it clearly communicates its intent. This is where the English majors shine; they've spent 4 years learning everything there is to know about styles and communication.

As an English major who has programmed computers since the age of ten, and who also took every programming course I could manage, it's nice to hear a little love for English majors! But I should add that an English degree is not a requirement; I also know some excellent developers who majored in more technical subjects, such as anthropology and archaeology!

Haskell for the Short Attention Span: Run-Length Encoding, Part 2

2007-03-05T20:13:00.000-05:00

Greetings! Last time I introduced a piece of code to solve a small real-world problem: decoding a set of function IDs from a run-length-encoded list of change points. I received some excellent feedback. One of the most valuable suggestions was that I avoid unnecessarily taking the length of the list in my "triplify" function. That makes a great deal of sense, considering that ideally I'd like to be able to handle infinite lists, and of course it would be nice if the runtime of my algorithm did not spiral out of control quite so quickly!

I also gave a little more thought to the various base cases. One of the nicest things about Haskell is its pattern matching. Indeed, even a simple function like "square a = a * a" makes use of pattern matching, where "a" on the left-hand side is irrefutable. My implementation last time failed to fully take advantage of pattern matching on multiple parameters, particularly to handle base cases, and did not even handle all the various termination conditions properly. So, here is a slightly condensed version of the code that makes the termination conditions much more explicit, and so I claim even though it is shorter, it is more self-exlanatory.

>import Char
>import Numeric
>rle_raw_str = "00 30 90 09 31 01 10 32 20 22 12 30 23 12 41 24" ++
>  "34 40 44 1C 0F C1 1D 00 D0 1D 03 D0 4D 05 D0 7D 0A D0 CD 10" ++
>    "D1 2D 20 D2 6D 30 D3 1D 40 D4 1D 50 D5 1F 00"

A new triplify:

>triplify :: String -> [String]
>triplify [] = []
>triplify (x:y:z:rest) = [x, y, z] : triplify rest
>triplify str = error "Unexpected string length (trying to match 3 characters)"

Treating the input data as a list of 12-bit numbers:

>rle_change_points = map (fst . head . readHex)
>  (triplify (filter isHexDigit rle_raw_str))

The main function: given a list of change points, a hint as to whether we are initially presuming the decoder will output ones or zeroes, and a maximum value, decode RLE data from the change points. Return the indices of the one bits.

>deRLE :: [Integer] -> Bool -> Integer -> [Integer]
>deRLE [] False _ = []
>deRLE points False max = deRLEHelper points max
>deRLE points True max = deRLEHelper (0 : points) max

>deRLEHelper :: [Integer] -> Integer -> [Integer]
>deRLEHelper [] max = []
>deRLEHelper [unmatched] max = [unmatched..max]
>deRLEHelper (start:end:rest) max = [start..end - 1] 
>  ++ deRLEHelper rest max

This is more like it -- the kind of program that resembles a proof more than code. I'm starting to prefer this style!

A brief explanation: if we're initially decoding zeroes, the empty list case can be disposed of quickly. The program filters this case out first so that the recursive helper function, which accumulates the output, doesn't need to handle this case. The next two lines handle non-empty lists. If we're initially decoding ones, we can still treat all cases the same if we just prepend a zero to "flip" the decoder. Our helper function then has only three cases: a termination case where an interval of ones is not closed (because we have a single change point left), in which case we spit out ones up to and including our maximum possible value; a termination case where we have two change points forming a closed interval, in which case we spit out an interval inclusive of the start and exclusive of the end, and a non-termination case in which we have more than two entries, which spits out a closed interval and continues the process.

Let's look at some test cases. First, we confirm that if we're generating zeroes and we encounter no change points, our result set is empty:

deRLE [] False 0xF

[]

We confirm that if we hit a single change point, the result set will contain all the values up to and including the maximum possible:

deRLE [0] False 0xF

[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

deRLE [11] False 0xF

[11,12,13,14,15]

In the general case where our interval is closed, our result set is inclusive on the left and exclusive on the right:

deRLE [5, 10] False 0xF

[5, 6, 7, 8, 9]

Closing one range and opening another without closing it works correctly:

deRLE [5, 10, 11] False 0xF

[5,6,7,8,9,11,12,13,14,15]

If we begin assuming our decoder generates zeroes, an empty list of change points maps to all possible values:

deRLE [] True 0xF

[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

A single change point at zero toggles the state of the decoder and produces and empty result:

deRLE [0] True 0xF

[]

A single change point greater than zero allows some values into our result set before it is closed:

deRLE [5] True 0xF

[0,1,2,3,4]

Two change points defines a range to exclude from the results, and we get the rest of the values in the range:

deRLE [5, 10] True 0xF

[0,1,2,3,4,10,11,12,13,14,15]

Three change points suppresses the rest of the result set:

deRLE [5, 10, 13]

[0,1,2,3,4,10,11,12]

With these tests I'm satisified that deRLE works for all expected cases.

I received more comments, including some recommendations for a nifty unfold. Thanks to everyone who made suggestions. Next time I'll take a look at how those work, talk about anything else that comes to mind, and then proceed to my next real-world problem!

Haskell for the Short Attention Span: Run Length Encoding, Part 1

2007-03-01T22:47:00.000-05:00

I'm a fortunate man. Some 50% of people who suffer herpes zoster infections involving the eye wind up with permanent eye damage. I seem to have escaped with little or no permanent damage. The nerves are not completely healed, and there is still visible damage under the skin, but it is no longer painful to work at the computer or read!

It's time to jump back on the horse and risk looking foolish in public by writing some code. I still consider myself to be close to a rank beginner in Haskell, so you're reading my "finger exercises." To experienced functional programmers they will probably sound like a new violin student sawing away. However, since I haven't been a student for almost twenty years and there is no one to assign me homework but myself, this seems to be the next best way to force myself to learn something!

With three children at home, two of them babies, I don't get a lot of unbroken free time; I've got a guaranteed short attention span. So consequently I'm going to look at some very small programs. However, rather than make up toy programs from scratch, I am now going to turn to a few real-world problems that I've stumbled across while doing embedded programming.

OK. Consider a spherical cow of uniform density... wait, I mean, consider a black-box system with an outward-facing interface in which a number of functions are made available. Functions are accessed via a 12-bit unique ID. A client of that system doesn't know which functions are available. The client needs a method to retrieve a list of funciton IDs. Let's assume we don't have bandwidth to burn, so we don't want to send a complete list of all the function IDs. Let's further assume that the functions are organized into a small number of groups with consecutive IDs. In other words, this is data that is very amenable to a simple compression scheme.

We're going to do it using Run-Length Encoding (RLE). Here is a brief informal explanation of RLE; if you are already know all about RLE, skip the next paragraph (but read the ones after that, please!)

RLE is a commonly used technique for encoding bitmaps; a variant of RLE is even used in fax machines. Rather than store a bit for every bit in a bitmap, RLE records _runs_ of repeating data. If you have a raster image that you're scanning left to right, top to bottom, and that image has a lot of horizontal lines in it, or black and white rectangles, this might be a big win. The RLE encoding will record long alternating runs of ones and zeroes. If the image has a lot of vertical lines, this might not be much of a win. The worst-case scenario is a 50% checkerboard: in that case, we'll have to indicate runs of length 1, and the overhead will be far worse than just encoding the bits. For that kind of image you'd be better off using a means of compression that actually adapts to the frequency of occurrence of particular patterns in the data, such as Huffman coding or LZW.

Now, there are several possible ways to represent the runs of RLE data. One scheme might use tuples consisting of the bit value and the number of occurrences of that value (the "run length"). For example, the tuples [(0, 14), (1, 28), (0, 3)] could represent a run of fifteen zeroes, followed by a run of twenty-nine ones, followed by four zeroes. Why are the values off by one? Because we would never need to encode a run of length zero, so we allow zero to represent one, and so on. A tuple like this could be encoded in a single byte, where the high-order bit represents the value and the remaining seven bits represented the run length - 1. This gives us the ability to represent runs of up to 128 bits. Of course, if we have a run of length 129 or greater, we'll need to represent it with multiple bytes. For degenerate cases where we encode very long runs, we'll have unnecessary redundancy.

For that low-entropy bitmap, a better scheme might be to just record the points at which the data _changes_. We have to choose an initial state for decoding: should the decoder, prior to the first change point, produce ones, or zeroes? Once we know that, we don't need to encode the bit values at all. If we assume that our encoded data begins with a run of zeroes, we could represent the example above (fifteen zeroes, followed by twenty-nine ones, followed by four zeroes) by recording only [15, 44]. Let's say that we want our decoder to spit out the indices of the one bits. We'll get:

[15,16,17,18,19,20,21,22,23,24,
25,26,27,28,29,30,31,32,33,34,
35,36,37,38,39,40,41,42,43]

Using this scheme, a bitmap of all zeroes would be represented by an empty list, while a bitmap of all ones would be represented by by a single [0]; it turns on the "ones" state and never turns it off, so we just generate ones until our range of values is exhausted. (This implies that, in addition to knowing what starting state it should assume, the decoder has to know the size of the bitmap we are representing). A bitmap consisting of all zeroes followed by a single one would be represented by [N - 1] where N is the number of bits in the bitmap.

If, instead of assuming that our data starts with an implicit run of zeroes, we assume instead that it starts with an implicit run of ones, it should be obvious that we could encode the same example using [0, 15, 44]; in this case, a bitmap of all zeroes would be represented by [0], which would yield an empty list of one-bit indices, while a bitmap of all ones would be represented by an empty list, yielding a list [0..n - 1] of bit indices.

We'll assume that our function IDs are represented this way: they are the one bits in the bitmap, and we want a list of their indices. When we query our interface about its function IDs, we get back a response that consists of a short list of change points. Here are the data bytes:

00 30 90 09 31 01 10 32 20 22 12 30 23 12 41 24 34 
40 44 1C 0F C1 1D 00 D0 1D 03 D0 4D 05 D0 7D 0A D0 
CD 10 D1 2D 20 D2 6D 30 D3 1D 40 D4 1D 50 D5 1F 00

The first time I encountered data like this, I wrote myself a little bit of Ruby code to decode it. Here's first part of the Ruby code, which turns these bytes into a series of 12-bit unsigned numbers by assembling three nybbles (half-bytes) at a time:

rle_raw_list = gets.chomp.delete(" ")

rle_change_func_ids = []
0.step(rle_raw_list.length - 2, 3) { |nybble_idx|
  rle_change_func_ids.push(rle_raw_list[nybble_idx..nybble_idx + 2].hex)
}

Here's how it works. The first line reads data from standard input and, reading left to right, removes any end-of-line character and deletes spaces. We next create an empty list. "0.step" is cute little bit of idiomatic Ruby shorthand: everything is an object, including integers, and they have a "step" method, so by calling 0.step we loop from zero to the string length - 2, incrementing by threes. We also provide a Ruby block, which is basically a closure that receives one parameter, the loop index, and which is bound to the name nybble_idx. Working inside-out, the body of this closure takes three-byte substrings of the raw data, passes them to the hex function to yield an integer, and then uses push, which treats the list like a stack and appends the new integer to the end. The result looks like this:

[0x003, 0x090, 0x093, 0x101, 0x103 ...]

This is the list of change points. Once I have that, I can generate the runs of data. I'll assume that our data starts with an initial run of ones:

rle_state = true
MAX_FUNC_ID = 0xFFF
current_func_id = 0

for change_func_id in rle_change_func_ids
  if rle_state == true
    (current_func_id...change_func_id).each {|valid_func_id|
      puts sprintf('0x%02X', valid_func_id)
    }
    rle_state = false
  elsif rle_state == false
    rle_state = true
  end
  current_func_id = change_func_id
end

Now, I should mention that I like Ruby, and especially like its support for nice idioms like blocks and closures and iterators and chaining functions. But while this Ruby code worked well enough for my little task, you might notice that it doesn't actually handle all the termination cases properly. As I work with Haskell, I'm finding that I like it quite a bit more than Ruby. One of the reasons is that Haskell code, being less imperative, seems closer to a kind of abstract, platonic representation of the problem space. Problems such as the failure to properly handle various termination cases tend to look much more obvious, particularly when functions are broken down into pieces using pattern matching.

Anyway, here's my Haskell version:

>import Char
>import Numeric

>rle_raw_str = "00 30 90 09 31 01 10 32 20 22 12 30 23 12 41 24" ++
>  "34 40 44 1C 0F C1 1D 00 D0 1D 03 D0 4D 05 D0 7D 0A D0 CD 10" ++
>  "D1 2D 20 D2 6D 30 D3 1D 40 D4 1D 50 D5 1F 00"

(My first opportunity to look silly: I'm sure there's a way to break a string across multiple lines with some sort of continuation character, but I could not get "\" to work together with Literate Haskell mode, so I'll just concatenate them and hope no one notices...)

>rle_bytes_str = filter isHexDigit rle_raw_str

That was easy!

Now, my second opportunity to look silly: I'm sure there is a very clever one-line fold that applies "take 3" in an mind-expanding manner, but I was unable to find it. This was about as clever as I could manage, but it does have the advantage of checking for unexpected data length:

>triplify :: String -> [String]
>triplify str | length str == 0 = []
>triplify str | length str `mod` 3 == 0 = ( take 3 str ) : triplify ( drop 3 str )
>triplify str = error "bad length (expected multiple of three)"

To see the results, evaluate "triplify rle_bytes_str." I get:

["003","090","093","101","103","220","221","230","231","241",
"243","440","441","C0F","C11","D00","D01","D03","D04","D05",
"D07","D0A","D0C","D10","D12","D20","D26","D30","D31","D40",
"D41","D50","D51","F00"]

Now I want to turn these into a list of numbers; these are the change points. Mumble, mumble...

>rle_change_points = map (fst . head . readHex) (triplify rle_bytes_str)

[3,144,147,257,259,544,545,560,561,577,579,1088,1089,3087,3089,3328,3329,3331,3332,
3333,3335,3338,3340,3344,3346,3360,3366,3376,3377,3392,3393,3408,3409,3840]

Our playing field is the range of integers 0x000..0xFFF or 0..4095 in decimal. We want to lazily generate a list of valid values using our RLE decoding scheme. Rather than walk the list of change points spitting out values using some kind of toggling state variable to keep track of whether the decoder is processing a run of ones or a run of zeroes, or walking all the possible values filtering it by the list of change points, we'll use two functions, one for extracting ranges, and one for generating values from ranges. Both functions receive a list representing "the rest of the work to do" in the form of the remainder of the list of change points, and so this is a _little_ bit like using continuation-passing style, or using a Monad to maintain the progress of the calculation. Maybe in Part 2 I'll have learned enough to explain what I mean by that!

Our first function, getRangeFromChangePoints, has to handle some interesting cases. Assuming we are decoding RLE in the range of possible values [X..Y], what happens when our list contains a final value, N, that opens a final range but doesn't explicitly close it? Well, there are two approaches we could take. The more conservative approach is to assume that this was a harmless mistake and close the range [N..N + 1) so that it contains only the value N. (Note that I'm using interval notation in which a square bracket indicates that the range _includes_ the bound specified, and a parenthesis _excludes_ the bound specified). However, there is a problem with this approach: it means we can't generate a range that includes the maximum value, Y! That's no good, so we'll assume that a final range opening with N means that we really want [N..Y] (inclusive). In fact, since we treat ranges as exclusive at the end, this is actually the only way we can generate a range containing Y.

For now, we also assume that running out of values is an error. We're assuming that our caller will handle the termination conditions.

>getRangeFromChangePoints :: [Integer] -> (Integer, Integer, [Integer])
>getRangeFromChangePoints ([]) = error "getRangeFromRLE: no change points in list!"
>getRangeFromChangePoints (a:[]) = (a, max, []) where max = 0xFFF
>getRangeFromChangePoints (a:b:[]) = (a, b - 1, [])
>getRangeFromChangePoints (a:b:ls) = (a, b - 1, ls)

Wow, that's pretty wordy as Haskell code goes, but I kind of like the way the pattern-matching breaks down. Note that in particular it makes the termination conditions obvious. This helps me think about the problem domain, rather than the implementation, in a way that the imperative Ruby code did not.

Next, here is the recursive function to generate values from ranges. We represent a range using the first two values of our tuple, while the third value is a list of the remaining ranges (sort of like our continuation). We handle the termination case, in which we have no more work to do, by just returning a list from our range, while the non-terminating case gets the next range (including the list representing our remaining work) and calls the function again to continue generating the list.

>genValuesFromRange :: (Integer, Integer, [Integer]) -> [Integer]
>genValuesFromRange (first, last, []) = [first..last]
>genValuesFromRange (first, last, to_do) = [first..last] ++ 
>  (genValuesFromRange (getRangeFromChangePoints to_do))

To generate the initial case we use a helper function called valuesFromRLE. In ddition to the change points list, it takes a Boolean value which indicates whether we are to assume that our RLE decoding is initially inclusive or initially exclusive: that is, whether the first value in our first range indicates that the range is starting or ending. If we want it to behave inclusively, we prepend a zero value to create a range starting with zero. Note that this will be harmless if our first range starts with zero, because we'll generate a range like [0..(-1)], which will contain no members.

>valuesFromRLE :: [Integer] -> Bool -> [Integer]
>valuesFromRLE change_points initially_inclusive = genValuesFromRange $ 
>    if initially_inclusive then getRangeFromChangePoints (0 : change_points)
>        else getRangeFromChangePoints change_points

Note that we can evaluate the whole thing, but more interestingly, we can use "take" to produce only the first few elements:

take 16 $ valuesFromRLE rle_change_points True

[0,1,2,144,145,146,257,258,544,560,577,578,1088,3087,3088,3328]

And there you have it. If you like, play with the code. Next time we'll see if we can encode the function IDs back into change points, and confirm the round trip. As always, I appreciate your comments.

Richard or Edna? (And Graham Hutton's Programming in Haskell)

2007-02-15T12:02:00.000-05:00

For some reason, Richard Bird's Introduction to Functional Programming Using Haskell, 2nd Edition, is now listed on Amazon as written by "Edna Bird" (and coauthored by "Wadler" with no first name). Assuming Richard is not actually undergoing a transformation along the lines of Walter Carlos to Wendy, this looks like an error...

Anyway, my copy of Graham Hutton's Programming in Haskell arrived from Amazon. The first remarkable thing about this book is that it is the thinnest book on Haskell I've yet seen. The highest page number is 170. It is even thinner than The C Programming Language, Second Edition.

What does this mean? Well, for one thing, it means the chapters are very brief. It is a beginner's text aimed at novices, even those who may have not programmed (in any language). I would definitely consider using it as a textbook for an introductory programming class. (I have a dream about teaching a programming class to gifted high school students or college first-year students before they have had their minds corrupted by too much Java or C++; we'd learn a little Haskell, Scheme, and Dylan, in that order, and then use our perspective gained to take a brief look at Java, Pascal, and BASIC. In that order, implementing a parser for Pascal and a complete implementation of BASIC. We'd start with this book. But anyway).

The explanation of curried functions (or how "all functions with multiple arguments are curried") is the clearest I've seen. So is the explanation of basic types and classes. His chapter on recursion is also a model of clarity. (I'm pleased to see it goes above and beyond Fibonacci numbers). In general, Hutton seems to be encouraging his readers to think like programmers think, but he doesn't require very many words to get his ideas across.

If you are busy like I am, you don't have time to read a long review, either, so I'll just conclude by saying that this looks like the introductory Haskell text!

Graham Hutton's Book has Shipped

2007-02-08T17:13:00.000-05:00

Amazon tells me that my copy of Graham Hutton's Programming in Haskell has shipped. Excellent!

With the passage of time and the assistance of an acupuncturist, the nerve damage and eye sensitivity left in the wake of my shingles infection has healed, to the point where reading is no longer quite so painful. And I don't have to wear my sunglasses to work on the computer anymore!

So, soon, hopefully back to actually writing some Haskell, as opposed to just reading about it. I have a couple of small real-world programs to try porting from Ruby, which should be educational. More soon!

Haskell Books Piling Up, and Herpes Zoster Ophthalmicus at One Month

2007-01-17T11:42:00.000-05:00

I've received a couple of Haskell-related books -- my Christmas presents to myself. I have only been able to skim these books, but here are my first impressions.

The first book is Chris Okasaki's Purely Functional Data Structures. When I was working on some code to solve Sudoku puzzles in Scheme, I became stymied because in the midst of my efforts to program in a function style, I kept slipping back into an imperative style. This book is the answer to the question "how do you manage data structures when you don't have mutable variables?" The answer, of course, is that you return new data structures based on the old ones. This is not necessarily as inefficient as you might expect, because the new data structure can frequently share content -- sometimes most of the content -- with the previous data structure. Okasaki's book is a model of clarity; on the back it indicates that it can be used for self-study. A lot of texts claim that, but this book seems to actually deliver it. The diagrams are marvelously clear and the learning curve is gentle. The body of the text uses Standard ML with extensions but there is an appendix containing Haskell code. I will have more to say about this book in future postings; I am really looking forward to trying out some of the ideas it contains.

The second book is The Haskell Road to Logic, Maths, and Programming by Kees Doets and Jan van Eijck. This is part of the King's College Texts in Computing series which includes An Introduction to Lambda Calculi for Computer Scientists. That book is thin, while this one is fairly fat; this volume is bursting with exposition (and code) on logic, set theory, and other topics dear to my heart. It looks quite fascinating and again I hope to have more to say about it soon.

It has been approximately a month since I was hit with the first symptoms of herpes zoster ophthalmicus (shingles infection involving the eye). The news is generally very good: there is little long-term damage to my cornea. My opthalmologist can see some slight scarring, but it should continue to improve. But the pain and hyper-sensitivity to light has persisted, and I have found it difficult to return to work because my eye tends to start watering madly or lose focus when I work at the computer for longer than a few minutes. The problem is in the branches of the trigeminal nerve, not the eyeball itself. Nerves heal slowly, so this is unfortunately not an illness for the impatient!

Shingles

2007-01-02T10:48:00.000-05:00

Well, I had great plans for my ten days off -- work on the apartment, organize the office, deep-clean the kitchen, read, and study Haskell!

So much for best-laid plans. Just before Christmas I came down with a shingles infection, which started in my right eye.

Shingles is a reactivation of the herpes zoster or "varicella" virus, the same virus that causes chicken pox. I did a near all-nighter the Monday a week before Christmas, which might not have been too bad, but then the following night we had a sick baby and I was also unable to sleep. That was apparently enough stress to cause the virus to reactivate.

Shingles is painful. I have become intimately familiar with two new types of pain, which I call the blowtorch and the nightstick. The blowtorch is a feeling like my skin is being burned by an open flame and is bubbling. That is the sensation of the blisters forming, although it comes at other random times too. The nightstick is deep pain along the nerves of my face, where they feel like I've been beaten. That produces a tremendous amount of muscle tension in my jaw, and around the base of my skull as well, where large areas are still hyper-sensitive to touch.

Valtrex (an anti-retroviral drug) also has nasty side effects. I got waves of fever and chills, often back-to-back. It also caused nausea, diziness, and strange visions. I'm off the Valtrex now, so thankfully those side effects have gone away.

For most of my ten days off work I was fairly incapacitated: unable to see, unable to read, lying in bed with fever or chills and with strange pains, covered with blisters and scabs. When I got out of bed, I was dizzy, stumbling around the house looking like a crazed sunburned pirate with an eye-patch on.

Anyway, I am now back at work. The scabs are gone, although my face is still visibly splotchy. My right eye is still swollen and there is still some pain. I am still using an antibiotic gel in my eye, which means my right eye is still hazy, so I am not driving yet. I see my regular doctor today and the ophthalmologist again tomorrow. I think the likely outcome is that my vision will not be significantly damaged. It seems like the pain will persist at reduced level for at least a while longer.

Dear reader, I sincerely hope you had a better holiday than mine. And if not, God bless you!

Happy Life Day and Wishing You Lots of Haskell in 2007

2006-12-22T10:20:00.000-05:00

Let's remember the words of Princess Leia, in the Star Wars Holiday Special:

We celebrate a day of peace. A day of harmony. A day of joy we can all share together joyously. A day that takes us through the darkness. A day that leads us into might. A day that makes us want to celebrate the light. A day that brings the promise that one day, we'll be free to live, to laugh, to dream, to grow, to trust, to love, to be.

Happy Life Day, everyone! Or whatever tradition you celebrate.

I am not planning to work on any more entries until early January, so I just wanted say that I am extremely grateful for all the comments and suggestions I've received on my blog entries. With two babies at home I don't get much time to study textbooks or tutorials, although I try, and I don't get much dedicated coding time. But the suggestions and concrete examples have helped me make good use of what free time I do have. Thanks to all of you for your support learning this exciting language!

From Bits to Cells: Simple Cellular Automata in Haskell, Part Two

2006-12-19T03:22:00.000-05:00

Let's get back to our CA generator. Literate Haskell follows:

Last time we defined a function to generate the next state of a given cell 
in our cellular universe, given a rule number and a tuple consisting of 
the current state of the cell to the left, the cell itself, and the cell 
to the right.

>import Data.Bits

>genNextBit :: Int -> ( Bool, Bool, Bool ) -> Bool
>genNextBit rulenum ( left, center, right ) = rulenum `testBit` idx
>    where idx = ( if left then (4::Int) else (0::Int) ) .|. 
>           ( if center then (2::Int) else (0::Int) ) .|. 
>           ( if right then (1::Int) else (0::Int) )

Recall that we can use automatic currying to make a rule-applying function 
like so:

>rule_30 = genNextBit 30

We can ask GHCi for the type:

:type rule_30

rule_30 :: (Bool, Bool, Bool) -> Bool

I've put it off while I work on the rules, but it is time to figure out
how to actually represent our CA universe. Let's start by using a list.
I know that I'm going to write a number of inefficient functions, and
do evil things like take the length of lists a lot, but let's suspend all 
concerns about efficiency over to a future discussion and consider this 
purely a proof-of-concept.

Our inital universe at time zero has one cell set to True:

>initial_universe = [True]

But that isn't quite the right representation for the universe, because 
it implies that our whole universe is one cell in size. We can't even 
apply our rule once because there is no left cell and right cell! 
Really, we want to pretend that we have an _infinite_ universe; at 
time zero, all the cells to the left and right hold False. Remember, 
Haskell is so powerful that it can traverse an infinite list in only 
0.0003 seconds! Well, if you don't evaluate the whole thing, that is.
Taking advantage of lazy evaluation, you can define all kinds of 
infinite structures. This construct will give us an infinite list of 
False values:

>allFalse :: [Bool]
>allFalse = False : allFalse

We don't want to evaluate allFalse, but we can partially evaluate it 
using a function like take. So can we represent our universe like this?

>genInfiniteUniverse :: [Bool] -> [Bool]
>genInfiniteUniverse known_universe = allFalse ++ known_universe ++ allFalse

Let's try it:

take 10 ( genInfiniteUniverse initial_universe )

[False,False,False,False,False,False,False,False,False,False]

Nope! Since the left-hand side of the universe is infinite, we will never
reach the middle element, no matter how far we travel from the start of the list! 
That's no good. However, we can do it another way. We'll allow our universe to
be expanded on demand on the left and right sides:

>expandUniverse :: Int -> [Bool] -> [Bool]
>expandUniverse expand_by known_universe = 
>   ( take expand_by allFalse ) ++ known_universe ++ ( take expand_by allFalse )

expandUniverse 3 initial_universe

[False,False,False,True,False,False,False]

We can use the expandUniverse function to expand our initial universe out to
a standardized width before we start applying the rules.

First, here's a routine to stringify a universe for display:

>boolToChar :: Bool -> Char
>boolToChar True = '#'
>boolToChar False = ' '

>stringifyUniverse :: [Bool] -> String
>stringifyUniverse ls = map boolToChar ls

Now our infrastructure is in place, so let's figure out how to apply our
generator rule. We know that we want to start with our initial universe. Let's
expand it to a fixed size. This will give us enough elements to start making
left/center/right tuples out of each consecutive set of three cells. Each tuple 
is then used to look up the next state of the cell at the center; this will 
become an element in our next universe. Then we move to the next cell (not 
three cells down). This means that the tuples overlap.

Let's make the tuples. We have to do some thinking here and consider all the
cases; the behavior isn't immediately obvious. The following almost works:

universeToTuples :: [Bool] -> [(Bool, Bool, Bool)]
universeToTuples universe | length universe >= 3 =
   ( universe !! 0, universe !! 1, universe !! 2 ) :
   universeToTuples ( tail universe )
universeToTuples universe = []

universeToTuples [False, True, True, True, False]

[(False,True,True),
(True,True,True),
(True,True,False)]

But it isn't quite right; it leaves off the end cases; when we apply our rules,
the intermediate representation of the universe as a list of tuples to look up
cell mappings will shrink. We actually want the following tuples:

[(False,False,True),
(False,True,True),
(True,True,True),
(True,True,False),
(True,False,False)]

where the first element of the list is considered as if it was just to the
right of an implied False, and the last element is considered as if it was
just to the left of another implied False. This sounds like another place we
can use our universe expander:

>universeToTuples :: [Bool] -> [(Bool, Bool, Bool)]
>universeToTuples [] = []
>universeToTuples universe = tupleize $ expandUniverse 1 universe
>   where
>       tupleize xs = 
>            if length xs > 3 then tuple3 xs : tupleize ( tail xs )
>               else [ tuple3 xs ]
>       tuple3 xs = ( xs !! 0, xs !! 1, xs !! 2 )

Why did I write it that way? Well, I tried to write tupleize using guards, 
special-casing length xs > 3 followed by an unguarded case for all other 
possibilities, but GHC didn't like it -- it told me I had non-exhaustive 
patterns. There is probably a smarter way to write this, but note that we
definitely don't want this version:

universeToTuples universe = ( xs !! 0, xs !! 1, xs !! 2 ) 
    : universeToTuples ( tail xs )
       where xs = expandUniverse 1 universe

In that version, the universe keeps expanding as we walk down the list,
and we never get to the end!

OK, now that we have our tuples, we want to turn them into our new universe,
given a cellular rule number:

>tuplesToUniverse :: Int -> [(Bool, Bool, Bool)] -> [Bool]
>tuplesToUniverse rule [] = []
>tuplesToUniverse rule (tup:tups) = genNextBit rule tup : tuplesToUniverse rule tups

Note that we don't have to explicitly take the tail since we provide a name
for it in the pattern. We're ready to define our genUniverses function that
applies a given CA rule. We can express a given generation like this:

>nextUniverse :: Int -> [Bool] -> [Bool]
>nextUniverse rule universe = tuplesToUniverse rule $ universeToTuples universe

Now, let's generalize it:

>genUniverses :: Int -> Int -> Int -> [[Bool]]
>genUniverses rule width count = take count 
>   ( iterate ( nextUniverse rule ) ( expandUniverse ( width `div` 2 ) initial_universe ) )

(You could also use a fold, and I'm sure there are lots of other ways to do it,
but iterate seems to work fine).

And now, witness the unfolding of a universe! Note that the parameters that
go to genUniverses are the rule number, the width for display, and the number
of generations:

putStr $ unlines $ map stringifyUniverse $ genUniverses 222 19 10

          #
         ###
        #####
       #######
      #########
     ###########
    #############
   ###############
  #################
 ###################
 
In general, a width of twice the number of generations - 1 will show all the 
transitions we are interested in; you could consider the diagonal area above 
to be the "light cone" of events causally connected to that single point (although
some rules will generate True cells outside of that "light cone" based on the
other False values in the initial universe). Let's make a helper function to 
choose a width for us:

>showRule rule gens = 
>   putStr $ unlines $ map stringifyUniverse $ 
>       genUniverses rule ( gens * 2 - 1 ) gens

Let's try a few of the other rules:

showRule 252 15
              #
              ##
              ###
              ####
              #####
              ######
              #######
              ########
              #########
              ##########
              ###########
              ############
              #############
              ##############
              ###############

showRule 78 15
               #
              ##
             ###
            ## #
           ### #
          ## # #
         ### # #
        ## # # #
       ### # # #
      ## # # # #
     ### # # # #
    ## # # # # #
   ### # # # # #
  ## # # # # # #
 ### # # # # # #

And finally, my all-time favorite, which simulates a Sierpinski gasket:

showRule 82 32
                                #
                               # #
                              #   #
                             # # # #
                            #       #
                           # #     # #
                          #   #   #   #
                         # # # # # # # #
                        #               #
                       # #             # #
                      #   #           #   #
                     # # # #         # # # #
                    #       #       #       #
                   # #     # #     # #     # #
                  #   #   #   #   #   #   #   #
                 # # # # # # # # # # # # # # # #
                #                               #
               # #                             # #
              #   #                           #   #
             # # # #                         # # # #
            #       #                       #       #
           # #     # #                     # #     # #
          #   #   #   #                   #   #   #   #
         # # # # # # # #                 # # # # # # # #
        #               #               #               #
       # #             # #             # #             # #
      #   #           #   #           #   #           #   #
     # # # #         # # # #         # # # #         # # # #
    #       #       #       #       #       #       #       #
   # #     # #     # #     # #     # #     # #     # #     # #
  #   #   #   #   #   #   #   #   #   #   #   #   #   #   #   #
 # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #

Wow!

Followup: I had mentioned that my code had a bug, because some pictures, such as this one:

showRule 29 11
          #
######### ###########
#         #
######### ###########
#         #
######### ###########
#         #
######### ###########
#         #
######### ###########
#         #

look different than the way Wolfram's book and web site shows them, which is like this:

          #
######### ###########
          #
######### ###########
          #
######### ###########
          #
######### ###########
          #
######### ###########
          #

After a little investigation this seems to be because Wolfram's implementation wraps around; the left neighbor of the leftmost cell of a given universe is taken from the rightmost cell, and vice-versa, while my implementation pretends that there is always more empty space available to the left and right.

Whether you consider this a bug or not is up to you. The wraparound behavior is probably considered more "canonical." You can compare the results from my program to the pictures at Wolfram's MathWorld site here. If you replace my universeToTuples function with this one:

universeToTuples :: [Bool] -> [(Bool, Bool, Bool)]
universeToTuples [] = []
universeToTuples universe = tupleize $ wrapUniverse universe
   where
       wrapUniverse xs =  ( last xs ) : ( xs ++ [ head xs ] )
       tupleize xs = 
           if length xs > 3 then tuple3 xs : tupleize ( tail xs )
               else [ tuple3 xs ]
       tuple3 xs = ( xs !! 0, xs !! 1, xs !! 2 )

you will get the wraparound behavior.

Thanks for reading and as always, I appreciate your comments.

From Bits to Cells: Simple Cellular Automata in Haskell, Part One

2006-12-17T17:37:00.000-05:00

The little Haskell toy I wrote to simulate a dot-matrix printhead was useful in one sense: it helped me learn a little more Haskell! I couldn't help noticing that the results look like the transformations you get when applying simple cellular automata rules. So my next experiment is to implement those rules, and see what else I can learn from the results.

What follows is Literate Haskell, but there is no main program to run; it is for you to experiment with interactively, if you like.

Some Haskell code to implement simple cellular automata (CA) rules:
part one, round one.

The simplest type of one-dimensional CA behaves as follows: 

- a cell may be on or off (one or zero). 

- time ticks by in discrete intervals.

- at each tick, the state of each cell is updated using a function that
maps the current state of the cell to the left, the cell itself, and
the cell to the right to the new cell value.

Because this value-generating function depends on 3 bits of input, a 
given CA rule actually consists of 2^3 = 8 possible mappings. The 
mappings can be represented by the binary values 0b000 to 0b111 
(decimal 0..7). By Wolfram's numbering convention for these simple 
CA, we actually count down from 7 to 0. So, let's say we have a rule 
that maps each possible set of left, center, and right values:

0b111, 0b110, 0b101, 0b100, 0b011, 0b010, 0b001, 0b000

to the new cell value:

0b0, 0b0, 0b0, 0b1, 0b1, 0b1, 0b1, 0b0

We can treat the resulting number, in this case 0b00011110, as the
rule number. This is rule 30 in Wolfram's schema; there are 2^8, 
or 256, possible rules, numbered from 0 to 255.

First, let's make a function that, given a rule number and three
values (left, center, and right), returns the new cell state. We
turn the three values into an index to look up the appropriate bit
in the rule number.

>import Data.Bits

>genNextBit :: Int -> ( Bool, Bool, Bool ) -> Bool
>genNextBit rulenum ( left, center, right ) = rulenum `testBit` idx
>    where idx = ( if left then (4::Int) else (0::Int) ) .|. 
>           ( if center then (2::Int) else (0::Int) ) .|. 
>           ( if right then (1::Int) else (0::Int) )

Hmmm... it is lacking a certain elegance, and I don't quite like
the way the indentation rules work in this case, but let's test it 
with a function that generates the 8 rule indices in the form of tuples:

>genRuleIndices :: [( Bool, Bool, Bool )]
>genRuleIndices = [ ( (val `testBit` 2), (val `testBit` 1),
>                   ( val `testBit` 0) ) | val <- [(7::Int), 
>                   (6::Int)..(0::Int)] ]

Now if we write:

genRuleIndices

we get:

[(True,True,True),
(True,True,False),
...
(False,False,True),
(False,False,False)]

and if we write:

map (genNextBit 30) genRuleIndices

this expression curries us a function (mmm... curry!) which takes 
a starting state and applies rule 30, then feeds it the possible 
starting states. The result is:

[False,False,False,True,True,True,True,False]

That looks like the bit pattern for rule 30.

Just for fun, let's confirm by making a function that will
translate a list of output bit values back into a rule number.
The signature should look like this:

sumBitVals :: [Bool] -> Int

And we want the list

>test_bit_vals = [False,False,False,True,True,True,True,False]

to map back to 30. Take a shot at it yourself; you might find
that the result is instructional I'll wait.

(Musical interlude).

Did you try it? Let's look at some possible implementation strategies.
We could make a list of the powers of two and then do some list 
manipulation to get the powers of two that correspond to our one-bits
summed up:

>powers_of_two_8_bits = reverse ( take 8 (iterate (2 *) 1) )

[128,64,32,16,8,4,2,1]

(An aside: since this is generated by a function that takes no 
parameters at runtime, it would seem like a sufficiently smart 
compiler could generate this list and stick it in the resulting 
program so that no run-time calculation is required to generate 
it. Does GHC do this? I don't know.)

Anyway, our implementation. We can tuple up our powers of two with
our bit values:

>tups = zip powers_of_two_8_bits test_bit_vals 

[(128,False),(64,False),(32,False),(16,True),(8,True),(4,True),(2,True),(1,False)]

Then we can turn this back into a list of only the powers of two that are 
"on," and sum the results:

sum (map (\ tup -> if snd tup then fst tup else 0) tups )

30

It seems like this should be simpler still. I looked in the standard 
library for a function to filter one list using a list of boolean 
values as a comb. Let's write one:

>combListWithList :: [a] -> [Bool] -> [a]
>combListWithList [] [] = []
>combListWithList ls comb = 
>   if (head comb) then (head ls) : combListWithList (tail ls) (tail comb)
>       else combListWithList (tail ls) (tail comb)

combListWithList powers_of_two_8_bits test_bit_vals

[16,8,4,2]

That seems good, although it doesn't express the idea that the lists
have to be the same length. It still seems amazing to me that I can 
reel off functions like that in Haskell and have them work right the 
first time! Now we can produce our final function:

>sumBitVals :: [Bool] -> Int
>sumBitVals ls = sum $ combListWithList powers_of_two_8_bits ls

sumBitVals test_bit_vals

30

There is probably an elementary way to implement the above function
using zipWith instead of my combList, but I'll leave that to you;
leave a comment if you figure it out!

As another aside, here is another function I came up with to generate 
this bit vals; it doesn't rely on a specific length.

>foldBitVals :: [Bool] -> Int
>foldBitVals ls = snd (foldr 
>   (\ flag tup -> if flag then ((fst tup) * 2, (snd tup) + (fst tup)) 
>                           else ((fst tup) * 2, snd tup) )
>   (1, 0) ls )

foldBitVals test_bit_vals

30

Take a moment to understand the above function; it is a little strange.
I perform a fold using a tuple. The first element is the power of two, 
so it keeps track of our place in the list, and the second is an 
accumulator as we add up our values. This is a trick for stashing
a state that is more complex than a single value into a fold.

Anyway, that was a long diversion, so let's end for now. Next time we'll look at ways to represent our CA universe as it evolves by applying our rules. As always, your comments are welcome!

The Revised Dot-Matrix Printhead

2006-12-14T14:23:00.000-05:00

It looks like this blog has been unceremoniously removed from Planet Scheme. I guess that's only fair, since I haven't written anything specifically about Scheme in a while. Best of intentions, and all that. This blog probably belongs on "Planet Programming Language Dilettante."

Anyway, I received some helpful feedback on the short program I wrote to print bitmaps of binary numbers. Jason Creighton in particular took a shot at a rewrite, and the result as highly enlightening. I also recieved two specific pieces of advice: use short function names, and don't write a comprehension like [a | a <- [a..b]] when you can just write [a..b]. Oops. Check, and thanks!

(Semi) or (Ill) Literate Haskell follows:

Haskell Binary Printhead Toy, Second Round

>import Data.Bits

Our functions to generate lists of signed and unsigned integers of
numbits length, revised with names as suplied by Jason and error-
catching as supplied by yours truly:

>unsignedInts :: Int -> [Int]
>unsignedInts bits | (1 <= bits) && (bits <= 16) = 
>   [(0::Int)..(bound::Int)] 
>   where bound = 2 ^ bits - 1
>unsignedInts bits = error "expected a value from 1 to 16"

>signedInts :: Int -> [Int]
>signedInts bits | (1 <= bits) && (bits <= 16) = 
>   [(- (bound::Int)) - 1..(bound::Int)] 
>   where bound = 2 ^ ( bits - 1 ) - 1
>signedInts bits = error "expected a value from 1 to 16"

Jason came up with a considerably simpler way to map the bits of
the binary numbers to the characters for printing:

>boolToChar :: Bool -> Char
>boolToChar True = '#'
>boolToChar False = ' '

I'm adopting that suggestion enthusiastically, since I don't think
code can get much simpler than that!

Jason then proceeded to turn my dog food into a much more flavorful 
wafter-thin after-dinner mint, leaving me struggling to understand
just what he did:

>bitPicture :: (Int -> [Int]) -> Int -> [Char]
>bitPicture intGen bits = unlines $ map stringAtIndex (reverse [0..(bits-1)])
>  where
>    stringAtIndex = map boolToChar . bitsAtIndex
>    bitsAtIndex idx = [ testBit n idx | n <- intGen bits ]

Wow. First off, Jason has supplied a type signature which expresses 
what the function actually _does_. The appropriate integer generator 
(the signed or unsigned version) comes in as a parameter; that's what 
(Int -> [Int]) means. We next get an integer argument (the number of 
bits), and finally, we spit out a list of chars.

Jason proceeds to use a couple of where clauses to set up some 
simplifying expressions. Let's look at the first one:

StringAtIndex = map boolToChar . bitsAtIndex

OK, this is slightly mind-twisting right off the bat. In the world 
of C and Java you can't write things like that. The dot is function 
composition expressed naturally; instead of something like

stringOfBoolsFromBitsAtIndex idx = map boolToChar (bitsAtIndex idx)

we can just get Haskell to chain the functions together for us. 
No fuss, no muss. But this function makes a forward reference to 
bitsAtIndex, which we haven't seen yet (completely illegal in C 
and Java). Let's make sure we understand what bitsAtIndex does:

bitsAtIndex idx = [ testBit n idx | n <- intGen bits ]

That's definitely more dense than the way I wrote it (and that's a 
good thing). To break down the list comprehension, the expression on 
the right hand side of the vertical bar says that we feed the supplied 
integer generator function the number of bits to use. That gives us a 
list. From that list we will draw our "n"s and test bit idx on them. 
By doing it this way, Creighton has pulled an act of Haskell sleight-
of-hand: instead of generating the bitmaps for each integer value, 
like I did, and then using "transpose" to rearrange them, this version 
accesses the "columns" of the table directly! With those two 
expressions, we've got our string representing all the bits at a 
given index _for the whole supplied set of integers_.

Wow. I feel like an audience member watching a magician smash up my 
watch and then give it back to me rebuilt as a marvelous whirring 
gyroscope.

There's more, but this part is relatively simple:

bitPicture intGen bits = unlines $ map stringAtIndex (reverse [0..(bits-1)])

We already know what unlines does; it turns our list of strings into a
properly line-broken string. We've just described how stringAtIndex works.
and map stringAtIndex (reverse [0..(bits-1)[) just feeds stringAtIndex a
set of indices mapped from high to low, so that our most significant bit
comes out leftmost. But what does "$" do?

My reference at zvon.org says this is the "right-associating infix 
application operator (f $ x = f x), useful in continuation-passing style."
I'm not sure I fully understand, and I'm not going to go into the meaning
of "continuation-passing style" right now, but I guess it saves us from 
having to write:

unlines $ map (stringAtIndex (reverse [0..(bits-1)]))

to get the right order of operations, which is nice. So I'll try to 
incorporate it into my own Haskell.

Anyway, let's try it. We need to drive the function:

>main :: IO ()
>main = do
>   print "Unsigned values (6 bits)"
>   putStr $ bitPicture unsignedInts 6 
>   print "Signed values (6 bits)"
>   putStr $ bitPicture signedInts 6

After using GHCi's :cd and :load command to read this file, just
type:

main

"Unsigned values (6 bits)"
                                 ################################
                 ################                ################
         ########        ########        ########        ########
     ####    ####    ####    ####    ####    ####    ####    ####
   ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##
  # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
"Signed values (6 bits)"
 ################################
                 ################                ################
         ########        ########        ########        ########
     ####    ####    ####    ####    ####    ####    ####    ####
   ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##
  # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #

Excellent. I laughed; I cried; I learned something today. I hope you did, too. Thanks, Jason! And thanks to the other people who commented!

Followup: for those following along the discussion in the comments, here is an alternate implementation of the bitPicture function:

bitPicture intGen bits = unlines $ map stringAtIndex $ [bits - 1, bits - 2..0]
  where
    stringAtIndex = map boolToChar . bitsAtIndex
    bitsAtIndex idx = map (flip testBit idx) (intGen bits)

Note that using [bits - 1, bits - 2..0] in the first line allows us to avoid the list reversal, so that seems like a clear win. The method of expressing bitsAtIndex above is one of several that were suggested. The idea behind the flip is that the return value of intGen should become the first parameter to bitsAtIndex, not the second. You can also express this by forcing stringAtIndex to be treated as an infix operator:

bitsAtIndex idx = map (`testBit` idx) (intGen bits)

Both of these alter the behavior of Haskell's automatic currying so that it replaces the second parameter instead of the first, leaving the first as the sole parameter to the resulting curried function; in Common Lisp, you might do this explicitly using rcurry. And don't forget the original, using a list comprehension:

bitsAtIndex idx = [ testBit n idx | n <- intGen bits ]

Assuming there is not a specific concern about efficiency, it seems like the choice between these versions might be a matter of style. Thanks again to everyone who made suggestions.

The Dot-Matrix Printhead: a Haskell Toy

2006-12-12T12:20:00.000-05:00

The body of this article is a literate Haskell program. You can extract the text, then save it as a file with the extension .lhs, then execute it using GHCi.

This is a Haskell toy to visualize twos-complement binary numbers.
In my previous articles on the subject of integer division, I alluded
two underflow and overflow and the "weird number" -- well, now you
can see them! 

Almost 30 years ago I wrote code on my Radio Shack TRS-80 to make my 
dot-matrix printer spit out bitmaps of binary numbers, which made 
pretty recursive patterns. This program commemorates that long-ago 
geekery from my early teenage hacking days.

First, we need the bits library:

>import Data.Bits

We'll also need the list library later:

>import List

Let's simulate n-bit binary number in both a signed and unsigned
interpretation. Given a number of bits, we want a function to make
a list of the possible values. For example, in unsigned form 8 bits 
will give us a list of the values 0..255; in signed form, it will be 
an asymmetrical list from -128..127. Note that this function generates
the whole list, so if you give it a numbits value higher than, say,
16, you might regret it.

Our calculation fails for values of numbits <= 0, so we put in a
guard case for that. We also want to discourage creating very large
lists, so we put in a guard case for numbits > 16.

>gen_n_bit_nums_unsigned numbits | numbits <= 0 = []
>gen_n_bit_nums_unsigned numbits | numbits > 16 = error "too many bits!"
>gen_n_bit_nums_unsigned numbits = 
>   [ n | n <- [(0::Int)..((2::Int)^numbits - 1)] ]

>gen_n_bit_nums_signed numbits | numbits <= 0 = [] 
>gen_n_bit_nums_signed numbits | numbits > 16 = error "too many bits!"
>gen_n_bit_nums_signed numbits = 
>   [ n | n <- [-(2::Int)^(numbits - 1)..((2::Int)^(numbits - 1) - 1)] ]

To test this we can execute:

gen_n_bit_nums_unsigned 4
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

gen_n_bit_nums_signed 4
[-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7]

That looks about right.

Now we want a function to access the bits of those numbers from most 
significant to least significant and build a list of corresponding 
boolean values. This would be expressed more naturally if EnumFromTo
operated descending sequences. I'm sure there's a better way, but for
now I will just reverse the resulting list:

>rightmost_bits num_bits val | num_bits > 16 = error "too many bits"
>rightmost_bits num_bits val | num_bits <= 0 = error "too few bits"
>rightmost_bits num_bits val = 
>   reverse [ testBit (val::Int) bit_idx | bit_idx <- [0..(num_bits - 1)] ]

Once we have a function which will do it with one number, doing it with a 
whole list of numbers is very easy. We will make a curried function and
use map. Currying in Haskell is very easy, which makes sense given that
the operation, "to curry" and the language, Haskell, are both named after
Haskell Curry!

Our rightmost_bits function takes two arguments, but we want to make a 
new function which we can hand off as an argument to map, along with a 
list. This new function will only take one parameter. We can ask GHCi 
what it thinks the type of the rightmost_bits function is:

:type rightmost_bits

It says:

rightmost_bits :: Int -> Int -> [Bool]

We can make a new function out of it by doing partial application:
instead of supplying all its arguments, we just supply the first one.

gen_rightmost_bits 4

If you do this in GHCi, you'll get an error message because the
result is not printable (GHCi can't apply show to the result). 
But you can bind it:

let bit_generator_4 = gen_rightmost_bits 4

And then ask GHCi what its type is:

:type bit_generator_4
bit_generator_4 :: [Int] -> [[Bool]]

Take a moment to make sure you understand what we've done here: 
Haskell has made us a curried function which takes a list of values 
instead of a single value, and generates a list of lists. This
seems pretty close to magic! Let's make another function that
takes the number of bits and a list, generates the curried
function, then maps the list to the curried function:

>gen_rightmost_bits num_bits ls = 
>   map (rightmost_bits num_bits) ls

As you can see, working with curried functions is completely
effortless in Haskell. Here's a general function to generate
a list of all the bit values for unsigned numbers of num_bits 
size:

>gen_all_bits_unsigned num_bits = 
>   gen_rightmost_bits num_bits (gen_n_bit_nums_unsigned num_bits)

>gen_all_bits_signed num_bits = 
>   gen_rightmost_bits num_bits (gen_n_bit_nums_signed num_bits)

If we execute:

gen_all_bits_unsigned 4

We get back the following (I have reformatted the output for clarity):

[[False, False, False, False], 
[False, False, False, True], 
[False, False, True, False],
[False, False, True, True],
[False, True, False, False],
[False, True, False, True],
[False, True, True, False],
[False, True, True, True],
[True, False, False, False],
[True, False, False, True],
[True, False, True, False],
[True, False, True, True],
[True, True, False, False],
[True, True, False, True],
[True, True, True, False],
[True, True, True, True]]

This is recognizably a table of the unsigned binary values 0..15.
This approach doesn't seem very "Haskell-ish" yet -- instead of 
generating the combinations as needed, I'm producing them all 
ahead of time. It also feels to me like I'm pushing uphill on 
the syntax, and having to use parentheses to force the order 
of evaluation. We can think more about that later, but let's 
get our pretty-printing working first.

How can I turn all those boolean values into a string I can print?
Well, we can take advantage of the fact that in Haskell, strings can
be treated as lists, and the same methods apply. This is not efficient,
but it allows us to use some of the standard functional techniques.
One of these is "fold."

Fold is a technique for boiling down a list into some kind of summary
form. Just what form this summary takes is up to you, since you can
supply your own function and a starting value. For example, to sum
the elements in a list, I could use foldl like this:

foldl (\ x y -> x + y) 0 [0, 1, 2]
 
The first parameter to foldl is a function. In this case I'll use
a lambda expression, which gives me a function I won't bother to
name. The second paramter is the starting value. The starting value
and the next item in the list are repeatedly passed to the function,
which accumulates a value. In this case, the final result is 3.

I can give foldl an empty string as the starting accumulator value
and my function can concatenate strings onto it: 

>stringify_vals =
>   foldl (\ x y -> if y then x ++ "#" else x ++ " ") ""

Now you might want to try to apply our list of lists to this
function:

stringify_vals (gen_all_bits_unsigned num_bits)

If you do that, though, you'll get a type error like this:

"Couldn't match expected type `Bool' against inferred type `[Bool]'"

The reason can be seen if we examine the types:

:type (gen_all_bits_unsigned 4) :: [[Bool]]
(gen_all_bits_unsigned 4) :: [[Bool]]

:type stringify_vals
stringify_vals :: [Bool] -> [Char]

We have a list of lists of bools, but we want to feed our
stringification function a list of bools. To apply each
element of (gen_all_bits_unsigned 4) to our stringification
function, we can use map again:

>stringify_all_unsigned_vals num_bits =
>   map stringify_vals (gen_all_bits_unsigned num_bits)

>stringify_all_signed_vals num_bits =
>   map stringify_vals (gen_all_bits_signed num_bits)

This will give us a list of strings, one for each list of boolean
values. (I've reformatted the output).

["    ",
"   #",
"  # ",
"  ##",
" #  ",
" # #",
" ## ",
" ###",
"#   ",
"#  #",
"# # ",
"# ##",
"##  ",
"## #",
"### ",
"####"]

That's nice: we can start to see our recursive structure! But
we really want that value to be turned into a single printable
string. To achieve that, we can use the unlines function.

>prettyprint_unsigned num_bits =
>   unlines (stringify_all_unsigned_vals num_bits)

>prettyprint_signed num_bits =
>   unlines (stringify_all_signed_vals num_bits)

When we interpret 

prettyprint_unsigned 3

we see a single string with newline characters escaped, like so:

"   \n  #\n # \n ##\n#  \n# #\n## \n###\n"

This will give the results we want when we pass it to putStr, like so:

putStr (prettyprint_unsigned 8)

        #
       #
       ##
      #
      # #
      ##
      ###
     #
     #  #
     # #
     # ##
     ##
     ## #
     ###
     ####

    (etc.)
    
Hmmm. That's nice, but it would be really cool if the results
were rotated, so that we could see what it would look like if
a printhead moving horizontally was printing out these values.
To do this, we can actually start with our intermediate list of
lists. If our four-bit numbers give us

[[False, False, False, False], 
[False, False, False, True], 
[False, False, True, False],
etc.

we can see the values the other way using transpose. Let's write
rotated versions of gen_all_bits_unsigned and gen_all_bits_signed:

>gen_all_bits_unsigned_rot num_bits = 
>   transpose
>   (gen_rightmost_bits num_bits (gen_n_bit_nums_unsigned num_bits))

>gen_all_bits_signed_rot num_bits = 
>   transpose
>   (gen_rightmost_bits num_bits (gen_n_bit_nums_signed num_bits))

And make a new stringify function to play with:

>stringify_all_unsigned_vals_rot num_bits =
>   map stringify_vals (gen_all_bits_unsigned_rot num_bits)

>prettyprint_unsigned_rot num_bits =
>   unlines (stringify_all_unsigned_vals_rot num_bits)

Now

putStr (prettyprint_unsigned_rot 6)

will give us:

                                 ################################
                 ################                ################
         ########        ########        ########        ########
     ####    ####    ####    ####    ####    ####    ####    ####
   ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##
  # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
 
Now that's what I'm talking about!
 
We can use the unsigned version to see the interesting transition
point between negative and positive values:
 
>stringify_all_signed_vals_rot num_bits =
>   map stringify_vals (gen_all_bits_signed_rot num_bits)

>prettyprint_signed_rot num_bits =
>   unlines (stringify_all_signed_vals_rot num_bits)

Now

putStr (prettyprint_signed_rot 6)

will give us:

 ################################
                 ################                ################
         ########        ########        ########        ########
     ####    ####    ####    ####    ####    ####    ####    ####
   ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##
  # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #

Now let's give our program a main function using the IO monad and
have it print out several of our results:

>main :: IO ()
>main = do
>   print "Unsigned values (8 bits)"
>   putStr (prettyprint_unsigned 8) 
>   print "Signed values (8 bits)"
>   putStr (prettyprint_signed 8) 
>   print "Unsigned values (6 bits) rotated"
>   putStr (prettyprint_unsigned_rot 6) 
>   print "Signed values (6 bits) rotated"
>   putStr (prettyprint_signed_rot 6)

After using GHCi's :cd and :load command to read this file, just
type:

main

I would invite any readers to play around with the code, and if you can make it more concise and/or more "Haskellish," please leave a comment.

Now if only we could get Haskell to generate the appropriate sound! My dot-matrix printer was loud. But that's a task for another day.

NOTE: there is a followup aticle to this one which develops the code further; see http://praisecurseandrecurse.blogspot.com/2006/12/revised-dot-matrix-printhead.html

Also, make sure to take a look at the comments on both this posting and the followup.

The Divisive Aftermath

2006-12-08T12:31:00.000-05:00

Antti-Juhani pointed out to me that Haskell provides the quot and rem pair of operations in addition to div and mod. The difference is that while both satisify the identity involving division, multiplication, and the remainder, div and mod round down (towards -infinity), while quot and rem round towards zero (truncating the fractional part).

That's great! (Besides the fact that I displayed my ignorance in public, that is). It means I really can use GHCi to model my functions for testing! And I was getting worked up to write a C version of Plauger's div which rounded away from zero for negative quotients so I could have some guaranteed-consistent behavior. Instead I can use the C standard function div and Haskell's quot and rem.

So, this sort of begs the question: is there a good reason to prefer one method of integer division rounding to another? Yes. It comes down to this question: do you want your algorithms to behave smoothly across the origin, or to behave symmetrically around the origin?

Let's briefly consider some Haskell code for mapping a range of fractions onto a range of integers again.

let gen_nths denom = [ (numer, denom::Int) | numer <- [ (-denom::Int)..(denom::Int) ] ]

let div_map m1 m2 = map (\ tup -> fst tup * ( ( (m2::Int) - (m1::Int) ) `div` 2 ) `div` snd tup )

div_map (-10) 10 ( gen_nths 3 )

[-10, -7, -4, 0, 3, 6, 10]

Notice something about those values: the distances between them follow a consistent pattern. Reading the list left to right, we have distances of 3, 3, 4, 3, 3, 4. This pattern repeats. It is smooth across the origin.

Now let's change our div_map function to use quot and rem:

let quot_map m1 m2 = map ( \tup -> fst tup * ( ( (m2::Int) - (m1::Int) ) `quot` 2) `quot` snd tup )

quot_map (-10) 10 ( gen_nths 3 )

[-10, -6, -3, 0, 3, 6, 10]

Looking at the differences between values, from left to right, we find that they are 4, 3, 3, 3, 3, 4. The function is symmetric around the origin.

Does this matter in practice? Of course! Let's say that we have a mapping using a non-origin-crossing version of our quot_map function:

let gen_non_negative_nths denom = [ (numer, denom::Int) | numer <- (0::Int)..(denom::Int) ] ]

let quot_map_2 m1 m2 = map ( \tup -> fst tup * ( (m2::Int) - (m1::Int) ) `quot` snd tup )

quot_map_2 0 20 ( gen_non_negative_nths 6 )

[0, 3, 6, 10, 13, 16, 20]

Shiny. The intervals go 3, 3, 4, 3, 3, 4. But if we shift the values:

let gen_non_positive_nths denom = [ (numer, denom::Int) | numer <- [ (-denom::Int)..(0::Int) ] ]

quot_map_2 0 20 ( gen_non_positive_nths 6 )

[-20, -16, -13, -10, -6, -3, 0]

The intervals go 4, 3, 3, 4, 3, 3 -- they are backwards. In other words, the effect of integer rounding on the values of the codomain changes if you shift the domain of the denominator across the origin: the ordering of the pattern is reversed.

If we do the same thing using div:

let div_map_2 m1 m2 = map (\ tup -> fst tup * ( (m2::Int) - (m1::Int) ) `div` snd tup )

div_map_2 0 20 ( gen_non_negative_nths 6 )

[0, 3, 6, 10, 13, 16, 20]

div_map_2 0 20 ( gen_non_positive_nths 6 )

[-20, -17, -14, -10, -7, -4, 0]

we get a pattern of intervals (the effect of rounding) which remains the same: 3, 3, 4, 3, 3, 4.

Now, smoothness across the origin is is what I want, at least for the kinds of functions I am working on now. But your problem domain may lend itself to writing functions which involve rotations, or mapping values across the origin: in that case, you're going to want the symmetry. The important thing is to know what strategy you are using and apply it consistently. I'm really impressed that Haskell give me so many interesting options.

The Division Bell Tolls for Me, Part Four (Conclusion)

2006-12-07T19:51:00.001-05:00

Well, this was initially going to be a three-part article, but things have become more interesting. The situation is not unlike picking up a log in the forest and finding all kinds of nifty crawlies living under it. "Interesting" to certain geeky people like myself, at least! It's about to get geekier. If you are allergic to ANSI or ISO standards, you'd better stop reading now. But I claim the payoff is worth it, if you can make it through to the end. At least, for some value of "worth it."

In the last installment we were exploring the behavior of integer division in Haskell. I want to get back to C now. We learned that the behavior of integer division involving negative results is not strictly defined for C. The behavior of % (mod) is also not very strictly defined.

Let's start with Kernighan and Ritchie's The C Programming Language, Second Edition (I'm not even going to try to figure out rules for pre-ANSI/ISO C). K&R tell us on p. 10 that

...integer division truncates; any fractional part is discarded.

That isn't very detailed, but on p. 41 they tell us

the direction of truncation for / and the sign of the result for % are machine-dependent for negative operands, as is the action taken on overflow or underflow.

OK, but that doesn't describe exactly what the options are. Things get a little bit more detailed on p. 205, where we read that no guarantees are made about the sign of the remainder!

...if the second operand is zero, the result is undefined. Otherwise, it is always true that (a/b)*b + a%b is equal to a. If both operands are non-negative, then the remainder is non-negative and smaller than the divisor; if not, it is guaranteed only that the absolute value of the remainder is smaller than the absolute value of the divisor.

This isn't actually internally consistent, because if the sign of the remainder is not correct, then the identity for division doesn't work for negative values unless the sign of the quotient is allowed to be incorrect! I've never seen it suggested anywhere else that division could be that loosely defined. But K&R isn't the formal standard, so let's move on.

The reason for the "looseness" that exists in the C standard, of course, is that the standard was originally written to, as much as possible, codify existing practice, and C has a strong bias towards efficiency. Since (apparently) different hardware division algorithms had different behavior, the standards committee did not feel that it was appropriate to require existing implementations to change behavior. Doing so might have required existing architectures to have to replace hardware division with software division, which could have inflicted an enormous efficiency cost.

According to ISO/IEC 9899:1990 (known as C90)

When integers are divided and the division is inexact, if both operands are positive the result of the / operator is the largest integer less than the algebraic quotient and the result of the % operator is positive. If either operand is negative, whether the result of the / operator is the largest integer less than or equal to the algebraic quotient or the smallest integer greater than or equal to the algebraic quotient is implementation-defined, as is the sign of the result of the % operator. If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a.

So we know that there are two options for rounding. In order to maintain the identity involving integer division and mod, though, the value of mod has to be consistent with the rounding strategy, even if the sign does not have to be consistent.

There is a back door that lets us get to defined behavior. Apparently the div function does have strictly defined rounding. In section 7.10.6.2 of the standard, we read:

If the division is inexact, the resulting quotient is the integer of lesser magnitude that is the nearest to the algebraic quotient.

That's interesting -- this is rounding towards zero. The div function returns a structure of type div_t that contains both the integer quotient and integer remainder. It is provided in the <stdlib> header, available in C++ as <cstdlib>. In his book The Standard C Library, P. J. Plauger provides an implementation for div. It looks like this:

div_t (div)(int numer, int denom)
    {        /* compute int quotient and remainder */
    div_t val;

    val.quot = numer / denom;
    val.rem = numer - denom * val.quot;
    if (val.quot < 0 && 0 < val.rem)
        {    /* fix remainder with wrong sign */
        val.quot += 1;
        val.rem -= denom;
        }
    return (val);
    }

We can see what he is doing: for negative quotients that are inexact answers to the division problem, he shifts the quotients up towards zero and the remainders get reversed. Note that he does not use the built-in % facility, presumably since its behavior does not have very strong guarantees placed on it.

C: A Reference Manual (5th Edition) by Harbison and Steele seems to indicate that the semantics are a little more rigorously defined. We read there that

For integral operands, if the mathematical quotient of the operands is not an exact integer, then the fractional part is discarded (truncation toward zero). Prior to C99, C implementations could choose to truncate toward or away from zero if either of the operands were negative. The div and ldiv library functions were always well defined for negative operands.

That seems pretty unambiguous, but then on page 419, when describing the div and ldiv function, the authors write

The returned quotient quot is the same as n/d, and the remainder rem is the same as n%d.

But that ignores the possibility of a pre-C99 implementation where / rounds away from zero for negative values, as does GHCi in my tests. So again we have a lack of rigorous internal consistency. It is worth noting here that K&R don't make any extra statements about the required rounding behavior of div and ldiv, and since K&R is still considered the "bible" by many C programmers, the guarantees on the div and ldiv function may not be very well-known -- or properly implemented.

Does C99 clarify this at all? ISO/IEC 9899:1999(E), Second Edition 1999-12-01, tells us that "the result of the / operator is the algebraic quotient with any fractional part discarded" and a footnote indicating that this is often called "truncation towards zero."

How about C++? ISO/IEC 14882, Second Edition (2003-10-15) does not actually say how rounding is performed, although it says that "If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined." There is a footnote indicating that "According to work underway toward the revision of ISO C, the preferred algorithm for integer division follows the rules defined in the ISO Fortran standard" (rounding towards zero). When we try to look up information about div and ldiv, we find that the C++ standard just refers us to the Standard C library.

OK, all the standards language is giving me a headache; let's take a look at some code. To begin with, let's confirm the way my C implementation does rounding of integer quotients. We took a look at 6/5, -6/5, 5/6, and -5/6 in Haskell; let's look at the same quotients in C:


int val_1 = 6;
int val_2 = 5;
int val_3 = -6;
int val_4 = -5
int result_1 = val_1 / val_2;
int result_2 = val_3 / val_2;
int result_3 = val_2 / val_1;
int result_4 = val_4 / val_1;
printf("result_1 = %d, result_2 = %d, result_3 = %d, result_4 = %d\n", result_1, result_2, result_3, result_4);

This gives me:

result_1 = 1, result_2 = -1, result_3 = 0, result_4 = 0

Yep, I'm getting rounding towards zero for both positive and negative values. Next, some Haskell. Let's bring back our algorithm from part 2:

let gen_nths denom = [(numer, denom::Int) | numer <- [(-denom::Int)..(denom::Int)] ]

let div_map m1 m2 = map (\tup -> (fst tup + snd tup) * (((m2::Int) - (m1::Int)) `div` 2) `div` snd tup + m1)

div_map (-10) 10 (gen_nths 3)

[-10,-7,-4,0,3,6,10]

And now let's write up my C algorithm again. This time we'll use int instead of long since we don't need big numbers (although on my target, ints are actually 32 bits long).

unsigned int denom = 3;
int numer;
for ( numer = -3; numer <= 3; numer++ )
{
    int quot = numer * 10 / denom;
    printf("quotient %d\n", quot);
}

Go ahead and try it on your platform.

Whoah! What happened? You might have noticed something very odd about the first few quotients. They are monstrously large! On my target I get:

quotient 1431655755
quotient 1431655758
quotient 1431655762
quotient 0
quotient 3
quotient 6
quotient 10

What happened is that I injected a bug to point out yet another possible way your C code can fail catastrophically. This behavior can surprise even experienced programmers. Note that since my denominator is always a positive value, I declared it as an unsigned int instead of an int. So what went wrong?

Let's look at the first example: -3/3 yielding 1431655755. The behavior you are looking at is actually mandated by the C standard. When mixing signed and unsigned types, the compiler is required to promote (that is, widen) the actual type of the calculation to an unsigned type. So, internally, if we are performing the calulation -22 (signed) / 7 (unsigned), the compiler is required to notice that both a signed and unsigned long value are presented to the integer division operator. The 32-bit twos-complement representation of -3 is 0xFFFFFFFD (the conversion to an unsigned intermediate value changes the meaning, not the representation). I multiply this value by 10, yielding 0xFFFFFFE2, and then divide it by 3, yielding 0x5555554B, or a decimal value of 1431655755. The compiler treats sticks this unsigned value right into the signed result variable. The signed or unsigned status of the destination variable has absolutely no effect; it does not dissuade the compiler from deciding to treat the values as unsigned. (It is a common misconception to think that the destination value influences the type of the calculation in C).

If you have a target with 16-bit ints, your rolled-over values will be different (0xFFFD, 0xFFE2, and 0x554B, or decimal 21835). So the mixing of signed and unsigned values has not only given us the wrong answer, but made the code that generates the wrong answer produce inconsistent results depending on the size of int, even when the values we start with are not actually too big to fit into 16 bits.

If that wasn't perfectly clear, and even if it was, if you are really trying to write portable numeric code in C that has to be correct, I urge to consider purchasing the MISRA (Motor Industry Software Reliability Association) book MISRA-C:2004, Guidelines for the Use of the C language in Critical Systems. It has the most detailed explanation of C's arithmetic type conversions, and more importantly, the implications of these type conversions in real code. The crux of the biscuit is that C is hard to get right, even for good programmers.

OK, so let's change my denominator back to a signed long and try it again. This time the results look more reasonable: -10, -6, -3, 0, 3, and 6.

Are things any different if we use div?

int denom = 3;
int numer;
for ( numer = -3; numer <= 3; numer++ )
{
    div_t val = div(numer * 10, denom);
    printf("quotient %d\n", val.quot);
}

In my case, no, since on my compiler and target, / already seems to round towards zero (asymmetrically) while Haskell rounds symmetrically downwards (floor behavior).

By the way, while we're at it, let's see what C has to say about the "weird" number divided by -1:

long most_negative_long = -2147483648;
long minus_one = -1;
long result = most_negative_long / minus_one;
ldiv_t ldiv_result = ldiv(most_negative_long, minus_one);
printf("results: %lX, %lX\n", result, ldiv_result.quot);

What do you get? I get zero as the result of both the / and ldiv.

I also get GCC telling me "warning: this decimal constant is unsigned only in ISO C90." What does that mean? The compiler is apparently warning us that in C99 we won't be getting an implicitly unsigned value out of the constant -2147483648, in case we might have wanted to use this constant in an expression involving signed types to force the calculation to be promoted to an unsigned type. But why would we get an unsigned value in the first place? Apparently in C90, the number's magnitude is interpreted first, and the value is negated. 2147483648 is too large (by one) to fit into a signed long, so the compiler promotes the type to an unsigned long, then negates it.

I have been trying to come up with an example of an expression that behaves differently when I use -2147483648 as a constant, as opposed to 0x80000000, but so far I haven't been able to come up with one. This may be because my compiler is already operating under C99 rules and so I never get the implicit promotion to an unsigned value.

Anyway, be that as it may, some parting advice and conclusions:

- GHCi (on the PC and Mac) and C (Visual C++ 6.0 and GCC on the PC and Mac) yield distinctly different rounding behavior for integer division. C90 allows this behavior. Does Haskell? Would it make sense for Haskell to define integer division more strictly, the way that C99 does?

- Division by zero is never OK; neither is taking % zero. Both are a fatal error in GHCi. The results are undefined in C (but a fatal error is generated by most implementations).

- Overflow (which, in the case of integer division, occurs only when the "weird number" is divided by -1) produces undefined results, and your code should avoid it, both in Haskell and in C.

- Operations on unsigned values are guaranteed to produce results that are consistent from platform to platform, assuming the integer size is the same. Operations on signed values don't have this guarantee.

- The rounding (truncation) of inexact quotients may be either towards zero in all cases, or towards zero for positive quotients and away from zero when the results are negative. If your implementation follows the newer C99 standard rounding should always be towards zero.

- Mixing signed and unsigned values in C expressions is very dangerous. If you do so, your implementation may have errors far more severe than differences in rounding behavior.

- Consider avoiding signed division of negative values in C altogether, if your algorithm allows it. Either implement the algorithm using entirely unsigned integral types, or shift the domain of your function so that you are operating on non-negative signed values, and shift it back (using subtraction, which has well-defined semantics) when your division is done.

- Algorithms which feed a range of values which cross the origin to integer division may vary between GHCi and C implementations. Because GHCi does not provide guaranteed rounding towards zero as C99 and the div and ldiv functions require, it is difficult to prototype in GHCi and expect to get the same results in C.

And, finally,

- Make sure your implementation actually works the way it is supposed to. Only testing can truly accomplish this.

Interesting, isn't it, how studying one language can enrich your understanding of another! At least, it works for me!

The Division Bell Tolls for Me, Part Three

2006-12-07T15:49:00.000-05:00

In the last installment, I pointed out a discrepancy between the way that Haskell does integer division and the way that some C code does it. Let's look at just how integer division behaves in Haskell a little more closely. You can type these expressions into GHCi:

6 / 5
1.2
5 / 6
0.8333333333333334
(6::Int) `div` (5::Int)
1
(5::Int) `div` (6::Int)
0

Integer division in the positive numbers always rounds down: 1.2 rounds down to 1, and 0.8333... rounds down to 0. In fact, it looks like the fractional part is just truncated. But let's check some negative values to be sure:

-6 / 5
-1.2
(-6::Int) `div` (5::Int)
-2
-5 / 6
-0.8333333333333334
(-5::Int) `div` (-6::Int)
-1

That's interesting; clearly it is not strictly truncation (rounding towards zero) that is happening, or else -5/6 would give us zero, not -1. And we clearly aren't getting "rounding" in the usual sense of rounding to the nearest integer (although there is no universal rounding algorithm to round to the nearest integer; there are lots of different variations in practice).

It looks like we have floor() behavior, which in the case of negative values means rounding away from zero. To state it slightly more rigidly, if the result of the div operation is a whole number, we get the whole number, otherwise we get an integer that represents the exact answer minus the fractional part.

If you learned integer division the old-fashioned way, on paper, you know what remainders are. The remainder is the leftover part of the process, and represents the numeator of the fractional part of the quotient. In Haskell, div gives you the whole number result of integer division, and mod will give you the remainder. So, for example,

(2::Int) `div` (3::Int)
0
(2::Int) `mod` (3::Int)
2

In fact, what this points to is that there is a relationship between the result of div and the result of mod. It should hold true in all cases, actually; in C, it is part of the ISO standard. The relatioship is this:

For any quotient o = m `div` n where n is not zero, and the remainder p = m `mod` n, o * n + p = m. In other words, you can reverse the integer division by multiplication as long as you add the remainder back in.

This relationship should be obviously true for any non-negative n and m. But I'll go further and say that while the exact meaning of mod for negative numbers varies from language to language, and perhaps from implementation to implementation, this relationship should still hold true, with the possible exception of cases involving overflow (which I'll discuss further below).

We can represent the relationship in Haskell like this:

10 `div` 3
3
10 `mod` 3
1
let undivide n o p = o * n + p
undivide 3 ( 10 `div` 3 ) ( 10 `mod` 3 )
10

In fact, let's test it for a few values of n and m:


let check_divide m n = ( undivide n ( m `div` n ) ( m `mod` n ) ) == m
[ check_divide m n | m <- [(-5::Int)..(5::Int)], n <- [(-5::Int)..(-1::Int)] ]
[ check_divide m n | m <- [(-5::Int)..(5::Int)], n <- [(-5::Int)..(-1::Int)] ]

Try out the results for yourself; again, not a rigorous proof, but suggestive.

But what about the overflow cases? Let's examine them. If Haskell's Int type is a 32-bit signed int, then we should be able to represent the values −2,147,483,648 (corresponding to 10000000000000000000000000000000 in binary or 0x80000000 in hexadecimal), to +2,147,483,647 (corresponding to 01111111111111111111111111111111 in binary or 0x7FFFFFFF in hexadecimal). Let's ask Haskell what happens when we try to exceed our largest positive number:

(2147483647::Int) + (1::Int)
-2147483648

Yep, we overflow; we get the largest negative number. Conversely, we can underflow:

(-2147483648::Int) - (1::Int)
2147483647

We don't get run-time error checking (and probably don't want it, for the sake of efficiency, when using mahine types). Of course, division by zero is still considered a run-time error:

(2147483648::Int) `div` (0::Int)
*** Exception: divide by zero

What about overflow or underflow in the results of division? With multiplication, it is very easy to overflow; multiplying two large numbers can easily exceed the width of a 32-bit signed value. You can come pretty close with:

(46341::Int) * (46340::Int)
2147441940

because 46340 is the next-lowest integer value to the square root of 2,147,483,647. Generate a result just slightly higher and you will roll over to a large negative:

(46341::Int) * (46341::Int)
-2147479015

With multiplication there are lots of combinations of values that will overflow, but with division it is a little bit harder to trigger overflow or underflow. There is one way, though. While 2,147,483,647 divided by any lesser value will be a lesser value, and divided by itself will equal one, recall that twos-complement representation gives us a slightly asymmetric set of values: the largest representable negative number is one larger, in absolute magnitude, than the largest representable positive value. Thus:

(214483647::Int) `div` (1::Int)
214483647
(214483647::Int) `div` (-1::Int)
-214483647
(-214483648::Int) `div` (1::Int)
-214483648

In 32 bits of twos-complement, -2,147,483,648 is the "weird number." As a general rule, if you take a twos-complement number, flip all the bits, and add one, you get the negative of that number. The only exception is the weird number. Let's see what happens when we try to divide the weird number by -1:

(-2147483648::Int) `div` (-1::Int)

Now, I would like to tell you what GHCi says when I ask it to divide the weird number by -1. I'd also like to see what it says about the mod. But I can't. GHCi crashes when I type in those expressions.

So, I can't tell you what Haskell says. But I can tell you what the C standard says. Here's a hint: not only is it not defined, but in fact the result of any overflow that occurs with arithmetic operations on signed integral typesis not defined by the language standard. Only the results of arithemtic operations on unsigned integers have defined semantics for overflow, making them portable -- assuming that the size of the type in question is the same. More on that next time.

The Division Bell Tolls for Me, Part Two

2006-12-05T18:44:00.000-05:00

OK. In our last installment I started talking about using Haskell one-liners to calculate some functions. The function in question was designed to map a set of fractions in the range -7/7 to 7/7 to the machine integers 0..65536. The function itself, along with a wrapper to test, it fits neatly into a Haskell one-liner (well, it might be more than one line, depending on your terminal width). You can use GHCi to evaluate it:

map (\tup -> (fst tup + snd tup) * 32768 `div` snd tup) [(numer, 7) | numer <- [(-7::Int)..(7::Int)] ]

I showed in the last installment that this function gave me the results I wanted:

[0, 4681, 9362, 14043, 18724, 23405, 28086, 32768, 37449, 42130, 46811, 51492, 56173, 60854, 65536]

Let's play with that function a little more, and then I want to talk about division (hence the title of the entry). In particular, integer division.

First, let's simplify our expressions by breaking them down and establishing some bindings. We can also get rid of the presumption that our output range starts at zero:

let gen_nths denom = [(numer, denom::Int) | numer <- [(-denom::Int)..(denom::Int)] ]

let div_map m1 m2 = map (\tup -> (fst tup + snd tup) * (((m2::Int) - (m1::Int)) `div` 2) `div` snd tup + m1)

And now we can test it. Note that we need to add a few parentheses:

div_map (-32768) 32768 (gen_nths 11)

[-32768, -29790, -26811, -23832, -20853, -17874, -14895, -11916, -8937, -5958, -2979, 0, 2978, 5957, 8936, 11915, 14894, 17873, 20852, 23831, 26810, 29789, 32768]

OK. Now what is it we've done exactly? Well, we've generated some test values, and an algorithm, for distributing a fractional range onto a machine integer range. For our purposes, think of it as a little machine for testing division.

To see just why I chose this algorithm to play with Haskell, we have to go back and consider some C code. It's quite a headache-inducing paradigm shift to go back to C/C++, but bear with me. Let's just start with the simplest thing: we'll create the same mapping we just generated, hard-coding the values:

long denom = 11;
long numer;
for ( numer = -11; numer <= 11; numer++ )
{
    long val = numer * 32768 / denom;
    printf("%d\n", val);
}

And the results:

Hmmm... wait a minute, let's compare the results:


Haskell            C
-32768             same
-29790             -29789
-26811             -26810
-23832             -23831
-20853             -20852
-17874             -17873
-14895             -14894
-11916             -11915
-8937              -8936
-5958              -5957
-2979              -2978
0                  same
2978               same
5957               same
8936               same
11915              same
14894              same
17873              same
20852              same
23831              same
26810              same
29789              same
32768              same

It looks like every single one of the negative values is off by one! In our third and final installment I'll dive a little deeper into the semantics of integer division.

The Division Bell Tolls for Me, Part One

2006-12-05T15:20:00.000-05:00

With apologies to both Pink Floyd and John Donne.

I've been toying with Haskell. I wish I had enough free time for a systematic study of Richard Bird's Introduction to Functional Programming Using Haskell, Second Edition, but for now I have to content myself with dipping into it in small scraps of free time when both babies are asleep and the dishes are done. In addition, I'm using Haskell to model the behavior of some functions that I'm actually writing in C++.

One of the reasons I like Haskell is that with a tool like GHCi, which gives me a REPL (a Read, Evaluate, Print loop for interactive development), I can write toy one-liners that do something useful, and since Haskell supports typing, I can test how machine types behave. With an important exception, which I will discuss.

Let's say I want to try out a function that maps the fractional values -7/7 through 7/7 to unsigned integers in the range 0..65536 (the range of values representable by 16 bits, plus one). In Haskell I can try this out using a one-liner (typed into GHCi). Let's build it up. First, the range of input values. Ignore for now the possibility of using or introducing a true rational number type; instead we'll generate a set of tuples. In Haskell you can express this very concisely using a list comprehension:

[(numer, 7) | numer <- [-7..7] ]

[(-7,7),(-6,7), (-5,7), (-4,7), (-3,7), (-2,7), (-1,7), (0,7), (1,7), (2,7), (3,7), (4,7), (5,7), (6,7), (7,7)]

The list comprehension can be (roughly) read as "Make a list of tuples out of numer, 7 where numer takes on the values from the list -7 to 7." Think for a moment about how you could do this in your favorite language.

Now let's do our math on the resulting list. We can use map to apply a function to the list. We can use fst and snd to get to the values in the tuple; for example, to look at the numerators, do this:

map fst [(numer, 7) | numer <- [-7..7] ]

[-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7]

Let's go ahead and do our scaling. We want to describe a single function to pass each tuple to; in fact we want a lambda abstraction, a function that we don't bother to name:

map (\tup -> fst tup / snd tup * 65536 ) [(numer, 7) | numer <- [-7..7] ]

[-65536.0, -56173.71428571428, -46811.42857142857, -37449.142857142855, -28086.85714285714, -18724.571428571428, -9362.285714285714, 0.0, 9362.285714285714, 18724.571428571428, 28086.85714285714, 37449.142857142855, 46811.42857142857, 56173.71428571428, 65536.0]

Whoops, that's not quite right. We want to map to only the positive values. We have to shift the domain (the incoming numerators) so they are non-negative:

map (\tup -> (fst tup + snd tup) / snd tup * 65536 ) [(numer, 7) | numer <- [-7..7] ]

[0.0, 9362.285714285714, 18724.571428571428, 28086.85714285714, 37449.142857142855, 46811.42857142857, 56173.71428571428, 65536.0, 74898.28571428571, 84260.57142857143, 93622.85714285714, 102985.14285714286, 112347.42857142857, 121709.71428571429, 131072.0]

But now the codomain is too big; we have to cut it in half:

map (\tup -> (fst tup + snd tup) / snd tup * 65536 / 2) [(numer, 7) | numer <- [-7..7]]

[0.0, 4681.142857142857, 9362.285714285714, 14043.42857142857, 18724.571428571428, 23405.714285714286, 28086.85714285714, 32768.0, 37449.142857142855, 42130.28571428572, 46811.42857142857, 51492.57142857143, 56173.71428571428, 60854.857142857145, 65536.0]

That looks about right. Now let's apply a type. Because I'm eventually going to be implementing this without floating-point, I want the math to be done on machine integers. There are some exceptions, but most target architectures these days give you 32 bits for int, so Haskell's Int, which is defined to be 32 bits, should yield approximately what I want. To introduce typing, all I have to do is add a type to the list values. Type inferencing will do the rest. Oh, and since division by slash is not defined on Int, I have to change it to `div` (infix division):

map (\tup -> (fst tup + snd tup) `div` snd tup * 65536 `div` 2) [(numer, (7::Int)) | numer <- [(-7::Int)..(7::Int)] ]

[0, 0, 0, 0, 0, 0, 0, 32768, 32768, 32768, 32768, 32768, 32768, 32768, 65536]

Whoah. Something has gone disastrously long. Take a moment to figure out what it is. I'll wait.

Did you figure it out?

The problem is that when I use integer division in an expression, the result is truncated (the fractional part is lost). If the division occurs before any of the other operations, most of the significant bits of the math are lost! I can fix this by making sure to do the division last:

map (\tup -> (fst tup + snd tup) * 65536 `div` snd tup `div` 2) [(numer, (7::Int)) | numer <- [(-7::Int)..(7::Int)] ]

[0, 4681, 9362, 14043, 18724, 23405, 28086, 32768, 37449, 42130, 46811, 51492, 56173, 60854, 65536]

That's better. While I'm at it, I can simplify out that factor of 2 by using half of 65536:

map (\tup -> (fst tup + snd tup) * 32768 `div` snd tup) [(numer, (7::Int)) | numer <- [(-7::Int)..(7::Int)] ]

[0, 4681, 9362, 14043, 18724, 23405, 28086, 32768, 37449, 42130, 46811, 51492, 56173, 60854, 65536]

In fact, I can ask GHC to verify that the results are the same:

map (\tup -> (fst tup + snd tup) * 65536 `div` snd tup `div` 2) [(numer, (7::Int)) | numer <- [(-7::Int)..(7::Int)] ] == map (\tup -> (fst tup + snd tup) * 32768 `div` snd tup) [(numer, (7::Int)) | numer <- [(-7::Int)..(7::Int)] ]

True

Very cool! Of course, this is not a rigorous proof, but I'm satisfied that my function is correct for the given inputs, and sometimes that's enough.

Some Very Basic Haskell and Thoughts on Error Diagnosis

2006-11-27T18:45:00.000-05:00

So, yesterday I attempted to write a very simple Haskell one-liner. I wanted to use a list comprehension to dump the results of some simple math on a range of numbers. Something like this:

[n / 5 | n <- [0..1024] ]

That's a tremendously concise program. You could read it as follows: "generate a list of n divided by 5 where n is drawn from the enumerated list of numbers 0 to 1024." Type this into GHCi (that's GCH in interactive mode) and it instantly spits out [0.0, 0.2, 0.4 through 204.8].

That's cool, but the reason I was writing this little program was actually to look at rounding behavior when doing division on hardware-sized integers. The '/' operator is not defined on the Int type, so if I ask the list comprehension to operate on a list of Int-typed values I understandably get an error:

Prelude> [n / 5 | n <- [(0::Int)..(1024::Int)] ]
<interactive>:1:1:
No instance for (Fractional Int)
arising from use of `/' at :1:1-5
Possible fix: add an instance declaration for (Fractional Int)
In the expression: n / 5
In the expression: [n / 5 | n <- [(0 :: Int) .. (1024 :: Int)]] In the definition of `it': it = [n / 5 | n <- [(0 :: Int) .. (1024 :: Int)]]

GHCi is giving me a lot of context here; that's nice. The message indicates the definition of "it." Apparently "it" is the way GHCi implements a REPL; my expression gets bound to "it" and evaluated. Then it zooms in on what goes wrong. Understanding this error message completely requires an understanding of type classes; I'm not fully up on type classes yet, but it obviously has something to do with type. The suggestion in this case is probably not what I want: I think it is suggesting that I could extend the slash operator to handle integer arguments. That would be a sensible suggestion if I was doing something a little more sophisticated with my own classes. But instead let's try div, which is supposed to do integer division, instead of the slash operator:

Prelude> [n div 5 | n <- [(0::Int)..(1024::Int)] ]
<interactive>:1:1:
Couldn't match expected type `(a -> a -> a) -> t1 -> t'
against inferred type `Int'
In the expression: n div 5
In the expression: [n div 5 | n <- [(0 :: Int) .. (1024 :: Int)]] In the definition of `it': it = [n div 5 | n <- [(0 :: Int) .. (1024 :: Int)]]

Whoah. Now the error message is different, but I'm doing something wrong. Let's see if we can decode it. It says that in "n div 5" it is expecting the type (a -> a -> a) -> t1 -> t. What does that mean?

I think it means that div takes two values and returns a third, and I'm then trying to apply two arguments to the resulting value. Or something like that. This error message may have everything I need to know; maybe after studying my copy of Bird's Introduction to Functional Programming Using Haskell, which should be arriving in the mail any day now, I'll be able to decipher this; but then again, maybe not. Time to do some Googling. Googling complete, with no answer; time to ask for help.

I got a very quick and helpful reply on fa.haskell. (The newsgroup comp.lang.haskell supposedly has been created, but it doesn't seem to show up in Google Groups yet). The helpful reader suggested that I use `div` (note that those are backticks, not single quotation marks). What this really means is that div in Haskell is a prefix operator, not an infix operator like the slash. It expects its arguments to come afterwards. The magic backticks allow transforming a prefix operator into an infix operator. That works great.

My larger topic is error messages. Having tried to contribute just a little tiny bit on d2c, the Dylan to C compiler, motivated by stumbling across bugs and places where error messages were a bit weak, I can attest to the following principle. Since I've never heard it expressed anywhere else, I'm going to call it Potts' First Principle of Programming Language Implementation. Here it is:

A compiler implementation will require several times more code to provide a helpful diagnostic message than it does to detect a failure, issue a cryptic message, and exit. The diagnostic-generating code will be complicated, difficult to understand, and inelegant. It is nevertheless worth writing.

The difference between the ugly implementation which is helpful to the end user and the wonderfully elegant implementation that produces a cryptic failure message is that the former will be adopted and the latter will not.

Consider writing two methods, one that compiles good code quickly but doesn't give you much help when a failure is detected, and another fully instrumented method that diagnoses the problem in English.

Having worked with a large number of different tools, I've found that the primary difference between a truly usable tool and one that is not so usable is the quality of the diagnostics.

A quick example from Dylan: Dylan allows multiple inheritance. Multiple inheritance introduces means that the inheritance graph of a given class can be not just a list but a DAG (a directed acyclic graph). This means that it is possible that you can have a diamond-shaped inheritance graph, in which one or more base classes is included via more than one path. This presents a problem when searching for the next applicable method. The rule, expressed informally, is this: the different partial orderings of the inherited classes, from child to parent to nth-generation ancestor, can't contradict each other. You can't have a class which is both a sports car first and a fire truck second, as well as a fire truck first and a sports car second. If you do, you don't know what is going to happen when you try to shift it into gear.

The d2c compiler complained about this situation with an error message that was, on the positive side, concise. It said "Inconsistent CPL" and quit.

The code in the compiler that detected this condition was a model of elegance. In order for it to display a much more detailed message, something like "class wonderCar: the partial class precedence list (sportsCar, fireTruck) reached via base class superClassTypeA contradicts the partial class precedence list (fireTruck, sportsCar) reached via base class superClassTypeB," some much uglier code has to be inserted, or wrapped around, that model of elegance, to accumulate the information to display to the end user. It's worth writing that method. It could even be implemented as a kind of exception handler when the elegant version fails.

Diagnostic messages: they're what's for breakfast.

Exploring Haskell

2006-10-25T19:21:00.000-04:00

Having gotten somewhat stalled on learning more advanced Scheme programming paradigms, I have decided to try learning Haskell. In particular, I want to use Haskell to get both more lazy and more functional. It is all too easy for me to write Scheme programs which use recursion and lists but are basically translations of the way I would write things in Pascal. I can build my little closures, and do maps and folds, but the programs still evaluate everything, still compute everything, and still use a lot of mutation. My Scheme functions often aren't referentially transparent; they're often really methods to mutate objects.

It is reasonably legitimate to use Scheme that way, but I'm not learning much.

In particular I'd love to use something more advanced for my embedded work, but it seems to me that using Scheme is just going to turn compile-time errors into run-time errors, with its lack of typing, and although my programs might be shorter, they won't really be any more explicit.

In particular, although I have become reasonably facile with s-expressions and tend to be able to see "past" the parentheses, Haskell confirms my belief that it isn't actually necessary for the programmer to play compiler and write the abstract syntax tree him or herself. There's a little bit of buzz beginning about how Haskell is easier for beginners, and my experience with Dylan leads me to believe that typing is actually valuable; in Dylan, for example, it can make a difference between code that uses full runtime dispatch and takes twenty minutes to run, or a version that takes a few seconds.

I'd also like to better understand the lazy paradigm, where a very large or infinite list or tree does not have to be fully generated or fully evaluated in order to be useful. I'd like to understand Monads, or at least how to use them.

A lot of my programming work involves explicit or implicit state machines and plumbing to manage state changes. To improve this I really just need something a lot more concise and expressive than C++. I need leverage, not totally new programming paradigms, at least not at first. So we'll see if Haskell can help me there.

I've been faintly interested in learning languages like Clean, or ML, or Miranda, or Ocaml. But so far what I'm reading leads me to think that it may not be worth my time to bother with these and that Haskell has absorbed a lot of the things that are cool about these languages and may, in fact, be the shit. A large amount of material is being written about Haskell, and the stable base/experimental extensions approach seems like the right thing. In other words, Haskell seems like a language upon which a lot of smart people are converging.

And if it isn't, maybe I can take some of what I learned using it back to Scheme, or maybe Kernel.

More to come!

Generic Functions and Pointers to Member Functions

2006-08-31T13:14:00.001-04:00

People who know me know that I still carry a torch for a wonderfully-designed but little-used programming language called Dylan. In my arrogant opinion Dylan took much of the best of Common Lisp and CLOS, regularized and streamlined it, and gave it a syntax more acceptable (due to familiarity) to programmers from the C and C++ world (although this annoyed some prefix syntax fans in the process). Dylan is a multi-paradigm language, where "everything is an object," designed to support functional styles, object-oriented styles, and procedural styles.

Dylan is still alive and kicking with several impressive implementations available here including d2c, an amazing compiler that generates C code from Dylan source, and which is written primarily in Dylan itself, and the formerly commercial Functional Objects compiler, which generates native machine code. I have not studied the Functional Objects codebase very much, but I have spent time with d2c. It is an amazing piece of code. Studying it makes me wish I was able to strap on an auxilliary brain or two and take a pill that gave me a post-graduate education in language implementation without all that tedious mucking about in graduate school, so I could contribute something useful to the project instead of just an occasional bug report or ignorant question.

In Dylan, and in Dylan's sire Common Lisp with CLOS, classes contain data. Classes don't contain methods. Methods are implemented using a construct known as a generic function. A generic function lets you define several specialized functions to operate on objects of different classes. A variety of functions with the same name are bundled together; as you define additional functions, they get added to the generic function. At run-time, when you make a call to the generic function, the specific function chosen can depend on the actual run-time type (the class) of the object you send to it. Classes can inherit from one or more other classes; this inheritance tree is used to make the decision about which actual method to call for a given object. Generic functions can be specialized in other ways; they are extraordinarily flexible and powerful. But I'm only going to touch today on generic function dispatch specialized on the class of the incoming object, incoming parameters, and return type.

In his article "A First Look at Dylan: Classes, Functions, and Modules," Steve Strassmann writes:

Object-oriented languages, including Dylan, provide polymorphic functions, which means a given function may be executed as one of several possible implementations of that function, called methods... when Dylan sees a call to name(x), depending on what type of object is, one of several methods is selected and executed. In Dylan, name is called a generic function, consisting of a family of name methods that implement the functionality of name for various classes (see Figure 2). Each of these methods "belongs to" its generic function (in this case, name) rather than to a class. This is a key point; it's the core difference between C++'s object model and Dylan's.

In terms of implementation, this means that when you make a generic function call, the generic function isn't a "standard" function; a dispatch mechanism comes into play to select the proper generic function based on the call's arguments. The run-time context contained in the object is explicitly passed to the function.

Strassmann gives examples generic function; I have stripped down one of his examples somewhat here:

// No type declaration, works on any type of object
define method double (x)
   pair(x, x);
end method double;

// Works on all numbers
define method double (x :: <number>)
   2 * x;
end method double;

// Works on all strings
define method double (x :: <string>)
   concatenate(x, x);
end method double;

When double is invoked on an argument, the most specific method is invoked... for example, double("foo") would invoke the third method, because <string> is more specific than <object>, which is what the first method is specialized to. If no match is found, Dylan will catch it and signal an error.

Besides a plethora of different ways to specialize generic functions, Dylan supplies various forms of introspection; if you want to extend or alter the run-time dispatch, you can do so.

To C++ programmers, this is inside-out. In C++, classes "contain" methods, known more commonly as "member functions" because they are "members" of the class. C++ supports polymorphism and dispatch based on run-time type. I'm going to talk a little bit about how objects and member functions work together in C++ and how you can use them, and how, when we look at C++ in light of Dylan or CLOS, C++ actually gives us a subset of object dispatch, presented in an obfuscated form.

Let's say you don't want to just make a new subclass with specialized methods and allow polymorphic dispatch to operate based on run-time type, but instead you want to handle your own run-time dispatch. In Dylan you can do this using introspection and some handlers that allow you to override the standard generic function dispatch. Since you have the object and the generic function and can get at specific functions, you can just call them, passing the object.

To do the same thing in C++ you need to work around the fact that C++ obfuscates what is actually going on when you call a method. You can do this by using a slightly obscure C++ construct called the pointer to member. For the present discussion the member in question will always be a member function, but keep in mind that pointers to members can work with data members as well. This use is probably even less common since if you have an object, or a pointer or reference to an object you can access public members directly as you would access members of a struct, or via an accessor function; I would think that pointers to data members are necessary only for serious runtime hacking or compiler implementation. But the key point here is that C++ pretends that both data members and member functions are part of classes, while CLOS and Dylan much more explicitly separate these concepts.

Pointers to member functions are uncommonly used, probably in part because of its somewhat obscure syntax. The only place I've seen them used, in fact, is the Darwin kernel's IOKit source code. Recently I've had a need to customize class behaviors at runtime without subclassing and without a complete refactoring of a class into modular pieces, so I've been investigating the construct again.

The syntax is awkward, but it is consistent with the general C school of thought which says that declarations are read backwards (right to left). In C, if you have an integer variable:

int i;

to make a pointer out of it, you insert an asterisk to the left of the variable name:

int * i;

Similarly, if you have a prototype for a function returning int and taking an int parameter:

int fn ( int );

to take a pointer to it, you insert an asterisk to the left of the name:

int * fn ( int );

but the order of evaluation means that the parser reads it as a function returning a pointer to int. So you have to change the order of evaluation using parentheses:

int ( *fn ) ( int );

Now fn means a pointer to a function, not a function returning a pointer.

A member function is basically the same, with the addition of the class name and the scope resolution operator (::). When you are declaring your class, this prefix is not wanted or needed (it is implicit within the class declaration's curly braces), but when you define your methods, you do so like this:

int my_class::my_member_func( int )
{
   /* function body */
}

Another aside: the separation between the class declaration and class definition is just one of the speed bumps you have to live with when using C++; it is there to support separate compilation, but if you've ever made the switch from C++ to Java you know that giving up the need to keep header files and implementation files in perfect synchronization gives you an immediate productivity boost.

If we want to make a variable that can point to that member function, we put an asterisk to the left of the name:

int my_class::*my_member_func_ptr( int );

The precedence rules get confused by this (during parsing, it probably looks like a collision between a definition of a member function and a conventional function returning a pointer with no type attached, or some such nonsense), so again we have to use parentheses:

int ( my_class::*my_member_func_ptr )( int );

and this gives us a variable, my_member_func_ptr, which can hold a pointer to a member function with the signature "returns int and takes one int parameter." Note that the parameter list, as in a function prototype or member function declaration, only requires the types of the parameters and not the names, although you can supply names for documentation purposes if you want.

An aside: it would be easy to ridicule this syntax, but ridiculing the syntax of C++ is kind of like shooting fish in a barrel. I've shown that the syntax is at least somewhat consistent with the other C++ syntactical forms. Because of that, this particular syntax doesn't really bother me; if I can't remember it off the top of my head, I can mentally follow this derivation path and reason it out. This isn't necessarily true of a lot of other pieces of C++ syntax which do bother me and which I'm quite happy to rant about; see my piece on struct.

A pointer to member function does not have a standard implementation; the implementation (size, etc.) may differ between implementations; you should probably treat it as an opaque data structure and make no assumptions about what it actually looks like inside, unless you want to write very non-portable code. There's nothing in the standard that says that pointers to member functions have to be the same size, for example, and the standard specifically says they are _not_ just specially typed pointers; they are not convertible to and from void* by casting, as other pointer types are, using either the old-style or new-style casts.

This is because pointer to member function is not a usable pointer by itself; instead it contains whatever extra information is needed to represent a specific member function for a given class, probably an index or offset of some sort. You can imagine that the compiler needs a mechanism like this for its own use, so that it can turn

object.member_function(...)

object_pointer->member_function(...)

into C-style function calls with the addition of a hidden parameter:

looked_up_member_function( this, ... )

Remember our discussion on generic function dispatch? You might notice that when you rewrite the code to explicitly pass in the contest (the "this"), it starts to look like Dylan (or, ignoring the difference between infix and prefix notation, CLOS). You can actually think of the C++ object model as a much more limited and obfuscated form of CLOS generic function dispatch. How weird is that?

The "this" pointer allows the function body access to the specific object instance variables, and can also be passed on to any subsidiary member function calls on the same object. In Dylan or CLOS you would access the data members (in slots) of the incoming object explicitly; C++ gives you access to the data members and member functions of "this" implicitly, although you can still use this-> as a prefix if you want to make very clear what you are doing, or protect against accidentally accessing something global or local in the member function's namespace that might inadvertently shadow a member. This merging of namespaces is another rich source of potential errors (remember my comment about how C++ is like obfuscated Dylan?)

Note that our pointer to member function is not defined to refer to a member function in the given class. It can have assigned to it any member function that is part of the class (or a derived class), and that has the same signature (that is, matching return type and parameter types). This, as you might imagine, allows the compiler to do dynamic dispatch based on runtime type; you can do the same thing, based on any criteria you choose.

Note also that the variable you've created is not yet initialized. There's that obfuscation again! In a language where everything is done by reference, that isn't even quite possible; your reference will wind up referring to something. But pointers enable whole new classes of errors, and there is unfortunately no such thing as a "reference to member function" in C++. Be careful to make certain you initialize it before use, preferably at the point the variable is defined! Not doing so will cause you severe tire damage!

And, in fact, the compiler may not help you avoid this. I tested GCC by writing a call to an uninitialized regular function pointer:

void ( *fptr ) ( void );
fptr();

and it generated a helpful warning for this case. When I wrote a similar call using an uninitialized pointer to a member function, like so:

void ( Class_c::*mptr ) ( void );
( this->*mptr ) ();

GCC produced no warning at all, and as you might expect, the call caused an immediate crash. This is the likely outcome, but according to the C++ standard the behavior is undefined (this is very bad; it means the program is not required by the standard to catch this as an error; it is free to silently fail in some insidious way, or destroy your hard drive, or electrify your keyboard).

You can initialize them to zero, the null pointer constant (there is an explicitly allowed conversion), but the results of calling a null pointer to member function are also undefined, so this doesn't buy you anything; you are better off initializing them at the point where they are defined. Here is an example of how to do so:

void ( my_class::*mp ) ( void ) = &my_class::member_function;

Since pointers to member functions are hard to read, especially for member functions that that accept a long list of parameters, it is valuable to make the construct into a type using typedef. I recommend using the naming convention

class name + the _kind_ of member func + "_pm_t"

But follow your own convention, or your team's convention, if you like. Keep in mind that the type can be used to represent any member function of the class (or a derived class) that matches the signature. The member function will probably represent a handler of some kind, or in design pattern terms a specific strategy. Describe what it handles, or what the strategies are trying to accomplish.

When you write the typedef, keep in mind that it looks just like the variable definition, except that the type name replaces the variable name and you put typedef in front. To define a type called my_class_SomethingHandler_pm_t, use the form:

typedef int ( my_class::*my_class_SomethingHandler_pm_t ) ( int );

Once you have a type, the following definition creates a variable with the new type and initializes it with a specific member function:

my_class_SomethingHandler_pm_t pm = &my_class::my_member_func;

This assignment can also take place in parameter binding. This means you can write a standalone function, member function, or static member function that accepts any pointer to member function matching the specified signature, and then pass it a specific one at run-time.

Once you have a pointer to member function, you can call that member function, but to do this you need an object (the "this" that will be in effect for the duration of the call). If you have a pointer to the object (which could be "this"), use
the syntax:

( object_ptr->*mp )( params );

If you have a local or global variable holding an object or a reference to an object, use the syntax:

( object.*mp ) ( params );

Note that the parentheses around the first part are mandatory, to help the parser. If your object pointer or pointer to member function is stored in a structure or you are accessing it via pointer you will probably have to introduce more parentheses to make sure the parts of the expression are evaluated in the right order. This kind of construct can get ugly fast, so be careful.

In his C++ FAQ Lite section on pointers to member functions available here Marshall Cline suggest that when making calls using pointers to member functions, you always define a calling macro like this:

#define CALL_MEMBER_FN(object,ptrToMember) ((object).*(ptrToMember))

and then do the call like this:

result = CALL_MEMBER_FN(PO,PM)( PL );

but I wouldn't necessarily recommend that; C-style macros are still quite evil, and can make it very hard to find out what the compiler is complaining about, or even what it actually compiled that you didn't intend.

The Kernel Programming Language and the Quest for Simplicity

2006-08-30T13:30:00.001-04:00

I've been reading with considerable interest about the Kernel programming language under development by John Shutt. Information and a PDF file are available here.

I am not sure I fully understand the implications and details of his $vau and $wrap constructions, but I strongly support his goals, and the rest of his report kept me, literally, awake half the night reading it. Shutt writes:

...the mandate of the Kernel language is to have a clean design, flowing from a broad design philosophy as refined by a series of more specific design guidelines --- just one of which is that all manipulable entities should be first-class.

He is trying to create a Scheme-like language which is even more uniform, predictable, and configurable than R5RS Scheme.

I don't have a Ph.D. in the programming language field, so bear with me if my terminology is a little vague. It seems that the big thing Shutt is attempting is to give fine-grained control over evaluation, essentially separating out the parameter-evaluation stage of a lambda call into a distinct and fully configurable stage. This means you can do more clever things with objects without evaluating them. I think it also points you towards macro-like constructions that don't lead off into the existing slightly swampy maze of different Scheme macro implementations. It also could be a more explicit and flexible means of handling the need for quoting.

On top of that he is also doing a number of slightly smaller things (on the scale of theoretical complexity), but which I think are great.

For instance, Shutt has in his design very explicit rules for what to do with cyclic structures, a.k.a. infinite lists. While in some situations creating these would be considered an error, in others they make perfect sense: for example, in creating trees that describe recursive-descent parsing. Therefore, giving a sensible semantics to handling cyclic structures is a sensible and intriguing thing to do. If you want to write functions which aren't willing to handle cyclic structures, you can use one of his predicates to check for that possibility.

He also has addressed a number of minor irritants which don't require a deep understanding of the lambda calculus to appreciate. For instance, he proposes that boolean evaluation should never be implicit: that is, if you want to evaluate something as a boolean value, you have to use a predicate on it to generate a boolean value, and compare it to true or false. In other words, no more "anything not explicitly false is not true" or "false is false, and nil is false, but anything else is true, and true is true" or other bizarre variant on this theme.

As someone who switches languages a lot, I have always tried to make my boolean evaluations absolutely explicit to avoid the potential confusion that implicit evaluation can bring. For example, I always write (pedantically) in C++:

if ( false == stack.full() ) {
push()...
}

In addition, he has addressed the question "if everything in Scheme has a value, what is the value of a control structure?" To make this explicit he proposes an immutable value called inert, somewhat analagous to void in C/C++, and which is an explicit type and which even has explict external representation.

There's lots more great stuff in Shutt's draft report and it addresses many of the weaknesses that make Scheme implementations so maddeningly inconsistent. Read it, study it, live it. I am looking forward to Shutt's doctoral thesis and I hope that there is one day very soon a freely available implementation of Kernel to try out!

A Rant about Const

2006-08-17T19:47:00.003-04:00

WARNING: THE FOLLOWING MAY CAUSE BRAIN DAMAGE

This is an unfinished essay that sat in draft form in my bog, unpublished, for several years. It seems very unfinished, but I decided to go ahead and publish it anyway. I'm not sure it actually makes any damned sense; it certainly needs some revision. There may indeed be a point buried in here somewhere, if only I can determine what it is!

---

I looked this up in the comp.lang.c++ newsgroups. What I keep reading is that returning a const value, when the value is int or float or some other plain built-in data type, as opposed to a class type, is not "meaningful."

Either I'm too dumb to understand this argument or the argument isn't actually coherent, it is just widely propagated because everyone mistakes the existing C/C++ runtime behavior for a sensible model of language semantics, which it isn't.

What they seem to be actually saying is "according to the language standard, C++ is not allowed to enforce meaningful const semantics on return types that are not reference or pointer types. And pointer types are hopelessly unsafe. But references can be pretty unsafe too."

There was a thread about this on comp.lang.c++, specifically about why you can't return a const int. One of the comments was:

"A value returned by a function is a rvalue, unless it is a reference.
The notion of being (or not being) const-qualified is not applicable to
rvalues of non-class types ('int' in your case). A rvalue cannot be modified just because it is a rvlaue. That's it. It doesn't make any difference whether you const-qualify it or not. That's what your compiler is trying to tell you."

http://groups.google.com/group/comp.lang.c++/browse_thread/thread/4e50f8abf9c11f71/6039d5b2e6612df0%236039d5b2e6612df0

As far as I can tell, the C++ standard specifies this because of the way returning values from functions has usually been _implemented_ in C/C++ (by copying on the stack). So the caller isn't _actually_ getting the "same" object or integer value, and in fact the original will be gone.

What this means is actually that you can freely change the return value:

int y = f(x);
y = y + 1;

But this is not actually "changing the rvalue" because the rvalue was actually copied into y; you're just changing a copy. So the statement above is correct in that the rvalue "cannot be modified." (It means that only indirectly).

In cases even when the compiler puts the return values in registers, or wherever, the standard rules about lvalues and rvalues still apply, for sanity and safety and consistency.

But it is not what I want to _express_ when I use const with a return value.

In the methods that generated warnings, I was using const return values to mean:

Case 1: what I'm returning is the result of a mathematical function call: f(x) is always y for the given x, so it wouldn't make sense for you to _change_ the value I'm returning to you. If my function f is f(x) = 1 + x, then f(1) = 2. It doesn't make any sense to then say f(1) = 3 later.

Case 2: what I'm returning is the result of an iterator and represents the state of another object at a given moment in the life of the program. Therefore, you shouldn't change _the value itself_; if you want to update it, call the iterator to get a new updated value. I say iterator_state = iterator:GetNextValue() and get iterator_state back; it doesn't make any sense to say iterator_state = iterator_state + 1 without calling the method.

I ought to be able to _say_ that the caller should not update the object I'm returning, whether "returning" means binding it via a pointer, a reference (hidden pointer), _or_ by copying the rvalue.

If it is a const u32_t I'm returning, the compiler should insist that the value be assigned only to a const u32_t. (It doesn't).

If I'm returning a const object, the compiler should enforce assigning it to a const variable. (It doesn't, but at least it doesn't generate the warning in those cases). This is because returning an _object_ on the stack does not constitute returning an "rvalue."

This is, as far as I can tell, a completely arbitrary distinction, with the sole exception that copying an object gets to invoke the copy constructor (default or provided) where copying a built-in type just does it for you.

In a similar thread Greg Comeau wrote:

"Also, returning a const T, where T IS NOT A BUILTIN TYPE many not be meaningless, because you may end up calling member functions on that object, and the member function may need to be a const member function."

It is "meaningful" in the sense that you may want to put the returned object into a const variable to _prevent_ calling any non-const member functions. But Greg phrased it backwards. You can always call const member functions on non-const objects. He should have said "you may end up calling member functions on that object, and you might want to prevent the calling of non-const member functions."

Example:

static AZMMultiZoneRef_c const MakeFromZonesBitmap( u32_t zones_bmp );

const AZMMultiZoneRef_c zones_ref = AZMMultiZoneRef_c::MakeFromZonesBitmap( p_data->zones_bitmap );

u32_t AZMMultiZoneRef_c::MutateMe( void_t );

zones_ref.MutateMe();

The compiler will (rightly) complain about this. But it will not complain about calling const member functions on a non-const object.

The intent is that you should not be able to mutate an object that is const, except using the "mutable" workaround to allow hidden state changes.

However, the rules for returned objects let us completely get around this! If I don't like that restriction, I can just assign the return value to a non-const object. So this is legal:

AZMMultiZoneRef_c zones_ref = AZMMultiZoneRef_c::MakeFromZonesBitmap( p_data->zones_bitmap );

zones_ref_2.MutateMe();

Not much of a restriction, then, is it?

OK, so let's say we're more serious about enforcing const. So, we'll use a pointer or reference instead, because that will maintain the const enforcement restrictions, right? BUT... the semantics are actually quite different, and there is a serious safety hole introduced:

"When returning references, a reference bound to the return value is not valid after object deletion; when returning values, a reference bound to the return value is valid after object deletion."

And, of course, if what you are returning a pointer or reference to is a an object in a _local_ variable, that is a seriously broken program right there. So it is kind of a "damned if I do, damned if I don't" situation.

C++ is actively hostile to functional programming. In fact, the "safety features" of the language can't even be used consistently. And with this compiler, when you try to express what you mean (taken as a given that the compiler won't enforce it), it treats it as a warning!

Paying the Sin Tax on Semantics: the Lowly Struct

2006-06-27T10:13:00.003-04:00

While this is not strictly about Scheme, I want to make a point about language design and the tax we pay (call it a sin tax, as the sins of the language designer are visited on generations of hapless language users) when there is no regularity in the syntax.

Programmers from the C/C++/Java world often look at languages like Scheme, with its relatively uniform syntax (or, I should say, almost a complete lack of syntax, where the language source is pretty much an textual form of an abstract syntax tree) and bemoan how strange it is.

But, as I will show, the alternative is actually far more complex: that alternative is to have semantics and syntax all jumbled together. The result is a jumbled mess that comes back to confuse generations of programmers again, and again, and again.

Said programmer with brains damaged from years of slogging away in C, C++, or Java might only really see this after working a bit with simple languages, such as Scheme, and then returning, as I've done with my embedded work. Going back is painful. To quote Gollum's Song:

Where once was light
now darkness falls
where once was love
love is no more

Let's look at one particular example which seems simple, but which is not, and which C and C++ programmers have come to accept. The Unix-Hater's Handbook describes this phenomenon with a quotation attributed to Ken Pier at Xerox PARC, which could also apply to the C family of languages:

"I liken starting one’s computing career with Unix, say as an undergraduate, to being born in East Africa. It is intolerably hot, your body is covered with lice and flies, you are malnourished and you suffer from numerous curable diseases. But, as far as young East Africans can tell, this is simply the natural condition and they live within it. By the time they find out differently, it is too late. They already think that the writing of shell scripts is a natural act."

C has the concept of a struct, which is a sort of low-level record:

struct s_tag {
   int x;
   char y;
};

This defines an aggregate type. If you put names after the definition they define variables of that type:

struct s_tag {
   int x;
   char y;
} s_var_1, s_var_2;

Just like you define instances of an int:

int i_var_1;

You don't actually need a name for the type, unless you want to use it elsewhere; the following is legal:

struct {
    int x;
    char y;
} s_var_1, s_var_2;

However, even given the relative simplicity of this construct, we're already in a twisty maze of language features, all not quite alike! The struct is unusual in C in that it operates in a separate namespace reserved for struct and union tags, kind of like the way Common Lisp uses a distinct namespace for functions. While you normally define an instance of a variable like this (say, at file scope, or as a local variable inside a function):

int my_int;

Given the struct definition:

struct s_tag {
    int x;
    char y;
};

you cannot write:

s_tag s_var_1, s_var_2;

because the struct tag (the part that goes between the keyword "struct" and the opening curly bracket) is not a type in the general C namespace.

To access that namespace, you use the word struct again as a qualifier::

struct s_tag my_struct;

In practice, most C programmers ignore this second namespace, and create a typedef, which makes an alias of the struct tag in the general C namespace. This could be written:

struct s_tag {
   int x;
   char y;
};

typedef s_tag s_type;

but there is a commonly used shortcut, in which wrapping a typedef around the struct declaration changes its interpretation, and instead of defining variables, you are declaring a type:

typedef struct s_tag {
   int x;
   char y;
} s_type;

Since you aren't going to use the tag, you can leave it off altogether:

typedef struct {
   int x;
   char y;
} s_type;

and still use s_type as a type:

s_type my_struct;

Already, as you can see, the struct requires a kind of "little language" within C, with a lot of context-senstivity necessary to parse all this. And people thing Lisp's format is complicated! Other "little languages" include the way in which for loops and switch statements are written.

A "little language" is also known as a DSL, or domain-specific language -- you see them used a lot in Lisp-style programming, and implemented using macros. But if we wanted to try to support these various syntactic and semantic variations using Lisp or Scheme-sytle macros, we couldn't do it -- it isn't just a matter of replacing curly brackets with parentheses; there is no underlying common syntactic form. In other words, comprehending a language like C requires that we constantly change the behavior of the lowest level of the compiler, the parser, in a context-sensitive manner. This makes the full C language quite complex, and don't even get me started on C++. It also imposes a burden on the programmer, which he or she will tend, over time, to forget is there -- read the quotation from Ken Pier again!

There's another way in which structs are special. C supports a special form of initializer, called an aggregate initializer. This lets you specify the contents of a struct on initialization -- that is, when it comes into scope, whether it is file scope or function scope -- but not later, upon assignment, also known as mutation. In other words, the legal syntax changes again depending on context!

This makes it very clear to me that it is highly valuable to teach Scheme first, so that this tortured mess can be understood as it is, rather than as a set of givens about programming in general.

This aggregate initializer syntax can also be used for arrays, unions, and various nested combinations of the above. It also can in particular be used for const variables. For our example:

const s_type my_struct = { 1, 'a' };

If you leave off some of the values, the remainder of the struct will be initialized to zero; aggregate initializers may be nested; dimensions must be specified, or the compiler won't know how much data to supply. All well and good, and commonplace to C programmers. Simple, useful, and aside from some caution you must exercise about alignment and possible holes in the runtime representation, structs generally go about their business quite happily and never hurt anyone. (Of course, this is a lie; this shit causes unanticipated bugs and crashes every day. It would be more accurate to say that at this point we haven't introduced that much complexity, and so experienced developers who have been around the block have learned how to use these language elements with reasonable safety by applying some commonplace "best practices." This isn't the same as claiming that the language truly supports or helps to enforce this reasonable safety).

And then C++ came along.

One of the ways you can initialize objects in C++ is to provide an initializer list in your constructor. This is in fact the required method for initializing members of a class that are const or that are references, which are inherently const. In other cases, it is not required that you initialize members that way, but due to the rules about default member initialization this could mean that if you don't, but assign an initial value in the constructor body, you're wasting effort. Chalk this up to the distinction C and C++ makes between initialization and assignment; somewhat baffling to Scheme programmers, who would understand these both as variants on the underlying concept of binding.

The class could be declared like this:

class my_class {
    const int a;
    const int b;
};

The constructor is declared like this:

my_class( int a, int b );

and defined like this:

my_class::my_class( int a, int b ) :
   member_a( a ),
   member_b( b )
{
    /* body, which is often empty */
}

The initializer list is, essentially, made up of constructor calls.

What do you do if you have a struct in your class?

class my_class {
    const s_type my_struct;
}

Can you initialize it like this?

my_class::my_class( int a, int b ) :
   my_struct( { a, b } )
{
    /* body, which is often empty */
}

Naturally, after using Scheme for a while, I tend to presume that programming languages are at least somewhat regular. There's an aggregate initializer syntax (really, another tiny DSL) that you can use to initialize a struct, right? So can I use it here?

The answer is "no, that would be too easy!"

If you are accustomed to Scheme, you have become used to a language that is relatively regular -- different language forms, which return values, can be used just about everywhere it might make sense to do so. But C++ was not designed like that. There is no underlying syntax that is common despite the changed context.

In particular, although compatibility with C was a major goal of the language design, C++ broke this compatibility in several ways:

1. struct types can be declared directly in the common namespace.

In other words, you can just say

struct s_type {
  /* ... */
};

without having to typedef it, and simply use s_type freely as a type. The typedef struct form still works, but you've introduced an alias for the type; this is not usually an issue since C programmers tend to use prefixes, or suffixes, or some Hungarian-like name mangling to try to keep them straight. This has the side benefit of allowing you to use header files containing the same struct declarations in plain old C, assuming you keep those headers free of other C++-specific code.

2. Structs are classes.

It seems like a strange design decision if a design goal was really to maintain as much compatibility with C++ as possible, but when Bjarne Stroustrup designed C++, he apparently decided that a struct was just a class, with different default access rules (all members are public by default). The C construct known as the union is also a class now, but that's another story for another day.

But despite this surface uniformity, C++ is still a hybrid language. It isn't "objects all the way down," like Ruby, or Dylan, where even an integer is an object, with a class. Which means that a lot of other language constructs act kind of like classes, in some contexts -- except when they don't.

When you read Stroustrup's book The C++ Programming Language, Special Edition, when you are expecing to look at examples of construction and initialization in classes, he often throws in a struct instead. The C++ Standard document often does the same thing. (Warning: reading the C++ Standard document can cause persistent brain damage).

This also means it is perfectly legal to adorn the good old struct with public, protected, and private, and to provide constructors, assignment operators, and various other methods.

In fact, if you want to use a struct as a const member of a class, which means that it must be initialized using the initializer list syntax described above, you must do so by giving the struct a constructor. You can do this inline as follows:

struct s_type {
   int x;
   char y;
   s_type ( const int init_x, const char init_y ) { x = init_x; y = init_y; }
};

Or you can just declare the constructor in the header and place the constructor definition in your implementation file, and you even... wait for it... use the same initializer-list syntax:

struct s_type {
    int x;
    char y;
    s_type ( const int init_x, const char init_y );
}

s_type::s_type( const int init_x, const char init_y ) :
    x( init_x ),
    y( init_y )
{
    /* empty constructor body */
}

And then, finally, in your class-containing-a-struct's initializer list, you can do this:

my_class::my_class( int a, int b ) :
   my_struct( a, b )
{
    /* body, which is often empty */
}

All that syntax, just to initialize a structure member, because Stroustrup decided that initializer lists would actually be lists of constructor calls, except when they aren't quite.

But what if you don't want to bother with that, but just want to set up the value of your member struct in the constructor body, like this:

my_class::my_class( int a, int b )
    /* no initializer list */
{
    my_struct( a, b );
}

The answer is: you can't! Because this isn't initialization; it is assigment. This is true even if the struct member of your class is not const.

However, you can assign your struct in the constructor body:

my_class::my_class( int a, int b )
    /* no initializer list */
{
    s_type temp_struct = { 0, 'a' };   
    my_struct = temp_struct;
}

and this is legal, because it isn't initialization.

If you want to maintain full compatibility with C and expose your header files to a standard C compiler, you will need to perform just this kind of awkward hack to use structs as members. This is apparently what maintaining full backward compatibility with C meant to Stroustrup: that is, it didn't mean as much as indulging his trivial observation that structs behaved like classes with public data members. Sort of.

Or, if you don't need your struct instance to be per-member (and if it is const, you probably don't), you can make it static, which means it is initialized at file scope:

class my_class {
    static const s_type my_struct;
}

const my_class::my_struct = { 0, 'a' };

Do you have a headache yet?

It is surprisingly difficult to get this information out of C++ books, even Stroustrup's books, and the C++ standard document: see the end notes, below. Understanding the usage in C++ basically requires an archaeological excavation of hacks: the original, oddly designed two-namespace struct in C, the common workarounds, the semantics of classes, Stroustrup's somewhat odd mutation of struct into class, and the strict distinction between initialization and assignment. (Not that there aren't a few things in Common Lisp that feels similarly weighted with historic baggage!)

I know this hasn't quite been about Scheme, but I am just trying to point out how C and C++ programmers have come to live with this strange mix of syntax-directed semantics, and semantic-specific syntax, where constructs are legal depening on their context. I've been using C and C++ on and off for about twenty years, but have only very recently fully understood why I can't initialize structs in what seems like the logical, backwards-compatible way. Maybe you think you can just look it up in the index. Good luck! And if you think you can just look this up in the language's BNF, think again!

C and C++ programmers live with these restrictions and special cases every day, but yet think that functional programming in a language like Scheme is somehow hard. It isn't -- it is freedom!

---------------------------

End Notes:

The compiler wasn't cooperating, so I asked myself "does C++ really forbid initialization of a struct member using aggregate initializer syntax (with the curly brackets) in a constructor initialization list?

Stroustrup, The C++ Programming Language, Special Edition p. 101, 234, 809, 818:

Stroustrup actually seems to advocate freely intermixing struct and class depending on your intentions for access control. Regarding initialization of structs, he writes "using a constructor [to initialize a struct] is usually better." But, of course, that breaks compatibility with one of the simplest but most highly useful tools of C, and the struct was never designed to support object-oriented programming.

Since the struct "tag" is promoted to a type in the general namespace, in order to maintain compatibility with C, which is broken anyway, there is a further workaround: although there is not distinct namespace for structs, you can have a struct and non-struct type with the same name declared in the same scope, but the non-struct will take precedence unless you disambiguate with the prefix "struct." Stroustrup's examples complicate things even further by disambiguating using namespaces, which are another feature not present in C.

According to Stroustrup's somewhat limited version of the grammar of C++, there isn't any aggregate initialization in mem_initializer_list (p. 810), but the grammar is not complete. Page 247 seems to indicate that items in the member initializer list in the constructor definition are all constructor calls, given that even POD members (plain old data, like int and char and float and pointers to these types) can be initialized with this constructor call syntax.

In C++ Std. section 8.4: the grammar shows ctor-initializer and mem-initializer-list (where "mem" means "member.") This is described in 12.6.2 and seems to break down further into the formal grammar into class names and parameter lists, which seems to indicate that these are all constructors, but again this does not seem to be a complete syntax for C++. Good luck trying to find a complete grammar for C++!

A New Planet Scheme!

2006-04-04T21:49:00.000-04:00

Planet Scheme is reborn at http://www.scheme.dk/planet/ and this blog is now syndicated. Thanks for aggregating me! Time to get back to my Sudoku solver, or take a diversion into another program.

Planet Scheme off the Air?

2006-03-15T11:31:00.000-05:00

Planet Scheme seems to be defunct.

Presumably this means they won't be aggregating this blog, so I guess I can stop asking!

Thinking about Sudoku and Scheme, Part 5.1

2006-02-09T11:53:00.001-05:00

Just a brief post today. I have been too busy to do much on my Sudoku solving program itself, but I did spend some time polishing up my array2D library. With revision this library has finally assumed what I feel is its "natural" shape. The optimal design was not clear at the outset, but with some use I feel I've discerned the implementation that minimizes the amount of redundant code and thus the number of places that possible errors may be hiding. I'm sure it could be even more concise; I have a feeling that a little macro magic could cut the lines of code in half, but the shape of that implementation has not yet become clear to me, and I have an allergy to using techniques that don't provide a clear advantage.

It is really quite a simple library, but in order to provide some assurance of correctness, I also wrote a series of PLT Scheme test cases. I have not figured out how to use DrScheme to tell me if this test suite covers all of the code, or if this is even possible, but it is at least nearly complete.

The library does not do meaningful error-checking. Scheme textbook code rarely does anything by way of error-checking. As a result I'm deficient on strategies I could use to address this, especially when trying to write to RSR5.

It isn't possible to code around every conceivable error. For some applications, it makes sense to perform verification any time data is read from or written to memory. We can't operate at that level. We also shouldn't put in effort to detect flaws in the implementation itself. Given our partially functional approach, in which we don't update any top-level definitions, there aren't a lot of unexpected states our library can get into. We should focus our attention on the response to incorrect inputs. There are only a couple of classes of errors that the library should expect:

1. The set of array boundary errors. Because coordinate pairs are mapped to a single index on a vector, many of possible boundary errors will result in an incorrect cell being set or get. Only cell references that exceed the internal representation will generate a meaningful run-time error, and this error will not tell us if the x or y index was out of bounds.

2. The set of errors that can arise from receiving an incorrect value-generator or mapping function. In Scheme, a function signature really consists only of the name and the number of parameters, and does not include type information about the parameters. Supplying an incorrect number of parameters will be caught with a meaningful error at run-time but because the passed functions may be called via several levels of indirection, and the function may not be bound to a named variable, it may be difficult to glean from the error message just what has gone wrong. (Another way to say this is that DrScheme has thrown away too much context information).

Type errors are potentially more insidious, but in my implementation these functions will tend to receive an array (vector), integer indices, and possibly another function. The result of doing a vector access on an integer or function, or treating a vector or function like an integer, should at least fail fast with a moderately meaningful error.

There are richer language constructs that could address these problems. For example, either Common Lisp or Dylan would allow me to specify type information for the parameters. The runtime is then capable of flagging type errors as soon as they happen, or better yet, verify type safety across functions and generate code that operates on POD (plain old data). Dylan also supports limited types, although implementation support in Gwydion's d2c is spotty. Limited types would allow range checking further upstream. Of course, if I wrote this program in Common Lisp or Dylan, I would not bother simulating an array. If our language supported exception handling, I could wrap the top-level operations to catch exceptions without too much modification inside all my functions.

Another approach to bounds-checking in my 2-D array would be to encapsulate the array data together with metadata on its x and y dimensions. I am doing this to a limited extent with the closure generation, but the captured x-dimension is not used to validate that the x-index is within bounds. Other array implementations use a record or a closure to wrap up the representation itself. But then it is more difficult to display the contents of the array, and if we are going to start down that road, we might as well try to generalize our library for an n-dimensional array. That seems like overkill, so for now we will call array2D complete as it is.

Interesting Embeddable Languages

2006-01-31T16:11:00.000-05:00

There are a few languages I am paying particular attention to these days.

The first is Scheme; that's the language I'm using for my Sudoku experiments.

The second is Lua. Lua is a light language that includes a byte code compiler and interpreter. It is designed to have a small implementation footprint and to interface well with C. It has lightweight threads. Lua's home is at http://lua.org.

The third is Io. Io has a syntax that looks a bit weird, unless you're familiar with Smalltalk. I've never used Smalltalk, but I have used NewtonScript. The prototype-based inheritance scheme used in Io reminds me of NewtonScript's inheritance, although Io does not support dual chains. It may not be quite portable enough to move over to an arbitrary platform, but I won't know for sure until I try. Io's home is at http://iolanguage.com.

And then there is Ruby. Ruby is not quite so lightweight, but it is designed to be embeddable; it would not be my first choice, though, because it does not have a well-tested compiler or byte code runtime. It has too little regularity in its syntax (otherwise known as "too much syntax"), and uses sigils, which I don't like except as convention, as in Dylan, but as far as I'm concerned for usability it beats Perl hands-down. I prefer it to Python for no particularly good reasons other than Python's use of whitespace, which is a relatively trivial feature, and Guido's apparent hostility towards fully usable lexical closures. Ruby's home is at http://ruby-lang.org.

Ruby's support for higher-order functions has the side effect of making it serve as an acceptable dialect of Lisp, even without an exact equivalent of Lisp macros. I was able to bring up my basic Sudoku code in just a couple of hours using Ruby. Ruby is great for rapid prototyping and the standard libraries "feel" just the right size. There's some lessons here to inform future generations of Lisp, if the Lisp community is willing to listen to them.

There are some Forth-inspired languages that are also interesting; I am a fan of Forth, and consider it to be the "other" programmable programming language. Joy (http://www.latrobe.edu.au/philosophy/phimvt/joy.html) is a sort of functional variant on Forth.

Thinking about Sudoku and Scheme, Part 4

2006-01-30T15:22:00.001-05:00

Last time I wrote:

Now we've got our given board and our candidate board, and we can start smashing them together to shake out candidates, and begin finding values to go in our boxes.

So let's do that. But first, I need to confess something. You may have found yourself wondering "You already have a data structure that contains the givens and their coordinates. Why make the given-board vector at all?" If you wondered that, congratulations. You're paying attention, possibly more than I am, and working towards writing code that is simple.

So what's the answer? The answer is "I don't have a good reason; the code just grew that way, and has not been optimally cleaned up yet." As I write this code, I'm learning to use Scheme more effectively. It has been an iterative process. Right now I'm in the part of the cycle that is excited to have the code successfully working on the first part of the Sudoku board solution. At some point I'll probably be in the part of the cycle that wants to rip up the code and make it smaller and simpler. Scheme lends itself well to stepwise refinement. This is both a blessing and a curse. A blessing, because it is easy to rewrite your code. In C++, assuming your design is not visibly horrible and doesn't crash, it is generally too painful to redo all those interfaces and class definitions and so working code often doesn't get improved unless there is a burning need. Scheme, especially if it is written in an appropriate functional style, is easy to improve locally. This also means that you can always improve it some more, and fall into the trap of improving it endlessly without solving an actual problem. That's the curse.

OK, now let's get to the meaty part, keeping in mind that this is code in progress. Here's how we map the givens and use them to cancel the first round of candidates. From the top:

(cancel-givens
(make-given-board given-list)
(make-initial-candidate-board))

Simple enough so far, right? Now we just have to define cancel-givens, and we're done.

(define cancel-givens
 (lambda (given-board candidate-board)
   (map-board-coordinates-elts
    given-board
    (lambda (x-idx y-idx elt)
      (if elt
          (cancel-given
           candidate-board x-idx y-idx elt))))
   candidate-board))

We know roughly what that map function is going to look like; it will call a function with the coordinates and elements of the given board. Now we just need to define cancel-given, and we're done. here's cancel-given. This one is big (most likely it could and should be further simplified):

(define cancel-given
 (lambda (candidate-board x-idx y-idx given)
   (reduce-candidate-list-to-given!
    candidate-board x-idx y-idx given)
   (letrec ((filtered-neighborhood-unique-coordinates-list
             (make-filtered-coordinate-list
              (get-unique-neighborhood-coordinates
               x-idx y-idx) (list x-idx y-idx)))
            (candidate-remover
             (make-candidate-remover given))
            (coordinate-list-handler
             (lambda (coordinate-list)
               (if (not (null? coordinate-list))
                   (begin
                     (candidate-remover
                      candidate-board
                      (caar coordinate-list)
                      (cadar coordinate-list))
                     (coordinate-list-handler
                      (cdr coordinate-list)))))))
     (coordinate-list-handler
      filtered-neighborhood-unique-coordinates-list))
   candidate-board))

Let's look at this one in a little more detail. Remember that this is called with each given. The first thing we do is turn the candidate list in the box with the given to a list containing only the given. Maybe that isn't the best representation, but it will do for now:

(define reduce-candidate-list-to-given!
 (lambda (candidate-board x-idx y-idx given)
   (set-board-elt!
    candidate-board
    x-idx y-idx
    (list given))))

Note that this is not strictly functional in style. I have tried to move over to a functional style, but my roots are still in imperative programming, so a fully functional, referentially-transparent implementation does not come naturally quite yet. In general, I am at a bit of a loss for good idioms to handle the gamut of solving strategies on the board over time without introducing mutation, but that is probably from lack of experience in purely functional programming techniques and data structures. I could keep regenerating the whole board, but that seems strange to me. I may explore a stricter functional design in a future version.

Meanwile, let's continue on and look at the next task, which is to remove the given from the entire neighborhood. Recall that the neighborhood of a box is the combined row, column and grid. We want a list of coordinates. Simply combining the coordinates for the row, column and grid will generate duplicate sets of coordinates; we also don't want to process the box itself, or we'll remove the given we just set. So we first use get-unique-neighborhood-coordinates:

(define get-unique-neighborhood-coordinates
 (lambda (x-idx y-idx)
   (let ((grid-bounds
          (map-coordinates-to-grid-bounds x-idx y-idx))
         (acc
          (make-unique-coordinate-accumulator)))
     (map-board-row-coordinates y-idx (car acc))
     (map-board-col-coordinates x-idx (car acc))
     (map-board-subarray-coordinates
      (car grid-bounds)
      (cadr grid-bounds)
      (caddr grid-bounds)
      (cadddr grid-bounds)
      (car acc))
     ((cadr acc)))))

The function map-coordinates-to-grid-bounds uses a little bit of Scheme math to determine the bounds of the 3x3 grid our box is in. Here's how I do that:

(define map-coordinates-to-grid-bounds
 (lambda (x-idx y-idx)
   (list (get-grid-lower-bound x-idx grid-x-dim)
         (get-grid-upper-bound x-idx grid-x-dim)
         (get-grid-lower-bound y-idx grid-y-dim)
         (get-grid-upper-bound y-idx grid-y-dim))))

And here are the helper functions:

(define get-grid-lower-bound
 (lambda (idx dim)
   (* dim (floor (/ idx dim)))))

(define get-grid-upper-bound
 (lambda (idx dim)
   (- (* dim (ceiling (/ (+ 1 idx) dim))) 1)))

The particulars of Scheme math require some care if you want to make sure you get a whole number result rounded in the direction that you want. If you're used to using languages that don't do exact fractions, this may seem like too much work. This way seems to work, though, so we will move on for now.

Next, we use an accumulator (created by make-unique-coordinate-accumulator) to collect up all the coordinates. This isn't a numeric accumulator, but a list accumulator: when we create it, it holds a reference to an empty list, and as we call it with coordinates, the list is assembled. Our accumulator generator looks like this:

(define make-unique-coordinate-accumulator
 (lambda ()
   (let ((coordinates (list)))
     (list
      (lambda (x-idx y-idx)
        (if (not (member (list x-idx y-idx) coordinates))
            (set! coordinates
                  (cons (list x-idx y-idx) coordinates))))
      (lambda ()
        coordinates)))))

This is again not strictly functional; in a more functional style, we'd probably generate a new accumulator with a new list created from the previous one. But then the client that held the accumulator would have to mutate its binding in order to get the new accumulator, so it would have to be strictly functional as well -- a sort of viral strict functionality would require rewriting all the upstream code. Something to think about!

This is yet another function generator, with a twist. We use a let to create a binding for a list, called coordinates. This is the list that will accumulate the coordinates. The actual return value of the function is... another list! This time, a list of two functions. The first function in the list receives coordinates and if the coordinate pair is not already present in the closed-over list, as determined by member, we destructively set coordinates to be the list with the new coordinate pair prepended. The second function in the list doesn't look like a function at all; in fact, it consists only of:

(lambda ()
 coordinates)

All that does is return the value held in the binding named coordinates. It's the rough equivalent of a return statement in C, C++, or Java. The important thing to note here is that both of the functions in the list we return contain a reference to coordinates. The binding in question is the one that is in lexical scope when the lambda form is executed. Note that we could stuff these functions inside some other data structure; we could even put them in a single cons cell using set-car! and set-cdr! But for now I am still using the list as my "Swiss Army Knife" data structure, so we'll use that.

Returning to the innards of get-unique-neighborhood-coordinates let's look at what happens next:

(map-board-row-coordinates y-idx (car acc))
    (map-board-col-coordinates x-idx (car acc))
    (map-board-subarray-coordinates
     (car grid-bounds)
     (cadr grid-bounds)
     (caddr grid-bounds)
     (cadddr grid-bounds)
     (car acc))

I'm applying my accumulator to the row, the column, and the subarray. The map functions are unexceptional; they are wrappers around my 2D array implementation. To pass the four parameters that constitute the bounding rectangle of the subarray, I'm again using those all-purpose list functions car, cadr, caddr, and cadddr. These simply correspond to retrieving the first, second, third, and fourth element in a list. Actually, in RSR5 Scheme you can rewrite this to use first, second, third, and fourth if you want to, but older textbooks generally use the composed list abbreviations, so I will stick with them for now; rather than just use clearer names, if I rewrite this to get rid of the composed list functions, I'd rather use a self-documenting data structure of some kind.

The last expression in the function is the return value. Don't overlook its importance:

(cadr acc)

This actually calls the function contained in the second element of our accumulator list, which will retrieve the contents of the accumulator. Since it is the last expression in the function, get-unique-neighborhood-coordinates will return its value.

Now we're back in cancel-given. The next thing we do is call make-filtered-coordinate-list on our unique list. We do this to remove the box containing our given, so that we don't wind up removing that candidate as well:

(define make-filtered-coordinate-list
 (lambda (coordinate-list coordinate-pair)
   (if (null? coordinate-list) (list)
       (if (not (equal?
                 coordinate-pair (car coordinate-list)))
           (cons (car coordinate-list)
                 (make-filtered-coordinate-list
                  (cdr coordinate-list) coordinate-pair))
           (make-filtered-coordinate-list
            (cdr coordinate-list) coordinate-pair)))))

This function is a textbook case of filtering out one member from a list, returning a new list. The key implementation detail here is that it recursively walks the list, building up a new list as it goes. As it stops to examine each element in the list, if it is not the equal to the item in question, it goes ahead and conses it on to the generated list; if it is, the element is not consed, and we just continue to recurse. You can see similar examples in The Little Schemer. Note that this function counts on the fact that equal? works properly on data structures that are not atoms and on atoms that are different objects in memory. In Scheme, Lisp, and other dynamic languages -- basically, as soon as you get away from "unboxed" primitive data types -- equality is a complex subject!

OK, are you still with me? We've got a list of the coordinates for the neighborhood we're examining. Next, we make a candidate remover, which is another function generator; when you pass it a candidate, it removes it from all the candidate list. That should be straightforward enough by now, so I won't belabor it. So, does it work?

Well, of course, it did not work on the first try. Or the second or third try! In fact, while I have presented this design top-down, I actually wrote it using a much more realistic mixture of top-down and bottom-up design. Sometimes the higher-order algorithm will be clear. This is often best worked out on paper. The cancel-givens and cancel-given function started out as a stub that called stubs. To test the implementation function-by-function, the stubs just returned fixed values. These were later fleshed out with real code. As I implemented more functions, I found that certain other function definitions seemed to naturally fall out, so wrote those next. Meanwhile, had already gone "bottom up" in the process of writing my 2D array functions, so my implementation hooked up in the middle. Then there was a bit of "impedance mismatch," where the functions I thought I would need turned out not to be precisely the functions I did need. I wound up iterating in both the "bottom up" and "top down" directions multiple times before getting even to this point. But using the DrScheme listener, turnaround on this kind of iteration is very quick.

The result of removing all the givens from the board, and crossing off candidates in the neighborhood of each given as I go, is a candidate-board vector that looks like the one below. A list of only one value indicates that the value has been solved. I have formatted the output lightly to make the rows a little more clear, and I have marked the initial set of givens in bold:

(#81
((2 3 7) (3 8) (2 3 7 8) (2 3 4) (6) (5) (2 3 4 8) (9) (1)

(1 2 3 6 7) (1 3 6 8) (2 3 6 7 8) (2 3 4 9) (2 3 7 8)
(2 3 7 8 9) (5) (4 6 8) (2 3 4 6 8)

(4) (5) (9) (1) (2 3 8) (2 3 8) (2 3 8) (7) (2 3 6 8)

(2 5 6) (4 6 8) (2 5 6 8) (2 5) (9) (1 2 7) (1 2 4 8)
(3) (2 4 6 8)

(2 3 5 9) (3 4) (1) (8) (2 3) (6) (7) (4 5) (2 4 9)

(2 3 5 6 9) (7) (2 3 5 6 8) (2 3 5) (4) (1 2 3) (1 2 8 9)
(1 5 6 8) (2 6 8 9)

(1 3 7) (9) (3 7) (3) (1 3 8) (4) (6) (2) (5)

(1 3 5 6 7) (1 3 6) (4) (2 3 6 9) (1 2 3 8) (1 2 3 8 9)
(1 3 8 9) (1 8) (3 7 8 9)

(8) (2) (3 6) (7) (5) (1 3 9) (1 3 4 9) (1 4) (3 4 9))

Note that there were 28 givens. The next important question to ask is "did we find any more solved boxes?" That is, did we reduce the candidate list in any of the non-given boxes to a length of 1, indicating only a single possibility in that box?

If you look closely, you will notice that, in fact, we have solved some boxes, simply by crossing out the givens and following through on the implications of those givens for the boxes in the neighborhood of each given. In the third-from-last row, which would be row 6 in our zero-based indexing, we see that there is a single 3 candidate in one of the candidate lists. This was not a given:

(1 3 7) (9) (3 7) (3) (1 3 8) (4) (6) (2) (5)

However, our code did not yet discover that we have made more progress. In the next installment, we'll look at how the code can make that discovery, and what the implications are. We'll also look how to apply some slightly less elementary solving rules to the board.

Practical Subversion and Other Subversive Practices

2006-01-30T12:34:00.000-05:00

Since I'm a fan of the book Programming Ruby, I purchased the two Pragmatic Programmer books, Pragmatic Version Control Using CVS and Pragmatic Version Control Using Subversion. I was planning to use them as a quick refresher to CVS and a quick cross-introduction to Subversion, since I have a couple of years of experience using (and occasionally fixing) CVS repositories, and also have used a couple of other tools including MKS RCS, Voodoo, and (a little bit of) ClearCase, and we are implementing a Subversion repository at work.

I wound up returning the books to the store, though. I would recommend either of them to someone who is new to both tools, but they are too light for someone who has already used one of these version control systems extensively.

For CVS, there are plenty of free texts available online, including the venerable Cederquist, which is a bit hard to use as a tutorial, and the Fogel and Bar book (at http://cvsbook.red-bean.com/). I have the second edition in the dead tree edition; the third edition is available free online. If you like it, buy a paper copy.

For Subversion, although there are some free texts available, I decided that Practical Subversion, by Garrett Rooney, is the right text, on the right level, at the right time, for me. The chapter on best practices alone helps differentiate it from other books which tend to be organized around a command-line options reference. We'll see how it holds up as I gain a little more experience with Subversion.

I also picked up a copy of The Reasoned Schemer. I am a big fan of The Little Schemer and The Seasoned Schemer, although I must admit I have not completed The Seasoned Schemer.

I also started reading A Little Java, a Few Patterns, which is an effort to teach functional and recursive programming using Java. Given that I had a lot of Java experience and had already thought a lot about design patterns, it seemed like a strange and forced hybrid, so I decided not to bother with it and just work on Scheme instead. The book may be interesting to developers who know Java and who would like to begin to understand Scheme.

I am now re-skimming The Little Schemer as a warmup to the new book on logic programming. I've been interested in learning Prolog for a while now but have not gotten much past reading part of Clocksin and Mellish's book Programming in Prolog, 5th ed. Given that I'm currently learning Scheme, implementing a Prolog-like language in Scheme might be the impetus that I need. If I get enough time to work on it I will report on what I find.

Thinking about Sudoku and Scheme, Part 3

2006-01-27T17:50:00.001-05:00

OK, so I've given you a small view of one part of the array2D library and how it is implemented. Now let's look at my Sudoku solver from the top. Note that this is a hobby project, done in the rare scraps of free time I am able to piece together these days, by a relative novice in Scheme. In other words, it is not finished, polished, textbook work, so be kind.

Let's review what Sudoku is and consider some of the most elementary solving strategies. First, terminology. These are the terms I use; some are borrowed and some are my own. Other Sudoku geeks may use alternate terminology.

Box: the smallest unit; a single space for a number. I identify boxes using zero-based x, y coordinate pairs.

Open box: a box that does not have a number in it yet.

Coordinates: on a 9x9 grid, which does not represent the only possibility in Sudoku, the top row goes from (0, 0) to (8, 0) and the rightmost colum goes from (8, 0) to (8, 8).

Given: one of the numbers already provided in the puzzle.

Grid: in a 9x9 Sudoku puzzle, one of the 9 3x3 sub-parts; on a 16x16 puzzle, one of the 16 4x4 sub-parts, etc. Grids are not necessarily square; some published puzzles could contain 4x3 grids, for example.

Virtual row: a single group that must contain the set of possible numbers (in a 9x9 puzzle, 1 through 9). Note that each box is actually part of three virtual rows: its row, column, and grid.

Number set: for a 9x9 puzzle, the integers 1 through 9. I have seen Sudoku boards that allow the numbers 1 through 12, 1 through 16, 1 through 25, and 1 through 49. Sometimes letters are used: for example, the numbers 1 through 16 can be encoded using the hexadecimal digits 0..F (or 1..G), and the numbers 1 through 25 can be encoded by the letters A..Y. There are more exotic Sudoku involving the letters that make a specific word, but this is really just an encoding issue and does not fundamentally change the rules.

Sudoku rule: there is probably a good formal expression of this, but informally speaking, the Sudoku rule says that each box in each virtual row must contain one of the numbers in the number set.

By implication, each box cannot contain a number that is not a member of the number set; it also cannot contain a duplicate of another number in the same virtual row; in a completed puzzle each virtual row must be filled, which means the whole puzzle must be filled.

If you find that a puzzle you are working on seems to break this rule, either the puzzle was not valid to begin with, or you have made a solving error. The second case is more likely, but I have found errors in published puzzles.

There are several possible types of errors. The givens may violate the Sudoku rule, which will lead to an insoluble puzzle, or more than one solution may be possible, which could lead you to find a solution that follows the Sudoku rule but which does not match the published solution.

Candidate: one of the possible values that could legally be written in a box.

On an empty 9x9 grid, each box has as its candidates all the numbers 1 through 9, so no progress can be made towards a solution.

When the givens are taken into account, the set of candidates in the remaining open boxes in the neighborhood must be reduced to maintain the Sudoku rule. As the puzzle is filled in, the candidates are reduced further.

As you perform logical deductions on the board, you will remove candidates; when only one candidate remains for a box, the number should be written down and the candidates for boxes elsewhere in the neighborhood must have that number removed; repeat until no open boxes remain. (This is actually in a nutshell the algorithm for solving any Sudoku puzzle, and translates directly into the main loop of a computer solution that uses human solving techniques rather than testing every possibile chain of possibilities).

Noncandidate: instead of writing down candidates as you work on the puzzle, you could also write down noncandidates: that is, numbers that have been ruled out for each box. When the set of noncandidates for a given box leaves only one remaining candidate in the number set, you can write down that possibility, and you must then add this number this to the sets of noncandidates elsewhere in the neighborhood. You could represent noncandidates by writing them down directly, although this can be confusing, or writing down the number set in each open box and crossing out numbers as they become noncandidates.

Single Candidate: the case when one candidate remains in a box; once you recognize this case, you should write in the number; the box is solved, you should then make sure to reduce the candidates in the neighborhood. Which brings us to another term.

Neighborhood: the combined row, column, and grid that contains a given open box. Neighborhood is a distinct concept from virtual row because if a number appears anywhere in the neighborhood containing a given box, it cannot be a valid candidate for the box; this is because the Sudoku rule applies to each box three ways.

Basic Solving Strategies

For demonstration purposes, we will use the following 9x9 puzzle (taken from _Sudoku: Easy to Hard Presented by Will Shortz_ Volume 3):

-------------------------
| 9 . 8 | 3 . . | 7 4 2 |
| . 4 . | 5 8 . | . 9 . |
| 2 . . | . 7 . | 1 . 8 |
-------------------------
| . . 6 | 2 9 4 | 8 3 . |
| 4 8 . | . . . | . . 1 |
| 3 7 . | 6 . 8 | . 2 . |
-------------------------
| . 3 . | . 5 6 | . . . |
| 6 . . | 1 . . | . 8 3 |
| . 2 . | . . 3 | . 1 5 |
-------------------------

Let's look at how we might represent this board in Scheme, and then start coming up with functions to operate on it.

To allow my solver to be configured for different board sizes and grid dimensions, we'll provide bindings for the independent dimension values:

(define max-box-value 9)
(define board-x-dim 9)
(define board-y-dim 9)
(define grid-x-dim 3)
(define grid-y-dim 3)

To start solving our sample puzzle, let's use the following algorithm:

1. Make a given board. A given board is a board array that contains only the givens. Here are the givens, as a list of list, where each list contains a coordinate pair as a list and a value:

(define given-list 
  '(((4 0) 6) ((5 0) 5) ((7 0) 9) ((8 0) 1)
    ((6 1) 5)
    ((0 2) 4) ((1 2) 5) ((2 2) 9) ((3 2) 1) ((7 2) 7)
    ((4 3) 9) ((7 3) 3)
    ((2 4) 1) ((3 4) 8) ((5 4) 6) ((6 4) 7)
    ((1 5) 7) ((4 5) 4)
    ((1 6) 9) ((5 6) 4) ((6 6) 6) ((7 6) 2) ((8 6) 5)
    ((2 7) 4)
    ((0 8) 8) ((1 8) 2) ((3 8) 7) ((4 8) 5)))

Here's a function which will make a given board:

(define make-given-board
  (lambda (given-list)
    (let ((given-board 
           (make-vector (* board-x-dim board-y-dim) #f))
          (setter! (array2D-make-setter board-x-dim)))
      (letrec ((do-write-givens
                (lambda (puzzle-array givens)
                  (if (not (null? givens))
                      (begin
                        (do-write-givens 
                         puzzle-array (cdr givens))
                        (setter! puzzle-array 
                                 (caaar givens) 
                                 (cadaar givens)
                                 (cadar givens)))))))
        (do-write-givens given-board given-list))
      given-board)))

This is a pretty simple function, but let's look at a couple of points. First, the default value of our vector is #f, the canonical "false" value. This has no real purpose other than allowing us to use the elements of this array act as an argument to Scheme's if or cond and give the expected results. We've already seen how to use letrec to create a self-recursive helper function; we already know how the curried setter! function works. The body of this function is a pretty straightforward example of recursion over a list. The arguments we pass to setter! are a little more interesting:

(setter! puzzle-array 
              (caaar givens) 
              (cadaar givens)
              (cadar givens))

These primitives provide shortcuts for expressing combinations of car and cdr, and are read inside out from right to left; caaar becomes (car (car (car ...))), cadaar becomes (car (cdr (car (car ...)))).

An aside: I have a love-hate relationship with these constructions. On the one hand, they allow you to do quick deconstruction of arbitrary list structures, and that's a good thing because lists are very quick and dirty and you can easily put together data structures using lists. On the other hand, they allow you to do quick deconstruction of arbitrary list structures, and that's bad because they are not self-documenting in any way and nothing in them is named. Using something like a plist or record type is probably a better idea, so I will consider that later; Common Lisp provides destructuring, which would also be a valid option because it is self-documenting.

Anyway, that will build a given board. Now let's build a candidate board. The initial candidate list can be easily generated using another function:

(define make-initial-candidate-list
  (lambda ()
    ((lambda (max)
       (letrec ((make-candidate-list
                 (lambda (count)
                   (if (> count max) (list)
                       (cons count 
                             (make-candidate-list 
                              (+ count 1)))))))
         (make-candidate-list 1)))
     max-box-value)))

I'm going to wrap this up in the form of a value generator. A value generator is a function that receives x and y indices and returns a new value for the board. In this case our value generator will ignore the parameters:

(define initial-candidate-value-generator
  (lambda (x-idx y-idx)
    (make-initial-candidate-list)))

Now we can use our set-board-elts primitive, which is a curried array mapping function, to fill in the candidates. Each box gets a list containing the full set of candidates:

(define make-initial-candidate-board
  (lambda ()
    (let ((candidate-board 
           (make-vector 
            (* board-x-dim board-y-dim) '())))
      (set-board-elts 
       candidate-board initial-candidate-value-generator)
      candidate-board)))

Now we've got our given board and our candidate board, and we can start smashing them together to shake out candidates, and begin finding values to go in our boxes. More on that next time.

Version Control Systems

2006-01-27T15:52:00.000-05:00

I've had a fair amount of experience using CVS, but not for a couple of years ago. Recently I have been investigating version control systems again. One scenario I wanted to investigate was the following. Assuming a tree of files like this:

A/
  B/
    foo.cpp
    foobar.cpp
C/
  D/
    bar.cpp
    barbaz.cpp

From this, we want to be able to checkout the following to a sandbox directory with a single checkout command:

F/
  foo.cpp
  bar.cpp

If you're a CVS or svn user, go along with me for a moment and assume that this is a valid thing to want to do.

Unfortunately, it seems to be impossible.

What about CVS modules?

Well, I would summarize what modules can do by saying that upon checkout, the use of modules can collapse existing directory hierarchy, or add directory hierarchy that does not exist in the repository, or place directories in places where they don't exist to start with, but they fall short of allowing you to arbitrarily rearrange the tree, and they won't rearrange files. This is probably in part because of the ways in which metadata is stored on disk for CVS sandboxes: it goes into your directories, even though CVS does not treat directories in general as first-class citizens.

Here is what you can do with modules:

Alias modules will simply allow you to use a different name for an existing module or path. When you check out, all intermediate directories will be created. For example:

r5rv_alias_dirs -a r5rv/a/b r5rv/c/d

Will give you:

r5rv/
     a/
       b/
         foo.cpp
         foobar.cpp
     c/
       d/
         bar.cpp
         barbaz.cpp

Regular modules let you label all or some of the files in a directory with a module name. For example, this will get only the files indicated and write them in a directory with the name of the module, generating no intermediate directories in the output:

r5rv_foo r5rv/a/b foo.cpp

# This will give you:

r5rv_foo/
         foo.cpp

Leaving off the filename will get you all the files in the specified subdirectory:

r5rv_b r5rv/a/b

giving you:

r5rv_b/
       foo.cpp
       foobar.cpp

Note that for regular modules you can't put multiple directories on the same line, or CVS gets confused.

If you want to put specific files or the contents of specific directories together, you have to use ampersand modules. But: when CVS writes out ampersand modules, it addes the module names to the directory structure! So, given:

r5rv_bar r5rv/c/d/ bar.cpp
r5rv_foo_bar &r5rv_foo &r5rv_bar

Checking out r5rv_foo_bar will give you:

r5rv_foo_bar/
             r5rv_foo/
                      foo.cpp
             r5rv_bar/
                      bar.cpp

Not quite what we want.

You can exclude directories when defining an alias module. For example:

r5rv_no_c -a !r5rv/c r5rv

will give you only:

r5rv/
     a/
       d/

Note that if you already have r5rv checked out from the module r5rv_alias_dirs above, CVS will not remove the contents of c/, so it would be best to remove your local sandbox version of r5rv before checking out this new module.

So can we achieve an output dir like:

r5rv_proj/
          f/
            foo.cpp
            bar.cpp

I don't think CVS can do this directly, but we come close, if we're willing to accept intermediate directories around our individual files. Using as a model the r5rv_foo_bar module above, we can change it to rename the working directory to something other than the module name:

r5rv_foo_bar_renamed -d r5rv_proj &r5rv_foo &r5rv_bar

We get:

r5rv_proj/
          r5rv_bar/
                   bar.cpp
          r5rv_foo/
                   foo.cpp

What if we wanted to fix up this hierarchy with a post-checkout script? Well, assuming we can guarantee the script will run on the client, if we have a script that will move our files, we can specify that we want a script to run by defining a module like this:

r5rv_post -o combine.sh -d r5rv_proj &r5rv_foo &r5rv_bar

This gives us what we want, but there is one problem: we have not properly preserved the contents of the CVS metadata directories. This means that CVS no longer knows what directory foo.cpp and bar.cpp belong to, and will be generating all kinds of errors when, for example, doing a status check or update. There are some workarounds that can be put into place using .cvsignore files, and I suppose that if I was feeling ambitious I could write some scripts that would actually run sed on the metadata files in the CVS subdirectories, but it should be obvious that this solution would be ugly and brittle.

So what about Subversion?

In Subversion, when you commit your initial structure, you can do something like this:

original:

a/
  b/
     foo.cpp
     foobar.cpp
c/
  d/bar.cpp
     barbaz.cpp

Let's say you want to be able to mix-and-match these into your output. You can check them in to svn as separate projects. Easily done:

svn import ./a file:///cygdrive/e/repo-svn/r5rv-a -m "initial"
svn import ./b file:///cygdrive/e/repo-svn/r5rv-b -m "initial"

Now you want to create a directory that will contain both of them upon checkout:

mkdir r5rv-proj
svn import ./r5rv-proj file:///cygdrive/e/repo-svn/r5rv-proj -m "initial"

Then over in your workspace, you check out that empty directory: the last parameter is the name to give it in your workspace:

svn checkout file:///cygdrive/e/repo-svn/r5rv-proj r5rv-proj

Now you have a working copy of an empty directory (something that is impossible in CVS!) You want to add a svn:externals property to it. This consists of a set of svn URLs for things that should be retrieved here when the directory is checked out. You can do this with svn propset, but since you want one local directory name and one svn URL per line, you can't really do it directly on the command line. Instead you can do something like

echo "r5rv-a file:///cygdrive/e/repo-svn/r5rv-a" >> props
echo "r5rv-c file:///cygdrive/e/repo-svn/r5rv-c" >> props

Check that it looks right:

$ cat props
r5rv-a file:///cygdrive/e/repo-svn/r5rv-a
r5rv-b file:///cygdrive/e/repo-svn/r5rv-b

then set the externals property using -F, which means read from a file, like so:

$ svn propset svn:externals -F props r5rv-proj/
property 'svn:externals' set on 'r5rv-proj'

You can confirm the property has been set:

$ svn propget svn:externals r5rv-proj
r5rv-a file:///cygdrive/e/repo-svn/r5rv-a
r5rv-b file:///cygdrive/e/repo-svn/r5rv-b

Clean up:

$ rm props

OK, now commit:

svn commit r5rv-proj/ -m "added external property"

And update:

svn update r5rv-proj/

You see something like this:

Fetching external item into 'r5rv-proj/r5rv-a'
A    r5rv-proj/r5rv-a/b
A    r5rv-proj/r5rv-a/b/foo.cpp
Updated external to revision 4.

Fetching external item into 'r5rv-proj/r5rv-c'
A    r5rv-proj/r5rv-c/d
A    r5rv-proj/r5rv-c/d/bar.cpp
Updated external to revision 4.

That's a lot of work! But the model is actually simpler than elaborate use of entries in the modules file. In addition, under svn, a non-privileged user can make this change (that is, a user with ordinary write access, rather than administrator access). And more importantly, these changes are all versioned; under CVS, if you want to use those module definitions, you have to make sure that the paths specified in the modules don't change, or the modules file will be out of sync with the repository structure. This is a general problem with CVS, which is not really designed to cope well with restructuring the repository.

Now your local project looks like this:

r5rv-proj/
          r5rv-a/
                 b/
                   foo.cpp
          r5rv-c/
                 d/
                   bar.cpp

Which is pretty close to what we want, taking into account the fact that neither CVS nor svn seems to be able to write individual files from different repository locations to the same output directory in the working copy.

However, there are a couple of things to keep in mind about the svn solution. First, your external links have to be complete svn URLs. That is, they can't be relative URLS to directories in the same repository [see note 1].

Worse, it seems that since I'm using svn URLs that start with svn+ssh, the URL I put into the svn::externals property has to include my username! [see note 2]. This means that the external URL will only work when I do the update, not when my co-workers do it. What a mess.

It appears that svn ignores externals when you perform a commit. That is, it assumes you are using an external piece of code that you don't own, and don't want to (or don't have permission to) change. However, you _can_ specify that the external reference should either remain stuck on a particular version, or should refer to the head; if you choose the latter, when you do an update, if the external tree have changed your working copy will be updated.

Anyway, there it is: externals are slightly more flexible than CVS, but not arbitrarily flexible, and with some critical usability issues. Neither of the tools really will let you assemble a checkout out of arbitrary directories and files.

I am going with svn and hoping not to look back, but the ability to define completely arbitrary modules would have been a nice fit to our build process.

From the point of view of programming languages, or even a DSL for version control, this would seem like a perfect example of failed Greenspunning. Why _shouldn't_ the modules system in CVS let you specify arbitrary paths, or even use regular expression pattern matching, to specify the members of a retrievable module? Why shouldn't a tool like svn let you use a DSL to specify what actually happens in the checkout process, with primitives that correspond to the domain entities and proper handling of metadata?

Without this, it seems to me, there is still room in the version control space for a better tool. But I guess there is always room for a better tool; the question is "how flexible is flexible enough?"

NOTE 1: Apparently this subversion feature (relative external links) has been under discussion for a long time. See the bug report. It looks like it might appear in svn 1.5, but I'm not holding my breath.

NOTE 2: There seems to be a way to configure resource files so that command-line svn clients will let you use external svn+ssh URLs that don't specify a username. However, at my workplace we are all using the TortoiseSVN client, and I'm not aware of any way to make that client work with these URLs without specifying the username. Also, just as a matter of design, it seems like a bad idea to force your repository to contain hard-coded references to its own URL, since these will break if the entire repository is moved.

Thinking about Sudoku and Scheme, Part 2

2006-01-25T12:50:00.001-05:00

Here is how I implemented some of my array primitives. I'll start in the middle:

(define map-board-row-elts
 (array2D-make-row-elt-mapper board-x-dim))

When treating a vector like a two-dimensional array, assuming that you store them row-first, the key piece of information you need is the size of the row. (More generally, for an n-dimensional array, to access an element you need to know the size of dimensions 1 to n - 1). On the top side of my program, the dimensions of my Sudoku board are known. The array primitives don't know. Rather than pass this information to every array access call, I create a function. The function array2D-make-row-elt-mapper captures this information using closure and returns another function:

(define array2D-make-row-elt-mapper
  (lambda (x-dim)
    (lambda (array2D y-idx elt-handler)
      (array2D-map-row-elts 
       array2D y-idx x-dim elt-handler))))

Note the nested lambda expressions. The top one receives the x-dim parameter, and the body of this function is another lambda expression. This second lambda expression is the return value of this function: it returns a function. This returned function invokes another function which requires an x-dim parameter.

In this case, the purpose of returning this function is to provide the functionality of another function, array2D-map-row-elts, but without the need to provide an x-dim parameter. The new function is a curried function.

What is a curried function? Currying means taking a function with n parameters and creating a new function with n - 1 parameters. The new function provides a default value for the missing parameter, giving you a simplified API to the original function.

Common Lisp and other languages provide curry and rcurry functions which peel off parameters from the left or right of the paramter list, respectively. So our currying may not meet a strict definition, although we are doing the same thing: providing an interface function that will supply a value for one of the original parameters. Currying often uses a constant for these default parameters; in our case, we're using a variable, but the idea is similar. Scheme does not have a standard curry function, but it is easy enough to express currying by using nested lambda expressions.

In my case, x-dim is the curried parameter. Inside this lambda expression is a reference to x-dim. Scheme supports lexical closure; at the time this lambda expression is evaluated, the result is a function object that "closes over" or "captures" -- that is, retains a reference to -- the variable binding in effect when the lambda expression is evaluated.

This is the variable binding owned by the caller, the variable bound to the name board-x-dim. It is not a copy: if some other piece of code updates the value in that variable, this function would see a different value for x-dim when it executes. This creates complex state with multiple possible "listeners" for the state change: this is one of the reasons that Scheme programmers tend to prefer a functional style where variables are not altered after initial binding.

If you are a C programmer, you may find this very confusing. You can think of it as if the returned function retains a pointer to the board-x-dim sent by the caller. The C runtime model is quite different, though: it has distinct lifetimes for variables; local non-static ("automatic") variables that exist on the stack may be recycled when a given function returns, so it is unsafe to retain pointers to them (in fact, retaining a pointer to an automatic variable is a common beginner's bug in C).

In Scheme, bindings exist as long as there are references to them; when there are no more references to them, they may be garbage-collected (or not).

Let's look at the definition of the next function we call, array2D-map-row-elts:

((define array2D-map-row-elts
  (lambda (array2D y-idx x-dim elt-handler)
    (array2D-map-subrow-elts
     array2D 
     0 (- x-dim 1) 
     y-idx 
     x-dim 
     elt-handler)))

OK, we call yet another function: array2D-map-subrow-elts, which is more general (it will map any contiguous subset of the array elements). It is the general case, and array2D-map-row-elts is the more specific case (it maps the whole row), which means we can quite naturally define this specific case by parameterizing the general case. It isn't quite the same as currying, but it is a similar idea; we provide some fixed parameters representing the start of the row (index 0) and end (index x-dim - 1). Here is the general function:

(define array2D-map-subrow-elts
  (lambda (array2D 
           x-first-idx x-last-idx 
           y-idx 
           x-dim 
           elt-handler)
    (letrec ((iter-x
              (lambda (x-idx y-idx)
                (elt-handler 
                 (array2D-get array2D x-idx y-idx x-dim))
                (if (< x-idx x-last-idx)
                    (iter-x (+ x-idx 1) y-idx)))))
      (iter-x x-first-idx y-idx))))

Are we there yet?

This function receives all the parameters and walks through the array, starting with an arbitrary x-idx (in this case, zero), and proceeding until we have processed the last legal x index (in this case, x-idx - 1).

Note that instead of iteration to walk the array, I use recursion. I won't go into a full explanation of recursion here; suffice it to say that although many people feel that recursion is unnatural and does not reflect how they think about iteration in the "real world," after expressing algorithms recursively for a while, it starts to seem much more natural, and the proposition that recursion and iteration can be transformed into each other does not seem so strange.

This function is formulated using tail recursion, where the bindings are not referenced after the recursive function call. In C or Pascal, the compilers are generally not smart about this sort of thing, and recursing on a large array could result in a very deep set of stack frames. A language like Scheme is able to recognize that since the values that exist in previous function calls are not used, it is free to lose track of the previous values, so no deep stack is actually required. Since this is the case, the decision to use recursion was largely arbitrary. I chose it because I wanted to practice writing recursive functions.

The letrec may be unfamiliar. If the innermost function was not recursive, we could just call it like this, without ever binding the function to a name at all:

((lambda (x-idx y-idx)
   ... )
0 y-idx)

In this case the innermost function is never bound to a name, because nothing has to refer to it by name. The expression around it would simply call it. This is also known as applying parameters to the anonymous function object.

You might think that we could just do this with let. The semantics of let allow the call from outside the function, but the binding to the name iter-x would exist only within the body of the let expression. This body consists of the expression or expressions that occur after the binding list in the let expression. Since the definition of the function occurs as part of the binding list, not part of the body of the let expression, let will not work; letrec is designed specifically to allow definition of recursive or mutually recursive functions within the binding list.

So now are we there yet?

Almost. My final comment on this function concerns the use of the elt-handler parameter. The generated function allows the caller to pass in a handler function. Applying functions to functions is known as higher-order programming; support for higher-order programming is one of the essential features of Lisp and Scheme.

It might seem like this is much too complicated. Functions generating functions calling functions calling functions? Well, yes, this is a bit of overkill to access an array; normally we would use some standard functions for handling data structures. But the general style: creating a lot of small functions -- appears very commonly in Scheme programs, and now you have had a taste of how a typical data structure library might be implemented.

I don't claim to be very experienced with Scheme yet, but I am happy to have gotten to the point where writing functions like array2D-make-row-elt-mapper and its supporting functions comes rapidly and naturally. Reading examples helps, but the lessons don't really click until you tackle a programming problem, and feel your mind begin to undergo rewiring. The level of abstraction, and thus the leverage you can gain from Scheme, become much higher than this, so stay tuned.

Some Computer Science Classics

2006-01-25T12:34:00.000-05:00

I've been building up a computer science library via ABE Books (http://abebooks.com, highly recommended), purchasing a couple of used books and a couple of new books each month.

Recently arrived used:

Hoare, Communicating Sequential Processes.
Dijkstra, A Discipline of Programming
Agha, Actors

Recently arrived new:
Brodie, Thinking Forth

Some comments on these texts later.

Thinking about Sudoku and Scheme, Part 1

2006-01-25T12:29:00.001-05:00

I've been working on some tools to help me solve Sudoku puzzles in Scheme. That goal is actually secondary to the goal of learning to write better, more idiomatic Scheme programs, and so progress towards the Sudoku solver is frequently interrupted while I backtrack in an attempt to reorganize and optimize the supporting code.

I'm working on this both in a bottom-up and top-down direction. Bottom up, to develop something of a domain-specific Sudoku-solving language. Top down, because my higher-level strategy is also not that clear at the outset and is undergoing stepwise refinement.

My approach to solving Sudoku by computer is not to recursively explore every the tree of moves until a solution is found. That approach is easily doable but less interesting to me than trying to emulate some of the solving strategies that can be performed by a human solver. Ultimately I would like the tool to assist a human solver, not replace her.

My tool of choice is PLT Scheme version 3.00. For reasons to painful to go into just now, I have currently given up on using either SRFIs or SLIB for libraries and am writing everything in plain RSR5 Scheme. More on hat later.

Welcome

2006-01-25T12:25:00.000-05:00

This blog, "Curse and Recurse" is a spinoff of my weblogs "Geek Like Me" and "Geek Like Me, Too."

http://thepottshouse.org/blosxom.cgi

http://geeklikemetoo.blogspot.com

The topic of this blog is pragmatic programming and programming languages. I am interested in clearer and more effective ways to express programs and tools that will get to bug-free code faster, Sapir-Worf be damned. I don't have a Ph.D. and this is not an exposition about theoretical type systems.

The languages I am currently most interested in are Scheme, and Ruby. I have long-term goals to learn idiomatic programming in Common Lisp and to find better approaches to embedded systems programming by using embedded languages such as Lua and Io. This is not currently another Ruby on Rails weblog and I am not doing web development these days, although I have done so in the distant past.

If you are still reading, welcome! Maybe we can both learn something.