doc: add Google I/O talk and programs

R=r
CC=golang-dev
http://codereview.appspot.com/1614041

6 files changed, 722 insertions, 0 deletions

diff --git a/doc/talks/io2010/balance.go b/doc/talks/io2010/balance.go
new file mode 100644
index 000000000..6a0713831
--- /dev/null
+++ b/doc/talks/io2010/balance.go
@@ -0,0 +1,164 @@
+// Copyright 2010 The Go Authors.  All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package main
+
+import (
+	"container/heap"
+	"fmt"
+	"rand"
+	"time"
+)
+
+const nRequester = 100
+const nWorker = 10
+
+// Simulation of some work: just sleep for a while and report how long.
+func op() int {
+	n := rand.Int63n(1e9)
+	time.Sleep(nWorker * n)
+	return int(n)
+}
+
+type Request struct {
+	fn func() int
+	c  chan int
+}
+
+func requester(work chan Request) {
+	c := make(chan int)
+	for {
+		time.Sleep(rand.Int63n(nWorker * 2e9))
+		work <- Request{op, c}
+		<-c
+	}
+}
+
+type Worker struct {
+	i        int
+	requests chan Request
+	pending  int
+}
+
+func (w *Worker) work(done chan *Worker) {
+	for {
+		req := <-w.requests
+		req.c <- req.fn()
+		done <- w
+	}
+}
+
+type Pool []*Worker
+
+func (p Pool) Len() int { return len(p) }
+
+func (p Pool) Less(i, j int) bool {
+	return p[i].pending < p[j].pending
+}
+
+func (p *Pool) Swap(i, j int) {
+	a := *p
+	a[i], a[j] = a[j], a[i]
+	a[i].i = i
+	a[j].i = j
+}
+
+func (p *Pool) Push(x interface{}) {
+	a := *p
+	n := len(a)
+	a = a[0 : n+1]
+	w := x.(*Worker)
+	a[n] = w
+	w.i = n
+	*p = a
+}
+
+func (p *Pool) Pop() interface{} {
+	a := *p
+	*p = a[0 : len(a)-1]
+	w := a[len(a)-1]
+	w.i = -1 // for safety
+	return w
+}
+
+type Balancer struct {
+	pool Pool
+	done chan *Worker
+	i    int
+}
+
+func NewBalancer() *Balancer {
+	done := make(chan *Worker, nWorker)
+	b := &Balancer{make(Pool, 0, nWorker), done, 0}
+	for i := 0; i < nWorker; i++ {
+		w := &Worker{requests: make(chan Request, nRequester)}
+		heap.Push(&b.pool, w)
+		go w.work(b.done)
+	}
+	return b
+}
+
+func (b *Balancer) balance(work chan Request) {
+	for {
+		select {
+		case req := <-work:
+			b.dispatch(req)
+		case w := <-b.done:
+			b.completed(w)
+		}
+		b.print()
+	}
+}
+
+func (b *Balancer) print() {
+	sum := 0
+	sumsq := 0
+	for _, w := range b.pool {
+		fmt.Printf("%d ", w.pending)
+		sum += w.pending
+		sumsq += w.pending * w.pending
+	}
+	avg := float64(sum) / float64(len(b.pool))
+	variance := float64(sumsq)/float64(len(b.pool)) - avg*avg
+	fmt.Printf(" %.2f %.2f\n", avg, variance)
+}
+
+func (b *Balancer) dispatch(req Request) {
+	if false {
+		w := b.pool[b.i]
+		w.requests <- req
+		w.pending++
+		b.i++
+		if b.i >= len(b.pool) {
+			b.i = 0
+		}
+		return
+	}
+
+	w := heap.Pop(&b.pool).(*Worker)
+	w.requests <- req
+	w.pending++
+	//	fmt.Printf("started %p; now %d\n", w, w.pending)
+	heap.Push(&b.pool, w)
+}
+
+func (b *Balancer) completed(w *Worker) {
+	if false {
+		w.pending--
+		return
+	}
+
+	w.pending--
+	//	fmt.Printf("finished %p; now %d\n", w, w.pending)
+	heap.Remove(&b.pool, w.i)
+	heap.Push(&b.pool, w)
+}
+
+func main() {
+	work := make(chan Request)
+	for i := 0; i < nRequester; i++ {
+		go requester(work)
+	}
+	NewBalancer().balance(work)
+}
diff --git a/doc/talks/io2010/decrypt.go b/doc/talks/io2010/decrypt.go
new file mode 100644
index 000000000..3292c30b2
--- /dev/null
+++ b/doc/talks/io2010/decrypt.go
@@ -0,0 +1,40 @@
+// Copyright 2010 The Go Authors.  All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package main
+
+import (
+	"crypto/aes"
+	"crypto/block"
+	"compress/gzip"
+	"io"
+	"os"
+)
+
+func EncryptAndGzip(dstfile, srcfile string, key, iv []byte) {
+	r, _ := os.Open(srcfile, os.O_RDONLY, 0)
+	var w io.Writer
+	w, _ = os.Open(dstfile, os.O_WRONLY|os.O_CREATE, 0666)
+	c, _ := aes.NewCipher(key)
+	w = block.NewOFBWriter(c, iv, w)
+	w2, _ := gzip.NewDeflater(w)
+	io.Copy(w2, r)
+	w2.Close()
+}
+
+func DecryptAndGunzip(dstfile, srcfile string, key, iv []byte) {
+	f, _ := os.Open(srcfile, os.O_RDONLY, 0)
+	defer f.Close()
+	c, _ := aes.NewCipher(key)
+	r := block.NewOFBReader(c, iv, f)
+	r, _ = gzip.NewInflater(r)
+	w, _ := os.Open(dstfile, os.O_WRONLY|os.O_CREATE, 0666)
+	defer w.Close()
+	io.Copy(w, r)
+}
+
+func main() {
+	EncryptAndGzip("/tmp/passwd.gz", "/etc/passwd", make([]byte, 16), make([]byte, 16))
+	DecryptAndGunzip("/dev/stdout", "/tmp/passwd.gz", make([]byte, 16), make([]byte, 16))
+}
diff --git a/doc/talks/io2010/encrypt.go b/doc/talks/io2010/encrypt.go
new file mode 100644
index 000000000..e5ab3fc59
--- /dev/null
+++ b/doc/talks/io2010/encrypt.go
@@ -0,0 +1,28 @@
+// Copyright 2010 The Go Authors.  All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package main
+
+import (
+	"crypto/aes"
+	"crypto/block"
+	"compress/gzip"
+	"io"
+	"os"
+)
+
+func EncryptAndGzip(dstfile, srcfile string, key, iv []byte) {
+	r, _ := os.Open(srcfile, os.O_RDONLY, 0)
+	var w io.WriteCloser
+	w, _ = os.Open(dstfile, os.O_WRONLY|os.O_CREATE, 0666)
+	defer w.Close()
+	w, _ = gzip.NewDeflater(w)
+	defer w.Close()
+	c, _ := aes.NewCipher(key)
+	io.Copy(block.NewCBCEncrypter(c, iv, w), r)
+}
+
+func main() {
+	EncryptAndGzip("/tmp/passwd.gz", "/etc/passwd", make([]byte, 16), make([]byte, 16))
+}
diff --git a/doc/talks/io2010/eval1.go b/doc/talks/io2010/eval1.go
new file mode 100644
index 000000000..2d7fc3be6
--- /dev/null
+++ b/doc/talks/io2010/eval1.go
@@ -0,0 +1,229 @@
+// Copyright 2010 The Go Authors.  All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package main
+
+import (
+	"bufio"
+	"fmt"
+	"os"
+	"strconv"
+	"strings"
+)
+
+// Generic expression parser/evaluator
+
+type Value interface {
+	String() string
+	BinaryOp(op string, y Value) Value
+}
+
+type Parser struct {
+	precTab map[string]int
+	newVal  func(string) Value
+	src     string
+	pos     int
+	tok     string
+}
+
+const alphanum = "_abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
+
+func (p *Parser) stop(c uint8) bool {
+	switch {
+	case p.pos >= len(p.src):
+		return true
+	case c == '"':
+		if p.src[p.pos] == '"' {
+			p.pos++
+			return true
+		}
+		return false
+	case strings.IndexRune(alphanum, int(c)) >= 0:
+		return strings.IndexRune(alphanum, int(p.src[p.pos])) < 0
+	}
+	return true
+}
+
+func (p *Parser) next() {
+	// skip blanks
+	for ; p.pos < len(p.src) && p.src[p.pos] <= ' '; p.pos++ {
+	}
+	if p.pos >= len(p.src) {
+		p.tok = ""
+		return
+	}
+	start := p.pos
+	c := p.src[p.pos]
+	for p.pos < len(p.src) {
+		p.pos++
+		if p.stop(c) {
+			break
+		}
+	}
+	p.tok = p.src[start:p.pos]
+}
+
+func (p *Parser) binaryExpr(prec1 int) Value {
+	x := p.newVal(p.tok)
+	p.next()
+	for prec := p.precTab[p.tok]; prec >= prec1; prec-- {
+		for p.precTab[p.tok] == prec {
+			op := p.tok
+			p.next()
+			y := p.binaryExpr(prec + 1)
+			x = x.BinaryOp(op, y)
+		}
+	}
+	return x
+}
+
+func Eval(precTab map[string]int, newVal func(string) Value, src string) Value {
+	var p Parser
+	p.precTab = precTab
+	p.newVal = newVal
+	p.src = src
+	p.next()
+	return p.binaryExpr(1)
+}
+
+// Command-line expression evaluator
+
+func main() {
+	r := bufio.NewReader(os.Stdin)
+	for {
+		fmt.Printf("> ")
+		line, err := r.ReadString('\n')
+		if err != nil {
+			break
+		}
+		fmt.Printf("%s\n", Eval(precTab, trace(newVal), line))
+	}
+}
+
+
+// Custom grammar and values
+
+var precTab = map[string]int{
+	"&&": 1,
+	"||": 2,
+	"==": 3,
+	"!=": 3,
+	"<":  3,
+	"<=": 3,
+	">":  3,
+	">=": 3,
+	"+":  4,
+	"-":  4,
+	"*":  5,
+	"/":  5,
+	"%":  5,
+}
+
+func newVal(lit string) Value {
+	x, err := strconv.Atoi(lit)
+	if err == nil {
+		return Int(x)
+	}
+	b, err := strconv.Atob(lit)
+	if err == nil {
+		return Bool(b)
+	}
+	return Error(fmt.Sprintf("illegal literal '%s'", lit))
+}
+
+type Error string
+
+func (e Error) String() string                    { return string(e) }
+func (e Error) BinaryOp(op string, y Value) Value { return e }
+
+type Int int
+
+func (x Int) String() string { return strconv.Itoa(int(x)) }
+func (x Int) BinaryOp(op string, y Value) Value {
+	switch y := y.(type) {
+	case Error:
+		return y
+	case Int:
+		switch op {
+		case "+":
+			return x + y
+		case "-":
+			return x - y
+		case "*":
+			return x * y
+		case "/":
+			return x / y
+		case "%":
+			return x % y
+		case "==":
+			return Bool(x == y)
+		case "!=":
+			return Bool(x != y)
+		case "<":
+			return Bool(x < y)
+		case "<=":
+			return Bool(x <= y)
+		case ">":
+			return Bool(x > y)
+		case ">=":
+			return Bool(x >= y)
+		}
+	}
+	return Error(fmt.Sprintf("illegal operation: '%v %s %v'", x, op, y))
+}
+
+type Bool bool
+
+func (x Bool) String() string { return strconv.Btoa(bool(x)) }
+func (x Bool) BinaryOp(op string, y Value) Value {
+	switch y := y.(type) {
+	case Error:
+		return y
+	case Bool:
+		switch op {
+		case "&&":
+			return Bool(x && y)
+		case "||":
+			return Bool(x || y)
+		case "==":
+			return Bool(x == y)
+		case "!=":
+			return Bool(x != y)
+		}
+	}
+	return Error(fmt.Sprintf("illegal operation: '%v %s %v'", x, op, y))
+}
+
+
+func trace(newVal func(string) Value) func(string) Value {
+	return func(s string) Value {
+		v := newVal(s)
+		fmt.Printf("\tnewVal(%q) = %s\n", s, fmtv(v))
+		return &traceValue{v}
+	}
+}
+
+type traceValue struct {
+	Value
+}
+
+func (x *traceValue) BinaryOp(op string, y Value) Value {
+	z := x.Value.BinaryOp(op, y.(*traceValue).Value)
+	fmt.Printf("\t%s.BinaryOp(%q, %s) = %s\n", fmtv(x.Value), op, fmtv(y.(*traceValue).Value), fmtv(z))
+	return &traceValue{z}
+}
+
+func (x *traceValue) String() string {
+	s := x.Value.String()
+	fmt.Printf("\t%s.String() = %#v\n", fmtv(x.Value), s)
+	return s
+}
+
+func fmtv(v Value) string {
+	t := fmt.Sprintf("%T", v)
+	if i := strings.LastIndex(t, "."); i >= 0 { // strip package
+		t = t[i+1:]
+	}
+	return fmt.Sprintf("%s(%#v)", t, v)
+}
diff --git a/doc/talks/io2010/eval2.go b/doc/talks/io2010/eval2.go
new file mode 100644
index 000000000..5524c8b3a
--- /dev/null
+++ b/doc/talks/io2010/eval2.go
@@ -0,0 +1,261 @@
+// Copyright 2010 The Go Authors.  All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package main
+
+import (
+	"bufio"
+	"fmt"
+	"os"
+	"strconv"
+	"strings"
+)
+
+// Generic expression parser/evaluator
+
+type Value interface {
+	String() string
+	BinaryOp(op string, y Value) Value
+}
+
+type Parser struct {
+	precTab map[string]int
+	newVal  func(string) Value
+	src     string
+	pos     int
+	tok     string
+}
+
+const alphanum = "_abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
+
+func (p *Parser) stop(c uint8) bool {
+	switch {
+	case p.pos >= len(p.src):
+		return true
+	case c == '"':
+		if p.src[p.pos] == '"' {
+			p.pos++
+			return true
+		}
+		return false
+	case strings.IndexRune(alphanum, int(c)) >= 0:
+		return strings.IndexRune(alphanum, int(p.src[p.pos])) < 0
+	}
+	return true
+}
+
+func (p *Parser) next() {
+	// skip blanks
+	for ; p.pos < len(p.src) && p.src[p.pos] <= ' '; p.pos++ {
+	}
+	if p.pos >= len(p.src) {
+		p.tok = ""
+		return
+	}
+	start := p.pos
+	c := p.src[p.pos]
+	for p.pos < len(p.src) {
+		p.pos++
+		if p.stop(c) {
+			break
+		}
+	}
+	p.tok = p.src[start:p.pos]
+}
+
+func (p *Parser) binaryExpr(prec1 int) Value {
+	x := p.newVal(p.tok)
+	p.next()
+	for prec := p.precTab[p.tok]; prec >= prec1; prec-- {
+		for p.precTab[p.tok] == prec {
+			op := p.tok
+			p.next()
+			y := p.binaryExpr(prec + 1)
+			x = x.BinaryOp(op, y)
+		}
+	}
+	return x
+}
+
+func Eval(precTab map[string]int, newVal func(string) Value, src string) Value {
+	var p Parser
+	p.precTab = precTab
+	p.newVal = newVal
+	p.src = src
+	p.next()
+	return p.binaryExpr(1)
+}
+
+// Command-line expression evaluator
+
+func main() {
+	r := bufio.NewReader(os.Stdin)
+	for {
+		fmt.Printf("> ")
+		line, err := r.ReadString('\n')
+		if err != nil {
+			break
+		}
+		fmt.Printf("%s\n", Eval(precTab, trace(newVal), line))
+	}
+}
+
+
+// Custom grammar and values
+
+var precTab = map[string]int{
+	"&&": 1,
+	"||": 2,
+	"==": 3,
+	"!=": 3,
+	"<":  3,
+	"<=": 3,
+	">":  3,
+	">=": 3,
+	"+":  4,
+	"-":  4,
+	"*":  5,
+	"/":  5,
+	"%":  5,
+}
+
+func newVal(lit string) Value {
+	x, err := strconv.Atoi(lit)
+	if err == nil {
+		return Int(x)
+	}
+	b, err := strconv.Atob(lit)
+	if err == nil {
+		return Bool(b)
+	}
+	s, err := strconv.Unquote(lit)
+	if err == nil {
+		return String(s)
+	}
+	return Error(fmt.Sprintf("illegal literal '%s'", lit))
+}
+
+type Error string
+
+func (e Error) String() string                    { return string(e) }
+func (e Error) BinaryOp(op string, y Value) Value { return e }
+
+type Int int
+
+func (x Int) String() string { return strconv.Itoa(int(x)) }
+func (x Int) BinaryOp(op string, y Value) Value {
+	switch y := y.(type) {
+	case Error:
+		return y
+	case String:
+		switch op {
+		case "*":
+			return String(strings.Repeat(string(y), int(x)))
+		}
+	case Int:
+		switch op {
+		case "+":
+			return x + y
+		case "-":
+			return x - y
+		case "*":
+			return x * y
+		case "/":
+			return x / y
+		case "%":
+			return x % y
+		case "==":
+			return Bool(x == y)
+		case "!=":
+			return Bool(x != y)
+		case "<":
+			return Bool(x < y)
+		case "<=":
+			return Bool(x <= y)
+		case ">":
+			return Bool(x > y)
+		case ">=":
+			return Bool(x >= y)
+		}
+	}
+	return Error(fmt.Sprintf("illegal operation: '%v %s %v'", x, op, y))
+}
+
+type Bool bool
+
+func (x Bool) String() string { return strconv.Btoa(bool(x)) }
+func (x Bool) BinaryOp(op string, y Value) Value {
+	switch y := y.(type) {
+	case Error:
+		return y
+	case Bool:
+		switch op {
+		case "&&":
+			return Bool(x && y)
+		case "||":
+			return Bool(x || y)
+		case "==":
+			return Bool(x == y)
+		case "!=":
+			return Bool(x != y)
+		}
+	}
+	return Error(fmt.Sprintf("illegal operation: '%v %s %v'", x, op, y))
+}
+
+type String string
+
+func (x String) String() string { return strconv.Quote(string(x)) }
+func (x String) BinaryOp(op string, y Value) Value {
+	switch y := y.(type) {
+	case Error:
+		return y
+	case Int:
+		switch op {
+		case "*":
+			return String(strings.Repeat(string(x), int(y)))
+		}
+	case String:
+		switch op {
+		case "+":
+			return x + y
+		case "<":
+			return Bool(x < y)
+		}
+	}
+	return Error(fmt.Sprintf("illegal operation: '%v %s %v'", x, op, y))
+}
+
+
+func trace(newVal func(string) Value) func(string) Value {
+	return func(s string) Value {
+		v := newVal(s)
+		fmt.Printf("\tnewVal(%q) = %s\n", s, fmtv(v))
+		return &traceValue{v}
+	}
+}
+
+type traceValue struct {
+	Value
+}
+
+func (x *traceValue) BinaryOp(op string, y Value) Value {
+	z := x.Value.BinaryOp(op, y.(*traceValue).Value)
+	fmt.Printf("\t%s.BinaryOp(%q, %s) = %s\n", fmtv(x.Value), op, fmtv(y.(*traceValue).Value), fmtv(z))
+	return &traceValue{z}
+}
+
+func (x *traceValue) String() string {
+	s := x.Value.String()
+	fmt.Printf("\t%s.String() = %#v\n", fmtv(x.Value), s)
+	return s
+}
+
+func fmtv(v Value) string {
+	t := fmt.Sprintf("%T", v)
+	if i := strings.LastIndex(t, "."); i >= 0 { // strip package
+		t = t[i+1:]
+	}
+	return fmt.Sprintf("%s(%#v)", t, v)
+}
diff --git a/doc/talks/io2010/talk.pdf b/doc/talks/io2010/talk.pdf
new file mode 100644
index 000000000..aff42c21d
--- /dev/null
+++ b/doc/talks/io2010/talk.pdf