Language and shell in Go with 92% test coverage and instant CI/CD [video]
youtube.com
youtube.com
If you're interested in Elvish, you may also be interested in the talk on its design - https://www.youtube.com/watch?v=wrl9foNXdgM
What's in the 8% not covered by testing?
The remaining 8% mostly falls into the following categories:
- Code that use OS functionalities that are cumbersome to mock in tests
- Code paths that are triggered relatively rarely and I was simply too lazy to add tests for them
Nothing is impossible to cover, but for whatever reason it was too much work for me when I wrote the code.
However, it's worth mentioning that I only settled on the transcript test pattern fairly recently, and if I were to rewrite or refactor some of the untested code today I would add tests for them, because the cost of adding tests has been lowered considerably. So Elvish's test coverage is still increasing slowly as the cost of testing decreases.
It's not easy to present though. I know on HN we see a lot of very clever people give some well executed presentations and it's sometimes easy to forget how much preparation and courage it takes to perform like that. And it's great to see how engaged people were with the content too.
Sorry, this is less of a question and more just comment of appreciation.
This is meant as additional information not criticism. I skimmed the transcript really fast so if this is in there and I missed it, please correct me, but two things I think are helpful for people creating projects like this to be aware of:
- This video seems to combine the concepts of lexing and parsing. It is usually beneficial to separate these two steps and lex the input into tokens before passing to the parser.
- Go actually has a pure Go implementation of Yacc in the toolset and I've used it in several projects to make parses. Dealing with the Yacc file is often much easier than dealing with code directly since it takes care of writing the actual parser. There is a lot of boiler plate that goes into parsers that when you use Yacc it "just works".
Edit: there are also some tools for writing parsers in Lex/Flex like syntax (re2c comes to mind) but I've found hand writing lexers to be effective in Go if your language doesn't have many different types of tokens.
So you either need to implement the lexer hack, or have a "string" token type which is disambiguated by the parser (which is what fish-shell does).
As the "Lexer hack" Wiki page says, this is only a problem if you're lexing in the first place. If you just parse the grammar, this isn't a problem.
git "commit" "-am" "message"
ls "-l"
etcLex/Flex takes care of that mostly for you which is one of the benefits of using a well worn lexer generator and not rolling your own.
I didn't have much time in the talk to go into the reason, so here it is:
- You'll need a more complex lexer to parse a shell-like syntax. For example, one common thing you do with lexers is get rid of whitespaces, but shell syntax is whitespace sensitive: "a$x" and "a $x" (double quotes not part of the code) are different things: the first is a single word containing a string concatenation, the second is two separate words.
- If your parser backtracks a lot, lexing can improve performance: you're not going back characters, only tokens (and there are fewer tokens than characters). Elvish's parser doesn't backtrack. (It does use lookahead fairly liberally.)
Having a lexerless parser does mean that you have to constantly deal with whitespaces in every place though, and it can get a bit annoying. But personally I like the conceptual simplicity and not having to deal with silly tokens like LBRACE, LPAREN, PIPE.
I have not used parser generators enough to comment about the benefits of using them compared to writing a parser by hand. The handwritten one works well so far :)
But I do get your meaning, I've written a lot of tokenizers by hand as well, sometimes they can be easier to follow the hand written code. Config files for grammars can get convoluted fast.
But again, I was not meaning it as criticism. But your talk title does start with "How to write a programming language and shell in Go" so given the title I think Lexers / Tokenizers are worth noting.
The authoritative tone of "how to write ..." is meant in jest, but obviously by doing that I risk being misunderstood. A more accurate title would be "how I wrote ...", but it's slightly boring and I was trying hard to get my talk proposal accepted you see :)
Honestly, I think this is overstating the amount of boilerplate in a parser and overstating how well a parser generator "just works". I haven't used Yacc, so maybe it's better than ANTLR, but having tried ANTLR and written a few recursive descent parsers I've been pretty well cured of wanting to ever use a parser generator. ANTLR's generated code is verbose, the data structures are hard to work with, and error handling leaves a lot to be desired.
Parser boilerplate can be reduced to a large extent with a good set of helper methods (I often find myself referring back to the set used in Crafting Interpreters [0]), and what you get in exchange is full control over the data structure generated by the parser and over the error handling. For a language that you're serious about, that tradeoff is totally worth it.
I'd be willing to believe that beyond a certain level of input complexity, ANTLR no longer pays for itself. In my experience, there exists a class of languages for which there's no better tool.
I certainly feel the amount of boilerplate in my hand-rolled recursive-descent parser is manageable. Of course it's not as succinct as an EBNF grammar:
- For example, you have to write an actual loop (with "for" and looping conditions) instead of just * for repetition
- The Go formatter demands a newline in most control flows
- Go is also not the most succinct language in general
So you do end up with many more lines of code. But at the end of the day, the structure of each parsing function is remarkably similar to a production rule, and for simpler ones I can mentally map between them pretty easily, with the added benefit of being able to insert code anywhere if I need something beyond old-school context-free parsing.
Historically, yes. In recent years combined lever-parsers have outperformed dedicated lexer + dedicated parser combinations, and with modern tooling this isn’t the janky mess it used to be. Some of the best tools out there are combined lexer-parsers.
With traditional techniques, yes. But if you eg use parser combinators (which would admittedly a bit unusual in Go), combining both steps is pretty common.
> - Go actually has a pure Go implementation of Yacc in the toolset and I've used it in several projects to make parses. Dealing with the Yacc file is often much easier than dealing with code directly since it takes care of writing the actual parser. There is a lot of boiler plate that goes into parsers that when you use Yacc it "just works".
You are right that it's best to avoid Go when you can. Just like Java folks (stereotypically) seemed to avoid writing Java at all costs and rather wrote XML config files to drive their logic.
Yacc (and lex) are otherwise not good choice for specifying languages these days.
As the sibling comment mentioned, you can find documentation on Elvish itself on the website https://elv.sh. There are tutorials and (not 100% but fairly complete) reference documents.