Lambda the Ultimate

(no message body)

I have done no measurements in this regard, but if Haskell can, I guess Scala can, too.

I think the Scala compiler was in the 10k lps range or less the last time I looked (a few years ago to be sure), while performance depended wildly on what type system features you were using. For comparison, C# and Java are in the 1 million lps range and that's pretty consistent. But there is less code to compile, so it doesn't feel that bad (implementing an IDE is tough though).

I'm not sure how Haskell get's away of 100k lps. Perhaps the Haskell type system doesn't do non-deterministic lub computations, or doesn't have an extensive implicit mechanism? Would love to see formal benchmarks on various compiler performance, especially for very typed functional languages (Haskell...Scala...F#).

I think you have to distinguish between the speed of the language compiler and the speed of a compiler written in that language. As Scala compiles to Java, Scala could be as fast as Java is. The actual speed of course depends on the kind of Java code the compiler is compiled to.

As Scala compiles to Java, Scala could be as fast as Java is.

This is not necessarily the case, and it doesn't even place an accurate upper bound on performance.

For example, there are many ways to encode pattern matching, especially on types, and the performance details will depend on the performance profile of (a) your back-end instruction set architecture (b) the amount of memory the (virtual) machine allows you to allocate [this can be important for special cases like nested pattern matching, since the code generation strategy here can be easily combinatorially explosive if naively coded]

I used to be able to point out differences in VB.NET and C# and could explain why VB.NET would be more efficient than C# in some cases, due to slight differences in their component models, but my memory is fading and I haven't compared the generated IL across the two languages in 3 years. You could do certain encodings in VB.NET that would compile down to a single IL instruction, but in C# you would have additional overhead.

I know there is one such case where VB.Net uses an IL facility for filtered exception handling that C# entirely ignores (see Partition II, Section 18.4 for some of the details). Ignoring it is probably for the better, its a very thorny area.

Early on, VB.Net lacked an equivalent of the C# "as" expression, for combining a type test with a cast avoiding both double-checking and exception-throwing. That changed a long time ago, though.

I share a vague recollection that there are a few other corners along the same lines.

I thought that they were going to use Scala as some sort of embedded DSL, rather than to build a compiler. For the former, Scala compiler performance is definitely relevant because you are essentially reusing it as your own, while for the latter it doesn't matter.

The speed of the Scala compiler has nothing to do with the target platform, most of the time is spent in the type checker.

I agree with the intuition that subtyping is part of a clean solution here, and I'll have a look at case classes.

Concerning "all objects can be Null", this seems to make things worse rather than better. Leg selection is presumably eliminated, but at the cost of a failure to check.

But your comment does raise an interesting point: things like "option 'a" induce lots of union leg checks. The particular case of "nullable 'a" may be sufficiently common and important to justify language support by doing the checks automatically and throwing some form of exception. This is a point I had not previously considered, so thanks for provoking the thought. :-)

The particular case of "nullable 'a" may be sufficiently common and important to justify language support by doing the checks automatically and throwing some form of exception.

Don't most languages with option types provide a library function that does just that? For example, the option type in F# has a Value method that gets the value if it has one and throws an exception otherwise.

This corresponds to my rather unscientific intuition (perhaps informed by the short series of IR's in Appel's "Compiling With Continuations") that 1) with no type discrepancies, one "transforms" (or accumulates information, etc.) using a given IR; otherwise 2) when encountering any type discrepancies, one instead "translates" to the next IR in a series.

For the basic semantic analysis and typechecking phases, two to four IRs can be quite manageable if your implementation language has decent pattern matching and algebraic datatype support.

A variant of this is the first solution that Mark and I came up with. We concluded that it doesn't work well. The graph has internal cycles (e.g. decl node points to def and vice versa). This means that the graph cannot be regenerated by a bottom-up rewrite in any simple way.

Let's simplify slightly, and assume that only the symbol resolver and the type inference passes are responsible for filling in fields after construction. If we can make it work for these, we can probably extend the solution to other cases if they arise.

The tacit assumption when multiple levels of IR are proposed is that we always proceed from the less populated AST to the more populated AST. Unfortunately, this isn't true. Many passes proceed by performing local rewrites on the AST graph and then re-running the symbol resolver and type check passes to re-construct the resolver- and type-related fields. Until the resolver and checker are re-run, we have what can be viewed as a mixed-type AST.

The alternative, I suppose, is that we strip back the more decorated AST to the minimal form, and then re-run the resolver and checker to regenerate the enhanced AST. That seems like a lot of redundant work.

I guess further discussion is going to hinge on the other details of your compiler design. From your response it would appear that you are planning on doing quite a bit of AST rewriting, and I am wondering whether you plan on using this strategy for optimization or just for desugaring complex syntactic forms into simpler ones. I have found rewriting, rebuilding, or otherwise molesting ASTs to be extraordinarily frustrating in the past and have finally rid my compiler of AST-based strategies for optimization and code generation and would counsel against it unless your implementation language has excellent support for pattern matching. Instead I am firmly of the opinion that ASTs should be decorated only, and the decorations--e.g. resolved symbol references--should guide a translation to an intermediate representation that is appropriate for advanced optimizations, without necessarily any resemblance to an AST.

Compilers--fast, optimizing ones, at least--seem to have this unfortunate curse that no matter which piece you try to simplify, it complicates all other parts. The art then comes down to choosing where to place complexity, and in some cases centralization works best, other cases decentralization works best.

If I am not wrong about your direction, it would seem you are favoring decentralization, since you seem to be planning many potential passes on this AST. This is going to reduce modularity and hinder the speed at which you can evolve the compiler. E.g. changes to the source language will propagate farther into the back end of your compiler if it is based on ASTs and relies on them for optimization.

So to summarize, my basic argument is that the separation into distinct IRs may not necessarily reduce the overall complexity of your compiler, but it will certainly modularize it and make it easier to evolve.

As for the compilation speed target, coupled with a desire to use the static type system of the implementation language to enforce a higher dimension of correctness than seems to be borne out in existing compilers, and your overall goal of creating a new language, be careful not to ask for too many miracles :-)

My first reaction when reading your question is the same as Oleg's about performance: are you sure that using a map (with a good implementation) is too slow?

Using a language with type inference is convenient for the programmer, but the compiler can still use an explicitly typed IR once you're past the type checker. Having a typed IR might sidestep the specific example you mention about rewriting an AST and having to re-run type-inference afterwards. My experience with augmenting rewrite systems to a typed setting is that it appeared much harder than it actually was once I sat down and did the work.

Having the option of running a type checker after each pass is still very useful for finding and isolating bugs though, and this is one of the things the core-lint mode in GHC does.

+1 for typed IR separate from the initial parse tree. I haven't had the pleasure of working on a compiler that uses an out and out new AST structure, but all multi-phase compilers I've worked on are written to have different assumptions about the AST as you go along. I'm more and more sympathetic to simply having a separate untyped tree and a typed one, and for Java-targeting compilers, perhaps a third AST after type erasure.

Short of having two or more ASTs, though, here are two tricks for having different invariants in the same AST:

1. There can be alternate constructors that take symbols as arguments instead of strings, and that auto-compute the type of the AST at construction time. The parser uses the constructors that take strings as arguments, but most everything else in the compiler uses the constructors that take symbols. It takes some discipline to use the right constructors at the right time, but the nice thing is that the symboly ones tend to be more convenient to use.

2. Adding flags to the AST that you can toggle as the phases go by. If you can't get a static check, then a dynamic check is honestly pretty good in practice. For example, the GWT compiler includes a flag for whether or not you can create new string literals. Once the string interning phase has past, you can't create a new one! The string interning phase toggles the flag, and if you try to create a literal with the flag off, the compiler aborts with an assertion failure.

Speaking of performance, I'd reconsider the off-hand comment about needing to run type checking and/or symbol resolution after the initial type check phase. It's first of all very slow, easily dominating the cost of a phase. Additionally it risks correctness. If you try to build a reference to a variable via its string name, your implementation is only correct if the name lookup in fact gets you back to the right variable. If you build the reference via a direct reference to the variable's symbol, it's foolproof.

I'm more and more sympathetic to simply having a separate untyped tree and a typed one

My old bytecode compiler for Magpie made that exact distinction. The "unbound" AST nodes were what came out of the parser and used strings for identifiers. There was a mirrored set of bound AST classes where references pointed directly to their target.

The main pass of the compiler would take an unbound expression and convert it to a bound one by resolving identifiers and building a symbol table.

It helped me keep things clear in my head about what stage I was in in any given region of code. I managed to minimize code duplication by having the bound and unbound AST classes share a common base class when it made sense. Like so:

// Base class.
public class CallExpr<TExpr> {
    public TExpr Target;
    public TExpr Arg;

    public CallExpr(TExpr target, TExpr arg) {
        Target = target;
        Arg = arg;
    }
}

// Unbound form.
public class CallExpr : CallExpr<IUnboundExpr>, IUnboundExpr {
    public CallExpr(IUnboundExpr target, IUnboundExpr arg)
        : base(target, arg) {}

    public TReturn Accept<TReturn>(IUnboundExprVisitor<TReturn> visitor) {
        return visitor.Visit(this);
    }
}

// Bound form.
public class BoundCallExpr : CallExpr<IBoundExpr>, IBoundExpr {
    public BoundCallExpr(IBoundExpr target, IBoundExpr arg)
        : base(target, arg) { }

    public IBoundDecl Type {
        get { return ((FuncType)Target.Type).Return.Bound; }
    }

    public TReturn Accept<TReturn>(IBoundExprVisitor<TReturn> visitor) {
        return visitor.Visit(this);
    }
}

Simple AST classes like literals would implement both IUnboundExpr and IBoundExpr and return themselves to transform to bound form.

I don't know how well it would scale to multiple passes, but for my very simple compiler it worked OK.

You should only do type inference once- after that, even node in the IR should be decorated with it's type, and IR transforms should maintain the type information. Likewise name resolution- it should be done once, as part of alpha renaming. Name representations can even be changed at that point to something more efficient (like integers).

Defining IRs as variant types have a lot of advantages. For one thing, they can be used to enforce invariants. For example, after lambda lifting, there should be no lambda expressions in the AST- so the post-lambda-lifting IR would simply not have the lambda expression variant. For the general things- such as type validation or debug printing, you can define a superset of all the IRs. Each individual IR just provides a one-way conversion from the specific IR to the generic. For example, the generic IR would need a lambda expression node, but the post-lambda-lifting IR would never generate it. Since you're not going from the general to the specific, a specific instance doesn't have to worry about how to handle those things it doesn't support.

I agree with this answer. As I understood it, point 2 was just about the ability to pass specific node types around, rather than requiring everything be of type Tree - shouldn't be a problem with this pattern. Another reference is the Datatypes a la Carte paper.

I've also used this approach with success. I also used a similar design to support 'open' and extensible types in languages that usually lack them, though that works best if there is a bottom type (bottom type in a variant can eliminate a member of the variant).

Basically, it affirms my fear of commitment. Do not tie the recursive knot until you're forced to do so. :-)

I agree in delaying the recursion. Delaying wrapping up the recursion is necessary as closing the recursion limits reuse. I also find that a pattern of "top level" recursive "closure" is the cleaner design that keeps the overall architecture in control.

The down side is the sometimes large number of functions/functors that needs to be wrapped into the top level "co-recursive" knot. That could be an issue for some, I have found that it pays off.

This approach can become painful to use in practice (at least in OCaml) when the AST is constructed from a number of mutually recursive datatypes. Then you end up having to parameterise by all of the mutually recursive datatypes.

Originally in my compiler I used Ocaml polymorphic variants with open recursion (after getting Ocaml fixed so that polymorphic variants were covariant!).

Now in theory, this is beautiful because the type of every operation can be specified exactly, or as close to exactly as one desires. For example term elimination and introduction. Furthermore there is a huge advantage coding the process because many unaffected terms can just be transfered, and terms only affected by structural recursion mapped. Not only is this nice to code it is efficient because passing these terms across does not require reconstructing them.

Nice in theory, but utterly untenable in practice. When you have 10 term types in the AST alone, you need 10 parameters.. and then you have to provide another 10 fixations to get closed types from the open ones .. and you've only just described the inputs to the first algorithm.

As soon as you try to remove or add terms to describe the output of the first algorithm, you have to write huge wads of it all out again. It is true you can group the summands but doing so requires advance knowlege of what your algorithms do and is fragile.

I never got past a single term split into two: general type terms which included type functions and type matches, and reduced terms (with the type functions and matches reduced away) and in the end we chucked that out because the error messages ended up being 100s of lines (not kidding!).

OK, so now I will mention another approach which helps to solve the problem: get rid of the AST ASAP.

This is what I do. Add a level of indirection. Replace the children in a tree with a synthesised identifer (I use an integer) and then map the integer to the children.

This then requires an extra lookup to do any recursive analysis: but it allows very simple linear analysis and makes it very easy to add extra information with any number of additional maps.

My functional code is instantly lambda lifted, and complex expressions are unravelled into three-address code. Problem of cyclic references are eliminated by the indirection: you can now use multiple maps to aggregate information.

For example, the type of a function can be calculated with a partial analysis without fully binding the function: in Felix I calculate return types by examining the returns of branches and backtracking to find the types of any variables or functions used: if I hit a recursion I just throw that case out and unify the rest (there is always a non-recursive branch or you'd have an infinite loop).

I have to emphasise this isn't a general solution, since as others note it is heavily dependent on the language syntax, semantics, and phasing of calculations. It is particularly difficult in Felix because it uses setwise scoping (everything is mutually recursive without any need for forward declarations) and because it supports overloading as well as ugly things like a typeof operator.

To be sure, whilst the typing problem took several years to get to the current half correct status, a much harder problem still remains: managing optimisation, particularly inlining. Here the typing is no big deal: the problem is efficiently inlining almost everything without duplicating any steps (for compiler performance) and without allowing recursive calls to lead to infinite expansions. I don't know how to do this. I believe this is a much harder problem. It is, however quite similar because one is constantly and simultaneously expanding and reducing terms.

.. without allowing recursive calls to lead to infinite expansions. I don't know how to do this. I believe this is a much harder problem.

There are several ways to avoid infinite expansions. The obvious one is to never inline anything that is recursive, but you already said you wanted to do that. The GHC inliner and COSTA identify groups of strongly connected components, take one function out of it and hope that the remaining parts are not cyclic. If so, you can freely inline the other functions. More details (and heuristics) about GHC (Section 3), and COSTA (Section 6).

If this isn't strong enough there are other options, but performance will suffer compared to the small and local approaches outlined above. The basic idea is that you keep track of (some of) the expressions you've already seen, and if your current expression in hand is related (in a certain way) to any of the previous expressions you need to stop. If I still haven't scared you off, keep reading.

The relation between the terms need to be a well-quasi-order (wqo), which is sufficient to guarantee that you can not create infinite chains of terms without at least two of the terms in them relating to each other. The homeomorphic embedding is a pretty standard one, but there are plenty of small variations to this relation. Ilya Klyuchnikov defines a relation which is not a wqo on arbitrary terms, but it is a wqo on the terms his supercompiler produces. Neil Mitchell uses a different relation.

The presence of types should not cause a problem for the homeomorphic embedding, the (safe) sledgehammer approach is to say that all types are related to each other (a more refined version is do structural comparison on types and consider all type variables equal, so [[a]] is embedded in Maybe [[b]], but not in [a]). The trouble is performing generalization on terms in the presence of types, but luckily that has already been solved.

Your "map/fold objects" technique sounds very much like the standard OO Visitor design pattern. It's typical to define a DefaultVisitor for a particular structure that just performs the "obvious" traversal, so clients just need to override the behavior at nodes of interest, and can also delegate to the super-class to continue the default traversal.

It's fairly straightforward to extend this technique to more ad hoc compositions of unrelated objects (e.g., trees with unanticipated structure). And particularly in a language with parametric polymorphism ("generics" in the JVM parlance) and traits or multiple inheritance, the resulting code can be kept reasonably clean, modular and well-typed.

On the other hand, I don't think this is a complete solution to the original challenge question. A combination of two-level types per Neel's answer and open visitors is probably as close as I know how to get, but I think the challenge remains open.

I wonder whether any of the "XML processing type systems" that were trendy for awhile would have anything to say about this? The job of building/traversing trees of known schema but unknown structure seems like a good match...

I reread my post and thought it wasn't too clear about how transforms are used. An example, replacing each conditional 'if c then e0 else e1' with the equivalent term '[ true -> e0 | _ -> e1 ] c' with a transform which only rewrites the AST.

def remove_ite: reshape unit =
    [ u, expr_ite p c e0 e1 ->
         alt0 = // some code which builds true -> e0;
         alt1 = // some code which builds _    -> e1;
         e    = expr_application p (expr_case p [alt0; alt1]) c;
              remove_ite u e
    | u, e -> reshape_child remove_ite u e ]

A lot of my code looks like the above, it is a very abstract robust approach to writing a compiler.

(Note that it is surprisingly close to neelk's contribution. I just made the decision not to have generic information in the AST, it's a separation of concerns issue I guess. In my view, the AST by definition already holds, or is elaborated to hold, exactly the information to be able to compile - all extra information you are interested in should be reconstructable from it and, if necessary, passed to a transforming function.)

But now that I think of it, all of the fields in the AST divide precisely into two categories:

1. Downward pointers. These constitute a strict tree.

2. Memoization pointers: e.g. the symbol resolution pass updated the defn/decl pointer fields during its traversal.

All of the memoization pointers are nullable in any case. So I think that aspect of my "part 1" can be disregarded.

Years ago I built an attribute-grammar based parser generator, so I'm familiar how these work and I don't see how they help. In a practical AG system you have both synthesized (computed bottom-up) and inherited attributes (computed top-down). In fact you usually have interdependencies between the two types. The attribute-associated fields have to be present in the AST structure when the AST node is allocated, and must be given values at allocation time. These values are then overwritten by the AG traversal pass.

But the same root problem exists: you need a default initializer for the attribute slots long before the correct value is known.

Oh. Maybe you're thinking about lazy attribute grammars (presumably with dynamic cyclic dependency detection and resolution)? The thing you have going for you here is that the attribute value construction can be performed lazily. This means that every attribute access is already wrapped in a get() pattern that is machine-generated, and the union dispatch can be hidden inside the machine-generated get() function. Is something like this what you have in mind?

That's an intriguing approach that I had not considered, and it bears some thinking on. Thanks!

Maybe you're thinking about lazy attribute grammars...

Sorry, yes, this is exactly what I was thinking.

I agree that lazy attribute grammars work well for this problem. I consider the AST to be fixed at construction time. Attributes are essentially memoised functions from AST nodes to attribute values. The laziness (or equivalently, demand-driven evaluation) takes care of dependencies between attributes, so you don't need to explicitly schedule AST traversals.

In our approach, the attribute values are not stored in the nodes. This evaluation method is also used in JastAdd, except that JastAdd is a generator, so they can add fields for the attributes (and methods, actually) to the AST classes at generation time.

We use this approach in the attribute grammar part of our Kiama language processing library for Scala. See this page for a short explanation and simple example. It also extends nicely to fixed point evaluation of circular attribute definitions.

We have some experience with building smallish language processors this way, but can't comment yet on performance when it's used to build large compilers.

"Can you explain more?" is never rude. If the question isn't clear, it needs to be refined to have a productive conversation. If I'm not willing to do that, I shouldn't have wasted everyone's time by asking!

In this case, the strong static typing is in both the compiler source language and the target language, but the language of interest is the source language used to implement the compiler.

Kaminsky-san is correct about the source of cyclic references, and per my response to this comment, I now think I see how that part of the problem can be eliminated.

To explain the problem with map:

There is a type field in every AST. The value of this field is computed by a separate pass, so we need a "neutral" initializer that can be used when the type field is initialized at AST node instantiation time. The only reason for map in this situation is to move the field into a second data structure in order to defer initializtion.

Because the relationship between type fields and ASTs is 1:1, the introduction of a map imposes log n overhead on an every type field access, which is an otherwise constant-time operation. Access to the type field is done pervasively. The added marginal cost imposed by a typical map implementation is therefore bounded below by ((k+1)n log(n))D, where D is the L2 cache miss cost (Interior index nodes in the map will not remain cached in L2 at this scale), n the number of AST nodes and k is the average number of input types that are accessed to compute each result type type during inference. k here is approximately 3, but n here is typically on the order of hundreds of thousands to millions. The killer here is the L2 cache miss latency, which on modern implementations is the high hundreds of cycles if you have an L3 cache (which may be absent on consumer-grade processors). The added cost imposed by the map (or any other comparably scalable indirection) is unacceptable in both relative and absolute terms. It's quite literally naked-eye perceptible.

I haven't collected the numbers you propose. I agree that would be a fine way to examine this if practical experience didn't already tell me that a map isn't a good approach here.

As to added complexity, I don't think that's at issue here. If we don't add a map, then we either need a canary value to initialize these fields (and some reason to think we won't access that by mistake) or we need to "lift" the canary value into type in order to ensure statically that our access pattern actually performs the canary check at all required locations.

Thanks for a detailed breakdown. I also avoid log n access time maps. I try to make every operation constant time when possible. When you say "typical map" it sounds like you're describing a tree. For example, I understand std::map in C++ is a tree, so I never use it (unless following orders). Also, I think some functional languages use tree-based maps to avoid updating old nodes, since tree alteration can be done by patching the path of change, so the new graph simply doesn't refer to old nodes that needed a change.

But even if a hashmap was constant time (because flat and contiguous -- either logically or physically) it sounds like you don't want one because it moves 1:1 info somewhere else unnecessarily. That would only be a good idea if you wanted one side immutable while the other side of the relation varied as different passes of code associated new info each time.

Yeah, cache line misses are very costly. I think of them as "about 100 cycles" times some constant factor that may vary. But sometimes they are necessary. Large hashmaps normally incur at least one miss per lookup; but if lookup is necessary, there's no choice. Also, I use doubly linked lists when I want constant time removal, even though this incurs a miss on both sides -- it's still better than non-constant time.

I'm not trying to talk you into using hashmaps. I meant to suggest when a cache line miss is unavoidable, because of how other things are organized, sometimes the extra data is better organized in a hashmap for lookup, if you can globally optimize how things lay out in relations. But if you're using tree maps, I would try to talk you out of using them.

While I can see (in abstract) how to go about discharging an exception freedom proof in this case, expressing that constraint in a type system lacking dependent types is something I don't see how to do.

One thought: assume you support linear/unique types and strong type updates, at least on phantom types.

The AST is a linear/unique type, and you use phantom types to track the 'maybe' state. When the value is resolved, you can update the phantom type in-place which will propagate up the tree. This being purely a type change operation, it has no runtime cost.

This is really just simulating typestate, which seems closer to what you want.

Perhaps so. But empirical experience with linear types makes me very reluctant to introduce it as a language feature. BitC is aimed at non-research users. As such, there is a class of ideas that are worked out from a formal perspective but still pretty rough from a presentation to users (and therefore utility) perspective that I try to avoid. It is an unfortunate truth that this class of "engineering for utility" work is not something that the current research funding paradigm is effective at funding. The current tech transfer funding paradigm, for its part, is bad at recognizing, examining, and (when appropriate) exploiting the resulting opportunity gaps. It's part of why "deep" research results with "obvious" benefit are hard to translate.

shap

Mozilla's Rust language has adopted typestate for reasoning about these sorts of properties. That's probably the better option here.

Exposing linear or unique types to people writing BitC code doesn't seem too horrible to me. People working at that level should be somewhat comfortable with the idea of using particular values in limited ways, because hardware has fanout limits. If you want to send some computed bits to a million different places, you pay for that in hardware, and the same can just as easily apply in low-level code.