Yet another Kernel interpreter

I wrote another Kernel-ish interpreter in JavaScript: Virtua.

This time, no tail-call optimization or first-class continuations, just plain old pedestrian control flow: LOOP, CATCH, THROW, UNWIND-PROTECT (unexpectedly, this didn't make the interpreter much smaller than the one with TCO and continuations.)

Probably the only interesting thing in there is that everything is fully OOP: EVAL is a message, as is COMBINE, as is MATCH - which means every object can potentially control its own evaluation, act as a combiner, and be used as a left-hand-side pattern in matching.

Again: Kernel is nice and elegant, but the interpretetive overhead of fexprs is killer [Edit: haven't measured it, and see this]. Maybe it doesn't matter for what I want to do: script web GUIs.

Previously: The Kernel Underground.

Algebraic Data Types

Reading this incredibly insightful article The Algebra of Data, and the Calculus of Mutation finally drove home the point to me why FP folks are so in love with their Algebraic Data Types: they connect wonderfully with very old (think B.C.) mathematical ideas - that every one of us has learned in school. The question is still whether that does make them good for programming. (HT Daniel)

Fun with Kernel

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

• Fexpr the Ultimate Lambda
• Semantic Extensibility with Vau
• Mutable Objects in Kernel
• Implementing Actors in 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

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

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

But there are two problems with the cloud:

1. Technical: doing stuff in centralized data centers, when all of your users have multiple, hugely overprovisioned computing devices is a bit of a joke.
2. 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

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

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...') and Rainer Joswig's post on LtU ("I would not want to live without that feature.").

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

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

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?

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

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

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

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

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

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

'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

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?

It is something of a commonplace to say that HorrorJavaScript 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

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- finement types wherein the typing relation is itself a predicate in the refinement logic. System D coordinates SMT-based logical implication and syntactic subtyping to automatically typecheck sophisticated dynamic language programs. By coupling nested refinements with McCarthy’s theory of finite maps, System D can precisely reason about the interaction of higher-order functions, polymorphism, and dictionaries. The addition of type predicates to the refinement logic creates a circularity that leads to unique technical challenges in the metatheory, which we solve with a novel stratification 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

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

The post on Dennis Ritchie by Herb Sutter is wonderful:

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

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

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

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

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

Thanks, Dennis.

Toolstrapping is everywhere - can you see it?

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

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

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

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

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

It's called programming

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