godfw-hoq-20160405.slide

Writing an Interpreter in Go

John Scott
jmscott@setspace.com
https://github.com/jmscott

Unix/Database Consultant
Founder, SetSpace, Inc, 1998-now
Founder, august.{com,net}, Inc, 1998-2006

Capitol One Conference Center
Plano, Texas, USA
April 5, 2016

* Paul Graham - YCombinator
 Your mind is like a compiled program you've lost the source of.
 It works, but you don't know why.

* What is a Compiler?
- program that transforms a formal language into another formal language
- immutable - same input language always yields same output language
- output language - called the _target_ - executes "fastest"
Does a compilier define semantics of either source or target language?

* Examples of Typically Compiled Languages
- go
- c
- java
- perl5 is *NOT* compiled
- *perl6* will eventually be compiled
- YACC compiles Backus-Naur into Go (and many other languages)
- Ken Thompson (gofather) compilied regular expressions into `pdp11` assembler
- compiling SQL into native code (Oracle, PostgreSQL)

* What is an Interpreter?
- program that directly executes the source program (often text)

.image godfw-hoq-20160405/tao.gif

- bourne shell, awk, javascript, ruby, SQL
- lisp was the first interpreter
- the java command is an interpreter (strictly) of compiled java class files

* Interpreter Translates Source into Internal Format
.image godfw-hoq-20160405/ast.png
.caption Abstract Syntax Tree (perl5, awk)
- line by line (many unix shells)
- virtual machine instruction (python, ruby, vbasic, , perl6)
- java translates jvm opcodes into native hardware instructions

* Abstract Syntax Tree of a Query Fragment in HOQ
.image godfw-hoq-20160405/ast.png
.caption Query Fragment
  $1 == "INBOUND" and ( $2 ~~ "^10[.]" or $2 ~~ "^192[.]168" )

* What is HOQ?
- Higher Order Query
- toy interpreter that demonstrates the famous YACC compiler for Go language
- also, hopefully, demonstrates "Communicating Sequential Processes"

Did I bite off more than I can chew?

* Inspired by "HOC" Calculator in Unix Programming Environment
.image godfw-hoq-20160405/upe.jpg
.caption Higher Order Calculator - Chapter 8
.caption Mighty Fine Book

* How Do We Invoke HOQ?
- command line program invoked with script as first argument
.html godfw-hoq-20160405/hoq.term
- hoq script _may_ invoke other unix programs and wait for their exit status

* HOQ Execution is Driven by Standard Input
- consuming text drives the execution of the whole hoq script
.html godfw-hoq-20160405/tr.term
.caption Terminal
- hoq terminates after reading the the final line and waiting for all processes to exit.

* HOQ Splits Input Into Fields
- input lines `strings.Split()` on tab separated boundaries
 line = strings.TrimRight(line, "\n")
 ...
 fields:   strings.SplitN(line, "\t", 255),
- `$1` is first tab separated field, `$2` is second field, ...
- `$0` is whole, current line, including tabs, minus terminating new line

* HOQ is Mostly Declarative
- qualify on patterns in tab separated field ($1, $2)
- qualify on process exit status codes (`uint8`)
- boolean combinations (logical and, or, not) on any qualifications
- subprocess are executed when boolean qualifications are true
Execution order of subprocess is directed acylic graph (DAG) 

* Hello, World

.code godfw-hoq-20160405/say.hoq 
.caption say.hoq

* Invoke Say
.code godfw-hoq-20160405/say.hoq 
.caption say.hoq

.html godfw-hoq-20160405/say.term 
.caption Terminal

* Good Bye, Cruel World
.code godfw-hoq-20160405/say-bye.hoq 
.caption say-bye.hoq

.html godfw-hoq-20160405/say-bye.term 

* Trinity
.code godfw-hoq-20160405/say-trinity.hoq 
.caption say-trinity.hoq
.html godfw-hoq-20160405/say-trinity.term 

* A Complex Qualification
.code godfw-hoq-20160405/complex.hoq
.caption Edited from https://github.com/jmscott/setspace/blob/master/schema/setspace/setspace.flow.example

* Is Wu Wei Nothing?

* Idiom #1 - Turn Any Function into a Channel
.play godfw-hoq-20160405/fib-seq.go
.caption Fibonacci is a Sequential Function

* Fibonacci Becomes a Channel
.code godfw-hoq-20160405/fib-chan.go /^func fib_chan/,/^}/
.caption Idiom #1 - Turn Any Function into a Channel

* Idiom #1 - Run the Fibonacci Series
.play godfw-hoq-20160405/fib-chan.go /^func main/,/^}/
.caption Idiom #1 - Turn Any Function into a Channel

* Abstract Syntax Tree is a Flow Graph
.image godfw-hoq-20160405/ast.png
 $1 == "INBOUND" and ( $2 ~~ "^10[.]" or $2 ~~ "^192[.]168[.]" )

* Data Flows From Leaves to Root
.image godfw-hoq-20160405/ast-flow.png
Each Edge is a Go Channel
.caption Each Node is an "OpCode" in a Flow Machine
 $1 == "INBOUND" and ( $2 ~~ "^10[.]" or $2 ~~ "^192[.]168[.]" )

* AST Query Fragment: Data Flows Towards String Equality Operand
.image godfw-hoq-20160405/ast-equal.png
 $1 == "INBOUND"

* AST Query Fragment: Send String Constant to Equality Operand
.image godfw-hoq-20160405/ast-push.png
Similar to Push in Sequential Machine

* Opcode: const_string()
.code godfw-hoq-20160405/opcode-const-string.go /^type string_value struct/,/^type string_chan chan/
.code godfw-hoq-20160405/opcode-const-string.go /^func/,/^}$/
.caption 'Push' a String Constant

* Idiom #2 - select{} on Two Channels Allows Concurrent Operands
.image godfw-hoq-20160405/opcode-idiom2.png
 $1 ~~ "^10[.]"

* The regex.Match() is a Binary Relation on Two Strings
.code godfw-hoq-20160405/opcode-rel2-string.go /^import /,/^}$/
.caption import "regexp"
.code godfw-hoq-20160405/opcode-rel2-string.go /^type bool_value struct/,/^type bool_chan chan/
.caption Idiom #2 - select{} on Two Channels Allows Concurrent Operands

* - OpCode: Relational Binary Operator on Two Strings
.code godfw-hoq-20160405/opcode-rel2-string.go /^func.*string_rel2/,/START FLOW OMIT/
.caption Upper Half of string_rel2()
.html godfw-hoq-20160405/splice-loop.html
.code godfw-hoq-20160405/opcode-rel2-string.go /END FLOW OMIT/,/^}/
.caption Lower Half of string_rel2()
.caption Idiom #2 - select{} on Two Channels Allows Concurrent Operands

*  Relational Binary Operator on Two Strings - Main Loop (Idiom #2)
.code godfw-hoq-20160405/opcode-rel2-string.go /START FLOW OMIT/,/END FLOW OMIT/

* 16 Opcodes of Flow Machine
- const_string, const_bool, const_uint8
- to_string_uint8, to_string_bool
- dollar, dollar0
- string_rel2, uint8_rel2, bool_rel2
- argv0, argv1, argv
- exec
- fanout_uint8, fanin_uint8

* Exec() of Command Sends Exit Status When Qualification is True
.code godfw-hoq-20160405/exec-xtrue.hoq
.html godfw-hoq-20160405/exec-xtrue.term

* Exec() of Command Sends Null When Qualification is False or Null
.code godfw-hoq-20160405/exec-false.hoq
.html godfw-hoq-20160405/exec-false.term

* Logical Boolean Operators Follow Strict SQL Semantics

Logical AND

.code godfw-hoq-20160405/and.txt

Logical OR

.code godfw-hoq-20160405/or.txt

All other binary operators are null if either operand is null

* Idiom #3 - Channels Over Channels
.code godfw-hoq-20160405/flow-get.go

* Flow Structure Synchronizes Operators
.code godfw-hoq-20160405/flow.go
.caption Idiom #3 - Channels Over Channels

* Each Opcode Syncs with main() on Each "Tick"
.image godfw-hoq-20160405/flow-sync.png 
.caption $1 == "INBOUND" and ( $2 ~~ "^10[.]" or $2 ~~ "^192[.]168[.]" )

* Idiom #4 - Close(channel) is a Cheap Broadcast
.code godfw-hoq-20160405/cheap-broad.go
.html godfw-hoq-20160405/splice-loop.html
 }

* Flow A and Flow B Run Concurrently
.code godfw-hoq-20160405/main.go
.caption Idiom #4 - Close(channel) is a Cheap Broadcast

* What is Go YACC?
- Compiles a Flavor of Backus-Naur Form (BNF) into Go Code
- Original Golang Grammar written in YACC
- Domain Specific Languages (chemical reactions, SAT solvers)
- Mutation Coverage

* Mechanics of YACC
- YACC generated Go code reads a stream of integers called <TOKEN>s
- Patterns are recognized in stream of <TOKEN>s
- Each pattern has an associated block of manually written Go code
- When the pattern is recognized in the stream then associated block of Go is invoked
- Patterns are recusive

* Backus-Naur Grammar of Backus-Naur Form
.code godfw-hoq-20160405/bnf.bnf

.caption Whitespace/Comment not specified. <TOKEN> is scanned integers, 'a'=97

* YACC Grammar for HOQ Language (Backus-Naur Form)
.code godfw-hoq-20160405/hoq.bnf
.caption Stripped from https://github.com/jmscott/play/blob/master/hoq/src/parser.y

* YACC/Go Code Snippet of Qualification Expression in HOQ Grammar 
.code godfw-hoq-20160405/exp.y
In YACC $1 is value of first term; $2 is value of second term ...
$$ is value of new, reduced term

* YACC Needs a Lexer 
- lexer easy to write by hand !!!
- just a big switch{}
- busts text into stream of integer tokens
- scanned token has a simple value related to scan yylval.(string, float, uint8)
- token const defined by YACC (see %token in grammar)
- co-routines invented to write lexers (Rob Pike)

* Go Files on github.com/jmscott
- hoq.go
- ast.go
- command.go
- compile.go
- opcode.go
- parser.y
- rummy.go
- tsort.go
.link https://github.com/jmscott/play/tree/master/hoq/src

* YACC Resources
.link https://docs.google.com/document/d/1P3BLR31VA8cvLJLfMibSuTdwTuF7WWLux71CYD0eeD8/edit Early GoLang in YACC
.link http://www.amazon.com/Unix-Programming-Environment-Prentice-Hall-Software/dp/013937681X Book 'Unix Programming Environment" by Kernighan and Pike
.link http://heim.ifi.uio.no/inf2270/programmer/historien-om-C.pdf C Written in Yacc
.link https://github.com/golang-samples/yacc Simple Go Calculator
.link https://golang.org/pkg/go/ast/ Go AST Library
.link https://godoc.org/golang.org/x/exp/ebnf EBNF in GoLang

* Lex Resources
.link https://www.youtube.com/watch?v=HxaD_trXwRE Lexer Talk by Rob Pike
.link http://www.colm.net/open-source/ragel/ Ragle is a Lexical Compiler
.link http://www-cs-students.stanford.edu/~blynn/nex/ Nex (New Lex)

* CSP Resources
.link http://research.swtch.com/power