World games

I will consider for the purpose of philosophizing about space and time world games which have spatial relations through a world and temporal relations through gameplay of some kind. Of particular interest is the kinematics of units, which can move in certain patterns in the world. I will start with considering combinatorial game theory in particular. In combinatorics, spatial relations can be modeled by graphs and time can be modeled by partial orders. Conway's game of life can be considered a zero-player combinatorial game, the spatial relations are basically a king's graph where each position is related vertically, horizontally, and diagonally. Checkers has its own sort of graph, defined by the movements of units backwards and forwards.

Chess is a separate concept because of the different kinds of motions of its units. This makes one wonder what the space of the world of chess means. Perhaps the most sensible thing, in general is that the spatial relations are the union of the knight's graph and the queen's graph. This is a diameter two graph, which means that no matter what unit you are using there are places that cannot be reached. This means the chess space at least preserves some sense locality which wouldn't be there if its union graph was diameter one.

Then there are a variety of subgraphs of these graph that determine the kinematics of different units. The minor piece graphs the bishop graph, the knight's graph, and the bishop graphs are all perfect. The bishop graphs are defined for different square colors, and the knight's graph is also bipartite. The bishop graphs need to be defined for a subset of the total space, because they cannot change colors. The rook graph is diameter two, which is shared by the queen's graph since it is a supergraph, as well the graph of the whole space, etc. The king's graph is also defined for the king. All of these are different graphs that describe the movement of different units. There are many different variants of chess as well.

Generally the most popular of these games tend to be board games where the world is simply the board and units move around it. War games are another interesting case, where the games tend to have a world map. The world map can have rivers, roads, mountains, forests, plains, and other concepts analogous to these concepts of real world geography. Likewise, units tend to come in a variety of forms, which can be moved around in these world which is a concept of space. Analogous concepts occur in turn-based and real time strategy games, which have spatial maps that units can move around in. A separate concept, something like an action game, tends to have only one main unit but they still tend to have some spatial world they take place in.

Metaphysics of space and time

In the mathematical abstractions of space time I described that I think that space and time can be specified by the mathematical concepts of metric and order. These are mathematical abstractions of our physical concepts of space and time. When space and time are separated from their physical meaning in this way, then they take on a metaphysical meaning.

When considering different metaphysical possibilities, like the notion of a two dimensional flat world like space structure, a space with more dimensions, or something like an automata whose only notion of space is a graph and whose time is merely a discrete total order, quite obviously we are already divorcing the concepts of space and time from their actual physical meaning.

As space and time can be considered both metaphysically as well physically, I would would feel remiss without talking at least a little about the nature of physical space and time. There are two important sources of realizations about physical space and time (1) special relativity and (2) general relativity. Special relativity at least tells us that the type of order that we will use for time must be a partial order rather then a total order. Many of these models mentioned before like automata tend to have absolute time which makes them a bad match for reality. The partial order underlying spacetime, could even be the fundamental structure of the universe as described by causal sets.

Then there is the issue of general relativity and the whole issue of the curvature of spacetime. There are two aspects to the curvature of spacetime (1) the local curvature (2) the global curvature. The global curvature appears to be mostly flat, so the curvature is largely caused by local phenomena in spacetime. The curvature is very much localized, because the gravitational force follows the inverse square law. It is localized both in space and time because the curvature can change over time, which means there is not a constant geometry of the universe. This means that you cannot simply use a separate concept like a metric to describe space separate from time. Nonetheless, it is often useful to consider metrics as a separate concept as described earlier.

The nature of stacks

Well registers can be better understood using graph theory, stacks can be better understood as total orders. Stacks, lists, vectors, and other related structures can all be classified as totally ordered data structures. Their underlying structure is that of a total order, but they are represented differently so that certain operations work differently on them. Stacks are optimized to deal with the top of the stack by pushing and popping elements from the top. The operations of push and pop are reverse to one another. This makes for an ideal implementation of stacks.

The relationship between lists and stacks is the reason why Lisp is so amenable towards programming on stack machines. Lists, which are fundamental to Lisp, and stacks are both totally ordered data structures. As a result, in order to make a Lisp dialect that works on a stack machine, all that you have to do is map between these two isomorphic data structures. Ideally, a Lisp dialect can be created for a stack machine which exposes all the aspects of its functionality to the user.

Register allocation through graph coloring

Instruction set architectures can be either register based or stack based. In general, register based machines are more low level, and they have a certain set of registers that variables can be stored in, otherwise they will be spilled into memory. Register allocation is considerably important for at least two reasons, first of all because no significant high level programming system exposes registers to the programmer. Generally, a high level architecture is based upon stacks which abstract registers away, necessitating allocation. Secondly, even among register machines there is a great deal of differences between the register files they have, the number of registers, their size, and so on, so that register allocation is needed for portability. The ideal today is to have a portable high level stack machine architecture (like the JVM or the CLR) which has both properties.

The issue is really how to pass operands to functions. Registers place special conditions on how operands can be passed to functions, where as stacks do not. A register based system of operand passing makes it so that you have to constantly consider where things are being allocated. Lisp requires a high level abstraction of operand passing, which is why it has always been so effective on top of a stack machine architecture. Any stack machine architecture can be made immediately amenable to Lisp, by making push instructions into atomic forms, and making other instructions into functional combiners. Fortunately, the problem of register allocation has an effective solution.

In order to proceed with dealing with this problem, we will start with a set of variables and we will perform liveness analysis in order to form an interference graph. The problem of register allocation can therefore be reduced to a problem of graph coloring, which we can deal with effectively using our understanding of graph theory. A coloring of a graph in this context is the same thing as a partition of into independent sets. The independent sets are registers to which values can be allocated to without effecting the other variables. One special case is that of an SSA (like the LLVM) for which the interference graph is chordal. Chordal graphs are a familiar class of graphs with only polynomial time coloring, so that makes register allocation even more readily computable.

Since register allocation is a graph coloring problem necessary to program in any register machine, you generally shouldn't program in the assembly language of a register machine like X86 or ARM unless you are a compiler developer. The register allocator and instruction optimizer can produce assembly code for these architectures better then or at least as good any individual developer can. On the other hand, it is sometimes acceptable to program in a high level stack based assembly language, as the language is sufficiently high level to be easily dealt with. Then you could understand a program all the way down to its assembly.

Fundamentals of combinatorics

If any two types of structures can be considered to be the fundamentals of combinatorics it is graphs and orders. Other structures are constructed after these simpler ones, but these are two of the simplest and most fundamental structures. Orders such as lattices and graphs are widely used throughout combinatorics, which is why they are so fundamental.

It is worthwhile to consider the metric properties of graphs. Graphs aren't just another structure, they are a way of defining the distance relations between points. There are metric properties of graphs like eccentricity, center, radius, diameter, and so on. It is worth considering this, because metrics and orders are perhaps the most fundamental concepts in general. With all this about the central importance of graphs and orders said, it is worth considering that they are not completely separate subjects from one another. Orders and graphs can be formed from one another in the manner listed below.

Orders derived from graphs:
The most immediate order that can be derived from a graph is adjacency containment. This forms a preorder, in which two elements are related if the set of nodes they are adjacent are included in one another. For the class of trivially perfect graphs, this preorder fully determines the graph. For example, a cluster graph is equivalent to a symmetric preorder. Cotrivially perfect graphs are determined by their coadjacency containment. Otherwise, the preorder only provides partial information on the graph.

Graphs derived from orders:
The most immediate graph that can be formed from an order is the comparability graph. The complement of this is the cocomparability graph. Both the comparability graph and the cocomparability graph are instances of perfect graphs. The comparability graph is the most general graph that can be formed from a partial order, but it doesn't always suffice. Another graph that can be formed by a partial order, particularly a hereditary discrete partial order, is the covering graph determined by the comparability of the transitive reduction of the partial order. This is a subgraph of the comparability graph.

Mathematical abstractions of space, time, and kinematics

There is a question of what mathematical structures to use in order to represent space, time, and related concepts. It is well known that time can be represented as a partial order relating events that are caused by one another. Space on the other hand, can be represented in multiple different ways, but generally we need some concept of a metric to determine distances between points. Entities in a space can only most readily effect other entities that are most near to them, as determined by the distance relation.

One property of these abstractions of space and time is that they both have a topology associated with them, the metric topology and the order topology. There is a question as to rather or not space and time are discrete or continuous or not, this can be determined by the topology of these structures. In particular, a discrete space will have a discrete metric and discrete time will have a discrete order. Another issue is rather time is absolute or not. An absolute time will use a total order and a relativistic time will use a partial order. The overwhelming evidence for relativity favors a partial order for time. The theory of causal sets uses a discrete partial order to define spacetime, for example, but sometimes it might be useful to have a different abstraction of time, or to have a way of representing space, since geometry is clearly so fundamental.

• Space : metric
• Time : order

These are mathematical abstractions of space and time, and therefore they don't have to be used to model actual physical space, but rather, they can be used to model anything analogous to them. If space is discrete for example, it may be useful to define it simply by a connected graph, then the metric will be simply be the path length. For example, for a cellular automata like Conway's game of life, the space is the connected graph of the max degree eight neighborhood relation between squares and the time will be an absolute, or total, discrete ordering. For a simple game like checkers, the space could be the squares pieces move on, and the time could be a discrete total ordering, and so on. The space could also be a manifold of any sort, like a two dimensional manifold, assuming there is a two dimensional space, like flat world. Or one could imagine a manifold with many dimensions greater then are own, or with some extra structure to it. This gives us an idea as to how to model all the different possible universes and environments an agent can be embedded in or involved with.

Of course, space and time, cannot be considered completely separate concepts even though concepts like order and metric can be considered separately from one another. One reason that they are related to one another is kinematics, the study of motion, which connects the two together to form spacetime. If one accepts a process ontology, which says that everything is an event, then one could suppose that the meaning of space in a kinematic universe is to define the nature of motion events. It is helpful to examine the relation between them by determining rather the amount of spatial distance between events is greater then the temporal distance, to determine if they can be causally related. In particular, one can define the average speed by the spatial distance divided by the temporal distance as it is typically defined in kinematics. In a discrete universe, the average speed is simply the average amount of time units spent on discrete spatial jumps. With these concepts we can define the equivalent of light cones used in relativity to determine causality.

2018 year in review

In terms of mathematics, one thing that was studied this year was topology. Topologies are ordinarily defined as certain set systems, with a restricted intersection closed condition, which limits the neighbourhood of points. An Alexandrov topology, on the other hand, doesn't have this condition and it is simply equivalent to a preorder, and every point has a small neighbourhood set. A topology defined this way typically has an interior but not a closure operation, as a consequence of this fact, so it is a Comoore family. There is a complementary Moore family which does have a closure operation, but only an Alexandrov family of this sort has a closure and an interior, and as described already it is determined by its specialization preorder. All finite topologies are Alexandrov topologies, so at least in the finite case, topology doesn't tell us anything more then order theory.

Frechet topology trivializes the specialization preorder aspect of the topology. A Hausdorff space also introduces the axiom that separate points are distinguished by separate neighborhoods, which is generally a good thing as we want to deal with spaces in which points are separated in some sense. As a consequence, most of the time we want to deal with Hausdorff topologies. It happens that order topologies defined by the open rays of a total order are all Hausdorff topologies for example. All finite Frechet topologies, and all finite Hausdorff topologies as well are discrete, so a Hausdorff topology can tell us nothing about a finite structure. There are other order topologies that are discrete and all of them that are hereditary discrete can be embedded within the integers, as already mentioned. Order topology, however, describes a great deal of properties of other types of total orders, like scattered orders, dense orders, connected dense orders, etc.

The most interesting and important aspect of order theory is the study of boolean algebra and relatedly set theory. This study of set theory, is the foundation from which all of mathematics inevitably derives. It is interesting then that the theory of total orders, which are so different from boolean algebras, produces an interesting type of theory on its own. A large part of the reason that this is the case, is due to the study of order topology. Topology provides an organizing principle for the study of total orders. This was demonstrated by my paper on the subject, which unlike its predecessors dealing with total orders, used topology as its foundation. It is worth bearing in mind that order topological principles can be applied to partial orders in general, by considering the total suborders of a partial order. For example, a partial order is hereditary discrete if all its chains are, or likewise, it is scattered if all of its chains are. This means topological principles can be used to better understand all of order theory in general.

Even so, a large part of the reason for studying topology is to better understand metric geometry. Geometry plays an absolutely fundamental role in physics and therefore every field of science, so it is worth pursuing it. It is generally agreed that real space is something like a manifold, and can be modeled as such. Every metric space has a topology of open sets associated with it, which as it happens is also a Hausdorff topology. I demonstrated that if the order topology of the set of distances is related to the topology of the metric space, in that it partially determines what types of topologies can be formed. This helped to demonstrate the relation between order and metric, which are two structures that share the property of having a topology.

In terms of computing, I studied the theory of stack machines. In particular, I studied the Java virtual machine (JVM), its specification, how to write programs in Java bytecode, and I made a compiler for a language for the platform. I read parts of the Java virtual machine specification many times. I also studied the CLR and programmed in CIL, and I intend to do so some more if I have the time. These are the two virtual stack machines which seem to be most used. There are some Common Lisp implementations which also have virtual machine stack machines used in their implementations, which was interesting to study as well. I intend to use many Java libraries in my code, regardless of which language I use, with the understanding of how they are dealt with by the understanding of the virtual machine.

One of the great things about stack machines like the JVM and the CLR is that they, being stack machines, can be easily made to correspond to Lisp because lists and stacks can both be made to correspond to one another since they are both total orders. It doesn't hurt that there is also a vast amount of libraries available on this platforms either, including libraries dealing with things like machine learning, and so on. These platforms are a great thing for language developers as well, who have a high level platform to deal with, and who don't need to deal with register allocation, much less deal with problems of producing code for particular platforms. The LLVM is a low level register based RISC machine, but at least it does register allocation so you don't have to deal with concrete register files for different platforms, things like that should be dealt with by the great libraries.

I like to think about programming from the perspective of a compiler writer, especially now, as I have studied the theory of compilers to a greater extent then ever before. Its good to know all the steps the compiler is doing, like parsing, semantic analysis, code generation, etc and what it is producing (like JVM or CLR bytecode) and that you are not programming with some black box. Certainly it is good to know how to be able to use all the features of your machine, and to be better able to deal with problems of performance, so common when you deal with projects that get really large over the years. So compiler development is my great organizing principle of programming.

A recent thought I had on the theory of parsers, which I thought might be interesting is to when given a sequence, output a set system of indices of that sequence. This set system, partially ordered by inclusion, could even characterize the parse tree of the sequence, if it formed an upper tree under inclusion. This could work for both text files and perhaps even binary files in general. Binary file formats will have their own way of dealing with them with an appropriate parser, which will determine which parts of the binary file are important, so we have more then just some opaque stream of numbers. This would use set theory necessarily. In terms of code generation I have been thinking about building an ontology of instructions, using pattern matching on instruction streams, and so on to see how instruction sequences are isomorphic to certain programs that compile to them.