The history of the Schwartzian Transform (2016)

Summary

The History of the Schwartzian Transform Sep 2, 2016 by brian d foy The history of the Schwartzian Transform is fascinating, full of intrigue, competing philosophies, and cross-language reluctant cooperation. The Schwartzian Transform is the name applied to a particular implementation of a cached-key sorting algorithm. The first public appearance is probably Randal Schwartz’s Usenet post on December 16, 1994 in response to Ken Brown’s request for help: I’m having trouble sorting on the *last* word of the last field in a record Ken Brown Randal included the following code in his reply: #!/usr/bin/perl require 5; # new features, new bugs! print map { $_->[0] } sort { $a->[1] cmp $b->[1] } map { [$_, /(\S+)$/] } <>; Randal didn’t name it. He wrote the code and essentially dropped the mic. He says that he was on a break from teaching a Perl class, so his response was brief and unexplicated - typical for an experienced Usenet denizen (he said that he was there when you could read all of Usenet in a half hour). I don’t think he expected it to be as troublesome as it turned out to be. His code isn’t that complex. It’s a big statement, but when I teach it in Perl classes, I tell people to read it from the end toward the beginning (a handy technique for any list pipeline): The first step computes the key to sort on. It combines that with the original value in a tuple. The middle step sorts of the computed element in the tuple. The last step extracts the original value from the tuple. You probably can’t imagine how shocking this could be back then. Perl 5 was officially released in October 1994, but the first development versions had been around since the middle of 1993. Randal was surely playing with Perl 5 as soon as it came out. This means that most Perl programmers had not yet seen new features like the map function or references. They certainly weren’t comfortable with those ideas. Randal, however, knew the decorate-sort-undecorate technique from LISP, especially since h...