This is part twenty-four in a series on the language spec for the Merg-E Domain Specific Language for the InnuenDo Web 3.0 stack. This post refers to both version v0.3 and version v0.4 of the language spec. I'll add more parts to the below list as the spec progresses:
- part 1 : coding style, files, merging, scoping, name resolution and synchronisation
- part 2 : reverse markdown for documentation
- part 3 : Actors and pools.
- part 4 : Semantic locks, blockers, continuation points and hazardous blockers
- part 5 : Semantic lexing, DAGs, prune / ent and alias.
- part 6 : DAGs and DataFrames as only data structures, and inline lambdas for pure compute.
- part 7 : Freezing
- part 8 : Attenuation, decomposition, and membranes
- part 9 : Sensitive data in immutables and future vault support.
- part 10 : Scalars and High Fidelity JSON
- part 11 : Operators, expressions and precedence.
- part 12 : Robust integers and integer bitwidth generic programming
- part 13 : The Merg-E ownership model, capture rules, and the --trustmebro compiler flag.
- part 14 : Actorcitos and structural iterators
- part 15 : Explicit actorcitos, non-inline structural iterators, runtimes, and abstract scheduler pipeline.
- part 16 : async functions and resources and the full use of InnuenDo VaultFS
- part 17: RAM-Points, RAM-points normalization bag, and the quota-membrane.
- part 18: Literal operators & Rational and Complex numbers.
- part 19: Interaction between operators, integer bitwidth generics, and the full numeric type-system.
- part 20 (v0.4): Compile-time dimensional analysis, SI/Planck units and the scaling literal operator.
- part 21 (v0.4): Tensors and tensor literals.
- part 22 (v0.4): Deprecating float/complex for rquantity/cquantity for full dimensional type-safety.
- part 23 : Flow control and exceptions.
- part24: The merge parts of Merg-E
- part25: The $threshold keyword and logging.
In this post we want to look at the merge constructs in Merg-E, but before we do, a few fun facts about the naming of the language.
Merg-E is a very much opinionated DSL that connects to 'merge' in multiple ways.
- Merg-E was inspired by a merge of many of the pet peeves that I acquired about programming languages in the 40 years since I first started seriously dabbling with Basic and Forth as a teen.
- Merg-E implements a merge of multiple programming and mathematical paradigms and computational execution models.
- Merg-E builds on the Yggdrasil scheduling and memory management in-memory graph model that aims to provide snapshotability under parallel processing through a git-like merge of mutated data and updated DAG structure into the Yggdrasil branches.
- Imports in Merg-E use the merge command, that implements a contracted surgical import and authority injection for functions inside of modules.
The first two should be apparent from all the earlier posts in this series, so in this post we will look into the last two.
A merge of pet-peeves
I could write a whole post on this subject alone, as I've accumulated quite a few pet-peeves over the years, but I'll keep it short with just two examples: numeric types and reference stealing.
One of my biggest pet-peeves—the resolution of which is part of what makes the Merg-E language highly opinionated, is the use of arbitrary-sized integers.
The problem they attempt to solve is overflow safety, but they do so at a massive price. How in heaven's name is it acceptable that simply adding 1 to a variable containing a huge number can throw a runtime out-of-memory error? In systems and cryptographic programming, allocating storage on demand for numbers destroys both time and memory predictability.
Overflow safety is vital, and Merg-E solves it in a way that many will likely disagree with: using strict, static type-based overflow safety.
Multiply a whole16 by a whole16 and the result refuses to fit into anything smaller than a whole32. If this means static types can rapidly grow to something massive like a whole16384, we accept that. Merg-E deliberately embraces this "type explosion" to avoid the fatal drawbacks of arbitrary-sized bignums. Most importantly for cryptography, fixed-size hardware-aligned integers prevent timing-based bit leakage. Mathematical operations simply don't take equally long with arbitrary-sized integers when comparing smaller versus bigger values, and for a Web 3.0 DSL, side-channel vulnerabilities like that are unacceptable. These needs give me the justification to finally act on a years-old pet-peeve.
A second example of an old pet peeve of mine is reference stealing.
In C++, many years ago, an early smart pointer called auto_ptr was deprecated. Why? Because if you handed it to a function, that function would silently steal the reference, leaving the original auto_ptr empty and prone to causing crashes. For most people using C++, this behavior was unexpected, unintended, and unsafe. From a least-authority and system robustness principle, however, handing over ownership by default is exactly what you want.
In Merg-E, if you declare anything as mutable without explicitly marking it as borrowed or shared, the default behavior when passing it into a function or a closure capture is strict reference stealing (a "move"). The parent scope is left with a "hollow" mutable, which is exactly as designed. Unlike C++, if you try to access that hollow parent again, the Merg-E compiler will immediately throw an error. It forces authority transfers to be absolute and auditable, resolving yet another one of my pet-peeves. Idiomatic Merg-E promotes the usage of copy over borrowed and the the use of borrowed over shared.
A merge of paradigms
Merg-E utilizes an object-capability security model and has support for actors, but unlike historical object-capability languages (such as E), Merg-E isn't an Object-Oriented language. It doesn't have objects or classes. Nor is it really a pure functional programming language either. From a purist perspective, it is a mixture of paradigms that belongs to none of them completely. If forced to categorize it, I would call it a closure-oriented, object-capability language layered with strong (yet deliberately incomplete) scientific computing and dataflow features.
Language naming history
The first working name for Merg-E was simply merge, but because it would be quite a challenge for anyone using Merg-E to find any info on the language named merge I quickly started looking at alternatives.
One alternative naming was edsger after the venerable Dutch computer scientist Edsger Dijkstra, someone even more opinionated than the language, but then after the introduction of the hazardous modifier into the language and the --trustmebro compiler flags, Merg-E is no longer fully in the spirit of the language. The name "edsger" does however survive as the name of the very strict Merg-E linter that is currently under construction.
One of the main ancestors of Merg-E in spirit is the least authority language E, even if Merg-E misses its VAT system and its distributed nature, and it isn't as purely ocap as E, it inherits much of the least authority spirit. After asking the architect of the E language for permission, Merg-E thus ended up with its name.
The hidden merge of program state
Unlike a language like E hat has persistent VATs that are possible because objects don't jump between event loops, Merg-E has a very different concurrency design. All 'merged' program state lives inside of a complex graph of 'scope' DAGs and membranes called Yggdrasil that is managed by the Niðhǫggr scheduler. Niðhǫggr takes a runnable, wraps it in a versionable membrane and puts that membrane into a short per-worker queue for running.
Now when a worker fetches the next entry from this queue, it runs whatever the task needs running until either task completion or in case of structural iterators until a preemption time has passed.
The runnable during this time can make changes to its own scope, but these changes are like local uncommitted changes. The changes to the DAG are made to the versionable membrane as a temporary layer on top of the actual scope DAG. with all changes contained only in the membrane.
Now when the worker completes this runnable's work, it takes the changed membrane and puts it in the merge queue where it stays untill Niðhǫggr has time to process it.
When Niðhǫggr takes the membrane from the merge queue, it attempts to merge the updates with the current real state of the runnables scope DAG, what should normally succeed. If the merge succeeds, the merged DAG will be the new state of the scope DAG. If it fails, the old version is kept and the runnable is treated as if it had never been run, with a short delay on rescheduling. (Future versions may introduce soft failure modes if this turns out needed). It is important to note that the rolback defence of the scheduler is NOT an excuse for the programmer not to use semantic locks!
So consider that Niðhǫggr is doing in-memory git-like merges under the hood all of the time.
The reason for this setup is multifold, but the prime reason during design was to enable a future persistent Yggdrasil that doesn't need to stop the world to do snapshots. While the snapshot feature for a persistent Yggdrasil is still far in the future and not on the direct short-term roadmap yet, the membrane and merge based approach to state is a fundamental aspect of the scheduler and worker design of the Merg-E runtimes.
The merge contract
So far all of the ways Merg-E is a merge or uses a merge described in this post have been under the hood. In this last section we look at the one place where merge enters the actual language syntax.
Because Merg-E is completely closure oriented without some kind of multi-file code merging (imports, etc), programs would be bound to grow very deep nesting with loads of code duplication. To address this, Merg-E has a pair of
language constructs, merge and def that together form a strict contract that combines what is traditionally considered an import with what is considered explicit dependency injection in other contexts.
In a single file context, we use function to define the inner function of a closure. With merge and def, we define the implementation of what is to become an inner function iside of a namespace or ns within a module file, and we define a merge within the outer function. Both contain an extensive contract-half or fingerprint that needs to match in order to compile.
A quick example. Imagine we have an inner function that checks if a whole16 number is a prime number. We don't bother with any implementation right now, but consider it's a parallelizable function that uses a shared mutable to keep track of how many primes it found.
reentrant mutable function is_prime = (x whole16)::{
ok_count: whole16;
}{
...
}!!{
...
};
Here we have the function named is_prime, we let it encapsulate the shared mutable ok_count, so the function itself becomes mutable as well. We promise the scheduler that the function is reintrant with the reentrant modifier. The function takes a whole16 as argument and it explicitly captures ok_count. All normal implicit captures count for inert values in the scope of the outer function. In this example both the function body and the function error body are left unimplemented. These are not that relevant at this point.
But now let's consider we want to move this inner function into a utils module. We now need to define a namespace in that file, and change the function into a def:
ns utils lang {
reentrant mutable def is_prime = (x whole16)::{
ok_count: whole16;
}{
max_prime: whole16;
}{
...
}!!{
...
}@[range_error];
};
Note that just like in an application file, a module file defines a name, utils in this case. And just as in an application file, the language definition needs to be pulled into the file scope with a first statement. A 'ns' or namespace statement in this case. So the above defines an is_prime def within a utils namespace.
One change you will note that there seems to be a second closure capture section where the inert max_prime gets captured, but this is not exactly true in a technical sense. The second section here is a contract statement that tells the compiler that the def expects max_prime to exist in any outer scope it is merged into. All other inert values will actually exist and be accessible from the def body, or they would be if the compiler would allow the code to compile things it can't confirm match the contract. The end of the def expression is new. We see the @[range_error] part. This part declares this function can throw a range_error, and if the compiler determines it might throw any other exception, the compiler will bail out because the implementation doesn't follow the contract.
But now, how do we use this implementation instead of the original function? We do this by using the merge expression:
reentrant mutable merge utils.is_prime as is_prime(x whole16)::{
ok_count;
}{
max_prime;
}@[range_error];
We note that while the implementation is no longer there, it is in the module file now, the merge in the application file and the def in the module file share a compatible contract. Most contract bits need to match exactly, though in some places lenience is provided. For example the application file may choose to omit the reentrant modifier. It is a property that the implementation offers in the module file, but if the application accepts this offer, it simultaneously tells the scheduler that it is willing to let invocations run in parallel. This is an offer the application may wish not to always make the scheduler.
Further note that in the merge side of things the types of ok_count and max_prime don't need to be explicitly expressed as in the module file because these are contained in the captured mutables and inerts themselves.
Conclusions
In this post we looked at the reason why Merg-E is called Merg-E and did a deep dive into the underexpressed aspects of Merg-E so far: The versioning membrane used by the scheduler and runners and the import and dependency injection mechanism provided by def and merge. This post was an auxiliary post meant to fill some minor language definition gaps, and to better communicate what Merg-E is and isn't.
