Building a simple concurrency teaching language with Go

15 August 2018

Nicholas Ng

Imperial College London

About me

Postdoc @ Imperial College

2

Concurrency @ IC

Disclaimer - course is not directly related to talk

3

Formal models of concurrency

The actor model

Process calculi

Alternatives

4

Formal concurrency models vs. Concurrent programming

Formal concurrency models

Concurrent programming

🤔 Executable formal model?

5

asyncpi: A teaching language based on "asynchronous π-calculus"

The asynchronous π-calculus (Honda, Tokoro 1991; Boudol 1992)

Objectives

6

This talk

7

The asyncpi language

    P,Q ::= 0           nil process
          | P|Q         parallel composition of P and Q
          | (new a)P    generation of a with scope P
          | !P          replication of P, i.e. infinite parallel composition  P|P|P...
          | u<v>        output of v on channel u
          | u(x).P      input of distinct variables x on u, with continuation P

A grammar specifies the syntax of the language, e.g.

(new ch)    # Create a new channel ch
(
  ch<a>     # Send on channel ch with a as parameter
  |         # Parallel composition - think spawn goroutine
  ch(x)     # Receive x on channel ch
   .0       # End of process (receive always have continuation)
)

Objective: make this input machine-readable

8

Parsing

Read stream of symbols of given grammar into abstract syntax tree

// +build ignore

package main

import (
	"fmt"
	"log"
	"strings"

	"go.nickng.io/asyncpi"
)

func main() {
    const example = `
(new ch)    # Create a new channel ch
(
  ch<a>     # Send on channel ch with a as parameter
  |         # Parallel composition - think spawn goroutine
  ch(x)     # Receive x on channel ch
   .0       # End of process (receive always have continuation)
)`

    process, err := asyncpi.Parse(strings.NewReader(example))
    if err != nil {
        log.Fatal("parse failed:", err)
    }
    fmt.Println("AST:", process) // AST of process
    fmt.Println("Calculi:", process.Calculi())
}

Implement Parse by fmt.Scanf?

9

golang.org/x/tools/cmd/goyacc

yacc (Yet Another Compiler-Compiler) is a parser generator

goyacc -p asyncpi -o parser.y.go asyncpi.y

More about parsing with Go

10

go generate

Instead of

#!/bin/sh

goyacc -p asyncpi -o parser.y.go asyncpi.y

Put this in a .go file:

//go:generate goyacc -p asyncpi -o parser.y.go asyncpi.y

package main

func main() {
    // ... uses parser.y.go
}
11

Objectives

12

Process reduction

We can write code to reduce in Go..

13

Process reduction

// +build ignore

package main

import (
	"fmt"
	"go/format"
	"io/ioutil"
	"log"
	"os"
	"strings"

	"go.nickng.io/asyncpi"
	"golang.org/x/tools/imports"
)

func main() {
    const sendrecv = `
    (new ch)(       # Create a channel "ch"
      ch<a>         # Send to "ch"
      | ch(x).0     # Concurrently, Receive from "ch"
    )`
    proc, err := asyncpi.Parse(strings.NewReader(sendrecv))
    if err != nil {
        // handle error
    }
    fmt.Printf("Before reduction:\n\t%s\n", proc.Calculi())

    // Reduce system for a single step
    asyncpi.Reduce1(proc)

    fmt.Printf("After reduction:\n\t%s\n", proc.Calculi())
}

func mustParse(s string) asyncpi.Process {
	proc, err := asyncpi.Parse(strings.NewReader(s))
	if err != nil {
		log.Fatal("parse failed:", err)
	}
	return proc
}

func reduceAll(proc asyncpi.Process) asyncpi.Process {
	for {
		changed, err := asyncpi.Reduce1(proc)
		if err != nil {
			log.Fatal("reduction error", err) // handle errors
			break
		}
		if !changed {
			break
		}
		proc, _ = asyncpi.SimplifyBySC(proc)
		fmt.Println("→ Reduces to:", proc.Calculi())
	}
	return proc
}

func fixImports(src []byte) []byte {
	opts := &imports.Options{TabIndent: true, Fragment: false}
	imported, err := imports.Process("/tmp/main.go", src, opts)
	if err != nil {
		log.Fatal(err)
	}
	return imported
}

func goFmt(src []byte) []byte {
	fmtd, err := format.Source(src)
	if err != nil {
		log.Fatal(err)
	}
	return fmtd
}

func writeTemp(content []byte) {
	f, err := ioutil.TempFile("", "generated")
	os.Rename(f.Name(), f.Name()+".go")
	if err != nil {
		log.Fatal(err)
	}
	if _, err := f.Write(content); err != nil {
		log.Fatal(err)
	}
	fmt.Println("written to temp file:", f.Name()+".go")
}
14

Play with processes in Go

// +build ignore

package main

import (
	"fmt"
	"go/format"
	"io/ioutil"
	"log"
	"os"
	"strings"

	"go.nickng.io/asyncpi"
	"golang.org/x/tools/imports"
)

func main() {
    const chainReaction = `
    (new ch2)(ch2<1, 2> | ch2(x, y).((new ch3) (ch3<x> | ch3(z).ch3(z).0 | ch3<y>)))`
    proc := mustParse(chainReaction)

    fmt.Println(proc.Calculi())
    // Keep reducing until not possible
    for {
        changed, err := asyncpi.Reduce1(proc)
        if err != nil {
            log.Fatal("reduction error", err) // handle errors
            break
        }
        if !changed {
            break
        }
        proc, _ = asyncpi.SimplifyBySC(proc)
        fmt.Println("→ Reduces to:", proc.Calculi())
    }
}

func mustParse(s string) asyncpi.Process {
	proc, err := asyncpi.Parse(strings.NewReader(s))
	if err != nil {
		log.Fatal("parse failed:", err)
	}
	return proc
}

func reduceAll(proc asyncpi.Process) asyncpi.Process {
	for {
		changed, err := asyncpi.Reduce1(proc)
		if err != nil {
			log.Fatal("reduction error", err) // handle errors
			break
		}
		if !changed {
			break
		}
		proc, _ = asyncpi.SimplifyBySC(proc)
		fmt.Println("→ Reduces to:", proc.Calculi())
	}
	return proc
}

func fixImports(src []byte) []byte {
	opts := &imports.Options{TabIndent: true, Fragment: false}
	imported, err := imports.Process("/tmp/main.go", src, opts)
	if err != nil {
		log.Fatal(err)
	}
	return imported
}

func goFmt(src []byte) []byte {
	fmtd, err := format.Source(src)
	if err != nil {
		log.Fatal(err)
	}
	return fmtd
}

func writeTemp(content []byte) {
	f, err := ioutil.TempFile("", "generated")
	os.Rename(f.Name(), f.Name()+".go")
	if err != nil {
		log.Fatal(err)
	}
	if _, err := f.Write(content); err != nil {
		log.Fatal(err)
	}
	fmt.Println("written to temp file:", f.Name()+".go")
}
15

Objectives

16

Generate Go code from asyncpi

// +build appengine

package main

import (
	"bytes"
	"fmt"
	"go/format"
	"log"
	"strings"

	"go.nickng.io/asyncpi"
	"go.nickng.io/asyncpi/codegen/golang"
	"golang.org/x/tools/imports"
)

func main() {
    const sendrecv = `
    (new ch)(       # Create a channel "ch"
      ch<a>         # Send to "ch"
      | ch(x).0      # Concurrently, Receive from "ch"
    )`
    proc := mustParse(sendrecv)

    var gocode bytes.Buffer
    if err := golang.Generate(proc, &gocode); err != nil {
        // handle error
    }
    fmt.Println(gocode.String())
}

func mustParse(s string) asyncpi.Process {
	proc, err := asyncpi.Parse(strings.NewReader(s))
	if err != nil {
		log.Fatal("parse failed:", err)
	}
	return proc
}

func reduceAll(proc asyncpi.Process) asyncpi.Process {
	for {
		changed, err := asyncpi.Reduce1(proc)
		if err != nil {
			log.Fatal("reduction error", err) // handle errors
			break
		}
		if !changed {
			break
		}
		proc, _ = asyncpi.SimplifyBySC(proc)
		fmt.Println("→ Reduces to:", proc.Calculi())
	}
	return proc
}

func fixImports(src []byte) []byte {
	opts := &imports.Options{TabIndent: true, Fragment: false}
	imported, err := imports.Process("/tmp/main.go", src, opts)
	if err != nil {
		log.Fatal(err)
	}
	return imported
}

func goFmt(src []byte) []byte {
	fmtd, err := format.Source(src)
	if err != nil {
		log.Fatal(err)
	}
	return fmtd
}
17

go/format package

Every Go programmer should know "gofmt"

You can also use go/format to format Go code (snippets)

// +build ignore

package main

import (
	"bytes"
	"fmt"
	"go/format"
	"io/ioutil"
	"log"
	"os"
	"strings"

	"go.nickng.io/asyncpi"
	"go.nickng.io/asyncpi/codegen/golang"
	"golang.org/x/tools/imports"
)

const chainReaction = `(new ch2)(ch2<1, 2> | ch2(x, y).((new ch3) (ch3<x> | ch3(z).ch3(z).0 | ch3<y>)))`
const sendrecv = `
    (new ch)(       # Create a channel "ch"
      ch<>          # Send to "ch"
      | ch().0      # Concurrently, Receive from "ch"
    )`

func main() {
    // import "go/format"

    var gocode bytes.Buffer
    err := golang.Generate(mustParse(sendrecv), &gocode)
    if err != nil {
        // handle error
    }

    formatted, err := format.Source(gocode.Bytes())
    if err != nil {
        // handle error
    }
    fmt.Println(string(formatted))
}

func mustParse(s string) asyncpi.Process {
	proc, err := asyncpi.Parse(strings.NewReader(s))
	if err != nil {
		log.Fatal("parse failed:", err)
	}
	return proc
}

func reduceAll(proc asyncpi.Process) asyncpi.Process {
	for {
		changed, err := asyncpi.Reduce1(proc)
		if err != nil {
			log.Fatal("reduction error", err) // handle errors
			break
		}
		if !changed {
			break
		}
		proc, _ = asyncpi.SimplifyBySC(proc)
		fmt.Println("→ Reduces to:", proc.Calculi())
	}
	return proc
}

func fixImports(src []byte) []byte {
	opts := &imports.Options{TabIndent: true, Fragment: false}
	imported, err := imports.Process("/tmp/main.go", src, opts)
	if err != nil {
		log.Fatal(err)
	}
	return imported
}

func goFmt(src []byte) []byte {
	fmtd, err := format.Source(src)
	if err != nil {
		log.Fatal(err)
	}
	return fmtd
}

func writeTemp(content []byte) {
	f, err := ioutil.TempFile("", "generated")
	os.Rename(f.Name(), f.Name()+".go")
	if err != nil {
		log.Fatal(err)
	}
	if _, err := f.Write(content); err != nil {
		log.Fatal(err)
	}
	fmt.Println("written to temp file:", f.Name()+".go")
}
18

golang.org/x/tools/imports package

You can also use imports to fix imports

// +build ignore

package main

import (
	"bytes"
	"fmt"
	"go/format"
	"io/ioutil"
	"log"
	"os"
	"strings"

	"go.nickng.io/asyncpi"
	"go.nickng.io/asyncpi/codegen/golang"
	"golang.org/x/tools/imports"
)

const sendrecv = `
    (new ch)(       # Create a channel "ch"
      ch<>          # Send to "ch"
      | ch().0      # Concurrently, Receive from "ch"
    )`
const chainReaction = `(new ch2)(ch2<1, 2> | ch2(x, y).((new ch3) (ch3<x> | ch3(z).ch3(z).0 | ch3<y>)))`

var withMain = golang.FormatOptions{
	Main:  true,
	Debug: true,
}

func main() {
    // import "golang.org/x/tools/imports"

    var gocode bytes.Buffer
    err := golang.GenerateOpts(mustParse(sendrecv), withMain, &gocode)
    if err != nil {
        // handle error
    }

    opts := &imports.Options{TabIndent: true, Fragment: false, Comments: true}
    generated, err := imports.Process("/tmp/main.go", gocode.Bytes(), opts)
    if err != nil {
        // handle error
    }

    fmt.Println(string(generated))
    //writeTemp(generated)
}

func mustParse(s string) asyncpi.Process {
	proc, err := asyncpi.Parse(strings.NewReader(s))
	if err != nil {
		log.Fatal("parse failed:", err)
	}
	return proc
}

func reduceAll(proc asyncpi.Process) asyncpi.Process {
	for {
		changed, err := asyncpi.Reduce1(proc)
		if err != nil {
			log.Fatal("reduction error", err) // handle errors
			break
		}
		if !changed {
			break
		}
		proc, _ = asyncpi.SimplifyBySC(proc)
		fmt.Println("→ Reduces to:", proc.Calculi())
	}
	return proc
}

func fixImports(src []byte) []byte {
	opts := &imports.Options{TabIndent: true, Fragment: false}
	imported, err := imports.Process("/tmp/main.go", src, opts)
	if err != nil {
		log.Fatal(err)
	}
	return imported
}

func goFmt(src []byte) []byte {
	fmtd, err := format.Source(src)
	if err != nil {
		log.Fatal(err)
	}
	return fmtd
}

func writeTemp(content []byte) {
	f, err := ioutil.TempFile("", "generated")
	os.Rename(f.Name(), f.Name()+".go")
	if err != nil {
		log.Fatal(err)
	}
	if _, err := f.Write(content); err != nil {
		log.Fatal(err)
	}
	fmt.Println("written to temp file:", f.Name()+".go")
}
19

Another use of generating Go code

// +build ignore

package main

import (
	"bytes"
	"fmt"
	"go/format"
	"io/ioutil"
	"log"
	"os"
	"strings"

	"go.nickng.io/asyncpi"
	"go.nickng.io/asyncpi/codegen/golang"
	"golang.org/x/tools/imports"
)

const chainReaction = `(new ch2)(ch2<1, 2> | ch2(x, y).((new ch3) (ch3<x> | ch3(z).ch3(z).0 | ch3<y>)))`
const sendrecv = `(new ch)(ch<> | ch().ch().0)`

var gocode bytes.Buffer

var withMain = golang.FormatOptions{
	Debug: true,
	Main:  true,
}

func main() {
    const srr = `(new ch)(ch<> | ch().ch().0)`
    proc := mustParse(srr)
    golang.GenerateOpts(proc, withMain, &gocode)
    fmt.Println(proc.Calculi())
    reduceAll(proc)

    generated := fixImports(gocode.Bytes())
    fmt.Println(string(generated))
    // writeTemp(generated)
}

func mustParse(s string) asyncpi.Process {
	proc, err := asyncpi.Parse(strings.NewReader(s))
	if err != nil {
		log.Fatal("parse failed:", err)
	}
	return proc
}

func reduceAll(proc asyncpi.Process) asyncpi.Process {
	for {
		changed, err := asyncpi.Reduce1(proc)
		if err != nil {
			log.Fatal("reduction error", err) // handle errors
			break
		}
		if !changed {
			break
		}
		proc, _ = asyncpi.SimplifyBySC(proc)
		fmt.Println("→ Reduces to:", proc.Calculi())
	}
	return proc
}

func fixImports(src []byte) []byte {
	opts := &imports.Options{TabIndent: true, Fragment: false}
	imported, err := imports.Process("/tmp/main.go", src, opts)
	if err != nil {
		log.Fatal(err)
	}
	return imported
}

func goFmt(src []byte) []byte {
	fmtd, err := format.Source(src)
	if err != nil {
		log.Fatal(err)
	}
	return fmtd
}

func writeTemp(content []byte) {
	f, err := ioutil.TempFile("", "generated")
	os.Rename(f.Name(), f.Name()+".go")
	if err != nil {
		log.Fatal(err)
	}
	if _, err := f.Write(content); err != nil {
		log.Fatal(err)
	}
	fmt.Println("written to temp file:", f.Name()+".go")
}
20

Objectives

21

Summary

22

More?

23

Thank you

Nicholas Ng

Imperial College London

Use the left and right arrow keys or click the left and right edges of the page to navigate between slides.
(Press 'H' or navigate to hide this message.)