Musings on AOT, JIT and Language Design | Hacker News Reader

Musings on AOT, JIT and Language Design

pointersgonewild.com

51 pointsingve65 comments

Between this post and others like it [1], Maxime Chevalier-Boisvert's ideas sound like they're evolving towards something very much like Julia [2], a dynamic language carefully designed to make ahead-of-time data-flow-based type analysis easy. This analysis allows Julia to achieve performance comparable to C and Fortran. Much of the design involves selecting which aspects of traditional unrestricted dynamism can be given up without compromising usability. For example, function bindings are constant by default, which allows type inference to know with certainty which function object is being called in most function calls. Similarly, since much of the difficulty in optimizing dynamic languages comes from trying to guess the types in arrays/structures/objects, Julia allows programmers to specify these, thereby eliminating this difficulty entirely. More information about Julia's design and implementation can be found here [3].

[1] http://pointersgonewild.com/2012/11/09/static-vs-dynamic-why...

[2] http://julialang.org/

[3] http://arxiv.org/abs/1209.5145

Don't compile to C. It's very difficult to avoid undefined behavior, you won't be able to modify the compiler backend (and you will want to as you start optimizing), you can't add new language intrinsics, good GC is pretty much incompatible with that, and precise control over debug info is impossible. Compile to LLVM IR and/or GCC IR instead.

A long-time disagreement between us :)

> [in C] It's very difficult to avoid undefined behavior,

True, but LLVM IR and other IRs have undefined behavior as well.

> you won't be able to modify the compiler backend (and you will want to as you start optimizing),

Not all languages need backend changes. And you can still add IR optimizations or backend changes that help your language, if you do. Yes, this might not be as easy, but then if you compile to LLVM IR, you might need IR changes for your special things anyhow.

> you can't add new language intrinsics, good GC is pretty much incompatible with that,

Good point, for most GC languages compiling to C is not a good option, which makes sense since C has no GC support.

> and precise control over debug info is impossible.

Yes, but using the C preprocessor you can get pretty far.

> Compile to LLVM IR and/or GCC IR instead.

More power that way, sure, but

1. It limits you to one compiler, while C has many.

2. LLVM IR changes over time (and recently had plenty of examples of this), so you'll need to track that. Whereas C is extremely stable, so long-term, it's much less work.

3. Emitting C is very easy (for those familiar with C), and also very easy to debug.

I think compiling to C is an excellent option. Sometimes better, sometimes worse.

  > True, but LLVM IR and other IRs have undefined behavior 
  > as well.

LLVM IR has less undefined behavior than C, and even despite the reduced surface area frontends have still historically wrestled with taming its UB (both PNaCL and Rust have documented their struggles).

  > It limits you to one compiler, while C has many.

To quote Walter Bright on this topic (which I've linked elsewhere in this thread, but here it is again: http://forum.dlang.org/post/n1vbos$11ov$1@digitalmars.com):

  > 1. You're at the mercy of bugs in the C compiler you 
  >    cannot fix.
  > 2. C leaves quite a lot as "implementation defined", 
  >    causing endless compatibility issues with various C 
  >    compilers.
  > [...]
  > 6. You'll suffer from endless bug reports caused by a 
  >    mismatch between your compiler and the user's C 
  >    compiler, whatever that might be.
  > [...]
  > 10. The order of evaluation of C code expressions is 
  >     implementation defined.
  > 11. Installation problems, again, because you don't 
  >     control the user's C compiler.

Sure, multiple implementations always brings with it those downsides you quoted. Same thing with web browsers, etc. But the benefits of multiple implementations are pretty significant as well, so it ends up worth it in some cases, and not in others.

I agree with the comparison to web browsers, but even then how much deliberately implementation-defined behavior do modern web standards contain compared to C? I can think of Javascript object property enumeration order being unspecified, but nothing else springs to mind.

There's quite a lot, I'm afraid. For example, the precision of sin/cos (this led to bugs on real websites), the precision of random numbers (this led to a bunch of recent blogposts).

And there are also non-semantic differences that end up being important, like one browser running certain things too slowly or taking too much memory.

Multiple implementations is always more complicated ;) But in many cases it's better than a monoculture, in my opinion.

Oh I'm not arguing in favor of a monoculture. But the OP's statement that "This would make it possible to leverage the C compilers that already exist for every platform out there" is naive because C's deliberate flexibility makes cross-platform and cross-compiler codegen fiendishly persnickety.

Meanwhile, the only thing that you gain from all this extra effort is the ability to target platforms that GCC and LLVM don't already support, but these platforms are all likely to be obscure resource-constrained devices, and I just can't see developers on these platforms flocking to such a thoroughly-dynamic language as the OP is envisioning.

Yes, the corner cases are quite bad. But still, C code can be remarkably portable. Back in the older days, using autoconf you could run - well written&portable - C code on a very wide variety of OSes and architectures. Since then both OSes and architectures have consolidated, so it's less noticeable I suppose.

But yes, I agree that in the context of a really dynamic language, it might not be what the author wants anyhow.

IR changes are not that significant. I followed LLVM from nearly the very beginning, and very rarely I was forced to amend something to keep up with the change. The biggest thing in the few past releases was the change in metadata (which got its own class hierarchy, separate from the values).

The very amount of tests in the LLVM source tree ensures that nobody will be motivated to do any significant change unless it is really, really needed, otherwise you'd be forced to do a lot of painful work to update all the tests.

Also, compiling to C pretty much rules out having a REPL for free and all the other fun, while with LLVM it's trivial.

Aside from metadata, some other large changes that have been going on are

* the removal of pointer types (still happening)

* the use/user flip

In my experience these have been significant in the amount of work it takes to track.

Both were not that big - at least not for the C API and text IR users. Worse for the C++ users, obviously, but that was never promised to stay stable and not covered by such a huge number of tests to deter any breaking changes.

Agreed that using the C API can be easier. But for text IR though, the changes were extensive. Scripts were provided that helped, but still, it was a bunch of work to add types/remove types due to the pointer types changes.

Related, here's Walter Bright on the difficulties of compiling to C: http://forum.dlang.org/post/n1vbos$11ov$1@digitalmars.com

Yes, he brings up some excellent points I hadn't considered. Sequence points and integral promotions are bugs waiting to happen.

Why is good GC basically incompatible with compiling to C? Because there's no portable way to scan the stack for live objects?

That, and the fact that you can't tell the compiler that it needs to be aware of pointers that can move across function calls.

In fact, there isn't any dialect of C, standard or not, that I'm aware of that allows you to do this in a fashion that works with precise, moving GC. (Mostly-copying doesn't count.) Maybe C++/CLI, but the object model you're opting into with that brings you so far from C as to barely be considered "compiling to C".

Add a hidden argument to every function marked as capable of transient reference: a pointer to a pointer to a structure (just another object) which serves as a "stack frame". In that function, if you do reference stuff, build your own "stack frame" and use that to maintain a shadow stack. If you allow threads to transiently access objects between "sync points" this won't even be all that inefficient, as you will only be using it to track sub-graph roots as you make calls to other functions... for various reasons many of the more legit mechanisms have that same limitation anyway (where threads are only stopped to be scanned at moments they mark as safe). Maybe you don't consider this to be "good gc", but if your criteria is simply "precise GC with only a minor performance penalty" I don't see any reason to doubt that C is up for the challenge. (And as you are uniquely aware, one would hope that if you were buying the static compilation argument you are also likely to not stress a garbage collector much in the first place, so I would expect the shadow stack to get very little use.) Is there something I'm missing? I really would be interested in a more expansive explanation as to why building a GC with C as a compilation target (as opposed to as a library for people you are expecting to program in C) is considered such a serious showstopping issue.

That's precise GC with a huge performance penalty, not a minor one.

The problem is not so much the spilling and reloading (though that is a large issue) as what that is going to do to the ability of the optimizer to reason about the code.

(If you're curious how I'm so sure it's a huge performance penalty, I have been spending a fair amount of time of the last month working with others to debug large performance problems caused by a variant of exactly this technique used in Servo.) :)

Do you know if you can compile to a text form of the LLVM IR? Also wondering how you'd interface with a GC if you did that.

In Open Dylan (http://opendylan.org/), we have a library of our own written in Dylan that lets us write out LLVM IR in binary files. We have to update it as LLVM changes, but that typically isn't all that bad.

We have some macros and a bunch of functions then that make emitting LLVM IR simpler. For example, the "ins--iterate" and "ins--if" / "ins--else" macros in this code handle phi nodes and so on:

https://github.com/dylan-lang/opendylan/blob/05271f6fec9da05...

This library is currently in the process of being updated from LLVM 3.5 to current HEAD as debug info has changed significantly upstream. After that, we will be landing some documentation for it as well.

If you're interested in learning or hearing more about this, we're typically around on #dylan on freenode IRC.

Yeah, you can compile to LLVM IR in assembly format and then run the result through llc. But you will pay in compilation time for this due to the serialization and deserialization steps, so I can't see a situation in which it'd be worth it to do so.

The LLVM GC interface is controlled through intrinsics, so you can access it through the human-readable IR representation just as you can with the API.

> so I can't see a situation in which it'd be worth it to do so.

The obvious one is not having a giant build time dependency that might change and be at different versions on different platforms. The text interface is far more stable.

The problem I had with doing this is how picky llvm is when it comes to ordering your temporary registers.

As far as I've seen, the text interface is radically more unstable. Like when they recently striped types from pointers, I was like "oh no that sounds like it'll be a lot of work to upgrade to", and all the backend peeps seemed to think it wasn't a big deal because LLVM's API handled it. Particularly when you factor in that any breakage in the direct LLVM API can often be resolved by looking at what Clang did when it upgraded.

That is a shame then.

I believe LLVM IR, even in its textual form, is not considered a stable interface.

It's not, but keeping up with upgrades generally isn't a problem. Not enough to outweigh the downsides of compiling to C.

And to be fair, it's not like the LLVM C API is going to remain the same forever, that changes too.

Last I worked on llvm-c, it was supposed to stay backwards compatible. They do add new functionality but the old API should still work until llvm 4. For rust, while we have been broken by bad code we generated and llvm bugs, I can't recall if the API ever was changed out from under us.

Honestly if you're going to take a step back and consider those things, why not also consider that we already have so many programming languages that it's almost impossible to get to a deep level of understanding of all of them.

Obviously if you enjoy making languages then you should do so - and in that case, noticing that your dynamic un-toolable language won't get wide scale adoption shouldn't matter. It's already a guarantee it won't get that wide scale adoption. Either make your un-toolable language because you enjoy making them, or contribute your efforts to an already popular language that you enjoy. There are tons of interesting problems and huge areas for improvements in every single language.

Don't make a new language for the goal of gaining widescale adoption.

This won't be good advice until it's been at least 20 years since any mainstream language was born. Today, you can point to Go, Rust, and Clojure as counterexamples within the past decade (and if there's a new mainstream language born last year, we probably won't know for 5-10 years).

I suspect what you're trying to say is "don't expect to succeed." That's true--most people will fail, but we should all hope people continue trying, unless we're satisfied with what we have. I'm not satisfied, and I think progress will require new languages, not just improving the ones we have.

Some things require that a lot of people try and fail. Language design is one of them.

I think he's also saying "do it for fun, not for success, have fun doing it", which is good advice IMO.

"and in that case, noticing that your dynamic un-toolable language won't get wide scale adoption shouldn't matter."

That's what I'm reacting to, and I still disagree. People should have an eye on what getting traction would require, even if only a tiny fraction of language designers can make it.

The problem is that a static easily tooled language is not going to be as good as the dynamic un-toolable one without massive tooling support specifically for that language's features. Creating those tools is not the job of a lone developer. The cost is immense. The language first has to achieve popularity to receive the tooling, or be heavily backed by a large tooling capable company (eg, Google, Jetbrains, Microsoft). So far, the only recent languages to receive the kind of required static tooling are from those 3 companies. Also note that the language did not come first in those cases - the requirement for the language came first, and a language was made to fit what was needed.

However even more importantly - if you're going to create a language, it needs to be the ultimate language in your own eyes. You can't leave off novel features that you have experience in because it doesn't have mass appeal or has tooling issues. You need to create the best language you possibly can if you want to compete with others trying to create the best language. Hamstringing your enjoyment of the language by going in a direction you don't like because it has more apparently mass market appeal isn't any more likely to be successful, and it certainly isn't going to be enjoyable enough for you to slog through the tiny complexities.

While there is a tiny chance that your language becomes the next big thing, it probably won't. That means you need to make the language you want to make and hope it succeeds, not make the language that 'will succeed' but you don't want to make.

Your point about support is well taken, but while Rust is being supported by Firefox, it was Graydon Hoare's side project for 3 years. It is at least possible for an individual to run with an idea for a static language and get community or corporate support, even if it is tremendously difficult. And I don't know if you can say that the language sprang from the requirement. It did, so far as a lot of people have had longstanding dissatisfaction with C++, but I'm not sure Mozilla originally was looking for a replacement (ditto for Google and Go--though lessons learned there may not apply to people who aren't Rob Pike...).

I agree with you so far as it can't be a language you don't want to make. I don't think this article describes that, but a more modest set of constraints. Elsewhere, the author mentions Julia as a positive inspiration.

I think the idea of compromise depends on the idea you're trying to bring into the world. You can't compromise your core idea, but you can compromise on other things. I guess I'm making assumptions about what the author is compromising that I'm not entitled to. Perhaps you know that I'm wrong.

The real problem isn't dynamic vs. static and how it affects tools. The problem is that programming languages are made by language designers, when what we would really need are programming experience designers.

We need people that look at the experience of programming as a whole, writing, editing, debugging, profiling, testing, analysis and packaging. People that take all of that into consideration and design languages within that context and under the constraints that imposes.

If you only see yourself as a language designer and ignore the wider context, your language will fail.

What makes you think language designers have no experience of programming? Rest assured that the Simon Peyton Joneses and Martin Odersky's of this world have been doing a lot of programming in their time.

To be sure, they do program applications that are quite different from what 'bread-and-butter' programmers do, and that might influence their taste in programming language features.

I don't think the hypothesis is that language designers have no experience programming, I think it's quite the opposite, that they have experience with poorly designed languages and tools, and perpetuate a sort of stockholm syndrome for the current state of what it means to be a developer.

We need languages designed to be used by future generations of programmers in a world where usability and tools come first. The "Manipulate symbols in this arcane syntax and hit F5/Run until it does what you want" experience is fundamentally at fault. Sure we have debuggers and IDEs, but they're more or less tacked on top of core flaws, things that allow for whitespace formatting debates or semicolon religion. My IDE and my VCS should just edit and encode the AST of my language. The compiler and IDE should share the exact same code for indexing and finding symbols in that AST -- the language acting as a library to the IDE so new releases with new features are automatically understood instead of lots of duplicated language for highlighting/completing/searching every language for every IDE. These are just a couple examples of the ways we're currently living in a state of sin.

Indeed. It's beyond my understanding how one could even consider not providing a public API to the parser, when one develops an interpreter or a compiler. Given all the complexity of such programs, this is trivial.

The standard library of a language should provide access to the parser, so that developers can easily create tools for the language they're using.

Two things:

1) It's not "trivial" -- it's actually a substantial amount of work, especially as the language evolves. How many parsers have you written? Do they have public APIs? Which public APIs to parsers have you used before?

2) It can actually constrain the evolution of the language. IIRC Python has had some non-trivial upgrades that "reinterpret" text with a different parse. If you have to provide parse tree compatibility in addition to text compatibility, that makes changing things harder.

I've noticed that people who have taken a compiler class (often not in C) but haven't worked on "real world" parsers (nearly all written in C/C++) have a very idealized notion of how they behave. Parsers written in C are more often than not tightly coupled to both the lexer and compiler.

Most modern compilers do provide hooks into the compiler. But this does limit flexibility to evolve the compiler.

You can turn the argument around. As writing a parser is near trivial with parser generator tools, parser APIs are not what is problematic with writing tools.

Some (most notably, gcc) are deliberately not providing any external access to the compiler entrails, out of some deranged ideological motives.

You just sang the song of Lisp programmers all over the worlds.

In Lisp basically everyone starts to develop their own languages. Given that most people can barely get a reasonable API together that's just a bad idea.

No disagreement here. I was just pointing out that what the GP wanted already exists in the form of Lisp (with different flavors of macro being different "API" to the parser, so to speak).

It is far, far easier to design a good DSL than to design a usable API.

> My IDE and my VCS should just edit and encode the AST of my language.

People have been saying this for generations. Nobody seems to really believes it enough to step up and try to make it work.

Lamdu[0] is trying it.

[0]https://peaker.github.io/lamdu/

See the JetBrains MPS for example.

    Manipulate symbols in this arcane syntax

People have been experimenting with alternatives to formal languages for decades. Some of the results might have been helpful for beginners, but as tool for expert programmers, formal syntax might not yet have been beaten.

I don't advocate against formal languages, just against using tools that fail to truly comprehend them -- e.g. supporting high-level refactors. I guess I should have said "manipulate by hand" to be more clear.

Many people use software all the time. Software developers obviously do. That doesn't mean they are magically able to themselves create applications that have a good UI and UX. In fact a lot, possibly most, are really bad at it.

The same goes for language designers. I don't think that they have no experience programming, they obviously do. I just don't think that it matters all that much.

Additionally the experience of developing software varies widely. Some use IDEs, some don't, some people use debuggers, others use print statements, some people use profilers, others never have a need to. Even if you have programming experience, your particular experience will be very different from the experience other people have, even developing in the same language.

So no matter how little or much programming experience you have, you can't create a great programming experience based on your experience alone. You need to have an understanding of other programming experiences.

    You need to have an understanding of other programming experiences.

Part of the problem of designing programming languages is that there is little agreement and extreme heterogeneity in the opinions of what is and what isn't a good idea in programming language design. Ideally, PL design statements like "language X is better than Y" should be accompanied by rigorous empiricism. Clearly, the field of PL design has a measurement problem. PL design doesn't have empirically validated and methodologically sound studies that quantify the "dividends" of one PL or PL feature "over another, such as reductions in defects, program size, or development time.

Of course PL development isn't the only field that lacks easy empirics. And PL development shouldn't let the perfect be the enemy of the good. It's quite clear that PL features do have positive productivity consequences, with garbage collection being the most clear-cut example.

The interesting question is what do we do the absence of good empirical methods.

There are several valid answers to this question. One of them is to be strongly guided by mathematical beauty and elegance. This is the family of languages that started with Lisp and is today represented most purely by Haskell, Scala, Clojure, Ocaml and F#. The key ideas from this family: garbage collection, higher-order functions, rich types, have been accepted by the programming mainstream.

One wonders if these ideas would have been discovered if John McCarthy had studied the programming experience of working Fortran / Cobol programmers, rather than Church's purely theoretical lambda-calculus.

In order to have an understanding of what a programming experience is, the designer either has to look at his own experience and also observe others, possibly taking input from likeminded people.

Further than that, in language design you obviously can't do A/B testing, since the cost would be too high, focus groups are in general fundamentally flawed because you can validate whatever you want and UX studies in language design would be too superficial, unless performed for a long period of time, but then you get to the same problems the scientists have to deal with in studies on nutrition.

So unless you're proposing design by committee, which never worked in language design, you tend to get the best results from one language designer that outlays the foundation based on personal opinions and ideally on the prior work of others and is then helped by the community.

I do understand your point on different styles of programming. However you can't please everybody. For example if you choose for your language to be IDE friendly, you end up with Java. Not sure how many people remember, but one reason for why Java EE has been a complete clusterfuck was the IDE oriented design, as in this belief that an IDE can help with the boilerplate and the wiring. The availability of IDEs is also why XML become popular. Even today Java is not usable without an IDE, because Java's libraries have been designed with IDEs in mind and they are too verbose for your brain to even remember the names of methods, let alone the happy path. Ruby's libraries on the other hand have been designed for expressiveness, for being easy to remember, also to counteract the poor IDE support. Neither approach is superior, but the choice in design was very conscious.

PHP and Perl were both written by people actively running into limitations of their existing tools (results may have varied!).

Honestly, I'd reverse it and instead of looking for exceptions, ask which languages the OP was thinking of? I'm sure they exist.

I think you're misunderstanding Daslch. He's saying that language designers should look at the entire user experience of programming. No doubt that language designers have plenty of programming experience.

There are "language designers" who still code, for example Anders Hejlsberg: https://github.com/ahejlsberg

I remember reading papers around a decade ago that combined AOT and JIT advantages by profiling that fed back into an AOT compiler. Even JIT's local optimizations can happen by sending an AST to a client to AOT compile and then run, optionally with a profile to further direct optimization. These kinds of methods, minus profile, were done with agent-oriented tech in 90's and in Juice project that used compiled, Oberon AST's to replace JavaScript.

Most of what we're doing isn't about what's technically the best so much as what was and is popular. That's for backward compatibility, integration, network, and marketing benefits. A clean slate attempt at profiling-guided AOT compilation, at server or binary, could probably match or do a lot better than most modern stuff.

Dynamic features in a language make tools impossible because communication is expected to be one way. The interaction between languages and their tools currently have a rigid design that is shared by almost every modern language.

I would love to see a language that breaks this mold. Where the language and the tools are intimately coupled, or at least had a more complex API. Why aren't the concepts of the convention over configuration movement being pushed further, into the developer workflow and the language itself.

What if unit tests exercising your code was expected, because this is what drives code completion.

How about a community that won't accept a new library as being complete until it hooks into the standardized tools to support its custom macros.

I'd love to see what could happen if we question our basic assumptions of the roles between language, tool, and programmer. What could we do differently if a program was stored as pure AST, instead of a text file, for instance?

> the design of my ultra-dynamic language would make it near-impossible to have much tool support

Dynamic, run-time reflection - yes, it is very harmful indeed. But dynamically extensible parser per se is not an obstacle for tooling.

> If you can hijack the parsing of a program while it’s being parsed, and alter the parser using custom code you wrote, then good luck running any kind of static analysis. It’s just not going to work.

It works. Easily. No problem at all. As long as you can clearly separate compilation time and runtime.

I could easily make any dynamically introduced syntax extension to play well with an IDE without any user effort. Autocompletion, semantic highlighting, type balloons, autoindentation - all the usual IDE stuff.

> Rest assured though, this language will be dynamically typed ;)

This is a big mistake. Dynamic typing breaks tooling, not an extensible syntax.

Smalltalk and Lisp have each had some of the best tooling around and they are both dynamically typed.

Yes. But both failed to deliver the autocompletion the spoiled kids expect these days.

And Lisp is far less dynamic than Smalltalk and the modern lesser toys like Python.

See in ACL2 how a fully static typing can be added on top without a significant change in semantics.

I think static vs dynamic and JIT vs AOT compilers are orthogonal concerns. JIT is alive and well in the JVM and a lot of effort is being put into JIT compilers for JavaScript. And you can certainly write an AOT for dynamic languages which attempts analysis to reduce the cost of dynamic features (type inference, vtable specialization and the like).

If you are interested in languages that compile to C take a look at Nim.

If I were doing a new language I would compile to web assembly.

You can tool for anything. It's a matter of tool coverage. If there are things that circumvent the tooling, that doesn't diminish the tool. It will tend to push programmers not to use those features though (see Aspect Oriented Java for the first few years).

Reply on news.ycombinator.com