6 ms·

META II: A Syntax-Oriented Compiler Writing Language (1964) [pdf]

83 points by espeed 10y ago

adamnemecek 10y ago
This seems very similar to OMeta https://en.wikipedia.org/wiki/OMeta https://en.wikipedia.org/wiki/OMeta that has been ported to a lot of languages http://www.tinlizzie.org/ometa/ http://www.tinlizzie.org/ometa/ OMeta really changed my view on how to prototype languages. TL;DR, OMeta let's you map patterns in your language to patterns in another language (say python) and thereby, you can implement a whole language roughly as easily as defining a BNF.
- chriswarbo 10y ago
  Yes, Meta II was a big inspiration of OMeta, e.g. see "Fundamentals of New Computing" (FoNC) discussions like http://fonc.vpri.narkive.com/GsIfD639/a-meta-ii-for-c-that-fits-in-a-half-a-sheet-of-paper http://fonc.vpri.narkive.com/GsIfD639/a-meta-ii-for-c-that-f...
- chubot 10y ago
  I looked into OMeta awhile back, which sounded cool although somewhat overblown, and wrote my own toy backtracking PEG implementation (somewhat based on LPeg), which isn't too difficult. I read most of the VPRI papers because I'm interested in compact software and DSLs. But then I had occasion to implement a "real" language, and I just went with a hand-coded parser instead, despite a desire to avoid that. I think these kinds of tools are good for prototyping toy languages, as you say, but unfortunately they're still TWO steps away from production quality implementations of real language. They're not good for even prototyping "real" languages (think shell, C++, Perl, Make), or production-quality implementations of "toy" languages. Possible reasons for this: 1) Developer experience... you end up having to reason about control flow and performance for "real" languages, breaking out of the declarative abstraction. 2) Most parsing tools are frameworks rather than libraries -- they kind of force you into a single lexer -> parser -> tree architecture (ANTLR being a prime example, re2c being a great counterexample for lexing). But this architecture doesn't work for many languages. 3) They make other unwarranted assumptions, e.g. about whitespace, which Bourne shell violates. There are a bunch of other reasons I can list if anyone is interested. A a good research topic is to bridge this gap. I wrote a very complete parser for shell in Python and sort of "discovered" what the language is... I would love to now port it to a meta-language and generate C/C++ code, rather than port it to C++ by hand. http://www.oilshell.org/blog/2016/11/17.html http://www.oilshell.org/blog/2016/11/17.html But I think it's impossible. I was thinking of putting out a "meta-language bounty" to help me solve this problem. I think what's more likely is that I will end up writing a custom code generator to port my subset of Python to C++. But I would love to be proven wrong. The Python parser is 3500 lines and the AST is 2000 lines. I would like to describe this with 200-500 lines of code in a meta-language (factor of 10 reduction). Although I think some things like good error messages are sort of "irreducible" so maybe that's impossible. Basically the goal is: describe bash with a meta-language. I have described it in ~5K lines of Python, which is a pretty good compression over the actual bash source code, where the parser is between 10K and 20K lines, spread out over many files and many stages. I wonder what Alan Kay would say about bash. I think he would probably say "don't use such a complex tool". But I think that's just an indication of the gap between research and practice. More people have used bash than any of his languages, and it consumes more CPU cycles worldwide as well. Although his ideas were influential, they had to be modified to actually work in practice.
  - zzzcpan 10y ago
    I think it's possible if you make your meta grammar programmable, i.e. instead of generating code to compile, go into higher-order programming and return structures that contain functions to execute. This will let you insert programmable hooks into nodes on different stages and various specific behaviors, including proper errors, specific whitespaces, etc. Even switch parsers depending on context. What I mean is something like this in pseudo code: parser = Parser (" ... program ::= statements eof statements ::= statement* ") parser.AddHookBefore ("statement", function { ... }) ast = parser.match (input)
    - chubot 10y ago
      How is that different than what something like Yacc or ANTLR already provide? Inserting arbitrary code is definitely necessary for real languages, but this breaks the model, any guarantees you might have gotten (about performance), and is often awkward. bash uses yacc, and there are a bunch of globals mutated in the semantic actions, which is not easy to reason about. They are REALLY breaking out of the model. That is why people prefer hand-written parsers, because you can develop your own model, specific to the language you are parsing. As I wrote in that blog post, my parser only requires two tokens of lookahead, so there are no fancy algorithms involved. The hard part isn't really deriving the parser from the grammar; it's everything else (parsing here docs, etc.) I would question whether this saves any effort or lines of code over the hand-written approach. I think you would just end up with something almost as long -- and if you count the parser generator itself, it will be longer.
      - zzzcpan 10y ago
        I guess the only option to keep clean grammars is to extend the meta language itself enough to support language-specific features. And if you implement it yourself it's not actually that hard to do. Parsing is not really a big deal after all. If I remember correctly the idea behind OMeta is to invent new languages to fit better into your problem domain so you could save a ton of code, not to parse existing ones.
walterbell 10y ago
Previous threads on meta-compilers, including a Javascript-based workshop/demo of techniques: https://news.ycombinator.com/item?id=8297996 https://news.ycombinator.com/item?id=8297996 https://news.ycombinator.com/item?id=8441041 https://news.ycombinator.com/item?id=8441041
espeed 10y ago
This is one of the papers referenced by Alan Kay in the talk posted to HN one day ago: Joe Armstrong Interviews Alan Kay [video] (https://www.youtube.com/watch?v=fhOHn9TClXY https://www.youtube.com/watch?v=fhOHn9TClXY) Discussion: https://news.ycombinator.com/item?id=13033299 https://news.ycombinator.com/item?id=13033299
pierre_d528 10y ago
Work is still being done in that direction see: https://github.com/harc/ohm https://github.com/harc/ohm
- andreaorru 10y ago
  That's very cool. Are you aware of similar tools written in languages other than JavaScript?
  - abecedarius 10y ago
    Hi Andrea -- https://github.com/darius/parson https://github.com/darius/parson is in Python. It's probably not very similar because I haven't got around to studying Ohm, but it shares the basic goal of not writing semantic actions inline in some particular language. (I wrote it in my first Recurse Center stint back in 2012.)
    - andreaorru 10y ago
      Hi Darius (it's a small world). That looks really good, I'll have a look at it!

83 points by espeed 10y ago

This seems very similar to OMeta https://en.wikipedia.org/wiki/OMeta https://en.wikipedia.org/wiki/OMeta that has been ported to a lot of languages http://www.tinlizzie.org/ometa/ http://www.tinlizzie.org/ometa/ OMeta really changed my view on how to prototype languages. TL;DR, OMeta let's you map patterns in your language to patterns in another language (say python) and thereby, you can implement a whole language roughly as easily as defining a BNF.

chriswarbo 10y ago
Yes, Meta II was a big inspiration of OMeta, e.g. see "Fundamentals of New Computing" (FoNC) discussions like http://fonc.vpri.narkive.com/GsIfD639/a-meta-ii-for-c-that-fits-in-a-half-a-sheet-of-paper http://fonc.vpri.narkive.com/GsIfD639/a-meta-ii-for-c-that-f...
chubot 10y ago
I looked into OMeta awhile back, which sounded cool although somewhat overblown, and wrote my own toy backtracking PEG implementation (somewhat based on LPeg), which isn't too difficult. I read most of the VPRI papers because I'm interested in compact software and DSLs. But then I had occasion to implement a "real" language, and I just went with a hand-coded parser instead, despite a desire to avoid that. I think these kinds of tools are good for prototyping toy languages, as you say, but unfortunately they're still TWO steps away from production quality implementations of real language. They're not good for even prototyping "real" languages (think shell, C++, Perl, Make), or production-quality implementations of "toy" languages. Possible reasons for this: 1) Developer experience... you end up having to reason about control flow and performance for "real" languages, breaking out of the declarative abstraction. 2) Most parsing tools are frameworks rather than libraries -- they kind of force you into a single lexer -> parser -> tree architecture (ANTLR being a prime example, re2c being a great counterexample for lexing). But this architecture doesn't work for many languages. 3) They make other unwarranted assumptions, e.g. about whitespace, which Bourne shell violates. There are a bunch of other reasons I can list if anyone is interested. A a good research topic is to bridge this gap. I wrote a very complete parser for shell in Python and sort of "discovered" what the language is... I would love to now port it to a meta-language and generate C/C++ code, rather than port it to C++ by hand. http://www.oilshell.org/blog/2016/11/17.html http://www.oilshell.org/blog/2016/11/17.html But I think it's impossible. I was thinking of putting out a "meta-language bounty" to help me solve this problem. I think what's more likely is that I will end up writing a custom code generator to port my subset of Python to C++. But I would love to be proven wrong. The Python parser is 3500 lines and the AST is 2000 lines. I would like to describe this with 200-500 lines of code in a meta-language (factor of 10 reduction). Although I think some things like good error messages are sort of "irreducible" so maybe that's impossible. Basically the goal is: describe bash with a meta-language. I have described it in ~5K lines of Python, which is a pretty good compression over the actual bash source code, where the parser is between 10K and 20K lines, spread out over many files and many stages. I wonder what Alan Kay would say about bash. I think he would probably say "don't use such a complex tool". But I think that's just an indication of the gap between research and practice. More people have used bash than any of his languages, and it consumes more CPU cycles worldwide as well. Although his ideas were influential, they had to be modified to actually work in practice.
- zzzcpan 10y ago
  I think it's possible if you make your meta grammar programmable, i.e. instead of generating code to compile, go into higher-order programming and return structures that contain functions to execute. This will let you insert programmable hooks into nodes on different stages and various specific behaviors, including proper errors, specific whitespaces, etc. Even switch parsers depending on context. What I mean is something like this in pseudo code: parser = Parser (" ... program ::= statements eof statements ::= statement* ") parser.AddHookBefore ("statement", function { ... }) ast = parser.match (input)
  - chubot 10y ago
    How is that different than what something like Yacc or ANTLR already provide? Inserting arbitrary code is definitely necessary for real languages, but this breaks the model, any guarantees you might have gotten (about performance), and is often awkward. bash uses yacc, and there are a bunch of globals mutated in the semantic actions, which is not easy to reason about. They are REALLY breaking out of the model. That is why people prefer hand-written parsers, because you can develop your own model, specific to the language you are parsing. As I wrote in that blog post, my parser only requires two tokens of lookahead, so there are no fancy algorithms involved. The hard part isn't really deriving the parser from the grammar; it's everything else (parsing here docs, etc.) I would question whether this saves any effort or lines of code over the hand-written approach. I think you would just end up with something almost as long -- and if you count the parser generator itself, it will be longer.
    - zzzcpan 10y ago
      I guess the only option to keep clean grammars is to extend the meta language itself enough to support language-specific features. And if you implement it yourself it's not actually that hard to do. Parsing is not really a big deal after all. If I remember correctly the idea behind OMeta is to invent new languages to fit better into your problem domain so you could save a ton of code, not to parse existing ones.

walterbell 10y ago

Previous threads on meta-compilers, including a Javascript-based workshop/demo of techniques: https://news.ycombinator.com/item?id=8297996 https://news.ycombinator.com/item?id=8297996 https://news.ycombinator.com/item?id=8441041 https://news.ycombinator.com/item?id=8441041

espeed 10y ago

This is one of the papers referenced by Alan Kay in the talk posted to HN one day ago: Joe Armstrong Interviews Alan Kay [video] (https://www.youtube.com/watch?v=fhOHn9TClXY https://www.youtube.com/watch?v=fhOHn9TClXY) Discussion: https://news.ycombinator.com/item?id=13033299 https://news.ycombinator.com/item?id=13033299

pierre_d528 10y ago

Work is still being done in that direction see: https://github.com/harc/ohm https://github.com/harc/ohm

andreaorru 10y ago
That's very cool. Are you aware of similar tools written in languages other than JavaScript?
- abecedarius 10y ago
  Hi Andrea -- https://github.com/darius/parson https://github.com/darius/parson is in Python. It's probably not very similar because I haven't got around to studying Ohm, but it shares the basic goal of not writing semantic actions inline in some particular language. (I wrote it in my first Recurse Center stint back in 2012.)
  - andreaorru 10y ago
    Hi Darius (it's a small world). That looks really good, I'll have a look at it!