Monte Compiler Ramble

Writing compilers is hard. I don't think that anybody disputes this. However, I've grown frustrated with the lack of compiler performance and robustness in the Monte toolchain. Monte will have a developer preview release in a few weeks and I need to get some stuff concerning compilers out of my head and onto the page.

Monte, the Mess

Right now, Monte is in the doldrums. We have deliberately wound down effort on features and exploration in order to produce a developer preview meant to pique interest and generate awareness of Monte, E, object capabilities, etc. As a result, it's worth taking stock of what we've built so far.

Monte's reference implementation is embodied by the Typhon VM, a JIT written in RPython which implements the runtime and interpreter, but does not do any parsing or expansion. Typhon is satisfactory, performing much like early CPython, and outperforming E-on-Java by a bit. However, its JIT does not provide any speed boost compared to interpretation; our execution model is far too sloppy. Additionally, the JIT is fragile and crash-prone as of writing, and we have it disabled by default.

Our current method of execution is to load Kernel-Monte, compile it to an in-memory bytecode resembling, but slightly different from, Smallcaps; and then provide user-built objects which interoperate with runtime objects and internally run this quasi-Smallcaps bytecode.

Performance is behind CPython by a serious but not insurmountable margin. This is unacceptable. One of the goals of Monte is to, by virtue of being less dynamic than Python, be faster than Python in execution. It's been a truism of compilers that lower expressiveness correlates with greater optimization opportunities for a long time, and clearly we are missing out.

Monte, the Metalanguage

A non-trivial portion of the ideology of Monte, which I did not realize when I first embarked on this journey, is that Monte is really an object calculus of some sort; it hides beneath it a simple core language (Kernel-Monte) that turns out to be a very simple universal computer based on message-passing. Almost everything that makes Monte distinct as a language is built on top of this core, from promises and vats, through modules and quasiliterals, to the entirety of the safe scope. The only gnarl that I have found while working with this core, in honesty, is the semantics of mutable names (var x := f()), which I am still on the fence about, but overall is not a tough complication. (Specifically, I don't know whether mutable slots should be created by a virtual machine instruction, or a primitive _makeVarSlot object.)

Unfortunately, Monte's metalanguage doesn't exactly correspond to anything in the literature. Worse, it somewhat resembles many different things in the literature simultaneously, making the choice of techniques much harder. Computer science, as a discipline, has developed an amazing corpus of compiler techniques, but they do require one to already have committed to a particular semantics, and choosing the semantic and evaluation model for Monte has been a challenge.

I'm only one person. Whatever I end up using has to be comprehensible to me, because otherwise I can't build it. This is unfortunate, as I'm something of a dunce, so I would prefer it if my semantics were simple. Additionally, typing is hard and it would be nice to find something easy to implement.

As a brief aside, I want to emphasize that I am not going to talk about parsing today. Monte's parsing story is very simple and solid, and the canonical expansion from Full-Monte into Kernel-Monte is also relatively well-understood. I want to talk about the stuff that makes compilers hard to scale; I want to talk about optimizations and modelling of semantics.

When I say "semantics of Monte" today, I am referring to the bundle of concepts that represent Monte's evaluation at its lowest level. Everything I'm talking about today starts at Kernel-Monte and (hopefully) only goes downward in expressiveness.

Monte, the Schemer

Strange as it might seem to children like myself, Monte is actually descended from Scheme via E, and this manifests in E's actor-like concurrency and also in the E documentation, which discusses E as a variant of lambda calculus.

What Maps Well

After slot expansion, (set!) bears clear similarity to the behavior of mutable names with VarSlot.

The general design of lexically-scoped closures on objects, and thus the optimization patterns, appear very similar between Monte and Scheme. For example, this commit was directly inspired by this Scheme compiler optimization, posted to Lambda the Ultimate a week prior.

List patterns are present in some Schemes, like Racket, and Monte's list patterns are still present in Kernel-Monte; one of the few explicit type-checked kernel situations. (I think that the only other one is the if expression's test… We don't currently require bindings to be :Binding.)

What Maps Poorly

Exceptions are the obvious problem. (call/cc) provides undelimited continuations, but ejectors are explicitly delimited continuations. Something like Oleg's shift/reset semantics, or Racket exceptions, provide sufficient structure to recover the semantics, but the difference is clear. Oleg only outlines how things work; he does not offer hints on optimization. There is a standard suite of optimizations on continuations when using CPS (continuation-passing style); however, CPS massively complicates implementation.

In particular, when using CPS, all method signatures are complicated by the transformation, which means that tracebacks and other debugging information have to be munged more. We also lose our "no stale stack frames" policy, which informally states that we don't have coroutines nor generators. The CPS transformation generally generates a form of code which should be run as a coroutine, with a live (delimited) continuation passed in from the runtime. This is not impossible, but it is a drastic shift away from what I've studied and built so far.

Since Kernel-Monte is an expression language, a desugaring from def to some sort of intermediate let is highly desirable. However, I have attempted to build this algorithm thrice and been stymied every time. The corner cases are constantly recurring; even the canonical expansion is sufficient to send me into fits with some of its pathological generated code. I've concluded that this transformation, while something I dearly want, requires much more thought.

What Isn't Clear

A-normal form sounds so enticing, but I can't articulate why.

Monte, the Talker

Monte's family tree is firmly rooted in elder Smalltalk-80, and incorporates concepts from its parents Python and E, cousins Ruby and JavaScript, and of course its {famti} Java. Our family is not all speed demons, but many of them are quite skilled at getting great performance out of their semantics, and our distant cousin Lua is often on top of benchmarks. We should make sure that we're not missing any lessons from them.

What Maps Well

We can suppose that every object literal is recurrent in a scope; it has some maker, even if that maker is the top-level eval(). In that sense, the script of an object literal, combined with the closure of the object literal, is just like a description of a class in a class-based language with no inheritance. We can even add on Monte-style extends object composition by permitting subclasses; there is no this or self, but the subclasses could override superclass methods and we could use the standard method cache technique to make that fast.

We have two more layers of boxing than most other object-based languages, but that doesn't seem to really impede the otherwise-identical "pass-by-object" semantics of Monte with pretty much every other language in the family. Our JIT has definitely proven capable of seeing through FinalSlot and Binding just like it can see through Int.

What Maps Poorly

Our family tree really should have a strict line in the sand for scoping rules, because half of the family doesn't have static lexical scopes. Much of what has gone into making Python fast, especially in the fast implementations like PyPy and ZipPy, doesn't apply at all to Monte because Monte does not have dynamic scopes, and so Monte does not need to recover static scoping information in the JIT.

Our static scope, honestly, works against us somewhat. I can't help but feel that most of the quirky design in Ruby and Python bytecode is due to not being able to erase away lots of scope semantics; contrapositively, Monte is actually kind of hard to compile into lower forms precisely because the static scoping information makes manipulating terms harder. (This might just be me whining; I mean "hard" in the "lots of typing and thinking" sense.)

We really do need a "deslotification" system of some sort. I've thought about this, and come up with a couple conceptual systems that generate type information for slots and erase bindings and slots during compilation when it can prove that they're not needed. Unfortunately, I haven't actually implemented anything; this is another situation where things are hard to implement. Once again, this is relatively untrodden territory, other than the word "deslotification" itself, which comes from this E page. Interestingly, I independently came up with some of the schemes on that page, which suggests that I'm on the right track, but I also learned that this stuff was never really implemented, so maybe it's a dead end.

What Isn't Clear

Bytecode seems like a good thing. It also seems like a serious albatross, once we start picking on-disk bytecode formats. I'm not sure whether the Smallcaps construction really is the best way of modelling the actions that Monte objects take.

Paths Unpaved

There's a couple options available to us that are relatively orthogonal to what I've talked about so far.

LLVM is the elephant in the room. It is an aggressively-optimizing, competent code generator for anything that can be put into a standard low-level-typed SSA form. For Monte, LLVM would enable a compilation strategy much like Objective-C (or, I imagine, like Swift): Arrange all objects into a generated class hierarchy, prove and erase all types to get as many unboxed objects as possible, and then emit LLVM, producing a binary that runs at a modest speed.

The main trick to LLVM that I see is that it appears to dictate a semantic model, but that is only because we are looking at LLVM through its intended lens of compiling C++, from which Objective-C appears the closest relative to Monte. However, there exist LLVM-targeting compilers which emit code that looks quite alien; the example that comes to my mind is GHC's LLVM backend, which generates the same graph-reducing machine as GHC's native backend. There's no reason that we could not pursue a similar path after figuring out our semantics.

Another growing elephant is Truffle. Truffle is much like RPython, providing pretty much the same stuff, but with two important differences. First, Truffle itself is not translated in the same way as RPython; there's a complex interaction between Truffle, Graal, and the JVM which produces the desired JIT effects. RPython's complexity is mostly borne by the compiler author; the fanciest switch on the panel of a translated RPython program is the one that controls the JIT's parameters. Truffle lets you pick between multiple different JITs at runtime! This is partially due to choices made in the JVM ecosystem that make this preferable.

The second different is worth emphasizing, just because it matters deeply to me, and I figure that it surely must resonate with other folks. Truffle is not a meta-tracing JIT like RPython, but a partially evaluating JIT. This is both a solid theoretical foundation, and a recipe for proven-correct aggressive optimizations. In benchmarks, Truffle does not disappoint. The only downside to Truffle is having to write Java in roughly the normal Java-to-Python proportions instead of RPython.

We could write pretty much anything in Truffle that we could in RPython; thus, sticking with RPython for the accumulated knowledge and experience that we have on that platform makes sense for now. A Truffle port could be done at some point, perhaps by the community.

Monte, the Frustration

I hate via patterns. But only as a compiler author. As a writer of Monte code, via is delightful. When compiling via patterns, though, one has to extract the guts of the pattern, which turns out to be a seriously tricky task in the corner cases. It's the kind of thing that even production-quality Haskell compiler libraries flinch at handling. (As a corollary, if I understood the Haskell bound package, I would be writing one compiler, in Haskell, and nothing else.)

DeepFrozen proof obligations really should be discharged at compile time whenever possible. They aren't really that expensive, but they definitely impose some running overhead. Similarly, a specializer that could discharge or desugar things like (0..!MAXSIZE) would be nice; that single expression was 20% of the runtime of the richards benchmark recently.

To be more blunt, I like partial evaluation. I would love to have a practical partial evaluator for Monte. I also don't feel that Monte's current semantics are very friendly towards partial evaluation. I really do want to lower everything into some simpler form before doing any specialization.

In Conclusion

In conclusion, I need a vacation, I think. If only there were a Python convention coming up…

~ C.

Last modified on 2016-05-02 21:02:00

Mont is a Category

I've had a lot of thought about Mont. (Sorry for the rhymes.) Mont, recall, is the set of all Monte objects. I have a couple interesting thoughts on Mont that I'd like to share, but the compelling result I hope to convince readers of is this: Mont is a simple and easy-to-think-about category once we define an appropriate sort of morphism. By "category" I mean the fundamental building block of category theory, and most of the maths I'm going to use in this post is centered around that field. In particular, "morphism" is used in the sense of categories.

I'd like to put out a little lemma from the other day, first. Let us say that the Monte == operator is defined as follows: For any two objects in Mont, x and y, x == y if and only if x is y, or for any message [verb, args] sendable to these objects, M.send(x, verb, args) == M.send(y, verb, args). In other words, x == y if it is not possible to distinguish x and y by any chain of sent messages. This turns out to relate to the category definition I give below. It also happens to correlate nicely with the idea of equivalence, in that == is an equivalence relation on Mont! The proof:

  • Reflexivity: For any object x, x == x. The first branch of the definition handles this.
  • Symmetry: For any objects x and y, x == y iff y == x. Identity is symmetric, and the second branch is covered by recursion.
  • Transitivity: For any objects x, y, and z, x == y and y == z implies x == z. Yes, if x and y can't be told apart, then if y and z also can't be told apart it immediately follows that x and z are likewise indistinguishable.

Now, obviously, since objects can do whatever computation they like, the actual implementation of == has to be conservative. We generally choose to be sound and incomplete; thus, x == y sometimes has false negatives when implemented in software. We can't really work around this without weakening the language considerably. Thus, when I talk about Mont/==, please be assured that I'm talking more about the ideal than the reality. I'll try to address spots where this matters.

Back to categories. What makes a category? Well, we need a set, some morphisms, and a couple proofs about the behavior of those morphisms. First, the set. I'll use Mont-DF for starters, but eventually we want to use Mont. Not up on my posts? Mont-DF is the subset of Mont where objects are transitively immutable; this is extremely helpful to us since we do not have to worry about mutable state nor any other side effect. (We do have to worry about identity, but most of my results are going to be stated as holding up to equivalence. I am not really concerned with whether there are two 42 objects in Mont right now.)

My first (and, spoiler alert, failed) attempt at defining a category was to use messages as morphisms; that is, to go from one object to another in Mont-DF, send a message to the first object and receive the second object. Clear, clean, direct, simple, and corresponds wonderfully to Monte's semantics. However, there's a problem. The first requirement of a category is that, for any object in the set, there exists an identity morphism, usually called 1, from that object to itself. This is a problem in Monte. We can come up with a message like that for some objects, like good old 42, which responds to ["add", [0]] with 42. (Up to equivalence, of course!) However, for some other objects, like object o as DeepFrozen {}, there's no obvious methods to use.

The answer is to add a new Miranda method which is not overrideable called _magic/0. (Yes, if this approach would have worked, I would have picked a better name.) Starting from Mont-DF, we could amend all objects to get a new set, Mont-DF+Magic, in which the identity morphism is always ["_magic", []]. This neatly wraps up the identity morphism problem.

Next, we have to figure out how to compose messages. At first blush, this is simple; if we start from x and send it some message to get y, and then send another message to y to get z, then we obviously can get to x from z. However, here's the rub: There might not be any message directly from x to z! We're stuck here. Unlike with other composition operators, there's no hand-wavey way to compose messages like with functions. So this is bunk.

However, we can cheat gently and use the free monoid a.k.a. the humble list. A list of messages will work just fine: To compose them, simply catenate the lists, and the identity morphism is the empty list. Putting it all together, a morphism from 6 to 42 might be [["multiply", [7]]], and we could compose that with [["asString", []]] to get [["multiply", [7]], ["asString", []]], a morphism from 6 to "42". Not shabby at all!

There we go. Now Mont-DF is a category up to equivalence. The (very informally defined) set of representatives of equivalence classes via ==, which I'll call Mont-DF/==, is definitely a category here as well, since it encapsulates the equivalence question. We could alternatively insist that objects in Mont-DF are unique (or that equivalent definitions of objects are those same objects), but I'm not willing to take up that sword this time around, mostly because I don't think that it's true.

"Hold up," you might say; "you didn't prove that Mont is a category, only Mont-DF." Curses! I didn't fool you at all, did I? Yes, you're right. We can't extend this result to Mont wholesale, since objects in Mont can mutate themselves. In fact, Mont doesn't really make sense to discuss in this way, since objects in sets aren't supposed to be mutable. I'm probably going to have to extend/alter my definition of Mont in order to get anywhere with that.

~ C.

Last modified on 2015-07-21 14:33:00

Monte: Types

In type-theoretic terms, Monte has a very boring type system. All objects expressible in Monte form a set, Mont, which has some properties, but not anything interesting from a theoretical point of view. I plan to talk about Mont later, but for now we'll just consider it to be a way for me to make existential or universal claims about Monte's object model.

Let's start with guards. Guards are one of the most important parts of writing idiomatic Monte, and they're also definitely an integral part of Monte's safety and security guarantees. They look like types, but are they actually useful as part of a type system?

Let's consider the following switch expression:

switch (x):
    match c :Char:
        "It's a character"
    match i :Int:
        "It's an integer"
    match _:
        "I don't know what it is!"

The two guards, Char and Int, perform what amounts to a type discrimination. We might have an intuition that if x were to pass Char, then it would not pass Int, and vice versa; we might also have an intuition that the order of checking Char and Int does not matter. I'm going to formalize these and show how strong they can be in Monte.

When a coercion happens, the object being coerced is called the specimen. The result of the coercion is called the prize. You've already been introduced to the guard, the object which is performing the coercion.

It happens that a specimen might override a Miranda method, _conformTo/1, in order to pass guards that it cannot normally pass. We call all such specimens conforming. All specimens that pass a guard also conform to it, but some non-passing specimens might still be able to conform by yielding a prize to the guard.

Here's an axiom of guards: For all objects in Mont, if some object specimen conforms to a guard G, and def prize := G.coerce(specimen, _), then prize passes G. This cannot be proven by any sort of runtime assertion (yet?), but any guard that does not obey this axiom is faulty. One expects that a prize returned from a coercion passes the guard that was performing the coercion; without this assumption, it would be quite foolhardy to trust any guard at all!

With that in mind, let's talk about properties of guards. One useful property is idempotence. An idempotent guard G is one that, for all objects in Mont which pass G, any such object specimen has the equality G.coerce(specimen, _) == specimen. (Monte's equality, if you're unfamiliar with it, considers two objects to be equal if they cannot be distinguished by any response to any message sent at them. I could probably craft equivalency classes out of that rule at some point in the future.)

Why is idempotency good? Well, it formalizes the intuition that objects aren't altered when coerced if they're already "of the right type of object." I expect that if I pass 42 to a function that has the pattern x :Int, I might reasonably expect that x will get 42 bound to it, and not 420 or some other wrong number.

Monte's handling of state is impure. This complicates things. Since an object's internal state can vary, its willingness to respond to messages can vary. Let's be more precise in our definition of passing coercion. An object specimen passes coercion by a guard G if, for some combination of specimen and G internal states, G.coerce(specimen, _) == specimen. If specimen passes for all possible combinations of specimen and G internal states, then we say that specimen always passes coercion by G. (And if specimen cannot pass coercion with any possible combination of states, then it never passes.)

Now we can get to retractability. A idempotent guard G is unretractable if, for all objects in Mont which pass coercion by G, those objects always pass coercion by G. The converse property, that it's possible for some object to pass but not always pass coercion, would make G retractable.

An unretractable guard provides a very comfortable improvement over an idempotent one, similar to dipping your objects in DeepFrozen. I think that most of the interesting possibilities for guards come from unretractable guards. Most of the builtin guards are unretractable, too; data guards like Double and Str are good examples.

Theorem: An unretractable guard G partitions Mont into two disjoint subsets whose members always pass or never pass coercion by G, respectively. The proof is pretty trivial. This theorem lets us formalize the notion of a guard as protecting a section of code from unacceptable values; if Char is unretractable (and it is!), then a value guarded by Char is always going to be a character and never anything else. This theorem also gives us our first stab at a type declaration, where we might say something like "An object is of type Char if it passes Char."

Now let's go back to the beginning. We want to know how Char and Int interact. So, let's define some operations analagous to set union and intersection. The union of two unretractable guards G and H is written Any[G, H] and is defined as an unretractable guard that partitions Mont into the union of the two sets of objects that always pass G or H respectively, and all other objects. A similar definition can be created for the intersection of G and H, written All[G, H] and creating a similar partition with the intersection of the always-passing sets.

Both union and intersection are semigroups on the set of unretractable guards. (I haven't picked a name for this set yet. Maybe Mont-UG?) We can add in identity elements to get monoids. For union, we can use the hypothetical guard None, which refuses to pass any object in Mont, and for intersection, the completely real guard Any can be used.

object None:
    to coerce(_, ej):
        throw(ej, "None shall pass")

It gets better. The operations are also closed over Mont-UG, and it's possible to construct an inverse of any unretractable guard which is also an unretractable guard:

def invertUG(ug):
    return object invertedUG:
        to coerce(specimen, ej):
            escape innerEj:
                ug.coerce(specimen, innerEj)
                throw(ej, "Inverted")
            catch _:
                return specimen

This means that we have groups! Two lovely groups. They're both Abelian, too. Exciting stuff. And, in the big payoff of the day, we get two rings on Mont-UG, depending on whether you want to have union or intersection as your addition or multiplication.

This empowers a programmer, informally, to intuit that if Char and Int are disjoint (and, in this case, they are), then it might not matter in which order they are placed into the switch expression.

That's all for now!

~ C.

Last modified on 2015-07-04 18:20:00

Valid CSS!