2

I am currently developing my own programming language (written in Lua). The text analyzer is composed of two functions: lexer and parser.

lexer takes as input a string, cycles over each character of it and divides it in tokens, either single words, numbers, strings, or symbols. It then returns an array of them.

parser takes a string too, internally calls lexer over it, and then, with the help of some recursive helper functions, builds a tree structure over the array returned from lexer

Now, this seems like a good example where the use of Lua's coroutines would fit very well: parser, as a normal function, would feed characters to the lexer coroutine, which waits until it has enough characters to return a token. Then parser uses that token for its tree structure.

This would require a bit of extra work to convert my code, but the question is: is it worth it? The code would probably consume less memory, but what are the other advantages? Would it be faster? More readable (probably not)? Should I overall do it?

  • 1
    Using co-routines you can suspend parsing in the middle of a message. That could be helpful when you parse large data that slowly arrives over time. (Though I'd consider redesigning the protocol in that case) – CodesInChaos Aug 24 '16 at 10:42
  • That's a thing I didn't think of. Fair enough. Previously, the way the REPL for my language worked was: Try parsing this first line; if an "unfinished X" error occours, concatenate to another line and retry parsing; Repeat until no "unfinished X" error occours, then parse the whole text and interpret the generated structure. But this opens the way to far nicer solutions on that side. Thanks for pointing it out! – user6245072 Aug 24 '16 at 10:52
1

This would require a bit of extra work to convert my code, but the question is: is it worth it? The code would probably consume less memory, but what are the other advantages? Would it be faster? More readable (probably not)? Should I overall do it?

The last thing I would consider using coroutines for is computational efficiency. They have lots of overhead in terms of capturing the state of the call stack and so forth and branching into instructions to resume where you left off (that's almost always a superset of the data and memory you need to do what you need to do if you programmed it absent coroutines which store/spill all that state).

They're all about productivity to me. Sometimes it's a bit time-consuming to implement even a forward iterator to a complex graph data structure, while the recursive coroutine implementation might be a lot simpler while making the data structure really easy to use for clients. That's when I reach for coroutines. When I'm that concerned with computational efficiency I don't even reach for Lua, not even LuaJIT.

This would require a bit of extra work to convert my code, but the question is: is it worth it?

I wouldn't even consider rewriting working, well-tested code to use coroutines if it does fine without them. That's implementation details, and I don't care about those. If it tests and works correctly and performs handsomely, then I don't care if it's using coroutines or whatever, and I don't think anyone should either until they should. If it doesn't work well at all and you're struggling to get anything right while tripping on bugs left and right because it's so hard to get these things right absent coroutines, then maybe using coroutines in the implementation might save the day, or not, but they're not some magical feature of the kind that should tempt you to rewrite what already works fine without them.

The code would probably consume less memory [...]

Why on earth would you think this? Coroutines almost always require a superset of the memory/data to the alternatives, because they have to be able to resume execution from any arbitrary point in the call stack. Human programmers usually have more information about exactly what data/memory they need in those contexts, and it's not like coroutines are optimized by wizardry as far as optimizers go. So it's usually the opposite; coroutines take more memory, not less, and are generally less efficient, not more, than the alternatives. But they can be a massive productivity boost to developers in some scenarios in helping them implement their code more simply and correctly.

1

Having one routine/thread feed another and wait for it to finish is pretty pointless, that is just a complicated way to do things synchronously/sequentially. What you can do in your case is put several lexers at work on different files and have your parser wait for them to finish.

You will find you need all of your lexer results before you can perform a meaningful parser operation (the parser needs to know what namespaces and methods are available in order to assess whether some call is possible or its syntax is correct for example). Lexing however you can do on a per file basis.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.