Pause-able Parsing and Elegant Interpreters in Go: Using Goroutines as Coroutines
20 September 2016
Tags: zygomys, coroutines, pause-able parsing

Jason E. Aten, Ph.D.
Principal Engineer, Sauce Labs
j.e.aten@gmail.com
@jasonaten_

https://github.com/glycerine/zygomys

[[https://github.com/glycerine/zygomys/wiki.]] The wiki has details, examples, and discussion.

* problem: implementating an interpreter efficiently

- suppose your code is running, and deep inside a nested set of possibly mutually recursive calls...
- and you run out of input.
- ... do you start all over?
- ... and take O(n^2) time to parse an n-line program? Ouch.
- you want to save your state, and resume later, exactly where you left off...
- this is exactly what happens at the interpreter prompt

* generally

- how to refactor your straight line code...
- to pause - and - resume gracefully
- to be interuptable
- to be lazy

* benefits of this style

- more coherency: keep the readability of straight-line code
- insert pause points after the fact
- easier to read => means easier to maintain, refactor, and extend


* context: zygomys interpreter

- an interpreted scripting language
- built in Go, for steering Go
- reflect to invoke compiled Go code
- zygomys has closures with lexical scope
- for loops
- higher order functions
- readable math: anything inside curly braces {} is infix. example: a = 2 * 5 + 4 / 2
.link https://github.com/glycerine/zygomys https://github.com/glycerine/zygomys

* context II: architecture / overview of zygomys implementation

- a) lexer produces tokens
- b) parser produces lists and arrays of symbols  <<<== focus of this talk
- c) macros run at definition type
- d) codegen produces s-expression byte-code
- e) a virtual machine executes the byte-code

* what specifically changes to make code pause-able? And more importantly, resumable?

* original parseArray (only 50% shown/fits on a screen)

.code orig.parser1.go

* before, closeup

.code before1.go

* after, closeup

.code after1.go

* zoom out: after in full context

.code after1full.go

* the key was getMoreInput() call instead of returning io.EOF... simple enough, but...

* that begs the question, how does getMoreInput() work...

* apparently the real magic is in getMoreInput(). It must be doing the heavy lifting...

* getMoreInput()

.code getmore2.go

* HaveStuffToSend() is easy...

.code havestuff.go

* what is unusual about getMoreInput()

- it can be called from multiple places
- callers get to retain the entire context of their call stack
- getMoreInput() returns to its caller precisely once the caller can continue
- and in the meantime, it does the channel work in a select{} to get more input from an asynchronous source

- In my humble experience, this is rare: a co-routine pattern
- Caller's code gets to pause. And then resume, right where it left off.

* supporting player: a background goroutine running an infinite loop that drives parsing. It also calls getMoreInput() to start top-level parsing.

.code infparse_nocomment.go

* call graph

.image med2.jpg

* so what does the Parser API look like from the outside?

* here is what the user sees:

* what the Parser API looks like

.code parser_api.go

* conclusion

- coroutine patterns are viable in Go
- we can avoid O(n^2) time interpreter parsing
- other uses: functional programming patterns like (lazy) generators[1]

-
-

[1] John Hughes, Why Functional Programming Matters
.link https://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf