go: New language.

Do iteration with goroutines and channels.  It's much prettier than
doing it with closures.

diff --git a/.gitignore b/.gitignore
index a66409a..2f9d34e 100644 (file)
--- 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 (file)
--- 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 (file)
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 --------------------------------------------------