'go fmt' pass on number breeding program.

[surreal-numbers] / chapter-1-experiments / ch1-breeding-numbers.go

diff --git a/chapter-1-experiments/ch1-breeding-numbers.go b/chapter-1-experiments/ch1-breeding-numbers.go
index 1e53fc3..a2b8d34 100644 (file)
--- a/chapter-1-experiments/ch1-breeding-numbers.go
+++ b/chapter-1-experiments/ch1-breeding-numbers.go
@@ -4,9 +4,400 @@
 package main
 
 import (
 package main
 
 import (

-    "fmt"
+       "flag"
+       "fmt"
+       "log"
+       "os"
+       "runtime/pprof"
+       "sort"

 )
 
 )
 

+// =============================================================================
+
+// This program recognizes four types of numbers:
+//   - Surreal symbols, like those generated by Axiom 1.
+//   - Surreal numbers, like those selected by Axiom 2.
+//   - Reduced form numbers, per Definition 7.
+//   - Named form numbers, which are the equivalence classes induced by
+//         Definition 6, represented by the first representative reduced
+//         form number encountered at runtime.
+//
+// Although the surrealNumber type can represent any of these four types of
+// numbers, the surrealUniverse contains only named form numbers.
+//
+// All equality tests (e.g. eq, geq, leq) in this program actually test for
+// similarity per Definition 6.
+
+// =============================================================================
+
+type surrealUniverse struct {
+       // The elements in this slice are stored in order according to Axiom 3.
+       // Thus, numbers[0] < numbers[1] < ... < numbers[n].
+       numbers      []surrealNumber
+       nextUniqueID uint
+}
+
+func (u *surrealUniverse) getIndex(num surrealNumber) int {
+       // Since getIndex() is only ever called on 'num' which already exists in
+       // the universe, we return the result directly, without bothering to
+       // confirm an exact match.
+       //
+       // Also, we can get away with a direct comparison of these floating point
+       // numbers since there will be an exact match, guaranteed since 'num' is
+       // already in the universe.
+       return sort.Search(u.cardinality(), func(i int) bool { return u.numbers[i].value >= num.value })
+}
+
+func (u *surrealUniverse) cardinality() int {
+       return len(u.numbers)
+}
+
+func (u *surrealUniverse) insert(num surrealNumber) {
+       // Before we can insert a number into the universe, we must first determine
+       // if it is newly discovered. We do this by looking at its ancestors, all
+       // guaranteed to be on the number line by construction, finding three
+       // cases:
+       //
+       //   1. There are zero ancestors.
+       //      We have rediscovered 0 and can abort the insertion unless creating
+       //      a brand new universe.
+       //
+       //   2. There is one ancestor.
+       //      If the number extends the number line, it is new, otherwise it will
+       //      be similar to a form with two ancestors and should be ignored since
+       //      the two ancestor form is a better visual representation.
+       //
+       //   3. There are two ancestors.
+       //      The number is only new if both ancestors are side-by-side on the
+       //      number line.
+
+       ancestorCount := num.leftSet.cardinality() + num.rightSet.cardinality()
+       switch ancestorCount {
+       case 0:
+               if u.cardinality() == 0 {
+                       num.value = 0.0
+                       num.identifier = u.nextUniqueID
+                       u.nextUniqueID++
+                       u.numbers = append(u.numbers, num)
+               }
+       case 1:
+               if num.leftSet.cardinality() == 1 {
+                       index := u.getIndex(num.leftSet.members[0])
+                       if index+1 == u.cardinality() {
+                               num.value = u.numbers[u.cardinality()-1].value + 1.0
+                               num.identifier = u.nextUniqueID
+                               u.nextUniqueID++
+                               u.numbers = append(u.numbers, num)
+                       }
+               } else {
+                       index := u.getIndex(num.rightSet.members[0])
+                       if index == 0 {
+                               num.value = u.numbers[0].value - 1.0
+                               num.identifier = u.nextUniqueID
+                               u.nextUniqueID++
+                               u.numbers = append(u.numbers[:1], u.numbers...)
+                               u.numbers[0] = num
+                       }
+               }
+       case 2:
+               leftIndex := u.getIndex(num.leftSet.members[0])
+               rightIndex := u.getIndex(num.rightSet.members[0])
+               if leftIndex+1 == rightIndex {
+                       num.value = (num.leftSet.members[0].value + num.rightSet.members[0].value) / 2
+                       num.identifier = u.nextUniqueID
+                       u.nextUniqueID++
+                       u.numbers = append(u.numbers[:rightIndex+1], u.numbers[rightIndex:]...)
+                       u.numbers[rightIndex] = num
+               }
+       }
+}
+
+// =============================================================================
+
+// Note: The following comparison functions apply only to numbers already in
+// the universe, not to new numbers constructed from the universe.  To
+// determine where a (potentially) new number goes, first insert it into the
+// universe.
+
+// This function implements Axiom 3 and is the root of all other comparisons.
+func (u *surrealUniverse) isRelated(numA, numB surrealNumber) bool {
+       // By construction, no number in this program will ever have more than one
+       // element in its right or left sets, nor will those elements be of a form
+       // other than that 'registered' with the universe. That allows direct
+       // comparisons using the surrealNumber.identifier field via u.getIndex().
+
+       // ---------------------------------
+
+       // First we implement the check "no member of the first number's left set
+       // is greater than or equal to the second number".
+       if numA.leftSet.cardinality() == 1 {
+               if u.getIndex(numA.leftSet.members[0]) >= u.getIndex(numB) {
+                       return false
+               }
+       }
+
+       // Now we implement the check "no member of the second number's right set
+       // is less than or equal to the first number".
+       if numB.rightSet.cardinality() == 1 {
+               if u.getIndex(numB.rightSet.members[0]) <= u.getIndex(numA) {
+                       return false
+               }
+       }
+
+       return true
+}
+
+func (u *surrealUniverse) isSimilar(numA, numB surrealNumber) bool {
+       if u.isRelated(numA, numB) && u.isRelated(numB, numA) {
+               return true
+       }
+       return false
+}
+
+func (u *surrealUniverse) equal(left, right surrealNumber) bool {
+       return u.isSimilar(left, right)
+}
+
+func (u *surrealUniverse) lessThanOrEqual(left, right surrealNumber) bool {
+       return u.isRelated(left, right)
+}
+
+func (u *surrealUniverse) lessThan(left, right surrealNumber) bool {
+       return u.lessThanOrEqual(left, right) && !u.equal(left, right)
+}
+
+func (u *surrealUniverse) greaterThanOrEqual(left, right surrealNumber) bool {
+       return !u.lessThan(left, right)
+}
+
+func (u *surrealUniverse) greaterThan(left, right surrealNumber) bool {
+       return !u.isRelated(left, right)
+}
+
+// =============================================================================
+
+type surrealNumber struct {
+       leftSet    surrealSet
+       rightSet   surrealSet
+       value      float64
+       identifier uint
+       generation int
+}
+
+type surrealSet struct {
+       members []surrealNumber
+}
+
+func (s *surrealSet) isMember(num surrealNumber, u surrealUniverse) bool {
+       for i := 0; i < len(s.members); i++ {
+               if u.equal(num, s.members[i]) {
+                       return true
+               }
+       }
+       return false
+}
+
+func (s *surrealSet) cardinality() int {
+       return len(s.members)
+}
+
+func (s *surrealSet) insert(num surrealNumber, u surrealUniverse) {
+       if !s.isMember(num, u) {
+               s.members = append(s.members, num)
+       }
+}
+
+func (s *surrealSet) remove(num surrealNumber, u surrealUniverse) {
+       for i := 0; i < len(s.members); i++ {
+               if u.equal(num, s.members[i]) {
+                       s.members[i] = s.members[len(s.members)-1]
+                       s.members = s.members[:len(s.members)-1]
+               }
+       }
+}
+
+// =============================================================================
+

 func main() {
 func main() {

-    fmt.Println("Hello, World!")
+       // Flags to enable various performance profiling options.
+       cpuProfile := flag.String("cpuprofile", "", "Filename for saving CPU profile output.")
+       memProfile := flag.String("memprofile", "", "Filename for saving memory profile output.")
+       suppressOutput := flag.Bool("silent", false, "Suppress printing of numberline at end of simulation. Useful when profiling.")
+
+       // Obtain termination conditions from user.
+       totalGenerations := flag.Int("generations", 2, "Number of generations of surreal numbers to breed.")
+       flag.Parse()
+       if *totalGenerations < 1 {
+               log.Fatal("ERROR: The argument to '-generations' must be greater than zero.")
+       }
+       remainingGenerations := *totalGenerations - 1
+
+       // Setup any CPU performance profiling requested by the user. This will run
+       // throughout program execution.
+       if *cpuProfile != "" {
+               cpuProFile, err := os.Create(*cpuProfile)
+               if err != nil {
+                       log.Fatal("ERROR: Unable to open CPU profiling output file:", err)
+               }
+               pprof.StartCPUProfile(cpuProFile)
+               defer pprof.StopCPUProfile()
+       }
+
+       // Build a universe to contain all the surreal numbers we breed.
+       // Seed it by hand with the number zero as generation-0.
+       var universe surrealUniverse
+       universe.nextUniqueID = 0
+       fmt.Println("Seeding generation 0 by hand.")
+       universe.insert(surrealNumber{surrealSet{}, surrealSet{}, 0.0, 0, 0})
+
+       // Breed however many generations of numbers were requested by the user and
+       // add them all to the universe.
+       fmt.Printf("Breeding Generation:")
+       for generation := 1; generation <= remainingGenerations; generation++ {
+               // Give the user some idea of overall progress during long jobs.
+               if generation != 1 {
+                       fmt.Printf(",")
+               }
+               fmt.Printf(" %d", generation)
+
+               // First generate all possible new numbers in this generation.
+               potentiallyNewNumbers := permuteExistingNumbers(generation, universe)
+               // Attempt to add the new numbers to the universe. Any duplicates will
+               // be weeded out in the attempt.
+               addNumbersToUniverse(potentiallyNewNumbers, &universe)
+       }
+       fmt.Printf(".\n")
+
+       // Setup any memory profiling requested by the user. This will snapshot
+       // the heap only at this point, after all numbers were generated.
+       if *memProfile != "" {
+               memProFile, err := os.Create(*memProfile)
+               if err != nil {
+                       log.Fatal("ERROR: Unable to open heap profile output file:", err)
+               }
+               pprof.WriteHeapProfile(memProFile)
+               memProFile.Close()
+       }
+
+       // Print the number line with generation on the horizontal axis and
+       // magnitude on the vertical axis.
+       if !(*suppressOutput) {
+               for i := 0; i < universe.cardinality(); i++ {
+                       printlnNumber(universe.numbers[i])
+               }
+       }
+       fmt.Println("After", *totalGenerations, "generations, the universe contains", len(universe.numbers), "numbers.")
+       fmt.Println("If output looks poor, ensure tabstop is eight spaces and that output doesn't wrap.")
+}
+
+// =============================================================================
+
+// We will only build permutations with 0 or 1 elements in each of the left and
+// right sets. This covers all the reduced form permutations. Any longer
+// permutations will be similar to one of the reduced forms.
+func permuteExistingNumbers(generation int, universe surrealUniverse) []surrealNumber {
+       // Profiling indicates that most calls to growSlice() and memMove()
+       // originate in this function. Allocating a sufficiently large slice
+       // upfront results in 2x speed improvement and 1/3 reduction in heap usage.
+       numberOfPermutations := ((universe.cardinality() + 1) * (universe.cardinality() + 1)) - 1
+       numbers := make([]surrealNumber, 0, numberOfPermutations)
+
+       // First build permutations with 1 element in each set.
+       for i := 0; i < universe.cardinality(); i++ {
+               for j := 0; j < universe.cardinality(); j++ {
+                       var leftSet, rightSet surrealSet
+                       leftSet.insert(universe.numbers[i], universe)
+                       rightSet.insert(universe.numbers[j], universe)
+                       newSurrealNumber := surrealNumber{leftSet, rightSet, 0.0, 0, generation}
+                       if isValidSurrealNumber(newSurrealNumber, universe) {
+                               numbers = append(numbers, newSurrealNumber)
+                       }
+               }
+       }
+       // Now build permutations with one empty set and one 1-element set.
+       for i := 0; i < universe.cardinality(); i++ {
+               var tempSet surrealSet
+               tempSet.insert(universe.numbers[i], universe)
+               newSurrealNumber := surrealNumber{tempSet, surrealSet{}, 0.0, 0, generation}
+               numbers = append(numbers, newSurrealNumber)
+               newSurrealNumber = surrealNumber{surrealSet{}, tempSet, 0.0, 0, generation}
+               numbers = append(numbers, newSurrealNumber)
+       }
+
+       return numbers
+}
+
+// Although a non-reduced-form number is technically valid, for the purposes of
+// this program we're declaring it invalid.
+func isValidSurrealNumber(candidate surrealNumber, universe surrealUniverse) bool {
+       // Is the number in reduced form?
+       if candidate.leftSet.cardinality() > 1 || candidate.rightSet.cardinality() > 1 {
+               return false
+       }
+
+       // Is the number valid per Axiom 2?
+       if candidate.leftSet.cardinality() != 0 && candidate.rightSet.cardinality() != 0 {
+               for i := 0; i < candidate.leftSet.cardinality(); i++ {
+                       for j := 0; j < candidate.leftSet.cardinality(); j++ {
+                               // Since candidates are drawn from the universe, this comparison is allowed.
+                               if universe.greaterThanOrEqual(candidate.leftSet.members[i], candidate.rightSet.members[j]) {
+                                       return false
+                               }
+                       }
+               }
+       }
+
+       return true
+}
+
+func addNumbersToUniverse(numbers []surrealNumber, universe *surrealUniverse) {
+       for i := 0; i < len(numbers); i++ {
+               universe.insert(numbers[i])
+       }
+}
+
+// Pretty print a number, indenting to indicate generation.
+func printlnNumber(num surrealNumber) {
+       for i := 0; i < num.generation; i++ {
+               fmt.Printf(".\t\t")
+       }
+       fmt.Printf("%s = ", toBase26(num.identifier))
+       fmt.Printf("<")
+       if num.leftSet.cardinality() == 0 {
+               fmt.Printf("---")
+       } else {
+               fmt.Printf("%s", toBase26(num.leftSet.members[0].identifier))
+       }
+       fmt.Printf("|")
+       if num.rightSet.cardinality() == 0 {
+               fmt.Printf("---")
+       } else {
+               fmt.Printf("%s", toBase26(num.rightSet.members[0].identifier))
+       }
+       fmt.Printf(">")
+       fmt.Printf("\n")
+}
+
+// This function is a total hack, intended only to avoid printing identifiers
+// as actual numbers since we don't want to imply any particular association to
+// specific 'real' numbers yet. Instead, print them with [a-z] as base-26
+// integers.
+func toBase26(num uint) (base26String []byte) {
+       // For alignment reasons, we never print more than three digits. Thus, any
+       // number greater than (26^3)-1 is out of range.
+       if num >= 26*26*26 {
+               base26String = []byte("xxx")
+       } else {
+               var firstByte, secondByte, thirdByte byte
+               thirdByte = byte((num % 26) + uint('a'))
+               num = num / 26
+               secondByte = byte((num % 26) + uint('a'))
+               num = num / 26
+               firstByte = byte((num % 26) + uint('a'))
+               num = num / 26
+               base26String = append(base26String, firstByte)
+               base26String = append(base26String, secondByte)
+               base26String = append(base26String, thirdByte)
+       }
+       return base26String

 }
 }