The Axis of Eval

Fun with Kernel

2012-01-20T19:43:00.005+01:00

Smug Kernel Weenies - known to be even smugger than Smug Lisp Weenies - are advised to check out Dale Schumacher's series on Kernel:

Besides vau (known as the Wow Combinator by fans, Frankenexpressions by critics), that unifies functions and (hygienic) macros in a single concept (with some open questions), one of my favorite Kernel features are first-class environments. They're just cute.

First-class environments have been shown to exhibit nice properties (e.g. you can write a module system in userland), and solve some of Scheme's problems (such as the letrec black hole), by Queinnec in the somewhat difficult to read Sharing Code Through First-class Environments. I think all designers of new dynamic languages should seriously consider them.

Previously: The Kernel Underground, Praising Kernel.

Why I find Dart's production mode evil

2012-01-06T21:10:00.006+01:00

Why Dart Types Are Optional and Unsound contains the following example:

class Mammal {}
class Cow extends Mammal { String moo() => 'moo!';  }
class Pig extends Mammal { String oink() => 'oink!'; }

Mammal mammal = new Mammal();
Cow cow = new Cow();
Pig pig = new Pig();

mammal = cow;      // [1]
pig = mammal;      // [2] Checks OK statically, but now pig holds a Cow.
print(pig.oink()); // [3] NoSuchMethodException if we get this far.

In production mode, the type declaration that pig holds instances of Pig is simply ignored at [2]! IMO, this should never happen. The Dart team's reasoning is that this is still "safe", because you'll get a NoSuchMethodException at [3].

But think about it: you might get the NoSuchMethodException at a completely different place in the program! What good are type declarations/assertions when you never know whether they are true? It actually feels worse than having no type declarations at all!

Thankfully, in Dart's checked mode, you will get the error at [2], making this behavior less troubling. But given that the page says that "type checks are not a major drain on performance", why have production mode at all?

Update: Relief! Bob Nystrom writes on HN:

My understanding was that the prime original motivation for unchecked mode was indeed performance. As our Dart implementations are getting more mature, we're starting to get a better picture of how it does actually impact performance.

I think what we're starting to see is that the performance implications aren't that bad. Given that, I think we're focusing less and less on production mode. It's still a valid option and it may make sense for some users but it may not be commonly used, sort of like -Ofast in gcc.

Small data and humble sequentialism

2012-01-06T17:50:00.002+01:00

Yeah, big data and massive parallelism in the cloud are exciting!

But there are two problems with the cloud:

Technical: doing stuff in centralized data centers, when all of your users have multiple, hugely overprovisioned computing devices is a bit of a joke.
Political: do you actually want to have all your users' data, and take on the huge responsibilities and risks associated with that?

The cloud is really a reaction to browsers' highly limited request-response interaction style. But browsers have changed now, they're becoming little operating systems.

May I suggest to take a fresh look at small data and humble sequentialism in 2012?

Type systems vs interactivity

2012-01-06T01:17:00.010+01:00

On Twitter last night, Paul Snively and I had one of our recurring type systems vs interactivity discussions.

Paul made his point clear:

My thesis is that programmers' ability to be logically inconsistent in a formal sense at any stage of development is overrated. #

To which I replied, equally grandly:

Without the ability to be inconsistent, you can't support the Lisp Experience™ #

My point is this: current type systems treat type checking as a batch job. But:

Intermittently, during editing, programs are nonsense. then we bring them back into consistency. type systems should support this #

I'd really love to treat type system outputs not as one-off errors that prevent running the program, but rather as a dynamic console of warnings, that updates as I change the - running - program. Every warning corresponds to a point in the program where I might get a runtime error if I were to run the program at this moment.

Update: James Iry blogged about the same conversation in Type Errors as Warnings.

Update 2: Paul Snively added another nice quote:

I observe that I'm given to extremes: give me Kernel or give me Coq! #

Update 3: Great minds think alike. Brian McKenna reports:

Simon Peyton-Jones talked about this a couple of times with me. It's something he's going to try with GHC #

Update 4: around 27:00 in this talk, SPJ details his idea for type warnings. #

Restartable exceptions

2012-01-04T19:04:00.006+01:00

TL;DR: Restartable exceptions are a must for new languages & they're dead simple to implement.

A dormant LtU thread on Go's proposed panic/recover exception-like mechanism is waking up again, and I'd like to take the opportunity to evangelize restartable exceptions once again (see also my previous post What's a condition system and why do you want one?).

Especially, because this is one of the few topics where David Barbour and me are of the same opinion. :) In the thread, David presents an interesting list of Error Handling Patterns, which includes the following points (my emphasis in bold):


Exceptions: Include a non-local exit so that error-handling may be isolated upon the stack. Unfortunately, in many languages this "unwinds" the "stack", and thus a lot of important, unfinished work is simply lost, and the error-handling policy cannot effectively say anything useful about error recovery. [...]
Resumable Exceptions: The unfinished work is maintained during error handling, and there are mechanisms available to return to that work - i.e. by return value, or via 'resumption points' annotated in the code (which look the same as exception handlers). This allows a great deal of flexibility for what those error-handling policy can express, similar to the pass-a-handler approach. The greater structure, however, can lead to better performance and static analysis.
Usefully, the difference between resumable exceptions and regular exceptions only requires a very minor tweak in implementation, even in languages such as C++ and Java: handle the exception as a new activation at the top of the stack, rather than unwinding first. (These activation records would need to include a pointer to the original frame in addition to the stack pointer.) This is exactly what Dylan does.

For a practical example of restartable exceptions, check out Chris Double's A tale of restarts ('This is a "I'm glad I used Dylan" story...').

Now, I still don't fully grok Kernel's continuation guarding ("Exception-handling 'done right'") and how it relates to restartable exceptions. This is definitely another topic John should put on his growing list of blog posts to write. :P

Ringing in the new programming year

2012-01-03T23:14:00.003+01:00

Straight outta Rob Pike's Command Center: Esmerelda's Imagination:
I resolve to recognize that a complaint reveals more about the complainer than the complained-about. Authority is won not by rants but by experience and insight, which require practice and imagination. And maybe some programming.
Gah. :) And Matt Might's 12 resolutions for programmers.

And don't worry, today's the most depressing day of the year, say experts.

(winningp) => t

2012-01-02T16:51:00.004+01:00

Thank you Paul Graham for the Lisp renaissance.

Say what you like about the tenets of Lisp, Dude, at least it's an ethos.

Some signs that Lisp has now gained significant mindshare again:

Designers explicitly state that they won't have macros or don't have them yet: Deca, Lua
Languages actually do add macros: Scala, Elixir

Now the big problem is that, as they say, in CS not only do we not learn from our mistakes, we also don't learn from our successes.

Let me tell you: people will spend the next 20+ years reinventing hygienic macros. (Or they could just use fexprs, and get hygiene for free.)

Isn't goto evil?

2012-01-01T23:09:00.002+01:00

Goto-considered-harmful-weenies (don't trust 'em) should ponder the following remark from the Novelties of Lua 5.2:

continuations are much worse

yet nobody complains; it is “cool” to support continuations

Ha!

PL Predictions for 2012

2011-12-31T19:50:00.000+01:00

Summary: another year of broken lexical scope and broken type systems.

There will be a new language with broken lexical scope (remember, it's a criterion for success).
A GWT-like, 80's style, object-oriented GUI framework will make Dart a major player in web apps.

Happy new year!

Call-by-push-value

2011-12-21T18:01:00.003+01:00

Call-by-push-value has a seducing PR message: Science is reductionism. Once the fine structure has been exposed, why ignore it?

Unfortunately, I'm too unsophisticated to be able to gain much insight from the CBPV papers. There's an introduction to CBPV for more mortal-like folks. Other material is hard to find.

What caught my eye was the following code sample from Paul Blain Levy's (rhymes with "all plain Stevie") PhD thesis:

thunk(print "hello1"; λz. print "we just popped" z; ...)

So, apparently you can do stuff in a function before you're even taking arguments. Interested!

Maybe one of you can provide more information about this interesting new thing?!

Looking back at predictions for 2011

2011-12-21T17:32:00.003+01:00

Let's take a look at my PL Predictions for 2011:

▶ JSON will be the default format for new internet APIs.

I'm not sure how to corroborate this one, but I think it's true. The most significant piece of evidence I have is that IBM even developed JSONx, a standard for representing JSON as XML.

▶ As more people use JSON, we'll see a XML renaissance, as we - for the first time - discover that XML actually gets some things right.

Didn't really happen, AFAICS. But there's this post: Why XML won’t die: XML vs. JSON for your API which says: "not everything in the world is a programming-language object". +1 to that.

▶ GHC will get typed type-level programming and end this highly embarrassing state of untypedness.

Strike!

▶ We'll have a verified compiler-and-OS toolchain for compiling and running some kinds of apps. It won't be x86-based.

Unfortunately, I didn't really track this issue in 2011. There's SAFE, and maybe the O'Caml folks have something to show.

▶ All kinds of stuff targetting JavaScript.

Yeah, well, that was easy. My favorite is Emscripten.

▶ Split stacks and maybe some scheduler improvements will be shown competitive with green threads in the millions-of-threads!!1! (anti-)scenario.

Nobody did this AFAIK, but I still think it's true. Maybe next year.

▶ some insanely great new PL for 2011

Kernel!

So, although most of the predictions were rather cautious, I'm satisified with the outcome.

what distinguishes a good program from a bad one

2011-12-19T19:04:00.002+01:00

Bugs and Battleships by Edward Z. Yang:

One might even say that the ability to generalize behavior of specific tests to the behavior of the program is precisely what distinguishes a good program from a bad one. A bad program is filled with many, many different cases, all of which must be tested individually in order to achieve assurance.

(HT @dyokomizo)

URLs

2011-12-13T03:58:00.001+01:00

One of my all-time favorite quotes:

Uniform Resource Locator is just the result of squeezing the term object reference through the IETF standardization process.

The extensible way of thinking

2011-11-26T01:18:00.008+01:00

'Twas November, 30 years ago:

Aucbvax.5036
fa.editor-p
utzoo!decvax!ucbvax!editor-people
Mon Nov 9 17:17:40 1981

>From RMS@MIT-AI Mon Nov 9 16:43:23 1981
Union types do not suffice for writing MEMBER.

They may be appear to be sufficient, if you look at a single program rather than at changing the program. But MEMBER is supposed to work on any type which does or EVER WILL exist. It should not be necessary to alter the definition of MEMBER and 69 other functions, or even to recompile them, every time a new type is added.

The only way to avoid this is if the system allows new alternatives to be added to a previously defined union type. And this must have the effect of causing all variables, functions and structures previously declared using the union type to accept the new alternatives, without the user's having to know what variables, functions or structures they are. Then you can define a union type called EVERYTHING and add all new types to that union. But then the system should save you trouble and automatically add all new types to the union EVERYTHING. This is tantamount to permitting you not to declare the type.

External variables are vital for extensible systems. A demonstration of this is in my EMACS paper, AI memo 519a.

Beliefs such as that type declarations are always desirable, and that external variables should be replaced by explicit parameters, and that it is good to control where a function can be called from, are based on a static way of looking at a program. There is only one program being considered, and the goal is to express that one program in the clearest possible manner, making all errors (in other words, all changes!) as difficult as possible. Naturally, mechanisms that incorporate redundancy are used for this.

The extensible way of thinking says that we want to make it as easy as possible to get to as many different useful variations as possible. It is not one program that we want, but options on many programs. Taking this as a goal, one reaches very different conclusions about what is good in a programming language. It looks less like ADA and more like Lisp.

It is no coincidence that "computer scientists" have been using the static view in designing their languages. The research has been sponsored for the sake of military projects for which that viewpoint may be appropriate. But it is not appropriate for other things. An editor designed to be reliable enough to be "man-rated" is a waste of effort; and if this unnecessary feature interferes with extensibility, it is actually harmful.

HT Usenet historian Chris.

Happy Birthday Go

2011-11-11T10:17:00.007+01:00

The Go Programming Language turns two.

I really want to like Go (Commander Pike is one of my heroes, and systems programming currently either means C or a Special Olympics scripting language). But I'm slightly put off by the lack of exceptions, and the seemingly gratuitous concepts offered instead. Does anyone have experience with how this aspect of Go pans out in real world use?

Is JavaScript a Lisp in disguise?

2011-11-10T13:01:00.005+01:00

It is something of a commonplace to say that ~~Horror~~JavaScript is a Lisp or Scheme in disguise.

But that's completely wrong!

Yeah, JavaScript gets closures right, and that has become the yardstick for measuring amateur-designed languages. If you do closures right, your language immediately enters the upper echelons of the language space. Sad, but true.

But in every other respect, JavaScript completely fails the Kool-Aid Lisp Test.

Peruse the good old list of Lisp features.

Rich arithmetic: NO

Multiple values: NO

Macros: NO

Closures: YES
Complex Lambda lists (optional, keyword, rest parameters): NO

Conditions, restarts: NO

Generic functions: MAYBE (through JS's hare-brained "object system")

Programmable parser: NO

But most of all:

THE HALLMARKS OF LISP HAVE ALWAYS BEEN EXTREME FLEXIBILITY AND EXTENSIBILITY, AND A MINIMUM OF NONSENSE THAT GETS IN YOUR WAY.*

JavaScript offers a maximum of nonsense, as amply documented. If you use Perl, you have 2 problems. If you use JavaScript, you have NaN problems.

If you say that JavaScript is a Lisp, you don't know jack about Lisp.

Linkdump

2011-11-09T22:08:00.008+01:00

I'm working on a Ninjas/Nazis/Bavarian Illuminati/Aliens/Werewolves* movie, so I don't have as much time for PL geekery atm. Here are some interesting links I haven't checked out fully yet.

▶ Nested Refinements: A Logic For Duck Typing (via @swannodette)

Programs written in dynamic languages make heavy use of features — run-time type tests, value-indexed dictionaries, polymorphism, and higher-order functions — that are beyond the reach of type systems that employ either purely syntactic or purely semantic reasoning. We present a core calculus, System D, that merges these two modes of reasoning into a single powerful mechanism of nested re- ﬁnement types wherein the typing relation is itself a predicate in the reﬁnement logic. System D coordinates SMT-based logical implication and syntactic subtyping to automatically typecheck sophisticated dynamic language programs. By coupling nested reﬁnements with McCarthy’s theory of ﬁnite maps, System D can precisely reason about the interaction of higher-order functions, polymorphism, and dictionaries. The addition of type predicates to the reﬁnement logic creates a circularity that leads to unique technical challenges in the metatheory, which we solve with a novel stratiﬁcation approach that we use to prove the soundness of System D.

(See also The Shadow Superpower: the $10 trillion global black market is the world's fastest growing economy: "System D is a slang phrase pirated from French-speaking Africa and the Caribbean. The French have a word that they often use to describe particularly effective and motivated people. They call them débrouillards. To say a man is a débrouillard is to tell people how resourceful and ingenious he is.")

▶ Dart Talk @ Stanford (I think this is by Bracha. Haven't checked it out coz it's in some weird Windows format.)

▶ Things SQL needs: MERGE JOIN that would seek (Nice idea about using histograms to speed up index scans. I believe the new App Engine query planner does that or something similar. Also Understanding Histograms in Oracle.)

▶ I'm a big fan of the tagless-final approach! (This comment caught my interest, because it reminds me of Kernel: "everything in the language has to become both directly interpretable and available as an AST".)

▶ New extension to Haskell -- data types and polymorphism at the type level (Ωmega-like.)

▶ Evolution of DDD: CQRS and Event Sourcing (@dyokomizo hyped this weird-sounding stuff in response to Beating the CAP theorem).

(* As Rob Zombie says: "I feel that the Nazi movie is back. Once the trend comes back, the Nazi trends comes back, now you pervert it like crazy and you add werewolves. So, I don't know if we'll ever see that movie, but now is the time. The time is now to strike with this.")

Open, extensible composition models

2011-11-08T17:23:00.010+01:00

Open, extensible composition models by Ian Piumarta.

Did VPRI just enter the FEXPR game?

The evaluator corrects several semantic inadequacies of LISP (described by Stoyan [5]) and is metacircular (written in the language it evaluates). The language provides:
lists and atomic values, including symbols
primitive functions called SUBRs
symbolic functions (closures) called EXPRs
a FIXED object that encapsulates another applicable value and prevents argument evaluation
predicates to discriminate between the above types
built-in SUBRs to access the contents of these values
a way to call the primitive behaviour of a SUBR
a quotation mechanism to prevent evaluation of literals
(my emphasis)

More later. HT @CraigOverend.

Update: Oh, also new: Alan Kay et al.: STEPS Toward Espressive [sic] Programming Systems, 2011 Progress Report HT hack the planet in exile

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

2011-10-29T16:00:00.002+02:00

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?

2011-10-24T20:26:00.006+02:00

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

2011-10-20T22:51:00.000+02:00

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

2011-10-13T22:56:00.005+02:00

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

2011-10-11T22:16:00.001+02:00

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

2011-09-29T12:04:00.003+02:00

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

2011-09-19T22:43:00.003+02:00

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

2011-09-08T17:49:00.009+02:00

A quick update on Kernel buzz:

There are now ~~fourfivesix~~seven implementations of Kernel and Kernel-like languages, in addition to John Shutt's original SINK:

klisp, by Andres Navarro. "written in C99 under the MIT license. It draws heavily from the Lua interpreter source code & file structure"
js-vau, by Tony Garnock-Jones. JavaScript.
vau.rkt, by Tony Garnock-Jones. Racket.
Hummus, by Alex Suraci. Haskell.
Cletus, by Alex Suraci. Atomy.
Schampignon, by me. JavaScript.
Klink, by Tom Breton. C.

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

2011-09-07T01:56:00.004+02:00

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

Oleg cat

2011-09-05T20:36:00.001+02:00

(via Paul)

Mortal combat

2011-09-01T20:50:00.004+02:00

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

2011-09-01T17:28:00.009+02:00

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

2011-08-28T11:25:00.001+02:00

SRII 2011 - Keynote Talk by Alan Kay

2011-08-25T15:40:00.007+02:00

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

2011-08-25T13:46:00.004+02:00

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

2011-08-23T23:16:00.006+02:00

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

2011-08-21T15:02:00.002+02:00

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

2011-08-20T13:25:00.010+02:00

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

2011-08-19T17:18:00.004+02:00

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

2011-08-19T02:36:00.009+02:00

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

2011-08-18T22:31:00.014+02:00

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

2011-08-18T21:35:00.005+02:00

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

2011-08-18T14:47:00.002+02:00

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

2011-08-07T16:48:00.008+02:00

"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

2011-08-06T18:32:00.003+02:00

(click to enlarge; via @hexmanshu)

The meaning of forms in Lisp and Kernel

2011-07-31T23:09:00.010+02:00

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

2011-07-31T17:53:00.003+02:00

(via @zachlendon)

Previously:

Some history

2011-07-31T14:22:00.003+02:00

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

2011-07-30T19:44:00.009+02:00

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...

2011-07-28T18:36:00.007+02:00

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

On the absence of EVAL in ClojureScript

2011-07-21T20:34:00.020+02:00

[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

2011-07-14T22:29:00.005+02:00

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

2011-07-10T16:49:00.002+02:00

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

2011-07-08T16:04:00.007+02:00

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

2011-06-29T19:30:00.001+02:00

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

2011-06-27T18:35:00.003+02:00

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

2011-06-22T07:26:00.006+02:00

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:

David Barbour's soft realtime model

2011-06-16T23:04:00.003+02:00

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

2011-06-12T18:13:00.004+02:00

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

2011-06-10T13:16:00.002+02:00

// 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

2011-06-07T17:37:00.003+02:00

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)

Extreme software

2011-05-28T17:56:00.005+02:00

Some programs are very successful with taking a paradigm to an extreme.

Emacs tries to represent every user interface as text. Even video editing.

Plan 9 tries to use filesystem trees as APIs for all applications and OS services.

It's interesting to abstract insights gained from extreme programs, and modify them.

We can ask: if Emacs is successful using plain text as user interface, what if we use hypertext?

Or: if Plan 9 is successful in using filesystem trees as APIs, what if we use activity streams?

Ouch

2011-05-28T17:15:00.000+02:00

Few companies that installed computers to reduce the employment of clerks have realized their expectations.... They now need more, and more expensive clerks even though they call them "operators" or "programmers."
— Peter F. Drucker

TermKit

2011-05-18T14:12:00.008+02:00

I happen to think that pushing beyond plain text is one of the most important tasks for programmers today, or as Conor McBride put it:

The real modern question for programmers is what we can do, given that we actually have computers. Editors as flexible paper won't cut it.

So of course I like TermKit:

It brings back memories of Apple Dylan:

It's simple: replace plain text files with collections, and lines with objects, and you get Good Things for free!

For example: Scott McKay describes the DEUCE editor:

The editor for FunO's Dylan product -- Deuce -- is the next generation of Zwei in many ways. It has first class polymorphic lines, first class BPs [buffer pointers], and introduces the idea first class "source containers" and "source sections". A buffer is then dynamically composed of "section nodes". This extra generality costs in space (it takes about 2 bytes of storage for every byte in a source file, whereas gnuemacs and the LW editor takes about 1 byte), and it costs a little in performance, but in return it's much easier to build some cool features:

- Multiple fonts and colors fall right out (it took me about 1 day to get this working, and most of the work for fonts was because FunO Dylan doesn't have built-in support for "rich characters", so I had to roll my own).

- Graphics display falls right out (e.g., the display of a buffer can show lines that separate sections, and there is a column of icons that show where breakpoints are set, where there are compiler warnings, etc. Doing both these things took less than 1 day, but a comparable feature in Zwei took a week. I wonder how long it took to do the icons in Lucid's C/C++ environment, whose name I can't recall.)

- "Composite buffers" (buffers built by generating functions such as "callers of 'foo'" or "subclasses of 'window') fall right out of this design, and again, it took less than a day to do this. It took a very talented hacker more than a month to build a comparable (but non-extensible) version in Zwei for an in-house VC system, and it never really worked right.

Of course, the Deuce design was driven by knowing about the sorts of things that gnuemacs and Zwei didn't get right (*). It's so much easier to stand on other people shoulders...

Secret toplevel

2011-05-14T00:06:00.005+02:00

A somewhat arcane aspect of hygienic macro systems is the notion that macro-introduced toplevel identifiers are secret.

An example of this in EdgeLisp:

The macro FOO expands to code that defines a variable X using DEFVAR, and prints its value:

(defmacro foo () #'(progn (defvar x 1) (print x)))

(#' is EdgeLisp's code quotation operator.)

Using the macro has the expected effect:

(foo)

1

But X isn't actually a global variable now:

x

; Condition: The variable x is unbound.

; Restarts:

; 1: #[handler [use-value]]

; 2: #[handler [retry-repl-request]]

; 3: #[handler [abort]]

The name X only makes sense inside the expansion of (foo). Outside, it gets transparently renamed by the hygienic macro system.

(In EdgeLisp, a UUID is attached as color (or hygiene context) to the identifier.)

Why the secrecy of toplevel variables? Well, it's simply an extension of the notion that identifiers that introduce new variable bindings (such as those in a LET) need to be treated specially to prevent unhygienic name clashes between macro- and user-written code. This secrecy completely frees macro writers from having to care about the identifiers they choose.

(Discussion of this topic on the R7RS list: Are generated toplevel definitions secret?)

The why of macros

2011-05-11T00:46:00.002+02:00

Good analysis by Vladimir Sedach:
The entire point of programming is automation. The question that immediately comes to mind after you learn this fact is - why not program a computer to program itself? Macros are a simple mechanism for generating code, in other words, automating programming. [...]

This is also the reason why functional programming languages ignore macros. The people behind them are not interested in programming automation. [Milner] created ML to help automate proofs. The Haskell gang is primarily interested in advancing applied type theory. [...]

Adding macros to ML will have no impact on its usefulness for building theorem provers. You can't make APL or Matlab better languages for working with arrays by adding macros. But as soon as you need to express new domain concepts in a language that does not natively support them, macros become essential to maintaining good, concise code. This IMO is the largest missing piece in most projects based around domain-driven design.

Hygiene in EdgeLisp

2011-05-10T17:15:00.002+02:00

EdgeLisp is chugging along nicely. I'll soon do a proper release.

I just implemented a variant of SRFI 72, that is a hygienic defmacro. (I wrote two articles about SRFI 72: part 1 and part 2).

(defmacro swap (x y)
 #`(let ((tmp ,x))
     (setq ,x ,y)
     (setq ,y tmp)))
nil
(defvar x 1)
1
(defvar tmp 2)
2
(swap x tmp)
1
x
2
tmp
1
(swap tmp x)
1
x
1
tmp
2

Compiling, linking, and loading in EdgeLisp

2011-05-08T19:11:00.008+02:00

EdgeLisp now has first-class object files (called FASL, for Fast-Loadable) and a primitive linker:

Let's compile a FASL from a piece of code:

(defvar fasl (compile #'(print "foo")))
#[fasl [{"execute":"((typeof _lisp_function_print !== \"undefined\" ? _lisp_function_print : lisp_undefined_identifier(\"print\", \"function\", undefined))(null, \"foo\"))"}]]

(Note that EdgeLisp uses #' and #` for code quotation.)

The FASL contains the compiled JavaScript code of the expression (print "foo").

We can load that FASL, which prints foo.

(load fasl)
foo
nil

Let's create a second FASL:

(defvar fasl-2 (compile #'(+ 1 2)))
#[fasl [{"execute":"((typeof _lisp_function_P !== \"undefined\" ? _lisp_function_P : lisp_undefined_identifier(\"+\", \"function\", undefined))(null, (lisp_number(\"+1\")), (lisp_number(\"+2\"))))"}]]

(load fasl-2)
3

Using link we can concatenate the FASLs, combining their effects:

(defvar linked-fasl (link fasl fasl-2))
(load linked-fasl)
foo
3

Compile-time effects

Fasls keep separate the runtime and the compile-time effects of code.

For example, a macro definition returns nil at runtime, and does its work at compile-time (edited for readability):

(compile #'(defmacro foo () #'bar))
#[fasl [

execute:
(typeof _lisp_variable_nil !== "undefined" ? _lisp_variable_nil : lisp_undefined_identifier("nil", "variable", undefined))

compile:

((typeof _lisp_function_Nset_macro_function !== "undefined" ? _lisp_function_Nset_macro_function : lisp_undefined_identifier("%set-macro-function", "function", undefined))(null, "foo", (function(_key_, _lisp_variable_NNform){ lisp_arity_min_max(arguments.length, 2, 2); return (((typeof _lisp_function_Ncompound_apply !== "undefined" ? _lisp_function_Ncompound_apply : lisp_undefined_identifier("%compound-apply", "function", undefined))(null, (function(_key_){ lisp_arity_min_max(arguments.length, 1, 1); return (((new Lisp_identifier_form("bar")))); }), ((typeof _lisp_function_Ncompound_slice !== "undefined" ? _lisp_function_Ncompound_slice : lisp_undefined_identifier("%compound-slice", "function", undefined))(null, (typeof _lisp_variable_NNform !== "undefined" ? _lisp_variable_NNform : lisp_undefined_identifier("%%form", "variable", undefined)), (lisp_number("+1"))))))); }))) ]]

Land of Lisp - The Music Video!

2011-05-05T00:59:00.003+02:00

Minimal and sleek / but still so clever you'll freak.

Via Book Review: Land of LISP, by Conrad Barski via @zooko.

Unlimited number of runtimes

2011-05-04T10:11:00.004+02:00

Because Lisp macros are written in Lisp, there's a runtime at compile-time. (See this previous post for more.)

Some Lisp compilers produce two separate object files for a .lisp file: A FASL file that contains the runtime effects, and a CFASL that contains the compile-time effects (such as macro definitions).

But why stop at two object files? A single file could in fact produce any number of runtimes (FASLs).

One example where this would make sense is documentation: Imagine a DEFDOC macro (for documenting variables), whose effects take place at documentation-time:

(defvar x 1)

(defdoc x "A cool variable.")

DEFDOC registers the documentation string "A cool variable." with X in some table, so that it can be looked up.

The FASL would contain (defvar x 1), and the DFASL would contain (defdoc x "A cool variable.").

Now it's up to the programmer to decide when and if to load the DFASL: in the development environment, one would always load documentation-time, but for a packaged application maybe not. There one would only ship the FASLs, not the CFASLs and DFASLs (unless the application is intended to be programmed by users).

on quotation

2011-04-29T23:44:00.008+02:00

Some über-obvious notes:

Lisp literals (booleans, numbers, strings, ...) are sometimes called self-evaluating or self-quoting objects.

This is important because it brings to mind that other objects don't evaluate to themselves: a symbol evaluates to the value of the variable it names, and a list evaluates to the result of a call.

To actually get hands on a symbol or list, we need to quote it. Literals need no quoting, they're self-quoting.

While unquoted X looks quite similar to quoted 'X, they're utterly different. X stands for read a variable from memory, while 'X stands for construct a symbol object with the name "X" (leaving interning aside).

And that's really the use-mention distinction.

A new Cambrian explosion

2011-04-28T11:25:00.005+02:00

Three areas that seem to be exploding are new programming languages, new databases, and new content-centric networking protocols.

But I think all of these developments will be dwarfed by the emergence of the browser as the unified display substrate and JavaScript as the new instruction set.

The last time we had a similar event was the introduction of the GUI in the 80's/90's: millions of programmers scrambled to write every imaginable application for this new system

But the GUI explosion will be peanuts compared to the browser+JS explosion! Not only are there far more programmers today, they're also all joined by the internet now. And there's ubiquitous view source. Need I say more??

Millions of programmers are scrambling right now to write every imaginable application for the browser+JS.

If you ain't emittin' HTML and JS, you're gonna miss out on this once-in-a-geological-era event!

R7RS discussion warming up

2011-04-28T11:17:00.003+02:00

I would still appreciate pointers as to how to implement this ;-) Anyone can implement Scheme, but only half a dozen people have implemented separate compilation with hygienically introduced toplevel bindings. — Andy Wingo of Guile

For example, '幺' (U+5e7a) has Numeric_Type = 'Numeric', since the character means small or young, so it can sometimes mean 1 in some specific context (for Japanese, probably the only place it means '1' is in some Mah-jong terms.) So, when I'm scanning a string and found that char-numeric? returns #t for a character, and that character happens to '幺' (U+5e7a), and then what I do? It is probably a part of other word so I should treat it as an alphabetic character. And even if I want to make use of it, I need a separate database to look up to know what number '幺' is representing. — Shiro Kawai of Gauche

Taylor Campbell's blag

2011-04-28T03:49:00.009+02:00

Taylor Campbell's blag contains many insightful posts related to programming languages, Scheme in particular.

For example, he clears up my confusion about UNWIND-PROTECT vs Continuations:

The difference [to DYNAMIC-WIND] is in the intent implied by the use
of UNWIND-PROTECT that if control cannot re-enter the protected
extent, the protector can be immediately applied when control exits
the protected extent even if no garbage collection is about
to run finalizers.

Note that one cannot in general reconcile

(1) needing to release the resource immediately after control exits
the extent that uses it, and

(2) enjoying the benefits of powerful control abstractions such as
inversion of control.

However, if (1) is relaxed to

(1') needing to release the resource immediately after control
/returns normally from/ the extent that uses it,

then one can reconcile (1') and (2) by writing

(CALL-WITH-VALUES (LAMBDA () <resource-usage>)
  (LAMBDA RESULTS
    <resource-release>
    (APPLY VALUES RESULTS))), or simply

(BEGIN0 <resource-usage> <resource-release>)

using the common name BEGIN0 for this idiom.  (In Common Lisp, this
is called PROG1.)

(And Dorai Sitaram says: UNWIND-PROTECT "cannot have a canonical, once-and-for-all specification in Scheme, making it important to allow for multiple library solutions".)

What's a condition system and why do you want one?

2011-04-27T22:30:00.024+02:00

This post attempts to explain how Lisp condition systems surpass ordinary exception handling. Condition systems don't unwind the stack by default and thus allow computations to be restarted, which is a useful tool.

Exception handling

try {
  throw new Exception();
catch (Exception e) {
  ... // handler code
}

Everybody knows what this exception handling code in Java does: the THROW searches for a CATCH clause (a handler) that catches subclasses of Exception, unwinds the stack, and calls the handler code with E bound to the exception object.

At the moment the exception is thrown, the stack looks like this:

... // outside stack
TRY/CATCH(Exception e)
... // middle stack
THROW new Exception()

There's an outside stack that doesn't concern us. The middle stack is the stack between the TRY/CATCH and the THROW, which is actually empty in this example, but usually contains a whole lotta function calling going on.

Before the handler is called, the stack is unwound:

... // outside stack
TRY/CATCH(Exception e)
~~... // middle stack~~
~~THROW new Exception()~~

When the handler is called, the stack looks like this:

... // outside stack
TRY/CATCH(Exception e)
... // handler code

Condition systems

Condition systems in the Lisp family are based on the fundamental insight that calling a handler can be decoupled from unwinding the stack.

Imagine the following:

try {
  throw new Exception();
} handle(Exception e) {
  ... // handler code
}

We've added a new keyword to Java, HANDLE. HANDLE is just like CATCH, except that the stack is not unwound when an Exception is thrown.

With this new keyword, the stack looks like this when the handler is called:

... // outside stack
TRY/HANDLE(Exception e)
... // middle stack
THROW new Exception()
... // handler code

The handler runs inside the THROW statement (Common Lisp would say, during the dynamic extent of the THROW).

For many exceptions it makes sense to simply unwind the stack, like ordinary exception handling does. But for some exceptions, we gain a lot of power from the non-unwinding way condition systems enable.

Restarts

One of the most interesting aspects of not automatically unwinding the stack when an exception occurs is that the we can restart the computation that raised an exception.

Let's imagine two primitive API functions: GETVAL and SETVAL read and write a VAL variable.

Object val = null;
Object getVal() { return val; }
void setVal(Object newVal) { val = newVal; }

Now we want to add the contract that GETVAL should never return null. When VAL is NULL, and GETVAL is called then an exception is raised:

Object getVal() {
  if (val == null) throw new NoValException();
  else return val;
}

A user of GETVAL may install a handler like this:

try {
  getVal();
} handle (NoValException e) { // note use of HANDLE, not CATCH
  ... // handler code
}

When GETVAL() is called and VAL is null, an exception is thrown, our handler gets called, and the stack looks like this:

... // outside stack
TRY/HANDLE(NoValException e)
getVal()
THROW new NoValException()
... // handler code

As you can see, our handler for NoValException runs, and the exception "isn't over yet", because the stack hasn't been unwound.

Thanks to the non-unwinding nature of condition systems, an application may decide to simply use a default value, when GETVAL is called and VAL is null.

We do this using restarts, which are simply an idiomatic use of non-unwinding exceptions:⁽¹⁾

We rewrite GETVAL to provide a restart for using a value:

Object getVal() {
  try {
    if (val == null) throw new NoValException();
    else return val;
  } catch (UseValRestart r) {
    return r.getVal();
  }
}

GETVAL can be restarted by throwing a USEVALRESTART whose value will be returned by GETVAL. (Note that we use CATCH and not HANDLE to install the handler for the restart.)

In the application:

try {
  getVal();
} handle (NoValException e) {
  throw new UseValRestart("the default value");
}

(The USEVALRESTART is simply a condition/exception that can be constructed with a value as argument, and offers a single method GETVAL to read that value.)

Now, when GETVAL() is called and VAL is null, the stack looks like this:

... // outside stack
TRY/HANDLE(NoValException e)
getVal()
TRY/CATCH(UseValRestart r) [1]
THROW new NoValException()
THROW new UseValRestart("the default value") [2]

The restart at [2] bubbles up, and is returned by the TRY/CATCH for the restart at [1], which means that GETVAL returns "the default value":

... // outside stack
TRY/HANDLE(NoValException e)
getVal()
TRY/CATCH(UseValRestart r)
~~THROW new NoValException()~~
~~THROW new UseValRestart("the default value")~~
return r.getVal(); // "the default value"

A simple extension would be to offer a restart for letting the user interactively choose a value:

Object getVal() {
  try {
    if (val == null) throw new NoValException();
    else return val;
  } catch (UseValRestart r) {
    return r.getVal();
  } catch (LetUserChooseValRestart r) {
    return showValDialog();
  }
}

This assumes a function SHOWVALDIALOG that interactively asks the user for a value, and returns that value. The application can now decide to use a default value or let the user choose a value.

Summary

The ability to restart a computation is gained by decoupling calling a handler from unwinding the stack.

We have introduced a new keyword HANDLE, that's like CATCH, but doesn't unwind the stack (HANDLE and CATCH are analogous, but not equal, to Common Lisp's handler-bind and handler-case, respectively).

HANDLE is used to act from inside the THROW statement. We have used this to implement restarts, a stylized way to use exceptions.

I hope this post makes clear the difference between ordinary exception handling, and Lisp condition systems, all of which feature restarts in one form or another.

Further reading:

A tale of restarts - comp.lang.dylan message by Chris Double ("This is a "I'm glad I used Dylan" story...")

Exceptional Situations In Lisp and Condition Handling in the Lisp Language Family - increasingly detailed papers by Kent Pitman

Footnotes:

(1) This is inspired by Dylan. Common Lisp actually treats conditions and restarts separately.

Lisp hype danger

2011-04-26T19:14:00.002+02:00

Yesterday, "Lisp was dead".

Today, Lispers are asked to "reproduce their pre-AI Winter achievements" and there's talk of "Lisp geniuses".

I sense danger in the hype cycle!

Hypercode

2011-04-26T13:16:00.005+02:00

I just saw this use of HTML lists and tables for syntax, and I liked it. I think that HTML is the future of all UIs, thus also of PLs.

The possibilities of using HTML instead of plain text are huge, and I wish that the syntax-obsessed would focus on HTML instead of plain text.

Original Dylan Manual

2011-04-25T17:04:00.004+02:00

Thanks to the Wayback Machine, I just discovered the original 1992 Dylan manual: Dylan (TM) -- An object-oriented dynamic language.

Back then, Dylan still had S-expression syntax, making its CL and Scheme heritage much more obvious.

If you want to see dynamic object-oriented PL design (as opposed to trial and error, plucking out of thin air, or other popular approaches) this is one of the few places to look.

(Here's another URL for the manual.)

EdgeLisp progress

2011-04-21T15:04:00.011+02:00

My hobby Lisp->JS compiler, EdgeLisp (formerly known as CyberLisp) just passed a major milestone: using multiple dispatch, a numeric tower (provided by Danny Yoo's js-numbers), and inline JavaScript, I'm able to write the > generic function as follows:

(defgeneric > (a b))
(defmethod > ((a number) (b number))
#{ jsnums.greaterThan(~a, ~b) #})

Checking it out at the REPL:

(> 200000000000000000000000000000000000000000 100000000000000000000000000000000000000000)
#t

Yay!

EdgeLisp is FAR from usable by anyone but me, but at this point I just had to blog about it. You can check it out here if you want.

Disclaimer: docs are outdated, and the project is in rapid flux.

The more I work on this, the more I respect anybody who's produced a usable PL. The sheer amount of work is unbelievable. :)

Props also to Douglas Crockford's json.js and Chris Double's jsparse.

Truth IS stranger than fiction

2011-03-30T11:52:00.004+02:00

An amazing look back at Java's early days, by Chuck McManis on HN:

Tcl was the 'language to beat' amongst the new language products. Self was the 'language like no other' (or a totally new way to express what you wanted to a computer). Java was the 'language that re-used code'. C++ was kind of a joke (remember this was the late 80's, early 90's) since it took a perfectly acceptable language, C, and made writing code harder, more error prone, and less likely to produce correct code (all true at the time).

Tcl was a language of rapid expression and Java was a language which was safer, in part, because it enforced a certain level of correctness (type safety, no pointer arithmetic, Etc.).

Tcl had a "huge" installed base of developers, Java had zero developers and hoped to have 10 or 20K eventually.

Bert Sutherland (the guy running Sun Labs and Ivan's brother) got everyone in a room and said "We're going to have a 'language' day, and each of you gets to present why you think your language should exist." the issue was of course that Sun had only so much budget and we had no business reason for developing any new languages.
Surprisingly to some, Tcl 'won' that evaluation. Self was going to continue because Bill could self fund it if he wanted to, and Tcl had the developer base and momentum. The decision was taken to scrap the remains of the Java team (called the Live Oak project at the time) at the end of the Fiscal Year (June 30th, 1995). We were all set to be 're-deployed' which was Sun code for 'find a new job inside of Sun or we'll lay you off.'

What happened next was unexpected. James Gosling, with Kim Polese's help, had convinced the lawyers to allow us to release the source code for 'free' (very un-Sun like) so that we could at least point at something we had done on our resumes. The requirement was that we have a trademarkable name for it (which I believe was, in part, to prevent Apple or Microsoft from re-publishing it as their own thing). We dropped Alpha 1.1 (we had secretly released Alpha 1.0 in February) on March 23rd. Kim sent out a press release to some folks. (not sure if she used PR Newswire or not) The Mercury News put it on the front page, they got a quote from Marc Andresson over at Netscape that it was cool. When I went to the WWW conference 2.0 (as in second conference :-) in Darmstadt Germany two weeks later, everyone wanted to talk about it. I manually downloaded and installed it on all the Sparcstation 20's that the sales office had brought to the conference and gave a quick set of talking points to the sales guys. When I got back there was a storm because folks like Ed Zander were demanding to know why they hadn't been briefed before we announced it, Phil Sampire(sp?) was complaining that people kept calling the sales office to get their sales droid to come out and talk about it and they had no marketing material and no prep. May press conference was already queued up as the SparcStation 20 / Firewall-One launch event, the SS20 got the boot and they replaced it with the Java 'launch'. I spent a crazy couple of weeks creating a completely Java home page for Sun (had I known it was a portent of all flash sites to come I might have shot myself right then and there :-)

Everyone 'forgot' about how they were going to flush the team and instead everyone came out of the woodwork to claim they had supported it all along, SunSoft, SunLabs, and Sun Interactive (which had the only financial success with it at the time, competing against the Time Warner VOD bids). An entirely new 'planet' was born, called JavaSoft and the rest is history.

What Java gave Sun at that point in time was a credible threat against Microsoft. The threat was that the new desktop was the browser, and the way you coded for the browser was Java. Tcl didn't play in that space, and to their credit I don't think the Tcl folks were willing to go there just to ride the buzz.

Java's wake grew to eclipse the other language efforts and Sun never looked back.

Duke's Law

2011-03-29T19:21:00.004+02:00

Raoul Duke:

As soon as somebody brings in a reference to xah lee, somebody else has to call somebody a Nazi, and then somebody else has to invoke the spirit of john harrop when he was an ocaml instead of F# bigot, etc. etc.

Syntax puns considered harmful (well, not really)

2011-03-29T17:44:00.007+02:00

Schemers use the word "syntax" to mean at least two (and maybe even three) different things:

in DEFINE-SYNTAX and LET-SYNTAX, syntax means macro expander
in SYNTAX and QUASISYNTAX, syntax means code
in BEGIN-FOR-SYNTAX, syntax means compile-time (although it's debatable whether this use of syntax is really different from the first one)

There is a certain elegance in that, but in the end it's also a bit silly.

And it's problematic, as the (awesome) paper Languages as Libraries shows: because LET-SYNTAX is already taken to mean "locally bind a macro expander", they have to use WITH-SYNTAX to mean "locally bind a piece of code".

Don't diss Java - Be Happy

2011-03-28T22:19:00.006+02:00

On the occasion of Gosling joining Google, it's Java diss time again. But most Java criticism doesn't take its raison d'être into account:

We were after the C++ programmers. We managed to drag a lot of them about halfway to Lisp. Aren't you happy? — Guy Steele

Java has many faults. But most of them are there by design. That's not something many language designers can claim.

Java was a Trojan Horse, designed to slip in a modicum of dynamic features without C++'ers getting suspicious.

That whole dynamic-language-in-the-mainstream thing may have never happened without Java.

Aren't you happy?

Computational Trinitarianism

2011-03-28T19:07:00.000+02:00

Given that software is so utterly confusing, it's often helpful to bring in metaphors from other areas, Christianity in this case: The Holy Trinity from Bob Harper's excellent Existential Type:
The Christian doctrine of trinitarianism states that there is one God that is manifest in three persons, the Father, the Son, and the Holy Spirit, who together form the Holy Trinity. The doctrine of computational trinitarianism holds that computation manifests itself in three forms: proofs of propositions, programs of a type, and mappings between structures. These three aspects give rise to three sects of worship: Logic, which gives primacy to proofs and propositions; Languages, which gives primacy to programs and types; Categories, which gives primacy to mappings and structures. The central dogma of computational trinitarianism holds that Logic, Languages, and Categories are but three manifestations of one divine notion of computation. There is no preferred route to enlightenment: each aspect provides insights that comprise the experience of computation in our lives.

OOP, again and again and again

2011-03-28T03:04:00.005+02:00

Nothing gets LtU's juices flowing like a good old OOP discussion. It starts with a harmless "OO is anti-modular? Really?" and runs into the right margin very quickly. It's worth a read.

In that thread there's also a quote describing OOP that's very close to my POV, by Jonathan Aldrich:

building dynamic dispatch into the language ... is the one thing that separates languages commonly considered "OO" from those that are not

Previously: Why are objects so unintuitive.

That explains it

2011-03-07T21:12:00.004+01:00

Kent Pitman:

I certainly sat in lots of Scheme design meetings where I pushed for obvious things like branch cuts, error handling, and other "useful" things and was told that such things would ... make the language "too useful" [thus meaning too many people would flock to it and it would be the end of the designers' ability to do the things to the language that _they_ wanted to do].

Seriously though, this shows that the forces behind Scheme are far from obvious.

Understanding Hygiene (part 2) -- SRFI 72

2011-03-07T19:32:00.017+01:00

My critically acclaimed Understanding Hygiene (part 1) contains the absolute baseline necessary for understanding hygienic macros.

This post is about my understanding of André van Tonder's SRFI 72 - a specific way of implementing hygiene, which differs from more widely used hygienic systems such as the venerable syntax-case.

It must be said that hygiene is still an area of active research. There be dragons. Nevertheless, van Tonder is quite confident of his design, going so far as calling it "improved hygiene". David Herman, who wrote the ~~book~~dissertation on the theory of hygienic macros is skeptical. Anton van Straaten makes some mediatory points. Matthew Flatt raises even more mind-bending questions.

That said, for a hygiene noob like me, SRFI 72 seems to be an elegant and workable design. I wrote a half-assed Lisp->C compiler that contains a SRFI 72 inspired macro system (here's a test from SRFI 72 in my Lisp that works -- phew) and the experience was quite pleasurable. Of the couple thousand lines of C in the system, only a couple dozen or so deal with hygiene.

Basically, what SRFI 72 says is this: when you create a piece of code using the code constructors syntax or quasisyntax, e.g.

(syntax (let ((x 1)) (foo x)))

the identifiers in there (let, x, foo) get a fresh hygiene context (or "color"). Thus they won't conflict with identifiers of another color -- such as those created by somebody else (e.g. another macro, or the user's source). That was the easy part.

Additionally, SRFI 72 makes such pieces of code obey a discipline that is similar to lexical scoping. That is the meaning of 72's money quote that van Tonder repeats multiple times, in the hope of hammering his point home:

the evaluation of any nested, unquoted syntax or quasisyntax forms counts as part of the evaluation of an enclosing quasisyntax.

Say we have some piece of silly code, like:

(quasisyntax (bla bla bla ,(some-unquoted-stuff (lambda () (quasisyntax (bla bla bla))))))

The outer quasisyntax constructs/quotes the piece of code. Then the "," unquotes and we call some contrived function that happens to take a lambda as argument. Then, inside the lambda there's another quasisyntax, so we're quoted again. The contrived unquoted stuff and the lambda don't matter. What matters is that there's an inner quasisyntax lexically embedded in the outer quasisyntax.

Now, SRFI 72's money quote tells us that the inner quasisyntax's bla's have the same color as the outer quasisyntax's bla's. Why? Because the inner quasisyntax is lexically nested in the outer quasisyntax, and like a lexical variable binding, the outer quasisyntax's color is "inherited" down to the inner quasisyntax.

This took me a looooooooooooooooooong while to figure out, and I hope that this post will help those trying to understand SRFI 72.

Questions?

Language design criticism = art criticism (?)

2011-03-01T16:51:00.004+01:00

A comment by Sean McDirmid on LtU is spinning off into a nice PL design discussion:

We should only critique designs like we critique art, I like this and I don't like that, made from the perspective of another person's tastes. C++ is an example of a language that has a controversial rather than poor design, some people find it ugly while others find it beautiful. A good design is simply a language designed by a good designer, and it might not suit your tastes but you should appreciate it for what it is, right?

I got into some arguments recently over Scala. That I was critical of Scala and compared it to C++ led someone to think I was a Scala hater, while nothing could be farther from the truth. People tend to get very emotional about their languages (or paradigm) of choice. A good discussion involves acknowledging our biases and being objective about our and others' opinions.

Applied Types

2011-02-26T12:21:00.002+01:00

Chris Double is again exploring ATS, a language with a very advanced type system:

ATS did save me from some errors in my larger program that this snippet can be used to demonstrate:
The read call must not read more data than the size of the buffer allows.
The conversion to a C string in-place means we need to read one less than the size of the buffer.
The file must be closed after use.
All these issues resulted in compile time errors. [!]

Emscripten

2011-02-24T02:16:00.003+01:00

This is CPython, the standard Python implementation, compiled from C to JavaScript using Emscripten, running in your browser (without any plugins).

Highly sick.

Emscripten is an LLVM-to-JavaScript compiler. It takes LLVM bitcode (which can be generated from C/C++, using llvm-gcc or clang, or any other language that can be converted into LLVM) and compiles that into JavaScript, which can be run on the web (or anywhere else JavaScript can run).

[So will we run Emacs in X11 in the browser??]

Wittgenstein for programmers

2011-02-19T23:29:00.004+01:00

Harrison Ainsworth's Wittgenstein for programmers is an awesome project. And very quotable:

Where a proposition describes the world, a program constructs the imagination.
The limits of our programming-languages mean the limits of our imagination.
What can be designed at all can be designed precisely. What is unknown we must leave uncoded.

Browsers will let PLs break free from plain text

2011-02-19T23:18:00.005+01:00

Programs really aren't plain text. Or they shouldn't be.

But until now there was no way out. OSes come with Ed, and Ed is the standard text editor.

But pretty soon, we'll want to do development in our browsers.

Do we really want to port our 1960's plain text infrastructure to browsers? Surely the answer must be a resounding ``No!''

Reinventing integrated development environments in the browser will make it possible to ditch plain text, and switch to the multimedial representations our programs deserve.

Finally.

Free as in Freedom

2011-02-16T21:58:00.002+01:00

Vladimir Sedach just tweeted something dear to my heart:

Arguing that the #GPL is restricting your freedom is exactly the same as arguing that the 13th Amendment is restricting your freedom.

Go GNU!

BTW, I'm now also a twit at @msimoni and like to get in touch with all PL enthusiasts out there!

Dear Lazyweb: RMS on namespace management

2011-02-16T16:26:00.006+01:00

I remember reading an article about RMS some time ago, where he says that a module system/namespace management for Emacs Lisp is not something he finds important.

I find this interesting because Linus essentially said the same thing wrt C.

If you know which article this is, please be so kind and post it in the comments, or send me a mail. Thanks!

(Edit: See also How important is language support for namespace management? on LtU.)

The LISP עץ החיים

2011-01-28T13:30:00.004+01:00

Plain awesome!

(cached copy in case the original site goes down)

Proglangs are machines, not media

2011-01-26T14:07:00.007+01:00

I've blogged about this before, but I think it's worth stressing again:

Programming languages should not be viewed as media, but as machines.

I first had this intuition when learning Common Lisp: CL is like a big program (i.e. an object, a machine), that's configured and used through Lisp code.

This has the nice side-effect of vindicating Lisp's built-in uglyness: who cares what a machine looks like, as long as it's the best for the job?

(Thanks to Harrison Ainsworth for the initial inspiration.)

[Edit: Ah well, I guess I pushed the publish button too quick. Of course, PLs are media. But that's obvious. I think it's important to also look at their object, machine aspects.]

Maniacal, religious dedication to code beauty

2011-01-23T17:46:00.002+01:00

It's hard to keep source code "beautiful".

I think the only way it can work is to be dedicated like Zen monks cleaning their monastery - even one speck of dreck is too much.

The best example I know is Jonathan Bachrach's GOO (which also has a lot of other qualities). The code in there is phenomenally clean and consistent, and looks funny and artful to boot.

The dark, dark, dark art of unwinding the stack

2011-01-20T23:29:00.002+01:00

Ian Lance Taylor, the author of the gold linker and the GCC version of the Go language, has written a nice mini-series on how to unwind the stack:

This is wizard-level material, and it probably helps to have the ELF and DWARF specs handy.

A Lisp slogan

2011-01-09T13:02:00.001+01:00

Lisp is the worst programming language, except all the others that have been tried.

Curing PL Anxiety

2011-01-06T13:47:00.007+01:00

Some years ago I was in a state that I now discover in many other people on the web, and which I term "PL anxiety". It is characterized by a constant insecurity about which PL is the best, which one to learn, how "fast" each one is, whether PG is really right, etc etc.

In retrospective, my way out of this was a four-pronged approach:

(1) The Breadwinner PL

You should know one language that's reasonably popular where you live, and which will always land you a job. In the past that meant C++, C, Java, C#, and maybe Perl and PHP, but these days you can probably also get away with Python, Ruby, JavaScript, or Scala.

What's important about the breadwinner PL is that you know its semantics and its standard library by heart.

(2) The C PL

Infinitely many good things come to you by learning C, because your OS is written in it. Studying C, you'll learn awesome stuff, like how to handle SIGSEGV, exploit your branch predictor, write a language runtime, and what a linker is, for example.

The more you learn about C, the more you'll learn about a wide array of services that are already provided to you by your OS and compiler. And C is fun and simple to boot, and will give you the warm fuzzy feeling that comes from building things (almost) from the ground up.

(3) The Romantic PLs

These are languages that you really like and if you're really lucky, might one day get paid for using. You don't have to make a choice - learn them all. They all have their pros and cons, and in the end you'll have to roll your own, anyhow.

(4) The Other Interesting PLs Out There

Also keep an eye on olden golden PLs and newcomers to the scene, even if you're never going to use them: they may blow your mind, and that's what you really should be looking for. Ωmega is a good example.

The Real World

I've come to start new non-hobby projects in my breadwinner language, because it's the most convenient, I know it by heart, all my problems have already been encountered and hopefully solved by somebody else, there are tons of libraries, and PLs seem to matter very little for many projects (and if they matter, you can always Greenspun it).

Motivation

The thing that keeps me motivated learning more about PLs are PLs themselves. I learned C writing Lisp->C compilers, for example. I'm learning about dependent types because I'd like to implement a PL that has them. It's weird, but works for me.

HTH.

On Python and Ruby

2011-01-06T12:55:00.002+01:00

I often like to make snide remarks at Python and Ruby, because ... well, because they're not Lisp.

To offset this a bit I'd like to say what I find good and impressive about them:

Python seems to be a great language for describing algorithms. For example, Kragen's hacks abound with samples of Python code that is simply wonderful to read, and seems like exactly the way to go.

Ruby is to be congratulated for demonstrating once and for all that dynamically-typed, semi-functional, object-oriented programming is a fun and useful paradigm for systems scripting.

Why Lisp is a Big Hack (And Haskell is Doomed to Succeed)

2011-01-02T16:09:00.018+01:00

Note: This post presents my thinking as of the time it was written. Presently, I may be thinking something else entirely.

I fear that Haskell is doomed to succeed. — Tony Hoare

I ♥ Lisp. I think it's the best tool we have, at the moment, for many applications.

I don't really love Haskell that much, but I track its progress with awe. (When I say Haskell, I'm not only speaking about Haskell per se, but also about all the FP languages in its halo, like Ωmega, Agda, Epigram, ...)

And when I look at Haskell, it seems obvious to me that it's out to eat Lisp's lunch. In fact, eat all other languages' lunches.

The gist of this post is: In the not-so-far future, Haskell will be able to do everything Lisp can do now (and more), but in an adjustably-safe, statically-verified manner.

What do I mean by that?

Adjustably-safe: In this mythical, not yet-existing, but clearly on-the-horizon "Haskell", you'll be able to choose how much safety you want. You'll have "knobs" for increasing or decreasing compile-time checks for any property and invariant you desire. Or don't desire. You'll be able to switch between Lisp-style dynamic typing, Haskell-style static typing, and probably even C-style weak/no-typing. In the same program.

Statically-verified: Haskell is clearly moving towards dependent typing, which in theory, allows the expression of arbitrary invariants that are maintained statically, without having to run the program. Dependent typing is the weirdest and most awesome thing to expect of programming, this side of quantum computers.

Lisp, as it stands, can't do any of that, and won't be able to do any of that. That's simply a fact. Why? Because it's coming at the problem from the wrong direction. Trying to graft an interesting type system or verification onto Lisp is simply too heroic and ill-specified a task. Lisp starts with ultimate freedom/unsafety, and you can't constrain it. Haskell starts with ultimate bondage/safety, and then, piece by piece, adds that freedom back. On a theoretically well-founded basis.

Right now, Lisp has certain advantages. As a command or scripting language where ultimate dynamism is desired (Emacs), it's still clearly superior. But Haskell is encroaching on its habitat from all sides, just like it's encroaching on the habitats of all other languages. Right now it may appear pointy-headed and harmless. But I think it's unstoppable, and doomed to succeed.

How does that make Lisp a big hack? If my theory is right, then once Haskell will be able to do everything Lisp can do now (and more), all the while maintaining adjustable safety and static verification, I think it will be justified to call Lisp a big hack - because it lacks the possibility of this safety and verification, in principle. (Of course you have to subscribe to the idea that this safety and verification is something that's good and superior. I do.)

(HN, Reddit)