4 ms·

I don't know. This is becoming conventional wisdom but I think a reverse argument is equally true: aspiring language designers get too bogged down in bytecode g

by norir 3y ago

I don't know. This is becoming conventional wisdom but I think a reverse argument is equally true: aspiring language designers get too bogged down in bytecode generation or gc that they are unable to make a compelling language that adequately differentiates itself from existing languages that already do those things well. Are you actually claiming that handwriting a recursive descent parser for most popular languages can be done in afternoon? Unless the language is a lisp, I find that unlikely in most cases. You can write a parser generator that generates a recursive descent parser. Writing the grammar will almost surely be significantly faster in the parser generator dsl than a handrolled recursive descent parser. To improve your language design skills, you need to design multiple languages. Parser generators will get you a prototype faster and allow you to explore the language design space. You can target a high level language to do the hard parts. Once you are satisfied with a language, then maybe it makes sense to design your own custom bytecode or gc to solve its unique problems. I do agree though that optimizing parsing at an early stage makes no sense and many do get bogged down there.

kerkeslager 3y ago
> Are you actually claiming that handwriting a recursive descent parser for most popular languages can be done in afternoon? Unless the language is a lisp, I find that unlikely in most cases. Yes. I've written enough parsers that I can say that with a lot of confidence, and I'm not sure where your doubt is coming from. The parser for Fur was written in about 6 hours and probably 4 hours of that was tracking down pathological semicolon elision edge cases (0/10, would not implement semicolon elision in future languages). I'm sure that Nystrom has written many more parsers than I have. The edge cases might be tricky to iron out for existing, mature languages, but when you're writing your own language I'd shy away from features which require crazy parser shenanigans like JavaScript RegEx literals or C++ templates, at least until you're far along enough to have justification for those kinds of features. This is also the sort of thing that I imagine ChatGPT, even the free version, could do in even less time. There's one caveat here, which is that error reporting is one pretty hard part of parsing. But if you understood that you wouldn't be recommending parser generators; poor error reporting capabilities is exactly why many production-quality languages have hand-rolled their parsers. > Writing the grammar will almost surely be significantly faster in the parser generator dsl than a handrolled recursive descent parser. I'm not interested in hearing speculation on things I've benchmarked. When it comes to performance, benchmark or GTFO. Performance isn't significantly different in most cases, and in pathological worst cases, it's often easily solved by memoizing (i.e. converting the recursive descent parser into a Packrat Parser). You shouldn't even memoize everything in most cases, because a lot of sub-parsers won't trigger backtracking, so there's no need to waste memory on memoization. > To improve your language design skills, you need to design multiple languages. Parser generators will get you a prototype faster and allow you to explore the language design space. To design a language, I don't need to write a parser at all in most cases. I certainly don't need to prototype syntax to design it effectively. Writing programs in your target syntax, even if you can't actually run them, is far more effective. Related to the fact that parsers aren't the hard part, syntax isn't the important part, so if you get bogged down in designing the syntax that's also a lose. I genuinely think most novel syntaxes create more usability/entry barriers for users than the benefits they offer. Go with the syntax of an existing popular language if you at all can--the simpler/more popular, the better. Semantics, idioms, and ecosystem are all much more important in what makes a language useful. > You can target a high level language to do the hard parts. That's exactly why this approach is terrible. The hard parts are the entire point of creating a new language. If the hard parts are all implemented in a different language then people should just use that language instead of yours. > Once you are satisfied with a language, then maybe it makes sense to design your own custom bytecode or gc to solve its unique problems. Still no--I don't think you understood what I meant when I said "the real hard problems of language development, which are things like bytecode generation and garbage collection". If you're targeting an existing VM such as the JVM or CLR you won't need to implement custom bytecode or GC, and even if you decide to implement your own bytecode or GC, you may be able to use an off-the-shelf implementation. You'll note that my post said bytecode generation, which is hard no matter what syntax you're implementing or bytecode you're targeting, because it's translating the semantics of the syntax to semantics that the target architecture can understand. When I said implementing garbage collection was hard, what I meant was not that implementing the algorithms is hard (you can literally plug in an off-the-shelf garbage collector in most cases) but that calling the garbage collection algorithms at the right times is hard.
- cxr 3y ago
  > I'd shy away from features which require crazy parser shenanigans like[...] RegEx literals Note to aspiring language designers: you don't have to shy away; you can 80/20 your way there even in extremely early versions of your language if you rule that, for now, all regular expression literals must be parenthesized (so just tell authors to write e.g. `(/re/)` rather than `/re/`). With this requirement in place, it's about as easy to support them the lexer as it is to support other multi-character operators like `&&` or `>=`. I call this trick the "eggex hack"—at least I would, except that chubot also chose the "eggex" terminology in Oil shell to describe a completely different concept for reasons that I don't understand.
  - kerkeslager 3y ago
    Interesting idea. To check my understanding, I think what your saying is the following?: The scanner has a "(/" token which triggers dropping into a different scanner/parser for RegExes. This secondary scanner/parser drops out upon seeing a "/)". Alternatively, the "(/" and "/)" could be replaced by a trivial one-token lookahead (which would allow "( /" to match, for example); the key here is to differentiate "(/" from "(" or "/" so that "(/" immediately tells you that you're in a RegEx. This obviates the need to differentiate arbitrary RegExes from other things which might occur after a division symbol "/" like in JavaScript. If that's what you're saying, seems brilliantly simple! I don't love the user experience of that, but maybe that's just an aesthetic opinion. Knowing how difficult it is to implement JavaScript-style RegEx literals, this seems like a good idea, at least at first.
    - cxr 3y ago
      You get the gist of the benefits—to get to a point where you can "implement JavaScript-style RegEx literals" without too much effort by removing some barriers to implementation—but some of the conceptual specifics in your understanding are off. > I think what your saying is the following?:¶ The scanner has a "(/" token which triggers dropping into a different scanner/parser for RegExes Not quite. First, you don't have separate `(/` and `/)` tokens. The `(/` character sequence is the start of a single pattern literal (the same way that if you're parsing JSON, the opening double quote is part of the string literal). What it does is serve as an unambiguous symbol that yes, what we are seeing here is a literal for a PCRE-style pattern. Secondly, you don't have to have a separate scanner. That's sort of the point—supporting "eggular expressions" is easy because tokenizing them is drastically simpler than the hacks regarding context-sensitivity that you must weave into both your parser and scanner (and complicate the scanner–parser contract) if you want conventional unparenthesized literals. Adding support for the parenthesized form to your lexer amounts to just a few lines of code, and not only that, but very simple, very boring code of the same sort that you have elsewhere—easier than the code to support numeric literals, even—whereas the same is distinctly not true if they are allowed to be unparenthesized. (NB: I mentioned 80/20 before. These "eggexes" are also the good kind of partial implementation: a pure case of forward compatibility—if you support the parenthesized form now, there's nothing stopping you from relaxing the paren constraint in the future and announcing that you now support unparenthesized literals.) > I don't love the user experience of that, but maybe that's just an aesthetic opinion. Yeah, aesthetic is right. I actually prefer them parenthesized, anyway, for entirely unrelated reasons. Similar constructions like "foo".bar and [].baz, while technically permitted in the grammars of several languages, raise my hackles. It's no less true concerning literals used for pattern matching. Parens need to be inserted on the lhs of the dot for anyone who wants my approval in code review. As it happens, though, there are benefits to readability on multiple levels (i.e. for both humans and machines).

by norir 3y ago

kerkeslager 3y ago

> Are you actually claiming that handwriting a recursive descent parser for most popular languages can be done in afternoon? Unless the language is a lisp, I find that unlikely in most cases. Yes. I've written enough parsers that I can say that with a lot of confidence, and I'm not sure where your doubt is coming from. The parser for Fur was written in about 6 hours and probably 4 hours of that was tracking down pathological semicolon elision edge cases (0/10, would not implement semicolon elision in future languages). I'm sure that Nystrom has written many more parsers than I have. The edge cases might be tricky to iron out for existing, mature languages, but when you're writing your own language I'd shy away from features which require crazy parser shenanigans like JavaScript RegEx literals or C++ templates, at least until you're far along enough to have justification for those kinds of features. This is also the sort of thing that I imagine ChatGPT, even the free version, could do in even less time. There's one caveat here, which is that error reporting is one pretty hard part of parsing. But if you understood that you wouldn't be recommending parser generators; poor error reporting capabilities is exactly why many production-quality languages have hand-rolled their parsers. > Writing the grammar will almost surely be significantly faster in the parser generator dsl than a handrolled recursive descent parser. I'm not interested in hearing speculation on things I've benchmarked. When it comes to performance, benchmark or GTFO. Performance isn't significantly different in most cases, and in pathological worst cases, it's often easily solved by memoizing (i.e. converting the recursive descent parser into a Packrat Parser). You shouldn't even memoize everything in most cases, because a lot of sub-parsers won't trigger backtracking, so there's no need to waste memory on memoization. > To improve your language design skills, you need to design multiple languages. Parser generators will get you a prototype faster and allow you to explore the language design space. To design a language, I don't need to write a parser at all in most cases. I certainly don't need to prototype syntax to design it effectively. Writing programs in your target syntax, even if you can't actually run them, is far more effective. Related to the fact that parsers aren't the hard part, syntax isn't the important part, so if you get bogged down in designing the syntax that's also a lose. I genuinely think most novel syntaxes create more usability/entry barriers for users than the benefits they offer. Go with the syntax of an existing popular language if you at all can--the simpler/more popular, the better. Semantics, idioms, and ecosystem are all much more important in what makes a language useful. > You can target a high level language to do the hard parts. That's exactly why this approach is terrible. The hard parts are the entire point of creating a new language. If the hard parts are all implemented in a different language then people should just use that language instead of yours. > Once you are satisfied with a language, then maybe it makes sense to design your own custom bytecode or gc to solve its unique problems. Still no--I don't think you understood what I meant when I said "the real hard problems of language development, which are things like bytecode generation and garbage collection". If you're targeting an existing VM such as the JVM or CLR you won't need to implement custom bytecode or GC, and even if you decide to implement your own bytecode or GC, you may be able to use an off-the-shelf implementation. You'll note that my post said bytecode generation, which is hard no matter what syntax you're implementing or bytecode you're targeting, because it's translating the semantics of the syntax to semantics that the target architecture can understand. When I said implementing garbage collection was hard, what I meant was not that implementing the algorithms is hard (you can literally plug in an off-the-shelf garbage collector in most cases) but that calling the garbage collection algorithms at the right times is hard.

cxr 3y ago
> I'd shy away from features which require crazy parser shenanigans like[...] RegEx literals Note to aspiring language designers: you don't have to shy away; you can 80/20 your way there even in extremely early versions of your language if you rule that, for now, all regular expression literals must be parenthesized (so just tell authors to write e.g. `(/re/)` rather than `/re/`). With this requirement in place, it's about as easy to support them the lexer as it is to support other multi-character operators like `&&` or `>=`. I call this trick the "eggex hack"—at least I would, except that chubot also chose the "eggex" terminology in Oil shell to describe a completely different concept for reasons that I don't understand.
- kerkeslager 3y ago
  Interesting idea. To check my understanding, I think what your saying is the following?: The scanner has a "(/" token which triggers dropping into a different scanner/parser for RegExes. This secondary scanner/parser drops out upon seeing a "/)". Alternatively, the "(/" and "/)" could be replaced by a trivial one-token lookahead (which would allow "( /" to match, for example); the key here is to differentiate "(/" from "(" or "/" so that "(/" immediately tells you that you're in a RegEx. This obviates the need to differentiate arbitrary RegExes from other things which might occur after a division symbol "/" like in JavaScript. If that's what you're saying, seems brilliantly simple! I don't love the user experience of that, but maybe that's just an aesthetic opinion. Knowing how difficult it is to implement JavaScript-style RegEx literals, this seems like a good idea, at least at first.
  - cxr 3y ago
    You get the gist of the benefits—to get to a point where you can "implement JavaScript-style RegEx literals" without too much effort by removing some barriers to implementation—but some of the conceptual specifics in your understanding are off. > I think what your saying is the following?:¶ The scanner has a "(/" token which triggers dropping into a different scanner/parser for RegExes Not quite. First, you don't have separate `(/` and `/)` tokens. The `(/` character sequence is the start of a single pattern literal (the same way that if you're parsing JSON, the opening double quote is part of the string literal). What it does is serve as an unambiguous symbol that yes, what we are seeing here is a literal for a PCRE-style pattern. Secondly, you don't have to have a separate scanner. That's sort of the point—supporting "eggular expressions" is easy because tokenizing them is drastically simpler than the hacks regarding context-sensitivity that you must weave into both your parser and scanner (and complicate the scanner–parser contract) if you want conventional unparenthesized literals. Adding support for the parenthesized form to your lexer amounts to just a few lines of code, and not only that, but very simple, very boring code of the same sort that you have elsewhere—easier than the code to support numeric literals, even—whereas the same is distinctly not true if they are allowed to be unparenthesized. (NB: I mentioned 80/20 before. These "eggexes" are also the good kind of partial implementation: a pure case of forward compatibility—if you support the parenthesized form now, there's nothing stopping you from relaxing the paren constraint in the future and announcing that you now support unparenthesized literals.) > I don't love the user experience of that, but maybe that's just an aesthetic opinion. Yeah, aesthetic is right. I actually prefer them parenthesized, anyway, for entirely unrelated reasons. Similar constructions like "foo".bar and [].baz, while technically permitted in the grammars of several languages, raise my hackles. It's no less true concerning literals used for pattern matching. Parens need to be inserted on the lhs of the dot for anyone who wants my approval in code review. As it happens, though, there are benefits to readability on multiple levels (i.e. for both humans and machines).