> * “No one cares much about LR(1) parsers anymore,” she said, referring to one of the classic tools of language processing. The remark saddened me because the theory of parsing is a thing of beauty. *
No one cares about LR parsing because:
1. It's about speed and memory efficiency, throwing other requirements into the wind, like interoperability and debuggability. LR runs on what is de facto its own virtual machine (shift-reduce automaton) over its own machine language (an incomprehensible table). This architecture known to most hackers in the form of tools like Yacc, where this is done in absolutely the most minimal way possible just to get the parser working. If you write a recursive descent parser, you can put an ordinary breakpoint on a function which corresponds to a grammar rule, and instantly see rules that are involved, just by looking at the ordinary stack trace. "Oh, we we got here by way of trying to parse an expression, then a term, then a factor, then an identifier". Moreover, unless you're spectacularly terrible at programming, your parser is reentrant.
2. If you have lots of memory, fast CPUs, and the stuff being parsed isn't very large, newer algorithms (or old ones that were not practical in the 1960's) are now practical. Why bother with LR when you can just recursively match, with backtracking (infinite lookahead LL rediscovered as "PEG"), and, as a bonus, define the entire syntax in one grammar, down to the lexical tokens.
3. Parsing is about syntax, and syntax isn't semantics. Once hackers mature, they lose interest in syntax, and consequently in stuff like LR parsing. Lisp shows us that we can get ahead by ditching the surface syntax. The best family of languages for language research, ironically, pretty much ignored and survived the whole LR craze, using recursive scanning routines dispatched by one or two characters of input. Once you know that parsing produces a tree, and that same tree is denoted by a tidy, unambiguous S-expression that requires no advanced parsing techniques, and that semantics only begins after that syntax tree, the excitement for parsing wanes, at least a little.
I'm not as worried about the author's conclusions as he seems to be. I think there will always be more engineers than physicists, more financial experts than economists, and more security professionals than cryptographers. There will always be more people who want to take advantage of the fruits of basic research than there are people who want to do that basic research. And moreover, the basic researchers are generally not as publicly celebrated than their entrepreneurial counterparts (cf Steve Jobs vs Don Knuth or Dennis Ritchie). Without data showing the decline of the number of people who want to do basic science, I'm not convinced that things like the theory of parsing will be lost to history.
That being said, I think there is a lot of extremely exciting stuff going on in theoretical computer science (this is my field), and I think we could do a lot better publicizing our work to encourage more people to think about our problems. It's a shame that there are no career benefits to doing so.
"I think we could do a lot better publicizing our work to encourage more people to think about our problems"
One step would be to tear down the paywall that keeps decades of super-interesting computer science research locked up. I'm looking at you, ACM.
(Paywalls really limit access from people non-affiliated to any subscribing institutions, and even for affiliated people, it might be that slightly annoying barrier that make them not bother if they don't really need to)
Interestingly, some of the more theoretical conferences have started to break off from ACM/IEEE and become independent. See, for example, the computational complexity conference[1] which is now completely independent.
your reply is dead on! It's not only ACM but pretty much all other publishers (ieee, springer, ...). What makes me angry is that all those research papers were in most cases funded by tax payers' money. Anyone remembers Aaron Swartz?
The article fails to mention Vick the Video Game programmer and Saul the security researcher.
Hackers and game developers are some of the best programmers in the world, just because there's no academic departments for these, this author would probably dismiss them as not doing real computing. But they are doing real computing, focusing on areas where the application of computers has the most impact in real life. So if "real" computing is different from "in real life" computing, so be it, I'll take the latter.
It's a shame the article missed them, but while they may not be as prevalent security and game programing do have their own academic departments these days. Often times they are placed under the "CS department", but that is to be expected. Astronomy, theoretical physics, soft-matter and applied physics all share the same department as well.
Computational Science is a bit of an outsider I have noticed though. It varies by university whether it is math, physics, computer or general science. Probably because it occupies the cross-roads between these.
> A prominent example is “What can be computed efficiently?” Theoretical computer science seizes on this question as one of its most central, existential concerns, but the answer also matters to those who write and run programs for practical purposes.
The problem is not that a theoretician has a different answer to the question than a software engineer, but that they are asking different questions with the same words. I think this is a good reason for the fields to be considered different.
In a hypothetical situation I could be developing a piece of software and have an algorithm that is astronomically more efficient than its closest alternative, BUT if the efficient algorithm is good at doing exactly one thing and nothing else, while its alternative can be easily adopted to a variety of tasks and furthermore can be more easily understood by the guy who comes along after me, I am going to use the one that is just good enough for the task at hand. The developer is interested in practicality while the theoretician is interested in ideality.
Another issue is that from a theoretical perspective, in a lot of cases, an algorithm that terminates, even if it takes longer than the heat-death of the universe, is an immense improvement over the current state.
And the problem will be solved. And most of the field upheaved.
What you mean is it's not solved from your perspective of the word solved. Again, that's the central point, that theoretical research is asking different questions (and answering them).
> I would not contend that mastery of the more theoretical topics is a prerequisite to becoming a good programmer. There’s abundant evidence to the contrary. But it is a necessary step in absorbing the culture of computer science.
I personally don't care about my feelings about the culture of computer science. I care about computer science, and I think you have to participate in all of the worlds, to achieve a mature understanding of the computer and it's role in society. When I can separate my mathematical and logical mind from my emotional mind, I can focus enough to do work. When my emotional mind ramps up because I'm (rather unscientifically) comparing myself to a very selectively observational evaluation of the value of the achievements of others, I am not sure what gets done aside from the passage of time.
[not related to content] I usually print interesting articles to XPS because the XPS reader on my tablet is so much faster than web browsers. As I've been doing this I've noticed that lots of sites out there just cannot be printed. For example, this article's content is put into some sort of a container, I presume, that has a fixed width or something that cuts off a part of the text. Even the "printer-friendly" version exhibits this problem. Sadly, but for me this means I'm not reading the article.
Brian Hayes is a treasure, and so is American Scientist. American Scientist has taken over the role that Scientific American had in the 70s and 80s, when it was good, and Brian Hayes is almost the A. K. Dewdney (different, but better in some ways) of our current era.
There's at least a fourth even more removed culture, the plc programmer who is even more pragmatic than the software developer. He cares about the program about as much as the data scientist. It's just there to do the job.
No one cares about LR parsing because:
1. It's about speed and memory efficiency, throwing other requirements into the wind, like interoperability and debuggability. LR runs on what is de facto its own virtual machine (shift-reduce automaton) over its own machine language (an incomprehensible table). This architecture known to most hackers in the form of tools like Yacc, where this is done in absolutely the most minimal way possible just to get the parser working. If you write a recursive descent parser, you can put an ordinary breakpoint on a function which corresponds to a grammar rule, and instantly see rules that are involved, just by looking at the ordinary stack trace. "Oh, we we got here by way of trying to parse an expression, then a term, then a factor, then an identifier". Moreover, unless you're spectacularly terrible at programming, your parser is reentrant.
2. If you have lots of memory, fast CPUs, and the stuff being parsed isn't very large, newer algorithms (or old ones that were not practical in the 1960's) are now practical. Why bother with LR when you can just recursively match, with backtracking (infinite lookahead LL rediscovered as "PEG"), and, as a bonus, define the entire syntax in one grammar, down to the lexical tokens.
3. Parsing is about syntax, and syntax isn't semantics. Once hackers mature, they lose interest in syntax, and consequently in stuff like LR parsing. Lisp shows us that we can get ahead by ditching the surface syntax. The best family of languages for language research, ironically, pretty much ignored and survived the whole LR craze, using recursive scanning routines dispatched by one or two characters of input. Once you know that parsing produces a tree, and that same tree is denoted by a tidy, unambiguous S-expression that requires no advanced parsing techniques, and that semantics only begins after that syntax tree, the excitement for parsing wanes, at least a little.