wingolog

Good evening, internets!

I am not doing a very good job at existing both online and off. Indeed this summer word-drought correlates with real-world motion, to Paris and England and the Netherlands, and back and back and back. Tonight I'm looking out at a working week here, then a flight to LA for a wedding and work, out to Montreal for the Scheme Workshop, to North Carolina to see the folks, back to LA, then Paris and home.

pon'drous & heavy: planetary rotations

With orbits like these, it's hard to keep centered, which is where I hack and write best. Still some things have managed to come off well -- Guile progresses towards a 2.0 release, though with a couple more milestone releases than predicted. I'll write about 1.9.12 when it goes out in a few days.

The recent GNU Hackers Meeting in the Hague turned out well. There were 40 or 45 people there. The talks were good, and the side-channel conversations were also good. Videos should be up shortly

I feel like we're in a kind of renaissance of GNU as a community of hackers -- that as our virtual community coalesces into real affinity networks, GNU hackers gain a sense of the possible, and of the will to get there. We're in a fortunate position I think -- we have the means to effect a large hack, so discovering our own possibilities is that much more exciting, and empowering.

Also on the GHM note, I should say something about the Revelation Space, which hosted the meeting. Well, it would have been nice already if it had only had our needs covered, which it did, but to us the revspace was made excellent by being so low-key, trusting and comfortable that we really felt at home. This feeling had a directly positive impact on the quality of our meeting. So thanks again, revspacers, and happy hacking!

Anyway, this is just to break the ice a bit, and see if I can get back in the rhythm of writing. Happy hack to all, and to all a good hack!

Sup, tubes. Time to talk shop!

about

I should say first that I don't work for Fluendo. There it is! And indeed my longtime readers do know this, but one would not have known it from looking at my about page.

I did my best to sow confusion, noting that though the page was last updated in 2006, that the previous update had been in 2004; but such shadow-facts stuck in folks' minds. So, I have replaced that page with one much less informative.

Two points of continuity remain. One, I am (at this writing) still in Barcelona, a pleasant place on this planet. Two, I still have the good fortune that my current employment shares space with GStreamer folk: Wim and Edward from Collabora Multimedia. Sometimes people ask me about how the job with Collabora is going. Well it isn't!

the hack

Indeed, I don't write much about work, so one can be forgiven for mistaking my work, if such forgiveness were even necessary. The work hack goes well. We have always had customers, since the beginning, but now it really feels like the adoption curve is starting to tick up.

I'm sure the founders and business people are quite pleased about this. As for myself, it is a mixed blessing -- and my technical readers will understand me here. I don't work on the input side of things, so I am free to appreciate their progress, which is indeed wonderful. I work more on the side of the toolkit used to develop spatial applications, specifically on the video integration, and it is a huge challenging scaling problem (limpidity, documentation, orthogonality). The market gapes wide before us, and we race to stuff its maw with digestable API and such; and meet it, mostly, and barely. It is a race.

picture elements

Thankfully some of this work has seen the daylight recently. The novelties that prompt me to write are:

• John, talking at TED this year. I cannot tell you what a privilege it is to work with John. He is how he is in this clip: articulate, verbally and in code, and compassionate.

• My goofy self, on the UK's "Gadget Show". But fortunately, the UK keeps its "Gadget Show" to itself, denying the rest of the world the pleasure of my visage.

  The mechanics of that show were interesting. The presenter and the producer showed up one Sunday, the latter with a simple camera and tripod in tote, and four hours later they had their footage. All that trimmed down to some four minutes for the final cut. The whole thing very professional, but agreeable -- nice folks, doing their job.

Hello world!

It's true, there is some fraction of my audience that has not yet compiled Guile, and with you I commiserate. Surely you are missing out.

But with the rest of you, I commiserate also. I write this while compiling psyntax-pp.scm; surely you understand. I write from an abyss actually, a hole of pending patches, a swirl of orbs yet to orbit. Thankfully I'm in a perhaps final bootstrap stage, thus liberty for these words.

So! It's spring! It's not yet beachtime here in the BCN, though it grows ever-near, but the summer is rolling into view, in an oblique slink.

In my listenings, I've heard a number of tunes that talk about k-holes. Apparently this is something related to the drug ketamine, which apparently leads to heartbreak and punk rock, or perhaps I have the causality reversed.

I don't know about ketamine, as I've never tried it, but I am sure that the hack seems a drug as potent. I go through phases of hack and phases of organizing, and these seem mutually exclusive. If I ever seem too dangerous, submit a good bug report, I'll ignore the world for a while, until the loop is closed.

gnu hackers

So! GNU Hackers Meeting 2010, co-located with GUADEC! We're a-hacking on the 24th and 25th of July, that's the Saturday and Sunday, and potentially hacking on in the Monday and Tuesday at the Revolution Space.

The GHM is for GNU hackers. Contributors to GNU projects are most welcome to come, and potentially give talks about the projects they work on -- send us a mail (linked from the above page) so we can schedule things.

The main focus of this particular meeting will be decentralized computing, a popular topic at the last meeting. We'll have Christian Grothoff there, the maintainer of GNUnet, and a motley collection of the GNU crew.

Many (most?) of my readers are part of the GNOME project, and all of you are welcome to attend. The registration deadline is rather soon (15 June), though I imagine it might be extended a week or two ;-)

There is some slight travel assistance available, but not as much as we would like. We'll be pulling strings hither and yon, but if you know of a benefactor, human or otherwise that would be willing to sponsor GNU to the tune of $1K or so, let us know!

This weekend has been odd: imagine a mix of sushi and pastis and billiards and flowering thyme & bay and bubbling streams and woodchippers.

All that to say, I haven't been able to respond to my previous missive in a proper fashion; but I was linked to an amazing speech by Eben Moglen that everyone should read. Yes, you, Mom!

Freedom in the Cloud, by E. Moglen, 5 Feb 2010.

In it Moglen deals with this idea of center-versus-edge. In the autonomous cloud piece, I wrote that the client-server paradigm was incompatible with autonomy; Moglen makes this point much better than I could. Incidentally the point was Brian Gough's, not mine, though its expression was my own.

My previous installments on November's GNU Hackers Meeting (hither, and thither) touched some topics that were important to me, but not as important as the one I'll mention tonight.

Tonight I want to talk about autonomy and the internet. I'll approach it from a roundabout direction.

the facebook problem

Many of you probably know someone who has had their Facebook account disabled. Here are a couple, and here are some thousands more. While I'm probably not the best person to speak of this, as I don't have a Facebook account, it's quite irritating to have this happen. It's like you've been unpersoned.

Beyond the individual indignation though, what is really important (and sometimes missing) is a more universal indignation: never mind me, what gives a corporation the right to unperson anyone?

Sure, I hear you arguing that it's their services, bla bla, but the end of it is that when you use Facebook, you lose autonomy -- communication and identity are needs just like any other.

I might be going out on a limb here, but consider Article 19 of the fine UN Declaration of Human Rights:

Everyone has the right to freedom of opinion and expression; this right includes freedom to hold opinions without interference and to seek, receive and impart information and ideas through any media and regardless of frontiers.

Emphasis mine, of course. What I'm saying is that you shouldn't depend on the government or a corporation or any other entity outside your actual community to be able to actualize these natural rights.

and further: article 12

Though I don't like the wording of this one as much as the previous article, nor the gendered pronouns, check it:

No one shall be subjected to arbitrary interference with his privacy, family, home or correspondence, nor to attacks upon his honour and reputation. Everyone has the right to the protection of the law against such interference or attacks.

As an American living in Europe, it has taken me some time to appreciate the European focus on privacy. I don't think people in the States understand the issues as well as people do here. OK, so your parents/grandparents lived through fascism: so what?

On a personal level, whether you're an industry insider, someone avoiding an abusive relationship, or an Earth Liberation Front activist, privacy is terribly important. It's not an exaggeration to say that to cede control over your privacy is to cede control over your identity.

But organizations that control your data on this level usually aren't stupid enough to let you know, or make you think about it. All that is left is a dull throb of database scandals and terms-of-service changes and wiretaps.

The problem is not the existence of malicious people: the problem is that the your data is out there. All it takes is one nosy person, or one controlling governmental agency (cf. A, B), or one corporation wanting to monetize (cf. all of them).

There are simply no safeguards. There is nothing you can do if you want to be a part of the modern web to protect your privacy. Your data on servers is always available to wiretap, and subpoena if necessary. Your data is not your own.

origins

Both of these problems (unpersonage and privacy violations) stem from the fact that you rely on someone else's computer to fulfill your personal needs. RMS wrote about this in an article entitled Who does that server really serve?, and I agree with all of his points.

Stormy Peters' recent article, 10 free apps I wish were open source, illustrates many of these misunderstandings. Besides the misleading terminology, what if Gmail were AGPL-free? Would that protect users against the recent Buzz fiasco? No, because users are not in control of the software they use. Users should be able to modify the software they run; if they cannot, due to that software running on another machine, they should not run software on another machine.

I don't think Richard's article goes far enough. As I mentioned above, the problem is that your data is just "out there". Let's postulate an AGPL Gmail that also allows me to run my own Gmail software on Google's network. While this would meet the Free Software definition, it still harms me as a user, because anyone who has access to that server has access to my data.

Besides that, there is the practical difficulty, in that Facebook or Google would never allow you access to the programs that run on your data in that way.

What I'm building up to is the idea that the client-server paradigm is fundamentally incompatible with autonomy. Growing your own food is better than sharecropping, better than "web 2.0".

what shall we do, sir wingo

A fundamental problem requires a radical (adj.: to the root) solution. As is often the case, the seed of a solution has been with us for a long time: public-key cryptography.

Geeks have long enjoyed mailing each other signed and/or encrypted mails, allowing private communication over insecure networks, relying on webs of trust to ensure the identity of the sender. Asymmetric cryptography allows you to send and receive private messages over insecure channels, like the internet.

I won't belabor the point, as most of my readers have seen GPG; it is the Right Thing. But what would GPG-style interactions mean in the context of Facebook?

All of you are probably cringing at this point, imagining the complexity and security implications. But let's bask in that moment for a while, shall we: if it were the case that fellow facebooklicans sent you private messages via GPG, being able to view them sensibly over the web would imply that the Facebook server would have your private key.

Extrapolating this farther, the very set of your "friends" is a kind of private data. If this data were properly encrypted and signed against your private key, to present the standard facebook view that most people know would again require your private key.

In the end, you can't have web services that access private data. Not if you want privacy, anyway.

an autonomous facebook?

To preserve the privacy of your identity, you should never send your private key over the wire. This is well-known. But if you are to do computation on your social network, as facebook.com does, then it follows that such computation must be done local to the user's machine.

But all of facebook on your local machine? Surely you're joking, Mr. Wingo! Well, yes and no. Obviously the answer is not "let's everyone download a program from facebook and run it locally with your private key as an argument". Not quite, anyway.

One good part of the so-called "web 2.0" is that I can code foo-anarchist-commune.org's web site in Scheme and no one is any the wiser. It's easy to deploy in today's environment; deploying e.g. a new facebook experience should not cause me to have to click something to install a new binary.

So, the constraints are:

1. My key pair is my identity. My public key may be distributed, but my private key must be private.

2. Since computation needs my private key, computation must happen locally. Viewing an "autonomous facebook" implies running a program on my local machine, with access to my private key.

3. Since an "autonomous facebook" would be useless without other people, I need access to other people's information, I need a network too.

We can already draw a picture of what this looks like. Let's assume that the end-user experience is still via the web browser.

I think that my paranoid readers know where I'm going with this. My technically-minded readers will be flabbergast, perhaps, at the enormity of the problem of implementing facebook under such constraints. How does my facebook know that it's participating in a network? How does it know about my friend Leif? How does it get updates? Where is the database?

autonomous data model

Well, one thing is clear: someone needs to hold all of that data. Who to do it? In the case of my data (my photos, my messages to others, etc), I should be the one, as it makes me more autonomous. Everyone needs to seed their own data on the network.

I might choose to seed my data from multiple locations, for reliability. Beyond that, nodes might cache information that is routed through them.

One way to implement such a distributed store would be git-like, with content-based addressing and consistent hashing; or like bittorrent. It would have efficiency advantages. I thought for a while that this would be the solution, but GHM folk brought up the privacy argument, that your pattern of network access is too revealing.

So my current thought is to use GNUnet somehow. I'm not sure how this will go, but it's worth a try.

new operating system

Currently, to deploy a web application, you have to pay for servers and bandwidth, and this eventually causes your interests to diverge farther from that of your users. With an autonomous cloud, you could instead deploy web applications using the compute power and bandwidth of leaf nodes -- the power of the people using your software.

This would drastically lower the hacktivation energy for a new project. The little green sandbox above starts to approach a new kind of operating system, even -- a new program to run your programs.

Obviously, I'm thinking Guile would be a fine runtime for the sandbox, to run programs written for Guile -- in Ecmascript or Lua or Scheme or Elisp or whatever other languages people implement for Guile. The user would receive the source code, and running it would automatically compile it on their machine. The application source would also be available to modify and redistribute.

Having a sandbox for mobile code also raises the possibility of interesting mapreduce-type operations, to index the distributed data store.

Firefox could be modified with a plugin to add a new addressing mode, which would go through the HTTP server running locally to your machine. You would be browsing the "autonomous web".

Of course, since the whole thing is based on protocols, one might substitute the Guile environment for something else; or write an alternate interface to Facebook that works over a console or presents you with a native (e.g., Clutter) interface.

related work

There have been loads of people thinking these ideas; none of them is new.

My ongoing use of the term "autonomous" is a nod to anarchists, and to the autonomo.us group. Autonomo.us would be a great organizing place for work around this, but their list server is a bit moribund; somewhat ironic. Perhaps we can return life to that group, though.

GNU Social is a project to make a free-as-in-freedom social network. I think it's a great initiative, and it's probably the place to go if you want to build an alternative to Facebook right now.

GNU Social has made the decision to just get something working. This is the right thing to do, IMO; but near-term solutions should not prevent concurrent research for the long-term. In the end if making an autonomous cloud turns out to be possible, perhaps we can rebase GNU Social on top of the autonomous infrastructure.

Is there something else I should really be looking at? Let me know! I don't think one can ever do a full survey of this field -- better to just start hacking -- but I'm interested in good ideas, especially to the data storage and access problem.

plan

All of this is a bit pie-in-the-sky, but I am going to see if I can work up a proof-of-concept for the upcoming GHM in July. If you are interested in helping this project, probably the best thing to do is to code up some little demo application using GNUnet or some other store. Once you have that, drop by to see me in #guile and we'll talk.

Comments welcome!

I know your problem: you are a student, and the Google Summer of Code has started, but you haven't found a project worth doing. Or, perhaps you have submitted a proposal already, but you're not psyched about it. You really wanted to munge bytes on disk using Scheme. I totally dig it.

That is why you should make a proposal to make a library for accessing Git datastores from Guile. Great idea, right? You probably had it too!

The scope of the work would be to write the equivalent of Git's "plumbing" layer in Scheme. The first step would be to be able to git cat-file any object in the database. Then you would need to be able to insert into the database, via git-hash-object, and then to be able to update a ref with git-update-ref.

At the same time, all of this functionality should be available on the command line, via something like a gilt executable: gilt cat-file foo, for example.

The reason why this work is interesting is N-fold:

• Having a Git library will be nice. Indeed a number of software projects use Git as a database.

• Having a Git implementation that can be linked to Guile will be good too. (Guile is LGPLv3+, Git is GPLv2 only.)

• It will be interesting to see how fast a Scheme-only solution will be. Raw SHA1 calculation will probably still have to be done in C though.

• Finally it's going to be total fun! It's a good scope for an SOC project: you can implement as far as you get, and you learn skills like how to do real-world development in Scheme, producing fast code.

Interested? Time is running out. 9 April appears to be the deadline. Requirements are a proficiency with Git, and you should implement a command-line Guile program that returns the MD5 or SHA-1 hash of the file given as its argument. It's OK to copy the MD5 or SHA-1 implementation from elsewhere, but document that; I just want to know if you can actually wire up the pieces correctly, and beyond that, is your Scheme in good taste.

So, should this thing be up your alley, send me a mail, or visit #guile during the European daytime, and let's talk!

So, back in November I went to a GNU Hackers Meeting in Sweden. In December I wrote about part of what I got from it, the relationship between GNU and the FSF. That post was long enough, so I left the rest for later, and later is finally now. So before heading out for the weekend, let me get to one of the pending topics.

recent developments in guile

I, your somewhat humble author, gave a talk! I spoke about recent developments in GNU Guile, eventually discussing sneaky plans to get Guile into Emacs.

Here is my first foray into the world of <video>:

If that doesn't work for you, you can download the video from a torrent, play the ogg from a direct link, or check the archive.org page for other versions, including H.264, and even animated GIF (what?). Or download the slides, and save yourself my witticisms.

Since that talk, things have changed somewhat: Guile does have a dynamic foreign function interface, delimited continuations, eval implemented in Scheme, etc. It's unclear whether this next release will be 2.0, or the one after that; but I'm through with features.

As I begin to write this, it's still the Ides of March -- the fifteenth day of the third month of the year.

Non-native English speakers likely haven't heard the word "ides" before, even in their native language -- at least it doesn't seem to be common in Spanish or French. But anyone who went through an American high school can see the crooning finger of the seer, as he tugged at Julius' Caesar's sleeve, and hear his crow, Beware the Ides of March.

Then it's all stab stab stab, and the tyrant is dead! Well not quite that soon, but thence goeth the play. We are told that Caesar was a man of hubris, with imperial ambitions, and it was a noble group of righteous republicans that took the dirty deed into their hands, ridding Rome of an oppressor.

Told, that is, by Cicero, a brown-noser with a gilded tongue; and from whose writings most of the history of the period derives. So says Michael Parenti in his The Assassination of Julius Caesar: A People's History of Ancient Rome.

class war

Parenti places the murder of Gaius Julius Caesar within a context of a popular struggle, playing itself out as a split between different segments of the ruling class. On the one side there were the slumlords, latifundistas, and slaveowners, and on the other side there was popular struggle, in the form of slave revolts, insubmission, graffiti (!), in addition to the formal political channels (the people's tribune and consul, etc.).

Within the ruling class (slaveholders all), there was a split. On one side were the optimates, the self-described best and brightest, those that would hold on to their privileges at all cost. The optimates spoke in terms of "rule of law", but they were happily oblivious to such things when it suited them.

On the other side were the populares, a reformist tradition stretching back a couple hundred years. It was dangerous to be a populare. A number of populare leaders had been killed, by gangs of men, or poisoned, often on direct senatorial order. All of this, to protect the privileges of the elite from any retrocession, however small, even coming as it was from other members of the elite.

Caesar was a populare, and a charismatic one at that. But he wasn't killed for being charismatic; on the contrary, if he had been an optimate, he would be described to history as a man of the highest republican principle.

Caesar was more a kind of former-day Roosevelt -- though not a revolutionary, certainly a reformer, who would change government to serve the people better. Also like Roosevelt, he was viewed as a traitor to his class. Caesar was one of the last of the populare leaders to have power. He was killed, argues Parenti, mainly because of his place in this tradition of social struggle.

Then, as now, the optimates would not allow the republic to fall into the hands of the so-called "mob". (What a word for the citizenry, eh?)

Flowers for Julius Caesar, by Gauis Caecilius. CC-NC-ND.

Every year, I am told, at the Ides of March, one may find bunches of fresh flowers, laid on the spot where Caesar was killed. If I had learned this before reading the book, I wouldn't have understood, but now I choose a meaning that makes sense to me: these flowers are for the people's struggle, that the slave rebellions of the past might not be in vain.

Assalamu alaikum, internets. And what internets! My wanderings this day have been varied, though my reactions be cloudy -- perhaps due to my cold. Damn the virus.

the prophetic voice

I was listening to a speech by Imam Mahdi Bray, who is, as you might guess, an imam -- a preacher, effectively. I was impressed by the strength and righteousness in his voice -- and then I started to wonder (and wander) a bit.

I grew up Catholic, very Catholic at times, and perhaps my readers will allow me to put off saying what it is that I am now, until I figure it out myself; but that past does not explain my weakness for sermons. It's almost as if I had some secret Baptist heart.

Take Martin Luther King Jr., a prophet if we ever had one. His speeches move, an effect that comes from the sense of ringing righteous justice; but that sense only rings in the body of the listener when given with the proper delivery. King spoke with the prophetic voice, not only with content but with a diction that carries weight and truth.

Mind you, it's a practiced diction: one can learn it in a school, even. But to speak in the prophetic voice is not mere device; it allows truth to shine through in a way that "rhetoric" does not.

A prophet is freed from the constraints of the premises of her day; she does not need to spend her time refuting arguments based on those premises, but to build off of the implications of her own. In doing so she allows those premises to be examined more explicitly, and honestly.

white hippies

So I was pleased to find that in a later listening of Unwelcome Guests, I came across the lovely words of Robert Jensen.

Jensen is a white journalist living in Texas. Granted, it's Austin, the anomalous hippie district, but Texas nonetheless. And just so that I'm not the only Free Software hacker blogging about sermons, I'd like to mention one he gave in 2007: We are all prophets now: Responsibilities and risks in the prophetic voice.

I'm happy he mentioned the risks aspect, because there are many. There is a fascistic tendency in rhetoric. Any humanist speaker should acknowledge that tendency, and its implications, and seek to mitigate both.

A Jensen interview was broadcast on Unwelcome Guests in the wake of the release of his book, All My Bones Shake. The title references the Old Testament, which is indeed a shaky point of reference, if one is looking for justice. (For a humorous take on the topic, see Saramago's Cain; not yet translated into English, it seems.)

But still, there are parts of the Old Testament that do have a ring worthy of King, that resounding clarity. Jensen quotes Jeremiah 1, 7-10:

But the LORD said to me, “Do not say, ‘I am only a youth’;
for to all to whom I send you you shall go,
and whatever I command you you shall speak.

Be not afraid of them,
for I am with you to deliver you, says the LORD.”

Then the LORD put forth his hand and touched my mouth; and the LORD said to me, “Behold, I have put my words in your mouth.

See, I have set you this day over nations and over kingdoms,
to pluck up and to break down,
to destroy and to overthrow,
to build and to plant.”

Righteousness, indeed!

cowboys and indians

Wandering on, Jensen ended up linking to Chief Illiniwek, a fictitious Native American character set up as a mascot for the University of Illinois -- finally retired some five years ago, due to concerns that he was, well, racist.

"Racist" rings alarm bells with people, but ultimately it's correct I think. Continuing this confessional thing, I was also a Boy Scout as a kid, eventually reaching Eagle, even. The Illinois mascot came out of American Scouting, almost a hundred years ago, but pseudo-Indian traditions are quite alive there still.

The important thing to realize is that such pseudo-traditions are just that, pseudo. They're fake. They come from a real desire to connect, to the land and to people, but via a connection to an idealized culture, without any inhabitants, without a connection to its survivors; and without any examination of the relationship between the military (upon which Scouts are modeled), colonialism, and native peoples.

To me though, the important realization is the level of ignorance in the world, and I don't mean that in a malicious way at all. Everyone needs roots, and native cultures are part of that. But roots cannot go down without reconciliation, and a very hard look at the past and what it means in the present. And that's something that was never discussed by the proponents of "respect the chief" (a pro-Illinois-mascot group), and something that was totally ignored when I was a Boy Scout, dressed up in skins, pretending that I was an Indian.

the profit

Lest this all be a bit too heavy, let me close with the classic:

A quiet woman said,
Speak to us of Virtue.

He then answered.
Goodness and Kindness are popular Virtues.
Some Virtues are much older.

The serene chaos that is Courage, and the phenomenon of Unopened Consciousness have been known to the Great World eons longer than Extaboulism.

Why is that? the woman inquired.

Because I just made that word up, the Master said wisely.

Kehlog Albran, The Profit

Guile now does delimited continuations.

Ahem! I say: Guile now does delimited continuations! Whoop whoop!

Practically speaking, this means that Guile implements prompt and abort, as described in Dorai Sitaram's 1993 paper, Handling Control. (Guile's abort is the operator that Sitaram calls control.)

I used to joke that all of this Guile compilation work was to bring Guile back into the 2000s, from being stuck in the 1990s. But delimited continuations are definitely a twenty-teens topic: besides PLT Scheme, I don't know of any other production language implementation that has delimited continuations as part of its core language. (Please correct my ignorance.) If this works out, and the implementation proves to be sufficiently bug-free, this is a great step forward not only for Guile but for the concept itself of delimited continuations.

Edit: Readers suggest that I add Scheme48, OCaml, and Scala to the list. Still, too few implementations for such a lovely construct.

Furthermore, I retrofitted Guile's existing catch and throw APIs, implementing them in terms of prompt and control, and providing compatible shims for Guile's C API.

Thanks again to Matthew Flatt for blazing the trail here.

rambling

So, for the benefit of those dozen or so people that will probably implement delimited continuations after me, here's a few strategies and pitfalls. For the rest of you, I recommend rancid wine.

First, I should make a disclaimer. Here, my focus is on a so-called "direct" implementation of delimited continuations; that is to say, I don't rely on a global continuation-passing style (CPS) transform of the source code.

There was recently an article posted to the Scheme reddit about Femtolisp, a Lisp implementation by Jeff Benzason. I thought it was pretty neat. I was especially pleased that he decided to support shift and reset; but bummed when I found out that he did so by local CPS-transformation. So you couldn't reset from arbitrary functions.

A local CPS-rewrite strategy doesn't work very well, because prompts are fundamentally dynamic. There is something fundamentally dynamic about them, that they are part of the dynamic environment (like dynamic-wind). So to support that via CPS, you end up needing some kind of double- or triple-barrelled CPS, with abort continuations as well. I think? I think.

So for me, direct implementation means that you use the language's native stack representation, not requiring global or local transformations.

Also I should confess that I didn't glean anything from Gasbichler and Sperber's Final Shift paper; in all likelihood, again due to my ignorance. So if I say things that they've said better, well, stories have to be retold to live, and it won't hurt if I add my interpretation.

the seitan of the matter

So, Digresso Riddikulus: poof! Where were we? And what's up with this jack-in-the-box? Yes, direct implementations of delimited continuations.

Here's a C program:

int baz ();
int bar () { return baz (); }
int foo () { return bar (); }
int main () { return foo (); }

And here's a C stack:

Right! So you see that function calls are pushing frames on the stack.

When you're programming normally, you have a top-down view of the stack. It's like standing on a ladder and looking down -- you see the top rung clearly, but the rest is obscured by your toolbelt.

Laying out the frames flat like this allows us to talk instead about the whole future of this program -- what it's doing, and what it's going to do. The future of the program is known as its continuation -- a funny word, but I hope the meaning is clear in this context.

Now, consider a C program that calls into some hypothetical Scheme, assuming appropriate Scheme definitions of foo, bar, and baz:

int main () { return eval ("(foo)"); }

And the corresponding pixels:

It should be clear that there are logically two stacks at work here. However they both correspond, in this case, to the same logical control-flow stack -- eval doesn't return until foo, bar, and baz have returned.

Also note that the "C" stack has been renamed the "foreign" stack, indicating that Scheme is actually where you want to be, and whatever is not in the Scheme world is heathen. This model maintains its truthiness regardless of the implementation strategy of the Scheme -- whether it reuses the C stack, or evaluates Scheme expressions on their own stack.

So! Delimited continuations, right? Let's try one. Here's some Scheme code that begins a prompt, and calls baz.

(% (baz) (lambda (k) k))

If baz returns normally, well that's the value; but if it aborts, the partial continuation will be saved, and returned. Verily, pixels:

The red dot and line indicates that that position in the continuation has been saved, and if we abort, we'll abort back to that line. It's like grabbing a cherry from the tree, and then falling down a couple of rungs on the ladder. Yes? Yes.

Expanding the example with an implementation of baz, we have:

(define (baz) (abort) 3)

So, baz will abort to the nearest prompt, and if the abort comes back, it will return 3. Like this:

Abort itself needs to capture a partial continuation -- that part of the continuation that is delimited by prompt and abort. (That's why they're called delimited continuations.)

In practice, for the implementor, this has a number of fine points. The one I'll mention here is that you don't actually capture the prompt frame itself, or the presence of the prompt on the dynamic stack. I tried to indicate that in my drawings by making the red line disjoint from the red box. The red box is what's captured by the continuation.

See Dybvig's "A monadic framework for delimited continuations" for a more complete discussion of what to capture.

(define (qux)
  (+ (k) 38))

OK! Assume that we save away that partial continuation somewhere, let's say, in k. Now the evaluator ends up calling qux, which calls the partial continuation.

Calling the partial continuation in this context means splatting it on the stack, and then fixing things up so that it looks like we actually called baz from qux.

I'll get to the precise set of things you have to fix up, but let's pause a moment with these pixels, and make one thing clear: you can't splat foreign frames back on the stack. Maybe you can in some circumstances, but not in the general case.

The practical implication of this is twofold: one, delimited continuation support needs to be a core part of your language. You can't evaluate the "body" part of the prompt by recursing through a foreign function, for example.

The second (and deeper) implication is that if any intervening code does recurse through a foreign function, the resulting partial continuation cannot be reinstated.

One could simply error in this case, but it's more useful to allow nonlocal exits, and then error on an attempted re-entry.

So yes, things you need to fix up: obviously the frame pointer stack. The dynamic winds (and more generally, the dynamic environment). And, any captured prompts themselves. Consider:

Here we see a prompt, which has a prompt inside it, which calls baz, which then aborts back to the first prompt. (You will need prompt tags for this.) Now, note: there are two horizontal lines here: two prompts active in the dynamic environment.

Let's see what happens when we reinstate the continuation, represented by the red dotted box:

Here we see that the blue line corresponding to the captured prompt is in a different place (relative to the base of the stack). That's because when you reinstate a prompt, any captured prompts are logically made new: one must recapture their registers, both real (via setjmp) and virtual (in the case of a virtual machine) when rewinding the stack.

And that's all!

postre

Meanwhile, back at the ranch: while searching for the correct spelling of riddikulus, I stumbled upon a delightful interview with JK Rowling, in three parts. Enjoy!