Keep Working, Worker Bee!

8.26.2005

I learned today that PLT Scheme actually has two kinds of thread-local storage boxes: parameters, which everybody knows about, and thread-cells, which as far as I can tell are not well-known at all even among PLT developers. The difference is very subtle: parameters are attached to a continuation and thread, thread-cells are only attached to a thread. That makes no sense, I know, but maybe it will with a code example:


(define p (make-parameter #f))
(define t (make-thread-cell #f))
(define k #f)

(begin
(thread
(lambda ()
(parameterize ((p 'thread-one))
(thread-cell-set! t 'thread-one)
(display "In thread 1:")
(newline)
(let/cc my-k (set! k my-k))
(printf "param: ~a, tc: ~a\n" (p) (thread-cell-ref t)))))

(sleep 1)

(thread
(lambda ()
(parameterize ((p 'thread-two))
(thread-cell-set! t 'thread-two)
(display "In thread 2, throwing to a continuation created by
thread 1:")
(newline)
(k 'dontcare)))))


This prints out:

 
In thread 1:
param: thread-one, tc: thread-one
In thread 2, throwing to a continuation created by thread 1:
param: thread-one, tc: thread-two


The second half of the printout is the interesting part. It shows that a continuation stores the parameter settings in effect when it is captured and carries them to new threads; it does not, on the other hand, capture the current values of thread-cells. This makes thread-cells, despite their obscurity, the better choice for implementing a lot of things; for instance, in an OS-like program that uses continuations to represent user processes and threads to represent particular slices of computation, thread-cells are the right abstraction for holding onto the OS resources that are particular to a thread.

That example wasn't pulled out of thin air, of course. It's actually how I came to learn about thread-cells at all, in fact; the PLT web server had an odd bug that cropped up because some resources that should be thread-cells were parameters instead, the result of which was that servlets that tried to save continuation objects occasionally found that when they eventually threw to them the servlet would die abruptly.

This is now fixed, and to celebrate I released a somewhat nifty new PLaneT package that highlights the power of being able to write abstractions over web interaction patterns rather than just web pages: resume.plt.

8.19.2005

So, I've been working a lot recently revising the R5RS semantics paper for the 2005 Scheme Workshop. In doing so I've discovered a lot of interesting R5RS quirks; here's one I discovered just recently. To my knowledge this hasn't been pointed out before, and it might well be a widespread example of R5RS nonconformance among Scheme implementations.

The R5RS seems to avoid specifying how continuations interact with the top-level environment deliberately, the only discussion being: "The continuation represents an entire (default) future for the computation. If the expression is evaluated at top level, for example, then the continuation might take the result, print it on the screen, prompt for the next input, evaluate it, and so on forever" (section 6.4). However, R5RS section 5.1 says: "At the top level of a program (begin ...) is equivalent to the sequence of expressions, definitions, and syntax definitions that form the body of the begin." So because when you type in (begin E1 E2 ...)that's exactly the same thing as just typing in E1 followed by E2 and so on, whatever continuations do with the top level, they should do the same thing whether or not they're in a top-level begin form, right?

I tested every Scheme implementation I could get my hands on, and this wasn't true for any of them when it comes to continuations. Here are the expressions I used:
(define num 0)
(define k (call-with-current-continuation (lambda (x) x)))
(set! num (+ num 1))
(k (lambda (x) x))
num

and

(begin
(define num 0)
(define k (call-with-current-continuation (lambda (x) x)))
(set! num (+ num 1))
(k (lambda (x) x))
num)

Try them in your favorite Scheme interpreter's REPL and you'll probably find that running the first yields 1 and the second yields 2. I tried it in mzscheme, guile, MIT Scheme, and Bigloo (the four Scheme interpreters I've currently got installed on my work computer) and that was the result in every case.

The only difference between the two pieces of code is that one's in a top-level begin and the other isn't, so clearly the R5RS specification that the two programs be equivalent isn't being followed. What's going on here?

What's going on here is that call/cc is exposing an implementation detail, as it does with so many features. My advisor suggests that the simplest way to implement a REPL will have a single evaluation context (i.e., what gets grabbed by call/cc) for every top-level expression it evaluates, and that the code that implements top-level begin uses that same continuation for all subexpressions rather than making a new one for each, meaning that the REPL's prompt is actually a prompt in the control-delimiting sense in all cases. Of course in that case you'll get the behavior I observed.

That behavior seems fine to me; in fact, considering that every Scheme implementation I tested does it this way it's probably a better way to do it than the way the R5RS suggests.

8.11.2005

I had a pretty abbreviated day today for various reasons, but I managed to get another new feature into PLaneT -- now it's possible to use the command-line tool to download PLaneT packages without installing them, so people with only intermittent Internet access can use PLaneT more easily. I've resisted features like this in the past on the assumption that people would tend to forget about the fact that PLaneT will do everything automatically for you if you let it, but I've come around lately to the opinion that I shouldn't remove features just because they can be misused.

I also had an epiphany about how to structure web servlets to implement save points in a web application that ought to be associated with a user rather than with a session. The answer is pretty simple in retrospect - use a table that maps users to continuations, capture a new continuation just before sending off any web page and bang the table to point to that continuation (removing any old ones), and throw to that continuation whenever the user logs in - but I actually implemented this feature a much harder way for the speed-dating project without ever realizing I could get the same effect for the cost of about ten lines of code if I just used the power of first-class continuations.

The fact that this was done in the context of a continuation-based web server makes the whole thing a little more ironic, but actually it sort of makes sense: the continuation-based web-server makes you think of continuations as the same thing as URLs, so when you have a problem that involves continuation-manipulation the natural thing to think of is rephrasing it as an HTTP redirect of some sort - perhaps saving URLs as they went by and doing an HTTP redirect to the last one of those a user had seen. I scratched my head over that for a long time and realized it didn't quite work, but didn't quite understand the essence of the problem and its solution. Like I said, I actually went off and implemented the whole thing a different, awful way that was a complete beast to maintain and never really worked exactly right.

But today I found myself saying, in trying to explain the issue to someone else, that the continuation you associate with a URL is taken one step too late: it will return _after_ the web page gets shipped off, not beforehand as it should. From that perspective the answer is obvious - if the continuations the web server provides don't work out, grab your own! Scheme has no problem with that, and the fact that the continuations aren't connected to URLs is completely inconsequential. The same solution would apply to any situation where a user wants to save and resume their session, on the web or off. You've got to love the fact that Scheme gives you power tools like call/cc -- very rarely used, but indespensable when they are.

8.10.2005

I think last night's hacking got me eager to break out of my theory tower and do real programming, and Noel's email about using PLaneT over HTTP gave me the final push I needed to finish off PLaneT's HTTP support. I'd been planning that support for a long time, even to the point where I had a complete implementation strategy, but I never got the motivation to actually program until today. I still think PLaneT's original protocol is a better fit for the problem PLaneT solves than HTTP is; the original goal was and still is that the client and the server have a little conversation about all the packages that the client will need to download, then the client downloads them all at once, just like the linux package manager systems out there. Unfortunately there are enough problems implementing that on both the server and the client that the protocol doesn't do any particular good for actual PLaneT communication; its only real role was stopping people with restrictive firewalls from using the service. That's what the HTTP client fixes, and it's fixed now. Fun fun fun! And, it meant I got to play with the web server some more to do things it doesn't often do, and that meant I discovered a few more issues (mostly docs bugs, one annoying design limitation).

I think you can feel like a computer scientist at any time of the day, but you can only feel like a hacker after midnight. I was helping Mike with a PLT-server based project (another Topsl project, as it happens) and after a certain point a nasty, nondeterministic bug started cropping up and eating our results. After a long while of looking over our code, we came to the conclusion that there was at least an equal chance that the bug was in the server; I've got some experience with the PLT server so I dove into its guts hunting for the problem. Long story short, I propped open my drooping eyelids and shortly before 2:00AM I was able to confirm the bug and verify a workaround. I'm pretty pleased with myself for finding that.

Other day's computer stuff: not much interesting to report. I rewrote a section of the R5RS paper, then rewrote it again, then wrote a formal system used in that section, then threw it away and used another one that I didn't realize had already been written; then started rewriting that one. Kathy and I also made a couple stabs at one of the core systems for a new paper we're working on together that extends on a bunch of stuff we both done independently; we just started this a few days ago, though, so there's not really much to say yet.

8.09.2005

It's becoming more clear to me that there's something lurking below the surface that relates contracts, foreign function interfaces, macros, and probably subtyping and (more speculatively) component systems in general: the notion of us versus them, negotiating our differences, and statically or dynamically keeping track of who we and they are. Contracts and foreign function interfaces keep track of us and them dynamically for the purpose of blame or conversion, respectively; a macro author builds up a semantic notion of us (the macro construct) versus them (the host language) that he or she then has to write a program to translate away. Subtyping contains a totally static version of the idea where we,an expression, may disagree with them, our context, about what our type is, but we can in some circumstances amicably resolve our differences.

I haven't worked out most of those examples yet, so I don't know if the connection is anything beyond superficial, but it seems pretty compelling to me after having worked out some toy examples. I'll have to investigate further.

8.03.2005

If you're interested in the continuation-based web-site authoring systems like the PLT web server and Avi Bryant's Seaside, you may well know about UnCommon Web. Just recently, UnCommon Web's author Marco Baringer made a Quicktime movie (.torrent) wherein he showed how to build up a simple interactive site using UCW; I checked it out today since I'm always curious at how people are taking the continuations-as-web-programming-paradigm idea. It's about 20 minutes long and really worth watching. It looks like at a very high level the code is organized in roughly the same way you'd organize it using the PLT server (no surprise), but instead of having programs periodically call a send/suspend procedure, instead they periodically send objects(?) called components that appear to represent web pages a "show" message that behaves as send/suspend does. This isn't a big deal but does seem to cause the code for individual pages to look different at a micro level. I am a little hesitant about that, since I've long since decided that organizing a web site's code around the web pages it displays is not the right way to do things most of the time, but I really don't know enough about UCW to say whether it's really a problem.

Other than watching that video, I spent much of today revising the Scheme Workshop paper; I have to say thanks again to the reviewers who really honestly gave me tons of very useful feedback. I've completed a once-over pass that fixes most of their complaints; the only thing left to do now is the unpleasant task of creating a new section and doing some major surgery on another. That's complicated by the fact that the paper is sitting right on the page limit as it is, but I suppose that's always how papers go.

In other news, it seems that the Fortress team is using PLT Redex to model the dynamic semantics of "Basic Core Fortress" (see page 104 of the new language specification). Neat!

8.01.2005

Hm, I see I forgot to mention that I was on vacation for the last week. Well, I was on vacation for the last week; specifically, Molly and I went down to Atlanta to visit my parents, raft down the Chatahoochie River, watch various plays and movies, enjoy the coastal Georgia beaches (I saw a baby sea turtle climb from its nest and march down to the ocean!), and generally do things that do not at all involve programming.

I'm still catching up with my emails, but I was happy to see that our "Operational Semantics for R5RS Scheme" paper was accepted by the Scheme Workshop, and I was even more happy to see that the reviews we got were extraordinarily helpful. All three reviewers really dug into the paper and identified a lot of ways we can make the paper stronger, while at the same time giving me the warm fuzzies with their positivity.

I also turned in my final grades for the class I taught over the past five weeks. My final exam was quite a bit harder than my midterm exam, but it seems like it served its purpose pretty well in differentiating the students rather than crushing them all and making them cry. Nobody got a perfect score on this one, but there were definitely solid A's and B's and so on. After I finished grading it, I made the final calculations and got my students' raw scores, curved them (I actually did pretty well, the curve was a just uniform five points all around, and really if I wanted to be a bit more of a tough guy I could've safely omitted it) and made that my final grade. All in all, I'm feeling pretty good about my class at this point. I will see whether I actually learned anything about teaching in the fall when I have to do it all over again, more slowly and with more students.