They said it couldn’t be done, and he did it

The post on Dennis Ritchie by Herb Sutter is wonderful:

Before C, there was far more hardware diversity than we see in the industry today. Computers proudly sported not just deliciously different and offbeat instruction sets, but varied wildly in almost everything, right down to even things as fundamental as character bit widths (8 bits per byte doesn’t suit you? how about 9? or 7? or how about sometimes 6 and sometimes 12?) and memory addressing (don’t like 16-bit pointers? how about 18-bit pointers, and oh by the way those aren’t pointers to bytes, they’re pointers to words?).

There was no such thing as a general-purpose program that was both portable across a variety of hardware and also efficient enough to compete with custom code written for just that hardware. Fortran did okay for array-oriented number-crunching code, but nobody could do it for general-purpose code such as what you’d use to build just about anything down to, oh, say, an operating system.

So this young upstart whippersnapper comes along and decides to try to specify a language that will let people write programs that are: (a) high-level, with structures and functions; (b) portable to just about any kind of hardware; and (c) efficient on that hardware so that they’re competitive with handcrafted nonportable custom assembler code on that hardware. A high-level, portable, efficient systems programming language.

How silly. Everyone knew it couldn’t be done.

C is a poster child for why it’s essential to keep those people who know a thing can’t be done from bothering the people who are doing it. (And keep them out of the way while the same inventors, being anything but lazy and always in search of new problems to conquer, go on to use the world’s first portable and efficient programming language to build the world’s first portable operating system, not knowing that was impossible too.)

Thanks, Dennis.

Toolstrapping is everywhere - can you see it?

Jacques Mattheij introduces an evocative term: toolstrapping: "Whatever tool you are building, you need that tool to build the tool."

One of the reasons behind the continuing success of C seems to be that, by virtue of it being the standard programming language, there's no toolstrapping involved in using C (because it's already been done for you).

In the world of Scheme, we have the phenomenon that most Scheme implementations are written in Scheme, eternally perpetrating Scheme's sillier parts.

And people who say that plain text is somehow natural or native to computing simply ignore the toolstrapping involved in plain text: your quaint Unix is already toolstrapped up the wazoo for handling plain text.

The browser is a chance to raise the toolstrap bar: from plain text to hypermedia. The window of opportunity closes once we're able to run Emacs in X11 in the browser.

It's called programming

People get annoyed when they must write two lines of code instead of one, but I don't. It's called programming. – Rob Pike

How to beat the CAP theorem

Nathan Marz has an interesting proposal, How to beat the CAP theorem, that should resonate with all you FP shills out there:

• make all your data immutable
• index snapshots of your data using "purely functional" batch computing (e.g. MapReduce)
• index the realtime data arriving after the last snapshot using an incremental computing system
• for querying, merge the index of the last batch job with that of the incremental system

As Marz explains, incremental computing has a much higher complexity than batch computing. Using it only for the last few hours of data removes a huge complexity burden from your shoulders:

Since the realtime layer only compensates for the last few hours of data, everything the realtime layer computes is eventually overridden by the batch layer. So if you make a mistake or something goes wrong in the realtime layer, the batch layer will correct it. All that complexity is transient.

Programming Language Checklist

Programming Language Checklist: You appear to be advocating a new programming language. Your language will not work. Here is why it will not work.

(via @importantshock)

Alan Kay on type systems

I'm not against types, but I don't know of any type systems that aren't a complete pain, so I still like dynamic typing.

(HT Paul Snively)

Delimited continuations papers 2

Had a conversation with a friend about delimited, composable continuations again. Previously, I've linked to some papers about delimited continuations. Here are two important ones:

Representing Monads: We show that any monad whose unit and extension operations are expressible as purely functional terms can be embedded in a call-by-value language with "composable continuations". As part of the development, we extend Meyer and Wand's characterization of the relationship between continuation-passing and direct style to one for continuation-passing vs. general "monadic" style. We further show that the composable continuations construct can itself be represented using ordinary, non-composable first-class continuations and a single piece of state. Thus, in the presence of two specific computational effects -- storage and escapes -- any expressible monadic structure (e.g., nondeterminism as represented by the list monad) can be added as a purely definitional extension, without requiring a reinterpretation of the whole language. The paper includes an implementation of the construction (in Standard ML with some New Jersey extensions) and several examples.

A monadic framework for delimited continuations: Delimited continuations are more expressive than traditional abortive continuations and they apparently seem to require a framework beyond traditional continuation-passing style (CPS). We show that this is not the case: standard CPS is sufficient to explain the common control operators for delimited continuations. We demonstrate this fact and present an implementation as a Scheme library. We then investigate a typed account of delimited continuations that makes explicit where control effects can occur. This results in a monadic framework for typed and encapsulated delimited continuations which we design and implement as a Haskell library.

I've blogged about the API and hair-raising example offered in this paper before.

The Kernel Underground

A quick update on Kernel buzz:

There are now fourfivesixseven19 (I stopped counting) implementations of Kernel and Kernel-like languages:

• SINK, by John Shutt. Scheme.
• klisp, by Andres Navarro. C.
• js-vau and vau.rkt by Tony Garnock-Jones. JavaScript and Racket.
• Hummus, Cletus, and Pumice, by Alex Suraci. Haskell, Atomy, and RPython.
• Schampignon, Virtua, and Wat by me. JavaScript.
• Klink, by Tom Breton. C.
• Karyon, by Jordan Danford. Python.
• εlispon, by Pablo Rauzy. C.
• fexpress, by Ross Angle. JavaScript.
• Qoppa, by Keegan McAllister. Scheme.
• Schrodinger Lisp, by Logan Kearsley. Python.
• squim, by Mariano Guerra. JavaScript.
• Nulan, by Pauan. Python.
• IronKernel, by Ademar Gonzalez. F#.
• Bronze Age Lisp, by Oto Havle. Assembly.
• Pywat, by Piotr Kuchta. Python.
• Wat.pm, by unknown. Perl.
• Extensible Clojure

Check them out for inspiration, and write your own. It's fun. Fexprs are fun exprs!

There are some interesting Kernel discussions going on in the Guile thread (and here) on LtU. David Barbour provides welcome criticism. (The truth can only be found in conflict. - Tarkovksy)

Oh, and I created this:

Syntax is a monad

I'm becoming aware of a whole Lambda-Meme-Universe! This one via Dorophone:

Oleg cat

(via Paul)

Mortal combat

A slightly confused anonymous commenter (I get to say such things about anonymous commenters, right?) reminded me of this quote by Ray Dillinger:

The scheme community is now very invested in its macrology; they got there by long hard work and emotional processing and yelling and screaming and weeping and gnashing of teeth, and they still remember the pain of not having a standard macrology. You will not pry it away except from their cold dead fingers, and you will not redefine it without defeating them in mortal combat.

I think the commenter misunderstood my earlier post. Syntactic extension is absolutely necessary, and modern Scheme macro systems are a fine way to do it.

On macros

This post by David Barbour is one of the most insightful statements on macros I have read (along with Vladimir Sedach's analysis):

It has been my impression that, no matter what specific thing you use macros to do, you can later invent a neat language feature that handles the problem in a clean and nice manner. The problem is the "later". Macros can do it "now"... in an ugly, brutish manner, true, but the job gets done. ...

Even among people who find macros smelly, you'll find many who think macros the least distasteful of these choices.

John Shutt's response ties this in with fexprs - instead of delegating the job to a separate preprocessing step, let the language itself have the power of self-extension:

Macros are an unpleasant feature to compensate, somewhat, for limitations of a language. It's better to compensate for the limitations than to leave the limitations in place without compensating at all. Better still, though, would be to eliminate the offending limitations. (Remove the weaknesses and restrictions that make additional features appear necessary.) Make no mistake, fexprs don't necessarily increase the uniform flexibility of the language; but with care in the design they can do so, and thereby, the jobs otherwise done by macros are brought within the purview of the elegant language core. So instead of an ugly brutish fix with macros now and hope for a more elegant replacement later, one can produce a clean solution now with fexprs.

PS: This point is subtle. After all Scheme is already self-extensible. But Scheme macros still are an additional "layer" on top of, and separate from, the core language. Kernel's fexprs are not - they are the core language, thus bringing self-extension within the purview of the elegant language core.

I endorse this

SRII 2011 - Keynote Talk by Alan Kay

Another awesome talk by Alan "I invented the term" Kay, after the recent Programming and Scaling.

"The internet is practically the only real object-oriented system on the planet." (~30:00)

SRII 2011 - Keynote Talk by Alan Kay - President, Viewpoints Research Institute from SRii GLOBAL CONFERENCE 2011 on Vimeo.

Also, the notion of reinventing the flat tire can't get enough airtime.

Zippers

I really need to understand Zippers. This seems like a good article. In the meantime, I'll meditate on the following diagram.

Totally awesome: FOSS Patents: Samsung cites "2001" movie as prior art against iPad patent

Attached hereto as Exhibit D is a true and correct copy of a still image taken from Stanley Kubrick's 1968 film "2001: A Space Odyssey." In a clip from that film lasting about one minute, two astronauts are eating and at the same time using personal tablet computers. The clip can be downloaded online at http://www.youtube.com/watch?v=JQ8pQVDyaLo. As with the design claimed by the D’889 Patent, the tablet disclosed in the clip has an overall rectangular shape with a dominant display screen, narrow borders, a predominately flat front surface, a flat back surface (which is evident because the tablets are lying flat on the table's surface), and a thin form factor.

(via @chris_stevenson:@stilkov)

Software is a branch of movies

A post by HXA about the ideology of software engineering prompted me to re-read an old Ted Nelson essay. Some choice quotes:

"Virtual" does not mean, as many think, three-dimensional. It is the opposite of *real*.

Virtuality therefore means the *apparent structure of things*

Engineers generally deal with constructing reality. Movie-makers and software designers deal with constructing virtuality.

Software is a branch of movies.

Movies enact events on a screen that affect the heart and mind of a viewer. Software enacts events on a screen which affect the heart and mind of a user, AND INTERACT.

Praising Kernel

I love Kernel! Let's face it: While Paul Graham has reanimated Lisp, Lisp has become stuck in a rut. CL hasn't changed since '94, and it probably won't, and heck, that's even a good thing - CL is the mud ball of strength, the acting patriarch of the Lisp family. There's a better chance of CL being around in 50 years than most other programming languages. The same for Scheme, although it's in a bit of an identity crisis right now. But what's crazy about Scheme is that it has become focused on ahead-of-time compilation, in a world where people run Linux in JavaScript JIT compilers. One of the purposes of Scheme should be to push compiler writers to be smarter. Let's forget all that static, performance-oriented stuff, let's make it as dynamic and general and simple as it can get, and spend the following decades on amazing new tech to make it fast! That's what Scheme's about, right? And let's not talk about Clojure, they don't even "see the need" for EVAL [in ClojureScript]. So much for the state of Lisp. Can you see it? We need to put the fun, nasty fun, back into Lisp. Lisp has been resting on its well-deserved laurels for much too long. Heck, even Java is getting lambdas now, and there's talk of macros in JavaScript. Lisp's purpose in the programming language galaxy is to assist our most gifted fellow humans in thinking previously impossible thoughts, remember? Do you really think current Lisps are up to that task?

So where does Kernel fit in? In short, I think Kernel is as close as you can get to the essence, the rhyming scheme of Lisp. Whereas the R6RS doesn't even mention interactive development, Kernel is squarely interactive. And it provides crystal clear semantics to go with it. LETREC blackhole? Hopeless toplevel? Not in Kernel. First-class environments solve these issues. Look, Kernel has a single form, $vau, that is as powerful as lambda, define-syntax, and let-syntax combined! (Strike that, it's even more powerful - you can use Kernel's macros, fexprs, just like ordinary functions.) Need I say more? Kernel can truly bootstrap itself from its 3 (or less) built-in forms (counting them is not easy), without the need for a separate expansion process, and without the need for a hygiene system - Kernel is simply inherently hygienic (when used right). Another form, $define!, not only takes on the roles of define and set!, but also doubles, nay, triples, nay, n-tuples, as a primitive for arbitrary namespace manipulation - you can build any module system you like on top of this single primitive! Think about it? Can your language do that? Fat chance! But should your Lisp be able to do that? I'd say. Now, you say, but no one has written real applications in Kernel yet. I say: that's what's so cool about it! It's a brave new world, without trodden paths, full of new discoveries in semantics, implementation technologies, and other things we can't even see yet. In the past 50 years, Lisp has succeeded in bringing object-orientation, dynamism, functional programming, and other niceties to the philistines. Soon, they'll even have macros and EVAL. Now it's time for Lisp to move another 50 years forward. That's what Lisp is for! And as far as I can see, Kernel is the vehicle for that. So fire up your printers, print out John Shutt's amazing works Fexprs as the basis of Lisp function application; or, $vau: the ultimate abstraction and the Revised ^-1 Report on the Kernel Programming Language, bind them, study them, and start hacking on Lisp's future! It's easy (nah, OK, it's hard) and it starts with you!

Virtua subjotting

I'm keeping a quite detailed log of Virtua on the new Subjot service: http://subjot.com/manuel/virtua.

(Subjot is an interesting new microblogging service, where every user has multiple streams, and you can choose which to follow. Here's an invite. I have no affiliation with Subjot.)

The Virtua programming language

Virtua will be my next programming language, with the following core features:

• combined object lambda architecture
• delimited continuations
• fexprs
• plus, of course, all the good stuff we're used to from Lisp: sane syntax, numerical tower, ...

Virtua will be written in JavaScript. The goal is to make Virtua a good command language for interactive, extensible, browser-based applications, like an Emacs for hypermedia.

If you're interested to work with me on Virtua, do get in touch!

Notes on delimited continuations

Delimited continuations are one of those topics where you need to spend months or maybe even years in the cloud of unknowing, until it suddenly makes click. At least, that's this autodidact's experience.

Delimited continuations are awesome, because they let us abstract over control flow - as I like to put it one man's control flow is another man's data, or as Chung-chieh Shan puts it: delimited continuations liberate control flow.

Continuations as we know them (i.e. those created by call/cc) are undelimited, they represent the whole rest of the computation. Delimited continuations represent the rest of a sub-computation up to a given prompt. They come from investigating REPLs: when you capture an undelimited continuation, the continuation includes the REPL's control flow! Generally, you don't want that, so with delimited continuations, the REPL can install a prompt before executing code entered by the user, and then you can capture a delimited continuation just up to that prompt, excluding the REPL's code.

My favorite description of delimited continuations is offered right at the start of A Monadic Framework for Delimited Continuations, even though the rest of the paper is quite over my head. Their API for delimited continuations is:

• newPrompt --- creates a fresh prompt, distinct from all other prompts. It's just an object that we use as an identifier, basically. Some systems simply use symbols for prompts.
• pushPrompt p e --- pushes prompt p on the stack, and executes expression e in this new context. This delimits the stack, so we can later capture a delimited continuation up to this part of the stack.
• withSubCont p f --- aborts (unwinds the stack) up to and including the prompt p, and calls the function f with a single argument k representing the delimited continuation from the call to withSubCont up to but not including the prompt. This captures a delimited continuation, analogous to how call/cc captures an undelimited continuation.
• pushSubCont k e --- pushes the delimited continuation k on the stack, and executes expression e in this new context. This composes the stack of k with the current stack, analogous to how calling the function representing a continuation in Scheme swaps the current stack with the stack of that continuation.

Now to the example! Delimited continuation examples are always hair-raising!! Brace yourself!!!

So, the first thing we do is call newPrompt (at the bottom) to obtain a fresh prompt, and then we pipe that into the function (at the top), so that we have a name, p, for the prompt. Inside that function we have the addition of 2 to a second expression, that pushPrompt's p on the stack, i.e. delimits the stack at this point. The if is called inside the new context delimited by p. Now it gets hairy: The if's test expression is a withSubCont, so it immediately aborts up to the outer pushPrompt and then calls the function that is its second argument with k bound to the rest of the computation between the withSubCont and the pushPrompt. What's the rest of that computation?? Well, by the magic of delimited control, k is now equivalent to the function λb. if b then 3 else 4. This is what I meant when I said that delimited continuations allow us to abstract over control flow - we have just turned an arbitrary, dynamic control flow sequence into a function. (Well, it's not really a function, but we can use it like one.) OK, so we have aborted back up to pushPrompt, and in k we have the rest of the computation as a function. What do we do with it? Well, we call it using pushSubCont once with False and once with True as argument, and we add the two results, giving us 7. Note that we just called the delimited continuation twice! We can not only abstract over arbitrary control flows, we can also call them as many times as we like. Now the whole shebang inside pushPrompt is over, and we return to the addition of 2 to our result of 7, giving us 9.

Previously: papers on delimited continuations.

A little Scheme interpreter

I've rewritten the Scheme interpreter from Kent Dybvig's dissertation Three Implementation Models for Scheme in JavaScript: Schampignon.

I think this is really a nice way to learn about implementing tail-calls and first-class continuations.

Schampignon is undocumented, because it's really just a rewrite of the Scheme code in section 3.4 of the dissertation, which explains things nicely. (Still, it took me a couple of days to figure out how it works.)

My next steps will be to add delimited continuations and fexprs to the code.

Going co-nuclear

I was discussing implementation inheritance on Twitter (no really!), when it dawned on me that my discussion partner was from a different "paradigm cult", and no agreement was possible.

John Shutt describes it nicely in his post Memetic Organisms:

The meme set carried by the [memetic] organism includes a mass of theories, some of which contradict each other. At the center of this mass is a nucleus of theories that are supposed to be believed (part of what Kuhn called a paradigm). Surrounding the nucleus are theories that are meant to be contrasted with the paradigm and rejected, together with memes about how to conduct the contrast; one might call this surrounding material the co-nucleus.

For the Clojurian I was talking to, implementation inheritance is co-nuclear. There's probably no way for him to accept that it has valid uses.