Compiler IDE API

As I am working (slowly) on a compiler at the moment, I have started thinking about IDE integration. It occurs to me (as I am sure it has to everyone else) that a compiler should not be a command-line program, but a library that can be integrated with applications and IDEs. The command line interface for the compiler should be just another client of the library.

So my question is, in an ideal environment (starting from scratch) what should an API for a compiler (targeting IDE integration as well as other runtime uses) look like? Obviously some method to build the code, some methods for auto-completion, type checking, type inference.

Other thoughts are that all the above functions need to operate in a dynamic environment, where incomplete code fragments exist, without breaking the compiler, and hopefully still offering useful feedback.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Merlin

The Merlin project brings IDE-as-an-editor-service features to OCaml programmers, and had to grapple with some of these questions -- possibly less so than languages like Scala or Kotlin or F# that worked on robust integration within more advanced IDEs, but I'm talking about what I know. Surprisingly few changes to the OCaml compiler were required to provide a good experience in term of type feedback on partial programs. The lexer and parsers were made incremental (this now comes mostly for free if you use Menhir, a parser generator that provides an incremental interface with an incremental interface that provides a first-class representation of pervasive parser state, and a function turning a token into a transition from state to state). The way the type-checker is implemented, which is to mutate inference variables as it goes on making deductions, gives a surprisingly convincing behavior on partial state: when it fails on a hole, you get a type error at the missing point, but the deductions that were made earlier in the program can be read back as a partial typing derivation.

I think that if I had to reimplement type inference (or, say, scope checking) for an IDE handling partial programs I would try to have explicit domain knowledge of partiality and incrementality -- for example as a monad. The important aspect I think is to be as explicit about the dependencies in the analysis; when type-checking a tuple (e1, e2), even if an error occurs in e1 it should be able to go along type-checking e2 nonetheless; whereas a sequential type-checker implementation that is not written with partiality in mind would just stop at e1.

It may also be the case that decoupling analysis phases that are often combined together would improve the user-observable behavior. For example, scoping (which variables exist in the environment, resolution of identifiers to binding sites) is often done at the same time as type-checking, but if you separate them you may be able to go much further in the scoping analysis and provide useful feedback even if your type-checker (which are typically more complex and thus more fragile) gave up on a hole long ago.

If you build your type

If you build your type checker to be incremental in the first place, it isn't going to give up and be fragile. Incremental type checking really isn't that different from incremental parsing using memoization and a worklist algorithm, you just have to handle remote lookup dependencies via a listener list. I don't think you can bolt this on though, type checkers written for traditional batch experiences are just outdated relics of a bygone age.

Hm

My point was not that incrementality support would make the type-checker fragile, rather than type-checker for sophisticated languages (OCaml, Scala, GHC...) are complex beasts in general, and a source of fragility, because of the problem domain itself.

Building an incremental type

Building an incremental type checker is not fundamentally more difficult. Even Scala's type system is fairly easy to make incremental (I did it) sans a couple of issues with impurity that couldn't be memoized very easily (in my case, explicit and implicit case class constructors had a weird first-to-post semantics). It didn't even require many code changes.

Appearance of an IDE could depend

Appearance of an IDE could depend on complexity of a grammar for a language:

  • If the grammar is fairly simple, one might consider completely replacing the editor by graphical code builder.
  • If the grammar is complex, classical text editor might be a better solution.
  • Nevertheless, one might imagine a hybrid solution which could be a graphical IDE for top-level grammar symbols, combined with a text editor for deeper symbols that may vary more in complexity than top-level symbols.

Compiling a source code

Compiling a source code could be separated into several phases. The first phase would compile only top-level symbols, embracing deeper symbols as simple string wholes. The second phase would compile deeper symbol string wholes. And so on recursively. This approach provides a granularity of code that could be partially compiled, with each fragment having its own isolated success/failure result, but implementing a parser that way might cause a few headaches more than implementing a single step parser.

You are really asking the

You are really asking the wrong question "how do I bolt my compiler on to an IDE" when you should be asking "how do I build a nice experience that includes an IDE?" Or maybe I'm just weird in that I start out from the editor first and work my way down to interpretation, there is no other way to do it in the live programming field.

If you just want to bolt your compiler on to an IDE, I suggest you look at existing IDE APIs like Eclipse but also VSCode and so on. Incrementality is easily handled the naive way (damage and repair), more sophisticated algorithms don't work in practice and anyways are unnecessary.

But really, decide what you want your programmer experience to be and start from there, don't work backwards.

Wishful Thinking

My first reaction is that i don't really want an IDE specific to my language/compiler. I was hoping to make integration with existing IDEs easier.

I usually program in 'vi', and find i want my personal programmer experience to be 'thinking'. Most auto-completion just gets in the way, like providing the closing bracket for a function call, when inserting or editing code the IDE nearly always gets this wrong. The assumption that you type code top-to-bottom, left-to-right seems wrong to me.

One thing that does occur to me, is i would like entering value level code, and it's inferred types to be automated somehow. Program modules should have concrete type signatures to define a stable API, yet these types can be inferred from code. Sometimes we want to auto-generate the module signature from the code, sometimes we want the code to be constrained by the module signature. As such it would be great to see the types for expressions dynamically, and be able to extract them into concrete annotations.

See, you don't really want

See, you don't really want an IDE at all. At least, you don't get why those features are useful, they have never been useful to you, or you've never seen a good design of them. So you don't really have the context to do this yourself.

I usually program in 'vi', and find i want my personal programmer experience to be 'thinking'.

Got it: you want Hawkeye (the guy who can shoot arrows with amazing accuracy), rather than Ironman (the guy with the augmented power armor). Programmers should just think harder/better and not rely so much on tools to offload that thinking. I totally disagree, but I think much of the PL community thinks like you.

Most auto-completion just gets in the way, like providing the closing bracket for a function call, when inserting or editing code the IDE nearly always gets this wrong.

Auto-completion is just about API discovery. If you are programming in small libraries you understand very well, then it will be more distracting than useful.

The assumption that you type code top-to-bottom, left-to-right seems wrong to me.

Most code is written top-down, then inside-out, then inside-out again. Anyways, a backward or bi-directional type system helps out here as the type information doesn't need to fly in just one direction, but most people get this wrong.

As such it would be great to see the types for expressions dynamically, and be able to extract them into concrete annotations.

A common use case.

Probably Right

See, you don't really want an IDE at all.

I may not want an IDE, at least not any i have seen, for myself, but i understand other people like them, so i want to make integration as easy and useful as possible.

Programmers should just think harder/better and not rely so much on tools to offload

I don't mind offloading some thinking, for example there is little point in memorising the details of an API when documentation is readily available online. But I do think people need to think architecturally first. I think problems are solved by the application of algorithms, and the abstract form of these should be familiar to the programmer. To build a compiler I need to understand trees as a data structure, I can look up the available functions and syntax easily, but I can't easily do so with understanding the properties of a tree (isomorphisms, algebra of rational trees etc).

Auto-completion is just about API discovery

I prefer to use a web-browser open to API documentation for this, which can explain the algorithm used, invariants, etc.

Most code is written top-down, then inside-out, then inside-out again.

I am not sure i agree with this. Often specific functions can be written and tested in isolation. Fixing bugs mutates the data at "random" points. Bottom-up is an equally valid approach.

It might be that i haven't seen an IDE i like, or maybe nobody has written an IDE for me.

You can always try to write

You can always try to write an IDE for yourself. Think about the experience you want and go for it. Technical know how isn't going to be your limiting problem.

Hazelnut

The integrated IDE/compiler idea must be quite old, but a new look at the idea of semantic editor from a PL point of view has been proposed by Cyrus Omar and his coauthors at SNAPL 2017 (see also their POPL 2017 paper). They explore a “clean-slate” design (echoing your premiss of “starting from scratch”).

Start from the idea that the implementation of a programming language should not just be a compiler, but a library that lets you manipulate the abstract representation of incomplete code. Then it is easy see that everything should remain at a semantic level: one should not just be able to, say, query the (incomplete) type at a location as one would expect from a standard IDE, but also move around in the abstract tree, insert program fragments, and making all sorts of transformations based on the semantics. In fact one wants edition actions rich enough to be able to write the complete program from scratch. The program is no longer a string of Unicode characters but an abstract object edited by means of a 2nd-level language of edition actions.

Then interesting PL questions arise such as "what is an incomplete program?" and "what sort of language makes up the edition actions?". The IDE is some UI to display the program and expose the possible actions; the display of the program itself can be semantic (Omar et al. refer to the projectional editors where the display depends on the type). They also mention the convergence with tactic languages in proof assistants.

The 'Kind' of Parsing Errors

This is a really interesting idea. I think can already answer some of this for my language, which makes this helpful. My intention was to have a Prolog like meta-language for manipulating the AST. Type inference/checking would also be a function of this language.

In light of this comment, it would make sense if all editor operations were defined in terms of this Prolog like meta-language. Complex editor functions and macros would easily fit into this model. The hardest thing to understand is what simple editing (entering characters) would be in this model.

I suppose we can start by typing the empty program, I'll use '[' and ']' to delimit the edited code:

[] : Void
[a] : X
[a(] : Error
[a(x] : Error
[a(x)] : X -> Y
[a(x)=] : Error
[a(x)=>] : {a : X -> Void}
[a(x)=>1] : {a : X -> Int}

It seems what i would need to do is turn any parse error into an 'error' type. Perhaps this should be a new kind, the kind of 'parsing errors'. Actually that makes a lot of sense now i think about it.

Compiler as a Web Service

I've spent a lot of time thinking about how to support compilation as a web service. We have construction of a codebase (via PUT or POST). And requesting various resources (via GET) can access not only the source code but also various optimized, evaluated, and compiled objects that can be derived from the source. (And history, etc..)

One might also 'GET' the result of computing an ad-hoc expression within a codebase via URL parameters. Potentially even subscribe, via Comet techniques (long polling, web sockets, etc.).

My own use case involves programmable wikis or forums, and filling a niche where communities could benefit from sharing free-form computations and data over the network. I'm not particularly interested in conventional desktop IDEs.

The API I've developed has a heavy emphasis on resource control and uses binaries as the basic IO model. The web server can allocate several "contexts" for computation, which are fixed-size heaps and have limited 'effort' quotas. Each context is associated with a dictionary and supports transactional updates to named functions. We can load contexts with binary input, and extract binary output, and evaluate or manipulate the binary in various ways. While the IO is presented as binaries at the API, under the hood a more structured representation would be used during evaluation.

It turns out I don't have much use for presenting the parse trees directly or anything like that. It's just not a great fit for web services.

Why IDE

You already have the ultimate IDE. Its called bash.

The Unix philosophy is to have an integration tool (shell) and a suite of arbitrary assistants (scripts or programs) specialised in particular tasks.

So really an editor which supports pluggable tools is the way to go.

Ideally in todays world you'd use a browser as the editor. That would suit your project well since your compiler is written in Javascript and generates Javascript so eventually you'd bootstrap the compiler so it is written in itself and the editing tools would be as well. So that way they fit nicely with the compiler too.

Don't make the mistake Ocaml did with really silly attribute extension to the syntax as a sop to those that couldn't figure out how make their editors handle extensible syntax. Integrate the editor tooling with the compiler so syntax extensions propagate to the compiler and tools together.

Web Browser

I think a web-based editor and sand-box for the compiler is the right way to go. Unfortunately the ES6 code does not run natively in browsers due to modules etc. I've been using TypeScript and Rollup for another project, and that might be the way to go (or Babel) it should be relatively straightforward as the compiler does not use the DOM or any browser specific functionality.

Generally I am against syntax extensions, it's kind of where Felix diverges from what i am trying to do. I want generics and expressive power, but i also want function application to always look like function application. Although i don't like Lisp as a language s-expressions do this perfectly. In a language of values and functions you don't need any additional syntax beyond '(', ')' and identifiers.

The concept is that polymorphism and type-classes can provide sufficient expressive power, that the syntax for function application and operators can always remain the same. You can create any domain-specific-language you like, but they will all use the same notation for function application and operators.