Loyc/EC# and Flame/D#

[qwertie]

Continuing discussion from #3.

[qwertie]

Thanks for your detailed reply.

You didn't mention Compile-Time Code Execution (CTCE). Given the name "D#", is that in your plans?

The main issue that sticks out in my mind is compatibility with C#. There are many programming languages in the world and people are making new ones all the time. I don't really want to make a programming language "for fun" - I want to make a meaningful contribution to the software industry. In fact, I'm starting to think about how to build an interoperability framework for WebAssembly, as soon as the first beta of the latter becomes available, because I think WebAssembly is the "future of the computer industry" (or at least, it will be if I have any say in the matter, but I'm just one guy with very little money, so... we'll see.)

I see new general-purpose language projects popping up all the time, and I don't like it. In my opinion there's no point in just making a language that is "better than C++" or "better than Java" or "better than C++", since several languages fitting these descriptions already exist, and many of them are even stable. Enhanced C# is really a gimmick - it's not the best language I could create, and it's not intended to be. I'm developing it because I think that backward compatibility is a potential fruitful way to put more power in the hands of developers. Switching languages is a risky business maneuver, and a potentially difficult one if you already have a C# code base. I think the cost and perceived risk of switching largely explains why there is slow uptake of nice languages like D, Rust, Nemerle and even Ceylon. Languages perceived to be obscure, like Nim, Plaid, or Dyvil, don't stand a chance.

That's why Enhanced C# tries very hard to be backward compatible with C#. I don't think 100% compatibility is necessary (or even possible, for people like me with very limited resources), but it's important to make sure the number of changes required to convert a large project to an EC# compiler is normally small. It's also really good, I think, to focus first on features that can be converted to plain C#.

You see, if I was going to make my idea of the ultimate programming language, it would start completely from scratch and mostly ignore mainstream languages like C#, except for the purpose of consensus building (it's important to keep conventions that programmers are familiar with) and copying good ideas. I wrote about this recently in the blog.

So to me, backward compatibility is non-negotiable [edit: unless you actually are interested in starting from scratch]. That said, I do believe in being more liberal about changes than C# itself. For instance, I've introduced a new value(->type) cast operator based on the observation that I usually decide to do a cast after I write the subexpression that needs a conversion, not before, and I'm also ticked off at needing double parens all the time: ((List<T>)L).Count. I don't think the C# team would do something like that because they'd hate having two syntaxes for the same thing. EC#, on the other hand, is officially a different language than C# and I hope users can accept that there are two syntaxes for a few things, the C# one and the EC# one.

Here are some specific points in response to your last message:

• The C# team themselves are interested in supporting extension properties and VB already does, so I'm interested too. However, the syntax bool IsAbstract[this IMember Member] doesn't feel right to me, since it looks like an indexer. Do you happen to know what the C# team was going to use?

• It's an interesting thought to just use a statement as a function body... but for C# 6 I must support a special syntax with =>. It doesn't overlap the statement grammar, but supporting both the C# 6 style and the D# style seems like overkill. I mean, I'm not opposed to having two syntaxes for the same thing, but one of them needs an obvious advantage over the other. Actually, it's kind of sad, because I actually have three syntaxes already, not including yours:

  int square(int x) { return x*x; }
  int square(int x) { x*x } // original syntax chosen before C# 6 (note the lack of semicolon)
  int square(int x) => x*x; // C# 6 syntax
  

I haven't removed the { x*x } syntax since it has a clear advantage over C# 6: you can write multiple statements in the method body, prior to the return value. The same syntax is also re-used elsewhere in the language, since you can write things like ...else if ({ var foo = Foo; foo.X*foo.Y }) .... It also has precedent, since Rust expresses return values the same way.

• How is your concept of static different from C# in terms of its practical effect on code?
• typeof(T) doesn't have to return System.Type, at least for you, if you're not concerned with backward compatibility.
• double(int) looks better than Func<int, double> and it can support, say, double(ref int) too, but I have a feeling it would slow down my parser. Languages in the C family might be more efficient to parse in with an LR parser generator, but mine is LL(k).
• Technically, your lambda syntax is incompatible with the current syntax of EC#, since foo(a < b > c) => d is already legal in EC# and the left-hand side is parsed as a normal call, not a method signature. More importantly, I want a language that can, at minimum, infer return values of lambdas. (Inferring the rest is obviously much harder; in fact the design of LINQ was changed during development due to the computational difficulty of inferring types when lambdas are nested.)
• I have to say bluntly that I don't like requiring a pointer syntax for ref variables. It's also a pet peeve that annoys me about C++ and Rust. It's not about being comfortable with pointers - I programmed in C++ for about 15 years, so I understand pointers perfectly well, but I want to be able to
  1. change the signature from ref int to int or vice versa without having to change the method body.
  2. not worry about whether something is a pointer when I'm using the members it refers too.

Also, references to class objects are also pointers. You don't require dereferencing those, right?

Your thoughts on templates are interesting. It is certainly nice to be able to verify in advance that all possible instantiations of a template/generic are valid (if the type matches the method signature). But templates like you find in C++ and D permit greater metaprogramming - for example, you can do a static if on the type T. I value performance, so I'm glad you have a plan for optimization. But I suspect it won't be able to optimize in some cases that D programmers take for granted, because without features like static if, you might have to use virtual dispatch instead.

It would be really nice to have non-nullable references.. have you seen the "Twisted Oak Studios" post on that?

I have a sense that it's important to start work on an SIL (and MLSL) in order to have a solid foundation for converting code between languages. However, if possible I want to have some synergy between SIL and WebAssembly, so I've been waiting for the WebAssembly folks to make up their mind about what kind of primitives they want. WebAssembly, like Flame's IR, uses structured control flow, probably so that it is straightforward to polyfill to Javascript, but they haven't settled on which primitives to use. But hey, maybe the particular primitives aren't actually that important: code built on top doesn't necessarily need to target the actual primitives; I guess a language conversion framework ought to have some way to map any reasonable set of structured primitives onto any other.

[jonathanvdc]

I've tried to split your comment into separate points:

Things that relate to D# and EC#

• Yes, I do plan on implementing CTFE, though I haven't done so yet, because it would require running an interpreter or a JIT inside the compiler itself, which would really just amount to creating an additional back-end. I've already started work on Flame.ExpressionTrees, a back-end that compiles IR down to LINQ expression trees (which the .Net framework can then execute). I've already created a toy REPL with it, so I suppose it could be retrofitted to run code at compile-time as well. Anyway, CTFE is more of an optimization in a programming language that currently lacks static if and template metaprogramming.
• I'm unsure as to whether keeping C#'s semantics intact at every turn is the way to go or not, because:
  • Backwards compatibility has been a blessing for C++'s adoption rate at first, but that blessing seems to have become more of a curse now. Signatures such as const int* (*f)(int, double) are - in my opinion - not something C++ should have inherited from C in the first place, along with the many evils of the C preprocessor and the C standard library, which does not even remotely fit in with the STL. One of the main reasons why I love the D language is that it eliminates all this C awkwardness.
  • Full backwards compatibility can and will create an uneasy power dynamic between the original and the derived language. Any language that claims to be a superset of another must implement the other language's new features every time they are added, even if that feature was already present in another form in the derived language in the first place. I once read that the TypeScript team had to redesign a bunch of object-oriented features because the ECMAScript 6 spec had significant overlap with those features. Looks like C# 6 made you add a lot of (potentially unwanted) features to EC#, as well.
• The Roslyn people don't seem to have decided on an "extension everything" syntax yet, as far as I can tell.
• D#'s static classes can have base classes and implement interfaces, and avoid redundant allocations because they have only one instance. They can also do everything a C# static class does. Here's an example:

// Definition
public static class EmptyStatement : IStatement
...
// Usage
IStatement stmt = EmptyStatement;

• I think lacking a dedicated syntax for delegate types is a shortcoming of C# right now. I picked int(double) for D#, but I wouldn't mind using something like TypeScript's double => int or the classic double -> int.
• C# infers lambda parameter and return types by relying on contextual information, which makes it unique in a language where every expression except for lambda expressions can determine their type based on subexpressions and manual typing. I've never read an article that explains just how this contextual type inference voodoo is performed, even when they claim that type inference has "improved". Seems to me like lambda type inference is more of a vague "the compiler will get it right"-ish notion than a well-specified algorithm. I don't see how anyone can implement a feature like this and still be able to infer the exact same types as the reference implementation every time. Lambda return type inference based on manually-typed parameters on the other hand seems perfectly doable. I'm okay with that.
• I concede that ref parameters have valid use cases, though I would advocate making the -> operator obsolete by replacing it with a more powerful . operator, which would make accessing pointer members easier.
• About templates and static if: I have - in my experience - never craved them in what little Haskell programming experience I have, because type classes have made Haskell's type parameters powerful enough to make "true" templates unnecessary. A template is just language-level support for copy-pasting code, which have spread like a cancer in just about every language they have been implemented in. Standard libraries are exceptionally vulnerable to template abuse, which D's standard library has quite successfully demonstrated. static if on generic parameters is nice, but from, what I understand, your friendly neighborhood RyuJIT will already constant-fold regular ifs on generic parameters.
• I would love to have non-nullable references, too. But I'm not all that fond of the withdefault(T) "operator" and the fact that all non-nullable references must be initialized. I would much rather just treat default(T) where T is a non-nullable reference type as if T were a value type: create a new instance, fill it up with default values - though I realize what the performance implications of such a mechanism would be.

Thoughts on WebAssembly and SIL

• WebAssembly seems like a great platform. I plan on creating a wasm back-end when the wasm people finalize the MVP spec, though I'm not entirely satisfied with wasm's memory model. A GC API, in particular, would be a welcome addition for managed languages: it'd be a shame to have to include a custom GC if the environment has a perfectly good GC just sitting there doing nothing.
• Lowering Flame's primitives to wasm primitives is perfectly possible, but it'd be a one-way trip for sure. Flame has the following primitive types:
  • bool, char, string: the usual;
  • int8, int16, int32, int64: signed integer types;
  • uint8, uint16, uint32, uint64: unsigned integer types;
  • float32, float64: floating-point types;
  • bit8, bit16, bit32, bit64: "bit types". These types are primarily useful when casting things and when performing IO. For example: long x = (long)(bit64)1.0; will store 1.0's bits into a 64-bit signed integer variable.
  • void: the void type;
  • null: the type of a null expression.
• IMO, WebAssembly is getting a lot of things right, but it doesn't look like it has any ambition to be an intermediary format for object-oriented assemblies. And that's fine, really. Perhaps a (heavily) modified version of wasm could serve as a basis for such a format? That would still make a hypothetical SIL and wasm incompatible, though. Maybe creating a similar design, analogous to wasm in many ways, but capable of containing more high-level and source-level information, would be more appropriate than a modified version of wasm.

These comments are starting to get absurdly long, and wasm and SIL seem - even though they fascinate me more than the practical differences between EC# and D# - somewhat off-topic here.

[qwertie]

There is, of course, a well-specified algorithm for how the type of a lambda is inferred. I've read about it (though I can't recall where) and I'm sure complete details are in the C# spec. The basic idea is (1) figure out what the possibilities are based on context (e.g. based on available method overloads, you might see that the lambda must have type T1 => T1 or T2 => bool); and (2) try to compile (semantically analyze) the lambda under the assumption that it has each possible type. If compilation is successful under exactly one assumption, type inference succeeds.

Okay, that definition of static classes sounds reasonable, and I guess it preserves backward compatibility, doesn't it? Apart from reflection...

I like the arrow syntaxes better, because it means no large lookahead is required to distinguish between A(B,C,...) X; and A(B,C,...);; note that the latter would be far more common than a statement that starts with A=>B or A->B.

Rust, by the way, does use . instead of ->, but I would still rather be able to forget about what's a pointer and what's a "direct" reference, so as not to have to add * when copying the value or sending it to another function.

I'm not sure what you mean about template abuse in D's standard library.

Do you have a citation for "RyuJIT will already constant-fold regular ifs on generic parameters"?

What? You're not seriously thinking of making, say, default(List<T>!) be a List<T> created without calling the constructor? Do I misunderstand?

---

The WebAssembly MVP is constrained to be "pollyfillable" - it has to map to asm.js, and they aren't able to support garbage collection under this constraint. I asked them if they had a plan for supporting garbage collection as a "first class citizen" in WebAssembly after MVP. One person responded:

Yes. I believe there is an issue about this, if not a page on the wiki. We've had in-person discussions about what it will look like and we are confident it can be done effectively. I plan to spearhead this effort if nobody else takes on that responsibility, and I'll make sure to collect feedback from people who intend to use it.

Unfortunately the WebAsm folks are focusing mainly on making a C-like machine language for compiling "native", static languages. I'm certain they are not interested in making a highly interoperable platform like the CLR is, nor are they interested in defining a multi-language standard library. That's too bad, 'cause I think the software industry has a tremendous need for a way for languages to talk to each other on a rich, high level. The good news is that they understand the value of providing a very flexible platform, and they believe in the Extensible Web manifesto. While the MVP might not be a very good basis for "managed" languages since it won't have a GC, likely won't allow programs to generate code at run-time, and might not even have a resizable heap, in the long run I think it will get all those things.

WAsm is going to be extremely important, I'm convinced of that. So, what we need to do is build an interoperability framework on top of it - a multi-language standard library, and ABIs for languages to talk to each other. The WAsm group itself won't make these things, but they are designing WAsm in such a way that an interoperability framework can be built on top. But who is "we"? I know I'd like to work on this, but I don't know about you.

Sorry if this seems off-topic, but I thought we were talking about "all the topics". My goal in life is to improve the world, so if I thought I could do more good by dropping EC# and building something on WebAssembly, I would do that. I definitely want to publish a nice macro library first though - hopefully LeMP and its macros will be useful to some developers, even if EC# never gets a proper compiler.

[jonathanvdc]

Oh, I didn't mean to discourage discussing wasm/MLSL at all. I just thought that maybe those topics deserved their own issue, though that might have been silly of me in hindsight.

Anyway, no need to lament EC#'s demise quite yet. Flame.Loyc and fecs are still in active development now (I do hope the latter qualifies or will qualify someday as an EC# compiler). I got to the point where a simple alt class's expansion is compiling correctly today - except for the debugger-related custom attribute, which I'm just ignoring right now -, and am moving toward implementing generics.

I would agree that WebAssembly is a golden opportunity for the development of a universal standard library. I would disagree that the time of either one of us would be "better spent" developing such an MLSL than developing Flame/Loyc/EC#/D#/other compiler and language tools, because such tools are very much a prerequisite for the emergence of any MLSL if you ask me.

The creation of WebAssembly might very well create an opportunity for the emergence of new managed languages and tools relating to them, because the toolchains that do will probably support wasm at launch - mainly thinking of gcc and LLVM here - will likely have low-level languages such as C and C++ in mind. These C/C++ implementations will surely stick with their own standard libraries. A compiler for a high-level, managed language that targets wasm shortly after launch stands to gain more attention than one targeting, say, the CLR. A wasm standard library for managed languages would be equally unprecedented. This would give a wasm MLSL - if published at just the right time - the strategic edge it needs to boost adoption.

All we need to AOT-compile a managed language such as EC# is a GC, which might just as well be the good old Boehm GC at first, which can be compiled with clang and then linked with the resulting wasm module.

I'm interested in working on the following (probably in that order):

• The further development of Flame.Loyc and fecs. Any front-end that can compile most C# code (not to mention EC#) to any Flame back-end is something sounds like good news to me.
• Creating a (binary) intermediary format for managed assemblies. Like .Net assemblies, but more extensible. Function bodies would be encoded in a wasm-like style, including a structured control flow approach and the everything-is-an-expression paradigm. I can't really tell how similar that would be to your hypothetical SIL project.
• Building a wasm back-end for Flame.
• Starting work on an MLSL, which is at first aimed mainly at supporting WebAssembly and perhaps also the CLR - I suggest the latter because that would enable C# programmers such as myself to code and debug in Visual Studio - code would run on the CLR but would be written with wasm in mind -, then open up a command prompt, type fecs Project.csproj -platform wasm and get a working wasm module, without having to change a single line of code. That'd be awesome.

Does that sound reasonable and/or appealing to you?

[qwertie]

When I think again about all the things I want to see accomplished, it strikes me how massive the task is. My wishlist includes:

• Make Enhanced C#, which brings advanced features to a mainstream language, in order to increase programmer productivity and achieve broader mindshare for previously obscure ideas like LISP macros.
• Make a multi-language standard library (MLSL) with strings, and the usual data structures, interfaces, and higher-order functions. Eventually the MLSL should include a wide variety of more advanced stuff, but collections and their interfaces are, of course, the most important thing.
• Standardize interfaces (not implementations) for common ideas that many standard libraries do not cover, such as graphs and other common mathematical objects; representations for 2D/3D transformation matrices, colors, 2D/3D/ND points, etc., that are not associated with any particular graphics library; maybe database access; and maybe GUI (if it's even possible to standardize that).
• Make a CLR-like binary interoperability framework built on WebAssembly (to support running on the MVP, it could be more Swift-like, with no garbage collector).
• Make a programming language of awesome power and flexibility.

This is too much to a couple of people to accomplish, even working full time (which I can't guarantee) and in fact, I know that if I were to do these tasks alone or even with one other person, I wouldn't get the highest-quality ideas. I feel like the right strategy is to build a community to crowdsource ideas, prototypes and code. I've known for some time that a community is needed, but I don't know how to build such a community, or even how to get publicity.

I have to admit, I feel like I am quite busy these days even though I'm actually on vacation. Even the mundane stuff can be really time-consuming - I'd like to combine LeMP and its syntax highlighter into one Visual Studio extension for example, and show errors with red squiggly underlines, but I haven't found time to work on that. And I'd like to write an article about syntax highlighting in VS, because I've made it quite easy to write a syntax highlighter for a Loyc language in VS. And... well, nothing's coming to mind, but I'm sure there's lots of mundane tasks to do. Plus, I believe I just met my wife, and happily, I'll be devoting substantial time to her.

I'd like to have a closer look at how you've combined EC# and Flame (and I'd like to know more about what Flame "is" and how it works) ... but I haven't found the time yet. I'd also like to know if you had any difficulties figuring out how to use EC# and Loyc trees - it was a big (and pleasant) surprise to see Loyc stuff suddenly integrated with somebody else's framework, with no foreshadowing in the form of "how-do-I-use-this" questions! Btw, are you using the EC# syntax highlighter and/or Custom Tool in Visual Studio? Are you using the latest version from Lib\LLLPG in this repo, or perhaps a regular build from Bin\?

So, yes, the four points you listed are appealing to me (assuming that I like the design of Flame, which I'm not yet familiar with). But if we are to have a chance of making serious progress, we'll need to figure out how to get more manpower. Do you have any ideas in that regard? Also, you'll need to write some sort of tour of Flame's architecture (giving the names of important classes and what they do), because I'm afraid I don't have time to figure it out by opening random source files (I'm too slow at figuring things out just by reading code).

[jonathanvdc]

My Loyc setup is pretty basic:

• I just build the entire Loyc solution and move the resulting binaries to Flame.Loyc's libs\ directory.
• Viewing EC# source is something I do in Atom, with regular C# highlighting, because it's snappy and lightweight, and because I'm not using Visual Studio's build and debug facilities - fecs is a command-line utility, after all. The Visual Studio extensions sounds nice, though. I'll look into that.
• LNodes are easy to understand and reason about because their structure is so regular. They're okay to consume from F#, too. I love 'em.
• The only real issue I've had with Loyc so far is that SourcePos does not refer to an ISourceFile, unlike SourceRange. That kind of prevents me from printing caret diagnostics when a syntax error is encountered. I'll have a stab at fixing that when Flame.Loyc's set of supported features starts to become bigger.

I'm sure there are lots of people out there who are interested in Flame, Loyc, WebAssembly and MLSL, but I have no idea how to make them magically appear here. Perhaps free cookies will do the trick?

I am now also in the process of documenting whatever comes to mind about Flame's architecture. Is there anything in particular you'd like me to elaborate on?

By the way: good news everyone, generic types have been implemented in Flame.Loyc as of today. The following alt class compiles successfully (though fecs whines about some attributes it does not yet know about: partial and some debugger-related custom attributes).

public alt class Maybe<T>
{
    public alt Just(T Value);
    public alt Nothing();
}

[qwertie]

Hi, I've been busy finishing up an Esperanto quick reference for my girlfriend...

I'd like to know more details about Flame's IR design - could you give a nontrivial example of some C# code and how it is represented in IR form? Have you considered mapping the IR to LES, as a way of communicating the content of an IR tree? And the type system - is it pretty much just .NET's type system? Is it C#-specific?

[jonathanvdc]

Awesome!

Here are a few examples of C# code that generates an IR tree, along with a short introduction that addresses a number of design choices that I made while creating Flame's IR.

Flame's type system is pretty close to the CLR's, though I think I'll revise it at some point in the future by making it rely more on reference equality (type equality comparisons are commonplace, but painfully slow right now), creating a "canonical" generic type/method instance type, and determining subclass/superclass relationships by virtual call. That should make Flame's type system more extensible and reduce implementation boilerplate code at the same time.

Also, yes, I have been thinking of using LES as an interchange format for Flame. Here's my proposal:

• Creating a Flame back-end that outputs LES trees that are entirely unambiguous, and therefore incompatible with the LES trees the C#/EC# parser produces. This will make creating an efficient front-end that decodes this format so much easier.
  • This will likely include mandating that the target of a call node is an id node. Invocations will be represented as #invoke(<target>, <args...>).
  • Locals are stored in a table and are accessed by index.
• Creating a binary format for LES, and using that to encode method bodies.
  • Type, field and method references are encoded as an index into a table for O(1) access. Parsing and resolving a textual representation of a type over and over again - which is what parsers and front-ends do - has never had positive effects on performance in my experience.
  • Nodes are encoded and decoded based on a "template", which consists of the node's target id (if any), and the count and encoding formats of its arguments - int literal, LES node, type literal, etc. Attributes are encoded analogously. If a node template's target is not an id (a scenario which I won't be optimizing all that much, as this is not something the back-end will produce), then a special "id" value will be used, and the target node will be inserted right before the argument list. These templates will be accessed by index.

Basically, I'd like to encode some_local(some_other_local, "hi") as:

locals:
    0: <index in type table>, "some_local", []
                                            ^~ empty attribute list, could be useful 
                                               for escape analysis information, etc
    1: <index in type table>, "some_other_local", []
code:
    #invoke(#getlocal(0), #getlocal(1), "hi")

which is then serialized as:

locals (these aren't necessary to correctly parse the LES tree,
        but I included them here because Flame will need them):
    0: <index in type table>, "some_local", []
    1: <index in type table>, "some_other_local", []
templates:
    0: #invoke(node, node, string)[]
    1: #getlocal(int)[]
code:
    #0(#1(0)[], #1(1)[], "hi")[]

The major advantage of this template-based approach is that certain features, such as an empty attribute list and an id target node, are zero-cost in the binary encoding, without reducing the set of LES nodes that can be encoded. Also, this optimizes frequently used operations, such as #getlocal in the example above.

Do you think that is something that can realistically be done, or would it require changes to Loyc's architecture? Did I miss any LES features? What do you think of this in general?

[jonathanvdc]

BTW, I forked Loyc and made some changes to better support fecs's caret diagnostics.

Here's fecs's previous output when I neglected to write a semicolon (no colors because GitHub won't let me include inline styles):

fecs Product.cs -repeat-command -terminal html

Error: 'TypeKeyword': expected Semicolon
Remark: D:\Programming\Git\Flame.Loyc\fecs\tests\Product.cs(16,13)

Now:

fecs Product.cs -repeat-command -terminal html

Error: 'TypeKeyword': expected Semicolon

    int n = rand.Next(0, 10), m = rand.Next(0, 10);
    ^                                              
Remark: In 'D:\Programming\Git\Flame.Loyc\fecs\tests\Product.cs' on line 16, column 13.

Should I send a PR?

[qwertie]

Why did you want to create a SourcePosAndFile class instead of just using SourceRange? With the latter, your error could show the range...

int n = rand.Next(0, 10), m = rand.Next(0, 10);
^^^                                              
In 'D:\Programming\Git\Flame.Loyc\fecs\tests\Product.cs' on line 16, column 13.

[qwertie]

I'm just starting to read your document... here are my thoughts on the first code block

// Gets the declaring method (i.e. the `id` function).
IMethod declMethod = ...;

// Maps the function's parameter to a "variable":
// an object that support creating a get-expression and a set-statement.
// Variables need not have an actual memory location. All they do
// is create expressions and statements.
IParameter[] parameters = declMethod.GetParameters();
// An argument variable is created by passing the parameter's signature
// and the parameter's index in the parameter list.
var arg = new ArgumentVariable(parameters[0], 0);    
// Creates an expression that gets the argument, and wraps that in a return statement.
// This is equivalent to C#'s `return value;`.
return new ReturnStatement(arg.CreateGetExpression());

This code is odd to me in the following ways:

• GetParameters() returns an array. Arrays are writable. Surely that's not what you want? Using arrays was a basic design flaw in the original .NET reflection interfaces; they did it because generic types did not exist at the time.
• Why isn't GetParameters() just a property called Parameters?
• It seems to me that the concept you've called a "variable" should be called a "property".
• It is odd that the number 0 is duplicated in new ArgumentVariable(parameters[0], 0) - what does it mean if I write new ArgumentVariable(parameters[0], 7)? Also, I wonder why the IParameter is not itself a "variable" (property).
• Why isn't CreateGetExpression() just a property called GetExpression?

[jonathanvdc]

• As I have stated before, I have scheduled a redesign of Flame's type system. Interfaces such as IMethod are a part of the type system and are, as such, subject to re-evaluation. I was already planning on making GetParameters() return a sequence rather than an array.
• Renaming it to Parameters seems like a welcome addition, as well.
• I disagree that variables in Flame should be called properties because:
  • Renaming the IVariable interface to IProperty would be foolish, as the IProperty name is already reserved for actual OO properties.
  • Properties are not capable of creating a release-statement (which tells the compiler that it is safe to reuse this variable) or an address-of expression. IVariable can do the former, and its sub-interface IUnmanagedVariable can do both.
  • Properties can be conveniently accessed by creating a PropertyVariable instance. Surely a PropertyProperty would seem out of place.
  • Variables in Flame correspond just plain C# variables most of the time. An ArgumentVariable creates expressions and statements that actually access and manipulate the underlying variable. The same goes for a LateBoundVariable, which is Flame's local variable implementation. Perhaps the technically correct C++ name for a "variable" in Flame would be an "lvalue", but I would rather not sacrifice usability for naming correctness.
• An IParameter does not encapsulate its own index, which makes constructing (verifiably correct) method signatures much easier. new ArgumentVariable(parameters[0], 0) is a concession to practicality. A typical front-end (fecs, for example) will have only a single line of code that creates an ArgumentVariable, usually nested in a loop. Creating method instances is a problem the front-end, middle-end and back-end have to face. I made the latter more bearable at the expense of the former. Also, making every IParameter an IVariable would be impossible either way, because Flame.Compiler - Flame's middle-end compiler assembly - both defines IVariable and depends on Flame - the project's reflection framework assembly -, which defines IParameter.
• For symmetry with CreateSetStatement, also defined in IVariable.

[jonathanvdc]

Okay. I made BaseParser use SourceRange objects when logging errors. I guess I'll revert that previous commit now, unless you can think of a reason not to. fecs output is now:

fecs Product.cs -terminal html -repeat-command

Error: 'TypeKeyword': expected Semicolon

    int n = rand.Next(0, 10), m = rand.Next(0, 10);
    ^~~                                            
Remark: In 'D:\Programming\Git\Flame.Loyc\fecs\tests\Product.cs' on line 17, column 13.

EDIT: if you prefer carets over tildes, you can always just:

fecs Product.cs -repeat-command -diagnostics-highlight-character caret

Error: 'TypeKeyword': expected Semicolon

    int n = rand.Next(0, 10), m = rand.Next(0, 10);
    ^^^                                            
Remark: In 'D:\Programming\Git\Flame.Loyc\fecs\tests\Product.cs' on line 17, column 13.

[qwertie]

Looking at the other examples I am uneasy about a couple of other things..

• LateBoundVariable is an odd name for a local variable. How is a local variable "late bound"?
• That variables are not block-scoped sounds potentially problematic, because in many languages including C#, you can define two different variables with the same name and different types in different blocks.
• From Int32Expression, EqualityExpression and LessThanExpression I gather that there is a separate data type for every single primitive type and operator. Why?

Why there is a distinction between 'statements' and 'expressions'? Experience has shown me that I don't want void to have special treatment.

What's 'pixie' and IMarkupNode?

[qwertie]

I have to admit, I don't understand very much of what you're saying about Flame and LES. This whole paragraph I'm simply not following at all:

Flame's type system is pretty close to the CLR's, though I think I'll revise it at some point in the future by making it rely more on reference equality (type equality comparisons are commonplace, but painfully slow right now), creating a "canonical" generic type/method instance type, and determining subclass/superclass relationships by virtual call.

And...

• I don't see why you'd use #invoke(<target>, <args...>) instead of <target>(<args>)

• LES is a text format by definition. I guess you meant to say "Creating a binary format for Loyc trees".

• This code is not valid LES:

  locals:
      0: <index in type table>, "some_local", []
                                              ^~ empty attribute list, could be useful 
                                                 for escape analysis information, etc
      1: <index in type table>, "some_other_local", []
  code:
      #invoke(#getlocal(0), #getlocal(1), "hi")
  

I was suggesting LES to be used as a format for communication purposes, i.e. between me and you and other developers, or between humans and computers, so that we have a well-understood, compact representation for the IR. A binary Loyc tree format and "index into a table for O(1) access" may be useful for something (although I don't know what your goal is), but it's not useful for communicating.

[qwertie]

Personally, I enjoy (and have a lot more experience in) language design over back-end design and optimization passes. So if I was focused more on the core/middle and you were focused more on the back-end, it would make sense.

You're right that fat pointers could (theoretically) be replaced with thin ones under global analysis, but (1) interface dispatch with fat pointers tends to be simpler than with thin ones (.NET optimized dispatch is complex), and (2) whole-program analysis wouldn't make sense in a system designed to replace the CLR - it's a dynamic system, and that's the way I think it should be. Part of the goal would be to get binary interop between programming languages, so global analysis isn't feasible (Wasm won't do dynamic linking in MVP, but it's a high priority). Plus, I'd like a language that supports "on-line" rewriting where debuggers or profilers or loggers can transform the code at runtime.

I think there's a good chance that there's an existing system somewhere we should start from, rather than starting from scratch. Perhaps we should start from one existing back-end and one existing "modular" programming language (I don't recall seeing any languages before that were designed to be "modular", but I know that many languages consist of highly orthogonal parts, which is ... similar.) So we should be on the lookout for prior work. I don't have access to (closed) academic journals... but the web probably has adequate info.

[jonathanvdc]

Well, isn't Lisp a (more or less) "modular" programming language? It has macro support, its code is data, and its syntax is fairly regular.

The features you're proposing (like run-time code rewriting) seem pretty neat. But they're also a lot of work, up to the point where they almost seem to necessitate a separate VM. Now, I'd sure like to build a VM, but to me it kind of makes sense to start small and focused; get the language itself right, before building lots of cool tools.

How about one of us creates a prototype repository, and we start working on this thing's syntax? We'll have to at some point, so why not right now? Otherwise, we'll probably just end up in endless feature discussions without writing a single line of code. Plus, building a parser and a number of sample programs will likely give us a better idea of which features are useful, and which aren't.

Also, I see that people are starting to notice LeMP. That's awesome. Congrats!

[qwertie]

I have a name idea: "clasm": Common Language Assembly, a cross between the ideas of Common Language Runtime and WebAssembly. This word doesn't look popular on google (although someone already wrote "a Clojure library designed to convert jvm assembler into bytecode" by this name), and while clasm.com is taken, I could pick up the .org.

[qwertie]

I should have been more clear. LISP is traditionally dynamically typed. I want something that is statically typed, with a modular type system - so that new typing mechanisms can be added. Also, I really don't like s-expressions - ironically, though LISP theoretically has "modular" (or at least replaceable) syntax, everybody just uses s-expressions. I really want to get away from that. Could say more later, gotta go.

[jonathanvdc]

"clasm" sounds good, albeit a bit low-level. Though I guess that's kind of the point, right?

Not a fan of S-expressions, either. It's easy to lose track of nesting. Maybe I wasn't entirely clear, though. I'm not advocating we create yet another dialect of Lisp, but I do think that some of its design decisions are worth considering, despite its syntactic flaws.

What do you have in mind for a "modular" type system, implementation-wise? Something macro-like, like alt class, but more powerful (i.e. on the semantic level)? I suppose this could enable users to define custom types, especially if "fundamental" operators, such as the dot (.) operator, could be overloaded.

About that low-levelness. Do you want clasm to provide low-level primitives, and then expect users to build high-level macros, effectively making it both a low-level and a high-level programming language? Or do you want it to be an actual assembly language that is targeted by compilers for high-level programming languages?

[qwertie]

See "typing according to Qwertie" - I'm interested in a layered type system. So yes, it would have low-level primitives and high-level macros and typing modules, making it low-level and high-level language at once. I do not envision ordinary users creating type-system modules or even their own macros, but that several parties could contribute parts of the language.

At the lowest level, perhaps there needs to be a built-in notion of physical types - the language would define a type system required for memory safety, but it should be fairly unconstrained. For instance, a structure like

struct Foo {
  double a; int32 b;
  Foo* next;
};

Could be seen as 12 bytes of "don't care" (for memory safety they don't matter) and 4 or 8 bytes of ptr<Foo> depending on memory model. Once a GC system is added to Wasm, that would be added to the base type system, too. Now, perhaps the lifetime system from Rust should also be part of the lowest level of typing (or it could be considered the second level, but still built-in). Maybe array slices have to be typed too, and the tags in tagged unions, where a tag determines if a blob of memory is "pointer" or "integer".

Other ideas of type would then be added as layers, with an unlimited number of types per value. I have no idea how to take the mathematical approach, where a type system could supply "proofs" of correctness, so instead we'd probably just let type system modules do "transmutes" (unsafe casts) and worry about their own correctness. At least typing modules that don't do transmutes should be guaranteed memory-safe (if not necessarily correct).

I imagine three kinds of typing, and each kind could have multiple modules:

1. Physical (float vs int, Foo vs Foo*). This category includes the lowest level and "views" built on top, e.g. int, uint and float are 3 views of the same bits.
2. Semantic (int has range 12...64, bits 0 and 2 set, represents a quantity of eggs). The defining characteristic of this category is that a program can still compile when a purely semantic module is disabled.
3. Naming (what methods and operators exist in relation to this value?)

Typing that is concerned with memory safety in the face of allocations and deallocations, i.e. lifetime analysis, has elements of the first two (it's "physical" in that it provides memory safety and "semantic" in that it does not affect code generation or even care about memory layout). I expect other modules may be multi-category, e.g. if a module merely requires proof that an int is in range 0..100, then it's purely kind (2). On the other hand, if two functions can be overloaded based the different integer ranges they accept, that's more of a (3) thing.

My idea is nebulous. We should look for prior work. One thing is, I want to write some software in Rust to get a better feeling for how it solves things, then think about what can be changed to increase its flexibility.

[qwertie]

Other research TODOs here. One thing I want to stress is that the different notions of type can be independent. For instance, suppose a value is measured in metres. In a traditional type system you'd have either metres<int> or int<metres>. But in both of these formulations, one of the types (int and metres) "knows" about the other. That's wrong. Also, traditionally there is only one way that types are inferred - often bottom-up and top-to-bottom, e.g. in var x = 4*6 + 8.0*3.0; Foo(x); the type is determined by looking at the "leaves" of the first statement and solving "up" the tree, then moving on to the second statement.

But when you see different ideas of type as independent, each one can have its own system for "solving" the type of each value has. For a unit system with types like kg/mol or m/s/s, bottom-up and top-to-bottom is very inconvenient - it requires a lot of unit type annotations in the code. It's much better to have an inference system, like I made back in university. Also, not everything needs to have a unit. The way I designed my unit system, any program that had zero annotations would still compile, and you could add units to a program incrementally; it would always compile as long as there were no contradictions. (Actually, it would always compile - unit errors were just warnings)

[jonathanvdc]

That's a really cool approach to typing, actually. I wouldn't include a lot of primitive typing disciplines, though. Over-designing the type system for a few specific scenarios, like Rust's lifetime system, would make the type system less flexible, in my opinion. Typing modules should just have the right tools to do that kind of thing themselves.

There's something you wrote that I don't quite understand though: how could metres<int> not know that its underlying type is an int? How else can you distinguish a metres<int> from a metres<double>? Do you mean that you'd rather just write metres x = 3; and have the compiler infer that x : metres<int>, or is it more of a fundamental issue?

Thumbs up for type inference. Powerful type inference makes programming fun, in my opinion. But if we're doing type inference, then I suggest we get rid of function overloading sooner rather than later. Type parameters are far more effective at achieving compile-time polymorphism than overloading, especially when they're combined with sufficiently powerful constraints, like typeclasses or interface constraints. Constructors may be an exception to this rule, though, and I'm unsure how those should be handled. Perhaps a new object construction paradigm is warranted? Implicit conversions also complicate type inference, though they can be pretty useful at times.

On a side note: I implemented Hindley-Milner type inference a while back. Is your unit inference algorithm similar?

[qwertie]

It seems to me that a certain amount of "primitive typing disciplines" (if I understand your meaning - and I don't necessarily) are necessary to let the other type checkers build on top and enjoy memory safety.

I suspect Rust's lifetime system doesn't reduce flexibility, because... imagine a program that wants to just use garbage collection and not worry about lifetimes. GC objects can have a lifetime of 'static (forever), which allows them to be passed to any method. On the other hand, without GC, some technique is needed for memory safety, and lifetimes are the best technique I know of.

Using the notation metres<int> implies a relationship that metres knows about int, which isn't necessary. My unit inference engine didn't care about the physical type at all; a unit of m (metres) could be applied to int, double, FixedPoint8, string, object, or whatever. It was a completely separate type system, and you'd write something like len = 5m`` to assign "5 metres" to the variable len. `len`'s physical type is `int`, and its unit type is `m`. The unit inference engine probably does need to know about "containment"... for instance, given

class Point {
   double X, Y;
}

There ought to be some way to specify that X and Y have the same unit as their containing type. I didn't get around to working out that problem.

Unit inference is only like Hindley-Milner in the general sense that you scan the program figuring out types as you go along using some unification rules.

Again, I'm proposing unit inference, NOT general type inference. I know general type inference doesn't get along with overloading, but overloading is really useful so ... I'd have to think long and hard before removing it. You may be right, but I want to get experience with Rust first (to better understand how they deal with overloading being missing). I've used Haskell for a few months, but that language is so wacky, it seems to occupy a different part of my brain and I'm not prepared to apply it to "normal" language design. Rust is nice because it bridges the gap.

Most likely some basic overloading could be allowed in any case (e.g. different numbers of arguments). I don't think unit inference needs to care about overloading: the unit checker could simply run after overloads are resolved (though this does imply that you can't overload functions based on unit types).

[qwertie]

I would point out that in the kind of language I'm proposing, it could have both type inference + overloading disabled AND no type inference + overloading allowed. After all, the coexistence of substantially different type systems is really the goal here. It's just that presumably we'd have to pick one system to be the default. But Loyc is about interoperability, and I still think that "one compiler, multiple languages" could be a fruitful approach to interop. Of course, we'd need to solve the problem of how to allow the language-with-type-inference to call arbitrary overloaded functions... from the user's perspective, I think he'll just need to be more explicit about the types of the arguments to the function, so that overload resolution works.

[jonathanvdc]

Actually, even if implementing the Rust lifetime system as a built-in feature doesn't force anyone to use it, I'd still rather figure out some way to provide low-level type system hooks. A Rust-style borrow checker could then be built on top of those hooks. But I also expect to be able to implement a GC, or Go's local variable references, on top of those hooks, without built-in support for either.
Moving these things from the compiler to the typing modules results in a separation of concerns, anyway. It'd make building the compiler itself easier, and there'd probably be fewer bugs.

I wouldn't dismiss the possibility of applying Haskell to "normal" language design out of hand. In my understanding, typeclasses are just like Go-style interfaces, which are instead used as generic constraints. They avoid the pain of copy-pasting the same function over and over again for all (numerical) types. They're also the moral equivalent of Rust's traits. If one ignores multi-parameter typeclasses for a minute, then what's not to love?

I'm a little puzzled as to why you'd want unit inference as a core feature which is on-by-default, but not type inference. Even Rust has type inference, and I can't say I've ever used units in F#, which has unit inference. C++ has units, too (no unit inference, though), and I've only used them once, because the standard library forced me to. C++ units were more of an inconvenience, really. That's just anecdotal evidence, though.
Don't get me wrong: I think unit inference is neat. But I'm not convinced that it's quite as useful as type inference.

Splitting these ideas up into a type-inferred language and an explicitly typed language would make sense, I suppose. And interop between those two languages would then probably require some thought, as well. But let's not get ahead of ourselves here. Building one awesome programming language should be challenging enough for now.

Perhaps a list of MVP-ish features for said language would be useful. It'd reveal which features are priorities and which ones aren't.

[qwertie]

I'm not sure what you mean about using "hooks" so that Rust-style lifetimes are not a core feature... but whatever you're thinking of sounds good. I'd need to see a more detailed and concrete design sketch.

Actually, Haskell type classes are very much like Rust traits, and not like Go-style interfaces. As I understand them, Go-style interfaces are more flexible than both. I think this flexibility limitation has a name in Rust: "trait coherence". I'm having trouble finding a definition of this term though. And in fact, these concepts aren't fully clear in my own mind (that's part of the reason I want to work with Rust for awhile.)

I don't want unit inference as a core feature. It is merely an example of a type system module that could be written. It is a useful example to show how different concepts of type can be independent. It is worth noting that if a unit inference module exists, it should be on by default, because unit information should be stored in compiled DLLs for interop purposes. For example, a unit inference engine will detect that the function

static int Square(int x) => x * x;

Has a polymorphic unit type of U => U^2 for some unit U. Even if this DLL never uses units, it is useful to store this information so that a different module that relies on units can interoperate with this one. Then again... I guess the unit types could be detected after-the-fact, by loading the DLL and analyzing it to reconstruct missing unit information.

Sigh. F# ... I've never been able to get used to it. The OCaml subset I can handle, but things like writing constructors, and other OO stuff, is way too hard and confusing in F#, I just fought with the compiler constantly and the syntax of everything was baffling. So I never got as far as trying out its unit system. Whether units are worth using depends on how easy it is; in many languages, units are a burden because they are overly infectious - when you start using them, the compiler starts requiring unit annotations all over the place. In languages like C++, units are definitely not worth using - the language just isn't designed for units, and you only get unit checking, which is horrible compared to unit inference. I don't know if F# makes units friendly enough or not.

I don't know if I was clear. I'm not saying "let's build a language with two type systems". I'm saying "let's build a language with unlimited type systems - two of them might be like these". And these type systems wouldn't be monolithic and totally separate, but modular, and sharing parts between them. Among the things I want to figure out are (1) how to allow interop between type systems that are incompatible in some ways, and (2) what kind of type system is the most flexible, so that it accommodates or "subsumes" the type systems of most existing languages. Now, in order to answer these questions, I think it would be instructive to actually try to implement two type systems that are traditionally considered incompatible, and see what we can learn from that experience.

[jonathanvdc]

Why would you say that Go interfaces are more flexible than Haskell typeclasses? Granted, Go-style interfaces don't have to be implemented explicitly, but in my understanding, typeclass instances can be declared pretty much anywhere. So - like Go-style interfaces - typeclasses don't impose the same implement-at-definition limitation that traditional interface types impose.

Oh. I see. I thought you wanted to make unit types built-in. I was confused. Sorry about that.

Your example is interesting. It seems to imply that one entity can have more than one "type." Seems promising.

Looking at different type systems and figuring out some way to unify them sounds like a good approach. Which type systems would you suggest we implement?

[qwertie]

Let's continue in #26.

[qwertie]

I think I should rename this repo to ecsharp, in order to free up Loyc for something that is not focused on .NET. GitHub is supposed to support automatic redirects. Likewise I'd migrate most of the .NET stuff to ecsharp.net.

I finished the LeMP reference manual BTW.

I was also thinking of creating an organization called Loyc. Unfortunately there is a problem: there is already a user named Loyc ... with no repos, no commits, no activity of any kind.