4 ms·

A few strong opinions, a lot stronger than they were in my 2017 talk https://youtu.be/_gmMJwjg0Pk https://youtu.be/_gmMJwjg0Pk, surely that must be the experien

A few strong opinions, a lot stronger than they were in my 2017 talk https://youtu.be/_gmMJwjg0Pk https://youtu.be/_gmMJwjg0Pk, surely that must be the experience speaking :) - Creating a DSL is a commitment. It is never done, it's either in development or abandoned. Plan for this, both in terms of team size and knowledge management. - Don't allow escape hatches or ways to access arbitrary functionality in the host language. When (not if) these are used, they ruin backwards compatibility and make maintenance of DSL code a nightmare. - Don't use a PEG (parsing expression grammar), they are terrible for backwards compatibility. Hand-written parsers are even worse. Using an LR parser generator is worth the time investment. - Support static analysis, or at the very least don't make it impossible to implement later. It improves productivity, and every error message is an opportunity to teach the DSL to the users. - You need a language server. The bare minimum is: highlighting, auto-completion, hints on hover, find references, rename. - It should be trivial to reproduce a production run on a development machine. This means the language should be deterministic, and the production context should be preserved for later reuse, and the development machine should be safe for accessing production data. - Thousands of unit tests, thousands of regression tests. It's fine to break these rules, if you can live with the consequences. And here's a brand new one from this year: use RAG to have ChatGPT "read" your documentation, and ask it to produce scripts for you. When the script doesn't compile, feed the error message back to ChatGPT and try again until you get a working script. Think deeply about why ChatGPT made some mistakes, as it's often the case that humans would have the same misunderstandings. Improve your documentation, error messages or syntax to eliminate them, and then try again to see if it works. We have been doing this for 6 months now, and there have already been some significant improvements that are only obvious in hindsight. And we've now opened a PhD position to investigate whether we can have a separate "LLM-friendly" syntax for the language, dedicated to making code generation easier.

cc_ashby 3y ago
Hey Victor, these are amazing tips. I am currently building a DSL for LLMs, and would love your feedback/consulting. I could not find your email online. Please feel free to reply to this or reach me here: [redacted] on X [email-redacted] Would love advisement from someone who has thought about DSLs extensively!
danielvaughn 3y ago
I'm in the midst of creating a DSL (it's my first try) and this sounds like really good advice. I'm not clear on the third item though - by LR parser generator are you talking about something like ANTLR?
- victorNicollet 3y ago
  Yes, something like ANTLR for Java, or the entire list here: https://en.wikipedia.org/wiki/Comparison_of_parser_generators#Deterministic_context-free_languages https://en.wikipedia.org/wiki/Comparison_of_parser_generator... I've had good experiences with Menhir (for OCaml) and Tree-sitter, and implemented my own SLR parser generator for C# https://github.com/Lokad/Parsing https://github.com/Lokad/Parsing In the end, what matters is that they should be able to report conflicts and ambiguities.
  - _a_a_a_ 3y ago
    Are you saying PEGs can't conflicts and ambiguities? I didn't know that.
    - victorNicollet 3y ago
      Not having ambiguities is actually the main selling point of PEGs. If you have two rules A and B that can both match the input, then a CFG A|B has an ambiguity (two possible derivations), but a PEG A/B explicitly says that the A derivation is chosen. The good part is that unlike a CFG, the PEG doesn't require you to go and fix anything (the / operator already did that for you). This makes the initial implementation of the grammar easier. On the other hand, if you already have code in the wild that uses the old grammar G1, and in order to add new features, you introduce a new grammar G2 that is a superset of G1. You need to know if any of the existing code has a derivation in G2 that is different from its derivation in G1 (as that would cause backwards incompatibility). With a PEG, there's no way to tell, so you have to check this by hand (and mistakes are easy). With a CFG, you know that backwards incompatibility happens if and only if G2 has conflicts, and those conflicts are precisely the cases that are not backwards compatible.
FrustratedMonky 3y ago
Is an LR better than a parser/combinator. Seems like there are pluses to rolling your own parser/combinator over the time to integrate with a yacc or other library.
- victorNicollet 3y ago
  I am a bit biased (in the sense that I wrote my own SLR parser generator twice, in C# and F#!), but the benefit of LR is that you can know whether your CFG contains conflicts, which is a game changer for preserving backwards compatibility when you change the syntax later during the life of the DSL. But if a parser combinator library may support converting the resulting combined parser into an eBNF grammar, and check whether that grammar contains conflicts.
  - marcosdumay 3y ago
    Hum... A grammar conflict on parser combinators always require that you step down from the parser abstraction and resolve it by hand with basic language functionality, doesn't it? It's something quite hard to notice. Are you concerned with the documentation getting out of sync with the actual language?
    - victorNicollet 3y ago
      In a situation where I'm adding a new feature to the language, with a new syntax that causes me to add a new rule to the grammar, I'm concerned that the new rule will accidentally "capture" some code that already exists in the wild, that was previously derived by another part of the grammar. To give a very ugly example, if you have a language with function calls f(expr, expr, expr) and you want to add tuple syntax to expressions with a brand new rule: expr := expr COMMA expr Then you might have accidentally turned all functions into unary functions, as the tuple rule captures the "expr, expr, expr" part and leaves you with f(expr).
  - FrustratedMonky 3y ago
    I do love F# for parsing and for DSL's. Maybe it is 'functional' programming bias. IF you are using a 'functional' paradigm, you can do your own parser/combinator. But if you are using C#, you use something like Yacc and LR.?
trealira 3y ago
> Hand-written parsers are even worse. Using an LR parser generator is worth the time investment. I'm curious, what makes you say this? From what I've read online secondhand, people tend to recommend handwritten recursive descent parsing and Pratt/TDOP parsing, because it's easier to add good error messages and later add context sensitive productions (e.g. the way Clang resolves class-wide declarations while parsing C++: https://eli.thegreenplace.net/2012/07/05/how-clang-handles-the-type-variable-name-ambiguity-of-cc https://eli.thegreenplace.net/2012/07/05/how-clang-handles-t...).
- mjul 3y ago
  He explains it in the linked video presentation which is worth watching: the value being that your parser generator will complain about any ambiguity in the grammar (shift-reduce conflicts) rather than having that show up as a “wat?” at runtime. You might argue that this argument reduces to checking the grammar using static analysis similar to the order generator. But then handwriting the parser is still extra work and risk.
  - civilitty 3y ago
    What I've seen most nontrivial projects do (and have done in a commercial product myself) is to start with a parser generator then move to hand written parsers when UX and polish become a bigger priority than exploring the problem space. The parser generator grammar spec can then be used to generate random test cases and compare the output of the new parser with the old one to make sure they're identical.
bloopernova 3y ago
Good lord yes on the language server. Reduce the friction involved with writing code. I'm frustrated with terraform-ls right now. It doesn't work with private module registries, reloading each module in the .terraform dir over and over. Which impacts performance by maxing out a CPU core. And yet a feature of Terraform Cloud (TFC) is that you can use private registries. Writing Terraform is already plagued by friction. Adding TFC adds to the friction. The language server then not loading private modules adds even more. Hopefully OpenTofu helps in that regard, but I don't think they've got anyone working on the language server either.
- cube2222 3y ago
  > but I don't think they've got anyone working on the language server either. Not yet, but it's on our radar. We're focusing on the stable release + registry for now (eta mid-December), but we're planning to work on the language server eventually. If you have any more frustrations with the language server, feel free to respond here, and it'll help us find avenues for improvements. Disclaimer: Interim Tech Lead of OpenTofu
  - bloopernova 3y ago
    It's really not a frustration, I should have mentioned that you were going to look at it once things settled down :/ I'm incredibly supportive of your efforts, I just wish I was a good enough coder to pick up golang and make the language server better instead of just griping about it. I created a ticket about dedupe, but I have to admit it's a very low priority compared to so much other stuff. I think my only other suggestion would be to concentrate on making the tf development cycle quick and easy. The easier it is for people to write the code, the more code they'll write, even with copilot or other helpers.
starcraft2wol 3y ago
This is ridiculously not practical. For lisp programmers making dsls is just how you write programs and you don’t need a parser.
Too 3y ago
One more from me - Any expression that may likely include a user-generated variable should have a strategy for how to inject it safely. To avoid sql injection class of attacks. Native templating is the best. If string templating is the only way out, the rules for escaping should be clearly defined and ideally functions for doing so provided by the reference implementation. Not like the geniuses at Atlassian who came up with JQL that refuse to document how it works, instead delegates all security to the user model and “don’t run queries with any data that you didn’t provide yourself”.
eternityforest 3y ago
What kinds of use cases justify this much effort?

cc_ashby 3y ago

Hey Victor, these are amazing tips. I am currently building a DSL for LLMs, and would love your feedback/consulting. I could not find your email online. Please feel free to reply to this or reach me here: [redacted] on X [email-redacted] Would love advisement from someone who has thought about DSLs extensively!

danielvaughn 3y ago

I'm in the midst of creating a DSL (it's my first try) and this sounds like really good advice. I'm not clear on the third item though - by LR parser generator are you talking about something like ANTLR?

victorNicollet 3y ago
Yes, something like ANTLR for Java, or the entire list here: https://en.wikipedia.org/wiki/Comparison_of_parser_generators#Deterministic_context-free_languages https://en.wikipedia.org/wiki/Comparison_of_parser_generator... I've had good experiences with Menhir (for OCaml) and Tree-sitter, and implemented my own SLR parser generator for C# https://github.com/Lokad/Parsing https://github.com/Lokad/Parsing In the end, what matters is that they should be able to report conflicts and ambiguities.
- _a_a_a_ 3y ago
  Are you saying PEGs can't conflicts and ambiguities? I didn't know that.
  - victorNicollet 3y ago
    Not having ambiguities is actually the main selling point of PEGs. If you have two rules A and B that can both match the input, then a CFG A|B has an ambiguity (two possible derivations), but a PEG A/B explicitly says that the A derivation is chosen. The good part is that unlike a CFG, the PEG doesn't require you to go and fix anything (the / operator already did that for you). This makes the initial implementation of the grammar easier. On the other hand, if you already have code in the wild that uses the old grammar G1, and in order to add new features, you introduce a new grammar G2 that is a superset of G1. You need to know if any of the existing code has a derivation in G2 that is different from its derivation in G1 (as that would cause backwards incompatibility). With a PEG, there's no way to tell, so you have to check this by hand (and mistakes are easy). With a CFG, you know that backwards incompatibility happens if and only if G2 has conflicts, and those conflicts are precisely the cases that are not backwards compatible.

FrustratedMonky 3y ago

Is an LR better than a parser/combinator. Seems like there are pluses to rolling your own parser/combinator over the time to integrate with a yacc or other library.

victorNicollet 3y ago
I am a bit biased (in the sense that I wrote my own SLR parser generator twice, in C# and F#!), but the benefit of LR is that you can know whether your CFG contains conflicts, which is a game changer for preserving backwards compatibility when you change the syntax later during the life of the DSL. But if a parser combinator library may support converting the resulting combined parser into an eBNF grammar, and check whether that grammar contains conflicts.
- marcosdumay 3y ago
  Hum... A grammar conflict on parser combinators always require that you step down from the parser abstraction and resolve it by hand with basic language functionality, doesn't it? It's something quite hard to notice. Are you concerned with the documentation getting out of sync with the actual language?
  - victorNicollet 3y ago
    In a situation where I'm adding a new feature to the language, with a new syntax that causes me to add a new rule to the grammar, I'm concerned that the new rule will accidentally "capture" some code that already exists in the wild, that was previously derived by another part of the grammar. To give a very ugly example, if you have a language with function calls f(expr, expr, expr) and you want to add tuple syntax to expressions with a brand new rule: expr := expr COMMA expr Then you might have accidentally turned all functions into unary functions, as the tuple rule captures the "expr, expr, expr" part and leaves you with f(expr).
- FrustratedMonky 3y ago
  I do love F# for parsing and for DSL's. Maybe it is 'functional' programming bias. IF you are using a 'functional' paradigm, you can do your own parser/combinator. But if you are using C#, you use something like Yacc and LR.?

trealira 3y ago

> Hand-written parsers are even worse. Using an LR parser generator is worth the time investment. I'm curious, what makes you say this? From what I've read online secondhand, people tend to recommend handwritten recursive descent parsing and Pratt/TDOP parsing, because it's easier to add good error messages and later add context sensitive productions (e.g. the way Clang resolves class-wide declarations while parsing C++: https://eli.thegreenplace.net/2012/07/05/how-clang-handles-the-type-variable-name-ambiguity-of-cc https://eli.thegreenplace.net/2012/07/05/how-clang-handles-t...).

mjul 3y ago
He explains it in the linked video presentation which is worth watching: the value being that your parser generator will complain about any ambiguity in the grammar (shift-reduce conflicts) rather than having that show up as a “wat?” at runtime. You might argue that this argument reduces to checking the grammar using static analysis similar to the order generator. But then handwriting the parser is still extra work and risk.
- civilitty 3y ago
  What I've seen most nontrivial projects do (and have done in a commercial product myself) is to start with a parser generator then move to hand written parsers when UX and polish become a bigger priority than exploring the problem space. The parser generator grammar spec can then be used to generate random test cases and compare the output of the new parser with the old one to make sure they're identical.

bloopernova 3y ago

Good lord yes on the language server. Reduce the friction involved with writing code. I'm frustrated with terraform-ls right now. It doesn't work with private module registries, reloading each module in the .terraform dir over and over. Which impacts performance by maxing out a CPU core. And yet a feature of Terraform Cloud (TFC) is that you can use private registries. Writing Terraform is already plagued by friction. Adding TFC adds to the friction. The language server then not loading private modules adds even more. Hopefully OpenTofu helps in that regard, but I don't think they've got anyone working on the language server either.

cube2222 3y ago
> but I don't think they've got anyone working on the language server either. Not yet, but it's on our radar. We're focusing on the stable release + registry for now (eta mid-December), but we're planning to work on the language server eventually. If you have any more frustrations with the language server, feel free to respond here, and it'll help us find avenues for improvements. Disclaimer: Interim Tech Lead of OpenTofu
- bloopernova 3y ago
  It's really not a frustration, I should have mentioned that you were going to look at it once things settled down :/ I'm incredibly supportive of your efforts, I just wish I was a good enough coder to pick up golang and make the language server better instead of just griping about it. I created a ticket about dedupe, but I have to admit it's a very low priority compared to so much other stuff. I think my only other suggestion would be to concentrate on making the tf development cycle quick and easy. The easier it is for people to write the code, the more code they'll write, even with copilot or other helpers.

starcraft2wol 3y ago

This is ridiculously not practical. For lisp programmers making dsls is just how you write programs and you don’t need a parser.

Too 3y ago

One more from me - Any expression that may likely include a user-generated variable should have a strategy for how to inject it safely. To avoid sql injection class of attacks. Native templating is the best. If string templating is the only way out, the rules for escaping should be clearly defined and ideally functions for doing so provided by the reference implementation. Not like the geniuses at Atlassian who came up with JQL that refuse to document how it works, instead delegates all security to the user model and “don’t run queries with any data that you didn’t provide yourself”.

eternityforest 3y ago

What kinds of use cases justify this much effort?