Makefile: The F# compiler has changed its name.

[fringe] / go-fringe.go

/* -*-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 --------------------------------------------------