3 ms·

For my main compiler project I’ve actually been moving away from this “pipeline” style because it’s inflexible and not great for incremental operations. Inspir

For my main compiler project I’ve actually been moving away from this “pipeline” style because it’s inflexible and not great for incremental operations. Inspired by the Forth dictionary, gradually I’ve arrived at a design where the compiler behaves like a database server—it takes requests in the form of program fragments and produces responses in whatever form you want by querying the database and generating intermediate results as needed. The pipeline is still there, it’s just not hard-coded, and modelled in a more relational way. (I plan on doing a detailed blog post on this after I land the code.) Ordinary compilation? Push a bunch of files and pull the generated code of anything referenced transitively from the program entry point or library exports. Documentation or TAGS generation? Pull the appropriate metadata. Syntax highlighting? Pull the lexical classes and source spans of the tokens—no parsing needs to happen. In general, if you want an intermediate result, you can just ask for it—there’s no hard-coded code path for “run the pipeline up to this point and bail”. The advantage is that this is amenable to producing partial results even when there are program errors—a lexical error doesn’t prevent parsing, it just produces an “error” token that can be displayed in an editor without compromising higher-level features like syntax highlighting, autocomplete, navigation, &c.

seanmcdirmid 9y ago
Many pipeline approaches include error tolerance. I specialize in incremental lexing and parsing for IDEs, and even have experience with some state based error recovery (so, for example, unbalanced braces remember previous brace associations, or a bad transient parse error doesn’t destroy the good trees on the precious run). I don’t see how a database approach would help, you just need to incrementalize the structures in your pipeline (or have reproduceable persistent markers like Eclipse’s elastic positions).
- evincarofautumn 9y ago
  Ah yeah, you can have incremental structures without an incremental pipeline or vice versa, they’ve just worked well together for me.
  - seanmcdirmid 9y ago
    You can make your pipeline mostly oblivious to the incremental nature of each stage, which has some SE benefits. However, I like to run all my phases as damage/repair work lists after the initial incremental lex stage: token changes dirty trees associated with them, putting them in a list for releasing, which then can cause retyping of those nodes, causing those to go on a work list, though the parsing worklist is cleaned before the type checking one before the execution (for incremental live programming) one. I’ve never seen two IDE-oriented incremental compilers use the same approach actually, there is a lot of diversity here.
    - evincarofautumn 9y ago
      That’s an interesting approach. Are you generally working in imperative languages? Last I recall you were using…Scala? I’m new to it, but it seems like there’s a lot of innovation quietly happening in this space. My approach is more like a declarative build system, I guess. To add TAGS support, for example, you add an output that can generate a TAGS file, and declare that it depends on a resolved AST (one with fully qualified names). Then you can make queries like “pull tags from {this set of files, the whole database, everything in this namespace, &c.}”. Dependencies are resolved, and errors reported, mostly automatically unless you want to change the default behaviours. If you want to regenerate tags after changing some input, then as an optimisation you can compute only the diff resulting from whatever dependency was changed upstream (usually a file, ultimately) at the memory cost of caching intermediates (which right now means leaving the server running).
      - seanmcdirmid 9y ago
        I haven't done anything with Scala in a long time. Tree incremental is important for large projects with < 50 ms response times. But it does require memoizing lots of information.

seanmcdirmid 9y ago

Many pipeline approaches include error tolerance. I specialize in incremental lexing and parsing for IDEs, and even have experience with some state based error recovery (so, for example, unbalanced braces remember previous brace associations, or a bad transient parse error doesn’t destroy the good trees on the precious run). I don’t see how a database approach would help, you just need to incrementalize the structures in your pipeline (or have reproduceable persistent markers like Eclipse’s elastic positions).

evincarofautumn 9y ago
Ah yeah, you can have incremental structures without an incremental pipeline or vice versa, they’ve just worked well together for me.
- seanmcdirmid 9y ago
  You can make your pipeline mostly oblivious to the incremental nature of each stage, which has some SE benefits. However, I like to run all my phases as damage/repair work lists after the initial incremental lex stage: token changes dirty trees associated with them, putting them in a list for releasing, which then can cause retyping of those nodes, causing those to go on a work list, though the parsing worklist is cleaned before the type checking one before the execution (for incremental live programming) one. I’ve never seen two IDE-oriented incremental compilers use the same approach actually, there is a lot of diversity here.
  - evincarofautumn 9y ago
    That’s an interesting approach. Are you generally working in imperative languages? Last I recall you were using…Scala? I’m new to it, but it seems like there’s a lot of innovation quietly happening in this space. My approach is more like a declarative build system, I guess. To add TAGS support, for example, you add an output that can generate a TAGS file, and declare that it depends on a resolved AST (one with fully qualified names). Then you can make queries like “pull tags from {this set of files, the whole database, everything in this namespace, &c.}”. Dependencies are resolved, and errors reported, mostly automatically unless you want to change the default behaviours. If you want to regenerate tags after changing some input, then as an optimisation you can compute only the diff resulting from whatever dependency was changed upstream (usually a file, ultimately) at the memory cost of caching intermediates (which right now means leaving the server running).
    - seanmcdirmid 9y ago
      I haven't done anything with Scala in a long time. Tree incremental is important for large projects with < 50 ms response times. But it does require memoizing lots of information.