Sunday, November 18, 2007

What a wonderful feeling!

Dare I say it, but I believe I may have finally been granted my freedom on the Internet. It would be pointless for me to describe any details of my ordeal over these last few months. Let's just say that I kept on fighting back; but ultimately it was not my doing that has given me a voice again. I'm surrounded by cables going in all directions, supporting what is left of my computer lab. None-the-less, I'm so thankful to be back in a situation where I can freely get updates to Scheme and what's happening in the world. Along the way I unearthed some security policy mistakes, that would make me cringe now, but prior to my baptism by fire, I was totally clueless. I thought I was doing a pretty good job before I was hacked into the 19th Century. Well, I'll be back with an article taking a second look at the flatten functions, in the light of R6RS, and with it the disappearance of set-cdr! and set-car! Of course, this means that my own version of the flatten algorithm is now obsolete. I think of the change as merely raising the bar on how tight you can code in a truly functional way. And I know it's possible to achieve excellent results, since the Haskell folks have been turning out very respectable run times; albeit, with the aid of a highly structured type system. As long as I can achieve the same O(n) complexity out of my library of routines, I won't quibble over a few lost clock tics. After all, my interest is and always will be, the art of programming in one of the finest languages I've ever used. Thank you, who ever you are, for giving an old man a break. I've learned more than I'll ever possibly be able to use about security. Most importantly, though, I've learned that ultimately, being on the Internet is a luxury granted to you by folks that have enumerable tools at their disposal with which they can shut you down completely. So when I say thanks, I truly mean it. I'm off to rebuild another box, with an actual hard drive that will store my work beyond a reboot. I've become a huge fan of the Live CD and *nix in general. I'll likely never work on a Windows machine again; most of my commercial software on that platform was lost in the battle anyway. Not that I'm a MS basher, but when you simply have to get a job done, under extreme conditions, it's hard to under estimate the power of a single bootable Linux CD. Take care, --kyle

Tuesday, November 13, 2007

To whom it may concern:

Excuse me readers, as I write a personal note: TWIMC: By your actions yesterday it appears that you were less predictable than I thought, and you never got my message. Let me come to the point. If I'm correct, then you have nothing to fear; if I'm wrong, then God help us all. Give me back my freedom. --kyle

Thursday, September 06, 2007

The Calling Card of a Cyber Attack

The Assailant Left Behind Some Clues

In my last article I told you about my system being compromised. Since then, I have been by and large offline, because every time I plug my computer into my router, which stays disconnected on the wan side, there are literally dozens of processes using very odd port numbers, and there all listening for a reply from one of the two DNS servers I have configured on the standard port 23. If I had more sophisticated software, I'd be able to see which URI they are trying to resolve. Something is in the works, and I may be able to do that soon. But that's not my story. The story is that I now believe that the spam they sent out from my system was merely a distraction.

In my offline forensic work, amateur as it is, I've discovered several things. The details will be somewhat vague because I'm not trying to divulge their methodology, in fear that it will be picked up by others. But I will give you enough so that you can inspect your own systems, and see if you also have an intruder.

First of all, I now know that the intruder had been in my system far earlier than Aug 28th, when I went offline. In fact, if I had to guess, what happened on Aug 28th was a retaliatory strike against my blog, for having taken counter measures on my side against the intruders. But why were they there to begin with?

As I write this, I have just pulled an all night'er going over something the intruder left behind. The actual logs of my system settings on Aug 3rd. In fact, each of the logs are dated and time stamped in their name, not just the last modified date. Well, obviously these were huge logs, so I did a diff on them, incrementally by dates to see what had been changed.

The first one is dated syssettings.200708030841, or Aug 3, 2007 at 8:41am. When I diff it against the next one dated 200708030900 what I get is the addition of 156 entries under the group:

> swupdate:ItemsRecordsArray:_arrary_index:0-155:Description = <hex …>

And one modified line:

< swupdatelastChecktime = "2007-08-03 07:41:36 -0400"

---

> swupdate:lastChecktime = "2007-08-03 08:42:16 -0400"

So you can deduce that a software update was performed in between the two logs. All the data is in hex, but since they all end with 0a, macs preferred end of line character, it would seem to be, as the item indicates, a text based description. I haven't decoded them yet, because that's not what is significant. What is significant is that there were 156 updates, in the span of less than an hour, if you believe the lastChecktime stamps. My system, which I have owned for many months was set to auto-update, which meant that it was unusual for me to even get more than one (1) or two (2) updates at time. Why would they want these updates?

Well, as my system is the Server version of Mac OS X, it has the capability of mirroring updates, that, if I were properly licensed, could be used for network installs. But I only have one Mac, and I'm only licensed for 10 clients. The other computers that make up my lab are all MS XP boxes. This was my first outing with Macintosh.

I'm not going to discuss what I found in the diffs of the other files specifically, as I believe this would be to the advantage of other intruders. But I will say that the changes were made to my default printer configuration and the mail:postfix and mail:imap areas. So, the changes that occurred on Aug 3, 2007 were two pronged.

I had already been highly suspicious of what was going on with my computer, because XXX suggestions kept popping up in my iGoogle page as suggestions based on my Internet usage. Since, as you all know, I'm a 50 something retired geek who spends his time dreaming up interesting, at least to me, things to do with the language Scheme and assorted other functional languages, I was not a little disturbed that iGoogle would be suggesting I head over to the latest `Live Nude Girls' site. When I reviewed my search history, it was exactly what you would expect from a nerd. But, when I went to Google Reader, I discovered quite a different history. You'd think I was a nineteen year old horn dog from the list of sites that were displayed in my history. I tried in vain to get this corrected by Google. Since their security reporting system is form based, and while you can report abuse quite easily, you must have a specific post or email to provide them. I even tried using a fake email, so I could get through to somebody at Google, but they aren't that easily fooled. If anyone is aware of an way to submit a security related concern or simply email their security group, I would appreciate knowing how one goes about it.

So naturally I changed my Google password to something quite a bit stronger. However, after another month or so went by I started to get the same types of tawdry suggestions from iGoogle. This time I simply put in a password so long and random that I figured the odds of someone guessing it were essentially nil. Well, as I now know, they weren't guessing at all. Since these passwords were so long, they had to be stored on disk, and I was obliged to copy and paste them in whenever I needed to access my account. But your probably saying, this happened months before Aug 3rd, and you'd be correct.

That's where another piece of forensic work comes in to play. It turns out that quite a number of executables in /sbin had a different date than the others, when you view it with `ls -lc'. For those not familiar with *nix, the -c option shows the dates of last change, instead of the creation date. What makes this unusual is that the date is Jun 25 12:43 for the lot. Where as the few not affected are dated Nov 15, 2006, well before I had purchased the computer. [Author's Note: After some more thought, there is a benign explaination for this. If a single Apple update required newer versions of the majority of the programs in /sbin, then it is possible that they could have a different date, but all be the same.] The other interesting thing I discovered was as a result of recently learning that the reason I was never getting any color coding of file types in an ls listing, was that the default terminal emulator, that I had been using, didn't support color. For those familiar with *nix, it will come as no surprise that what I saw was an assortment of executables using black text on a red background. For those not familiar, as I was not until just recently, this indicates that a file has the SUID bit set. This does not show up in any standard usage of ls; by default all they present to you is the user, group, and other permissions. [Author's Correction: After a little sleep, I see that an `s' is used in place of an`x' in the user symbolic permissions when the suid bit is set. You see what you know, as I'm known to say with some frequency.] A file with SUID set will execute with the privilege of the superuser, regardless of the privilege of the user executing the program.

So, it is now seems clear that the intruder had gained access to my system through an escalating of privilege attack, and was probably inside my intranet prior to Jun 25, 2007. People thought, including myself, that I was over-reacting to a threat I could only vaguely describe, from the strange suggestions in iGoogle, and the various error messages that were showing up in my logs. I had even gone to the extent of making my OS X box nearly FIPS compliant, only lacking in the physical security department. But the audit logs take a while to figure out, and Apple's support system for their Server product is quite expensive. The cheapest support option is some $2,500. There's always the per incident option, which will put you back $200 a call. And, in fact, I made two such calls to sort out some odd behavior with my box. The last analyst I got told me to turn off the firewall that comes with the server, which is disabled by default. He told me I'd be fine with a hardware firewall router. But, if any of you are Steve Gibson fans, you should know that an external firewall can't block a process that has no business going out to the Internet, because it only cares about the port that a packet is going to, and as long as that packet is well formed, and the port is not blocked because it's a common port for outgoing traffic, the firewall is obliged to send it on its way. And since the conversation initiated from within the intranet, it will gladly accept well formed responses, as long as they are correct for the state of the conversation. [Author's Note: There may exist security devices that can be configured to work with software on the computer to identify the process that is sending out a packet. I'm not a router guru. I just know that I've never owned a router that has this capability.]

So, I didn't turn off my firewall. In fact, I got a much better software firewall, that actually showed me where the packets were going, and from which process they came from. However, the intruder had rigged `ipfw' (Apple's not so comprehensive out of the box firewall). So, the better firewall was being foiled by the infected `ipfw'. It wasn't sufficient to merely stop ipfw from the cute little GUI interface apple has for their *nix daemons. I had to physically quarantine `ipfw'; but, of course, this was way too late for anything to stop the damage already done. It only provided some additional forensic evidence.

I have megabytes of forensic evidence, but I'm still facing a complete re-installation of all my computers. You see, at some stage, either early on to begin the attack, or later on, to continue the attack, despite my precautionary measures, they were using the XP boxes to gain access to the server. The infection completely shuts down Norton 360, whenever you reboot the computer, and even while 360 appears to be scanning, and giving a clean bill of health to your system, the infection is raging. In fact, the more you do to prevent it's operation, the more it cripples your system, even attacking DVD/CD drivers leaving you no solution but to live with the infection or rebuild from scratch.

As I promised, I'll give you a list of warning signs about this particularly nasty infection.

First of all, make sure you have audit enabled on your system. I don't have the link handy, but if you search the Apple Knowledge base for audit, you should get the appropriate pdf that gives you everything you need to know about becoming as FIPS compliant as you want to.

Second, buried in my printer log, I now know, were early signs of the infection. The messages are few and far between, but they will indicate that postfix is running with `root' privilege's. This should never be the case. Postfix has a postfix account that it should be running on.

Another clue, is to run

$ sudo ps -Ao 'pid, uid, user, command' | less

If you notice that all your daemons are being executed by either yourself, www and root, you have got a serious problem. You might even see the unknown user in the above command or in your logs listed as `[uid -2] [gid -2]'. This would be a bad thing.

And then there are countless other error messages that refer to out of range parameters to empty arrays, that typically coincide with a malloc error message. When I brought this to Apple's attention on my second service call, they told me I must have been out of memory. Yeah, on a 4GB machine, I'm out of memory. I don't think so, and neither should you.

One final bit of information. While searching for these error messages, I ran across a very strange site, forgive me, I don't have the URL at hand. It detailed an attack that exploits the postfix system in OS X, and insures it's survival by infecting the program responsible for resetting permissions on an OS X drive. The sign of infection will be that the program has a strangely recent last modified date. They use this program, because Apple, in it's wisdom, has chosen to have it's SUID bit set. And, if you've ever called Apple for support, you know that the first thing they have you do is run this program. In fact, the documentation suggest that you run it after any application installation. This is wise advice, since the install may have left inappropriate permission on directories. But, by allowing any user to run the program, it becomes a natural target for exploits, since it runs as root. Again, I'm leaving out details on purpose. Why anyone would publish such a thing is beyond me, but in their minds they feel they are ultimately doing good. So, their site will continue to provide would be intruders with well thought out exploits.

I'm not so sure I've done you much good either, since by the time your seeing these messages in your logs, it's probably too late. But at least you would know to take your machine off the Internet, where it is no doubt infecting other machines.

And the motive behind these intrusions may well be to steal Apple software. From what I see in the logs left behind, it appears that they are using the zombie machines to access the built in capability to deliver client software from an Apple server. This ought to be a top priority for Apple, since every server they infect, could conceivably be delivering countless clients, free of charge to the intruders.

I wish I could end this post with my usual Enjoy! But I'm afraid today, it's more appropriate to say,

Be Alert,

--kyle

Saturday, September 01, 2007

Thanks to Blogger.com

My Apologies

On or about Aug 28, 2007, my system was compromised. This resulted in what I understand was offensive content either directly posted on my blog, or perhaps sent to persons in my contacts list. As I had shut down my Internet exposure after discovering that my system had been compromised, I do not know what happened specifically, other than that yesterday, Aug 31, 2007, I learned that the good people at blogger.com had shut down my site for inappropriate content. First I would like to thank the folks at blogger.com for taking this prudent measure, and for correcting the matter within less than 24 hours after I was able to get back onto my account and read their message to me. I never saw a message from blogger on my personal email address, so I was left with no options at first to find out why I couldn't gain access to my Gmail account or my blog, as my Gmail account had also been turned off. It was very frustrating at first, because none of the forms in the security center at blogger.com allowed me to communicate my concern without entering a valid Gmail account, which at first appeared deleted.

However, shortly after I had signed up for another Gmail account, in an attempt to communicate to blogger.com, my original Gmail account became active again, which is when I discovered that they had sent me a message indicating that it had been shutdown, and assured me a human would look at it within a day. To my delight, true to their word, this morning I found my blog back online. I deeply appreciate their rapid response, to what I understand, from their message, was the result of a phishing scam that affected many sites on blogger.com, not just my own. Security is best left to the experts. It is quite humbling to realize you have no 100% effective means of protecting you online identity. I have implemented all blogger.com's suggestions regarding protecting my site, but one can never be certain of anything. I am just very grateful that I have my site hosted by blogger.com, who so effectively handled the problem, even when I was not available. The restoration of my site appears to be complete, from my quick browsing through my various articles. If anyone notices some unusual or inappropriate language in one of my articles or comments, please leave a comment, and I will correct it as quickly as possible.

To those who may have received some sort of spam or offensive material, either from visiting my site, or by email, please accept my apology. I was truly helpless to stop it from happening, and I have tried to implement all prudent measures to prevent it from occurring again, but I assure you that I was trying to prevent a compromise to my system to the best of my ability, and still my private information was exposed. I had an email discussion with my good friend Jens Axel Søgarrd on this matter prior to the event, and we both agreed that there was only so much that one could do, short of going offline completely. As I said before, it was quite humbling to witness personally. The people who do this sort of thing are not amateurs. They exploit vulnerabilities in very sophisticated ways, and in the end, you can only hope that you have done everything you know how to do to prevent it from happening to you.

While I'm apologizing, I would like to say that my last article made mention of a bug I had corrected in the author's code, in the client software for the Quantum Random Number Generator. I recently discovered the author's email reply to me had been sent to an account I rarely use, so I only recently learned that he had corrected me. The code as provided on their site is correct, and it was I that had made a mistake in interpreting it. Amazingly, my port of the code, which included an inaccurate correction to the original, still worked without a problem, most likely because the section of code that I changed involved option handling, and I had hard coded the options that were appropriate for my use, so my use of my buggy code did not expose the problem. I am quite human, and vulnerable to making mistakes. When I become aware of a mistake in an article that I have published, I have and will always post a retraction. It is the only decent thing to do if you wish to be taken seriously. I welcome any corrections anyone finds in my articles, and will publicly admit the misstatement, so that you can be assured that, to the best of my knowledge, what I post is accurate. That is one of the pleasures of presenting this blog to my readers; I get the benefit of peer review, and I have learned more than a few things through the insightful comments left on my articles. Please keep them coming.

Sincerely, with my apologies to anyone affected,

--kyle

Sunday, July 22, 2007

Quantum Random Bit Generator Service

Random Bits from Zagreb, Croatia

Once in a while, something worthy of being called a Web Service comes on the scene, that makes the internet a better place. Radomir Stevanović, B.Sc., a Research assistant, PhD student, at the Ruder Boskovic Institute, Centre for Informatics and Computing, located in Zagreb, Croatia has put up a wonderful resource to aid researchers all over the world. It is called the Quantum Random Bit Generator Service. Rather than using cumbersome equipment to generate random numbers from quantum events yourself, Radomir has made a very simple Web Service that takes requests for N bits of random numbers, pre-formated in any of the usual C integer and float types, which you can choose from when you make the request. He even provides source code for the interface.

As my readers are aware, this blog is about Scheme. So you may be waiting for the punch line, "I ported the interface to Scheme." Well, not yet. I returned to my roots as a C++ programmer, and merely ported the supplied C++ code to the Mac OS X, using the Intel C/C++ compiler v10.0.016, which allows me to generate code specifically optimized for the two dual core Intel Xeon processors under the hood. The gcc compiler that Apple ships with their Mac Pro's doesn't have that capability. The port went splendidly. I just had to clean up a couple of the author's typos, you know the difference between `=' and `==' in C++, and how easy, and dangerous, it is to get them wrong. It was fun hacking up C++ again, but I don't miss those kind of silly mistakes that can take you hours to find. Lucky for me the Intel compiler provided a very prominent warning, so the credit really goes to the compiler.

After I hard coded into my version my account name, password, as well as changing all the default values to the ones I would typically use, and got it compiled without any warnings, it work the first time like a charm. There is a quota system in place, however, for now it appears that they have got everyone set to unlimited. As I intend it to merely replace a call to the pseudo random number generator in Scheme with a request to their service, I can't imagine I'll be a noticeable hit to the bandwidth of their server, even if they did have a limit. When I hack up the Scheme version I'll post the code here.

Their site proudly displays their average entropy, and the number of gigabytes that they've served up, as well as the average of all bytes served, which, not surprisingly is near dead on 127. And they have plans for even easier access to their service in the future. For now, they lack a secure protocol for obtaining your bits, which means nothing, unless you were going to use it to generate cryptograms with their data. However, they have secure access in the works. But for scientific work, this is already a real win. I hope they keep their non-secure service freely available to scientists, and make their money off the secure access.

Oh, and by the way, be prepared to solve some differential equations before you can get an account. I thought that was a nice touch; instead of typing in goofy looking letters to prove your human, you have to do a math problem. At their site, you have to prove you have mathematical competency as well as being human.

Enjoy!

--kyle

Monday, June 25, 2007

The Flatten Benchmark Results

Four Flatten Scheme Functions Benchmarked

Finally, the results are in, and the graphs are ready to present. After my last article, I received two (2) new excellent functions from two different readers, and they both do very well, beating my own version of flatten when benchmarked on a favorable Scheme implementation and given a favorable range of list complexity. What I show in todays article are the results of four (4) functions when run on four (4) different Scheme implementations, and for a range of list complexities starting at complexities of 1.93 x 10^3 up to 1.93 x 10^8, and on two Scheme implementations up to 3.86 x 10^8.

The complexity of a list was determined by a simple Scheme function, included in the flatten-benchmark.ss source, that sums the number of pair?'s and atom?'s in a list. This turns out to be a very accurate measure of the input length to a function, and a vast improvement over simply reporting the "length" of a list. Throughout this article, and on the graphs, it will be referred to as the "Complexity" of a list.

The list was constructed by successive cons'ing of what, in the benchmark source, I call a list-segment. Each list segment was composed of three sub-lists. The final list segment looked like this:

(a
 (b (c (d (e (f (g (h (i (j (k (l
    (m n)
 o) p) q) r) s) t) u) v) w) x) y)
 z a b c d e f g h i j k l m
 n o p q r s t u v w x y z a
 (b 
  (d (i q r) (j s t)) 
  (f (k u v) (l w x)))
 (c 
  (g (m y z) (n aa bb)) 
  (h (o cc dd) (p ee ff))))

When I refer to lists of a certain length, I'm not referring to the Scheme function by the same name, but rather to the number of list-segments, as above, iteratively cons together. Thus when I say I started with lists of length 10 up to 100 step 10, I mean to say ten (10) list-segments up to one hundred (100) list-segments step ten (10), whose (length test-list) => just happens to be 10 up to 100, but whose complexity is equal to 1930 up to 19,300. Lists of length two (2) million, therefore, had complexity of 3.86 x 10^8.

The graphs show the relationship between the "Adjusted Real Time (ms)" of execution in milliseconds on the y axis vs. the unit-less "List Complexity" on the x axis. The "Adjusted Real Time" is simply the real time of execution for a function, extrapolated to equal the real time of execution for a list of given complexity, if that function had executed one thousand (10^3) times over the same list. This was done to provide continuity over all graphs. The actual test runs were conducted using list lengths, that started at lists of length 10 up to 100 step 10, run for 1000 iterations, and progressed, by orders of magnitude, up to lists of length one million, and for two Scheme implementations, up to lists of length two million. But as the list lengths increased, I necessarily had to reduce the number of iterations, in order for the results to be collected in a reasonable amount of time. You will, therefore, see "Adjusted Real Time" reported, when testing lists with lengths over one million, which were only executed for a single iteration, but have been adjusted by multiplying the actual real time of execution by 10^3. Like wise, if an actual run was made for 100 iterations, then the "Adjusted Real Time" is equal to the actual real time of execution times ten. All runs for lists shorter than length one hundred thousand were run for at least ten iterations. Naturally, the precision of the numbers reported for lists of greater complexity suffers from this method, however, as you will see, this loss of precision was not significant, compared to the effects of the ever dwindling available memory that showed up in all Scheme implementations, more notably in some than others.

You may be wondering why I chose to scale up the different runs according to list length instead of complexity. The answer is that it was a matter of convenience on my part. It was just very simple to increment each run by powers of ten, which is easy to achieve using lengths. I covered every order of magnitude with ten data points for each function, and, in the cases where I was able to execute out to lists of length two million, I gathered ten data points for the span between one and two million, in steps of 100,000 for every function. The complexities of each list were calculated just prior to each data point collected. The benchmark could have been designed in such a way as to pre-calculate all the complexities, and store them in a top-level vector, but I have designed the benchmark to accept an arbitrary list, as well as all the other test parameters, interactively to facilitate early experiments. When I settled on the common testing parameters to use across all Scheme implementations, I simply fed them in via a shell script that ran all the tests for a given implementation as one job.

As introduction, I present the four (4) functions and give specifics on their origin and a brief description of the algorithm that they employ. The two reader contributed functions go by the names "flatten-Eugene" and "flatten-Sacundim", after the names of their respective authors. The other two functions are named for features they employ, so the function "flatten-accum-cons-sans-reverse", uses an accumulator style of function, which employs the Scheme primitive "cons" to build its result list back to front, but doesn't actually reverse its result list. Finally, the function "flatten-set-cdr!" is the function I wrote and presented in my previous article, which employs the Scheme primitive "set-cdr!" to build its list in the order of visitation of the elements of the input list.

It may seem unfair to compare a function, that returns a reversed list as its result, to the other functions, which all build their lists in the order of visitation of the input list. While that is true, "flatten-accum-cons-sans-reverse" was included as a kind of gold standard for the other functions to beat, and as you'll see, Eugene's function did just that in data collected on several test runs.

flatten-accum-cons-sans-reverse

This function serves as the gold standard. I wrote it myself, but I'm not the original author, as it is too obvious a solution to have not previously been written. Unfortunately, I don't know who the original author is, and perhaps no one does. If you happen to know this bit of Scheme trivia, I will be glad to share it with the rest of the readers and give the original author their due credit. Since it doesn't reverse its result list, it can only be employed in applications in which the order of visitation of its argument need not be preserved. As far as I know, it is the fastest way to non-destructively flatten a list in Scheme.

(define (flatten-accum-cons-sans-reverse x:xs)
  (define (f x:xs result)
    (cond
      [(null? x:xs) result]
      [(pair? (car x:xs)) 
        (f (cdr x:xs) (f (car x:xs) result))]
      [else (f (cdr x:xs) 
        (cons (car x:xs) result))]))
  (f x:xs '()))

flatten-set-cdr!

This is the function I posted in my initial article. It is a diversion from accumulator style functions in that instead of passing the result list around as an argument, it uses the lexically bound identifier "last-elt" to keep track of the last pair in the "let bound" result list, thus allowing set-cdr! to mutate "last-elt" to establish the link to each successive cons pair? constructed in the result list. I know this is in violation of "The Eleventh Commandment", as per Friedman and Felleisen in their classic 1996 book, "The Seasoned Schemer", but I will let the results speak for themselves.

(define (flatten-set-cdr! x:xs)
  (let* ([result (cons '() '())]
         [last-elt result])
    (define (f x:xs)
      (cond
        [(null? x:xs) result]
        [(pair? (car x:xs)) 
          (f (car x:xs)) (f (cdr x:xs))]
        [else 
          (set-cdr! last-elt 
                    (cons (car x:xs) '()))
          (set! last-elt (cdr last-elt)) 
          (f (cdr x:xs))]))
    (f x:xs)
    (cdr result)))

flatten-Eugene

This is an elegant function which uses two helper functions to avoid the necessity to reverse its list. Eugene Wallingford wrote this function as the answer to an exercise in the 1st ed. of EOPL, which he taught from at The Univ. of Northern Iowa, until the 2nd ed. of "Essentials of Programming Languages" dropped its emphasis on Scheme. The original problem asked for the student to write a function to flatten a proper list of symbol?'s. Thus, in Eugene's function, as he sent it to me, he used the predicate symbol? where each of the other functions use pair?. To put his function on equal ground with all the other heterogeneous list flattening functions, I made the trivial conversion from symbol? to pair?, which simply required the reversal of the order of the two expressions within the "if" expression of "flatten-sym-expr". In results from tests not shown in this article, there was no noticeable degradation in the performance of Eugene's function for having made the change.

(define flatten-with-accumulator
  (lambda (slst symbols-so-far)
    (if (null? slst)
        symbols-so-far
        (flatten-sym-expr
         (car slst)
         (flatten-with-accumulator 
           (cdr slst) symbols-so-far)))))

(define flatten-sym-expr
  (lambda (sym-expr symbols-so-far)
    (if (pair? sym-expr)
        (flatten-with-accumulator 
          sym-expr symbols-so-far)
        (cons sym-expr symbols-so-far))))

(define flatten-Eugene
  (lambda (slst)
    (flatten-with-accumulator slst '())))

flatten-Sacundim

This function is an ingenious attempt to improve on flatten-set-cdr! by placing all recursive calls in tail position, and employing an additional argument within the loop, that maintains a list of outstanding non-null cdr's of previous pairs, that remain to be processed after the car of a pair? has been processed. It does this at the expense of adding another conditional statement inside the loop, and with an additional cons cell constructed for each pair? seen who's cdr is not null. It was left by a brave reader as a comment, without an email address to reply to the reader directly, so I know very little about the details of its origin, other than what was said in the comment, which you can find at the bottom of my previous article. I'm not even aware of the authors full name. None-the-less, as I promised, I placed the function in with the pack to be benchmarked, and it turned in a very fine performance, especially when compiled.

(define (flatten-Sacundim list-of-lists)
  (let* ([result (cons 'will-be-thrown-out '())]
         [last-pair result])
    (let loop ([remainder list-of-lists]
               [stack '()])
      (cond
        [(null? remainder)
         (unless (null? stack)
           (loop (car stack) (cdr stack)))]
        [(pair? (car remainder))
         (loop (car remainder) 
               (cons (cdr remainder) stack))]
        [else
         (set-cdr! last-pair
                   (cons (car remainder) '()))
         (set! last-pair (cdr last-pair))
         (loop (cdr remainder) stack)]))
    (cdr result)))

The astute reader may be asking why the identifier "last-pair" is colored differently than other identifiers. The answer is that the program I wrote and use to syntax colorize Scheme code posted to this blog, is at once perceptive enough to recognize the identifier for a popular srfi-1 function of the same name, but lacks a sufficiently sophisticated parser to see that the identifier is lexically bound within the function. It's on my very long TODO list before I release "format4blog", which I have previously posted about. If you are in need of this type of service for your own blog, I highly recommend you use Jens Axel Søgarrd's Paste Scheme service.

Results

Here are the graphed results presented grouped by Scheme implementation in alphabetical order. Within a Scheme implementation they are presented by first showing an overview graph of the entire data set for an implementation, followed by graphs of the same data set, truncated at descending list complexity, by steps of powers of ten. After the graphs, I'll provide some analysis, from my perspective, on the results, and finally end with what I feel is the take home message from this effort.

To make full disclosure, let me tell you that all tests were conducted on a Mac Pro Server, OS X v10.4.9, with 4gb's of physical memory installed, and two duo core Xeon Processors, each running at 3gHz. No other applications were in the foreground while these tests were being conducted. There were some background processes that I could not safely squelch during testing, but none were actively allocating memory to any measurable extent, and likewise, all 4 cpu's showed no significant activity prior to the beginning of a test run.

Chicken

Chicken_EntireDataSet
Chicken_Complexity_LT_e07
Chicken_Complexity_LT_e06
Chicken_Complexity_LT_e05
Chicken_Complexity_LT_e04

DrScheme

DrSchemeEntireDataSet
DrScheme_Complexity_LT_e07
DrScheme_Complexity_LT_e06
DrScheme_Complexity_LT_e05
DrScheme_Complexity_LT_e04

MzScheme

MzScheme_EntireDataSet
MzScheme_Complexity_LT_e08
MzScheme_Complexity_LT_e07
MzScheme_Complexity_LT_e06
MzScheme_Complexity_LT_e05
MzScheme_Complexity_LT_e04

Petite Chez Scheme

Petite_EntireDataSet
Petite_Complexity_LT_e08
Petite_Complexity_LT_e07
Petite_Complexity_LT_e06
Petite_Complexity_LT_e05
Petite_Complexity_LT_e04

Analysis

I typically pull images off my web site, but this time around I thought I would give Flickr a try. The graphs load quite quickly for me, and my internet connection is a standard residential ADSL line to my home office. Let me know how this works out for you; if I get enough feedback that they are taking too long to load, I'll move them back onto my website and/or reduce their size.

I received excellent support from Felix at Chicken. Once he gave me a few pearls on the proper way to setup the compiler, all the problems I had mentioned in my prior post regarding segment faults disappeared. Those errors, were in fact, due solely to my having turned on the -unsafe optimization prior to having made certain there were no undefined identifiers loose at the top level. Chicken's compiler is quite fast; the benchmark code compiles nearly instantly on my box, even with every optimization I could turn on employed.

One of the first things you might notice about the first graph is that it appears some what jagged. This is the version of the graph, even after I manually removed obvious outliers; i.e, those data points where the execution time actually went down with increased complexity. I did not have to make such modifications to any of the other three implementations, which were, by and large, all monotonically increasing in execution time. My speculation is that Chicken's GC is collecting garbage in larger chunks than the others, because when the execution times suddenly jumped in places, I found that it did not always happen for all functions, and no function was immune from the anomaly. I had the choice of showing all the data, which would have appeared quite erratic, or doing my best at preserving the relative ranking among functions at each point retained, and presenting what I did, which amounts to a manual smoothing filter applied to the actual data. Consequently, there are somewhat fewer actual data points on the chicken graphs.

The other thing to notice about the Chicken graphs, is that they are fairly linear through out the set of graphs. Due to the design choices made by Chickens athors involving memory allocation, I was not able to test beyond lists of length one million. This was confirmed to be legitimate by Felix. Therefore, Chicken was never stressed to the same degree as MzScheme and Petite Chez Scheme. Tests on DrScheme were likewise terminated at lists of one million. One look at MzScheme's entire data set graph will give you a good idea of the other end of the spectrum regarding design choices, when an implementation is stressed with very little available memory left. Eugene's function is quite notable in its performance with the Chicken compiler. It starts off beating the other two functions quite soundly, but then ends up being the slowest when the lists grew to enormous complexity. In fact, I just noticed that I missed another place where Eugene's function beats the gold standard; on the other graphs I tried to place an annotation whenever this occurred. It is also notable how well Sacundim's function does with the very complex lists when compiled with Chicken. In places throughout the range of complexities Sacundim's function is seen to do better than my own function, and although the precision is poor at the end, you can just make out that Sacundim's function beats mine at the final data point. If you take a look at the graphs for all Scheme implementations, you'll see that flatten-Sacundim is more typically running slightly slower than, but nearly parrallel with flatten-set-cdr!

Turning my attention to the DrScheme graphs, you'll notice that here too I terminated the graph at lists of length one-million. I didn't actually see DrScheme crash from heap exhaustion on this set of graphs, but under a previous version of DrScheme, circa v369.100, it did. For safety sake, and due to the increasing run times, I never took it out past one million on the graphs I'm presenting today.

Looking at the overall all graph for DrScheme, you immediately notice its smooth increasing slope. This is most certainly not a result of the linear functions being tested, but rather to DrScheme taking an increasingly longer time to process the memory requirements of these functions. As DrScheme is using MzScheme as its underlying Scheme engine, you only need look at MzSchemes overall graph to see where DrScheme was headed if I had opted to continue. You should also take note that flatten-Sacundim in particular, but also flatten-Eugene, appear to be doing rather poorly in the later part of the overall graph, but this is atypical of both functions performance over the whole set of DrScheme graphs. As you see, I have made a couple of notations where flatten-Eugene actually does better than the gold standard. Another thing to note is that there is a distinct cross over point between flatten-set-cdr! and flatten-Eugene on the overall graph. This is a recurring theme in the graphs for all implementations. Flatten-set-cdr!, for what ever reason, seems to be less effected by the underlying implementations poor response to lists of enormous complexity than the other functions, except in the case of the Chicken compiler where flatten-Sacundim puts in its best performance.

Although, I've mentioned it on several occasions already, as we turn our attention to the overall graph for MzScheme, its quite dramatic. To place the entire data set on the same graph, you have to accommodate for the seemingly exponential rise in run times seen in the last few data points. It is amazing that MzScheme didn't crash by looking at the overall graph. I brought this to the attention of Mathew Flatt, who is the go to guy for PLT software, and he indicated that their was a change made to how they handle very large objects that coincides with the time frame in which I noticed a change in behavior of my benchmark. That is, previously it had failed to make it out to lists of length two million, crashing before all functions had made it. Now it doesn't crash the system after upgrading to v370.3, but we get these extraordinary jumps in run times. Mind you, these are lists of enormous complexity, that in real world applications would rarely, if ever, be constructed. However, it is possible to do without the exponential rise in run times, as you can see by looking at Petites overall graph.

It is somewhat surprising to see the difference in ranking between flatten-Eugene on DrScheme vs. MzScheme. Flatten-set-cdr! is fairly consistently the fastest function, other than the gold standard, on the entire set of graphs for MzScheme, while under DrScheme, it only begins to out perform flatten-Eugene when the lists become very complex.

Finally, we have the Petite Chez Scheme graphs to analyze. Here, even more dramatically than with MzScheme, you see how poorly flatten-Eugene appears to be performing on the initial chart. But a quick glance through the entire set reveals, that flatten-Eugene firmly had the competition beat right up until the final run. Again, for whatever reason, flatten-set-cdr! is less effected by these enormous lists than flatten-Eugene. The other quality of the Petite graphs that you can't escape, is their very smooth linear look, save for the overall graph, which clearly shows the same nonlinear growth rate in execution times as it encounters the largest lists. However, this time, the change happens over a broader spectrum of list lengths, so that even though the overall graph looks like its going north in a hurry, it retains its smoothness. It would be fascinating to have a deeper understanding of what engineering trade-offs each implementation made that produces these wide difference in behavior when stressed with having to allocate memory close to the limit of what is available on a given computer. I suspect if I had the luxury of running this benchmark on a 64bit platform with 32gb of physical memory that things might look quite different indeed.

Take Home Message

When I started this article, I greatly under estimated the time required to publish results that were as creditable as I wanted them to be. It was a real wake up call for me to see the differences in performance of these functions, all of which are based on algorithm's that are O(n) in their complexity, as they were executed under vastly different list complexities, and Scheme implementations. The results say one thing loud and clear. If you are going to select one function over another, and performance matters, then you really need to know the platform on which it will be operating, and the types of input, to which, it will most likely be applied. There are simply too many variables, outside of the programmers design of a function, to take into account for anyone to claim their function is the best implementation of a class of function, under all conditions.

For instance, I rarely use MzScheme in my own work, because of the value added for me by working in the ever helpful and forgiving DrScheme development environment, and I would never be flattening lists of the complexity for which flatten-set-cdr! is particularly well suited. So, for me, it makes more sense to use flatten-Eugene in my library. On the other hand, if you are an Emacs wizard, and you use MzScheme directly from within the editor, then flatten-set-cdr! would likely be your best choice for performance across the board. If you are one of the many fans of Petite Chez Scheme, your going to want to use flatten-Eugene for your everyday list flattening needs, but if you had a particular application in which you anticipated encountering lists of enormous size, then you might consider flatten-set-cdr! for its robust response to the larger lists. Flatten-Sacundim makes a good showing in the compiled environment of Chicken, so on that platform you would have even more choices to pick from. And then you might be a person for whom style is the most important thing for you in Scheme. For those, you cannot escape the elegance of the flatten-Eugene function, that manages to do so well in so many likely scenarios, and has sole claim to the ability to beat the gold standard, a function that can only be used in special cases.

I am also quite aware of the limited scope, within which, I have been able to run this benchmark. There are dozens of other Scheme implementations not represented here, either due to my inexperience with them, my inability to get them to compile on my box, or because it was going to be a far greater task to make a single source file portable enough to run my benchmark on them. The other shortcoming of these results, is that they all came from a single machine using a single operating system. I had hoped to repeat all the runs on my Windows XP box, which also has two (2) 3gHz Xeon processors, and 4gb's of memory, but I simply couldn't afford the time. You could also make a the valid criticism that I stuck with a single form of list-segment throughout the tests I'm reporting in this article. The truth is, I had very much wanted to publish results for varying list structures, but again, I felt obligated to release these results sooner rather than later, because of the kind contribution of my readers. I have made the Scheme benchmark source available to the public at this link on my web site, for those who might want to run the test on their own platform. It is not published on the web site itself, so you'll need to use the link provided here on my blog. If you do download the source, please pay special attention to the notes I have made throughout the code, as this benchmark code is intended only for those who will take on the responsibility for what it might do to their system. In preparing this article I discovered the limits of the various Scheme implementations by encountering several crashes along the way. None of these crashes effected my Mac Pro, or had any lingering effects on the crashed Scheme systems. However, you may not be so lucky.

As always, it was my pleasure to bring this article to you. Please leave a comment as to your take on the article. I'm always open to criticism, and accolades alike.

Enjoy!

--kyle

Sunday, June 03, 2007

A Better Flatten

A Better Flatten Algorithm in Scheme

After a little nudging from my friend Robby Findler to clean up my algorithmic act, I hunkered down with DrScheme to come up with the best list flattening function that I could dream up. For the last few days I've been doing some serious benchmarking between various functions that all do the same job, they decompose a list. It turns out that their are a cluster of four or five functions that all operate in O(n) time, but they differ by small factors in their actual run times. It also turns out that the type of list being flattened can make an otherwise excellent algorithm look very bad. One benchmark in particular proved to spoil a very popular algorithm, that builds the list back to front, and then applies reverse! on the result. I simply handed the algorithm the answer to begin with, and it fell behind other algorithms which had previously never made it into the top five. That is, I presented the function with a completely flat list as the input.

No destructive algorithms were considered, but mutation during construction of the newly produced flattened list was most definitely on the table. The fastest algorithm was a version of a function that normally required reversal to generate the list in the order visited in the input list. There are times when the order would be of no importance to the application, so I left it in the pack as the gold standard to beat.

What I came up with is an algorithm that needs no reversal of its result, and is faster than all but the one algorithm that doesn't reverse its list, and the difference between the two is very small. The function is quite robust in handling differently structured lists; never leaving its top ranking regardless of what list I through at it.

However, I still wasn't satisfied that I knew enough about my function to call the race. So I grabbed a Scheme to C compiler and ran the benchmarks all over again. On small lists, with lengths less than 100,000 (which means there were actually many times that number of elements, since `length' only measures the cdr spine of a list), the results of compiling were about what I had been told. I saw something like an order of magnitude of speed boost, depending on the function. There were some ranking changes within the slower algorithms, and to my surprise, some segment faults on some of these functions. I was hoping that I could get beyond lists of length 2,000,000, which is where, even with 4gb of memory, I hit a wall with DrScheme. However, to my surprise, the compiled code wasn't able to go beyond 1,000,000 before it faulted because of an out of memory allocation error that crashed the entire application. Further, as the length of the lists increased, the gap between the compiled codes performance and that of DrScheme shrank, depending on the algorithm, to somewhere between two to four times faster than the byte code of DrScheme.

It was quite a lesson in just how well DrScheme has been engineered. I saw more program failures over the course of one day than I've seen in my entire experience with DrScheme. I should divulge that this was the first time I had used the compiler, so in the right hands things may have worked out quite nicely.

Update: 2007-06-26 07:37am EDT.

So the record is clear, all the problems I encountered with the Chicken compiler were due to my own lack of experience with this fine piece of software. The segment faults turned out to be uncaught unbound identifiers at top level, which were not reported by the compiler, because I had, from my lack of experience with Chickens compiler, turned on the option -unsafe, and by doing so, it gladly accepted unbound identifiers, because in this mode the burden of correctness lays squarely at the feet of the programmer. And I was foolish enough to run my code for the first time with this option selected. I later contacted Felix at Chicken, who was enormously helpful in getting me squared away on all my concerns, including the ability to use `eval' in a compiled program to allow the interactive specification of the list structure to be tested. It turns out that my last line in the above paragraph was correct. In the right hands, Chicken is a very fast compiler that produces excellent run times. Please see my follow up post for the results of Chickens benchmark on four different functions, where you will see that, unlike most other Scheme implementations, Chicken produced code that remained linear throughout its operating range. I regret having made any comments before talking with the experts at Chicken, who were quite gracious and helpful in getting me on the right track.

If your interested in the function I wrote, visit schemecookbook.org/Cookbook/ListFlatten where I discuss more details. I would be particularly interested in anyone that believes there is a faster algorithm for non-destructively flattening a list. Leave a comment with your algorithm, and I'll post it, even if it turns out that its just a worthy contender.

For those of you who don't want to visit the Cookbook here is the code

(define (flatten x:xs)
  (let* ([result (cons () ())][last-elt result])
    (define (f x:xs)
      (cond
        [(null? x:xs) result]
        [(pair? (car x:xs)) (f (car x:xs)) (f (cdr x:xs))]
        [else (set-cdr! last-elt (cons (car x:xs) ()))
              (set! last-elt (cdr last-elt))
              (f (cdr x:xs))]))
    (f x:xs)
    (cdr result)))

Note: An astute reader has correctly pointed out that the nil's in this code are not quoted. DrScheme employs an extension to its reader that allows () to be evaluated as '(), saving the programmer from placing all those tic marks in the code, when it is obvious that they should be quoted. As the reader points out, this is not standard R5RS Scheme. And, indeed I had to make a glogal replace on all my nils to compile it. DrScheme employs many reader extensions that are not strictly R5RS Scheme, as do many other implementations. However, for the purest, and to help out when trying to implement portable Scheme code, DrScheme retains a language level which only accepts strict R5RS Scheme. I'm more egalitarian in my approach to implementations of Scheme. So when a better method of writing Scheme is offered, I usually adopt it, especially if it will save me keystrokes, and clean up the appearance of the code at the same time. If you are not using DrScheme, you may likely need to change the code above by adding tic marks in front of each nil. C'est la vie.

Please do leave a comment regarding the function. I'd really enjoy hearing about your own favorite version of this function. I've built up quite a collection on the way to designing this one, and there are some subtle design choices to make. It would be great to see how other people approached the problem.

Enjoy!

--kyle

Wednesday, May 09, 2007

DivaScheme Being Played by the Master

Danny Yoo on Keyboards


In the last post I was remiss in not mentioning a DrScheme Keybinding alternative that I have been religously using since it was first available. A fantastic programmer by the name of Daniel Yoo is in charge of maintaining DivaScheme and of course was instrumental in its development. I've included a YouTube embeded video of Danny at the keyboard using DivaScheme. It's quite amazing what it can do in the hands of a master. I hope you enjoy.

DivaScheme


You can get DivaScheme for free. If you like simple, un-chorded command keys as much as I do, and you program in Scheme, this is it.


Enjoy!

--kyle

Tuesday, May 08, 2007

Keybinding in DrScheme Explained

Keybinding 101 in DrScheme

Ever since I can remember during my days with DrScheme, it has always annoyed me that I couldn't comment out a block of code with an easy to use keyboard shortcut. The default short cut for the comment-out command is either `ESC;c:semicolon' or `m:c:semicolon'. Now see here we go, I have to immediately explain this little language for expressing keystrokes, or you won't get a thing out of what I'm trying to convey. The truth is that I only last week finally put all the pieces together to assign a set of easily accessible keys combinations to both the comment-out and the uncomment commands, which in scheme simply prepends a semicolon at the very first character of a line, and removes it respectively. These are great tools when you are hacking up a program and you run into a bug, but your not quite sure what section of code is responsible for the bug. You just comment out pieces of your source in a logical progression until you've isolated the little pest.

Let me say first how appreciative I am of the help I received on this topic, both from various posts on this topic at plt-scheme@list.cs.brown.edu, and specifically a grand gentlemen who is perpetually involved with helping people who submit posts or bug reports to PLT. His name is Robby Findler, and you'll never find a more helpful man to deal with on matters relating to PLT. And he is kind of heart, not known to me to punish you for posting a bug report that turns out to be your own typographical mistake. I can vouch for this personally. Actually, I could say the same things about nearly the entire PLT crew, but it was Robby who specifically helped me out with todays topic.

The first thing you should realize about assigning a new key binding to actuate a certain command is that there are several ways to go about it. But to make the task much simpler for typical kinds of keymapping, which is what the process is called in DrScheme, the PLT bunch have provided a way directly off the `Edit' menu, under the menu item `Keybindings' a sub-menu-item entitled `Add User-defined Keybindings...'. Sounds simple enough, and indeed a file open dialog box appears straight away ready to accept your User-defined Keybinding file. The catch is, it doesn't take you to a directory filled with example keybinding files that you could use as a template in making your own file. The truth is the description of the structure of this file is only been recently better documented in the manuals, and in my opinion, the documentation still leaves the uninitiated pretty much clueless on what sort of file they should be handing to DrScheme as a valid keybindings file. I intend to show you how that file should be written, and document where you can read more about the topic.

First off you'll want to read section 3.3.7 Defining Custom Shortcuts, in the PLT:DrScheme Programming Environment Manual. I've reproduce it here with permission, for your convenience, since it's such a short piece.


3.3.7 Defining Custom Shortcuts

The Add User-defined Keybindings... menu item in the Keybindings sub-menu of Edit selects a file containing Scheme definitions of keybindings. The file must contain a single module that uses a special keybindings language, (lib "keybinding-lang.ss" "framework"). For example, a file named mykeys.ss for keybindings might contain the following code:


(module mykeys (lib "keybinding-lang.ss" "framework") ...)

The keybindings language includes all of MzScheme, (lib "mred.ss" "mred"), (lib "class.ss"), and one addition, a keybinding form:


(keybinding keybinding-string-expr keybinding-proc-expr)

The keybinding-string-expr must produce a suitable first argument for map-function in keymap%, and the keybinding-proc-expr must produce a suitable second argument for add-function in keymap%.


Also the require statement


(require (lib "tool-lib.ss" "drscheme"))

adds all of the names defined in the tools manual to your keybindings module, in order to help define drscheme-specific keybindings.



Putting it all together it means our keybinding file should come out looking something like this, for a single instance of key remapping:


(module mykeys (lib "keybinding-lang.ss" "framework") (require (lib "tool-lib.ss" "drscheme")) (keybinding keybinding-string-expr keybinding-proc-expr))

Now all we have to do is come up with two expressions, the keybinding-string-expr and the keybinding-proc-expr. They've even provided hot links to the functions whose arguments these two expression become to help us out. These hot links are live in this post as well, so feel free to check out the documentation available for both functions.

In the case of the first keybinding-string-expr the documentation has become quite thorough. It describes how you build the string that defines the keystroke sequence that you wish to use to activate your function. I'll review this with you in just a moment. In the case of the second keybinding-proc-expr it is not clear at all what you should be using for a valid function name, nor where one would find them. As it was explained to me by Robby Findler, the scope of the available functions includes simply everything PLT has to offer, including functions that can be found in PlaneT, and even my own libraries. That's good to know, but I remain fuzzy on the precise protocol for calling functions from different sources. What I intend to do in this post is make available to you a method of determining the vast majority of editor functions available in standard DrScheme. If you have a desire to make a hot key for your favorite PlaneT package function I would refer you to the good people on the PLT mailing list, who should be able to come up with an answer for a specific question on mapping a specific function.

Now to get back to how you go about defining the keystrokes for your new keybinding-string-expr. The first thing to know is the terminating character, of a possibly chorded key combination, can have more than one keybinding. The rules for precedence over which keybinding actually gets invoked are pretty simple, but very specific. Generally speaking, the more modifier keys used in a key combination, the higher its precedence. In the event that two key combinations enumerate the same number of modifiers, the string that prohibits the use of the most modifier keys while typing the other required keys in the sequence, has the higher precedence. I'll have more to say about this later when we get to some specific examples.

The actual string that makes up the keybinding-string-expr is formated as a semicolon delimited sequence of state strings. Each of these state strings indicates the presence of a either a modifier key being pressed or not pressed, or a the state of a mouse button, a double or triple click, function keys, numeric keypad keys or a regular character key. Certain characters are special. The colon indicates that the previous character in the string is to be interpreted as a modifier key. And the semicolon delimits sequences of states, such that you can represent first one key being pressed and then subsequently another key being pressed. Since they are special, and since states like the status of a mouse button do not have standard character representations, PLT has come up with a long list of special names that you can use to represent these states. For a complete list see the documentation for the map-function. I'll just give you enough to get you started. The colon key is represented as the string "colon" and the semicolon character is represented by the string "semicolon", not surprisingly. Another special character is tilde `~' key. When it is prefixed to a modifier key, it reverses the meaning, such that it only matches states in which the modifier key is not pressed. Since the modifier keys are so commonly used, I've reproduced their representative strings below for you convenience.

The modifier identifiers are:
  • ``s:'' -- All platforms: Shift
  • ``c:'' -- All platforms: Control
  • ``a:'' -- Mac OS X: Option
  • ``m:'' -- Windows: Alt; X: Meta
  • ``d:'' -- Mac OS X: Command
  • ``?:'' -- All platforms: allow match to character produced by opposite use of Shift and/or AltGr/Option, when available; see get-other-shift-key-code in key-event%

By the way, that last modifier matching string "?:", produces two other precedence classes of state strings, both of which rank below everything else. The higher of the two precedence classes takes effect when you simply use the "?:" match sequence on either the Shift or the AltGr(Windows)/Option(Mac) keys, and the lowest takes effect when you use it on both. But remember, you'll likely be trying to achieve the highest precedence you can so that you'll be certain to override any other keybinding that may be in effect for your chosen hot key, so it's not likely that you'll be worrying about these types of match sequences very often.

I think about now is a good time to review some examples taken shamelessly from the manual.

Examples:

  • "space" -- matches whenever the space bar is pressed, regardless of the state of modifiers keys.
  • "~c:space" -- matches whenever the space bar is pressed and the Control key is not pressed.
  • "a" -- matches whenever ``a'' is typed, regardless of the state of modifiers keys (other than Shift).
  • ":a" -- matches only when ``a'' is typed with no modifier keys pressed.
  • "~c:a" -- matches whenever ``a'' is typed and neither the Shift key nor the Control key is pressed.
  • ":esc;:c:c" -- matches an Escape key press (no modifiers) followed by a Control-C press (no modifiers other than Control).
  • "?:d:+" -- matches when Command is pressed with the key that produces ``+'', even if producing ``+'' normally requires pressing Shift.

There are two examples here that I think are worthy of mention beyond what is explained in the manual. The first is the ":a" sequence. You'll notice it has a leading colon, but no preceding character for the colon to interpret as a modifier key. This has a very desirable effect, in that is it matches only if no modifier keys are pressed. You'll remember that the precedence goes up with the number of modifiers that cannot be pressed for a state string to match, all else being equal. Well this is the best way to insure that your hot key to whatever key you've chosen; lets make it a bit more realistic and map it to a function key like this ":f11", will have the highest precedence possible for an un-chorded press of F11. The state string ":f11" matches only if no modifier keys are pressed and the f11 function key is pressed by itself, and since it is preceded by a colon, it trumps any other keybinding to f11 without a modifier key, except for any other keybindings that are identical, in which case, unfortunately, the winner is selected arbitrarily. The other example worthy of further mention is the ":esc;:c:c" sequence. Note it to starts off with a colon as well, so the Esc key must be pressed by itself. Then there is that semicolon. This translates to, and now you release the previous state string, and press the sequence corresponding to the following state string. In this case the following sequence again starts off with a colon (you can tell somebody was after the highest possible precedence they could get), so the following `c:' represents the control key, which must be typed in the absence of any other modifiers due to the previous colon. Finally, we get to the actual character key, which is the letter `c'. To match this sequence you have to type the Esc key by itself, release it, and then type control-c, with no other modifier keys pressed. Not the most convenient shortcut, but it shows off the versatility of what you can do with the proper encoding.

I encourage you to read the entire section on the map-function. It is very well written, and it supplies you with the names for any possible key and/or mouse combination you could possibly want. With all that we've learned now, you can finally decode those annoying hot keys for commenting out code that I was complaining about at the outset of this post. They are `ESC;c:semicolon' and `m:c:semicolon' respectively. Well that first one sure looks familiar. It requires that you press the Esc key, with any set of modifiers you'd like to throw in, then release the Esc key, and finally press control-semicolon. Not what I'd call exactly convenient. Then it gets worse with the next sequence. At the time I first started using DrScheme I didn't own a *nix box, or a Mac. And the first of the two required modifier keys in this sequence is the meta key, which has no equivalent on an XP box. So even had I wanted to learn these unwieldy chorded keystrokes, I wasn't going to be able to use that hot key sequence at all. I know now that I could have used the Alt key for the meta key, but at the time I was clueless. Now I own a Mac Pro and DrScheme gives you the option of using your option key as the meta key. However, the option key is my gateway into quick access to a variety of special characters, that I would other wise have to pull up the special-character tool to insert into a document. No, what I wanted was a very quick key combination, so that I'd actually get some use out of these shortcuts.

The official document within the Help Desk where you can find the default global keybindings for an editor is keymap:setup-global in frameworks functions. However, this doesn't nearly cover all the keybindings you'll see when you look at your Active Keybindings. To get the entire list, minus the menu shortcuts, you have to employ the use of several functions, each of which adds its own particular set of bindings to the keymap. As far as I know, this information is not provided in any one location within a particular manual. So, here you get the product of my research into reconstructing the better part of the Active Keybindings in a default DrScheme system.

(let ([keymap (new keymap:aug-keymap%)]
[drscheme:keymap
      (drscheme:rep:get-drs-bindings-keymap)])
(scheme:setup-keymap keymap)
(keymap:setup-global keymap)
(keymap:setup-search keymap)
(keymap:setup-file keymap)
(keymap:set-chained-keymaps keymap
        (list drscheme:keymap))
(let* ([table (send keymap get-map-function-table)]
      [bindings (hash-table-map table list)]
      [sym-first-list
       (sort
        bindings
        (lambda (x y) (string<=? (cadr x) (cadr y))))])
; At this point sym-first-list is a list of pairs,
; where the car is the state string and the cadr
; is the function name (in most cases.)

There are in fact commands available for all the menu functions, but to get the correct function name to call to actuate them takes some direct help from someone in the PLT group to help you, or a lot of searching through source code. As far as I know, there is no place in the manuals that gives any more information than what I've provided you. And as you can see, it's scattered about in different function calls that simply take a lot of time to research. Now many of these functions are displayed in the Active Keybindings dialog box, however, there is no way to copy them off the dialog box, so that you can make your own list and design a strategy for your custom keymapping. Hopefully, the tables below will fill this gap, and you'll be able to get to the majority of the generic editor functions provided by a basic DrScheme editor frame in Scheme mode. One very hospitable thing the PLT crew have done with the global keybindings is make it quite simple for you to override them. If you go down the list, there is only one state string that begins with a colon, and that is for the mouse-popup-menu, bound to ":rightbuttonseq". That means, if you would rather use a keybinding for something else, or swap a couple around, you can easily do this by simply placing a colon at the beginning of your own custom keybinding, which will automatically give it higher precedence, as we discussed above.

Keymap - Welcome to DrScheme, version 369.100-svn5may2007 [3m].
"\u001f"undoback-to-prev-embedded
-editor
"m:c:left"
")"balance-parensback-to-prev-embedded
-editor
"ESC;c:left"
":rightbuttonseq"mouse-popup-menuback-to-prev-embedded
-editor
"a:c:left"
"ESC;""insert-""-pairbackward-character"c:b"
"ESC;("insert-()-pairbackward-character"left"
"ESC;0"command-repeat-0backward-kill-word"m:del"
"ESC;1"command-repeat-1backward-kill-word"ESC;del"
"ESC;2"command-repeat-2backward-select"s:c:b"
"ESC;3"command-repeat-3backward-select"s:left"
"ESC;4"command-repeat-4backward-select
-word
"m:s:b"
"ESC;5"command-repeat-5backward-select
-word
"ESC;s:b"
"ESC;6"command-repeat-6backward-select
-word
"a:s:left"
"ESC;7"command-repeat-7backward-select
-word
"c:s:left"
"ESC;8"command-repeat-8backward-sexp"ESC;left"
"ESC;9"command-repeat-9backward-sexp"m:c:b"
"ESC;<"beginning-of-filebackward-sexp"ESC;c:b"
"ESC;>"end-of-filebackward-word"m:b"
"ESC;["insert-[]-pairbackward-word"ESC;b"
"ESC;a:return"do-returnbackward-word"a:left"
"ESC;b"backward-wordbackward-word"c:left"
"ESC;c"capitalize-wordbalance-parens")"
"ESC;c:="uncommentbalance-parens"]"
"ESC;c:a:return"do-returnbalance-parens"}"
"ESC;c:b"backward-sexpbeginning-of-file"m:<"
"ESC;c:down"down-into-embedded
-editor
beginning-of-file"ESC;<"
"ESC;c:f"forward-sexpbeginning-of-file"d:up"
"ESC;c:g"ring-bellbeginning-of-file"c:home"
"ESC;c:k"remove-sexpbeginning-of-line"c:a"
"ESC;c:left"back-to-prev-embedded
-editor
beginning-of-line"d:left"
"ESC;c:p"flash-backward-sexpbeginning-of-line"m:left"
"ESC;c:return"do-returnbeginning-of-line"home"
"ESC;c:right"forward-to-next
-embedded-editor
capitalize-word"m:c"
"ESC;c:s:a:return"do-returncapitalize-word"ESC;c"
"ESC;c:semicolon"comment-outcenter-view-on-line"c:l"
"ESC;c:space"select-forward-sexpcheck syntax"c:c;c:c"
"ESC;c:t"transpose-sexpcheck syntax"f6"
"ESC;c:u"up-sexpcollapse-newline"c:x;c:o"
"ESC;c:up"up-out-of-embedded
-editor
collapse-space"m:space"
"ESC;d"kill-wordcollapse-space"ESC;space"
"ESC;del"backward-kill-wordcommand-repeat-0"c:u"
"ESC;down"down-sexpcommand-repeat-0"m:0"
"ESC;f"forward-wordcommand-repeat-0"ESC;0"
"ESC;g"goto-linecommand-repeat-1"m:1"
"ESC;l"downcase-wordcommand-repeat-1"ESC;1"
"ESC;left"backward-sexpcommand-repeat-2"m:2"
"ESC;o"toggle-overwritecommand-repeat-2"ESC;2"
"ESC;p"goto-positioncommand-repeat-3"m:3"
"ESC;return"do-returncommand-repeat-3"ESC;3"
"ESC;right"forward-sexpcommand-repeat-4"m:4"
"ESC;s:a:return"do-returncommand-repeat-4"ESC;4"
"ESC;s:b"backward-select
-word
command-repeat-5"m:5"
"ESC;s:c:b"select-backward
-sexp
command-repeat-5"ESC;5"
"ESC;s:c:down"select-down-sexpcommand-repeat-6"m:6"
"ESC;s:c:f"select-forward-sexpcommand-repeat-6"ESC;6"
"ESC;s:c:n"flash-forward-sexpcommand-repeat-7"m:7"
"ESC;s:c:return"do-returncommand-repeat-7"ESC;7"
"ESC;s:c:u"select-up-sexpcommand-repeat-8"m:8"
"ESC;s:down"select-down-sexpcommand-repeat-8"ESC;8"
"ESC;s:f"forward-select-wordcommand-repeat-9"m:9"
"ESC;s:l"insert-lambda-templatecommand-repeat-9"ESC;9"
"ESC;s:left"select-backward
-sexp
comment-out"m:c:semicolon"
"ESC;s:return"do-returncomment-out"ESC;c:semicolon"
"ESC;s:right"select-forward-sexpcopy-clipboard"m:w"
"ESC;s:up"select-up-sexpcopy-clipboard"ESC;w"
"ESC;s:v"select-page-upcopy-clipboard"a:c"
"ESC;space"collapse-spacecopy-clipboard"d:c"
"ESC;t"transpose-wordscopy-clipboard"c:insert"
"ESC;u"upcase-wordcut-clipboard"c:w"
"ESC;up"up-sexpcut-clipboard"a:x"
"ESC;v"previous-pagecut-clipboard"d:x"
"ESC;w"copy-clipboardcut-clipboard"s:delete"
"ESC;y"paste-nextdelete-key"del"
"ESC;{"insert-{}-pairdelete-next-character"c:d"
"ESC;|"insert-||-pairdelete-previous
-character
"c:h"
"TAB"tabify-at-caretdelete-to-end-of
-line
"c:k"
"["rewrite-square-parendo-return"s:return"
"]"balance-parensdo-return"s:c:return"
"a:c"copy-clipboarddo-return"a:return"
"a:c:down"down-into-embedded
-editor
do-return"s:a:return"
"a:c:left"back-to-prev-embedded
-editor
do-return"c:a:return"
"a:c:right"forward-to-next
-embedded-editor
do-return"c:s:a:return"
"a:c:up"up-out-of-embedded
-editor
do-return"c:return"
"a:down"next-pagedo-return"d:return"
"a:left"backward-worddo-return"m:return"
"a:return"do-returndo-return"ESC;return"
"a:right"forward-worddo-return"m:s:return"
"a:s:down"select-page-downdo-return"ESC;s:return"
"a:s:left"backward-select
-word
do-return"m:s:c:return"
"a:s:right"forward-select-worddo-return"ESC;s:c:return"
"a:s:up"select-up-sexpdo-return"m:a:return"
"a:up"previous-pagedo-return"ESC;a:return"
"a:v"paste-clipboarddo-return"m:s:a:return"
"a:x"cut-clipboarddo-return"ESC;s:a:return"
"a:z"undodo-return"m:c:a:return"
"c:)"non-clever-close
-round-paren
do-return"ESC;c:a:return"
"c:+"redodo-return"m:c:s:a:return"
"c:/"undodo-return"ESC;c:s:a:return"
"c:["non-clever-open
-square-bracket
do-return"m:c:return"
"c:]"non-clever-close
-square-bracket
do-return"ESC;c:return"
"c:_"undodo-return"return"
"c:a"beginning-of-linedown-into-embedded
-editor
"m:c:down"
"c:a:return"do-returndown-into-embedded
-editor
"ESC;c:down"
"c:b"backward-characterdown-into-embedded
-editor
"a:c:down"
"c:c;c:b"remove-parens-forwarddown-sexp"m:down"
"c:c;c:c"check syntaxdown-sexp"ESC;down"
"c:c;c:g"ring-belldowncase-word"m:l"
"c:c;c:l"introduce-let-ansdowncase-word"ESC;l"
"c:c;c:o"move-sexp-outend-of-file"m:>"
"c:c;c:r"make-read-onlyend-of-file"ESC;>"
"c:d"delete-next-characterend-of-file"d:down"
"c:down"next-pageend-of-file"c:end"
"c:e"end-of-lineend-of-line"c:e"
"c:end"end-of-fileend-of-line"d:right"
"c:f"forward-characterend-of-line"m:right"
"c:f6"toggle-focus-between
-definitions-and
-interactions
end-of-line"end"
"c:g"hide-searchexecute"f5"
"c:h"delete-previous
-character
find-string-again"d:g"
"c:home"beginning-of-fileflash-backward-sexp"m:c:p"
"c:i"toggle-search-focusflash-backward-sexp"ESC;c:p"
"c:insert"copy-clipboardflash-forward-sexp"m:s:c:n"
"c:k"delete-to-end-of
-line
flash-forward-sexp"ESC;s:c:n"
"c:l"center-view-on-lineforward-character"c:f"
"c:left"backward-wordforward-character"right"
"c:n"next-lineforward-select"s:c:f"
"c:o"open-lineforward-select"s:right"
"c:p"previous-lineforward-select-word"m:s:f"
"c:pagedown"next-tabforward-select-word"ESC;s:f"
"c:pageup"prev-tabforward-select-word"a:s:right"
"c:r"move-to-search-or
-reverse-search
forward-select-word"c:s:right"
"c:return"do-returnforward-sexp"ESC;right"
"c:right"forward-wordforward-sexp"m:c:f"
"c:s"move-to-search-or
-search
forward-sexp"ESC;c:f"
"c:s:a:return"do-returnforward-to-next
-embedded-editor
"m:c:right"
"c:s:left"backward-select
-word
forward-to-next
-embedded-editor
"ESC;c:right"
"c:s:right"forward-select-wordforward-to-next
-embedded-editor
"a:c:right"
"c:s:tab"prev-tabforward-word"m:f"
"c:space"toggle-anchorforward-word"ESC;f"
"c:t"transpose-charsforward-word"a:right"
"c:tab"next-tabforward-word"c:right"
"c:u"command-repeat-0goto-line"m:g"
"c:up"previous-pagegoto-line"ESC;g"
"c:v"next-pagegoto-position"m:p"
"c:w"cut-clipboardgoto-position"ESC;p"
"c:x;("keyboard-macro-start
-record
hide-search"c:g"
"c:x;)"keyboard-macro-end
-record
insert-""-pair"m:""
"c:x;b"jump to binding occurrenceinsert-""-pair"ESC;""
"c:x;c:f"load-fileinsert-()-pair"m:("
"c:x;c:g"ring-bellinsert-()-pair"ESC;("
"c:x;c:o"collapse-newlineinsert-[]-pair"m:["
"c:x;c:s"save-fileinsert-[]-pair"ESC;["
"c:x;c:w"save-file-asinsert-lambda-template"m:s:l"
"c:x;d"jump to definition (in other file)insert-lambda-template"ESC;s:l"
"c:x;e"keyboard-macro-run
-saved
insert-{}-pair"m:{"
"c:x;n"jump to next bound occurrenceinsert-{}-pair"ESC;{"
"c:x;o"toggle-focus-between
-definitions-and
-interactions
insert-||-pair"m:|"
"c:x;u"undoinsert-||-pair"ESC;|"
"c:y"paste-clipboardintroduce-let-ans"c:c;c:l"
"c:}"non-clever-close
-curley-bracket
jump to binding occurrence"c:x;b"
"d:c"copy-clipboardjump to definition (in other file)"c:x;d"
"d:down"end-of-filejump to next bound occurrence"c:x;n"
"d:g"find-string-againkeyboard-macro-end
-record
"c:x;)"
"d:left"beginning-of-linekeyboard-macro-run
-saved
"c:x;e"
"d:return"do-returnkeyboard-macro-start
-record
"c:x;("
"d:right"end-of-linekill-word"m:d"
"d:s"save-filekill-word"ESC;d"
"d:s:left"prev-tabload-file"c:x;c:f"
"d:s:right"next-tabmake-read-only"c:c;c:r"
"d:up"beginning-of-filemouse-popup-menu":rightbuttonseq"
"d:v"paste-clipboardmove-sexp-out"c:c;c:o"
"d:x"cut-clipboardmove-to-search-or
-reverse-search
"c:r"
"d:z"undomove-to-search-or
-search
"c:s"
"del"delete-keynext-line"c:n"
"down"next-linenext-line"down"
"end"end-of-linenext-page"c:v"
"f1"search-help-desknext-page"a:down"
"f5"executenext-page"pagedown"
"f6"check syntaxnext-page"c:down"
"home"beginning-of-linenext-tab"c:tab"
"insert"toggle-overwritenext-tab"d:s:right"
"left"backward-characternext-tab"c:pagedown"
"leftbuttondouble"select-click-wordnon-clever-close
-curley-bracket
"c:}"
"leftbuttontriple"select-click-linenon-clever-close
-round-paren
"c:)"
"m:""insert-""-pairnon-clever-close
-square-bracket
"c:]"
"m:("insert-()-pairnon-clever-open
-square-bracket
"c:["
"m:0"command-repeat-0open-line"c:o"
"m:1"command-repeat-1paste-click-region"middlebutton"
"m:2"command-repeat-2paste-clipboard"c:y"
"m:3"command-repeat-3paste-clipboard"a:v"
"m:4"command-repeat-4paste-clipboard"d:v"
"m:5"command-repeat-5paste-clipboard"s:insert"
"m:6"command-repeat-6paste-next"m:y"
"m:7"command-repeat-7paste-next"ESC;y"
"m:8"command-repeat-8prev-tab"c:s:tab"
"m:9"command-repeat-9prev-tab"d:s:left"
"m:<"beginning-of-fileprev-tab"c:pageup"
"m:>"end-of-fileprevious-line"c:p"
"m:["insert-[]-pairprevious-line"up"
"m:a:return"do-returnprevious-page"m:v"
"m:b"backward-wordprevious-page"ESC;v"
"m:c"capitalize-wordprevious-page"a:up"
"m:c:="uncommentprevious-page"pageup"
"m:c:a:return"do-returnprevious-page"c:up"
"m:c:b"backward-sexpredo"c:+"
"m:c:down"down-into-embedded
-editor
remove-parens-forward"c:c;c:b"
"m:c:f"forward-sexpremove-sexp"m:c:k"
"m:c:g"ring-bellremove-sexp"ESC;c:k"
"m:c:k"remove-sexprewrite-square-paren"["
"m:c:left"back-to-prev-embedded
-editor
ring-bell"m:c:g"
"m:c:p"flash-backward-sexpring-bell"ESC;c:g"
"m:c:return"do-returnring-bell"c:x;c:g"
"m:c:right"forward-to-next
-embedded-editor
ring-bell"c:c;c:g"
"m:c:s:a:return"do-returnsave-file"c:x;c:s"
"m:c:semicolon"comment-outsave-file"d:s"
"m:c:space"select-forward-sexpsave-file-as"c:x;c:w"
"m:c:t"transpose-sexpsearch-help-desk"f1"
"m:c:u"up-sexpselect-backward
-sexp
"m:s:c:b"
"m:c:up"up-out-of-embedded
-editor
select-backward
-sexp
"ESC;s:left"
"m:d"kill-wordselect-backward
-sexp
"ESC;s:c:b"
"m:del"backward-kill-wordselect-click-line"leftbuttontriple"
"m:down"down-sexpselect-click-word"leftbuttondouble"
"m:f"forward-wordselect-down"s:c:n"
"m:g"goto-lineselect-down"s:down"
"m:l"downcase-wordselect-down-sexp"m:s:down"
"m:left"beginning-of-lineselect-down-sexp"ESC;s:down"
"m:o"toggle-overwriteselect-down-sexp"m:s:c:down"
"m:p"goto-positionselect-down-sexp"ESC;s:c:down"
"m:return"do-returnselect-forward-sexp"ESC;s:right"
"m:right"end-of-lineselect-forward-sexp"m:s:c:f"
"m:s:a:return"do-returnselect-forward-sexp"ESC;s:c:f"
"m:s:b"backward-select
-word
select-forward-sexp"m:c:space"
"m:s:c:b"select-backward
-sexp
select-forward-sexp"ESC;c:space"
"m:s:c:down"select-down-sexpselect-page-down"s:c:v"
"m:s:c:f"select-forward-sexpselect-page-down"a:s:down"
"m:s:c:n"flash-forward-sexpselect-page-down"s:pagedown"
"m:s:c:return"do-returnselect-page-down"s:c:down"
"m:s:c:u"select-up-sexpselect-page-up"m:s:v"
"m:s:down"select-down-sexpselect-page-up"ESC;s:v"
"m:s:f"forward-select-wordselect-page-up"s:a:up"
"m:s:l"insert-lambda-templateselect-page-up"s:pageup"
"m:s:left"select-to-beginning
-of-line
select-page-up"s:c:up"
"m:s:return"do-returnselect-to-beginning
-of-file
"s:c:home"
"m:s:right"select-to-end-of
-line
select-to-beginning
-of-file
"s:d:up"
"m:s:up"select-up-sexpselect-to-beginning
-of-line
"m:s:left"
"m:s:v"select-page-upselect-to-beginning
-of-line
"s:home"
"m:space"collapse-spaceselect-to-beginning
-of-line
"s:c:a"
"m:t"transpose-wordsselect-to-end-of
-file
"s:c:end"
"m:u"upcase-wordselect-to-end-of
-file
"s:d:down"
"m:up"up-sexpselect-to-end-of
-line
"m:s:right"
"m:v"previous-pageselect-to-end-of
-line
"s:end"
"m:w"copy-clipboardselect-to-end-of
-line
"s:c:e"
"m:y"paste-nextselect-up"s:c:p"
"m:{"insert-{}-pairselect-up"s:up"
"m:|"insert-||-pairselect-up-sexp"m:s:up"
"middlebutton"paste-click-regionselect-up-sexp"ESC;s:up"
"pagedown"next-pageselect-up-sexp"a:s:up"
"pageup"previous-pageselect-up-sexp"m:s:c:u"
"return"do-returnselect-up-sexp"ESC;s:c:u"
"right"forward-charactertabify-at-caret"TAB"
"s:a:return"do-returntoggle-anchor"c:space"
"s:a:up"select-page-uptoggle-focus-between
-definitions-and
-interactions
"c:x;o"
"s:c:a"select-to-beginning
-of-line
toggle-focus-between
-definitions-and
-interactions
"c:f6"
"s:c:b"backward-selecttoggle-overwrite"m:o"
"s:c:down"select-page-downtoggle-overwrite"ESC;o"
"s:c:e"select-to-end-of
-line
toggle-overwrite"insert"
"s:c:end"select-to-end-of
-file
toggle-search-focus"c:i"
"s:c:f"forward-selecttranspose-chars"c:t"
"s:c:home"select-to-beginning
-of-file
transpose-sexp"m:c:t"
"s:c:n"select-downtranspose-sexp"ESC;c:t"
"s:c:p"select-uptranspose-words"m:t"
"s:c:return"do-returntranspose-words"ESC;t"
"s:c:up"select-page-upuncomment"m:c:="
"s:c:v"select-page-downuncomment"ESC;c:="
"s:d:down"select-to-end-of
-file
undo"c:_"
"s:d:up"select-to-beginning
-of-file
undo"c:/"
"s:delete"cut-clipboardundo"\u001f"
"s:down"select-downundo"a:z"
"s:end"select-to-end-of
-line
undo"d:z"
"s:home"select-to-beginning
-of-line
undo"c:x;u"
"s:insert"paste-clipboardup-out-of-embedded
-editor
"m:c:up"
"s:left"backward-selectup-out-of-embedded
-editor
"ESC;c:up"
"s:pagedown"select-page-downup-out-of-embedded
-editor
"a:c:up"
"s:pageup"select-page-upup-sexp"m:up"
"s:return"do-returnup-sexp"ESC;up"
"s:right"forward-selectup-sexp"m:c:u"
"s:up"select-upup-sexp"ESC;c:u"
"up"previous-lineupcase-word"m:u"
"}"balance-parensupcase-word"ESC;u"

The following tables are meant to help you in making decisions about what shortcuts you might want to create. I've arranged them first by platform specificity and followed up with tables of easy sequences to type and then the akward sequences, either because they take your hand off the home row, or they involve more than one modifier key and finally those that involve a sequence of keystrokes. You'll find that some sequences will inevitably be in more than one table, as they qualify under several catagories. If your like me you'll find it ineresting what choices were made to accomadate such a diverse audience as are the consumers of PLT software.


Unicode Character - Control - Unit Separator: its control effect is to make following text underlined.
"\u001f"undo

Platform Neutrual Keyboard Commands: avaialable on all platforms.
"ESC;c:="uncomment
"ESC;c:b"backward-sexp
"ESC;c:down"down-into-embedded-editor
"ESC;c:f"forward-sexp
"ESC;c:g"ring-bell
"ESC;c:k"remove-sexp
"ESC;c:left"back-to-prev-embedded-editor
"ESC;c:p"flash-backward-sexp
"ESC;c:return"do-return
"ESC;c:right"forward-to-next-embedded-editor
"ESC;c:semicolon"comment-out
"ESC;c:space"select-forward-sexp
"ESC;c:t"transpose-sexp
"ESC;c:u"up-sexp
"ESC;c:up"up-out-of-embedded-editor
"c:)"non-clever-close-round-paren
"c:+"redo
"c:/"undo
"c:["non-clever-open-square-bracket
"c:]"non-clever-close-square-bracket
"c:_"undo
"c:a"beginning-of-line
"c:b"backward-character
"c:d"delete-next-character
"c:down"next-page
"c:e"end-of-line
"c:end"end-of-file
"c:f"forward-character
"c:f6"toggle-focus-between-definitions-and-interactions
"c:g"hide-search
"c:h"delete-previous-character
"c:home"beginning-of-file
"c:i"toggle-search-focus
"c:insert"copy-clipboard
"c:k"delete-to-end-of-line
"c:l"center-view-on-line
"c:left"backward-word
"c:n"next-line
"c:o"open-line
"c:p"previous-line
"c:pagedown"next-tab
"c:pageup"prev-tab
"c:r"move-to-search-or-reverse-search
"c:return"do-return
"c:right"forward-word
"c:s"move-to-search-or-search
"c:space"toggle-anchor
"c:t"transpose-chars
"c:tab"next-tab
"c:u"command-repeat-0
"c:up"previous-page
"c:v"next-page
"c:w"cut-clipboard
"c:x;("keyboard-macro-start-record
"c:x;)"keyboard-macro-end-record
"c:x;b"jump to binding occurrence
"c:x;d"jump to definition (in other file)
"c:x;e"keyboard-macro-run-saved
"c:x;n"jump to next bound occurrence
"c:x;o"toggle-focus-between-definitions-and-interactions
"c:x;u"undo
"c:y"paste-clipboard
"c:}"non-clever-close-curley-bracket

Platform Neutral Mouse Shortcuts available on any platform with a mouse, but note `paste-click-region' requires a three-button mouse.
":rightbuttonseq"mouse-popup-menu
"leftbuttondouble"select-click-word
"leftbuttontriple"select-click-line
"middlebutton"paste-click-region

Mac Specific Shortcuts: using the `option' key modifier - from my experience on a Mac Pro running OS X Server v10.4.9, thankfully the a:c, a:v, a:x and a:z shortcuts aren't active, and the option key's function to provide an extended character set to your keyboard takes precedence. It is interesting to note the sequences involving both the meta and option key; as far as I know these are impossible combinations on any keyboard of which I'm familiar. Also, there seems to be an effort to capture all possible bindings of the return key, perhaps to prevent anyone from binding any modifier enhanced sequence to the return key.
"ESC;a:return"do-return
"ESC;c:a:return"do-return
"ESC;c:s:a:return"do-return
"ESC;s:a:return"do-return
"a:c"copy-clipboard
"a:c:down"down-into-embedded-editor
"a:c:left"back-to-prev-embedded-editor
"a:c:right"forward-to-next-embedded-editor
"a:c:up"up-out-of-embedded-editor
"a:down"next-page
"a:left"backward-word
"a:return"do-return
"a:right"forward-word
"a:s:down"select-page-down
"a:s:left"backward-select-word
"a:s:right"forward-select-word
"a:s:up"select-up-sexp
"a:up"previous-page
"a:v"paste-clipboard
"a:x"cut-clipboard
"a:z"undo
"c:a:return"do-return
"c:s:a:return"do-return
"m:a:return"do-return
"m:c:a:return"do-return
"m:c:s:a:return"do-return
"m:s:a:return"do-return
"s:a:return"do-return
"s:a:up"select-page-up

Mac Specific Shortcuts: using the `command' modifier
"d:c"copy-clipboard
"d:down"end-of-file
"d:g"find-string-again
"d:left"beginning-of-line
"d:return"do-return
"d:right"end-of-line
"d:s"save-file
"d:s:left"prev-tab
"d:s:right"next-tab
"d:up"beginning-of-file
"d:v"paste-clipboard
"d:x"cut-clipboard
"d:z"undo
"s:d:down"select-to-end-of-file
"s:d:up"select-to-beginning-of-file

*nix and Windows Specific Shortcuts: using the `meta' key modifier on *nix or `Alt' key modifier on Windows - also available on OS X by giving up the function of your option key.
"m:""insert-""-pair
"m:("insert-()-pair
"m:0"command-repeat-0
"m:1"command-repeat-1
"m:2"command-repeat-2
"m:3"command-repeat-3
"m:4"command-repeat-4
"m:5"command-repeat-5
"m:6"command-repeat-6
"m:7"command-repeat-7
"m:8"command-repeat-8
"m:9"command-repeat-9
"m:<"beginning-of-file
"m:>"end-of-file
"m:["insert-[]-pair
"m:a:return"do-return
"m:b"backward-word
"m:c"capitalize-word
"m:c:="uncomment
"m:c:a:return"do-return
"m:c:b"backward-sexp
"m:c:down"down-into-embedded-editor
"m:c:f"forward-sexp
"m:c:g"ring-bell
"m:c:k"remove-sexp
"m:c:left"back-to-prev-embedded-editor
"m:c:p"flash-backward-sexp
"m:c:return"do-return
"m:c:right"forward-to-next-embedded-editor
"m:c:s:a:return"do-return
"m:c:semicolon"comment-out
"m:c:space"select-forward-sexp
"m:c:t"transpose-sexp
"m:c:u"up-sexp
"m:c:up"up-out-of-embedded-editor
"m:d"kill-word
"m:del"backward-kill-word
"m:down"down-sexp
"m:f"forward-word
"m:g"goto-line
"m:l"downcase-word
"m:left"beginning-of-line
"m:o"toggle-overwrite
"m:p"goto-position
"m:return"do-return
"m:right"end-of-line
"m:s:a:return"do-return
"m:s:b"backward-select-word
"m:s:c:b"select-backward-sexp
"m:s:c:down"select-down-sexp
"m:s:c:f"select-forward-sexp
"m:s:c:n"flash-forward-sexp
"m:s:c:return"do-return
"m:s:c:u"select-up-sexp
"m:s:down"select-down-sexp
"m:s:f"forward-select-word
"m:s:l"insert-lambda-template
"m:s:left"select-to-beginning-of-line
"m:s:return"do-return
"m:s:right"select-to-end-of-line
"m:s:up"select-up-sexp
"m:s:v"select-page-up
"m:space"collapse-space
"m:t"transpose-words
"m:u"upcase-word
"m:up"up-sexp
"m:v"previous-page
"m:w"copy-clipboard
"m:y"paste-next
"m:{"insert-{}-pair
"m:|"insert-||-pair

Easy to Type Shortcuts
")"balance-parens
"TAB"tabify-at-caret
"["rewrite-square-paren
"]"balance-parens
"a:c"copy-clipboard
"a:v"paste-clipboard
"a:x"cut-clipboard
"a:z"undo
"c:)"non-clever-close-round-paren
"c:+"redo
"c:/"undo
"c:["non-clever-open-square-bracket
"c:]"non-clever-close-square-bracket
"c:_"undo
"c:a"beginning-of-line
"c:b"backward-character
"c:d"delete-next-character
"c:e"end-of-line
"c:f"forward-character
"c:f6"toggle-focus-between-definitions-and-interactions
"c:g"hide-search
"c:h"delete-previous-character
"c:i"toggle-search-focus
"c:k"delete-to-end-of-line
"c:l"center-view-on-line
"c:n"next-line
"c:o"open-line
"c:p"previous-line
"c:r"move-to-search-or-reverse-search
"c:return"do-return
"c:s"move-to-search-or-search
"c:space"toggle-anchor
"c:t"transpose-chars
"c:tab"next-tab
"c:u"command-repeat-0
"c:v"next-page
"c:w"cut-clipboard
"c:y"paste-clipboard
"d:c"copy-clipboard
"d:g"find-string-again
"d:return"do-return
"d:s"save-file
"d:v"paste-clipboard
"d:x"cut-clipboard
"d:z"undo
"f1"search-help-desk
"f5"execute
"f6"check syntax
"m:""insert-""-pair
"m:("insert-()-pair
"m:0"command-repeat-0
"m:1"command-repeat-1
"m:2"command-repeat-2
"m:3"command-repeat-3
"m:4"command-repeat-4
"m:5"command-repeat-5
"m:6"command-repeat-6
"m:7"command-repeat-7
"m:8"command-repeat-8
"m:9"command-repeat-9
"m:<"beginning-of-file
"m:>"end-of-file
"m:["insert-[]-pair
"m:b"backward-word
"m:c"capitalize-word
"m:d"kill-word
"m:f"forward-word
"m:g"goto-line
"m:l"downcase-word
"m:o"toggle-overwrite
"m:p"goto-position
"m:space"collapse-space
"m:t"transpose-words
"m:u"upcase-word
"m:v"previous-page
"m:w"copy-clipboard
"m:y"paste-next
"m:{"insert-{}-pair
"m:|"insert-||-pair
"return"do-return
"}"balance-parens

Shortcuts That Take a Hand Off Home Row
":rightbuttonseq"mouse-popup-menu
"ESC;c:down"down-into-embedded-editor
"ESC;c:left"back-to-prev-embedded-editor
"ESC;c:right"forward-to-next-embedded-editor
"ESC;c:up"up-out-of-embedded-editor
"ESC;del"backward-kill-word
"ESC;down"down-sexp
"ESC;left"backward-sexp
"ESC;right"forward-sexp
"ESC;s:c:down"select-down-sexp
"ESC;s:down"select-down-sexp
"ESC;s:left"select-backward-sexp
"ESC;s:right"select-forward-sexp
"ESC;s:up"select-up-sexp
"ESC;up"up-sexp
"a:c:down"down-into-embedded-editor
"a:c:left"back-to-prev-embedded-editor
"a:c:right"forward-to-next-embedded-editor
"a:c:up"up-out-of-embedded-editor
"a:down"next-page
"a:left"backward-word
"a:right"forward-word
"a:s:down"select-page-down
"a:s:left"backward-select-word
"a:s:right"forward-select-word
"a:s:up"select-up-sexp
"a:up"previous-page
"c:down"next-page
"c:end"end-of-file
"c:home"beginning-of-file
"c:insert"copy-clipboard
"c:left"backward-word
"c:pagedown"next-tab
"c:pageup"prev-tab
"c:right"forward-word
"c:s:left"backward-select-word
"c:s:right"forward-select-word
"c:up"previous-page
"d:down"end-of-file
"d:left"beginning-of-line
"d:right"end-of-line
"d:s:left"prev-tab
"d:s:right"next-tab
"d:up"beginning-of-file
"del"delete-key
"down"next-line
"end"end-of-line
"home"beginning-of-line
"insert"toggle-overwrite
"left"backward-character
"leftbuttondouble"select-click-word
"leftbuttontriple"select-click-line
"m:c:down"down-into-embedded-editor
"m:c:left"back-to-prev-embedded-editor
"m:c:right"forward-to-next-embedded-editor
"m:c:up"up-out-of-embedded-editor
"m:del"backward-kill-word
"m:down"down-sexp
"m:left"beginning-of-line
"m:right"end-of-line
"m:s:c:down"select-down-sexp
"m:s:down"select-down-sexp
"m:s:left"select-to-beginning-of-line
"m:s:right"select-to-end-of-line
"m:s:up"select-up-sexp
"m:up"up-sexp
"middlebutton"paste-click-region
"pagedown"next-page
"pageup"previous-page
"right"forward-character
"s:a:up"select-page-up
"s:c:down"select-page-down
"s:c:end"select-to-end-of-file
"s:c:home"select-to-beginning-of-file
"s:c:up"select-page-up
"s:d:down"select-to-end-of-file
"s:d:up"select-to-beginning-of-file
"s:delete"cut-clipboard
"s:down"select-down
"s:end"select-to-end-of-line
"s:home"select-to-beginning-of-line
"s:insert"paste-clipboard
"s:left"backward-select
"s:pagedown"select-page-down
"s:pageup"select-page-up
"s:right"forward-select
"s:up"select-up
"up"previous-line

Single Chorded Shortcuts With More Than One Modifier
"a:c:down"down-into-embedded-editor
"a:c:left"back-to-prev-embedded-editor
"a:c:right"forward-to-next-embedded-editor
"a:c:up"up-out-of-embedded-editor
"a:s:down"select-page-down
"a:s:left"backward-select-word
"a:s:right"forward-select-word
"a:s:up"select-up-sexp
"c:a:return"do-return
"c:s:a:return"do-return
"c:s:left"backward-select-word
"c:s:right"forward-select-word
"c:s:tab"prev-tab
"d:s:left"prev-tab
"d:s:right"next-tab
"m:a:return"do-return
"m:c:="uncomment
"m:c:a:return"do-return
"m:c:b"backward-sexp
"m:c:down"down-into-embedded-editor
"m:c:f"forward-sexp
"m:c:g"ring-bell
"m:c:k"remove-sexp
"m:c:left"back-to-prev-embedded-editor
"m:c:p"flash-backward-sexp
"m:c:return"do-return
"m:c:right"forward-to-next-embedded-editor
"m:c:s:a:return"do-return
"m:c:semicolon"comment-out
"m:c:space"select-forward-sexp
"m:c:t"transpose-sexp
"m:c:u"up-sexp
"m:c:up"up-out-of-embedded-editor
"m:s:a:return"do-return
"m:s:b"backward-select-word
"m:s:c:b"select-backward-sexp
"m:s:c:down"select-down-sexp
"m:s:c:f"select-forward-sexp
"m:s:c:n"flash-forward-sexp
"m:s:c:return"do-return
"m:s:c:u"select-up-sexp
"m:s:down"select-down-sexp
"m:s:f"forward-select-word
"m:s:l"insert-lambda-template
"m:s:left"select-to-beginning-of-line
"m:s:return"do-return
"m:s:right"select-to-end-of-line
"m:s:up"select-up-sexp
"m:s:v"select-page-up
"s:a:return"do-return
"s:a:up"select-page-up
"s:c:a"select-to-beginning-of-line
"s:c:b"backward-select
"s:c:down"select-page-down
"s:c:e"select-to-end-of-line
"s:c:end"select-to-end-of-file
"s:c:f"forward-select
"s:c:home"select-to-beginning-of-file
"s:c:n"select-down
"s:c:p"select-up
"s:c:return"do-return
"s:c:up"select-page-up
"s:c:v"select-page-down
"s:d:down"select-to-end-of-file
"s:d:up"select-to-beginning-of-file

Shortcuts That Require a Sequence of Keys
"ESC;""insert-""-pair
"ESC;("insert-()-pair
"ESC;0"command-repeat-0
"ESC;1"command-repeat-1
"ESC;2"command-repeat-2
"ESC;3"command-repeat-3
"ESC;4"command-repeat-4
"ESC;5"command-repeat-5
"ESC;6"command-repeat-6
"ESC;7"command-repeat-7
"ESC;8"command-repeat-8
"ESC;9"command-repeat-9
"ESC;<"beginning-of-file
"ESC;>"end-of-file
"ESC;["insert-[]-pair
"ESC;a:return"do-return
"ESC;b"backward-word
"ESC;c"capitalize-word
"ESC;c:="uncomment
"ESC;c:a:return"do-return
"ESC;c:b"backward-sexp
"ESC;c:down"down-into-embedded-editor
"ESC;c:f"forward-sexp
"ESC;c:g"ring-bell
"ESC;c:k"remove-sexp
"ESC;c:left"back-to-prev-embedded-editor
"ESC;c:p"flash-backward-sexp
"ESC;c:return"do-return
"ESC;c:right"forward-to-next-embedded-editor
"ESC;c:s:a:return"do-return
"ESC;c:semicolon"comment-out
"ESC;c:space"select-forward-sexp
"ESC;c:t"transpose-sexp
"ESC;c:u"up-sexp
"ESC;c:up"up-out-of-embedded-editor
"ESC;d"kill-word
"ESC;del"backward-kill-word
"ESC;down"down-sexp
"ESC;f"forward-word
"ESC;g"goto-line
"ESC;l"downcase-word
"ESC;left"backward-sexp
"ESC;o"toggle-overwrite
"ESC;p"goto-position
"ESC;return"do-return
"ESC;right"forward-sexp
"ESC;s:a:return"do-return
"ESC;s:b"backward-select-word
"ESC;s:c:b"select-backward-sexp
"ESC;s:c:down"select-down-sexp
"ESC;s:c:f"select-forward-sexp
"ESC;s:c:n"flash-forward-sexp
"ESC;s:c:return"do-return
"ESC;s:c:u"select-up-sexp
"ESC;s:down"select-down-sexp
"ESC;s:f"forward-select-word
"ESC;s:l"insert-lambda-template
"ESC;s:left"select-backward-sexp
"ESC;s:return"do-return
"ESC;s:right"select-forward-sexp
"ESC;s:up"select-up-sexp
"ESC;s:v"select-page-up
"ESC;space"collapse-space
"ESC;t"transpose-words
"ESC;u"upcase-word
"ESC;up"up-sexp
"ESC;v"previous-page
"ESC;w"copy-clipboard
"ESC;y"paste-next
"ESC;{"insert-{}-pair
"ESC;|"insert-||-pair
"c:c;c:b"remove-parens-forward
"c:c;c:c"check syntax
"c:c;c:g"ring-bell
"c:c;c:l"introduce-let-ans
"c:c;c:o"move-sexp-out
"c:c;c:r"make-read-only
"c:x;("keyboard-macro-start-record
"c:x;)"keyboard-macro-end-record
"c:x;b"jump to binding occurrence
"c:x;c:f"load-file
"c:x;c:g"ring-bell
"c:x;c:o"collapse-newline
"c:x;c:s"save-file
"c:x;c:w"save-file-as
"c:x;d"jump to definition (in other file)
"c:x;e"keyboard-macro-run-saved
"c:x;n"jump to next bound occurrence
"c:x;o"toggle-focus-between-definitions-and-interactions
"c:x;u"undo

You should be aware that these tables were built from the output as produced on a Mac Pro; it is entirely possible that they would give somewhat different output depending on the platform you have DrScheme installed on. Use these tables as a guide, and when you want to make a binding change, double check your own Active Keybinding dialog to make certain that the keys your are binding to are either free or the ones you had decided to override. Finally, the Active Keybinding dialog will show many bindings to menu shortcuts, but the name that is used to describe it is clearly not a valid Scheme identifier, rather it is a description of the menu item's function. If you really want to bind to one of these functions, you'll need the assistance of someone from the PLT team. I had hoped to be able to programatically provide a list of these functions for you, but the code that manipulates these bindings is inside a private function within the code that defines one of the frameworks most basic interface, and there was no clear way for me to access it without hacking into DrScheme.

Now to wrap it all up, I've put an abridged version of my own keybinding module below. However, the two different forms in which you will likely be calling your target functions. The first form is when you simply write your own lambda function of two arguments, an editor<%> object and an event<%> object. You'll likely have little use for the event<%> object, as you know what triggered the call to your function, however, if you had need of the exact time that the event had taken place, you can query the event to get that information. The editor<%> object, on the other hand, is your only link to DrScheme. You can call any public method on the editor you so desire. I've given some simple examples of inserting a string-snip<%> object. But, truely, your imagination is the only limit on what you can do with your custom keybinding and a live editor at your command.

The second form is the method you need to use to execute any of the named functions from the editor's keymap. You send the editor's keymap the call-function method with the name of the function as a string argument. These are the functions listed in the tables. I encourage you to read the documentation regarding the editor<%> class. You're bound to come up with some inovative ways of doing things you never dreamed of before.

As always, it's been a pleasure bringing you this article. I hope you have learned something new. Either way, please leave a comment about your impression of the topic, how it was covered, how it could be improved or anything else you have on your mind.

(module schemekeys-keymap
(lib "keybinding-lang.ss" "framework")

; Adds DrScheme Specific functions to the
; available functions we can bind to.
(require (lib "tool-lib.ss" "drscheme"))

(define (sendsnip e s)
(let ([snip (make-object string-snip% s)])
  (send snip set-flags '(hard-newline))
  (send e insert snip (string-length s) 0)))

(keybinding ":d:semicolon"
(lambda (editor event)
  (preferences:show-dialog)))
(keybinding ":c:1"
(lambda (editor event)
  (sendsnip editor
            "(module <name>
            \"../schemekeys/schemekeys.ss\"")))
(keybinding ":c:5"
(lambda (editor event)
  (sendsnip editor
            "(fold (λ (x rest)
             (if (<pred>? x)
             (cons x rest) rest))
             () <list>)")))
(keybinding ":f2"
(lambda (editor event)
  (send
    (send editor get-keymap)
    call-function
    "toggle-focus-between-definitions-and-interactions"
    editor event #t)))
(keybinding ":c:8"
(lambda (editor event)
  (send
    (send editor get-keymap)
    call-function
    "keyboard-macro-start-record"
    editor event #t)))
(keybinding ":c:9"
(lambda (editor event)
  (send
    (send editor get-keymap)
    call-function
    "keyboard-macro-end-record"
    editor event #t)))
(keybinding ":c:0"
(lambda (editor event)
  (send
    (send editor get-keymap)
    call-function
    "keyboard-macro-run-saved"
    editor event #t)))
(keybinding ":d:]"
(lambda (editor event)
  (send
    (send editor get-keymap)
    call-function
    "comment-out"
    editor event #t)))
(keybinding ":d:["
(lambda (editor event)
  (send
    (send editor get-keymap)
    call-function
    "uncomment"
    editor event #t)))

Enjoy!

--kyle