Lambda the Ultimate

FWIW I added a bonafide implementation of variant types in version III-2.0586 (i.e. about a year ago), complete with pattern matching and exhaustivity checking for match statements. Variants are implemented underneath the hood as objects allocated on the heap, but they don't have semantically visible identity; equality is checked with deep comparison. This makes an optimized implementation of variants with bit-packed value representations completely transparent.

One more polite way to formulate my disagreement, that I should have thought about first, is the following. Your masquerade of variant types does not feel convincing because the other feature "emulations" you present *are much better*. Your emulation of Abstract Data Types is very good: I can see myself using that and thinking in terms of type abstraction (a related point was made in the CTM book about the Oz language). Interface Adapters are also quite believable. Ad-Hoc polymorphism is a bit cringey, but ad-hoc polymorphism generally is anyway. The variant types are ill-served by this contrast: I don't think they work, while the other *do*, so by this point of your article I was used to "surprisingly good" emulations.

In my experience, a good exhaustivity check is "orders of magnitude" more helpful for programmer productivity (both in writing bug-free code *and* in refactoring code afterwards) than any kind of extensibility of variants that will be used in much rarer cases -- it's still useful, but not in the same league.

My understanding (but Ben can correct me) is that Virgil is not a "Google language", it's just a language that happens to be created by someone who works for Google.

Factor and Magpie (mine) are other languages that are created by Googlers but aren't from Google itself. Google just happens to be quite friendly towards extra-curricular projects.

Given that Google has many PL PhDs and other enthusiasts, not all of them are working on language design as their full time job. Affiliation listed on a paper then becomes a bit weird, but not by much.

Reality is, there are few--probably zero--places in the world that are going to pay you to design your own language for your own purpose. So one has to make some compromises; maybe work on another language project that is close to your ideas, maybe contribute some language ideas to an existing language, maybe work on a different system in a different area of CS altogether. I think doing some of each of these is instructive. One needs some exposure to real-world problems and to see how languages fail. If you can palate the ickiness of writing, maintaining, debugging, or extending a mountain of Java or C++ code, there are a lot more job prospects, and some of that experience may transfer into the language.

I chose to work on a non-PL project starting off at Google and spent 3 years there. It gave me a perspective on debugging and logging in the large that I don't think I would have gotten elsewhere. Now I'm on the V8 team, and I'm happy to work on compilers as my FTJ, even if both the implementation language (C++) and the target language (Javascript) are both losers. There are other language projects around at Google, but I'm happy to keep chugging along in this PL direction.

Reality is, there are few--probably zero--places in the world that are going to pay you to design your own language for your own purpose.

Well I got lucky, and it helps to be in research (vs. the Google PhD super-dev). Unfortunately, such jobs are just becoming more rare.

Reality is, there are few--probably zero--places in the world that are going to pay you to design your own language for your own purpose [all of the time].

The more classic compromise is life as an academic: teaching and managing research in trade for time to pursue personal projects. But the ratio of graduating PhDs to available positions seems to tend towards zero over time. Oddly enough the trade-offs inside the ivory tower are remarkably similar: contributing techniques to projects in related areas / seeing completely different areas of CS. They also bring the same benefits in terms of cross pollination.

It gave me a perspective on debugging and logging in the large that I don't think I would have gotten elsewhere.

You are in a place that seems uniquely suited to that experience (thinking back to Matt Welsh's blog posts). Speaking of which, your paper looks interesting so it's landed on the "to read" pile. Hopefully I will have some more on-topic comments later. After a quick look though I do already have a naive question to ask: about 70% of the material covers a description of novel aspects of the language, less than 30% evaluates the impact of those aspects. The evaluation is in the form of analytic discussion rather than empirical results.

Although that split seems pretty standard for a paper introducing a novel language, it leaves me curious: how much is that split a result of the way that you wanted to write the paper, and how much is an artifact of writing it in a way that will get it published? In particular, what kinds of useful knowledge arise from looking at large-scale uses of an existing language that are difficult to communicate / shoe-horn in the standard template for a research paper.

Empiric evaluation would be nice, but unfortunately, nobody knows how to empirically evaluate programming languages in a way that (1) is not limited to trivialities (like surface syntax), (2) properly eliminates the gazillion of irrelevant variables (like bias from predominant practice), and (3) is practical.

Are you sure that is actually a conjunction and not a disjunction?

Empirical evaluation does seem to be difficult, and the relative lack of results that I've seen is the main motivation for asking. The difficulty seems to be related to the type of question / property that is being evaluated. As in any other field, trying to evaluate a poorly chosen property will lead to weak results. Some poor examples that have been tried include:

* does language X make a programmer more productive (specifying which programmer is one of the gazillion variables)?
* does language X make code better (specifying better hits both problems (2) and (3) at once)?

Some good examples (off the top of my head as skimming the last couple of years of PLDI will take too long):

* does language X permit efficient compilation?
* does language X lead to a tractable analysis of Y?
* how compact is language X, i.e. given common idiom Y how many ways can it be expressed (the Python criteria)?
* can we reduce the language size by simulating feature X with feature Y (attempting to veer ever so slightly back on topic)?

In general "weaker" results are easier than "stronger" results, i.e. does there exist a program in language X with property Y rather than does every program in language X meet property Y. But those weaker results can still be evaluated empirically, I believe that your problems apply more to stronger results.

I'm still curious though - let's say that you were in a position where you had a large corpus of test programs, like .... all the javascript that V8 runs on. What kind of empirical experiments are enabled by a corpus of that size? Can you treat it as a representative sample of programs (yes, stepping over the statistical can of worms for that term) and do things that are not possible just using a handful of handcrafted examples?

Some good examples (off the top of my head as skimming the last couple of years of PLDI will take too long):

* does language X permit efficient compilation?

That's more an evaluation of compiler technology than language design.

* does language X lead to a tractable analysis of Y?

Not sure what you mean by that, or how to evaluate it empirically.

* how compact is language X, i.e. given common idiom Y how many ways can it be expressed (the Python criteria)?
* can we reduce the language size by simulating feature X with feature Y (attempting to veer ever so slightly back on topic)?

These are both questions about orthogonality. It's a good criterium, but one that you have to evaluate through analysis, not empirically.

I'm still curious though - let's say that you were in a position where you had a large corpus of test programs, like .... all the javascript that V8 runs on. What kind of empirical experiments are enabled by a corpus of that size? Can you treat it as a representative sample of programs (yes, stepping over the statistical can of worms for that term) and do things that are not possible just using a handful of handcrafted examples?

There may be interesting phenomena to observe that way (although I'm skeptical that it can give you more than vague data points). But such an analysis is impossible for a new language. And certainly, anything along these lines is far outside the scope of a paper about such a topic anyway, wouldn't you agree?

The empirical equivalent of those analytical questions is, "how easily does a person learn how to do X?" ie.

* does language X permit efficient compilation?

becomes:

* how easily does a new developer learn how to express efficient programs in language X?

It's not clear that analytical simplicity always translates into end-user understandability.

* does language X lead to a tractable analysis of Y?
Not sure what you mean by that, or how to evaluate it empirically.

Sadly I didn't see that the word property was missing on a proofread. What I had in mind was static analysis, but I see that Ray has covered that issue far more comprehensively below when discussing safety.

It's a good criterium, but one that you have to evaluate through analysis, not empirically.

Not necessarily... an explanation requires some fluffy handwaving here to construct an argument. By idiom I mean a common technique for implementing something (or other). Analysis of how many ways that can be expressed in a Turing Complete language will be infeasible. But there is a coarse approximation that would be applying a brute-force enumeration counting the ways using n-symbols. Of course this is still not accurate as deciding if the string of n-symbols implements the given idiom would still be intractable, but assume some approximation is chosen and the result evaluated.

Would that be an analytic result, or an empirical experiment? My interest is essentially in where we draw the line between empiricism and analysis in a field that consists mainly in symbol manipulation. But, apologies to Ben as I was initially curious about this issue in the context of evaluating Virgil, but I've clearly wandered quite far on a tangent so I think I will stop here.

How should we evaluate programming languages and research on programming languages?

...and I don't have a good answer either. :(

Empirical evaluations have value, but are not in themselves the kind of evaluations that we as human beings are likely to be satisfied with.

An empirical evaluation would ask the same series of specific questions about every programming language, and restrict itself to questions that can be unambiguously answered. That would mean things that can be known or counted or measured.

For example, if we wanted to evaluate "expressiveness" we would be asking a long series of specific questions about whether particular constructions from other languages can be expressed with strictly local transformations (where 'strictly local' has a specific meaning such as 'with an isomorphic Abstract Syntax Tree') and if not, whether it is possible to define routines/transformers elsewhere that make such local transformations possible.

Similarly, we could evaluate "safety" with a long series of specific questions about what if anything we are able to prove in advance of running the program or in advance of running particular parts of the program, whether runtime data can undefine/redefine runtime semantics such as procedure calls/returns (cf. stack stomping and execution of stack-allocated or malloc'd buffers), whether 'junk' data is ever visible in the values of uninitialized variables, whether writes to arrays are bounds checked, etc.

But that series of answers, however valuable it may be, is never going to satisfy people. Certain kinds of 'expressiveness' actively limit 'safety' for example, and people will prefer one over the other to different degrees. If you assign an aggregate score for either quality or both based on some scoring algorithm, the scoring algorithm itself is necessarily something that people can disagree about. IE, given the algorithm and the answers to the empirical questions, you can empirically determine the score, but there is no set of facts from which you can empirically determine a 'best' scoring algorithm.

seems like yes i'd like to be able to have the raw #s for languages, and then people can just say, personally i like scoring more for expressiveness than safety, and i can say i'm the other way 'round a little bit.

at the moment, most people talk about programming languages w/out talking about these concepts for the most part; most programmers don't have the words or training or learning or experience to talk about things in such ways, leading to lame flame wars, and excessive use of python (shudder).

Sure, we could ask a series of questions about what properties the language has--how easy it is to implement that is or that anticipated (i.e. step 0) feature or pattern or construct. That is only an interesting question up to a point. At some point after that, the inductive features of the language must take over. We cannot possibly imagine all possible programs or all possible patterns, therefore we must be able to design languages that have positive combinatoric properties. Languages must have building blocks that can be fit together in new and interesting ways. Rough edges make combining constructs harder.

That is one of the ideas I am trying to explore here.

Unfortunately, even if we were able to talk about empirically evaluating the step 0 constructs, an empirical evaluation of the combinatoric properties of a language seems even harder! After all, there is no way to say what combinations are the most useful or the most likely to be used ahead of time. We can only talk about and show examples of how a language is modular and constructive in this fashion.

This is what I tried to do in this paper--as honestly and as straightforwardly as possible. There are tradeoffs when going for combinatorics versus breadth in features.

To the point of evaluation. Originally I tried to publish a version of this paper that contained benchmark results showing that Virgil is competitive in performance (even superior in some cases) with other languages like Java and C#, as well as benchmarks that showed that the normalization (flattening) of tuples makes a huge difference in performance, an implementation choice that, while technically orthogonal from the design aspect of integrating tuples and functions, is of enormous practical importance, since I believe that slow language constructs breed some distrust in programmers and lead them to handicap themselves when approaching design problems. The feedback I got from program committees is that an experimental results section is a wondrously entertaining and contentious bikeshedding experiment and a complete distraction from the design contributions of a paper. It is an easy way to earn a rejection from a disgruntled PC member in the name of "high standards". Experimental results sections rarely please all reviewers. In response I ripped it out; in a strange way it led to the purer, cleaner, benchmark-free version of the paper given here. Not that I wouldn't enjoy writing up some detailed performance comparisons of Virgil versus other languages. But that is another day....

ppig is concerned with such questions.

so F# isn't what C# shoulda been? :-(

No, too much syntactic departure from the C tradition. C# was supposed to be a better Java. It is in many respects, but Virgil is better than both.

I always thought Nemerle was what C# should have been.

Not too mention the quality of engineering of the Nemerle compiler meets or exceeds that of any other Microsoft compiler; they found tons of bugs in MSIL and .NET's CLR generics implementation. This is likely due to the fact that Nemerle is actually a very small core, and much of the language functionality is actually done in macros as part of the standard library. For example, C# added async/await as language features, whereas Nemerle simply wrote some macros.

That might have been true of early Nemerle when they still primarily used the C syntax and before they introduced the powerful macro facilities, but it's grown into too radical a change from the existing C/Java tradition. Been awhile since I looked at it too closely though. Perhaps it's time for another look!

People are way too enamored with LINQ, but people have to do all kinds of stuff to actually get any "call by intention" to work correctly. For example, Linqkit and calling AsExpandable() and Invoke() and Expand(). A proper DSL crafted solely for the context of SQL Generation would hide these abstractions for the user. C# designers did not think of that, and as a result we have an ugly DSL. Anybody who tells you LINQ is nice is an idiot who is wow'ed by a simple demo.

Nemerle is better than Virgil, although F# with full code quotations is much nicer even yet, because it hides all the plumbing Nemerle exposes as macros.

Also, not sure when they introduced macros, but Nemerle had macros and fairly expressive generics in 2008.

To your point about casting values, I am surprised you did not mention infoof, the property equivalent to typeof. In either event, infoof is trivial in Nemerle, it's simply a macro.

The other, broader issue, is that MSIL was never designed for these sorts of embedded languages, that's why we even have expression trees in the first place, because there is no duality between the language we program and and the byte code we execute, so we need to manually quote our code. F# manages to hide a remarkable amount of this mess, but they do so by creating a peer API Expr and map Expr to Expression Trees, so that they can get the advantage of expressing ASTs as discriminated unions. But, of course, F# could be better here, since it doesn't have an elegant solution for the expression problem.

At the same time, MSIL gets further hacked up. Rather than genuinely supporting infoof, we get hacks like CallerMemberName. Who thinks up dumb stuff like that? Same people who thought the DLR was elegant, I assume. Meanwhile, .NET framework guys do everything they can to avoid putting in runtime features to improve the experience for F# users, such as CallerMemberName rather than improving the allocator for functional languages.

People are way too enamored with LINQ [...] C# designers did not think of that, and as a result we have an ugly DSL.

It depends what you mean by LINQ. It's a fairly overloaded term now, but the IEnumerable LINQ extensions are quite good. The integration of quasi-quotation in the form of LINQ expressions are also nice. The query syntax was unnecessary, although I'll admit it's been convenient to have in a few cases. Complex grouping queries are much simpler to read in the flat query syntax than in the method-chained syntax.

Certainly C# has annoying corner cases even in LINQ, but I don't think you can deny that it's miles better than what's available in other major C tradition languages.

As for how Nemerle compares against Virgil, certainly Nemerle is more featureful, but it's not easy to see what the core Nemerle language really is due to the macro magic. Virgil's language is relatively simple and expressive given the description in this paper. In perusing Nemerle's standard library, it doesn't even look like polymorphic Nemerle classes compile to generic CLR classes, ie. all collections under Nemerle.Collections accept and return System.Object. That's certainly not what I'd expect a serious CLR language to generate.

I think LINQ is a cool idea, but it always bothered me that to make the implementation sufficiently extensible and flexible enough to support SQL backends, expression trees were necessary. This adds a whole meta-language to the language that wasn't there before. Perhaps C# would have been cleaner if it did have a meta-language from the beginning, but bolting one on the side always seems like a bit of a hack. From what I understand of the common backends for LINQ, I don't think they they make that much use of the expression trees in any case, so it seems like a lot of complexity pushing in the wrong direction.

Relational and mainstream languages are headed for a collision in the coming years. Too much real-world work deals with reading, writing, querying, copying, and otherwise tending to persistent data stores. If the right concurrency models can be made to fit, and the right consistency dimensions carefully added to the language, it will make a huge difference in productivity for the average programmer stuck with some SQL or NoSQL datastore that they are currently clumsily hacking on in the language du jour. This is coming from my experience working with object/relational mappings in Java with both a SQL db and a No-SQLish db.

I think LINQ is a cool idea, but it always bothered me that to make the implementation sufficiently extensible and flexible enough to support SQL backends, expression trees were necessary.

I agree. They should have just abstracted values via the finally tagless pattern, then provided an interpreter for so-called "LINQ to objects/XML", and a translator for "LINQ to SQL". Unfortunately, due to the absence of higher kinds, this pattern is clumsy at best in C#.

Relational and mainstream languages are headed for a collision in the coming years. Too much real-world work deals with reading, writing, querying, copying, and otherwise tending to persistent data stores.

I'm struggling with this now in fact. You really want a uniform API for orthogonal persistence that supports direct object access and iteration, but none of the options seem viable.

Querying, filtering, ordering is nice in LINQ to objects, but it lacks an API for updating and deletion. You could just use raw collections, but this doesn't really allow for efficient lazy loading from the persistent store.

Supporting an expression tree API like LINQ to SQL is possible, but far less efficient when the objects happen to be in memory since you have to interpret or compile the expression.

I think ultimately the only orthogonal persistence for current platforms like the CLR, will end up being a specialized collection, probably a cache-oblivious b-tree, that exposes a LINQ expression API with update and delete. A "fluent" query API might be possible as well, but I haven't seen a particularly satisfactory one yet.

The paper you link to was published when LINQ already had community tech previews.

My rant is more about false promises, rather than what they should have done. Don't promise what you can't deliver. Consider that LINQ was meant to unify many stories, such as those that were covered by DataTable. This objective clearly failed, as there is no way to directly represent PIVOT and UNPIVOT in LINQ, you have to resort to a GroupBy encoding and you have to know the targets (for PIVOT and/or UNPIVOT) ahead of time. (Granted, with enough reflection, you could do this, but it completely defeats the objectives of writing LINQ rather than generating it.) DataTable did not have this limitation.

tl;dr: Embedded reporting sucks, and computer scientists don't know what to do about it.

I think ultimately the only orthogonal persistence for current platforms like the CLR, will end up being a specialized collection, probably a cache-oblivious b-tree, that exposes a LINQ expression API with update and delete. A "fluent" query API might be possible as well, but I haven't seen a particularly satisfactory one yet.

I have no idea why these implementation details matter. A data structure that exposes a LINQ API? I tried reading this several times, and am sure I have no idea what you are suggesting. Please break it down for me.

I mean simply what Ben said, re: programs need to query, filter and update data, and LINQ is a decent API for doing so. However, no existing data structure available for .NET supports the necessary semantics for all such programs, ie. an object may contain an enumerable set of some sort, but this set can't scale to arbitrary sizes without exhausting main memory, or be queried efficiently at such sizes using the IEnumerable LINQ API.

To resolve this, developers must connect to a specialized storage manager which introduces an explicit partition, like LINQ to SQL did with EntitySet and EntityRef, thus complicating reasoning about such programs.

Instead, why not take the object database concept to its logical extreme and simply make such sets a cache-oblivious search tree of some sort, thus supporting arbitrary sizes, a structure that supports constructing relatively efficient queries, and asymptotically optimal block transfers for data being actively accessed, all without leaving a language's object model. If you're familiar with Waterken, basically the approach taken in it's object store, but add efficient querying via a LINQ API.

I agree that big data makes reasoning about bulk updates difficult. I am doubtful "simply make such sets a cache-oblivious search tree of some sort" is the answer for all applications.

I am not familiar with Waterken in detail, only at a superficially high level. Perhaps my only excuse for doubting you is ignorance. I will check it out, thanks.

Lambdas soon, hopefully! Halfway there, and not mentioned in the paper, Virgil also has partial application with a syntax similar to Scala:

var f = o.m(x, _, z);

which is covered in the tutorial. I also have plans to beef up pattern matching both for type queries and proper sum types. I think these will make some pretty nice upgrades to the core without upsetting the balance of other features.

Virgil also has partial application with a syntax similar to Scala

I'm not sure I like this approach. I find reading Scala difficult because of this sometimes. I generally think lambda syntax should be so concise as to not need such a shorthand.

How is this resolved:

var f = o.m(x, _, z)(_, 3);

Is f a single-arg function itself performing a partial application that returns a single-arg function, or is f a two-arg function?

If we assume

class C {
  def m(x: int, y: int, z: int) -> int;
}
var o = C.new();

Then:

var f = o.m(x, _, z)(_, 3);

t1 = o.m // a closure of type (int, int, int) -> int, with o bound as the receiver

t2 = t1(x, _, z) // a closure of type int -> int, with x and z bound as paramters 1 and 3

t2(_, 3) // type error because t2 is of type int -> int

I think the nice way to make this feature work well is to have an explicit marker of where the lambda-abstraction floats to. When I implemented it as a syntax extension for OCaml, I used \( ... ) : parentheses with a backslash to indicate the abstraction site. There is then no question of what m.f(x, _) means as opposed to list.map(x + _): you use either \m.f(x, _) or list.map \(x + _).

In Virgil it is always clear where the abstraction occurs, because _ can only be used in place of an argument to an actual application, never to an infix operator or other expression. To do list.map(x + _) you would write list.map(int.+(x, _)). Anything more complicated would need a lambda.

t2(_, 3) // type error because t2 is of type int -> int

I should have been more clear. I hoped my description would convey that o.m returns a two-parameter first-class function, so you have two partial applications, and I wanted to know whether the expression I provided abstracts both calls at once, thus yielding a two-parameter tupled lambda, or only one at a time, thus yielding a two-parameter curried lambda. The former seems more in line with Virgil's philosophy, but I suspect the latter. This ambiguity is why I don't like _ on its own.

gasche described one possible way to disambiguate, although I still prefer being even slightly more explicit with lambdas. C#'s lambda syntax is sufficiently concise that I very rarely curse it. When I do, it's either some limitation with type inference, or I'm simply cursing all the N-ary overloads I have to generate, a problem Virgil thankfully avoids.

Ah. I see your question now, and I hope my example makes the rules clear. I didn't design for the case you describe because I think that reasoning about expressions should be local, regardless of partial applications. Thus we can have a simple rule:

For any application of m: (A, B, C) -> D

m(x, y, z)

A partial application:

m(x, _, z)

has type B -> D

We can then proceded from the left to right evaluation rules to understand more complex expressions. Also note that more than one _ is allowed in an application.

For any use case more complicated than that, I expect that lambda should be used instead.