chapter-1-experiments/ch1-breeding-numbers.go

// (c) 2020 Aaron Taylor <ataylor at subgeniuskitty dot com>
// See LICENSE.txt file for copyright and license details.

package main

import (
        "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() {
        // 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
}