Discuss: making a pluggable programming language

[qwertie]

Continuing from #12 .

Again, I haven't really coded in Rust yet so I don't have a complete sense of it yet. But my thinking right now is this: there is practical power in being able to say "treat this as an IFoo—yeah, I know it doesn't explicitly implement IFoo, but it has all the methods of an IFoo so please treat it as one." That's what Go lets you do but Rust/Haskell do not.

My favorite example is IList<T>, which was defined first, and does not have IReadOnlyList<T> as a supertype even though the latter is merely a subset of the former. I have personally experienced the problems this causes, because

1. if you really just want to accept a IReadOnlyList<T> but IList<T> is more popular, it is tempting to make an overload that accepts IList<T> and converts it (.AsListSource() extension method) to IReadOnlyList<T>. Likewise when implementing a read-only list, it's tempting to implement IList<T> as well as IReadOnlyList<T> so it'll be compatible with libraries that only accept IList<T>.
2. Together, this pair of accommodations causes pervasive "ambiguity" errors everywhere, which is a massive inconvenience that leads one to write a lot of extra methods to avoid the "ambiguity" errors. It is for this reason that I defined IListAndListSource<T> and filled my source code with disambiguating overloads. Look for IListAndListSource overloads in the ListExt class - it's a mess, there is no other way AFAIK to set it up that is convenient both for users of the old IList and new IReadOnlyList.

I realize this is a much smaller problem in Rust than C#, because you are allowed to implement traits on types that originally did not implement them. However, the fact is, you shouldn't have to explicitly implement IReadOnlyList<T> at all, since it's just a subset of IList<T>. So I want a language that can just see this relationship by itself. Some would argue this shouldn't happen automatically... and there are cases when that makes sense. But even if there are cases when we don't want an automatic conversion, there are more cases where we clearly do, and I think a developer should have the option of getting an automatic conversion when one is desired. But of course, this means we need a solution other than littering call sites with conversions everywhere.

Another favorite example of mine would be the situation where a DLL wants to implement a "plug-in" interface. It's pretty silly to have to reference a tiny (say 4KB) assembly whose only purpose is to store the definition of an interface so that a plug-in can implement the interface. It would be better if the plug-in can define its own copy of the interface as source code, and then the host application can just cast the plug-in object to its copy of the interface. In .NET this is impossible - both the host and the plug-in must have the "same" interface, and this means not only "an interface with the same name and the same members in the same order", but that it has to be stored in the same physical file on the hard drive too! That's waaay too restrictive IMO.

Also, I have a sense that Rust's "coherence", if that's defined as "a given type can only have a single implementation of an interface/trait", is unnecessarily restrictive. There may be some programming languages that do not have this restriction, or specific tricks you can do without it (e.g. different "views" of the same physical type), and therefore a language that wants to support as many type systems as possible shouldn't mandate "coherence". But I never studied Go deeply so I don't know if Go enforces coherence or not.

I'm not sure how to "unify" all the type systems yet - to make them interoperable. One possible approach is

1. start by thinking of "what's the most flexible type system I know of - one that's a superset of most others?" Union and intersection types come to mind. Possibly dependent types, except that I know nothing about them. If I start thinking low-level, I want tagged unions and pointers-that-can-also-be-integers (e.g. pointer turns into an integer if low bit = 1 - this is a core implementation detail for certain high-prformance data structures and an important implementation detail of interpreters such as Ruby.) Also, the CLR's run-time generics are great and I'd like to support them - it should be possible to instantiate new generic types at run-time. (On the other hand, because we want maximal flexibility, we ought to support D/C++-style templates too, which perhaps are not feasible to instantiate at runtime.)
2. Based on the best ideas we can find, we design a single really flexible type system.
3. Then survey several languages to see whether their type system is effectively a subset of ours. If the answer is "no" then we ask "what modifications are necessary to our type system to let it subsume that one?"
4. And all the while we should be asking ourselves, "how can we modularize this, minimizing dependencies between components?" Because when we figure that out, we'll have a way to allow 3rd-party type system components.

Note: I would forget about type inference in the beginning - I think that's something we can figure out later, by asking the question "what needs to be removed or altered to make type inference work well?" But since type inference is an optional feature that some developers don't even want (some see little value beyond the basics, like lambda type inference and the inference of var in C# - hell, I remember reading lots of opposition to "var" in C# 3.0, although I think most of those people are eating their words now.), I don't think we should dwell on it in the beginning.

Right now I'm thinking of scaffold... a workspace where one could begin building a language with multiple type systems and multiple sets of rules. I'm thinking of a program as if it were a file system, with "genericized" folders called "spaces" (short for "namespaces"). A space can be a namespace, a C# class, a struct, an enum, a method body, or something else defined by a 3rd party. Each space can be parameterized. What are the parameters? I'm not sure what the parameters should be yet; it's tempting to say "types" but we don't even know what those are yet, and some people will want spaces parameterized by compile-time constants, as in C++ where you can use Foo<17>. In any case, the parameters are something that exists at compile-time, to permit genericity.

Each space will have a "kind", like "namespace", "enum", "interface", "class", and so on. There would be special-purpose kinds, like "C#-style class" and "Rust-style trait". My thinking right now is that the "kind" specifies a "gatekeeper" for the space. It controls what can be added to the space (or maybe it just gives error messages when the wrong stuff is added), it is in charge of name resolution and overload resolution, and it might control how the type system works for code within the space.

Note: I think parameterized namespaces are fantastic and I want a language with those. For instance I once wrote a series of math classes that supported different kinds of numbers; for example an "affine transform" class: Transform3d<float>, Transform3d<double>, and of course Transform3d<FixedPoint<16> > because an important target platform had a 400MHz CPU with no FPU. The point is, because the namespace itself cannot be parameterized, there were <type parameters> all over the place. If instead the number type were a parameter of the enclosing namespace, most of those <angle brackets> could disappear. This feature will make it easier to write generic code, and therefore programmers will write more generic code. Edit: Keep in mind, most people don't want to use Transform3d<float> and Transform3d<double>, but just one or the other - so it makes sense to write using MathLibrary<double> and drop the type parameters everywhere else.

[qwertie]

To answer your last question, I can think of three type systems that seem totally incompatible, yet we would like them to interoperate:

1. "The ultimate statically typed language" - a mix of ideas from Rust & Ceylon, and to a lesser extent, Go, C#, and others. (Footnote: have you heard about C++'s equivalent of C# async/await? The design they made for C++ is superior to C#, but it wasn't included in C++17).
2. Julia - a high-performance but memory-hogging dynamic language centered around "multimethod" dispatch.
3. Javascript - because it currently rules the world.

I doubt we'll really be able to fit all three into a unified type system; I don't see how to combine Rust's non-OO design with C#'s OO design plus JS's prototype system plus Julia's multimethods. Getting these to work together harmoniously could be daunting. Naturally I tend to focus on (1) much more than the others, but ... we'll never really be done until systems this different can interoperate effectively.

[qwertie]

I would be nice to figure out if we can involve people who have worked on similar concepts before. I Googled around to find these:

• Bernhard Humm and Ralf Engelschall: A plea for pluggable programming languages
• Erik Meijer and Peter Drayton: Static typing where possible, dynamic typing where needed
  https://www.researchgate.net/publication/220946547_A_Plea_for_Pluggable_Programming_Language_Features
• Werner Dietl: "Checker Framework"

[qwertie]

This HLVM project sounds so much like Loyc:

http://www.ffconsultancy.com/ocaml/hlvm/

Looks like a typical open-source project though: very little documentation. But I wondering if I should just join an existing project like this one rather than attempting to make yet another language.

[qwertie]

OMG - the HLVM guy is charging £39 to let you read articles about HLVM? Ummmm... is that any way to get contributors on board? I also note that the author apparently ignores comments on his blog. Not a good sign...

[jonathanvdc]

Ah, so I see you've stumbled across HLVM as well. Its premise sounds nice. But I can see some serious problems with the project:

• The last commit to HLVM seems to date back to five years ago.
• Its source code footprint is suspiciously small, but only because it offloads all the hard work to LLVM.
• Getting LLVM (C++) and HLVM (OCaml) to communicate probably adds yet another layer of interop hell onto the already ugly problem of configuring a project that uses a native library like LLVM to build and run on multiple platforms.

So I'm somewhat inclined to consider HLVM as a "wrapper library" around an old version of LLVM. Its distinguishing feature seems to be that it also implements a GC. But no generics are a deal-breaker. And I'm not that fond of documentation pay-walls, either. So I wouldn't use HLVM as a compiler back-end. I'd say that compiler writers are likely better off generating LLVM IR directly, if they're going to go through the pain of building and configuring LLVM anyway.

I do like the idea of HLVM, though. Like WebAssembly, but for high-level, garbage-collected languages, right?

On a separate note: you have some great programming language design ideas. Like the "spaces" abstraction, and parameterized namespaces, which remind me of Ada's generic packages. I can definitely imagine people using that.

So if you want to create a brand new programming language, then I suggest you go for it. It'll be fun. Besides, what could possibly go wrong?
If you'd rather join an existing project instead, then that's perfectly understandable, as well. But why choose one when you can have both? Becoming a member of an existing community usually doesn't mean that you can't have any projects of your own.

I apologize for being so unresponsive over the course of the last few days. I've been working on school-related projects, which have kept me busy. Implementing last-minute features, doing merge-gone-wrong damage control. The works.

By the way, I see that you now have competition from Cirru to define a text format for WebAssembly. Interesting. May the odds be ever in your favor.

[qwertie]

How did you tell you old it is - did you actually download the repo? I didn't get that far. There's a copyright 2009 in the footer, but I could understand if the guy forgot to update it for six years.

No generics is a good point, but I assumed it would get generics eventually. Probably it's better to include them near the beginning of development though. The thing that impressed me most was the small size of it, and the sophistication of the GC. As for being "suspiciously small because it offloads all the hard work to LLVM", the author claims otherwise in a blog post:

now that HLVM supports standalone compilation using LLVM's IR optimization passes as well as unoptimized JIT compilation, we see that LLVM's optimization passes only give small performance improvements in many cases and even substantially degrade performance on our 10-queens benchmark. This is a direct result of HLVM producing near optimal code directly (which greatly reduces compile times) and has eliminated our desire to add support for LLVM's optimization passes

Of course, it's not explained how near-optimal code is generated directly. So, if development has halted, most info about HLVM is behind a paywall, and the author doesn't respond to blog comments, I'm not inclined to even download the source, let alone join the project.

It's inspirational, anyway - I'd love to figure out how to pack a powerful, extensible, fast language into less than 2000 LoC.

The Cirru guy seemed to immediately concede that LES should win. I was actually taken aback :D

I was glad to hear from you again! BTW I'm finally going to publish articles about Enhanced C# soon at the new ecsharp.net.

[jonathanvdc]

I didn't download HLVM, but I did find a GitHub mirror of the HLVM repo. hlvm.ml, the monolithic 2500 LoC HLVM implementation, seems to use LLVM. If any native codegen is performed by HLVM, then it must be exceedingly well hidden. I think the author meant that HLVM doesn't rely on LLVM's optimization passes (other than the tail-call optimization optimization), but still uses LLVM for codegen.

Also, judging by reading the HLVM source code, the optimization described in the blog post you linked is really recursive function inlining, not "true" loop unrolling. LLVM doesn't do that, for good reason: it amounts to improving performance by throwing virtually unbounded amounts of code size at the problem. That might work out well for simple 'fib' benchmarks - the entire 'fib' function is small enough to be held in the processor's cache at all times, and there's no need to make lots of relatively expensive function calls - but the code size increase could just as well result in cache misses and page faults for larger programs. In my humble opinion, it's more of a performance lottery than a conventional optimization. Improving the performance of simple functions like 'fib' could degrade the performance of complex, real-life programs. I suspect that LLVM's optimizations are geared towards optimizing larger programs, instead of tiny benchmarks.

In addition, HLVM is always compared to OCaml in that seven-year-old blog post. I'd like to see how HLVM compares to an optimizing ML compiler like MLton. A comparison with C and present-day OCaml would probably be helpful as well.

Looking forward to reading more about EC#. Incidentally, I've been using fecs to compile some C# benchmarks under -O1 and -O3, and then compare their performance. Inlining and scalar replacement of aggregates seem to be very effective at obliterating struct overhead, especially on mono. Maybe I should post some bar graphs of my own.

[qwertie]

Sadly, people don't seem to support the quick-binding operator. Not affirmatively against necessarily, but unwilling to say they like it.

[jonathanvdc]

Aw, that's a shame. Quick-binding seems like a really useful feature. I like think of x := y as a generalization of the var x = y; pattern. Besides, weren't people opposed to var in the first place, as well?

I think it's kind of funny that you write

Whatever syntax we use, actually implementing it will be challenging.

because fecs implements :=, =: and "block expressions" out-of-the-box in just a few lines of code. Quickbind.ecs works as expected.

Obviously, this problem is only easy from a compiler perspective. I can imagine that directly lowering block expressions to C# code is not entirely trivial. I remember implementing a pass that does just that: -fimperative-code, to support quick-bind-like code for -platform c++. I ended up spilling expression results into variables whenever a statement was encountered in an expression, to preserve the order of evaluation (Flame compiles block expressions down to expressions that contain statements).

[qwertie]

Yes, it's easy to implement in a proper compiler, but not easy to lower to plain C#. Actually, since LeMP doesn't have access to type information, it is sometimes impossible and, in general, some cases cannot be handled property. For example, given

if (f(#runSequence(g(), h()))) ...

"f" could be a delegate variable, so in theory we should implement this as

var f' = f; // BTW, EC# allows ' in identifiers
g();
if (f'(h())) ...

f should be stored in a temporary in case g() changes it. But of course, f is more likely to be a method group, in which case it can't be stored in a variable. So LeMP can't store f in a temporary.

Hmm, what made you support the =: operator? Did we talk about that? At first I thought of using :: because its precedence is well-known and I thought it looked good visually. Then I switched to =: for awhile as a mirror of :=. But I found that to be ugly, and C# coders are not necessarily familiar with := so =: wouldn't mean anything. Plus, its precedence is not as guessable as :: since the latter already exists in C++ and C# (same precedence in both). So I decided to switch back.

EDIT: of course, the more common case is stuff like

if (Foo.Bar(#runSequence(f(), g())))

Where Bar is a method group. Here, the problem is, Foo could be a property/variable (possible to store in a temporary) or it could be a class/struct (not possible to store in a temporary).

[jonathanvdc]

I don't recall my exact reasoning when I implemented := and =: support in fecs, but I think I noticed CodeSymbols.QuickBindSet and then I just ran with it, I guess. Quick-binding was an easy-to-implement and useful feature, and a nice distraction from the repetitive labor of implementing arithmetic operators. Block expressions were fun, too, and they were clearly part of your long-term plans. So I implemented those, as well.

I must say that I'm so sure about :: as a quick-bind operator. Granted, it makes tons of sense from an operator precedence viewpoint. But isn't it somewhat ambiguous for the analyzer, which can't know in advance if A::B.c is a static member of A::B or an instance member of a quick-bound variable? To remain compatible with unmodified C#, you'd always have to default to the former, even if it's super rare, which could become EC#'s very own most vexing parse.

Ouch. I hadn't even considered that LeMP is a lexical macro processor (and that C# has lots of weird corner cases). Doesn't that preclude implementing block expressions/#runSequence as a macro? Or do you have some kind of devious workaround?

Which makes me wonder: how would you tell the two meanings of the :: operator apart in a lexical macro processor like LeMP? Isn't that just as hard as lowering expression blocks/#runSequence?

[qwertie]

The main article introducing Enhanced C# is ready!

[qwertie]

I have a simplistic plan. :: is for namespace aliases so the left-hand side must normally be an identifier. If it's not, it can be treated as a quick bind. In case it's an identifier, I simply decided that if it's lowercase (e.g. global::) it's an alias, otherwise it's treated as a quick bind. If this were a proper compiler, I would instead just check if there is any known alias left of ::, and if so treat :: as not a quick bind. If I understand correctly, the list of all possible aliases is readily available from the project settings and from previous statements in the same C# file.

I've determined that most block expressions can be implemented as a macro if I cheat a bit and use some heuristics. I previously used one of these heuristics in match and matchCode: if you write match(Foo) {...} or match(foo()) {...}, Foo or foo() will be saved to a temporary variable, but if you write match(foo) {...}, it's assumed to be a variable and won't be saved to a temporary. Devious and evil, maybe, but at least for my own code, it's a pretty reliable heuristic.

[jonathanvdc]

I guess those are relatively reliable heuristics. They'd work for most of the code I write, as well. Except for my arguments, which I format as Foo. But that's no big deal, because the extra temporary probably doesn't matter, since even mono does copy propagation, according to the man page.

Doing this without any heuristics would be extra cool, though. Maybe a few built-in low-level meta-programming features in the C# compiler, such as "do x if foo is a type name, y otherwise", could do the trick. Which is actually a little bit like D's static if and a number of compile-time predicates. If you're interested, I could implement something like that in fecs, along with whatever C# language features you need to get some examples running and evaluate the approach.

Awesome article, by the way! I enjoyed reading it.

[qwertie]

I thought of a couple of new syntaxes for quick binding based on the idea of $ meaning "create a variable". What do you think of these?

if (GetList()::$list.Count > 0)
if (GetList()($list).Count > 0)

By adding $ as a binary operator, it could even be

if (GetList()$list.Count > 0)

[jonathanvdc]

if (GetList()$list.Count > 0)

is my personal favorite. I think the others (especially GetList()($list)) introduce too much noise. I don't know what's wrong with := and =: - which may come across as more familiar to users of other programming languages - besides operator precedence, though. Doesn't $ face the same problem?

[qwertie]

Well, C# developers are a conservative bunch; I'm concerned that they will complain about any new syntax. Also, regularity is a virtue. So while := is a very convenient way to create variables, it's redundant since var already exists, so I expect it to attract haters, and more importantly, there will be people who won't use EC# because it adds too much stuff - people in the "there should only be one way to do something" mindset. Meanwhile =: has no precedent in other languages, and its precedence is non-obvious.

When it comes to pattern matching (match and especially matchCode), though, they need a unary operator to create new variables since variables are created positionally, so := and =: don't make sense there, and (var x) is terribly verbose. So I have defined $ to create vars in those contexts (some languages go even further and eliminate all syntactic markers that a new variable is being created, but that's impossible in matchCode - see more rationale here). But having been forced to define $ for creating variables, logically we could extend this to other contexts, like a new for loop

for ($x in list)

Or even a new way to declare variables:

$x = 5;

Again, this last one especially might attract haters so ... maybe let's not promote this even if it's allowed.

[qwertie]

One person did comment that

(var x, var y, var z) = tuple;

was too verbose, so some would appreciate

($x, $y, $z) = tuple;

Now, it's not as short as

(x, y, z) := tuple;

But it has a virtue: you don't have to create every variable. So if you already created x and y earlier, you'd just write

(x, y, $z) = tuple;

to create z and reassign the existing vars.

[qwertie]

@jonathanvdc 3 days ago I discovered something slightly devastating - I mean, it's a good thing, but it's not good for me. It turns out that C# 7 has been in development for more than a year - since well before C# 6 was officially released. Plus, they've been conducting all the design out in the open where anyone could read it... except that I didn't realize this and wasn't following along. You can find summaries of the discussions here, and I've been reading those for something like 15 of the last 70 hours, and I'm still far from done reading. I discovered this by listening to this DotNetRocks podcast, which is also quite informative.

Obviously if I want to avoid throwing away EC#, I'll need to adapt to C# 7. The main things will be to support the new "record classes" like class Foo(int X, int Y), and I'll have to replace the current pattern-matching system with their new pattern-matching system, insofar as it is possible to do so with lexical macros. Lots of work. Back to work...

[jonathanvdc]

Yeah, they're sneaky like that.

Oh, I think it'd be awesome if a lexical macro could lower pattern-matching and "record classes" to regular C# 6 constructs. Kind of like a Javascript-to-Javascript compiler.

It's fine (but not nearly as satisfying) if that turns out to be impossible, though. Because, well, at some point, Roslyn and mcs are going to support C# 7 pattern-matching. So you can just have LeMP ignore the pattern-matching constructs. If that's the case, then I'll teach the Flame EC# front-end to compile pattern-matching as well.

Supporting the (new) pattern-matching syntax seems critical to EC# regardless.