Experience Report: Using Coroutines for Parsing

[Romain Doumenc]

Hi everyone,

I took some time over the past weeks to experiment with the coroutine switching capabilities in the runtime – in this case for parsing.

I find this new API extremely useful, and started seeing quite a few places in the code base I maintain to simplify some complicated, synchronized, stateful machines.

The document is at: https://trout-software.notion.site/Parsing-with-Coroutines-13bf9f8a093980d7a0fcf41b81594677

I hope it is useful for others also interested in experimenting
--
Romain

[roger peppe]

Interesting! Thanks for sharing.

This is related to something that I've been planning to explore for a while now: using iterators themselves and their associated coroutines accessed via `iter.Pull`, to do parsing. That is, instead of gaining access to the underlying coroutine machinery by use of "go:linkname", perhaps we can get a bunch of the same advantages by using the more structured form already provided by the standard library.

I suspect that the feedback from parser to scanner you describe can be implemented by allowing the parser to invoke methods on the iteration values (tokens) returned by the scanner.

I wonder if the result might actually be nicer (easier to understand and better structured) than the direct use of coroutines, which personally I find quite hard to "get".

  rog.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/golang-nuts/d095a5d6-679f-4c13-82d3-7acf07cf9996n%40googlegroups.com.

[robert engels]

I agree, all you need is generators - that they are implemented with coroutines is immaterial.

Take a look at this, and substitute the yield() function for crReturn().

To view this discussion visit https://groups.google.com/d/msgid/golang-nuts/CAJhgacjwXX6EeRt5%2BzDhy_15wXyvNxHv8CAfLvu0nTz1w2KJPQ%40mail.gmail.com.

[Romain Doumenc]

Hi Roger,

Glad you found this interesting, and thank you for reading !

One can obviously always use methods on a structure instead of
coroutines (in the example I provided, the state could be stored in
the tokenizer), and the question is when storing the state on the Go
stack directly makes code more readable – and yes, a lot of what
“readable” means is colored by one’s own experience.
I think the largest benefit does not stem from the feedback from the
parser to the tokeniser (although I do find it very cute), but instead
from the ability of the parent routine to restart the parser when an
error is found. With coroutines, this can be expressed as a simple for
loop; but I have not seen something as neat with other methods –
either stack unwinding (hard to maintain invariants) or instead
pushing deep down in the parser the knowledge about how much tokens to
throw away.

My goal in reaching code currently hidden in the library was to see
how much more we could do if we had full coroutines, and not making
any claim about finding a “best” or even a “better” approach. Looking
forward to seeing what you create with iterators!

Best
--
Romain

[robert engels]

Btw, wasn’t being dismissive of your effort - I only linked to the article (which is pretty old) because it covers many of the same ideas you were discussing - and whenever I get the chance to link to something involving Knuth I am going to take it :)

> --
> You received this message because you are subscribed to the Google Groups "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

> To view this discussion visit https://groups.google.com/d/msgid/golang-nuts/CAMYUV_oa_DEWceZUFx6EqPjkJ1cqVA5GS6pQEeK-h%3DkrExAhiA%40mail.gmail.com.

[roger peppe]

On Mon, 18 Nov 2024 at 18:02, Romain Doumenc <rom...@trout.software> wrote:

Hi Roger,

Glad you found this interesting, and thank you for reading !

One can obviously always use methods on a structure instead of
coroutines (in the example I provided, the state could be stored in
the tokenizer), and the question is when storing the state on the Go
stack directly makes code more readable

That's not quite what I meant. I was suggesting exactly storing the state

on the Go stack, just as you're doing with your coroutines, but instead

of using the internal Go API, ISTM that it should be possible to use

iter.Pull, which uses coroutines under the hood, instead.

Here is a sketch of the idea: https://go.dev/play/p/pFHvaSgOn9c

 

  cheers,

    rog.

[Jason E. Aten]

I implemented this iter.Pull strategy for keeping parser state, instead of

using a background goroutine (as I did for years) in my pure Go lisp, zygomys, 

and the resulting code is much easier to read and follow, and about 12% faster on 

Linux (although 0.3% slower on Darwin).

Details and specific code here:

https://github.com/glycerine/zygomys?tab=readme-ov-file#v9-release-notes-using-iterator-instead-of-a-goroutine-for-parser-state

v8.1.0 has the old goroutine version, v9.0.7 has the new iterator pull (implicit coroutine, so

no linkname hacking required) version, if you want to compare code side-by-side. 

See the zygo/parser.go file specifically to compare the read-ability.

It might look a little strange, because you store the iterator, the yield(), next(), and stop() func

as members in the Parser state, but it works, and works well. 

I'm much happier re-using my library for things like JSON or config parsing without having to worry about

the extra background goroutine in my stack dumps, which was always a bit surprising.

- Jason

[roger peppe]

Glad to hear it worked out for you! 

  rog.

--

You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/golang-nuts/e79975fe-6839-4d4d-8e52-f26748c1bdbcn%40googlegroups.com.