Mike Schaeffer's Weblog
Fri, 22 Feb 2008
Renaming SVN Users on Windows
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!

[/tech/programming] permanent link

Thu, 14 Feb 2008
CAR, CDR, and Lisp...
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!

[/tech/lisp] permanent link

A correction and another blog.
  • 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!
  • [/tech/general] permanent link

    Mon, 11 Feb 2008
    Renaming historical users (svn:author's) in SVN repositories
    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!

    [/tech/programming] permanent link

    Fri, 01 Feb 2008
    Excel, CR/LF, and CSV
    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!

    [/tech/excel] permanent link