From d888ccd559a84c180936e9adadae1f655f15356e Mon Sep 17 00:00:00 2001
From: Mark Wooding <mdw@distorted.org.uk>
Date: Mon, 30 Nov 2009 09:20:06 +0000
Subject: [PATCH] go: New language.

Do iteration with goroutines and channels.  It's much prettier than
doing it with closures.
---
 .gitignore   |   2 +
 Makefile     |  15 +++++++
 go-fringe.go | 143 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 160 insertions(+)
 create mode 100644 go-fringe.go

diff --git a/.gitignore b/.gitignore
index a66409a..2f9d34e 100644
--- a/.gitignore
+++ b/.gitignore
@@ -7,3 +7,5 @@ test.log
 *.hi
 *.core
 *-fringe
+*.8
+*.6
diff --git a/Makefile b/Makefile
index 119a8ff..b79bf6a 100644
--- a/Makefile
+++ b/Makefile
@@ -130,6 +130,21 @@ scheme-fringe: scheme-fringe.o
 	$(SCMC) -o $@ $^
 
 ###--------------------------------------------------------------------------
+### Go.
+
+GOOBJ			 = 8
+GOC			 = $(GOOBJ)g
+GOLINK			 = $(GOOBJ)l
+CLEANFILES		+= *.$(GOOBJ)
+.SUFFIXES: .$(GOOBJ) .go
+.go.$(GOOBJ):; $(GOC) $(GOFLAGS) $<
+
+LANGS			+= go
+SOURCES			+= go-fringe.go
+go-fringe: go-fringe.$(GOOBJ)
+	$(GOLINK) -o $@ $^
+
+###--------------------------------------------------------------------------
 ### Smalltalk.
 
 LANGS			+= smalltalk
diff --git a/go-fringe.go b/go-fringe.go
new file mode 100644
index 0000000..70e23b5
--- /dev/null
+++ b/go-fringe.go
@@ -0,0 +1,143 @@
+/* -*-go-*-
+ *
+ * Same-fringe solver.
+ */
+
+package main
+
+import (
+	"fmt";
+	"io";
+	"os";
+)
+
+///--------------------------------------------------------------------------
+/// Utilities.
+
+var prog = os.Args[0];
+
+func bail(msg string) {
+	fmt.Fprintf(os.Stderr, "%s: %s\n", prog, msg);
+	os.Exit(1);
+}
+
+///--------------------------------------------------------------------------
+/// Iteration protocol.
+///
+/// A data type implements the iteration protocol by providing a method which
+/// simply writes its consistuent elements to a provided channel.  The
+/// iteration machinery runs this method in a separate goroutine.
+
+// A convenient abbreviation.
+type any interface {}
+
+type Iterable interface {
+	// Simply put the items to the channel CH one at a time.
+	Iterate(ch chan<- any);
+}
+
+// An iterator.
+type Iterator <-chan any;
+
+// Returns an iterator for a given iterable thing.
+func MakeIterator(it Iterable) Iterator {
+	ch := make(chan any);
+	go func () {
+		it.Iterate(ch);
+		close(ch);
+	} ();
+	return ch;
+}
+
+// Returns the next item from an iterator IT.  If there is indeed an item
+// available, return it and true; otherwise return nil and false.
+func (it Iterator) Next() (any, bool) {
+	item := <-it;
+	if closed(it) { return nil, false; }
+	return item, true;
+}
+
+// Answer whether the iterators return the same items in the same order.
+// Equality is determined using `=='.  Maybe we'll do better some day.
+func SameIterators(ia, ib Iterator) bool {
+	for {
+		a, any_a := ia.Next();
+		b, any_b := ib.Next();
+		if !any_a { return !any_b }
+		if a != b { break }
+	}
+	return false;
+}
+
+///--------------------------------------------------------------------------
+/// Node structure.
+
+// Just a simple binary tree.
+type Node struct {
+	data byte;
+	left, right *Node;
+}
+
+// Iteration is easy.  Note that recursion is fine here: this is just a
+// simple function.
+func (n *Node) Iterate(ch chan<- any) {
+	if n == nil { return }
+	n.left.Iterate(ch);
+	ch <- n.data;
+	n.right.Iterate(ch);
+}
+
+// Parse a tree from a textual description.  The syntax is simple:
+//
+//	tree ::= empty | `(' tree char tree `)'
+//
+// where the ambiguity is resolved by declaring that a `(' is a tree if we're
+// expecting a tree.
+func ParseTree(s string) *Node {
+	var parse func(int) (*Node, int);
+	n := len(s);
+	i := 0;
+	parse = func(i int) (*Node, int) {
+		if i < n && s[i] == '(' {
+			left, i := parse(i + 1);
+			if i >= n { bail("no data") }
+			data := s[i];
+			right, i := parse(i + 1);
+			if i >= n || s[i] != ')' { bail("missing )") }
+			return &Node { data, left, right }, i + 1;
+		}
+		return nil, i;
+	};
+	t, i := parse(0);
+	if i < n { bail("trailing junk") }
+	return t;
+}
+
+///--------------------------------------------------------------------------
+/// Main program.
+
+func main() {
+	switch len(os.Args) {
+	case 2:
+		t := ParseTree(os.Args[1]);
+		i := MakeIterator(t);
+		for {
+			item, winp := i.Next();
+			if !winp { break }
+			fmt.Printf("%c", item);
+		}
+		fmt.Printf("\n");
+	case 3:
+		ia := MakeIterator(ParseTree(os.Args[1]));
+		ib := MakeIterator(ParseTree(os.Args[2]));
+		if SameIterators(ia, ib) {
+			io.WriteString(os.Stdout, "match\n");
+		} else {
+			io.WriteString(os.Stdout, "no match\n");
+		}
+	default:
+		bail("bad args");
+	}
+}
+
+///----- That's all, folks --------------------------------------------------
-- 
2.11.0