ltratt

tree-sitter is excellent stuff! It's heavily inspired by Tim Wagner's PhD thesis (original site seems to be down, but https://web.archive.org/web/20150919164029/https://www.cs.be... works). IMHO more people should know about that work, and the sequence of work from Susan Graham's lab that led up to it. We have also been heavily inspired by Tim's work and Lukas's thesis extends and updates a number of aspects of that seminal work including, in Chapter 3, error recovery (https://diekmann.co.uk/diekmann_phd.pdf).

All that said, it's surprisingly difficult to compare error recovery in an online parser (i.e. one that's parsing as you type) to a batch parser. In the worst case (e.g. load a file with a syntax error in), online parsers have exactly the same problems as a batch parser; however, once they've built up sufficient context they have different, sometimes more powerful, options available to them (but they also need to be cautious about rewriting the tree too much as that baffles users).

I think we are in agreement that skipping over large chunks of input is rarely a good idea. In Section 7 ("Using error recovery in practice") we show how you can make fine-grained decisions about what to do when recovery has happened in our Rust parsing system. The more fine-grained you go, the more code you have to write, but it allows you to do exactly the sorts of things that rustc does with structs if you want. https://softdevteam.github.io/grmtools/master/book/errorreco... is a more approachable version of the same stuff.

Co-author here. If you want to quickly play with this on the command-line with your favourite Yacc grammar, a simple way is to use nimbleparse https://crates.io/crates/nimbleparse ('cargo install nimbleparse' should do the trick; though note that you will probably need to munge your lexer a bit). You can see this in use in the paper itself: the examples at the end are direct output from nimbleparse https://github.com/softdevteam/error_recovery_paper/tree/mas.... Some example grammars are at https://github.com/softdevteam/error_recovery_paper/tree/mas... if you want to get going quickly.

If instead you want to use the full set of Rust libraries, a good place to start is https://softdevteam.github.io/grmtools/master/book/quickstar....

Community wisdom has long held that good error recovery is impossible for automatically generated parsers and I unquestioningly accepted that wisdom for years. When I was building a Yacc system in Rust, I eventually investigated further, and found that there's loads of work in this area over several decades. None of it ever found its way into real parsers, probably because it was too slow. I extended some of that work a bit, made it more efficient, and took advantage of the speed of modern machines and now have an approach to automatic error recovery that you have to do quite a lot of work to beat with a hand-rolled parser. More at https://softdevteam.github.io/grmtools/master/book/errorreco... if you're interested!

No.

I don't pretend to have a total picture of all the possibilities, and there's quite a bit of not-always-explainable variation in what I do know, but I think it would be fair to say that people in this field are quite some way from going hungry. It tends to be better remunerated than a typical software gig but it's certainly possible to earn more in AI/ML. A lot also depends on whether you want to be a "normal" engineer or are willing/capable of taking on managerial responsibility.

I lead a PL/VMs/compilers research group and the number of organisations interested in hiring people in this area keeps growing and growing. Now, that's not to say that there are ever going to be hundreds of thousands people working in this field, but it turns out that lots of organisations have realised they have pressing language needs. It varies all the way from those wanting to make mainstream language implementations perform better on their codebases to those wanting to reimplement a major internal language in a modern fashion.

At the moment -- and I expect for the foreseeable future -- demand quite significantly outstrips supply. Because of that, organisations are often quite flexible in how they view potential hires in this area. Simplifying a bit, there are two main ways to get in to the field: obtain specific training in the field (e.g. a PhD); start / contribute to a project (not necessarily OSS) that shows expertise (e.g. if you start filing high quality PRs against Rust or LLVM, people will fairly quickly realise you know what you're doing).

Best of luck -- it's a really fun field, with lots of interesting challenges, and a good group of people!

I completely agree: the poor quality of error reporting in parsing tools is a significant reason not to use them. When I started looking into this a couple of years back, what surprised me is how much work there's been in this spread over decades.

Building upon that (and obvious bias alert!) led us to come up with a couple of new algorithms. The current paper draft is https://arxiv.org/abs/1804.07133 (a future version of that paper will probably chop out MF which, in retrospect, adds too much complexity over CPCT+ for the relatively small gains). The Rust library (https://crates.io/crates/lrpar) it's implemented in is documented at https://softdevteam.github.io/grmtools/master/book/errorreco... which is probably a friendlier starting point. Summary: one can do a surprisingly decent job of error recovery for very little work.

History suggests that, for a good approximation of the truth, the resources put into a language implementation (and, in particular, into JIT compiling VMs) strongly correlate with its performance. So V8 and HotSpot, for example, both have great performance -- and both have had large teams working on them for many years.

Interestingly, PyPy has pretty decent performance despite having had a much smaller team working on it, mostly part-time. An interesting thought experiment is whether similar resources put into PyPy -- or a PyPy-like system -- would achieve similar results. My best guess is "yes".

> Pure compiler jobs are far and wide between.

In an absolute sense, this is true. There are never likely to be hundreds of thousands of compiler jobs.

In a relative sense, this isn't true. I run a PL research group with a heavy focus on (mostly dynamic) compilers, and I've lost track of the number of companies (some obvious, some not) who are desperate to hire people with a compiler background to do compiler stuff. Because there are so few people with suitable training, and as said elsewhere on this thread, industry has become used to taking good people without a compiler background and crossing their fingers that they can learn the ropes -- which good people of course can, given a bit of time. But, in my experience, even groups which are largely staffed with people who haven't done a compiler PhD would love to hire people with compiler PhDs.

Will this always be true? Well, it perhaps wasn't (as) true 15-20 years ago when people often only seemed to care about C++ and Java performance. But, given the continual increase in the quantity of languages that people want to run fast (and, often, on a variety of devices), it's hard to see that happening any time soon.

The problem is more-or-less as bad for a normal distribution as it is for a skewed distribution (I'd have said the distribution from my examples is right skewed, not that it makes any difference to my argument): the minimum gives you no information about the distribution. As Figure 1 of [1] (bias alert: I'm a co-author) shows, it seems that, on modern systems, you can can find pretty much any distribution you want if you have enough benchmarks.

[1] https://soft-dev.org/pubs/html/barrett_bolz-tereick_killick_...

In my experience people think/hope that the minimum tells them the performance of their program when all noise is removed. However, this is based on the assumption that programs have a single performance point which, as the Stabilizer paper shows, is rarely the case on modern systems. Rather, what the minimum tells you is the behaviour of your program at one given point in the non-deterministic performance space. This might seem like a minor, perhaps even a pedantic, difference, but I have found it to be a profound observation.

Imagine, for example, your program has 100 possible ASLR states: in 99 of those states it takes 1s to run and in the 1 remaining state it takes 0.8s to run. Using the minimum, you will think your program takes 0.8s to run even though there's only a 1% of chance of observing that performance in practise. That's bad, IMHO, but the problem compounds when you compare different versions of the same program. Imagine that I optimise the program such that in those 99 slow states the program now takes 0.9s to run, but in the remaining state it still takes 0.8s. The minimum will tell me that my optimisation made no difference (and thus should probably be removed) even though in 99% of cases I've improved performance by 10%.

Benchmarking is hard -- I've spent far more time investigating it then I ever wanted to. Much of the advice in this article matches the advice I give when people are foolish enough to ask me (though CPU pinning can have very odd results for systems which expect to use all of a CPU's cores). However, there are two related points where I respectfully disagree with the author: disabling ASLR is probably not a good idea for most people; and using minimum values is almost never a good idea. Ultimately, the traditional idea that programs have a single performance number doesn't generally hold true on modern systems: one needs to accept that programs have a set of performance numbers. The Stabilizer paper [1] does a very good job of articulating this, IMHO, and does so particularly in the context of ASLR. As soon as you accept the idea that programs don't have a single performance point, it then becomes fairly clear that the best way to get a good idea of a program's performance is to run it as many times as possible and compute some basic statistics over that. ASLR is one aspect where simply running a program enough times gives you some idea of the overall performance of the program. Some modern benchmarking tools make calculating reasonable statistics fairly painless (e.g. things like Criterion for Rust). But, overall, this is still a painful area and there's a lot of work we could do to make life easier for people measuring software IMHO.

[1] http://www.cs.umass.edu/~emery/pubs/stabilizer-asplos13.pdf

> They correctly point out that error handling is by far the biggest one, and usually ends up being the biggest part of a parser for a language, full of crufts and strange mixtures of semantics and syntax. Add to this that you frequently want to try to partially recover -- make a guess as to what was intended and continue parsing in the hopes of finding more actionable errors later in the code.

I agree. Personally, I ignored automated error handling in parsing for years because it seemed to be a lost cause. Eventually, I decided to look in more detail at it, and soon came across a rich vein of previous work that's been largely ignored / forgotten. I suspect that's because the approaches they proposed were too slow to be practical back in the day. After a bit of modernisation, it turns out that these techniques run more than fast enough on modern machines and can even be extended to do a better job than previous approaches attempted (draft paper at https://arxiv.org/abs/1804.07133 ; a more down-to-earth explanation of how to use the accompanying software at https://softdevteam.github.io/grmtools/master/book/errorreco...).

EDIT: fixed URL.

My experience is different. I've converted two or three grammars from recursive descent to LR recently. In each case, the recursive descent authors have made surprising mistakes, resolving ambiguities in ways that violate the intended spec. This isn't surprising: you can't, in general, know when you're resolving ambiguities in a recursive descent parser, so mistakes are almost inevitable.

The hard time limit on UK PhDs is a recent-ish thing, which started coming in around 2010ish from memory (as is usual with such things, there was a fairly long phase-in, which messes with my memory). Broadly speaking, anyone who started in the old system could still carry on for as long as they wanted.

[It's also possible to "suspend regulations" -- which is University speak for "something happened which the rules don't deal with sensibly" -- and extend a PhD's length, though this is generally accompanied by weeping and gnashing of teeth by administrators. It's much harder to do than it used to be.]

LALRPOP is an LR parser, which is a very different formalism to PEG: it's easy to write a grammar in either that's difficult/impossible to express in the other.

If you'll permit the immodesty, another Rust parser is lrpar (https://crates.io/crates/lrpar) which is a more direct drop-in replacement for Yacc, but with better error recovery. [Note: I'm biased because I wrote parts of lrpar and the wider framework, grmtools, it's a part of.]

> The problem with yacc/bison-style LALR parser generators is that you end up with an LALR parser. Which works great on syntactically correct code, but trying to get a reasonable error message out of one is about as much fun as repeatedly poking yourself in the eye with a sharp stick.

The standard ways of getting error messages from LR parsers are pretty bad, but there is a long line of work that's tried to make it better. If you'll forgive the immodesty on my part, I've been working on updating and fixing that work. There's a draft paper at https://arxiv.org/abs/1804.07133 and a beta-ish implementation at https://github.com/softdevteam/grmtools/, so you can see what you think!

[EDIT: fixed formatting]

The best place to start with Krun is its GitHub page https://github.com/softdevteam/krun/

In general, yes, you're reading the timings right, but there's a couple of factors to consider.

First, the JIT compiler has often done most of its work during the first in-process iteration, so the plots are not generally following a "one in-process iteration is slow, then the JIT kicks in from in-process iteration 2 onwards" model. Put another way, the JIT compiler is often making even the first in-process iteration run pretty fast.

Second, I would suggest that the often small timing differences are more worrying than they may first appear. In a semi-mature compiler, optimisations are frequently in the range of a 0.5-1% improvement. So if your measurements are only accurate to (say) 2%, most of your attempted optimisations will be misclassified (bad optimisations will sometimes be measured as good; good optimisations will sometimes be measured as bad). Furthermore, when a VM recompiles things, it generally performs several optimisations at once. Thus, if the overall performance gets worse (even if by a small bit), it may suggest that several optimisations performed badly at the same time.

I'm very surprised to hear this: I've submitted several artefacts; co-run an AEC for a (small-medium) conference; and spoken to a lot of people about it. I've heard virtually nothing negative until your post. Indeed, the artefact reviews I've received have nearly all been thorough and considered (one review was slightly nitpicky, but that's one review out of 10-12). For paper reviews, on the other hand, I'm very happy if 1/2 of reviews are thorough and considered. Bear in mind that most of the artefact reviewers also implicitly review the paper, and you get some idea of how good a job they do.

My main bugbear with the whole thing is the incorrect spelling of "artefact". And when that's my main bugbear... well, things aren't too bad!

Mea culpa! Fixed with thanks.

The Rules of the Game is a fascinating book because it starts with the lead-up Jutland, goes back in time to explain how the culture and personalities of the Royal Navy came to be, before going back to Jutland. It made my head hurt the first time I read it, because so much was unfamiliar, but a second read really brought things to life.

The synopsis / review this book offers is a good one but it could, perhaps, be generalised. Though Gordon doesn't make it explicit as such, the lesson I ended up taking away from the book is that cultures tend to go through alternating periods of encouraging initiative or obedience. You can see this in armies (perhaps the classic example is the Prussian / German army: it started off with Frederick the Great as an army of obedience; became (at the top levels at least) an army of initiative under von Moltke the Elder; and (in the West, at least) went back to an army of obedience for most of WWI), technology (look at any well known company's research lab culture), and even wider society. If I had to briefly summarise the consequences of this, it tends to come down to when two broadly equal organisations square up against each other: if one uses obedience as its model, and the other initiative, the latter will tend to win; if the two both use the same system, the outcome seems to be mostly random.

[That said, Jutland isn't a great example of this in my opinion, as it was so protracted and its outcome so muddy. Poor ship design and some sloppy practises with explosives meant the British came off worse in terms of casualties, so arguably the Germans won the day. However, the (smaller) German Navy realised that it had only survived through luck, and basically stayed in port for the rest of the war, whereas the British were out sailing in force less than a week later and continuing the blockade of Germany. The Germans eventually thought the only way to win at sea was unrestricted submarine warfare, which turned out to be perhaps the biggest PR disaster in history. I was astonished to realise that the German Navy's inferiority complex from Jutland persisted into WWII: the German Navy stalled shamelessly when asked to help invade Britain, as the lesson they learnt from Jutland was that the British Navy could never be defeated, so what was the point of trying? So Jutland had complex long-term effects that defy easy classification. Which is, perhaps, why it's so fascinating.]

My gut feeling is that one can minimally maintain systems in "forgotten" languages indefinitely if they're basically stable and feature complete. But it seems that people come unstuck for systems that still need to evolve -- even if that evolution is slow and/or sporadic. The obvious alternative is to rewrite systems in new languages, but that is generally prohibitively expensive. Even for those that can afford the expense, the new system tends to not to take considerable time to bed in, so flipping the switch from the old to the new is only for the brave or those with excellent PR departments.

Although we didn't have this in mind when we started on this work, I've come to think that language composition might offer a way out of this mess (I immodestly offer [1] as an early example). If one composes an old and a new language, one can migrate a system from an old to a new language bit-by-bit. As well as amortising the translation cost, it also means that one can minimise the "switch flipping" problem: disasters seem much less likely if the composed system can be introduced gradually.

[1] http://tratt.net/laurie/blog/entries/fine_grained_language_c...

Sulong is a really good idea -- I wish I'd thought of it first! We've had a student do a small project looking at something equivalent for RPython. There are, as expected, no show-stoppers yet, but I have no idea how far we'll be able to go with the limited resources we have to throw at the problem.

A crude R/Python composition would be fairly simple (http://goo.gl/p1opSl shows that a strict and lazy language can be crudely put together pretty easily, though you miss good performance and all the programmer-friendly features of PyHyp). Closures/generators are unlikely to be a big deal (PyHyp has good suggestions for both). Although I don't know much about R's class system(s), I expect that we can probably do OK on those. However, I have no idea how R's vectorised types might be handled -- those could be painful to deal with, or they might just fall out of the hat, and I'd have to know more about them in order to make an informed guess. However, this isn't on our roadmap at the moment, as it doesn't fit in with our current funding, unless anyone wants to change our minds!

Why Python and PHP? There are several reasons, but the major ones were: we had to start somewhere; we had an excellent Python interpreter available to us, as well as a fairly decent PHP interpreter; and PHP and Python turn out to be rather different languages with a number of tricky challenges. We certainly look forward to other people composing together even more distinct languages (e.g. we've also done a composition of Python and Prolog http://goo.gl/p1opSl, though, compared to PyHyp, it is rather simplistic).

We're working on it. Keep an eye on http://soft-dev.org/events/vmss16/ over the coming days.

If you're interested in left-recursion in PEGS then, at the risk of gross immodesty, you may be interested in http://tratt.net/laurie/research/pubs/html/tratt__direct_lef...

With less risk of immodesty you may also find http://arxiv.org/pdf/1207.0443.pdf?ref=driverlayer.com/web interesting.

There's probably more recent work than these two papers, but I'm a little out of date when it comes to the PEG world.

Incremental parsing is designed for just this use case. The last major work in the area that I know of is Tim Wagner's PhD thesis http://www.cs.berkeley.edu/Research/Projects/harmonia/papers...