Older blog entries for wingo (starting at number 334)

guile and delimited continuations

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.

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!

Syndicated 2010-02-26 20:39:22 from wingolog

lunches and lunches

unordered lists

There are lunches, and then there are lunches to write about.

Today I started to think I was in one of the latter when the patxaran came out; but I knew it when I decided to go to the park afterwards and lay down in the sun. Tomato & oil, chard & potato, rare beef, sweet fried things, vermouth, wine, "rancid wine", and yes, a shot of espresso.

Also: Barcelona's Ciutadella is its Dolores Park. No bi-rite creamery, nor tartine bakery, but the park itself has that same feel, sometimes. Wafting guitar, bagpipes, plucked violin, tightrope walkers, and jugglers, hand and foot.

Syndicated 2010-02-26 20:03:39 from wingolog

sidelong glimpses

Evening, tubes. I don't usually post about works-in-progress, but this one has been on my mind for two or three weeks, really paralyzing my mojo, so perhaps getting it out in textual form will help me move on a bit.

operation delimited continuation

So yes, to my non-programmer audience, let this be a pleasantly written but unintelligible lullaby, a word-train rocking you to sleep; but to the nerds out there, I'm quite fascinated with this topic, and I hope I'm able to convey some of that fascination to you.

Consider the following C program:

#include <stdlib.h>

int main ()
{
  abort ();
  return 0;
}

Let's assume we have it in foo.c, and compile it. We'll do so from tcsh, for reasons to be explained later.

$ tcsh
% limit coredumpsize unlimited
% gcc foo.c

OK, we should have a binary in a.out. Now, we run it, with predictable effects:

% ./a.out
Abort (core dumped)
% ls -l core
-rw------- 1 wingo wingo 151552 2010-02-14 21:37 core

So, what happened was that the program ran, then it got to the abort, which caused it to unexpectedly exit. Where did it exit to? In this case, back to the prompt.

That program is no longer running, but when it exited, it left behind a copy of its state -- of its continuation. A continuation is what's left of a computation. In this case, what's left is for abort to return, then main returns 0, then probably some system-specific code, then we'd be back at the prompt again. Aborting just brought us back to the prompt a little faster.

Anyway, the core dump has all of the data that would be necessary to complete the process' computation. With a debugger you can get in and see what that data was, but you can't run the program again from that point -- you'd need some extra OS-level support for that.

why are you talking about this stuff

Glad you asked! Core dumps are really a specific instance of control features in programming languages. Control features are what allow you to skip around in your program. In this case, we skipped back to the prompt.

Scheme includes support for a very low-level control feature known as continuations. With continuations, you can implement all kinds of things, like exceptions, coroutines, generators, and short-cut operators. You can make up new control operators in a Scheme library and add them to an innocent, unsuspecting program.

Many people are aware of this, but fewer know that continuations have a problem, a big problem. The origin of the problem is that a continuation captures the whole future of a computation, not just a part of it. So if you implemented exceptions with continuations, imagine dumping core every time you threw an exception. Not very efficient, no?

Well the truth is more complicated of course. If you have access to the entirety of a program, the compiler can transform your code into what is known as continuation-passing style (which the laity may recognize by the weaker names of single-static-assignment or A-normal form) and in that case invoking a continuation is just like calling a function. But for the rest of us, we have to play tricks with dynamic extents, incrementally dumping parts of the core as the program enters different dynamic extents.

(I'm simplifying here, to continue the core-dump metaphor, in the knowledge that the clergy will correct this doctrine in the comments.)

But in the general case, capturing and reinstating continuations can be quite expensive, because in the absence of sophisticated analysis, one simply dumps the whole core. It's a terrible but common implementation strategy.

There are other, deeper problems with continuations as present in Scheme, notably the lack of composability. Though I do understand that this problem is deeper, I don't understand its depths, so I'm going to forgo a discussion of that here.

the solution: more power

So, continuations are great, but they can be expensive to implement. OK. In this context it's amusing that the solution to this problem is actually to give continuations more power.

The problem is that in Scheme you have control over where you dump core, but not how far you dump core. While it's true that continuations logically capture the whole future of a computation, in practice that continuation has a limit: the process boundary. Our a.out was spawned at the tcsh prompt, but it has no access to the implementation of the shell itself, not to mention the kernel.

So, more power, as we were saying: let's allow programs to delimit the range of computation captured by a continuation. Instead of capturing continuations up to the process boundary, a program can capture a continuation only up to a certain point in a program.

Pleasantly, that point is known as a %, pronounced "prompt". (Dorai Sitaram notes that he would have preferred >, but it was taken by greater-than. Also, this comes from back in 1993, so perhaps he can be forgiven the tcsh-style prompt.)

It's as if you were implementing a shell in your program, as if your program were an operating system for other programs.

Here's a translation of foo.c into a Scheme that supports prompts:

(define (foo)
  (abort)
  0)

And now we run it, in a prompt:

(% (foo)
   (lambda (core . args)
     (format #t "Abort (core dumped): ~a\n" core)
     (format #t "Arguments to abort: ~a\n" args)
     1))
;; =| Abort (core dumped): #<continuation ... >
;; =| Arguments to abort: 
;; => 1

The second argument to % is the "handler". When abort is called, control returns to the handler, and the continuation -- the "core dump" -- is passed as the first argument. Unlike in UNIX, abort in Scheme can take any number of arguments. Those arguments are passed to the handler.

Also unlike UNIX, the core dump may be revived; but normal Scheme continuations do have a UNIX similarity in that reviving them is like invoking exec(3) -- they replace the current process image with a new one. This might be the right thing for user space to do, but if you're implementing a kernel, scheduling a process shouldn't give that process control over the whole system.

Instead, delimited continuations are more like functions, in that you can call them for a value. Like this:

(% (foo)
   (lambda (core . args)
     (format #t "Abort (core dumped, but continuing): ~a\n" core)
     (format #t "Arguments to abort: ~a\n" args)
     (core))) ;; revivify the core, letting the program finish
;; =| Abort (core dumped, but continuing): #<continuation ...>
;; =| Arguments to abort: 
;; => 0

gloves off

If you didn't know about continuations before, and you've gotten this far, then drinks all around! If not, then, um, drinks all around? In any case, we're going more hard-core now, so you'll need it.

Delimited continuations are not quite a new topic. The first reference that I'm aware of that begins to understand the problem is The theory and practice of first-class prompts, by Matthias Felleisen, in 1988.

Unfortunately that document is only available behind a paywall, because the ACM is a pack of scrooge mcducks. So instead you'll probably have to deal with Sitaram and Felleisen's 1990 contribution, Control delimiters and their hierarchies.

But don't read that one first. First, read Sitaram's beautifully clear 1993 paper, Handling control, which is a lovely exposition of the offerings that delimited continuations have to the working Scheme programmer.

An obvious extension of Sitaram's work is in the implementation of abstractions that look like operating systems. Back in those days it wasn't quite possible to imagine, but the current example would be the web server, where each session is a different process. So we return HTML and wait for the user to come back, and in the meantime schedule other processes; and when they do come back, we resume their session via resuming their computational process.

It's typically said that with continuations you can implement any control feature, but that's not true if your target language also has continuations. For example, you can implement exceptions with continuations plus mutable state, but if the program you are running also uses continuations in their standard Scheme form, the program's use can conflict with the implementation of exceptions, producing incorrect programs.

feature on top of feature

This is why it's 2010 now and no major programming language includes delimited continuations in its specification -- because it's tough to see how they interact with other primitive elements of the language. There has been a lot of research on this recently, with some promising results.

But before I move onto the shining light, I should mention a pit of darkness, which is the profusion of delimited control operators in the literature.

Sitaram in his papers proposes prompt (or %) and control (similar to abort) as his primary delimited continuation operators. But there are others. The ones that are seen most often in the literature are shift and reset, and also there is cupto. It was only in 2007 that Dybvig, Peyton-Jones, and Sabry were able to tease out their relationship; if you are interested, I highly recommend the first third of A monadic framework for delimited continuations, despite the title.

This result was mentioned by Matthew Flatt's 2007 paper, co-written by Yuan, Findler, and Felleisen, Adding Delimited and Composable Control to a Production Programming Environment. All this article has really been a prelude to mentioning this paper, and I think it merits a section of its own.

the flatt contribution

Go ahead and open up the Flatt paper, and skim through it.

I'll wait.

OK! First impressions?

Mine were, "what is the deal with all those pictures?". They seemed to be an affectation of friendliness, but appeasing neither the uninitiates nor the academics. But reading the paper in more depth, I was really impressed by their ability to convey information to the Scheme practitioner.

Because let's face it, there are piles and piles of terrible papers out there; and, what's worse, piles and piles of potentially good papers that simply aren't intelligible to the practicing programmer. OK, I dig on the lambda calculus; but what is your supposedly-proven result from your toy grammar going to do to help me make programs?

So I've always been skeptical, perhaps overly skeptical, of the desire to prove properties about programs, of the need to justify with symbology what you already know to be right. I still haven't seen the light. But at least now I know it exists, thanks to Flatt et al's paper.

The practical problem that I had was that Guile's catch and throw still weren't quite integrated with its new virtual machine; they caused the virtual machine to recurse, calling itself reentrantly. Besides being inelegant, this forced the catch expression and handler to be allocated as closures, and restricted potential optimizations.

So I started to look at how I could express catch and throw in Guile's intermediate language. It was not clear that I could add them in an orthogonal way, until I remembered something I read about delimited continuations; but it wasn't until the Flatt paper that I really understood how to implement catch and throw in terms of these lower-level primitives.

But again, it seems I'm writing into the night, so I'll try to wrap up briefly. The form of catch is like this:

catch key thunk handler [pre-unwind-handler]

Then on the other side, you have throw:

throw key arg ...

I'm not trying to argue these are the best control operators, not by a long shot; but they are what we have now, so we need to support them.

So, following Flatt, imagine we have a fluid (dynamically-bound) variable, %eh, the exception handler. Then throw is easy:

throw key arg ... =
  (fluid-ref %eh) key arg ...

Yay psuedocode. catch is trickier, though:

catch key thunk handler =
  let prompt-tag = (fresh-tag)
    % prompt-tag
      with-fluids %eh = (throw-handler prompt-tag key)
        (thunk)
      λ (cont thrown-key arg ...)
       handler thrown-key arg ...

Aside from the pseudo-code being obtuse, perhaps you're confused that the % there has three arguments -- a tag, then an expression, then the handler (a lambda). Well the tag is useful to identify a particular prompt, so that an abort can jump back to a particular location, not just the most recent prompt.

Also you're probably underwhelmed, that most of the interesting work was pushed off into throw-handler, which takes the given handler and does some magic to it. Well indeed, there is some magic:

throw-handler prompt-tag catch-key =
  let prev-eh == (fluid-ref %eh)
    λ (thrown-key arg ...)
     if thrown-key is catch-key or catch-key is true
       abort prompt-tag thrown-key arg ...
     else
       prev-eh thrown-key arg ...

So the resulting throw-handler would run in the context of the throw invocation, and if the key matches, or we are catching all throws (catch-key is true), we'll jump back to the prompt.

Note that in our definition of catch, the first argument is the captured continuation, but that argument is never referenced. This simple observation allows us to note at compile-time that the continuation does not need to be reified -- there's no need to dump core, it's just a longjmp().

Guile also supports pre-unwind handlers: handlers that run in the context of the throw instead of the context of the catch. Since Flatt breezed over this in his paper, I'll mention an implementation of that here:

catch key thunk handler pre-unwind-handler =
  let prompt-tag = (fresh-tag)
    % prompt-tag
      with-fluids
          %eh = (custom-throw-handler prompt-tag key pre-unwind-handler)
        (thunk)
      λ (cont thrown-key arg ...)
       handler thrown-key arg ...

So, all the same, except the handler is made by custom-throw-handler.

custom-throw-handler prompt-tag key f =
  let prev = fluid-ref %eh,
      running = make-fluid false
    λ (thrown-key arg ...)
     if thrown-key is key or key is true
       let was-running = fluid-ref running
         with-fluids running = true
           if not was-running
             f thrown-key arg ...
           # fall through in any case
           if prompt-tag
             abort prompt-tag thrown-key arg ...
           else
             prev thrown-key arg ...
     else
       prev thrown-key arg ...

what

I know your eyes are glazing over by now. Mine are too, and it's not just the wine. But there's something important here.

The important thing is that small sigil, =; those definitions really are it. If you can prove anything about the behavior of catch now, you should be able to prove it about the new implementation above -- even though it works completely differently.

That's power! Power to refactor, knowing that your refactorings are correct. Because I was lost in a morass, paralyzed in front of my keyboard, wondering about the ghosts awaiting me if I poked code. Now I know. I need an efficient with-fluids, some pieces of prompt and abort, and to add that all to the bootstrap language of Guile, and I have it. It's right. And I know it is because Flatt et al have already done all of the calculations for me :)

the sound of mandolins

I realize it's something of a fizzleout ending, but I think it has to remain that way before I get it all into git. Inshallah we'll be rolling like this to Guile 1.9.8, though it could very well be 1.9.9. But either way, I didn't imagine myself saying this, but thank you, Flatt & crew: your formal work has led me to see the way out of my practical problem. Cheers!

Syndicated 2010-02-14 23:55:00 from wingolog

sindicat, dia zero

I have been meaning to join a union for a long time. There is so much necrophilia in the world, a globalized obsession with The Economy that prefers numbers over life, that to be alive is an obligation to fight against deadening discourse.

I say "discourse", and I sound flaky, but I really do believe in the magical power of stories. Stories are why we get up and go to work in the morning. Granted, some correlation makes a story more powerful -- of Richard Stallman having Emacs at his back when he said, "Let there be GNU" -- but stories project into the future, generating the ongoing present.

But a bard alone does not a story make. A story is a relationship between people that feed each other. Groups that realize this have immense power, power over the ongoing present -- power to fashion (hu)man in their own image.

That's why I'm interested in unions. Most people work at the poo end of the capitalism stick, and they know it. They know that capitalism is also just a story, one among many; and that retelling another kind of story can lead to a better present.

axis powers

I'm 30 now, and Churchill be damned, I'm growing more leftist by the year. But perhaps it is tempered, if "tempered" is even an appropriate verb, by a growing appreciation of the value of autonomy -- freedom, but of the kind that ends that ends where another's nose begins. Generally speaking, coercion is an evil.

The corrupting influences of the very existence of coercion are not widely appreciated. Everyone knows that politicians tend to be despotic, but few people appreciate that anyone in such a position of control would tend to poison their community, and themselves. The problem is not the politicians, it is power itself. It's the "absolutely" in "absolute power corrupts absolutely". It's why Gandalf refused the ring.

Since it's an underappreciated point, let me draw a diagram. ASCII in the house!

                    human             machine
              +-----------------+------------------+
authoritarian |   socialists    |     fascists     |
              +-----------------+------------------+
libertarian   |   anarchists    |     randroids    |
              +-----------------+------------------+

To divide all of politics into two dimensions is a conceit, of course, but to me this is the most useful division. A further conceit is for those dimensions to carry a value judgement, but hey, it's my blog, and blogs are conceited anyway.

By human, I mean what in Spanish one would call solidario -- people working in support of each other. In contrast, machine privileges "the system" -- the economy, for example.

In the US, the common way of describing the political divide is "liberal versus conservative", which to me makes no sense whatsover. First of all, it misuses words: "liberal" has an accepted meaning in the international context, generally translating to "free-market". "Conservative" has the positive connotation of preserving traditions, but none of the practical implications -- practically speaking, conservatives are more "free-market" even than the liberals, and that free-market ideology leads to Wal-Mart and the death of Main Street and all those things that any US resident knows about.

These connotations obscure the real problem: the liberal-conservative axis represents but a part of the space that I showed above, a part mostly on the authoritarian-machine side. There are differences, but they are slight, given the big picture.

At the risk of belaboring the point, I'll point out one thing. Rural areas in the US are typed as being "conservative". But in reality many people are simply rebelling against an imposed authority -- "outsiders coming and telling us what to do". This is a libertarian sentiment. But these people then get caught in the (masterfully told) Republican story of "personal freedom is the freedom to do whatever you want, other people's noses be damned", and many come off believing it. The story creates reality.

apt-get install anarchy

It should be clear that I'm really attracted to the anarchist project. The anarchists are practically the only people that recognize the corrupting nature of power. Anarchist unions have no union bosses, unlike the majority of unions, here in Spain or otherwise. And anarchist unions are not just working at ameliorating working conditions, which is important, but also at the general plan of revolution, of enacting that story that we retell and dream: a world without coercion. That's what freedom means to an anarchist.

Personally speaking, my working conditions are fine, which gives me some liberty to write about these topics. I'm happy that I'm able to say that, but given that my needs are met, it's really an obligation to work for the freedom of others.

(I can't really leave this point without mentioning Propagandhi's Resisting Tyrannical Government.)

Many programmers are in a similar situation. It seems that computer programming is fundamentally tricky, and that the demand for programs always outweighs the supply of practitioners.

Of course if you're stuck in a shit job it might not appear that way. You're probably feeling a bit indignant, reading some of this, and I understand that. In that case you really need to protect yourself, via the traditional organizing methods of a union. See Val Aurora's negotiation notes for some steps you can take on your own; but we programmers are an individualist bunch. It's hard to accept that one can exhibit solidarity without abandoning personal freedom. I think unionizing programming shops is a fine idea, depending on the union of course.

cgt

Here in Barcelona there's a splendid anarchist tradition; beautiful, and heartbreaking too. The evening waxes long, so I can't dig up more links than this; but it hit close to barri here. The nearby Fabra i Coats textile plant, here in my Sant Andreu neighborhood, was colllectivized, along with many other workplaces.

The tradition lives on in many forms; in hearts, yes, but also in outward manifestations like the anarchosindicalists. It's not just about better working conditions; it's about better ways of inter-human relations, about a world without coercion.

So it's with all these thoughts in mind that today I stepped into the offices of the CGT. There was some confusion about what sector I was working in, finally resolved as "the commercial sector" (what?), but it seems I have joined a union.

Further bulletins as events warrant!

Syndicated 2010-02-13 00:02:42 from wingolog

nukular

Good evening, internet. I've got a personal story to tell, then something of immediate relevance. I just can't stand these stories about the NIF, this test fusion facility at Lawrence Livermore. But the personal bits first.

nukular

Faced with the typical dilemma of "what to do with your life", as a 16-year-old high school student, I was sure I wasn't going to be a nuclear engineer. My dad worked for the power company at that time, and I had grown up in the figurative shadow of McGuire nuclear station. The nerdiness of the whole thing attracted me, but the nuclear profession seemed so dead, like so much office work.

So it was with some surprise that I found myself that summer at a camp run by the nuclear engineering department at North Carolina State University. To this day I'm not sure why I went. But go I did, and ended up being attracted by the promise of solving our world's energy problems via fusion power. Limitless energy! And I, your humble writer, could have a hand in it. Surely there would be a corner of the spotlight reserved for my modest contributions, and if not the spotlight, then some nook in engineer heaven.

Nothing about the education there had much to do with fusion, though. Most undergraduate programs are basically funded by the nuclear power industry. There is some medical work, a fair amount of plasma work, and a modicum of fundamental work, but the professors who do well (and transitively, their grad students) sell to the fission power industry. Thermal hydraulics simulation codes. Safety assessments. Sponsored chairs. Fuel rotation algorithms (my department chair got rich off that).

But it took me a couple years to realize that, because you know, it's the bait and switch thing. Even to the very end. In my last year there I was working for a professor on a monotonic X-ray source, for medical imaging applications. As it was sold to me, this was going to allow more accurate mammograms, without the need for painful compression. All the simulations were coming out good, the device looked quite powerful, and my advisor said, "This will make a great gun!"

A gun! Because I didn't mention the other funder: the military. This guy was a Naval Fellow This and a Thank You From The Army That, and here I was thinking I was earning my honorable discharge via working on a medical imaging device.

I did end up getting my BS there, and at the top of my class, which that year was a class of one. But that's another story.

fusion

Well, longer story shorter. When I went into nuclear engineering, in 1997, the main way of thinking about fusion energy was the tokamak, the donut-looking thing that tries to make a ring of plasma, then magnetically compress it into a density and temperature that will sustain fusion. Then somehow you extract the heat, boil water, turbines, generators, same old story.

It's an enormous complicated thing, into which billions and billions of dollars were sunk, both in the US (like at the Princeton facility) and internationally, through ITER. About the same time I went into NE, US funding for ITER was pulled.

So what was I to do, the erstwhile fusion power Nobel prizewinner? Well the US story was that they had another thing going, the so-called National Ignition Facility. Perhaps you've seen it in the news recently. Their PR agency is quite good; the message was mainly conveyed as "plucky and valiant scientists make step towards fusion energy".

But the NIF has little to do with energy. Here's the deal: due to popular protest, the US can't make test explosions of H-bombs any more. But how are they to know what would happen if they dropped a bomb on some unsuspecting adversary, if they can't test their weapons? Well they simulate those explosions with computer codes. (That's why LLNL and LANL have the some of the world's fastest supercomputers.)

But how will they know if their codes actually work? They need actual fusion explosions. So they concocted a plan to sell Congress a power plant driven by fusion bombs.

That plant is NIF.

Of course, the actual development of this story has more nuances, but the reason that the US is funding NIF is entirely due to its military applications.

energy

Peak oil, peak coal, peak gas. Blood for oil. Global warming. Poisonous gas wells. Vampire hydro dams. These things are well-known.

Peak uranium is also fairly well-known, but fission energy has other problems, of which I'll touch only one today. But first, the engineering issues with internal-confinement fusion power.

NIF claims to be a power plant. But actually getting useful power out of bombs is very unlikely. How are you going to harvest the resulting heat energy without destroying the enclosure? What about all those neutrons? What about the radioactive trash that the neutrons make?

But beyond that, how would you sustain ignition of fusion bombs? The idea is, one explosion goes off. Then you position the next pellet, fire on it, and so on at such a rate that the residual heat creates conditions for a sustained reaction: ignition. When I was studying these things, the estimated necessary rate for this process was 10 to 20 times a second.

This is an engineering nightmare. Fission is easy in comparison.

I don't think ICF will ever achieve ignition, but this is a prediction from someone who's been happily out of that industry for almost a decade.

An almost equally large problem is money. Finance, rather. Nuclear fission plants can deliver effective per-unit costs of electricity, of course ignoring externalized costs. That is, effective if you don't count in finance costs. Building a fission plant typically costs multiple billions of dollars. Fusion plants are probably just as costly. The NIF test facility is already brushing 5 billion, though I wouldn't be surprised if it ended up costing twice that.

This financing issue turns out to affect not just the bottom line. It ends up being large, centralized agencies that control such large investments. Centralized power is centralized control, and that goes for electrical power too.

powerdown

As someone who went in idealistic, with the hopes of solving the world's energy problems, I am still an optimist. The solution to the world's energy problems will be twofold: power-down, and energetic democracy. One way or the other, we will consume less energy in the future. That's power-down. The other side is people producing sustainable energy for themselves and their community: geothermal heat, solar power, wind power.

There's simply no other way. We can try other ways, but they will only hurt us in the end.

Syndicated 2010-01-31 21:35:29 from wingolog

readings

While I fail to sleep, some readings:

Is it time for a Fifth International?, by Michael Albert. I've always respected Albert's work on parecon. He's a very smart and principled fellow. It's also equally clear that someone else will have to be the one to implement his ideas.

Permaculture for renters, and emergent urbanism. Via the ever-inspiring Federico.

Last year I went on a Jane Austen kick. Sense and Sensibility, Mansfield Park, Northanger Abbey, Pride and Prejudice, all these, check. Only two more savory delights left! Oh, Mr. Darcy!

My current reading is the fascinating The Assassination of Julius Caesar: A People's History of Ancient Rome. It's a little hard to get a hold of, but I highly recommend it. Parenti is a great storyteller, and it's great to hear him rip a hole in Cicero. It's also eerie how the struggles of Roman times echo our own.

Syndicated 2010-01-27 00:52:14 from wingolog

twenty ten

Sup tubes,

I'm feeling dandy as a dandy here, having just finished implementing a dynamic foreign function interface for Guile. By that I mean that you can call C procedures without writing any C code.

To be fair, most Schemes have this capability already, so Guile is playing catch-up here. But still, this is some sweetness. I can call functions with any number and type of arguments, including by-value struct args and return values, and things just work. It's nice, and liberating.

intensification

Continuing a series of things I'm told happen in France, I'm told that when you don't know the words to a song, and just make some stuff up, in French you're singing yogurt. Yaourt, rather. As in, Teak me daou tou ze pair dais yaourt yoaurt yaourt. I've always thought that Danone should host an international yogurt competition.

Anyway. nontechnical readers, feel free to hum the yogurt national anthem for a few paragraphs here, 'cause I'm going to talk about Guile a bit.

Guile! Hark, the beloved hack-country! Yes. We just made a release, did you know? 1.9.7, dontcha know. I'm particularly pleased that if you enter an expression at the REPL and something goes wrong, and you don't catch it, you are dropped into the debugger instead of being presented with a backtrace printout.

The debugger is totally silly at this point. You can't do much more than just print a backtrace. But you can parameterize the printing of that trace, print local variables for each frame (bt full), inspect values, print with different widths...

That last bit is crucial. You typically don't want objects to print out in their entirety, because that could be quite long. So you truncate the output. But Murphy's law says that the part that gets truncated is always the part that you need! So actually, being able to specify the #:width is a big win.

Also you can profile expressions. Like this one, check it:

scheme@(guile-user)> ,profile (resolve-module '(gnome gtk)) #:hz 20
%     cumulative   self             
time   seconds     seconds      name
 13.16      0.12      0.12  variable-bound?
 10.53      0.10      0.10  #<procedure 9d2ad68 at ice-9/boot-9.scm:584:4 (obj)>
  7.89      2.80      0.07  vm-apply
  7.89      1.27      0.07  memq
  7.89      0.17      0.07  module-make-local-var!
[...]

In this case it reminded me that I had some bugs to fix, that things were taking about 10 times longer than they should have. But hey, that's what profilers are for, right?

One can trace, too:

scheme@(guile-user)> ,trace (fib 3)
(fib 3)
|(fib 2)
||(fib 1)
||1
||(fib 0)
||1
|2
|(fib 1)
|1
3

Sweet? [Y/N]

There are other lovelies in that release: the SSAX XML toolkit is now part of Guile, there's some unicode normalization improvements, some speedups, more compile warnings, and such. It was a lovely release. 1.9.8 will be even better!

digression

This stuff isn't always on my mind, you know. Most of the time, perhaps; but maybe in the same way that what you go to sleep thinking about is in your dreams, and in your mind vaguely in the morning. I gave my folks the (excellent) Settlers of Catan game this Christmas, with the Cities & Knights 5-6 player extension, and we all slept dreaming of sheep.

(Catan is a great game, for those few of you that haven't had the pleasure yet, and it appeals to most everyone. Call a game night, for great justice!)

Anyway. Probably what's most been on my mind in recent weeks is movement: to Paris and back (often), to the north of France for Christmas, to Bruges and Ghent for New Year's, to Lousiana just recently for a number of birthdays -- speaking of which: I am now 30. Trust my words no more!

Apart from that, time passes. A few months ago I planted the idea in my parents' mind that we were going to make or join a commune in a few years. At this point they're totally down. They've put off buying "old age insurance", or whatever you call it -- instead we younguns will take care of them. It's a retirement plan.

If you're reading this from anywhere that has roots, at any level, this won't surprise you at all. But the states is a different kettle of fish. At 13 they bussed me 30 miles away to secondary school; at 15 I went to (public) boarding school, 250 miles away; at 17 to university, at a similar distance. But the university bit was "close", family-wise. It's common to go 1000 miles away. Then when you graduate, it's common to go 1000 miles in a different direction, to find a job, and then likewise 5 years later when you change jobs. Myself, I left the states, and spent 8 years of the aughties abroad.

What I mean to say though is that you aren't expected to have roots in the states. I didn't live near my grandparents. Going home just now I didn't go to North Carolina, I went to Louisiana where my mom's family is.

These are many details, but it's all to say, the future is going to be like the past, but not like the recent past. It was really neat to hear my mom and dad and sisters and aunt all down with the idea of living together. Separate "houses", same place. I'm sure we can get some more too -- friends, partner's family, &c. Maybe we can even take over a town government. The times, they are a'rollin' round, round to a re-vision of what they were.

nerd resolutions

Readers: you really didn't want to know my personal resolutions, did you? Perhaps you did. Kind readers, you few.

Silent sufferers, the rest; but here is some nerd fodder, in the form of new year's resolutions:

  • Switch to Notmuch mail. Will require some kind of Gnus-like integration.

  • Get a version of elisp running under Guile that's faster than Emacs' implementation, but still strictly compatible.

  • Release Guile 2.0 in March, to wide acclaim.

  • Go to FOSDEM, the European Lisp Conference, GUADEC, and one other conference. (More if you invite me to speak.)

  • Work-related: start working in a G-Speak environment by default (with G-Speak as the window manager).

  • Start poking solutions to Free distributed web services. GNU has a huge role to play here, and I think Guile is the language/vm in which to implement the applications. More on this in the future.

  • See if I can corral the necessary elements to get a working Guile-in-Emacs branch in Emacs' repository. A stretch for this year, I think.

You can see that all of these are for the love. I really dig on the Guile work that we've done the last year, and 2010 is the year to strut our stuff.

non-nerd resoutions

I guess the only one I really want to get out there is to be more real. Garden more. Chat more. Organize more. More human, more vegetable, less machine. How this meshes with my profession, or even my hack-desires, I have no idea.

Syndicated 2010-01-27 00:00:09 from wingolog

girations

time

Well, I do declare! It took me until after lunch to realize this day is has a personal significance: it was five years ago today that I came to Spain, not for the first time, but for this time.

Europe's been good to me, but the heartstrings still tug homewards. Here my word choice betrays me. True, there is no one place for me to go back to in the States, a "home" of relationships; but there is something there. Something green, something makeshift; something not entirely settled.

It sure isn't the health care. Or the architecture, for that matter, I notice as I hear the bells chime three, from the office where I sit.

I guess one doesn't have to explain the pull of a native land.

travellin

I'm told that in France one may wish bonne année all throughout January, as long it's the first time you see someone. So bonne année, tubes! Nice to rap at ya.

These waning days of my twenties are somewhat dislocated; or bilocated, perhaps. I spend a fair amount of time in Paris. Modern times, modern relationships, right? So it's me, my girlfriend, and the Talgo. I slept four nights on the overnighter last month, it will be four this month, and next month at least two.

It's not the cheapest way to travel, but I just feel bad about taking planes all the time -- apart from the environmental impact, plane travel just doesn't do a body right. You're alternately treated as a terrorist or a consumer. Your mind doesn't have time to arrive. It just ain't natural.

Anyway, until soon. Ciao!

Syndicated 2010-01-15 14:26:28 from wingolog

gnu, gnome, and the fsf

I have been meaning to write this article for a couple weeks now, ever since the recent GNU Hackers Meeting over in Göteborg. I'd rather be hacking tonight, but some other circumstances make such a report a bit more timely; so, here goes!

GHM

I arrived a little late, having missed the first day's talks. I was particularly irked to have missed Bruno Haible's talk on modularity and extensibility, but I understand that there will be some video up soon.

I didn't know enough at that time to miss having seen José Marchesi's talk, but now that I know the fellow, it is a shame indeed. Actually that was one of my biggest take-aways from that event: that I never really knew GNU as a community of maintainers. GNU in 2009 is not the kind of organization that flies people all over to meet each other, and it's to our loss. I hope to see much more of GNU hackers in the future.

So everyone that goes to conferences knows why they are great: the hallway track. Or the bar track, as it might be. So what were the topics?

GNU is not FSF

This point really surprised me: that GNU is not the Free Software Foundation. There a relationship, but they are not the same thing, not by a long shot.

So here's the deal. In the beginning, there was GNU. But Richard realized that in the world of 1985, with proprietary software on all sides, it would be easier to defend the small but growing software commons if hackers collaborated by assigning their copyright to one U.S.-based organization. The FSF was set up as the legal entity associated with GNU, with RMS at its head.

25 years later it's still like that. The copyright assignment paperwork that every GNU contributor signs has some clauses that obligate the FSF to keep their conributions free (in the Free Software sense), but ultimately trust in the FSF is a trust in RMS, and in his principles. It is a testament to RMS's character that there are 35000 lines in fencepost.gnu.org:/gd/gnuorg/copyright.list, representing at least 5000 contributors.

But what's up now? As free software became more and more successful, it became clear that there were other ways to get involved than just writing code. There's all kinds of advocacy work that needs doing, for example. The FSF was a natural concentration point for these efforts.

However, also inevitably, with the influx of people, the composition of the FSF changed. There are very few hackers in the FSF now. There is RMS of course, whose work these days doesn't involve programming, but that's about it. Recently Mako was added, which is an important step to redressing that situation, and more on that later.

I mean, look at www.gnu.org and www.fsf.org. See the difference?

So the advocacy and campaigning is with the FSF, and the hackers are with GNU. I think every GNU hacker is really down with the message of freedom; I mean, we are the ones hacking the hack. But, as a majority, the GNU hackers are not down with "Windows 7 Sins" or "Bad Vista" or most of these negative campaigns the FSF has been running recently.

I say this as a GNU maintainer, not as a representative of GNU, but I believe I have the facts right.

GNU and RMS

All GNU hackers respect RMS. We respect his ethical principles, his vision, his tenacity, and his hack. I mean, GNU Emacs: this, for most of us, is the best software in existence. The early days of GCC. Texinfo. Really remarkable contributions, these, without which the world would be a poorer place.

(If you disagree, that's cool; but I'm just trying to explain where we come from. I guess also I should clarify what I mean by GNU here. I mean, "people who have signed paperwork to assign copyright to the FSF". I know that mentioning the FSF there is a bit ironic, but it's a strict definition.)

But nowadays, while RMS's principles remain strong (thankfully), he's a bit absent, technically. That would be OK -- he has certainly put in his hack-time -- but that the GNU project doesn't really have a means to make technical decisions on its own right now. Each maintainer can mostly make decisions about their modules, and we can talk to each other (mostly via gnu-prog-discuss), but there is no governance structure for the GNU project itself.

Worse, sometimes RMS decides things without any input at all, when such input really is needed. The decision to bless Bazaar as the official GNU version control system, for example, really sits poorly with a lot of people. The adoption of SCM and MIT Scheme as two additional Schemes in the GNU project also are real WTF decisions.

These "blessings" don't have much of an effect on people's behavior -- most active GNU modules use git, for example -- but they make people lose faith in GNU's technical coherence.

The issue here is that the GNU project is a community of people working for software freedom, yes, but we have some specific values binding us together. One, the ethical principles of supporting user freedom; more on that later. Secondly, there is a technical vision of a "GNU project" as a cohesive, well-thought-out, integrated technical whole. One can now argue about the extent to which that is currently true, but it is a very important value to GNU hackers.

Things were more or less fine when there was more of UNIX that needed to be reimplemented, and when RMS himself was more on the ball. But now there is a significant measure of dissatisfaction within GNU itself about the way decisions are made. There are some steps being taken to fix this (a recently created GNU advisory board, for example), but it is ironic that some decisions in GNU really do come from one man.

At the same time there is actually a widespread concern within GNU about what would happen if decision making were to be made more open. No one wants outsiders making decisions, it would still have to be maintainers; but there is concern that things might get out of hand, that there might be too many pointless discussions, that bad decisions could be made, that there would be a tyranny of the talkers, etc. This is why things are changing really slowly. Everyone wants more autonomy, but they don't want to lose the solidarity.

GNU and GNOME

So what's the deal with GNU and GNOME? Everything, and nothing. Allow me to explain.

GNU people see GNOME as an "outside" thing at this point. To most GNU hackers, GNOME is not quite GNU. GNOME doesn't follow GNU's coding standards (recall the point about technical integrations), assigns no copyright to the FSF, and seems to prefer LGPLv2+ and not GPLv3+. There is hardly any communication between GNOME people and GNU people. In GNOME, people look at problems their systems are having, and decide to solve them within GNOME -- PolicyKit, for example.

(I don't want to pick on David's excellent software; but I'm equally sure that it never crossed David's mind to suggest PolicyKit for inclusion into the GNU project. There are many similar examples.)

Hell, many GNU people even use things like Sawfish or Xmonad or StumpWM or other such things. Admittedly, GNU folks would be more likely to install GNOME on their cousin's computer; but as for themselves, Emacs is the only program many people need.

GNOME people on the other hand are in two camps, more or less. Broadly speaking these camps correspond to Free Software and to Open Source, respectively. The former feel a strong heart-tie with the GNU project; perhaps they started working on GNOME back when it really was a GNU project, or perhaps they started with it because they believed in GNU's ethical principles and chose that environment because they wanted to spread user freedom to their friends. As I say, most GNOME people are disconnected from GNU per se, so this tie really is more cultural than practical, but it is there, and it is strong in its own way.

The Open Source people tend to value GNOME in particular from the days when Qt was GPL-only, or even proprietary, and GNOME allowed them to develop open source applications as well as proprietary ones. Open Source people appreciate the technical comraderie, as well as the technical excellence of the platform, but often disagree with the GNU project's copyleft principles, instead appealing to individual choice as to whether to use or make proprietary software or not.

I hope I haven't been uncharitable to anyone here. Please correct me in the comments if so.

is GNOME GNU?

So, Andre posts, wondering about the relationship between GNU and GNOME. I hope I have been able to add some broader context to the question.

I think that Andre's characterization of RMS as "fascistic" is totally wrong. There are serious problems of decision-making within the GNU project, yes, but "fascistic" takes it a bit too far, and almost brushes Godwin's Law ;)

The particular context in which the discussion has been brought up, that nasty thread on foundation-list, is unlikely to bring about any mutual understanding. It is ironic that the topic is the code of conduct, which was designed to promote understanding.

Bottom line, GNOME can be GNU if it wants to. But I don't think a decision is necessary right now, and certainly not on foundation-list, not in that thread of the talkers.

GHM redux

I promised to talk more about hallway tracks at the GHM, but I've run out of semicolons. Until next time!

Syndicated 2009-12-13 21:33:44 from wingolog

maxwell's equations of software

There was some interesting feedback on my last article, and I ended up wanting to say too much in reply that here I am again, typing at the ether.

Stephen reflects the common confusion that somehow this is just a little file that might or might not work. No man, this is Guile! That's the implementation of Guile's eval. So unit tests, yes, we have more than 12000 of them. Only some of them specifically test the evaluator, but all of them go through the evaluator.

But to be honest, I think unit tests help, but when I'm hacking the compiler the most useful test is to simply rebuild the compiler. If it successfully bootstraps, usually we're doing pretty well.

Zed raises a more direct criticism:

This is why I hate lisp: [link to my article] Long and dense, no comments, not semantic. That's "awesome code"?

I don't think I used the word "awesome", but yes, I believe so, in the sense of "inspiring awe" -- at least for me.

I'm going to call on my homie Alan Kay for some support here. There was an oft-cited interview with Alan Kay a few years back, when he described eval as "Maxwell's equations of software". I quote:

[Interviewer:] If nothing else, Lisp was carefully defined in terms of Lisp.

[Alan Kay:] Yes, that was the big revelation to me when I was in graduate school—when I finally understood that the half page of code on the bottom of page 13 of the Lisp 1.5 manual was Lisp in itself. These were “Maxwell’s Equations of Software!” This is the whole world of programming in a few lines that I can put my hand over.

I realized that anytime I want to know what I’m doing, I can just write down the kernel of this thing in a half page and it’s not going to lose any power. In fact, it’s going to gain power by being able to reenter itself much more readily than most systems done the other way can possibly do.

Just for context, here is that half-a-page -- Maxwell's equations of software:

evalquote is defined by using two main functions, called eval and apply. apply handles a function and its arguments, while eval handles forms. Each of these functions also has another argument that is used as an association list for storing the values of bound variables and function names.

 evalquote[fn;x] = apply[fn;x;NIL]

where

 apply[fn;x;a] =
       [atom[fn] → [eq[fn;CAR] → caar[x];
                    eq[fn;CDR] → cdar[x];
                    eq[fn;CONS] → cons[car[x];cadr[x]];
                    eq[fn;ATOM] → atom[car[x]];
                    eq[fn;EQ] → eq[car[x];cadr[x]];
                    T → apply[eval[fn;a];x;a]];
        eq[car[fn];LAMBDA] → eval[caddr[fn];pairlis[cadr[fn];x;a]];
        eq[car[fn];LABEL] → apply[caddr[fn];x;cons[cons[cadr[fn];
                                                   caddr[fn]];a]]]

 eval[e;a] =
       [atom[e] → cdr[assoc[e;a]];
        atom[car[e]] → [eq[car[e];QUOTE] → cadr[e];
                        eq[car[e];COND] → evcon[cdr[e];a];
                        T → apply[car[e];evlis[cdr[e];a];a]];
        T → apply[car[e];evlis[cdr[e];a];a]]

pairlis and assoc have been previously defined.

 evcon[c;a] = [eval[caar[c];a] → eval[cadar[c];a];
               T → evcon[cdr[c];a]]

and

 evlis[m;a] = [null[m] →  NIL;
               T → cons[eval[car[m];a];evlis[cdr[m];a]]]

From the LISP 1.5 Programmer's Manual

What a mess! Where are the unit tests? Where are the comments? A little bit of whitespace, please! They use "cdar", "caar", and "cadr". They should be using named accessors! What if you eval an atom that's not found in the association list? Did they really name a function "evlis"? Et cetera.

Now, I do think the LISP 1.5 (it wasn't yet spelled "Lisp" then) evaluator is awesome, as it was in McCarthy's first papers on the subject. If you disagree with that, that's cool, I see why one would "hate" my poor imitation.

But given the Lisp history of meta-circular evaluators, one doesn't need to comment every one as if it were the first. In the same way that one recognizes an if statement without the need for a design pattern behind it, I would want anyone who's hacking on Guile's evaluator to have read or perhaps even written several evaluators; and once you've written one, you know the pattern.

More substantively, Charles speculates on source-to-source transformations to ease interpretation. I admit almost total ignorance regarding PreScheme; I've been meaning to learn about it for years now. But the point of this evaluator was to have it use the same representation as VM-compiled procedures; ideally it should run fast, but the first priority is for it to run on the VM itself instead of on a separate stack. There's certainly many more clever things that can be done there, and thankfully since eval is implemented in Scheme and compiled like anything else, it will also reap advantages of an improving compiler.

Regarding Emacs, I hope to say more on that point within a week or so, when the video for my talk at the recent GNU Hackers Meeting gets put up.

Finally, Bubo asks if this work is in a released tarball. Not yet is the answer, but it will be in Tuesday's 1.9.6 release.

Happy hacking!

Syndicated 2009-12-11 14:23:10 from wingolog

325 older entries...

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!