sw.py

#!/usr/bin/env nix-shell
#! nix-shell -i python -p python27Packages.attrs python27Packages.enum34

# Let us have *timelines*, which are totally ordered sequences of observations
# of events tagged with (monotonic) timestamps. The possible states of
# observation are *aspects* of time from the event's point of view:
# {pu'o}: The event has not yet happened
# {ba'o}: The event has happened
# {ca'o}: The event is happening

# We then insist that timelines have only some legal forms; a timeline must
# always have monotonic timestamps, and also must have a shape like this:
#          ,~~~~~~~~~~~~~~~~~~~~~~.
# .   .   /   .  ^.   .   .   .   .\  .   .   .
# _______/^      |                 ^\__________
# ^       |      |                 |        ^
# |       |      |                 |        |
# pu'o   co'a    ca'o             mo'u     ba'o

# As a result, there are restrictions on the legal ordering of states. For
# example, a {ba'o} cannot precede a {pu'o}. Nonetheless, we can define a
# partial binary gluing or union operator on timelines which interleaves
# observations according to their timestamps. We can also define the
# intersection of two timelines as only the observations which they have in
# common.

# What's the difference between {co'u} and {mo'u}? {mo'u} is the natural end
# of an event, while {co'u} is the actual end of the event. For example, a
# natural death is {mo'u} while a murder or untimely end is {co'u}.

# Let us say that a *story* is a set of tagged timelines associating some
# event name to the timeline of that event. We can take the union and
# intersection of stories in the obvious way. Then:

# (1) Any set of stories forms a topological space, with unions of subsets as
# its open sets.
# (2) A story maps to its timelines.
# (3) Any union of stories maps to the union of those stories' timelines, if
# such a union exists.
# (4) Timelines form a category with the obvious identity morphism. There is a
# morphism from any timeline U to any other timeline V iff V can be glued with
# some other timeline X to yield U; in other words, U -> V takes a timeline to
# one of its "subset" timelines.
# (Presheaf) Then for any set of stories S, we can assign a presheaf F of
# timelines on stories.
# (5) Assume that we select S s.t. for any two stories in S, their union
# exists according to (3). In practice, we aim to detect violations of this
# property!
# (6) Furthermore, the gluing property holds. XXX actually prove it.
# (Sheaf) Then F is a sheaf of timelines on stories.

# Not yet considered:
# * Relativity and relativistic coordinates, which I suspect are special cases
#   of establishing a metric space on events
# * CTCs or other non-trivial topologies in timelines

from __future__ import division

import attr
from enum import Enum

class Aspect(Enum):
    puho, coha, caho, cohu, mohu, baho = range(6)

implicit = object()

# Valid left-to-right transitions.
transitions = {
    Aspect.puho: set([Aspect.puho, Aspect.coha, Aspect.caho, Aspect.cohu,
                      Aspect.mohu, Aspect.baho]),
    Aspect.coha: set([Aspect.caho, Aspect.cohu, Aspect.mohu, Aspect.baho]),
    Aspect.caho: set([Aspect.caho, Aspect.cohu, Aspect.mohu, Aspect.baho]),
    Aspect.cohu: set([Aspect.baho]),
    Aspect.mohu: set([Aspect.baho]),
    Aspect.baho: set([Aspect.baho]),
}

class GlueError(Exception): pass

@attr.s
class TimelinePrinter(object):
    width = attr.ib()
    start = attr.ib()
    stop = attr.ib()

    def _prettyIndex(self, point):
        rv = (point - self.start) * self.width / (self.stop - self.start)
        return int(max(0, min(rv, self.width - 1)))

    def _checkOverlap(self, i):
        if self.dots[i] == '*':
            return True
        else:
            self.dots[i] = '*'
            return False

    def addPoint(self, point, char):
        point = self._prettyIndex(point)
        if self._checkOverlap(point):
            self.line[point] = '!'
        else:
            self.line[point] = char

    def addEdge(self, points, fillChar):
        for x, y in zip(points, points[1:]):
            x = self._prettyIndex(x)
            y = self._prettyIndex(y)
            self.line[x:y] = fillChar * (y - x)
            self.dots[x] = self.dots[y] = '*'

@attr.s
class PrettyPrinter(object):
    width = attr.ib()
    start = attr.ib()
    stop = attr.ib()

    def add(self, timeline):
        tp = TimelinePrinter(self.width, self.start, self.stop)
        tp.line = ['?'] * self.width
        tp.dots = [' '] * self.width
        timeline.pretty(tp)
        return tp.line, tp.dots

def gluePoint(left, right):
    if left is implicit:
        return right
    elif right is implicit:
        return left
    elif left == right:
        return left
    else:
        raise GlueError("Couldn't glue points %r and %r" % (left, right))

def checkEdge(l, point, r):
    if l and l[-1] >= point:
        raise GlueError("Couldn't glue left edge")
    if r and point >= r[0]:
        raise GlueError("Couldn't glue right edge")

@attr.s
class Timeline(object):
    purci = attr.ib()
    cfari = attr.ib()
    cabna = attr.ib()
    sisti = attr.ib()
    balvi = attr.ib()

    @classmethod
    def fromAspects(cls, aspects):
        currentStamp = float("-inf")
        currentState = Aspect.puho
        purci = []
        cfari = implicit
        cabna = []
        sisti = implicit
        balvi = []
        for stamp, state in aspects:
            if stamp <= currentStamp:
                raise GlueError("Non-monotonic")
            if state not in transitions[currentState]:
                raise GlueError("Invalid transition")

            if state is Aspect.puho:
                purci.append(stamp)
            elif state is Aspect.coha:
                cfari = stamp
            elif state is Aspect.caho:
                cabna.append(stamp)
            elif state in (Aspect.cohu, Aspect.mohu):
                sisti = stamp, state
            elif state is Aspect.baho:
                balvi.append(stamp)
            else:
                raise GlueError("Invalid state")

            currentStamp = stamp
            currentState = state

        self = cls(purci, cfari, cabna, sisti, balvi)
        return self

    def pretty(self, pp):
        purci = [float("-inf")] + self.purci
        cabna = self.cabna
        balvi = self.balvi + [float("inf")]

        pp.addEdge(purci, '_')
        pp.addEdge(cabna, '~')
        pp.addEdge(balvi, '_')

        if self.cfari is not implicit:
            pp.addPoint(self.cfari, ',')
        if self.sisti is not implicit:
            point, aspect = self.sisti
            pp.addPoint(point, 'x' if aspect is Aspect.cohu else '.')

    def glue(self, other):
        cfari = gluePoint(self.cfari, other.cfari)
        sisti = gluePoint(self.sisti, other.sisti)

        purci = sorted(set(self.purci + other.purci))
        cabna = sorted(set(self.cabna + other.cabna))
        balvi = sorted(set(self.balvi + other.balvi))

        if cfari is not implicit:
            checkEdge(purci, cfari, cabna)
        if sisti is not implicit:
            checkEdge(cabna, sisti[0], balvi)

        return Timeline(purci, cfari, cabna, sisti, balvi)

    def earliest(self):
        if self.purci:
            return self.purci[0]
        if self.cfari is not implicit:
            return self.cfari
        if self.cabna:
            return self.cabna[0]
        if self.sisti is not implicit:
            return self.sisti[0]
        return self.balvi[0]

    def latest(self):
        if self.balvi:
            return self.balvi[-1]
        if self.sisti is not implicit:
            return self.sisti[0]
        if self.cabna:
            return self.cabna[-1]
        if self.cfari is not implicit:
            return self.cfari
        return self.purci[-1]

@attr.s
class Story(object):
    timelines = attr.ib()

    def glue(self, other):
        ts = self.timelines.copy()
        for k, t in other.timelines.iteritems():
            if k in ts:
                ts[k] = ts[k].glue(t)
            else:
                ts[k] = t
        return Story(ts)

    def pretty(self):
        width = 72
        # Slow but whatever.
        start = float("inf")
        stop = float("-inf")
        just = 0
        for k, tl in self.timelines.iteritems():
            start = min(start, tl.earliest())
            stop = max(stop, tl.latest())
            just = max(just, len(k))
        pp = PrettyPrinter(width, start, stop)
        for k in sorted(self.timelines):
            tl = self.timelines[k]
            line, dots = pp.add(tl)
            print k.ljust(just), ''.join(line)
            print ''.ljust(just), ''.join(dots)

def sectionsOf(sheaf):
    if not sheaf: return []

    rv = []
    s = None
    for story in sheaf:
        if s is None:
            s = story
        else:
            try:
                s = s.glue(story)
            except GlueError as ge:
                print "Couldn't glue", ge
                rv.append(s)
                s = story
    rv.append(s)
    return rv

def globalSectionOf(sheaf):
    s = sheaf[0]
    for story in sheaf[1:]:
        s = s.glue(story)
    return s

f = Timeline.fromAspects

g = [
    # The Phantom Menace
    Story({
        "anakin-life": f([[-32, Aspect.caho]]),
        "obiWan-life": f([[-32, Aspect.caho]]),
    }),
    # Attack of the Clones
    Story({
        "anakin-life": f([[-22, Aspect.caho]]),
        "obiWan-life": f([[-22, Aspect.caho]]),
    }),
    # Revenge of the Sith
    Story({
        "anakin-life": f([[-19, Aspect.caho]]),
        "leia-life": f([[-19, Aspect.coha]]),
        "luke-life": f([[-19, Aspect.coha]]),
        "obiWan-life": f([[-19, Aspect.caho]]),
    }),
    # A New Hope
    Story({
        "anakin-life": f([[0, Aspect.caho]]),
        "leia-life": f([[0, Aspect.caho]]),
        "luke-jediTraining": f([[0, Aspect.coha]]),
        "luke-life": f([[0, Aspect.caho]]),
        "obiWan-life": f([[0, Aspect.cohu]]),
    }),
    # The Empire Strikes Back
    Story({
        "anakin-life": f([[3, Aspect.caho]]),
        "leia-life": f([[3, Aspect.caho]]),
        "luke-jediTraining": f([[3, Aspect.caho]]),
        "luke-life": f([[3, Aspect.caho]]),
    }),
    # Return of the Jedi
    Story({
        "anakin-life": f([[4, Aspect.cohu]]),
        "leia-life": f([[4, Aspect.caho]]),
        "luke-jediTraining": f([[4, Aspect.mohu]]),
        "luke-life": f([[4, Aspect.caho]]),
        "obiWan-life": f([[4, Aspect.baho]]),
    }),
]

print "Global section of G-Canon:"
globalSectionOf(g).pretty()