Temerity

I added a column to my Scheme Implementation spreadsheet. That is ‘Arbitrary Metric A’ As the name suggests, it is arbitrary. However, it is also a metric. My opinion about the merits of any particular scheme implementation was not a factor.

Metric A sucks. It cannot be independently verified, it's relevancy cannot be determined, the bias is unknown. It has exactly one virtue: it has a value. I'd like to come up with something better, but until I do, here it is.

If you have an objective metric, give me the values, (or better yet, tell us how to derive them!!!) and I'll add a column for that.

---

Not only did I have the temerity to measure Scheme implementations on a hidden scale (it could have been a Ouija board), I had the temerity to rank the implementations. Furthemore, I divided them into four broad tiers.

Tier 1 is the powerhouse implementations. Of course PLT scheme is the most popular scheme. I was surprised to find that Gauche is tremendously popular. I've heard of it, but never used it. I was also surprised, but pleased to see MIT Scheme is still popular enough to stand out from the crowd.

Tier 2 is the usual suspects. These implementations are well known and have a solid following. The surprise here is that EdScheme is in this tier but Chez Scheme is not and that Scsh is here but Scheme 48 is not.

Tier 3 is the genus omne.

Tier 4 is the obscure implementations.

Stupid software

I'm getting old and I can't work these newfangled “web” applications. Let me try again.

http://spreadsheets.google.com/pub?key=twRSWnj1h-j_F3IHRXxwrmg&output=html

Please email me if you have problems.

A list of Scheme implementations

I've made a list of Scheme Implementations at this incredibly ugly URL: http://spreadsheets.google.com/ccc?key=0Aozj6rF-PmISdHdSU1duajFoLWpfRjNJSFJYeHdybWc.

This list is not meant to be exhaustive, but I'd like it to include all the Scheme implementations that are likely to affect, or to be affected by, the next Scheme standard.

For the moment, I just want to make a list of active implementations. I don't want to compare features, or list conformance. I'll add these later if they seem relevant.

Please send me email if I have omitted things, got things wrong, or included abandoned implementations. Thank you for your time.

A harder puzzle

The previous puzzle was inspired by this one:

(define (f l)
  (if (null? l) 
      #f
      (let ((r (fold-left kernel k0 l)))
        (f (if (car r) (cadr r) (caddr r))))))

(define (kernel l e)
  (list (not (car l))
        (if (car l) (cons e (cadr l)) (cadr l))
        (cons e (cons e (cons e (caddr l))))))

(define k0 (list #f '() '(#t #t #t)))

Q1 (easy): Show that for any non-negative integer n, (f (make-list n)) can return no value other than #f.

Q2 (very hard): Show that for any non-negative integer n, (f (make-list n)) returns #f.

A small puzzle

I got this from Marshall Spight today.

(define (f a b)
  (if (zero? b)
      a
      (f (logxor a b)
         (* (logand a b) 2))))

Q: F is better known as ______ ?

You may need these auxiliary functions.

(define (logand a b)
  (cond ((zero? a) 0)
        ((zero? b) 0)
        (else
         (+ (* (logand (floor (/ a 2)) (floor (/ b 2))) 2)
            (if (or (even? a)
                    (even? b))
                0
                1)))))

(define (logxor a b)
  (cond ((zero? a) b)
        ((zero? b) a)
        (else 
         (+ (* (logxor (floor (/ a 2)) (floor (/ b 2))) 2)
            (if (even? a)
                (if (even? b) 0 1)
                (if (even? b) 1 0))))))

And please don't just post a spoiler. If you just want ‘first credit’, email me directly.

What's amusing to me is that it isn't obvious if F even terminates.

Hyperspec search engine

For those of you who like this sort of thing, I have a “Google Custom Search Engine” for searching the Hyperspec and the AMOP. You can put it on your home page or on your web site with some simple Javascript:

<form action="http://www.google.com/cse" id="cse-search-box">
  <div>
    <input type="hidden" name="cx" value="008072110934663485714:6gce0ybe318" />
    <input type="hidden" name="ie" value="UTF-8" />
    <input type="text" name="q" size="31" />
    <input type="submit" name="sa" value="Search" />
  </div>
</form>

<script type="text/javascript" src="http://www.google.com/coop/cse/brand?form=cse-search-box&lang=en"></script>

If you are adventurous, you can use the AJAX api and build your own interface to it.

I'm on You Tube

I was an extra in this very short commercial.

How Not to Write Code, II

Ok here's my view on the example in the last post.

It's a little hard to assign blame or point to a particular failure as the root cause of the problem. There are systemic problems beyond the obvious ones. I'll just point out a few problems.

First and foremost is using local time. Time values should always be handled as UTC values. In general, you only need local time if you are printing something for a human to look at. At this point, you can convert the timestamp from UTC to local time, if you know what time zone you are in. Conversely, you should convert from local time to UTC as soon as you read a local time.

You can in theory handle everything as a local time if you retain the time zone, but this violates an abstraction. You want to represent an instant in time, not the local convention for naming it.

The underlying problem is conflating the presentation with the representation. An instant in time is what you want to represent. You present that to the user as a series of characters. You don't want to represent the time as the character string you present to the user. (Consider, you may present the time to the user as a bitmap that shows a drawing of a calendar with the date circled in red. You wouldn't dream of using that bitmap as the internal representation!)

But the programmer who coded this up in the first place can't be blamed too much because there are problems with the software involved in presentation and persistence. The display is a web browser, and the current technology of page layout is to put markers around text. You cannot simply put a date object on a web page. You must create a text string that represents the date and use that instead. When a date is entered as part of a form, the character string entered is returned. The browser encourages sloppy practice.

The database was a major problem. The programmer went out of his way to bypass the database schema by declaring everything as an unstructured list of strings. Now this in itself is not necessarily a bad thing, but to do this correctly you want to add an abstraction layer that manages the mapping from objects to their serialized forms. Part of the purpose of that abstraction layer is to hide the underlying persistent representation. The user shouldn't be aware that there are strings at the bottom. The mapping layer ought to provide a reasonable set of primitive types (booleans, integers, enums) in addition to a few of the more complex types one might store in a database, like dates and URLs. The mapping layer also ought to canonicalize and validate the data. If this existed, the programmer would most likely have used the abstraction layer to store the date objects rather than serializing them to strings by hand. It would be less likely that local times would have been stored in the database.

Ideally, you'd like a rich object model that worked from end-to-end. Requests to the server would contain embedded date objects, these date objects could be written to the database directly. When presenting data, the date objects would be retrieved from the database and placed in the appropriate data structures to send back to the browser. Unfortunately, neither the viewing nor the persistence layers provide this.

The last issue is the insane workaround. The programmer was obviously clever, but what on earth possessed him to write that? How did that pass code review?! The problem is that there is corrupted data in the system. For heaven's sake don't add helper functions to make more of it!

There are dozens of ways to fix this bug, and nearly all of them are better. Here's one way (admittedly off the top of my head):

1. Add the ‘date’ abstraction to the database that keeps dates and times in UTC format and hides the mechanism of serialization.
2. Add new fields to the existing objects to replace the ones holding strings in local time. Initialize the new fields with the UTC dates and times that correspond to the local time strings.
3. Deprecate the old field. Write code that throws an exception if any other code tries to read or write it.

You'd also have to fix the remaining code to work correctly. The existing code misuses Date objects, so they are definitely suspect. A trick here would be to make some scaffolding code. Define a new class (call it UTCDate or something), that is a simple shim over the real date class. It should have the exact same API as the Date class, except it should not have the constructors or selectors that caused the original problems. Make the database return objects of this class. Do not allow coercion between Date and UTCDate. Now go through the code and fix the type errors. You'll end up following the data flow of Date objects through the code. Since Date and UTCDate are virtually the same, most of the time you'll just have to replace one with the other. The places where you can't are the problem spots.

Once everything works with UTCDates, you can textually replace UTCDate with Date (provided you made the API compatible) and toss out the scaffolding.

How Not to Write Code

or

It's About Time

What is it about time and calendars that induces people to make the same mistakes over and over and over? Once again I ran into some date handling issues in some code I was debugging. The problem was the same as it always is, but the attempted solution is, shall we say, interesting.

I was going to rant, but I think I'll just describe the code. You'll see some bad ideas here. They aren't mine. I had nothing to do with the design or implementation of the original code or the so-called solution.

The code keeps track of a set of a few hundred items that change over time. There is a browser-based API that allows you to add items, examine items, make changes to items, and examine the history of an item. It's a very simple application that is only slightly more sophisticated than having all the users share and edit a wiki page (or a big whiteboard).

The persistence layer for this application was a simple key-value store. The items being tracked had a bunch of fields, and each field was string. This was convenient because the key-value store didn't have much of a schema management layer. If you wanted to store anything other than a byte string, you had to define your own serialization mechanisms. If you wanted to change your schema, you were pretty much on your own. Most applications just used the system as a BLOB store.

This application was no exception. But rather than using the field names as keys, it simply serialized the entire item as alternating key value strings in a single BLOB and used an ID number as the key in the database. When fetching an item, the code would get the BLOB and separate out the keys and values and put them in a hash table. This, too, was a common practice.

Since items can change, they have a history, so there are times and dates associated with the items. People want to see and manipulate the times and dates. At first, the times and dates were simply entered as text, stored as text strings, and simply written on the page as the original text. This was sufficient for most needs, but then someone wanted the program to act on the time and date information. Some of the times and dates that were recorded were fairly important and people wanted to get email reminders near those times.

The date library came in handy at this point because it could parse text into date objects. The date objects could be compared with each other to develop a chronology, and the components of the date — the day, month, and year — could be easily manipulated. A small change to the database schema was made for convenience. Dates were no longer stored as human-readable text, but instead were stored as the number of milliseconds since the date epoch.

Things were working fine for a while, but then someone wanted a calendar display. As it turns out, there was a calendar display library that was trivial to link in and use.

There was a slight problem. Everything displayed in the calendar was off by seven hours.

Ever since the application was created, the people using it naturally entered times and dates in local time. The application stored these faithfully as strings. When date objects were introduced, everything seemed to be working fine. What no one noticed was that since the time zone wasn't specified, the date objects were constructed with the assumption of Universal Time. Everything “worked” because nothing in the application so far payed attention to the time zone. The calendar library was different.

There were two ways to fix this, neither way was pleasant. Option one was to go through the entire legacy code and make it aware of time zones. There were three drawbacks to this: a lot of changes to the code, increase in the code size because of the tables involved in handling time zones, and, most importantly, the issue of a lot of dates in the database stored with the wrong zone. Option two was to continue to treat time as local time, but to provide a correction to it prior to calling the calendar library. Option two was clearly the easier path. No legacy code needed to change, and even better, no legacy objects needed to change.

So two routines were written. One to convert a year, month, day, hour, minute, second sextuple in local time to a date object with the correct value of milliseconds since the epoch. The second to convert a date object in universal time to one with the incorrect value of milliseconds, but with the correct values of year, month, day, hour, minute, and second in local time.

The first routine worked like this: the six arguments were used to initialize a date object in universal time. Then the time zone correction was applied. This was done in two phases. First, the longitudinal correction of seven hours was applied, then the resulting date was checked to see if a further correction for daylight savings time was needed. If necessary the additional hour was added. The date object returned had the correct number of milliseconds since the epoch and was suitable for using with the calendar library.

The corrected date objects were not suitable for use with legacy code, so the second routine ‘uncorrected’ them. This was done as follows: first the corrected date object was printed as a string in UTC time. The resulting text represented the desired date. That is, the corrected UTC time printed the same as an uncorrected local time. The second step was to then extract and parse the year, month, day, hour, minute and second fields out of the text string. These fields were used to construct a new date object without using the time zone information. This new date object was uncorrected, but was compatible with the legacy code.

Needless to say this code deserved a unit test, so tests were written to ensure that it behaved correctly near the daylight savings time boundaries.

Things were continuing on smoothly. The code worked and the tests passed. But recently another engineer added an expanded test. The unit tests were run regularly on the primary platforms, but they hadn't been tested on the more obscure ones. The expanded tests used a farm of machines to test the code on many more platforms. Errors appeared.

Playing around with ‘decanonicalized’ date objects like we were doing makes some assumptions about the implementation of the date library. The primary assumption is that if you create a date object and don't specify a time zone, you implicitly mean Universal Time. Some implementations assumed you implicitly mean local time. Another assumption is that the components of a date object (year, month, day, etc.) are synchronized with the millisecond value in the same way in each implementation. Some implementations don't support arbitrary mutations to date objects in this way.

This leads to a whole slew of bizarre behavior. Double corrections, ignored corrections, the month value being modified, and so forth.

The story ends here because this is the state I found the code in. There is a replacement tool in development, so there is no real need to fix this code.

---

As I said before, I was going to rant about this, but for the moment I'm holding my tongue. I'd like to see what other people think.