Success := It comes to me

So, I realized that my previous musings of library and language separation are quite irrelevant. After all, I already was describing systems of compile-time function manipulation. So one simple idiom later, and those problems are, well, clearly resolved.

GenerateCode(function) {
    // Generate your own code from the contents of function here
    // And emit the result as output from the process
    // completely by-passing the main compiler
    // Alternatively, compile for JVM or CLR or whatever you feel like
}

main() {
    GenerateCode(real_main);
}

real_main() {
   // Really run the program here
}

Meta-programming is so powerful.

In other news, the parser construction is going a lot more solidly. I grabbed Bison 2.5 using Cygwin, and it's considerably more impressive than it's previous version. Adding a var keyword quickly resolved my ambiguity problems (turns out you can't function call and function define in the same scope, so all I had to do was disambiguate variables from everything else). All I'm doing now is wrapping up actually creating the AST, making sure the lexer has been updated with all the changes, and then it's time to semantically analyze, and by that, I mean get meta-programming. After that, all that's left is code generation, and probably updating for everything I notice I've forgotten. For example, right now, I've got no initialization lists in constructors, whoops.

I've actually been seriously considering implementing for JVM and CLR. They would hardly be the most maintainable Java/C# code you ever saw, but I think I can make it work. It would certainly increase the probability of the language being adopted. I even think that it can be implemented as a library, which would be so sick.

Oh lord, I might actually succeed.

Language and Library separation, and some Library plans

Library and language separation. When the language is simple, then it's easy to enforce a separation. However, as the language becomes more complex, then it's getting more difficult. For example, earlier, I posted about the need for a Standard.Map -like structure to define the type 'type' by. It would be much easier to recycle those definitions of how a Set should behave, not least easier for the implementers.

What I could do is simply leave the type as undefined, and merely mandate that 'type' can be used. In conjunction with the language providing an explicit cast in situations where it's needed, this should allow the type 'type' to be part of the Standard library, and even inherited from. What I don't like about this approach is that you could never write your own Standard library for a specific implementation, even with a copy of the operating system and processor architecture documentation. I guess that I'll have to live with extending that definition to "implementation documentation". Hell, it's not like you couldn't write- and use- your own compiler- at compile-time- and then run the resulting code- at compile-time- and use it to compile your own program-  if you really, really, really wanted to, I guess.

I should just include a note in the "Standard" saying, quite clearly, that the implementation shall document all APIs necessary to implement the whole Standard library.

Maybe I should begin constructing an actual Standard document. It would be much easier to have a full reference of all my ideas, it would be easier to communicate with people, and it would be easier to make sure that I haven't missed anything. Of course, a Standard is not an actual Standard without a long, drawn-out ISO committee waste of time. But a full specification would be an advantage.

Library changes. Firstly, as you may have gathered, there's now the use of sub-namespaces (the existing std namespace was way too cluttered). The containers will go in, imaginatively, Containers. I'm going to strip the unordered containers and call them hash instead, e.g. HashMap. That's just more descriptive. In addition, I will add an unordered_vector. The main difference between Vector and UnorderedVector is that you could call unordered_vector just a bucket full of stuff- for example, you can erase O(1) by swapping to the end and then popping off the back.

Most things will remain mostly the same, but I'm definitely going to introduce a full range object and use it where appropriate to simplify the use of algorithms, and cut the number of overloads of many functions drastically and use named parameters instead- especially functions like constructors. Strings, I am so cutting the string/wstring debacle and just going to go UTF-16. Java and C# and Windows are all UTF-16, and I figure that it's just the most compatible way to go. I'm not sure about what the new IOStreams are going to look like, but they're certainly not going to look like the current ones. For example, I am leaving buffering to be an implementation detail and not going to define any of it in my interfaces, and I will probably go back to templates instead of virtual functions for polymorphism.

In addition, I'm going to add some more functional algorithms, like map and reduce, and I've talked about some Interop functionality. I also want to add some Standard GUI code. Honestly, the point of Standard GUI libraries is not to be the latest and greatest in GUI work, but something simple and functional that can be used to create simpler GUI applications.

I'm also definitely considering adding support for DSLs for some relatively ubiquitous languages like SQL (i.e., kind of like LINQ but it'll suck less in terms of error reporting) or XML as Standard.

Threading. I don't want to just wrap atomic operations or mutexes. I want something along the lines of TBB  or PPL. I want something smoother, more integrated. I also need to address the use of compile-time threading, which is something I want to hide from the user. I definitely don't want to force serialized compilation, but I also need to perform sometimes complex mutations at compile-time, and I'm going to need a powerful threading library to support that, and possibly a couple of language additions too.

I've also been thinking about mathematical support. Let's face it, there's really no need for everyone to define their own Point class or their own Vector3 class or their own Rectangle class. The Standard can provide that. Everybody's life would be much easier if the Standard provided a little more in terms of BLAS support. 

I also want to version the library separately from the language. If there's a problem, I want it resolved sooner rather than later. I don't want stuff that's bugged sitting around for a decade before it gets fixed. In addition, I want to be able to provide full source code for all functionality that isn't compiler, OS or processor specific- that is, all functionality built on functionality from the language. If I'm going to say "You must provide SharedPointer", then I want to have source code that is portable to show for it and say "Well, if you can't be bothered to write your own, here's mine so just copy and paste it and you're done".

What I will definitely not do is ever refer to the C or C++ Standards, or include the C or C++ Standard library. If I ever see anyone tag an SO question "DeadMG++/C++" without discussing interoperation, I'll flip my brains.

Another problem I've been considering is variadics. Ultimately, I feel like now that we can produce complex data structures at compile-time, they should be part of the library. However, I'm not totally sure how I could retain the relatively seamless integration of variadics, mostly as relates to deduction. Of course, now that regular iteration over them can be done.

I guess that ultimately, "DeadMG++" really offers a new style, where functions and types are generated, and there's old-style "C++" where they are just literals. The new style is much more powerful and flexible, but the old style can be easier to use.

Legacy types, type baggage, and CamelCase

I've been thinking about clearly separating some functionality out into a standard Legacy namespace. For example, function pointers. I already had plans to Standardise a small JIT functionality, and this will give me the opportunity that I need. I want to make it very clear that function pointers should not be used for regular code anymore.

func(float, float) -> int {
    return 1;
}
std.functional.function(int(float, float)) my_func(func);
std.legacy.function_jit("cdecl", int(float, float)) my_func_jit(my_func);
std.legacy.function_pointer("cdecl", int(float, float)) my_func_ptr = my_func_jit; // implicit cast


Other things I'm expecting to put in the legacy namespace will be tools for dealing with C-strings, for example, as well as (maybe?) things like error codes. Perhaps instead of legacy, it should be interop, and I'll add things for dealing with things like BSTRs, other string encodings, that kind of thing.

Another thing I've been thinking about is type baggage. For example, if you look at a C++ type, then they don't just have member functions and member variables (and static variables)- they also have typedefs and constants, which I am terming compile-time baggage. Now, in "DeadMG++", the simplest way to do this would be to just pack the baggage into a struct. However, of course, a struct is not a type and cannot be used to declare types, which would be somewhat problematic. Fortunately, casts are here to the rescue. Effectively, this would be given the same treatment as bool- language constructs which expect a type, such as variable definitions, would explicitly cast the result of any expression to 'type'. Of course, users might find that an implicit or even automatic cast would be the right thing to do, but that's none of my business.

More, I've been thinking about naming conventions. I always have a naming convention problem. I suck up the naming convention of code I'm using like a vacuum cleaner, which makes my code a bit rough when I'm dealing with std::vector<T>::push_back() and ReadFile in the same code. That's why I've decided that "DeadMG++" will use the Windows API conventions- which are also followed by C# and (close to) Java. That is, I will likely use things like Standard.Legacy.FunctionPointer, as opposed to std.legacy.function_ptr. Oh, and I also decided to use the dot notation for namespaces- they're objects like everything else, right?

The simple fact is that now that using definitions are not broken, then you can effectively re-name it however you like, and it also makes using verbose names much less of a big deal. You can see this in C#- who complains about System.Collections.Generic.Dictionary? Nobody, because everybody just does using namespace System; using namespace Collections; using namespace Generic;.

GPU parsing?

See, I figure that, in any specific program of a non-trivial size, there must be millions of statements and/or expressions that are only a few characters, and that they could all be lexed and parsed in parallel. This sounds lik a job for a GPU- massive parallelisation on a task. The only problem is that lexing and parsing will be very branchy integer code and GPUs prefer less branches, more floating-point. I wonder if it would be viable?

Apparently, Fermi (and likely AMD's new architecture) offer equal 32-bit int and 32-bit floating-point performance. Still very branchy code... but that's what mass parallelism is for, amirite?

Now, first you need to know the scope you're in - type, namespace, function. Consider the ANTLR grammar for a namespace:

namespace_definition: 'namespace' identifier '{' 
    (variable_definition | function_definition | namespace_definition)+ 
'}'

The "Parallelize Me" sign here is that big plus sign saying "One or more". So we start off in serial, and let's say that we find the namespace token, and we know we're in a namespace. What we do is we find the terminating '}', so we know everything up to that point is a sequence of (variable_definition | function_definition | namespace_definition). The trick to the parallelising here is that each of them is clearly delineated. Let's have a further look at the definition of these rules.

variable_definition : [stuff] ';'
function_definition : 'function' [stuff] '{' [stuff] '}'
namespace_definition : 'namespace' [stuff] '{' [stuff] '}'

Once we have the list of contents of the original namespace, we just search through it and partition off all the contents into their separate rule invocations. Another sweet trick here is that we don't need to know the difference between a function_definition and a namespace_definition to parallelise at this point- we only need to know where they lie. Once we've separated out the invocations, we just stick them in a list, and parse them in parallel.

Now, an important point is that this is only partially independent. For example, inside the curly brackets, you need to know whether you're a namespace or a function before you can parse the contents. Once you know, however, the above rule can be trivially re-applied, until you reach the "atom" of the grammar- expression-statements. Haven't come up with any way to parallelize the parsing of individual expressions- most. Some, like indexing expressions, can be parallelized and importantly, type_literals indeed can also be parallelised, should I choose to include them. However, I'm going to go out on a limb and say that in a non-trivial program, there could be millions of expressions.

Now, ideally, I'd split this workload up into two segments, CPU and GPU parsing. CPU parsing will do the initial separation work- basically, determine all the expressions. The GPU will then parse all the expressions. Of course, since C++ AMP doesn't exist yet, then I have no desire to actually write a single line of GPGPU code and will probably just stick to CPU parsing, but it's an interesting idea.

Literal syntax

I've been thinking again about literal syntax- that is, defining type literals.

type t = new type;
t.public_functions.insert("DoStuff", [&](this) {
        return 1;
});

type t {
    DoStuff() {
        return 1;
    }
}

Is the first form really that bad? I could just cut the second form entirely. It would be a bit ... strange, I guess. The literal is more natural. But I honestly can't think of any reason to actually keep it, and ditching it would save the grammar from having to deal with it. I could also avoid having to deal with "this" as a keyword- along with many other keywords I've managed to eliminate. Like, say, dynamic_cast, and new. I wonder if the other cast keywords can also be eliminated?

If I went with form 1 instead of form 2, I could have public/private/protected just as strings.

Could it also be used to remove declarations/definitions? I mean as an implementation detail. When a function is added to the type, then it doesn't have to make full semantic sense until the pass is complete and the type is instantiated. Adding the function would effectively "declare" it. If all functions were written in Form 1 instead of Form 2, then I would never need declarations.

The problem is that some devs may well find it unintuitive. It's one thing to attract people with "You can do whatever the hell you want" and another to say "You have to write in this new crazy syntax". And what about free functions? Whilst it would be great to transform Form 2 into Form 1, I'm not sure that dropping Form 1 would actually be a smart idea.

Lexing and parsing

So, I manually constructed a working lexer. It wasn't that tough. Now when I'm constructing a working parser, it's getting a little tougher, although on the plus side, the parallelisable design is going to be sweet. Consider the following:

vector(identifier) var;

versus

vector(identifier) { }

Owch. This gets even hairer if I start passing, say, a lambda to my metafunction. Now, I believe that this is resolvable, but, well, it would be difficult. As such, I've decided that pretty much the only unambiguous way to make this work is going to be to introduce a "function" keyword.

function vector(identifier) {} // I'm a function!
vector(identifier) var; // I'm a variable!

Earlier decision points will make it much easier to parallelise, as well. I also decided to, well, flat out ditch type literals, and for the same reason I will probably not bother with initializer lists either- or certainly not to begin with. I will now do

t = []{ 
    type t;     
    // some more stuff
    return t;
}();



The previous system will be, quite simply, not in the language. Hopefully once the parser is completed, I can begin working on the semantic analyzer and get back to posting about something that isn't either grammar or theory.

Ultimately, the grammar can be fine-tuned later. What I need to do is get cracking and finish a parser that can do more than just parse namespaces, which it currently can but that's not terrifically impressive, and then I can get cracking on semantic analysis.

Mutable Types Part 2: dynamic

Another implication of mutable types and unified compilation is dynamic. Here I'm referring to the specifier used in .NET 4 to refer to types where operations are determined at run-time, and the compiler will accept anything. In "DeadMG++" then we can implement it as a library using mutable types. dynamic will operate like boost::any does in C++ in terms of holding and storing any value. The new trick is how it can be operated on dynamically- that is, when you attempt to access a member or function, then a new one will be generated and added, and implemented or thrown on.

type dynamic = struct {
    type base = struct {}
    std::unique_ptr(base);
public:
    dynamic(object) {
        type derived = struct : base {
            decltype(object).remove_reference() value;
            // implement constructors & etc
        }
        base = std::dynamic_allocate(std::unique, derived, forward(object));
    }
    // etc
};
dynamic.on_change(
    event = member_variable_access,
    action = [&](name) {
        base.public_functions.insert(
            name := "__" + name, // reserved names
            function := [&](this) {
                if (decltype(this).has_public_variable(name))
                    return dynamic(this.name);
                else
                    throw std::no_operation(...);
            },
            virtual := true
        );

    }
    // Repeat for member function
);


This is, of course, somewhat simplified pseudo-code. I haven't gone anywhere near locking down the API of type. However, I hope that you can get the gist of it.

One language that can do dynamic types, static types, type inference, meta-programming? Now that's what I call generic.