I was born in 1975. In the 'computer world', this means I grew up at the tail end of the 8-bit era. By the time I was a teenager the market was in the middle of deciding whether to go with PC's, the Apple Macintosh, or something else. Microsoft basically cinched that deal in 1990 with the release of Windows 3.0, the first relevant version. A PC running Windows 3.0 wasn't as nice as a Macintosh, but it didn't matter. If you already had a PC, you could buy Windows off the shelf for $89, retain all of your existing hardware and software, and then experiment with the GUI when you had the time. If typing win at a DOS prompt took you down the rabbit hole, clicking 'Exit Windows' took you right back to your comfort zone.

Windows 3.0 also had the benefit of a huge installed base of latent and mostly unused hardware. A typical business PC in 1990 might have been something like an 80286 with 2MB of RAM, a 40MB disk, and an EGA (640x350x4bpp) bitmapped display. It would then be running DOS software that basically couldn't address more than the first 640K of memory, and tf you ever saw the bitmap display in use, it was probably for a static plot of a graph. Compared to a Macintosh from the same year, a PC looked positively like something from a totally different generation. Windows 3.0 changed all this. It allowed you to switch your 80286 into 'Protected Mode' to get at that extra memory. It provided a graphics API (with drivers!) and forced programs to use the bitmapped display. It provided standard printer drivers that worked for all Windows programs. Basically, for $89 it took the hardware you already had and made it look almost like the Macintosh that would otherwise have cost you thousands of dollars. It was utterly transforming.

Almost 20 years later, the most interesting thing about this is the relative timing of the hardware and its software support. Most of the hardware in my 'typical 1990 PC' was introduced by IBM in its 1984 announcement of the IBM PC AT. The first attempt by IBM and Microsoft to support the 80286 natively came three years later in 1987's release of OS/2. The first 286-native platform to reach mainstream acceptance came in 1990. Think about that: it took 6 years for the open PC market to develop software capable of fully utilizing the 80286. The 80386 fared even worse; The first 386 machine was released in 1986, and it didn't have a major mainstream OS until either 1993 or 1995 (depending on whether or not you count Windows NT 3.1 as 'mainstream'). Thus, there were scores of 286 and 386 boxes that did nothing more than execute 8086 code really, really fast (for the time :-)). In modern terms, this is analogous to a vendor introducing a hardware devide today and then delaying software support until 2018.

This is emblematic of the hugely diminishing value of an open device platform in today's computer industry. In 1989, using a computer was largely an exercise in getting the damn thing to work. When those are the issues you're worried about as a PC user, an open platform is helpful because it enables a broader selection of vendors for parts and software. If you've run out of slots for both your video board and your bus mouse interface, you can always switch to an ATI video board with a built-in mouse port. If you need a memory manager that supports VCPI to enable your V86 multitasker, you can always switch to something like QEMM/386. If you need more memory to run your spreadsheet, you can go to AST Technolgies and buy a LIM/EMS board. When you're worried about these kinds of issues, issues 'low in the stack', the flexibility of choice provided by openness is useful enough that you might be more willing to bear the costs of a market slow to adopt new technologies.

Of course, price is also a factor. In 1988, Byte magazine ran a review of Compaq's Deskpro 386s. This was their first 80386SX machine, a desktop computer designed to be a cheaper way to run 80386-specific software. The cost of the review machine was something like $15,000. In 2007 dollars, this would buy you a nice, reasonably late-model BMW 3-series. A year later in 1989, my family bought a similar machine from ALR, which cost around $3,000. Thus isn't nearly as bad, but it's still around $5,200 in 2007, which basically means that a mid-range 1989 PC is priced at the very top end of the 2007 PC market. With monetary costs that high, that other benefit of openness, price competition, becomes a much bigger deal. Compaq ended up suffering badly as competition drove the price of the market to where it is today.

In the intervening 20 years, both of these circumstances have changed dramtically. PC's, both Windows and Macintosh, are well enough integrated that nothing needs to be done to get them to run aside from unpacking the box. NeXTStep, which in 1994 required a fancy $5,000 PC bought from a custom vendor to run well, will shortly be able to run (with long-range, high-speed wireless!) on a $200 handheld bought at your local shopping mall. Our industry has moved up Maslow's hierarchy of needs from expensive, unreliable hardware, run by the dedicated few to cheap, reliable hardware, run by disinterested many. We can now concentrate on more interesting things than just getting the computer to work, and tt is with this shift that the some of the unique value of openness has been lost. Unfortunately, the costs have been retained, there is no countervening force in the market that's forcing open platforms to move any faster.

Personally, I believe this bodes very well for Apple's latest attempt to own the smartphone space. There will only be one vendor and one price for the iPhone, but the platform will be able to move faster to adopt new technolgies, and integrate them more tightly, because there's only one kind of hardware to run on. The fewer hardware configurations and stricter quality control guidelines will make it easier (and more mandatory) that developers produce high quality software. The fact that entry into the software market is controlled, doesn't matter, because there are still more eligable developers than the platform actually needs. The net result of all this is that Apple, again, has a product that looks 'next generation', but the pricing and openness factors that cost them that advantage in the early 90's are no longer there. It's a good time to be involved in the iPhone, methinks.

reddit this! Digg Me!

A few months ago, I ran into a problem with a macro that seriously changed my opinions on how they should be used. It all comes down to the fact that macro are incorporated into compiler output. Two pieces of code that look nicely decoupled in the source text can end up very entwined with each other, once they are compiled.

To illustrate, I'll use the macro in question, something I once used to accept a sort of simulated 'multiple return value' in a dialect of Scheme. This is a low level example, something from my hobby work, but it can apply equally well to other uses of macros.

(defmacro (values-bind form vars . body)
  (with-gensyms (form-rv-sym)
    `(let ((,form-rv-sym ,form))
       (list-let ,vars (if (%values-tuple? ,form-rv-sym)
                           (slot-ref ,form-rv-sym 'v)
                           (list ,form-rv-sym))
         ,@body))))

This macro expands code like this:

(values-bind (returns-2-args 'foo) (arg-1 arg-2)
   (+ arg-1 arg-2))

Into code that looks like this:

(let ((#:form-rv-sym-69@00beeec4 (returns-2-args 'foo)))
   (list-let (arg-1 arg-2) (if (%values-tuple? #:form-rv-sym-69@00beeec4)
                              (slot-ref #:form-rv-sym-69@00beeec4 'v)
                              (list #:form-rv-sym-69@00beeec4))
     (+ arg-1 arg-2)))

And then, the compiler compiles that form and drops the result into the output file, which now contains several pretty deep assumptions about the simulated multiple value protocol it needs to honor:

Values are returned in a single value that satifies %values-tuple?.

Values are extracted from a tuple with a call to slot-ref for slot v.

Values are stored within slot as a list.
While the source text that uses values-bind doesn't need to know any of these details, the compiler output does. This results in compiler output that is very closely tied to the value protocol; Compiler output that is likely to be incompatible with any changes to that protocol.

In many development scenarios, this doesn't matter. Within a single project, if compiled file A comes to depend on assumptions embedded in macros from file B, it's less of an issue: both files are usually compiled at the same time. If both files can't be simultaneously compiled, things start to go wrong. I ran into this issue myself when trying to change the multiple value protocol I was using in my compiler. My core library was built with the old protocol, my new library was to be built with the new protocol, and the two could not interoperate for the brief period of time necessary to produce a compiled version of the new library. There are several possible approaches to solving this, but but one I took was the two step of building a new 'old' library that can handle both protocols, using it to compile a version that works only with the new protocol, and then switching over completely. It was a mess, and a mess I created myself with a macro that expanded into something that assumed way too much. The better approach, the approach that I switched to, is this:

(define (call-with-values proc vals)
  (apply proc (%values->list vals)))

(defmacro (values-bind form vars . body)
  `(call-with-values (lambda ,vars ,@body) ,form))

This expands the above code to something more palatable:

(call-with-values (lambda (arg-1 arg-2)
                     (+ arg-1 arg-2))
                  (returns-2-args 'foo))

The only assumption this makes in the compiled output is that there's a function call-with-values that calls its first argument with values passed in as its second argument. All of the gory details, which could easily be the same three from my list, are hidden behind function calls and dynamic linkage. This is actually the representation that made the two-step cutover approach plausible. Switching to this version of the values-bind macro removed assumptions about the value protocol from every call site, and made it easy to switch.

The upshot of this is something that's, I'm sure, pretty common knowledge in Lisp/Scheme circles: macros are best when limited to syntax, with the underlying functionality implemented in a more functional interface. The functional interface keeps things more decoupled, even when compiled, and leaves your software more managable. It also provides a second way to 'get at' the functionality provided by the underlying code. With the function/macro split, the macro expansionn can be avoided entirely, in the case when you already have a closure that contains the code you need to run.

One more brief example, a bit higher up the 'stack' in the language environment is the transformation of this macro:

(defmacro (with-output-to-string . code)
  (with-gensyms (saved-output-port-sym output-string-sym)
    `(let ((,saved-output-port-sym (current-output-port))
           (,output-string-sym (open-output-string)))
       (unwind-protect (lambda ()
                         (set-current-output-port ,output-string-sym)
                         ,@code
                         (get-output-string ,output-string-sym))
                       (lambda ()
                         (set-current-output-port ,saved-output-port-sym))))))

Into this macro/function pair:

(define (call-with-output-to-string fn)
  (let ((saved-output-port (current-output-port))
        (output-string (open-output-string)))
    (unwind-protect (lambda ()
                      (set-current-output-port output-string)
                      (fn)
                      (get-output-string output-string))
                    (lambda ()
                      (set-current-output-port saved-output-port)))))

(defmacro (with-output-to-string . code)
  `(call-with-output-to-string (lambda () ,@code)))

reddit this! Digg Me!

The instructions I gave earlier on Renaming SVN Users work only when the SVN repository is hosted on a machine that can run SVN hooks written in Unix style shell script. On a conventional Windows machine, one without Cygwin, MSYS, or similar, you have to switch to writing hooks in something like Windows batch language.

If all you want to do is temporarily rename users, then you can just create an empty file named pre-revprop-change.cmd in your repository under hooks\. The default return code from a batch file is success, which SVN interprets as a all revision property changes, all the time, by anybody. If you want to implement an actual policy, Philibert Pérusse has posted a template script online.

reddit this! Digg Me!

A couple weeks ago, I got into a brief reddit discussion on the relative merits of Lisp's car and cdr functions. Given a Lisp list, applying car to the list returns the first element of the list and applying cdr to the list returns a list of every element excluding the first. For someone new to Lisp (as we all were once), these names can be a bit awkward. However, like many other aspects of the language, there is more to car and cdr than meets the eye.

The first implementation of Lisp was done by Steve Russell on an IBM 704. The 704 was a 36-bit vacuum tube machine that IBM started selling in 1954. By the time it was discontinued in 1960, they had sold a total of 123 of the machines, each capable of a whopping 40,000 calculations per second. Russell's original 1959 implementation of Lisp on this machine took advantage of the fact that the 704's instruction set had special capabilities for accessing two distinct 15 bit fields of a 36 bit value loaded into a machine register: the address and decrement fields. In Russell's own words: "Because of an unfortunate temporary lapse of inspiration, we couldn't think of any other names for the 2 pointers in a list node than 'address' and 'decrement', so we called the functions CAR for 'Contents of Address of Register' and CDR for 'Contents of Decrement of Register'." Interestingly enough, he continues with this: "After several months and giving a few classes in LISP, we realized that 'first' and 'rest' were better names, and we (John McCarthy, I and some of the rest of the AI Project) tried to get people to use them instead. ... Alas, it was too late! We couldn't make it stick at all. So we have CAR and CDR. " So there you have it: car and cdr, two of the most famous and widely used functions of Lisp and its descendents, owe their names to a bizarre quirk of a computer architecture that's been obsolete for close to fifty years. For the record, here's a source listing for the original 704 implementataion of car taken from MIT AI Lab Memo 6:

LXD JLOC, 4
CLA 0,4
PAX 0,4
PSX 0,4

But the story of car and cdr doesn't stop there. In the 1960's and early 70's, the University of Texas at Austin ran a computer called a CDC 6600. The 6600 was one of Seymour Cray's first big supercomputer designs, and was the fastest computer in the world for a time. It had a 60-bit machine word and an 18-bit address space, so you can probably see where this is going. The designers of UT's Lisp for the CDC 6600 added a third field to cons cells, giving them each three pointers, the car, cdr, and csr. I'm sure the third pointer was useful for implementing things like trees of nodes and lists of key/value pairs, although apparantly not useful enough to stick around. Two pointer cons cells are a better fit for modern hardware, and two two pointer cons cells can represent everything that a single three pointer cons cell can represent.

Back at MIT in the 70's, and before things like defstruct, Maclisp took the idea of multi-pointer cons cells to what must be its logical extreme: hunks. A Maclisp hunk was a structure like a cons cell that could hold an arbitrary number of pointers, up to total of 512. Each of these slots in a hunk was referred to as a numbered cxr, with a numbering scheme that went like this: ( cxr-1 cxr-2 cxr-3 ... cxr-n cxr-0 ). No matter how many slots were in the hunk, car was equivalent to (cxr 1 hunk) and cdr was equivalent to (cxr 0 hunk). This is a nice generalization of the basic idea of a cons cell, but modern Lisps offer other ways to structure data that are both possibly more useful and more readable: structures for a fixed collection of named slots, hash tables for a variable collection of named slots, and vectors for a collection of numbered slots.

After these historical blind alleys, it's interesting to think about why car and cdr still persist fifty years after McCarthy and Russell roamed the halls of MIT evangelising first and rest. Common Lisp does at least have first and rest as part of the standard. However, when I was taught Lisp in the mid-90's, I was encouraged to primarily favor the older car and cdr. I remember two primary reasons for this. The first was that existing code favored car and cdr, so it was important to be able to read code written in that style. The second reason was that first and rest impose a particular meaning on the fields of a cons cell that may or may not be appropriate. In the common case of a linear list, first and rest work rather well. If you call first on the list, you get the first element, if you call rest, you get the rest. In the case of a cons cell as a node of an association list, they work less well, unless, that is, you can figure out a reason why first makes sense as 'key', and rest makes sense as 'value'.

Some of this confusion stems from the fact that most Lisps, despite the name List Processing, don't have an official list data type. What they have instead is a two element cons cell and a set of conventions in the library, reader, and writer for using the to make linear lists. In a sense, this is a lot like strings in C. C doesn't have a string type, what it has instead is a pointer to character data (char *) and a set of library conventions for using blocks of memory as strings of characters. This laxness on the part of both languages comes with the advantages and disadvantages you'd expect from letting the deatils of an underlying implementation leak through. In the case of C 'strings', the representation lends itself both to things like Rob Pike's beautiful regex implementation in The Practice of Programming and a seemingly never ending series of buffer overrun attacks. In the case of Lisp cons cells, it provides both an incredibly flexible data structure, and confusion over such basic notions as the 'first', 'second', and 'rest' of a list.

If something as baroque as 'car' actually makes more sense than 'first' because 'first' doesn't match up well to underlying abstraction, it might them make sense to reconsider the underlying implementation. Some modern Lisps like Clojure do just that; A Clojure 'list' isn't a string of cons cells, but rather an instance of a JVM object that implements the interface ISeq:

public interface ISeq extends IPersistentCollection{
   Object first();
   ISeq rest();
   ISeq cons(Object o);
}

Clojure's user-visible first and rest functions ultimately call into their like-named methods in ISeq:

static public Object first(Object x){
	ISeq seq = seq(x);
	if(seq == null)
		return null;
	return seq.first();
}

// ...

static public ISeq rest(Object x){
	ISeq seq = seq(x);
	if(seq == null)
		return null;
	return seq.rest();
}

A noteworthy difference between this and a 'conventional' Lisp is the return type of rest: it's another ISeq, rather than a Object. Because of this, the 'CDR' of a Clojure cons cell has a new constraint: it is constrained to be another sequence, increasing greatly the likelihood that 'rest' really is 'the rest'. While this could be done even if rest returned an Object, constraining rest to be a sequence eliminates a number of edge cases in the language that arise when you allow the rest of a list to be something other than a list itself. This altered representation also fits in nicely with Clojure's host JVM: there's nothing that says ISeq has to be implemented by a two-element pointer. Indeed, Closure "also implements first and rest for vectors, strings, arrays, maps, Java Iterables, lazily calculated and infinite sequences etc." All these implementations of ISeq make it easier for Clojure sequences to interoperate with Java, and it makes it easier to build a sequence library that works on all kinds of sequences. What's lost with this choice is the ability to use a cons cell as an informal two-element structure. Even then, this style of first and rest could co-exist with implementations of car and cdr that work the 'old way'.

So in the end, maybe car and cdr are all right. They aren't the best names in the world, but they fit nicely the semantics of a unrestricted two-pointer cons cell. For those cases where you really are finding the first and rest of a list of cons cells, it is easy to use the first and rest functions in lieu of car and cdr. Then, for dialects like Clojure, your code is automatically portable to other sequence types. If you're using cons cells as a ad hoc structure, then you can either use car and cdr and accept those names as historical baggage of the second oldest major programming language, or investigate some of the other more modern ways of structuring data in Lisp programs.

reddit this! Digg Me!

There was a copy/paste error in the version of ant-up I posted a while ago. It has now been corrected.

I ran across Adam Houghton's blog the other day. It looks pretty interesting and there's software to download (which is more than I can say right now). The blog seems to currently focus on Apple/Java/AJAX related content. The iPhone based javadoc viewer looks particularly interesting, for those of us not interested in carrying around a library.

Also, on a totally different note is Autoblog, a 'professional' blog covering automotive news. It's updated fairly often too.

reddit this! Digg Me!

I've been keeping track of the vCalc source code in an SVN repository since May of 2005. While I'm the only person who has ever committed code into the repository, I've developed vCalc on three or four machines, with different usernames on each machine. Since SVN records usernames with each commit, these historical usernames show up in each svn log or svn blame. svn blame is particularly bad because it displays a code listing with the username prepended to each line in a fixed width gutter. With some usernames longer than others, usernames that are very long can exceed the width of the gutter and push the code over to the right. Fortunately, changing historical usernames isn't that hard, if you have administrator rights on your SVN repository.

SVN stores the name of a revision's committer in a revision property named svn:author. If you're not familar with the term, a revision property is a blob of out of band data that SVN attaches to the revision. In addition to the author of a commit, they're also used to store the commit log message, and, via SVN's propset and propget commands, user-provided custom metadata for the revision. Changing the name of a user associated with a commit basically amounts to using propset to update the svn:author property for a revision. The command to do this is structured like so:

svn propset svn:author --revprop -rrev-number new-username repository-URL

If this works, you are all set, but what is more likely to happen is the following error:

svn: Repository has not been enabled to accept revision propchanges;
ask the administrator to create a pre-revprop-change hook

By default, revision property changes are disabled. This makes sense if you are at all interested in using your source code control system to satisfy an auditing requirement. Changing the author of a commit would be a great way for a developer to cover their tracks, if they were interested in doing something underhanded. Also, unlike most other aspects of a project managed in SVN, revision properties have no change tracking: They are the change tracking mechanism for everything else. Because of the security risks, enabling changes to revision properties requires establishment of a guard hook: an external procedure that is consulted whenever someone requests that a revision property be changed. Any policy decisions about who can change what revision property when are implemented in the hook procedure.

Hooks in SVN are stored in the hooks/ directory under the repository toplevel. Conveniently, SVN provides a sample implementation on the hook we need to implement in the shell script pre-revprop-change.tmpl, but the sample implementation also has strict defaults about what can be changed, allowing only the log message to be set:

if [ "$ACTION" = "M" -a "$PROPNAME" = "svn:log" ]; then exit 0; fi

echo "Changing revision properties other than svn:log is prohibited" >&2
exit 1

The sample script can be enabled by renaming it to pre-revprop-change. It can be made considerably more lax by adding an exit 0 before the lines I list above. At this point, the property update command should work, although if you're at all interested in the security of your repository, it is best to restore whatever revision property policy was in place as soon as possible.

reddit this! Digg Me!

I've spent a fair amount of time lately working with code that generates Comma Seperated Value files for loading into Excel. You'd think the format would be trivial, but not quite. One additional subtlety, one not covered in that 'specification', is Excel's inconsistent handling of end of line markers. As it turns out, if Excel loads a CSV file that contains a quoted, multi-line value, it expects a different line feed convention within the quoted value than the usual CR/LF. A CR embedded in a quoted field renders as a box, rather than as part of a newline. To suppress the box, CSV files for Excel need to be written with a LF-only convention within quoted values. Even then, Excel will not automatically expand rows containing a multi-line value. That has to be done manually.

Internally, Excel seems to follow the same LF-only convention that this issue with CSV files seems to imply. Taking the CODE(...) of each character in a manually entered multi-line cell value, shows only one charater, a LF, at each line break. My guess is that the quotes in a CSV file just act as a signal to turn off all special character handling, not just handling that signals new rows and cells. Either way, it's more than a little irritating that Excel compatible CSV files with multi-line values have to have two seperate end of line conventions.

reddit this! Digg Me!

Another one along the lines of My last post. I tried to compile this source file today, using the compiler in my little Lisp:

(define (values . args) (%panic "roh roh"))

(define (test x) (+ x 1))

I got the following result:

d:\test>vcsh -c test.scm
;;;; VCSH, Debug Build (SCAN 0.99 - Dec 17 2007 16:47:30)

; Info: Loading Internal File: fasl-compiler
; Info: Package 'fasl-compiler' created
; Info: Loading Internal File: fasl-write
; Info: Package 'fasl-write' created
; Info: Loading Internal File: fasl-compiler-run
; Info: Package 'fasl-compiler-run' created
; Info: stack limit disabled!
Fatal Error: roh roh @ (error.cpp:168)

Needless to say, fatal errors still aren't any good. However, this one is a bit more interesting than a simple type checking problem. The function %panic is the internal function used to signal fatal errors from Lisp code. The first definition above redefines values, the function to return multiple return values, so that it always panics with a fatal error. This is the kind of thing that, if done in a running environment, would break things almost immediately.

But, the compiler is slightly different.... it isolates the program being compiled from the compiler itself. This is done to keep redefinitions that might break the currently running compiler from doing just that. Redefinitions by the compiled program are only supposed to be visible to the compiled program. Since the above program never itself invokes values, it should never hit the call to %panic... except that it does.

What's happening here lies in the processing of the second definition. The definition itself is transformed a couple times by macroexpansion, first to this:

(%define test (named-lambda test (x) (+ x 1)))

And then, basically, to this:

(%define test (%lambda ((name . test) (lambda-list x)) (x) (+ x 1)))

The second macroexpansion step is the step that looks for optional arguments, and the internal function that parses lambda lists for optional arguments returns three values using values. This invocation of values happens in the environment of the program being compiled, so it hits the new %panic-invoking definition and the whole show grinds to a halt. The 'easy' fix, ensuring that macro expansion is isolated from potentially harmful redefinitions, won't work. Macro expansion has to happen in the user environment, so that macros can see function definitions that they might rely upon.

I don't have a unit test for the user/compiler seperation logic, so I thought when I started this blog post I was going to say something like: 'look, something else fundamentally broken, and without a test case'. That's interesting, but if you need convincing to write unit tests, you're probably already lost. What I actually learned while researching this post is a bit more subtle: it's a fundamental problem, but it's more about the design than the code itself. While the design I have for user/compiler seperation seems to work most of the time, it's not adequate to solve this kind of problem. I'm not yet exactly sure what the solution is, but it won't necessarily involve a missing unit test.

reddit this! Digg Me!

The other day, I had the following (abbreviated) dialog with my little Scheme interpreter:

scheme> (intern! 'xyzzy2 (find-package "keyword"))
; Fatal Error: Assertation Failed: STRINGP(pname) @ (oblist.cpp:451)
c:\vcalc>vcsh.exe

scheme> (intern! 12)
; Fatal Error: Assertation Failed: STRINGP(sym_name) @ (oblist.cpp:269)
c:\vcalc>

Needless to say, 'Fatal errors' aren't good things, and fatal errors in intern!, a core function, are even worse. Without going into too many details, the first call should be returning successfully, and the second should be throwing a runtime type check error. However, the implementation of intern! wasn't checking argument types and passing invalid arguments into lower layers of the interpreter's oblist (symbol table) code, which died with an assertation failure.

To put this in perspective, my implentation of intern! is about five years old, and something that I thought to be a fairly reliable piece of code. At the very least, I didn't think it was susceptable to something as simple as a type checking error that would crash the entire interpreter. Of course, when I looked at my test suite, there wasn't a set of tests for intern!. That might have something to do with it, don't you think?

Here are the morals I'm taking from this little story:

Do not assume something works, unless you have a complete test suite for it. (Even then be wary, because your test suite is probably not complete.)

Shoot for more than 60% code coverage on your test cases.

Don't write your own interpreter, because there are probably hundreds of other bugs just like this one. :-)

reddit this! Digg Me!

I don't usually write posts for the sole purpose of linking to other posts, but this is an exception. This is brilliant. What it is is the USDA's Food Pyramidbut adapted to how programmers should spend their time. My one complaint is that it's way too focused on coding. My experience has been that it really pays to spend time on design work and learning to how to better interact with others, be they clients or team-mates. If you can design your way out of a rewrite, or work with your client to recast requirements to save complexity, it can be far more cost effective than even the best raw code.

reddit this! Digg Me!

Last June, I wrote a bit on my experiences with the Cingular 2125 Windows Smartphone. After more than a year, the phone has been a good choice, but there have been several suprises, for both the good and the bad.

This is the first phone I've used with a web browser that's usable for general web surfing. Most sites render reasonably correctly, and the display is large enough to contain a useful amount of content. It's still not perfect, the browser crashes too often and it is difficult to log into reddit, but this is a vast improvement over conventional phones.

I installed a 1GB SD Card that is borderline useless. This might be different if I'd been more aggressively installing software or music, but as it is, the primary benefit of having a card like this is that I can now take 40,000 pictures before I run out of space.

Outlook integration is still incredibly useful, but it's been harder to keep the calendar in sync than I thought. This is probably due to the fact I get lots of meeting invites that change, but it's made it difficult to rely on the phone as the 'authoritative' source for my scheduling information I hoped it would be.

J2ME is a non-starter on this phone. There is a JVM, but it's buried under a submenu and the applications running on it look more like 'steerage class' than 'first class' citizens of the phone. They aren't integrated with the main application launcher, and their interfaces look like something out of 1988. I really get the impression that the phone has J2ME solely for the purpose of selling into corporate clients with a requirement to run custom J2ME code.

Given the power of the underlying hardware and the quality of the display, I was hoping to find more games for the phone. My previous two phones both had small collections of J2ME games purchased through my service provider's web site. AT&T has finally started adding games for this phone to their site, but the selection is limited, expensive, and not that great. I did at least find a few games elsewhere that are pretty fun, Atomic Cannon and Nethack. These were both pretty easy to install. Atomic Cannon, in particular, demonstrates the graphics of the phone quite well.

I don't use the 'Phone as Modem' capability at all. I don't have as many places where I need to use it as I thought. That said, it does work, and would be a nice way to check mail in a pinch.

reddit this! Digg Me!

In my career, I've done a bit of switching back and forth between Emacs and various IDE's. One of the IDE features I've come to depend on is quick access to the compiler. Typically, IDE's make it possible to compile your project with a keystroke, and then navigate from error to error at the press of a key. It's easy to recreate this in Emacs. The following two expressions make Emacs work a lot like Visual Studio in this regard.

(global-set-key [(shift f5)] 'compile)
(global-set-key [f12] 'next-error)

After these forms are evaluated, pressing Shift-F5 invokes the compile command, which asks for a command to be run in an inferior shell, typically make, ant, or some other build utility. The catch is that it runs the command in the directory of the current buffer, which implies that the build script can be found in the same directory as the current source file. For a Java project with a per-package directory hierarchy, this is often not true. There are probably a bunch of ways to fix this, but I've solved it with a Windows NT batch file, ant-up.bat, that repeatedly searches up the directory hierarchy for build.xml. I just compile with ant-up, rather than a direct invocation of ant. This is not the most elegant solution, I'm sure, but it took about five minutes to implement and works well.

@echo off

setlocal


:retry

set last_path=%CD%

echo Searching %CD% ...

if exist build.xml goto compile-now

cd ..

if "%last_path%"=="%CD%" goto abort

goto retry

:compile-now

call ant -k %1 %2 %3 %4 %5

if errorlevel 1 goto failure

goto success

:abort

echo build.xml not found... compile failed

:failure

exit /b 1

:success

exit /b 0

reddit this! Digg Me!

Lately, I've been thinking a bit about the way language design influences library design. My line of thought started out inspired by some of the recent conversations about closures in Java, but it ended up also touching on dynamic typing and a few other 'modern' language features. This will end up being more than one post, but I thought I'd record some of it in my blog, with the hope that it might shed some light for somebody, somewhere.

To motivate this discussion, I'll use as an example a simple C implementation of a string-interning function, intern_string. If you're not familiar with the concept of interning, the premise is that interning two objects ensures that if they have the same value, they also have the same identity. In the case of C strings, interning ensures that if strcmp(intern_string(a), intern_string(b)) == 0 holds true, then intern_string(a) == intern_string(b) also holds true. Since it effectively means that each string value is only stored one time, this technique can reduce memory requirements. It also gives you a cheap string equality comparison: checking two interned strings for equality reduces to a pointer comparison, which is about as fast as it gets.

Given a hash table that compares keys by value, implementing the function string_intern is fairly simple. In the following code code, intern_table is a hash table that maps strings to themselves. hash_ref, hash_set, and hash_has are functions that manipulate the hash table:

int hash_has(hash_table_t ht, char *key) - Returns TRUE or FALSE, depending on whether or not the key key is found in the hash table ht.

char *hash_ref(hash_table_t ht, char *key) - Returns the value bound to the key key by the hash table ht. If the key is not found, behavior is undefined.

char *hash_set(hash_table_t ht, char *key, char *value) - Binds the value value to the key key in the hash table ht. If the key is already present, the existing value is overwritten. This function returns value.
Note the critical assumption that the hash_* accessors implement key comparison by value sementics, strcmp, rather than identity semantics, ==.

   hash_table_t intern_table; // assume this is initialized somewhere else.

   char *intern_string(char *str) 
   {
     if (hash_has(intern_table, str))
        return hash_ref(intern_table, str);
    
     char *interned_str = strdup(str);
  
     hash_set(intern_table, interned_str, interned_str);

     return interned_str;
   }

The first step of intern_string is to check to see if the intern table already contains a string with the value of the new string. If the new string is already in the intern table, then the function returns the copy that's in the table. Otherwise, a new copy of the incoming string is created and stored in the hash table. In either case, the string returned is in the the intern table. This logic ensures that every time intern_string is called with a str of the same value, it returns the same exact string.

If you haven't guessed already, the problem with this implementation of intern_string lies in the dual calls to hash_has and hash_ref. Both calls involve searching the hash table for the key: hash_has to determine if the key exists, and hash_ref to retrieve the key's value. This means that in the common case, interning a string that's already been interned, this implementaion searches the hash table twice. Double work.

Fixing this problem involves changing the calling conventions for hash_ref. One of the simplest ways to do this involves defining a specific return value that hash_ref can return in the 'key not found' case. For strings in C, NULL is a logical choice. This change to hash_ref makes it possible to remove the double search by eliminating the explicit hash_has check:

   hash_table_t intern_table;

   char *intern_string(char *str) 
   {
     char *interned_str = hash_ref(intern_table, str);

     if (interned_str == NULL) 
     {   
        interned_str = strdup(str);
  
        hash_set(intern_table, interned_str, interned_str);
     }

     return interned_str;
   }

For this string interning, this change to hash_ref interface works fairly well. We know that we'll never store a hash key with a NULL value, so we know that NULL is safe to use for signaling that a key was not found. Were this ever to change, this version of hash_ref doesn't return enough information to distinguish between the 'key not found' case and the 'NULL value' case. Both would return NULL. To fix this, hash_ref needs to be extended to also return a seperate value that indicates if the key was found. This can be done in C by having hash_ref return the 'key found' flag as a return value, and also accept a pointer to a buffer that will contain the key's value, if it's found:

   hash_table_t intern_table;

   char *intern_string(char *str) 
   {
     char *interned_str;  

     if (!hash_ref(intern_table, str, &interned_str))
     {   
        interned_str = strdup(str);
  
        hash_set(intern_table, interned_str, interned_str);
     }

     return interned_str;
   }

This is probably about as good as you can get in straight C. It easily distinguishes between the 'no-value' and 'no-key' cases, it's relatively clear to read, and it uses the common idioms of the language. However, C is a relatively sparse language. If you're willing to switch to something a bit more expressive, you have other choices.

One example of this is a choice that's particularly well supported by dynamically typed languages. With a language that can identify types at runtime, it becomes possible for hash_ref to return values of a different type if the key is not found. This value can be distinguished from other return values by virtue of the run time type identification supported by the language. In one such language, Scheme, this lets us implement intern-string like this:

 
   (define *intern-table* (make-hash :equal))

   (define (intern-string str)
    (let ((interned-str (hash-ref *intern-table* str 42)))
     (cond ((= interned-str 42)
             (hash-set! *intern-table* str str)
              str)
           (#t
             interned-str)))))

If you prefer C/JavaScript-style syntax, it looks like this:

 
   var intern_table = make_hash(EQUAL);

   function intern_string(str)

   {
      var interned_str = hash_ref(intern_table, str, 42);

      if (interned_str == 42)
      {
          hash_set(intern_table, str, str);
          return str;
      }

      return interned_str;
   }

In this case, hash_ref has been extended with a third argument: a default return value if the key is not found. The above code uses this to have hash_ref return a number in 'no value' case, and it's the type itself of this return value that ensures its distinctness. This is a common dynamic language idiom, but for a moment, consider what it would look like in C:

   hash_table_t intern_table;

   char *intern_string(char *str) 
   {
     char *interned_str = hash_ref(intern_table, str, (char *)42);

     if (interned_str == (char *)42) 
     {   
        interned_str = strdup(str);
  
        hash_set(intern_table, interned_str, interned_str);
     }

     return interned_str;
   }

At first, this actually seems like it might a plausible implementation of intern_string. My guess is that it might even work most of the time. Where this implementation gets into trouble is the case when an interned string might reasonably be located at address 42. Because C is statically typed, When hash_ref returns, all it returns is a pointer. The caller cannot distinguish between the 'valid string at address 42' return value and the 'no-key' return value. This is basically the same problem as the case where we overloaded NULL to signal 'no-key'.

The way the dynamically typed language solved this problem is worth considering. When a dynamically typed language passes a value, what it's really doing is returning a pointer along with a few extra bits describing the type of the object being pointed to. (Runtime implementations might vary, but that's the gist of many.) Using dynamic typing to distinguish between those two possible cases really amounts to using those few extra type bits to contain 'another' return value, one holding information on whether or not the key was found. This is exactly what our 'best' C implementation does explicitly with a return value and a reference value. The dynamic typing isn't necessarily adding any expressive power, but it is giving another, concise means of expressing what we're trying to say.

reddit this! Digg Me!

It seems that it's been a while since I've posted: about four months. That's longer then I meant, but isn't that always the case?

In the four months since I've not been posting, Ryan has crawled, learn to walk, learned to talk a little, and learned to respond to simple questions. Personally speaking, I've worked a bit on vCalc, not to mention the more important bill-paying work of my full time day job. Personally, I think Ryan is making me look like a slacker, but I suppose that's a matter of judgement. :-)

Anyway, I hope your holiday season was all you wanted it to be, and Happy New Year. I have a few ideas for new posts, so with some luck, the next gap won't be four months long.

reddit this! Digg Me!

Ryan, believe it or not, turned one last month. Rather than write too much about it, I'll let this video of his first year speak for itself. Please enjoy!



reddit this! Digg Me!

For the better part of my career, I've straddled the fence between pure software development roles and consulting roles. My first job after graduating in 1997 was at a hardware firm developing embedded software for process control hardware. Over the three years I was working there, I was on point for everything from register-level device drivers running on the custom hardware to a device configuration GUI running on a PC. By the time I left the firm, I even had the opportunity to write a small programming language, complete with compiler and 'VM'. This was a perfect job for a guy with a freshly-minted Computer Science degree and a hankering to write some cool code. At least it was perfect at first.

What ultimately drove me to leave that role is something that I think most technical jobs, particularly those in product development, have in common: a severe risk of detachment from your clients. Software developers, myself included, tend to be an introverted lot; Even if they weren't, it's oftentimes percieved to be in the best interests of a software house to keep software developers on task developing software. In other words, there are both personal and corporate pressures to keep developers hacking away at the code instead of talking to customers. The risk here is that the people who best understand the products are the people that potentially least understand the customers. I can tell you from firsthand experience that, while I knew in detail the sampling characteristics of the device I was building, I had no idea how it might be used in a chemical plant to measure a temperature sensor and control a pump or a heater. It's easy to develop a product in that kind of vacuum and then get it totally wrong for your market. If you're not careful, it's also easy to get your product totally wrong for your own company, which is what arguably happened to the group I was in.

Organizations counter this risk of specialization by having other job roles that can be more focused on customer needs and less focused. From the perspective of someone sitting in an R&D lab, these other jobs represent the steps a product takes out the door towards doing useful work for a customer. A researcher discovers a new technology or technique, a developer turns it into a product, a marketer figures out how to promote it, a salesperson sells the product, and finally, a consultant integrates it into the customer's system. As work moves down this path, it gets progressively more applied and progressively less abstract. The reverse is true too: the further away from pure research you get, the closer you get to customer requirements. As much as a development lab has the responsibility to push product out to customers, customer-facing staff has the responsibilty to push information on customer requirements back to the lab to drive product development priorites. If a developer isn't talking to a customer and a consultant is, then it's a safe bet that the consultant has a better idea of what a product needs to do to sell.

This is the reasoning that led me out of pure software development and into a consulting role at a different firm. In this new role, I was on projects developing configuration websites for computer resellers. If you envision Dell's online computer configuration tool, you're not far off from the kind of websites I was developing. While consultants at this company still did a bit of programming, the theory was that the heavy lifting of actually building the software was done in the company's R&D lab. Consultants were to focus on more basic customization and integration work. On my projects, most of my software devlopment work was limited to customizing the layout of web pages and writing interfaces to databases and authentication providers. Interesting stuff, but not close to the same technical league as what I was doing in my previous job.

The risks in this kind of internal consulting role are different than the risks in a purely development role. Unlike a developer sitting in an R&D lab, someone who might get to see a customer once a month or two at best, a consultant quite often is working on-site with the customer on a daily basis. In fact, It's easy for a consultant to see customer staff far more often than other employees of their own company. Of course, this potential isolation also includes the R&D lab and the sales group. In the worst case scenario, you end up with three independant silos in your organization: sales selling whatever they want, developers developing whatever they want, and the poor consultants caught in the middle, between an over-ambitious contract and a under-done base product. I shared an office with a guy working on a project that was sold as a one month customization of one of our other base products. When I joined the firm, this project was in its 18th month of (mostly non-billable) consulting time. There was obviously a lot that had gone horribly wrong on that project, but foremost was a total disconnect between what the salespeople thought they had ready to sell and what the developers had actually produced to sell. (Not that the consultants were blameless on that project either: there were huge estimation and process problems in the customization work plan.)

I do not know of a role that is completely free of these types of risks, but my experience has tended to be that the difference between success and failure in any role is more related to communication with those around you than it is to technical skills. It is as much about giving your stakeholders what they want when they want it as it is anything else (including giving them something 'great'). This can be a difficult pill to swallow since it places emphasis on skills that do not come naturally to many developers. If you're a developer used to setting the development agenda it's even worse, since it might involve ceding at least some of this power to people downstream and closer to customers. However, if you're really good, you will do whatever it takes (even it it's 'not your job') to know your customer's business well enough to anticpate what they need before they request. Either way, success is ultimately about pressing your boundaries beyond your comfort zone to get what you need to do the thing you love in a way that satisfies those that care about your work.

reddit this! Digg Me!