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.

Intellectual badass Sunday reading

"Nerd? We prefer the term intellectual badass." – Unknown

AMD Fusion Developer Summit Keynotes, about AMD's upcoming "Cray on a Chip". Basically, they'll make the parallel processors (formerly known as GPUs) coherent with the brawny sequential CPUs, allowing you to "switch the compute" between sequential and parallel, while operating on the same data (e.g. fill an array sequentially, then switch to parallel processing to crunch the data, all in the same program - and memory space).

[racket] design and use of continuation barriers, by Matthew Flatt. "Use a continuation barrier when calling unknown code and when it's too painful to contemplate multiple instantiations of the continuation leading to the call."

Monads and Effects is a bad marriage, by David Barbour (who is probably really a front for an army of intellectual badasses). "Monads capture a lot of effects by default: ordering/time, identity, state, commitment, and unbounded time/space resource consumption."

Tutorial: Metacompilers Part 1, about META II, the one Alan Kay and the other VPRI folks always talk about. "You won't really find metacompilers like META II in compiler textbooks as they are primarily concerned with slaying the dragons of the 1960s using 1970s formal theory."

Microsoft and the Bavarian Illuminati: "In the Object Linking and Embedding 2.0 Programmer's Reference there is a very curious term. On page 78, the second paragraph starts with the sentence, 'In the aggregation model, this internal communication is achieved through coordination with a special instance of IUnknown interface known as the /controlling unknown/ of the aggregate.'"

Linux kernel word cloud

(click to enlarge; via @hexmanshu)

The meaning of forms in Lisp and Kernel

There are so many nice things to be learned from Lisp - and Kernel.

Take this:

A Lisp REPL reads forms input by the user.

But Lisp is never content with a form alone: it always wants to evaluate the form, determine its meaning.

For instance, when you input a symbol form, Lisp will not just return the symbol object - it will return the value of the variable binding referenced by the symbol - which is the symbol's meaning, per Lisp's rules of form evaluation.

No wonder then that one of the central features of Lisp is quotation - telling Lisp not to determine the meaning of a form presented to it, but rather give us the form itself.

So what's a form? A form is "any object meant to be evaluated", in other words, we may treat any object as a form, as something to evaluate, as something to determine the meaning of.

Lisp's evaluation rules do not prescribe in any way that forms are bound to text-based representations - a form is any first-class object meant to be evaluated. (And in fact, Racket, a leading Lisp implementation already supports images as forms.)

So Lisp is chiefly concerned with determining the meaning of forms read from the user.

Macros then allow us to extend the variety of forms recognized by a Lisp, beyond the ways that mere function calls can.

Where in a function call the meaning of every operand is established automatically before the function is actually called, macros have total freedom in evaluating - determining the meaning of - operands, or not evaluating them at all (as a short-circuiting AND operator may do, for example).

But Common Lisp and Scheme macros, by their preprocessing nature (a macro call works at a time conceptually different from runtime, translating source expressions to other expressions, to be evaluated at a later time), cannot be used in a first-class fashion. For example, it is not possible to apply the AND macro to a list of dynamically computed values (without resorting to EVAL), like we could with a function.

In a sense, macros of the preprocessing kind restrict our ability of determining the meaning of forms: With preprocessing macros, we may only determine the meaning of forms available at preprocessing time.

This where Kernel's fexprs come in. Fexprs drop the requirement of macros to be expandable in a separate preprocessing step. Thus, we may apply the AND fexpr to a list of dynamically computed operands, for example.

But fexprs go beyond being merely a more convenient replacement for macros. As John Shutt shows, a new lexically-scoped formulation of fexprs - as presented in Kernel - is even more fundamental to Lisp than lambda. In Kernel, lambda is defined in terms of vau, the ultimate abstraction:

($define! $lambda
  ($vau (formals . body) env
     (wrap (eval (list* $vau formals #ignore body)
                 env))))

Through the power of fexprs, Kernel needs only three built-in operators (define, vau, and if) as well as some built-in functions. This is vastly simpler than any definition of Scheme! Scheme built-ins such as lambda, set! (!), define-syntax and others fall directly out of fexprs, for free, radically simplifying the implementation. But I'm rambling.

In essence, fexprs liberate Lisp's ability to determine the meaning of forms.

It's getting midnight (on a Sunday!), so I can't do fexprs or my excitement about them justice. But I hope this post has made you think about forms and their meanings, and to check out Kernel and share the excitement about the brave new Lisp world of fexprs.

The War Between Developers, Designers, & Project Managers

(via @zachlendon)

Previously:

Some history

Reading the interesting Portable and high-level access to the stack with Continuation Marks, I found the following quote about procedure calls (my emphasis):

This [not properly tail-calling] behavior of the SECD machine, and more broadly of many compilers and evaluators, is principally a consequence of the early evolution of computers and computer languages; procedure calls, and particularly recursive procedure calls, were added to many computer languages long after constructs like branches, jumps, and assignment. They were thought to be expensive, inefficient, and esoteric.

Guy Steele outlined this history and disrupted the canard of expensive procedure calls, showing how inefficient procedure call mechanisms could be replaced with simple “JUMP” instructions, making the space complexity of recursive procedures equivalent to that of any other looping construct.

Then it gets highly ironic, with a quote by Alan Kay:

Though OOP came from many motivations, two were central. ... [T]he small scale one was to find a more flexible version of assignment, and then to try to eliminate it altogether.

Some nice paperz on delimited continuations and first-class macros

My current obsessions are delimited continuations (see my intro post) and first-class macros (fexprs). Here are some nice papers related to these topics:

Three Implementation Models for Scheme is the dissertation of Kent Dybvig (of Chez Scheme fame). It contains a very nice abstract machine for (learning about) implementing a Scheme with first-class continuations. I'm currently trying to grok and implement this model, and then extend it to delimited continuations.

A Monadic Framework for Delimited Continuations contains probably the most succinct description of delimited continuations (on page 3), along with a typically hair-raising example of their use.

Adding Delimited and Composable Control to a Production Programming Environment. One of the authors is Matthew Flatt, so you know what to expect - a tour de force. The paper is about how Racket implements delimited control and integrates it with all the other features of Racket (dynamic-wind, exceptions, ...). Apropos, compared to Racket, Common Lisp is a lightweight language.

Subcontinuations. This is an early paper on delimited continuations. It also describes control filters, a low level facility on top of which dynamic-wind can be implemented. Control filters are also mentioned - in passing - as a nice tool in the Racket paper (above).

Fexprs as the basis of Lisp function application or $vau: the ultimate abstraction and the Revised^-1 Report on the Kernel Programming Language. These two are probably the two papers I would take to the desert island at the moment. I'm only a long-time apprentice of programming languages, but I know genius when I see it.

If you know of any related nice papers, let me know!

---

On Twitter, Paul Snively mentioned Oleg's paper Delimited Control in OCaml, Abstractly and Concretely, but probably only because he's mentioned in the Acknowlegdements - kidding! It's a great paper, and I'm studying it too, but unfortunately it's not really applicable to implementing delimited control in JavaScript, which is what I'm trying to do.

Everything you always wanted to know about JavaScript...

...but were afraid to ask Brendan Eich. (the whole thread, starting with this post)

On the absence of EVAL in ClojureScript

[I got bored with the original text of this post. In short: the authors of ClojureScript have taken the pragmatic approach of reusing Clojure-on-the-JVM to generate JavaScript. This means there can be no EVAL in ClojureScript. I think that's sad because Lisp is one of the finest application extension languages, and without EVAL you can't do a really extensible app. Apparently, the ClojureScript authors view the browser-side as something of an adjunct to server apps. In my view, all the action of the future will be in the browser, and not on the server.]

Frankenprogramming

David Barbour throws down the gauntlet to John Shutt in an already interesting and entertaining ("about as coherent as a 90 day weather forecast") LtU thread:

John Shutt would like to break the chains of semantics, e.g. using fexprs to reach under-the-hood to wrangle and mutate the vital organs of a previously meaningful subprogram. Such a technique is workable, but I believe it leads to monolithic, tightly coupled applications that are not harmonious with nature. I have just now found a portmanteau that properly conveys my opinion of the subject: frankenprogramming.

I'm looking forward to John's reply. In the meantime, I have to say that I like to view this in a more relaxed way. As Ehud Lamm said:

Strict abstraction boundaries are too limiting in practice. The good news is that one man's abstraction breaking is another's language feature.

Previously, regarding fexprs: John Shutt's blog

Atwood's Law

Any application that can be written in JavaScript, will eventually be written in JavaScript.

(source; also: Duke's Law)

it is nice to have the power of all that useful but obsolete software out there

Subject: Re: Switching tasks and context
∂08-Jul-81 0232 Nowicki at PARC-MAXC Re: Switching tasks and context
Date: 6 Jul 1981 10:32 PDT
From: Nowicki at PARC-MAXC
In-reply-to: JWALKER's message of Wednesday, 1 July 1981 11:52-EDT
To: JWALKER at BBNA
cc: WorkS at AI

[...]

The important thing is that such a tool WORKS, and I find incredibly useful. The virtual terminal uses ANSI standard escape sequences, so we can use all the tools that have been around for a long time (like the SAIL Display Service, Emacs under TOPS-20 or Unix, etc.) with NO modifications. We are planning to use this to develop a more integrated system, but it is nice to have the power of all that useful but obsolete software out there.

---

(via Chris, who's scouring Unix history for us)

PL nerds: learn cryptography instead

I've never studied cryptography. So when the paper Tahoe – The Least-Authority Filesystem fell in my lap, I was perplexed.

Using just two primitives, secret-key and public-key cryptography, they build an amazing solution to information storage. (Try to understand the two main diagrams in the paper. It's not hard, and it's amazing.)

Before encountering Tahoe-LAFS, cryptography was just a way to keep stuff secret to me. But cryptography also provides us with tools to design programs that wouldn't be possible otherwise.

State of Code interview

Zef Hemel has interviewed me for his weblog, State of Code: Lisp: The Programmable Programming Language. I don't feel qualified to be the "Lisp guy", but as you know, I never leave out an opportunity to blather about PLs.

Zef (@zef) is an academic developing mobl, a language for mobile apps, and is now working for a web-based IDE company, so the State of Code is a place to watch.

John Shutt's blog

John Shutt now has a blog: Structural insight.

John is pushing the envelope of Lisp with his Kernel programming language, a "dialect of Lisp in which everything is a first-class object". And when he says everything, he means it.

Not content with just first-class functions and continuations, John also wants first-class environments and first-class macros. Some fun LtU discussions in which John participated come to mind:

• Fexprs as the basis of Lisp function application; or, $vau: the ultimate abstraction
  
• Lisps, First-Class Special Forms, Fexprs, The Kernel Programming Language
  
• First-class environments. Discuss. ;)

David Barbour's soft realtime model

David Barbour is to me one of the most important thinkers on distributed programming languages and systems.

He frequently posts on LtU and on Ward's wiki.

(And he now has a blog!)

In this LtU post he describes a very interesting soft realtime programming model, reminiscent of Croquet/TeaTime:

---

I'm also using vat semantics inspired from E for my Reactive Demand Programming model, with great success.

I'm using a temporal vat model, which has a lot of nice properties. In my model:

• Each vat has a logical time (getTime).
• Vats may schedule events for future times (atTime, atTPlus).
• Multiple events can be scheduled within an instant (eventually).
• Vats are loosely synchronized. Each vat sets a 'maximum drift' from the lead vat.
• No vat advances past a shared clock time (typically, wall-clock). This allows for soft real-time programming.

This model is designed for scalable, soft real-time programming. The constraints on vat progress give me an implicit real-time scheduler (albeit, without hard guarantees), while allowing a little drift between threads (e.g. 10 milliseconds) can achieve me an acceptable level of parallelism on a multi-core machine.

Further, timing between vats can be deterministic if we introduce explicit delays based on the maximum drift (i.e. send a message of the form 'doSomething `atTime` T' where T is the sum of getTime and getMaxDrift.

---

Previously: Why are objects so unintuitive

Everything in JavaScript, JavaScript in Everything

We can now run Linux, LLVM bitcode, and a lot of other languages in JavaScript.

And we can run JavaScript in everything - browsers, servers, toasters, Lisp.

Like IP in networking, JavaScript is becoming the waist in the hourglass.

I don't know what it means yet, but it sure is exciting.

No No No No

// Note: The following is all standard-conforming C++, this is not a hypothetical language extension.

 assert( top( o-------o
              |L       \
              | L       \
              |  o-------o
              |  !       !
              !  !       !
              o  |       !
               L |       !
                L|       !
                 o-------o ) == ( o-------o
                                  |       !
                                  !       !
                                  o-------o ) );

Multi-Dimensional Analog Literals

WADLER'S LAW OF LANGUAGE DESIGN

In any language design, the total time spent discussing
a feature in this list is proportional to two raised to
the power of its position.

    0. Semantics
    1. Syntax
    2. Lexical syntax
    3. Lexical syntax of comments

(That is, twice as much time is spent discussing syntax
than semantics, twice as much time is spent discussing
lexical syntax than syntax, and twice as much time is
spent discussing syntax of comments than lexical syntax.)

(source, via Debasish Ghosh)