The need for high-level architectures

Most instruction sets available in stock hardware are register-based, which means that programmers dealing with them need to manually perform register allocation. This manual register allocation is generally not as good as an optimizing compiler anyways, which performs liveness analysis, graph coloring, etc to appropriately allocate variables in registers. Stack machines on the other hand, avoid this issue, and provide programmers with an easy to use high level instruction set.

Stacks are a totally ordered data structure. On the other hand, the Lisp programming language, which was named for List processing, focuses on lists which are a also a totally ordered data structure. Lists and stacks are two types of representations of a totally ordered data structure. As a consequence, stack machines belong together with a Lisp dialect which corresponds to their instruction set. A Lisp compiler for a stack machine can be constructed with ease.

Well the majority of instruction sets available in stock hardware are register based, we can at least get high-level stack based architectures with virtual machines. In particular, there is the JVM and the CLR which are both stack based. Towards this end, I created Lisp flavoured Java, which is a Lisp dialect which corresponds directly to the Java virtual machine bytecode. Atomic forms in the language correspond to the push instructions in the virtual machine. Combiners correspond to atomic instruction classes or to macros, which generate simpler forms. This demonstrates that even a stack based machine like the JVM can be made isomorphic to a Lisp dialect.

The Lisp programming language championed the notion of homoiconicity, which means that code is written as data. This considerably simplifies the parsing phase of the complier. High level stack-based architectures, like the JVM or the CLR, are perhaps equally important as they simplify code generation as well. A Lisp dialect designed for a high level stack based architecture, can be compiled seamlessly.

Lisp flavoured java implementation

The four previous posts described the Lisp flavoured java programming language, which is a thin wrapper over the Java virtual machine. This language was designed so that it would hide nothing of the virtual machine's internals from the programmer, and so that Lisp forms would translate directly to bytecode. The syntax of the language is Extensible Data Notation, which is determined by the Clojure reader. Semantic analysis is performed by the resolver, and compilation is done with the help of the ASM library. This is an early release, so some of the features of this language ould be improved in the future.

https://gitlab.com/jhuni/lisp-flavoured-java

Lisp flavored java defining classes

Classes can be defined in Lisp flavored java using the full extent of the different features of the Java virtual machine, like access flags, types, and so on. Although Clojure does provide a genclass interface it doesn't deal with access flags and all the functionality of the java virtual machine, because the language wasn't designed to be Java with parenthesis like this one. Here is an example of a Hello World class, which is one of the simplest things you will see programmed in Java. One notable aspect of this program is that it uses . in order to invoke an initialization method, which is something that probably hasn't been seen before quite like this. This can be used to initialize this or super with the appropriate arguments and it will be produce the appropriate invokespecial instruction.

(class public HelloWorld
  (method public V <init> []
    (.<init> super))

  (method public static V main [(arr java.lang.String) args] 
    (.println java.lang.System/out "Hello world"))

Well is the one special type of instance method whose invokation . may not be familiar the on the other hand the class initializer is a static method used to initialize the class so it can be used to deal with certain aspects of programming in the Java virtual machine. One of the reasons that this syntax is possible is that Lisps in general including Clojure allow the tags to be used in symbol names. Note that the message doesn't need to be clarified because static variables and static methods are imported throughout the class by default just like Java.

(class public Message
  (field public static java.lang.String message)
  (method public static <clinit> [] 
    (setf message "Hello World"))
  (method public V <init> []
    (.<init> super)))

The importation of static methods allows for you to implement static recursive functions that can call themselves. The most obvious example that comes to mind is the factorial function so that will be demonstrated here. Its also worth mentioning that type inference is supported in the exact same manner as in Java, which is that it is supported for local variables. Type inference cannot be supported for methods and their return values, because it is necessary for us to know at compile time what the signatures of the methods of the class are in order to do self reflection.

(class public FactorialHelper
  (.method public V <init> []
    (.<init> super))
  (method public static I factorialIterative [I n]
    (var rval 1)
    (var i 1)
    (while (<= i n)
      (setf rval (* rval i)) 
      (incf i 1))
    rval)
  (method public static I factorialRecursive [I n] 
    (if (= n 0)
      1
      (* n (factorialRecursive (- n 1))))))

Here is one more example that better demonstrates some details like dealing with constructors, and using this in order to deal with fields, methods, and things like that on it.

(class public Point
  (field public I x)
  (field public I y)

  (method public V <init> [I x I y] 
    (.<init> super)
    (setf (.-x this) x)
    (setf (.-y this) y))

  (method public I getX []
    (.-x this))

  (method public I getY []
    (.-y this))

  (method public V setX [I x]
    (setf (.-x this) x))

  (method public V setY [I y]
    (setf (.-y this) y)))

Hopefully these few examples demonstrated some of the functionality of the Lisp flavoured java language system, which is directly translatable to Java bytecode with appropriate instructions, access flags, and so on. This is now a pretty full description of the capabilities of this language like its data operations, modification procedures, control flow, and class syntax. This language can be considered to be essentially Java with parenthesis, which makes it ideal for programming on the Java virtual machine.

Lisp flavoured java control flow

Unconditional branches:
In order to implement a programming language isomorphic to the JVM instruction set, it is necessary to support goto statements, because that is how control flow is dealt with on a low level. Most high level languages on the JVM don't support this. To implement any language with branches, its good to be able to use symbols to define the branch targets.

(tag label)
(go label)

This is a trivial example, so it is not hard to see how this corresponds to bytecode.

label:
goto label

This syntax is mostly reminiscent of Common Lisp, much like the syntax for modification procedures except you can declare tags anywhere rather then in just a body. Common Lisp is influenced by the Lisp machine lisp so it is clearly best suited for low level programming.

Generalized conditionals:
The java virtual machine instruction set has several operations that deal with conditional branches. These require on certain conditions placed on operands on the stack, so they can be generalized by using appropriate logical operators. There are two types of logical operators that deal with single arguments operators that classify the sign of an argument and operators that determine rather or not a value is null or not. Then there are a variety of comparison operators. With the operations that determine sign it may not be obvious the to the Java programmer that is their actual purpose.

(isnonnegative num)

An operation like ispositive, isnegative, isnonnegative, isnonpositive, iszero, or isnotzero produces the correspond conditional branch instruction then as you would expect.

iload_0
ifge then
iconst_0
goto end_conditional
then:
iconst_1
end_conditional:

The builtin comparison operations which are limited to integers can be generalized with the appropriate comparison instructions for you.

(<= num1 num2)

The appropriate bytecode is then produced from this logical operation.

iload_0
iload_1
if_icmple then
iconst_0
goto end_conditional
then:
iconst_1
end_conditional:

If the values are compared are longs, then we can get the appropriate value with the proper comparison followed by a test on it. To do a conditional branch you can simply then use if with an appropriate conditional and it will generate the proper bytecode for you.

(if (<= num1 num2) (go label))

The presence of the if statement around the branch statement tells the compiler that you want to a conditional branch, so it can generate the proper bytecode for you, without increasing the complexity of the bytecode. Perhaps a different syntax could be created for this, but this works.

iload_0
iload_1
if_icmple label

This makes the instruction a bit more functional, which is a positive development, but it doesn't hide any functionality from the user or abstract anything anyway that you could use yourself in your programs.

Switches:
Lookupswitches can be dealt with by using the extend prefix notation as expected. The switch is passed as the first argument to the combiner followed by the operand to be pushed onto the stack.

(lookupswitch 
    (10 label1
     20 label2
     30 label3
    :else dftl)
    num)        

This operation could be dealt with instead by a case statement, but the purpose of this language is to hide nothing, and no operation in the instruction set from the programmer. This produces a complex instruction which looks something like this.

iload_0
lookupswitch 
 10 : label1
 20 : label2
 30 : label3
 default : dftl

As can be clearly seen here, the switch instruction still corresponds to the bytecode generated. Table switches can be automatically recognized and generated for you if you use an interval of keys or they can programmed directly.

Method calls:
The syntax to support method calls is not that interesting, Clojure already has a syntax that works well enough so there is no need to change it. The only issue is that the implementation will need to do a bit of reflection to determine the right kind of instruction to use, but once that is done the method call is translated directly to a sequence of instructions pushing values onto the stack followed by the correct invoke instruction.

(java.lang.Math/max 0 10)
(.charAt "string" 0)

The following produced assembly code demonstrates how these function calls correspond directly to invoke instructions on the java virtual machine.

iconst_0
bipush 10
invokestatic java.lang.Math/max(II)I
ldc "string"
iconst_0
invokevirtual java.lang.String/charAt(Ljava/lang/String;I)C

The benefit of using this notation is that this follows the same pattern of all the combiners defined so far, values are pushed onto the stack one by one and then the instruction is determined by the prefix. As mentioned previously, high level programmers might not realize that when programming Java the instance a method is being applied on is actually an operand pushed onto the stack.

Lisp flavoured java modification procedures

The first part of this process of abstracting the Java virtual machine dealt mainly with the construction of expressions from atoms and functions, and less with the aspect of modifying storage locations. This lead to a minimal abstraction of Java bytecode, however, I want to create not only a minimal abstraction but an elegant one as well. Towards that it is useful to introduce generalized variables. In the Java virtual machine there are four types of things that can be considered to be generalized variables: local variables, class variables, instance variables, and array index variables. These are displayed below. By abstracting these different types of variables away, we can modify any of them using a single function and then the compiler can produce the appropriate function associated with them. The Lisp way of doing this is to have a function like setf which modifies variables.

(type I x)
(setf x 10)
(type D y)
(setf y 1.0)

The appropriate local variable modification instructions are introduced by the compiler corresponding to the form of the variable being modified.

bipush 10
istore_0
dconst_1
dstore_1

This is how you might deal with modifying a static variable of a class:

(setf MainClass/name 0)

This will be compiled to a putstatic instruction with the appropriate type:

iconst_0
putstatic MainClass.name I

When dealing with compound variables a special form can be placed in as the first argument to the setf rather then an atom. The form appears exactly as an access to the variable would appear.

(type (arr I) coll)
(setf (aload coll 0) 10)
(setf (aload coll 1) 20)

These two function calls are expanded into two different iastore instructions. The appropriate instruction in this case is determined by the element type component of the array type of the variable being referenced. The ordering of the operations on the stack produced by the modification procedure is preserved, because the lvalues in the Java virtual machine instruction set always come first. This means this is still a simple abstraction of the Java virtual machine instruction set which corresponds directly to its bytecode.

aload_0
iconst_0
bipush 10
iastore
aload_0
iconst_1
bipush 20
iastore

The other type of compound variable, the instance variable can be dealt with as you would expect.

(type java.awt.Point p)
(setf (.-x p) 10)
(setf (.-y p) 20)

The type of the field being modified is determined at compile time by reflection.

aload_0
bipush 10
putfield java/awt/Point.x I
aload_0
bipush 20
putfield java/awt/Point.y I

Well all of these different uses of the assignment procedure have been interesting, the Java virtual machine does support one other type of modification procedure that deals with variables and that is the iinc procedure. The iinc procedure only deals with integer valued local variables though, so I believe it is worthwhile to abstract it away with a procedure like incf. This incf function can then be applied to any of the different types of variables.

(type I x)
(incf x 1)
(type (arr I) coll) 
(incf (aload coll 0) 1)

When the variable being dealt with by incf is an integer then it will produce the appropriate iinc instruction in order to provide you with more compact byte code. Otherwise, it will be necessary to get the value of the variable being addressed, push the amount it is to be added by onto the stack, and then add them in order to get what the value is going to be set to.

iinc 0 1
aload_1
iconst_0
aload_1
iconst_0
iaload
iconst_1
iadd
iastore

These two types of instructions will allow you to produce any of the modification instructions available to the Java virtual machine in an effective and generalized manner. We can now see how there are two different types of data operations available in the Java virtual machine: functions that deal with modifying values on the stack, and modification procedures that assign values to variables. Together these two types of instructions already described here define all the data operations of the Java virtual machine. The only instructions that have not been dealt with yet are the control flow instructions which will be dealt with in a later post.

Lisp flavoured java

The problem of how to make a thin layer over the Java virtual machine instruction set is addressed here. Lisp programs are built up two components: atomic expressions and compound forms. As the Java virtual machine is a stack machine, the thin layer over it will be constructed by making it so that atomic expressions correspond to push instructions and compound forms correspond to everything else. In this way, the Java virtual machine can be made isomorphic to a Lisp dialect. The structure of the Java virtual machine described in the JVM specification further describes the instruction set of the JVM and how it handles types with prefixes with type prefixes like Top which describes how instructions are provided as combiners.

Atomic expressions:
The Atomic expressions in the Java virtual machine come in two forms: constants and variables. The atomic expressions in Lisp correspond directly to the Atomic instructions in the Java virtual machine. In this way, the Lisp flavored java is orthogonal to the Java virtual machine's high level instruction set. Here are some examples of constant expressions:

10
2.2
"foo"

Integer like expressions are read as integers rather then as longs by default, just like the Java programming language, though unlike Clojure which assumes you are using a long by default. The use of integers by default is necessary for any kind of low level programming on the Java virtual machine, as ints are used for array access, array length, etc and they have the most specialized instructions associated with them, so especially for performance it is necessary to use integers by default. Float like expressions are read as doubles just like Java again, as there is no need to change that standard. So literals are like what you would expect from Java. The atomic expressions are directly converted one to one to push instructions and the appropriate push instructions that save the most space are determined for you.

bipush 10
ldc2_w 2.2
ldc "foo"

Variables are different from constants in that they can have a type associated with them. Consequently, type declarations can be associated with variables. One of the first thing one notices when writing JVM bytecode by hand, is that it is hard to keep track of local variables without the use of names, so certainly is nice to be able to use symbols instead that refer to local variables.

(type I a)
(type J b)
a
b

The appropriate push instruction is determined for you based upon the type of the local variable referred to be the symbolic expression. The atomic expression then corresponds one to one with a push instruction in the machine code.

iload_0
lload_1

The other type of variables besides local variables is class variables. The class variables can be designated using a slash in a symbol.

java.lang.Math/PI
java.lang.System/out

The class variables are then converted to get static expressions. Since variables can have types, class variables can have types as well. The types of class variables is determined by reflection rather then by type declarations.

getstatic java/lang/Math.PI D
getstatic java/lang/System.out Ljava/io/PrintStream;

This demonstrates how different atomic expressions like constants, local variables, and class variables in the language correspond directly to push instructions in the Java virtual machine, making the language a thin layer over the Java instruction set.

Compound forms:
Compound forms are constructed by combining atomic expressions with a combiner. The definition of combiners is determined by their types as described by the Java virtual machine specification. The appropriate typed version of an instruction is then determined at compile time. Consider the operation Tneg which can come in the forms ineg and lneg. The Tneg combiner is compiled to the appropriate instruction based upon the type of the argument passed to it. The standard means of defining these typed combiners is to simply remove the T prefix in front of it. So Tneg is simply neg.

(neg 1)

The neg operation is then compiled to its corresponding combiner instruction well the atomic expression one is compiled to its appropriate push instruction and these are then added to the machine code.

iconst_1
ineg

The same is true for the Trem operation which is simply reduced to rem when it appears in a compound form.

(rem 10 2)

When an operation like rem is applied to multiple arguments the order the arguments appear in is preserved by the stack machine. In many ways the nature of Lisp as a means of constructing programs from ordered lists is especially suited for programming with a stack machine.

bipush 10
iconst_2
irem

In order to make the programming easier, for the other arithmetic operations + corresponds to Tadd, * corresponds to Tmul, - corresponds to Tsub, and / corresponds to Tdiv. These are merely aliases for these fundamentally typed operations.

(type I x)
(/ (* x (+ x 1)) 2)

These expressions can be nested, and then their arguments will be pushed onto the stack in order and then evaluated accordingly. In this way, we can see how this Lisp dialect directly corresponds to the JVM instruction set.

iload_0
iload_0
iconst_1
iadd
imul
iconst_2
idiv

Logical operations like shl,shr,ushr,and,or,xor are similarly provided directly to the programmer accordingly and they are compiled to their typed versions. Casts can be expressed as T2i, T2l, T2f, T2d, T2s, T2c, and T2b. These convert an operand of some type to some other type. The ordinary standard of expressing these operands by removing the type in the front would leave a combiner with a name starting with a letter, so I decide that these can aliased by their cast names int is T2i, long is T2l, float is T2f, double is T2d, short is T2s, char is T2c, and byte is T2b. This basically describes how the data transformations in the JVM can be converted directly to a Lisp like syntax in an effective manner. The next detail is to determine how to deal with arrays. Elements of arrays can be loaded with aload as you would expect.

(type I i)
(type (arr I) coll)
(+ (aload coll i) (aload coll (+ i 1)))

This expression and all of its components are then converted directly to the following bytecode:

aload_0
iload_1
iaload
aload_0
iload_1
iconst_1
iadd
iaload
iadd

Arraylength is an interesting case unlike the other ones described so far as it doesn't have any special type information associated with it, because it simply applies to arrays every time.

(type (arr I) coll)
(arraylength coll)

This is one is so simple that you hardly even need a compiler to deal with it, it can be converted directly to its associated bytecode.

aload_0
arraylength

You can do a getfield operation much like you would in Clojure by specifying the field name in the combiner.

(type java.awt.Point point)
(.-x point)

The owner of the field is determined by the argument passed to the field accessor, and then the type of the field is determined by reflection which then is used to output the appropriate getfield argument.

aload_0
getfield java/awt/Point.x I

So all of the atomic expressions and combiners so far have directly correspond to instructions in the Java virtual machine instruction set with their operands pushed onto the stack. You can make instructions that have instruction parameters by using extended prefix notation. Extended prefix notation means that the instruction parameters are passed in the front next to the combiner before the operands to be pushed onto the stack are specified.

(type java.lang.Object obj)
(newarray I 9)
(multianewarray I 9 9)
(instanceof java.lang.String obj)

These operations like new, newarray, multianewarray, instanceof, and checkcast correspond directly to their corresponding instructions except they must have some instruction parameter passed to it in the front.

bipush 9
newarray int
bipush 9
bipush 9
multianewarray [[I 2
aload_0
instanceof java/lang/String

This describes how all the different combiners and atomic expressions can be made to correspond to machine instructions, except in the case in which their is an extended prefix notation which means that the programmer will have to pass an argument in the front to define the instruction before the following stack operands. This deals with most of the data operations of the Java virtual machine. Miscellaneous other no operand instructions like nop, pop, athrow, monitorenter, and monitorexit simply correspond directly to their machine instructions. Pop is simply a function which takes its argument pushes it onto the stack and then returns nothing. Variable modification and control flow will be dealt with later.

Stack compatability

Given a high level programming language abstraction of stack machine instruction set, stack compatibility means that the operations passed to functions and the values they return correspond to values directly placed on top of the stack in the same order as they were put in. In the JVM user defined functions can only return a single value so stack compatibility and the principle of consistency dictate that multiple valued functions should not be used by the programmer, so operations like dup, dup2, dup_x1, dup2_x1, dup_x2, and dup2_x2 should be handled by the compiler and not the programmer. Since these multivalued functions are the stack manipulation operations, this means that stack manipulation should be left to the compiler and there should only be a higher level expression based language, whose compiler automatically handles stack maintenance. In this way, operations will all be consistent with user defined methods.

To make things consistent, the this argument passed to a function through the stack can be a parameter rather then a special keyword. This detail is forgotten by some high level programmers that use Java without using the bytecode. A form of this sort (.method this a b c) actually maintains stack consistency because this is passed onto the stack first, so it maintains stack compatibility with the bytecode produced. Stack compatibility will be make compilation between the high level language and the underlying stack machine rather seamless, allowing the programmer full access to underlying system.

Understanding the java virtual machine instruction set

It is well known that Lisp programs consist of two components: atoms and compound forms. Compound forms start with a combiner and they are followed by a collection of other forms which can be atoms or other compound forms. Using combiners and starting with atoms we can form any Lisp program. This concept of program construction can be related to programming in a stack machine. Atoms are things that are pushed directly on to the stack, and combiners are the instructions that manipulate stack operands.

The atomic expressions in the JVM can only mean the constants and variables that can be loaded onto the stack directly using certain operations. Constants can be pushed onto the stack using either special operations designed to save space or by a reference to the constant pool assigned to the ldc instruction. Variables come in two forms: local variables and class variables. Local variables are accessed by some integer as well as a type, well class variables are accessed by getstatic. As any programmer would want to assign names to variables, they can be represented in practice using symbols. In order to distinguish between local variables and class variables there can be a delimiter like '/' in Clojure or ':' in Kawa Scheme. In any case in the end we have two types of atoms: constants and symbolic variables.

All other things can be done using compound forms with appropriate combiners which correspond to instructions. All the arguments to a compound form are pushed onto the stack followed by the combiner. A uniquely valued combiner consumes its arguments and then either puts something onto the stack or it returns nothing. There are arithmetic, logic, cast, and comparison functions for dealing with primitive values, the load and access functions for dealing with arrays, allocation instructions, type checkers, and field access instructions. All of these are essentially functions that directly operate on values on the stack. The nop and pop instructions consume their instructions but don't do anything. So in terms of data operations, the main thing is modification procedures like store, astore, putfield, and putstatic which operate on place forms of various sorts.

The control flow instructions come in two basic forms : conditional branches and switches. There are a wide variety of different control flow instructions that are variants of these two forms. Switches are different because they involve branching to a wide variety of different points. Other procedures include return, throw, monitorenter, and monitorexit. All of the instructions mentioned so far take the basic form of an operation that takes its arguments on the stack and then returns some value or nothing at all. Methods, which are user defined combiners, take the same form as this. As a result, many of these instructions can in theory be defined as methods. For example, one can define most arithmetic, logic, comparison, and cast instructions as methods instead of as instructions and it will have the same effect on the stack. The only exception to this is local variables and control flow instructions which deal with properties inaccessible to invoked methods.

Methods come in different forms including instance methods and static methods. The difference between the two doesn't always matter that much because the JVM can use devirtualization to optimize instance methods. All Clojure functions are defined as instance methods on function objects, but this is okay because the JVM is very good at devirtualization especially as clojure functions are final. Invokespecial deals with constructors and other special cases. The main point then is that there are methods that can be accessed by pushing their operands onto the stack and then returning either some value or nothing in the case of a void method. So since the virtual machine directly supports uniquely valued functions like these they should be the basis of all compound forms.

Then finally there are instructions that return multiple values. These operations like dup, dup2, dup_x1, dup2_x1, dup_x2, and dup2_x2 don't do anything special, but rather they provide a more efficient alternative to pushing things onto the stack more then once. As these multi valued instructions do not follow the calling convention defined for methods, which is that they either push a value onto the stack or nothing at all, they should be handled entirely by the compiler. The main function of the compiler then, is to find ways to insert instructions like dup into compiled forms to make them more efficient, as these operations like dup should not be handled by the user. Instead, the stack should certainly be abstracted away by an expression based system like Lisp.

So in conclusion there are three types of operations in the JVM instruction set: atomic values which are push instructions, uniquely valued instructions like method calls, and multi valued instructions. The later the multi valued instructions can be handled entirely be the compiler. This demonstrates how a Lisp like expression tree can easily be mapped onto the JVM instruction set, and in general a stack machine is an ideal platform for implementing a Lisp dialect using the outline described here.

On virtual machines and computer architectures

There is a wide variety of different instruction set architectures being used today, with varying degrees of complexity. In particular, there are now reduced instruction set computer architectures (RISC) that are the most barebone, having only operations for dealing with the registers and transferring data between the registers and memory. These architectures are especially common in mobile devices, because it is believed that implementing more complex instructions will place greater demands on heat and power usage. Due to the increase in mobile devices, RISC is especially common. CISC architectures tend to offer a bit more complex instructions, like instructions that combine ALU operations and loads and stores. High level computer architectures offer even more complex operations, but they are much less common. The wide variety of different architectures is a necessary consequence of, if nothing else, the vast amount of people now involved in computing at this stage in history.

Due to this wide variety of instruction set architectures, there is no reason to expect any particular complex feature will be available in any given processor. Indeed, if you selected some computer processor there is a good chance it would be a RISC computer with no complex features at all but only the bare minimum available to perform basic operations. So the utility of a virtual machine, is its portability and the extent to which it makes its complex features portable. The best way to make a program portable, or to get high level features, is to use a virtual machine.

The enormous success of the JVM is due to its portability. It was the first to really push the motto "compile once, run anywhere." Any given program for the JVM in any compiled language, can be compiled directly to JVM bytecode, there is no need for compilation to separate platforms. Given a JVM program you can can send it to someone over the network without even knowing what platform they have, simply trusting they have a compliant JVM implementation. This is genuine, true portability. We live in a networked, interconnected world, so portability certainly cannot be ignored.

The historical trend seems to be that we originally had to start with simple computers and writing assembly language by hand for any given physical machine, which is one of the impetus for the development of higher level architectures which made it easier to write assembly code for the machine. But then compilers got better, making that less necessary, leading to more reduced instruction sets. At the same time the physical high level architectures that existed, died out due to among other things a lack of portability to other more compiler-dependent reduced instruction sets. The Lisp machines died out at this time.

The next development was the virtual machine, which adapted to the reality of highly networked machines. This was best exemplified by the JVM, which first allowed people to compile a program once and run it anywhere. Its success, well other systems failed, was due to this feature. Then the next thing that happened was that specialized hardware was created for the JVM. So the only successful high level computer architectures today are specialized processors designed to run a VM more efficiently. The only way to get a successful physical machine with high level features today is to create a specialized processor for an existing virtual machine. All that is to say you need a virtual machine.

I have in mind a garbage collected stack machine for the implementation of Lisp. At least these high level features will together make the implementation of a Lisp environment more effective. Of course, these features are hardly supported in stock hardware. Fortunately, the JVM (as well as the CLR) is already a stack machine with an excellent garbage collector. Its not clear what more features one could use to implement Lisp so the JVM may already be perfect as is. Hence, the utility of Clojure.

Prefix sublist ordering

Given a set of sequences or lists, we can partially order them by rather or not one list can be embedded in another from the start. This produces a partial ordering of the set of sequences or lists we are being given.

This partial ordering is necessarily going to be a lower forest for any given relation, but if it as a prefix sublist closed relation then it is going to be a lower tree like the one shown above. One example where this prefix sublist ordering may be used is to order the sequences of indices or keys of some data structure. If that data structure is a nested list, then its sequences of integer indices can also be ordered by the lexicographic ordering. The following routine demonstrates the lexicographic ordering. Its relatively easy to implement, the main thing is to order the check the order of the first indices of the sequences and then recursively check the rest of the indices.

(defn lexicographic-successor?
  [a b]

  (cond
    (empty? a) true
    (empty? b) false
    :else (and
           (<= (first a) (first b))
           (lexicographic-successor? (rest a) (rest b)))))

This lexicographic ordering of the sequences of indices which are themselves ordered as a tree by the prefix sublist ordering produces an ordered tree. Such ordered trees are counted by the Catalan numbers $C_n$. As they are ordered trees they correspond to pure lists. The build-pure-list routine can produce a pure nested list from a such a set of indices and the get-indices routine can be used to convert any list rather it is pure or not into a set of indices.

(defn get-indices
  [coll]

  (if (empty? coll)
    #{(list)}
    (set
     (cons
      (list)
      (mapcat
       (fn [i]
         (let [v (nth coll i)]
           (if (and (seq? v) (not (empty? v)))
             (map (partial cons i) (get-indices v))
             (list (list i)))))
       (range (count coll)))))))

(defn build-pure-list
  [indices]

  (let [current-coll (sort
                      <
                      (apply
                       union
                       (map
                        set
                        (filter
                         (fn [i] (= (count i) 1))
                         indices))))]
    (map
     (fn [i]
       (build-pure-list
        (for [index indices
              :when (= (first index) i)]
          (rest index))))
     current-coll)))

It was already stated that the prefix sublist ordering is a lower tree. This means that is a meet semilattice (it is only missing a maximal element). As a result, we can compute the meet of two different elements using the longest-common-prefix function.

(defn longest-common-prefix
  [a b]

  (if (or (empty? a)
          (empty? b)
          (not= (first a) (first b)))
    '()
    (cons (first a) (longest-common-prefix (rest a) (rest b)))))

Making use of this longest-common-prefix routine, we can compute the distance between two elements in the tree. The distance is the sum of the distances to their longest common prefix, which being a prefix is only equal to the difference of their sizes. Then making use of the lexicographic ordering provided by lexicographic-predecessor as well as the

(defn indices-distance
  [a b]

  (let [ancestor (longest-common-prefix a b)]
    (+ (Math/abs (- (count ancestor) (count a)))
       (Math/abs (- (count ancestor) (count b))))))

(defn indices-distances
  [coll]

  (let [sorted-coll (sort lexicographic-successor? coll)]
    (map
     (fn [i]
       (indices-distance
        (nth sorted-coll i)
        (nth sorted-coll (dec i))))
     (range 1 (count sorted-coll)))))

This produces a sequence of positive integers corresponding to the distances of the tree. These sequences of distances fully determine the structure of the ordered tree. Given a monotone sequence, we can compute a sequence of distances from that monotone sequence sequence by taking the differences between elements of the sequence and adding one to make them positive. Further, given a semiorder we can compute such a monotone sequence from the cardinality of the sets of predecessors of each of its elements which fully determines the semiorder. That monotone sequence can then be converted into a sequence of distances and then into an ordered tree. This demonstrates the correspondence between these two types of Catalan structures, the ordered trees and semiorders.

Lattice completions

Given a partial ordering relation there are three types of elements that can occur in it defined below.

• Minimal element : an element with no predecessors
• Maximal element : an element with no successors
• Enclosed element : an element which is neither minimal nor maximal

Any partial ordering relation can be extended to form a lattice, by adding certain elements to it. These elements are going to be either minimal, maximal, or enclosed. Here is an example of a lattice completion that demonstrates each type of element, highlighted in blue added to a partial order:

A lattice, therefore, is in some sense a special type of partial order that has certain elements added to it. The dissimilarity or the distance of a given partial order to a lattice is the number of elements that need to be added to it in order to get a lattice. It is worth considering certain classes of partial orders that have bounded dissimilarity to a lattice.

• Difference zero : these are elements that are already lattices themselves
• Difference one : meet semilattices are missing only a maximal element, join semilattices are missing only a minimal element, and partial orders that are missing only an enclosed element
• Difference two : unique extrema partial orders that are missing only minimal and maximal elements but not any enclosed elements

The unique extrema partial orders which are missing only extremal elements and which are not missing any enclosed elements seem to be an interesting particular case. They are at most distance two from a lattice, and they include semilattices which are at most distance one, and lattices themselves as special cases.

The strongly unique extrema partial orders are a special case of unique extrema partial orders, which are closed under taking suborders. Forests are a special case of strongly unique extrema partial orders, and trees are a special case that are also semilattices. Locally total orders are a special case of forests that are both upper forests and lower forests. Total orders are a special class of locally total orders. All of these classes of partial orders are at most distance two from a lattice, making them relatively similar to lattices. Other classes can be distinguished by their similarity to lattices.

Boolean formulas as lattice polynomials

Given any lattice ordered set, we can form lattice polynomials from the use of variables like x,y,z and so on as well as the lattice operations $\wedge$ and $\vee$. On two elements we have lattice polynomials like $$a \wedge b$$ $$a \vee b$$ Which shows that in general, on two elements the types of lattice polynomials that we can form on them are not that interesting. On three elements we can form a wide variety of lattice polynomials like $$a \vee (b \wedge (c \vee d))$$ $$a \wedge (b \vee (c \wedge d))$$ In general, for any given lattice, these lattice polynomials can be arbitrary trees that can be expanded to any given depth. In a distributive lattice, on the other hand, the lattice polynomials can be reduced to only two elements which can be expressed one of two ways, either as the meet normal form or as the join normal form of their variables. $$ (a \vee b \vee c) \wedge (d \vee e \vee f) \wedge (g \vee h \vee i) $$ $$ (a \wedge b \wedge c) \vee (d \wedge e \wedge f) \vee (g \wedge h \wedge i)$$ A boolean algebra is a special case of a lattice, therefore boolean formulas can be expressed as a special case of lattice polynomials, with the only adjustment being that variables can be either negated or not. Boolean algebras are distributive, therefore every boolean formula can be expressed as either the conjunctive normal form or the disjunctive normal form. This shows that propositional logic deals with a subset of lattice theory.

Combinatorial use of the Catalan numbers

The Catalan numbers count a number of structures that appear in mathematics like ordered trees, monotone paths, non-crossing partitions, unlabeled semiorders, etc. But one of the most interesting things about Catalan numbers is that they count the number of expressions that can be built from purely parenthesis like these.

()
(())
(() ()), ((()))
(() () ()), (() (())), ((()) ()), ((() ())), (((())))

In other words, these Catalan numbers can be used to count the number of Lisp expressions built purely from the parenthesis. For those of us interested in list processing, it is worth considering the Catalan numbers and the structures related to them.

Asymptotic growth of the Catalan numbers

The Catalan numbers have a convenient definition in terms of the central binomial coefficient, which is defined by the factorial. As such, we can compute the asymptotic growth of the Catalan numbers using the asymptotic definition of the factorial we already have acquired using Stirling's formula. The central binomial coefficient is equal to $2n$ factorial divided by $n$ factorial squared. $$\frac{(2n)!}{{(n!)}^2}$$ We can plug in the asymptotic definition of the factorial into the above equation to get the following formula. $$\frac{ \frac{\sqrt{2\pi (2n)} (2n)^{2n}}{e^{2n}} }{ (\frac{\sqrt{2\pi n} n^n}{e^n})^2 } $$ In order to reduce this formula first we will notice that the $e^{2n}$ on both sides of the equation can be eliminated. To simplify the denominator notice that the square root of four is two, which can be pulled out of the square root. Then simplify $(2n)^{2n}$ by pulling out each of its factors. Then to simplify the denominator square it by multiplying the exponent of the factors by two, eliminating the square root. This results in the following reduced formula $$\frac{ 2(\sqrt{\pi n}) 4^n n^{2n} }{ 2(\pi n) n^{2n} } $$ It is plainly apparent that $2$ and $n^{2n}$ can be eliminated from both sides of the ratio. Then the two terms involving $\pi n$ can be simplified by adding their exponents which effectively puts the square root in the denominator. $$\frac{4^n}{\sqrt{\pi n}}$$ This is the asymptotic definition of the central binomial coefficient. Then in order to get the asymptotic growth of the Catalan numbers from this all that we have to do is divide it by $n+1$. $$C_n \sim \frac{4^n}{\sqrt{\pi n}(n+1)}$$ This gets us the asymptotic definition of the Catalan numbers. They grow at the rate of an exponential function with a base of four. This demonstrates that the asymptotic definition of the Catalan numbers can be acquired just from the definition of the asymptotic growth of the factorial which we have already shown.

Stirlings approximation

The factorial is typically defined by the product of the first $n$ numbers. It can therefore be assumed that the factorial can simply be defined by the product of the first $n$ numbers and that is all there is to it. But actually, to compute the factorials of large numbers it is better to use a different algorithm then that. The best ones tend to use the prime factorization, by noting that the prime factors of $n!$ are all less then $n$ as well as some variant of Legendre's formula which determines the exponents of the prime factors of the factorial. The best algorithm to compute factorials seems to be the prime swing algorithm which reduces it to the swings, with a good big integer library this can be used to compute very large factorials quickly.

Considering that the factorial can be expressed in different ways, it is worth considering how it can be expressed asymptotically. To begin with we know that the factorial function $n!$ grows super-exponentially because $n!$ is multiplied by increasing large numbers as the sequence grows. When one considers super-exponential functions one of the first functions that comes to mind is $n^n$. As it turns out the ratio between $n^n$ and $n!$ grows only exponentially, so it can be reduced. In order to consider the base of this exponential growth rate, we will divided consecutive terms of it. $$\frac{\frac{(n+1)^{(n+1)}}{(n+1)!}}{\frac{n^n}{n!}}$$ We can change $(n+1)!$ to $n!*(n+1)$ and then remove $n!$ from both sides. After that we can remove one from the exponent of $n+1$ by dividing it by $n+1$ to get the reduced formula. $$\frac{(n+1)^n}{n^n}$$ The resulting formula ${(\frac{n+1}{n})}^n$ is precisely the limit definition of $e$ which is what we are familiar with. $${(\frac{n+1}{n})}^n$$ This demonstrates that the ratio between $n^n$ and $n!$ grows exponentially. As both of these two functions have interpretations in combinatorics, with $n^n$ counting the number of functions on a set and $n!$ counting the number of them that are reversible, this counts the ratio of reversibility of them. This ratio grows exponentially at a rate with a base of $e$ as we have shown. This seems to be a fundamental theorem about the nature of reversibility. This gives us a hint as to how we can asymptotically approximate $n!$. Abraham De Moivre demonstrated that $n!$ grows at the rate of $\frac{n^n}{e^n}$ times $\sqrt{n}$ as well as some constant left to be determined later. $$n! \sim c \sqrt{n} \frac{n^n}{e^n}$$ Stirling then proved that the constant is equal to the square root of $2\pi$ which produces Stirlings formula for the factorial. $$n! \sim \sqrt{2\pi n} \frac{n^n}{e^n}$$ This equation given by Stirling is the full asymptotic definition of the factorial function. The appearance of $e$ in the asymptotic definition of factorial also gives some insight into why it is that the reciprocals of the factorials happen to converge to $e$.

Base of differential fixed points

Consider the definition of the difference quotient in terms of the quotient produced by an interval of length $h$. $$\frac{f(x+h)-f(x)}{h}$$ We want to study the fixed points of this difference quotient, supposing that $h$ is fixed. In order to do so we can equate $h$ with $f(x)$. To simplify this equation we can multiply both sides by $h$ and then add $f(x)$ to both sides. $$\frac{f(x+h)-f(x)}{h}=f(x)$$ $$f(x+h)-f(x)=hf(x)$$ $$f(x+h)=(h+1)f(x)$$ At this point we can raise $h+1$ to the power of $1/h$ to get the base of the fixed point of difference quotient with fixed length $h$. $$b = (h+1)^{\frac{1}{h}}$$ This formula works in general to compute the base of the fixed point of a difference quotient of any given length. We tend to want to reduce our consideration to the case of unit fractions $1/n$ in which case we get the following familiar formula for the base of the differential of the fixed point of a given unit fraction length: $${(\frac{n+1}{n})}^n$$ Actual values of this sequence of rational numbers are provided below. The first case $2$ is the fixed point of the difference quotients of length $2$ or the difference quotients of length $1$, the next number $9/4$ is the base of the difference quotients of length $1/2$, and the next is the base of the difference quotients of length $1/3$, and so on. $$2, \frac{9}{4}, \frac{64}{27}, \frac{625}{256}, \frac{7776}{3125} ...$$ As a result, in the case of finite differences it is possible to use $2^x$ as a fixed point. The consecutive differences of the $2^x$ sequence are the values of $2^x$ itself. But this $2^x$ value does not suffice when taking difference quotients of smaller lengths. $$1,2,4,8,16,32,64,128,256,...$$ In order to get the fixed point of the difference quotients of smaller lengths it is necessary to use the formula ${(\frac{n+1}{n})}^n$ we derived earlier to get a different base. If we then continue this process to infinity we get the base of the fixed point of the derivative which is $e$ which leads to the function $e^x$ which is equal to itself under differentiation. This demonstrates that the limit ${(\frac{n+1}{n})}^n$ is not simply a random means of generating $e$ it is actually a formula for the different fixed points of the difference quotient. So actually the identity of $e$ is as the fixed point of the derivative and the limit definition is just computing different fixed points of the difference quotient.

Order theory and mathematical analysis

Asymptotic analysis describes the limiting behavior of a function as it approaches infinity. Using asymptotic analysis, we have notions of different rates of growth, so for example, we can have linear, polynomial, or exponential growth rates among others. We can extend this notion to totally order functions by their growth rate, so that growth rates are roughly totally ordered. Though this totally ordered structure is not going to be an ordinary one.

Through the use of order theory, we can extend the real numbers to get non-Archimedean ordered fields that contain both infinite and infinitesimal elements. This includes ordered fields such as the surreal numbers as well as the transseries which characterize growth rates. It has even been shown that the field of transseries carries the structure of the surreal numbers. This shows that the growth rates of functions form the most general order worth studying. This directly applies order theory to asymptotic analysis.

Asymptotic analysis is directly related to the calculus because the derivatives of functions are really another way of looking at the growth rate. So really by looking at order theory, we can see how it is directly applicable to most of mathematical analysis already.

Metric spaces are already explicitly defined in a way that relates them to order theory, as they use an order to relate their distances to one another. Something must be closer to something else in an ordered fashion. Recently, I demonstrated that metric spaces are directly related to the order topology of their set of distances. The order topology of the set of distances places a limit on the topology of the metric space. This demonstrates that really practically all of mathematical analysis can benefit from the use of order theory.

But the relationship goes back in the other direction too because of the order topology. Given any partially ordered set we can explore the topological properties of the order using the open sets formed from it. This shows that topological notions like isolated points can be applied to any partial order. This demonstrates the analytic and topological nature of order theory itself.

Really, metric spaces, orders, and so on are all united by the common thread of topology. Really, it can be said that the common thread at the root of different aspects of mathematical analysis is topology. Orders have a topology on them, and metrics have a topology on themselves and their distance order. As it happens, I consider orders and metrics to be two of the most important structures so thinking about them, the relationship between them, and relating that back to topology has consumed much of my attention.

Rates of convergence

Given a sequence of rational numbers that sequence can either converge or diverge. If it converges to some point in the number line, then it does so at some rate. It can either converge to a rational number or to an irrational number. If it converges to some rational number then it is equal to some rational number plus or minus some infinitesimally small sequence that converges to zero. It is well known, for example, that the reciprocal 1/n converges to zero, so a number like 5+1/n converges to 5. The reciprocal of another function like 1/n^2 converges to zero quickly, so 5+1/n^5 converges to 5 quicker then 5+1/n. This difference is expressed in rates of convergence.

If we have some sequence that converges to an irrational number, then the same principle applies analogously. Consider the Leibniz formula, it converges to pi, but it does so extremely slowly. In order to get an accurate approximation of pi, it is not a very efficient sequence to use. The Ramanujan formula and Chudnovsky formula converge much faster. This shows that irrational numbers can be approximated to a greater or better extent by different sequences. An irrational number can then be defined be the most convergent sequence that is currently available. This is similar to defining them by equivalence classes, except this allows you to actually compute rational approximations.

Theory of relations

The concept of a total ordering relation plays a fundamental role in mathematics. Sequences are a type of total ordering in which elements can occur more then once. Sequences in which no element appears more then once are no different then a total order. The importance of this concept derives from the importance of total orders. By combining the theory of total orders and sequences with set theory we can get the theory of relations which deals with sets of sequences.

Given a partial ordering relation, sequences in the partial order are called monotone non-decreasing if no two elements coming after one another are ever less then one another in the partial order. It is monotone increasing if they are not equal either. A partial ordering relation can be determined by its relation of monotone sequences. The typical definition of a partial ordering relation is the set of all monotone non-decreasing sequences in the partial order of size two. This relation of monotone non-decreasing sequences has the properties of reflexivity, anti-symmetry, and transitivity that characterize partial orders. This leads to a special kind of relation.

Given a partial order we can form a relation from its monotone non-decreasing sequences of a certain size. If it is finite height, we can form a relation consisting of its maximal monotone increasing sequences, and so on. In general, it is useful to consider relations consisting of sequences of any size using this understanding of order theory and sequences. The notion of a nary relation is merely a special case which consists of sequences of any particular size.

As a consequence, it is now useful to extend our understanding of relations beyond the theory of nary relations and specifically unary relations, binary relations, ternary relations, and quaternary relations, which is typically established. We can use concepts analogous to the theory of set systems to talk about special classes of relations. The rank of a relation is the size of its largest sequence. Sequences in a relation can be distinct or equal and so on. The theory of relations will play a foundational role in the construction of our new computer algebra system.

Total order theory

My recent research into the theory of order topology led me to realize just how connected the theory of order topology and metric spaces is. A metric space can be partially characterized by the order topology of its distances, so that a metric space with discrete distances is itself discrete. In this way, order topology is connected not only to the theory of metric spaces but all of mathematical analysis. The results of this research, and a considerable examination of the theory of total orders in general is presented in the following paper.

https://drive.google.com/file/d/1RNg0yXtIad6ziTvjkzINajBknPl6n9wG/view?usp=sharing

Falsehood preserving boolean formulas

The particular class of falsehood preserving boolean formulas is of some interest to us, because it can be expressed with differences rather then with complements. So we can apply them to sets without having to deal with or define their complements. The most basic falsehood preserving logical connectives in set theory are the constant empty set and the identity. Beyond that there is union, intersection, difference, and symmetric difference which are among the four most important logical connectives in set theory. All of them are falsehood preserving because they do not take anything from the complement. They can be expressed with union, intersection, and difference without reference to complements. The symmetric difference is merely the difference between the union and the intersection. Other boolean formulas can be expressed using complements, when necessary, but it is useful to be able to express set theoretic operations without defining them.

Boolean formulas

Boolean formulas can be used to express constraint satisfaction problems in general, among other things. The manner in which we solve boolean formulas is defined by resolution. Assuming that a given boolean formula is effectively expressed in conjunctive normal formula we can apply resolution to any two clauses in the boolean formula which have complementary literals, which will get us a new clause which contains all literals that do not have complements. Well applying the resolution rule, if we get a clause that is simpler then some larger clause that contains it, we can eliminate the larger clauses. This is one way we can use deduction to solve logic problems.

Cauchy sequences of rational numbers

One of the important problems in analysis is determine how to represent real numbers. The natural definition which occurs from order theory is that a real number is defined by a Dedekind cut which is effectively a partition of the rational numbers into upper and lower sets relative to the real number. This defines the order theoretic properties of the real number. In order to make sense of the Dedekind cut, it is necessary to have a lower bound sequence and an upper bound sequence, the two of which together give an increasingly accurate interval approximation of the real number. The representation of a real number in terms of a sequence of intervals is equivalent to using two sequences anyways.

On the other hand, if we take the metric definition rather then the order definition we get Cauchy sequences which are sequences that satisfy the Cauchy criterion which states that consecutive numbers get increasing close together as the sequence goes on. We can represent any given number then using a cauchy sequence of rational numbers. In an implementation sense, this can be defined using a function between the set of natural numbers and the set of rational numbers, both of which are countable so this can be implemented computationally. A single sequence may not be enough to compute the order properties of the number, but it is enough to define the number in terms of the metric space.

Scattered total orders

A totally ordered set is hereditary discrete if it is locally finite. A locally finite total order can be of four types: bounded, lower bounded, upper bounded, and unbounded. The bounded locally finite total orders can be further classified based upon their cardinality because they are finite. The lower bounded locally finite total order describes the non-negative integers $\omega$ and an upper bounded locally finite total order describes the non-positive integers $-\omega$ which are their order dual. The unbounded locally finite total order describes the integers $\mathbb{Z}$. All hereditary discrete total orders are suborders of the integers, which makes the integers the most advanced number system that can be used to describe hereditary discrete ordering structures.

The bounds of these hereditary discrete total orders can be visualized by using an arrow diagram. This leads to the description of the natural numbers as -> their order dual as <- and the integers as the bidirectional arrow <->. The unbounded order can be described as a dot point or a number which simply states what the cardinality of the order. In this way, we can see how locally finite total orders are described by the manner in which they are bounded or unbounded.

Scattered orders are distinguished from hereditary discrete ones in that some of their subsets have points that are limits of isolated points rather then being isolated themselves. Scattered orders can be formed from the ordinal sum of one another. At the most basic level, we can take the ordinal sum of some finite number of hereditary discrete total orders. An example is the total order [-> <-] which describes a pair of orders that are both pointed in the same direction to an unbounded extent. We can also get the double arrow [-> ->] and the double back arrow [<- <-] both of these orders are ordinal numbers and their duals respectively as they use only one type of arrow. We can also add bounds on established orders [-> .], [. <-], [. <->], [<-> .], [. <-> .]. These can be extended to any number of elements like [-> -> <- <-] which is two double arrows going to the same direction.

Some scattered orders are well founded or converse well founded, depending upon rather or they have all their arrows going in the same direction or in other words rather they have minimal or maximal elements. These well orders correspond to ordinal numbers, which are a particular type of scattered ordering. The process of chaining together these total orders can be extended infinitely in either direction. This leads to the ordinal of the second power $\omega^2$ which is equivalent to the sequence [-> -> -> ...] going on infinitely. There is also its order dual $-\omega^2$ which is equivalent to the sequence [... <- <- <-]. These are some of the ordinal scattered orders with an unbounded number of locally finite total orders chained together.

The total orders can also be combined together in a non-ordinal manner like [<- <- <- ...] which continually chains together an infinite number of back arrows going in a forwards direction. This is not an ordinal because the arrows are chained together in a different direction then the arrows are going themselves. Its order dual is [... -> -> ->] which is an infinite number of forward arrows chained together in a backwards direction. We can also chain together integer sets like [<-> <-> <-> ...] and [... <-> <-> <->]. If we chain together these locally finite orders in a manner that is unbounded in both directions then we can get a new type of total order. An example of this is the order [... -> -> <- <- ...] which is an infinite number of arrows pointing chained together from both sides pointing towards the same point. Other examples include [... -> -> -> ...] and [... <- <- <- ...]. Notice that no orders of this type are ordinals or reverse ordinal no matter what arrows are chained together in them. If we then combine together an unbounded order in an unbounded manner we get [... <-> <-> <-> ...] which is $\mathbb{Z}^2$ which is the next type of order we are going to consider.

A locally finite total order is defined as one in which for any pair of elements within the total order there is only a finite number of points between them. Each point is contained in a single set which is defined by all the points that are finitely reachable from that point. The sets form the locally finite components of the total order which partition the order. Every scattered total order can be described as an ordinal sum of locally finite total orders in this manner. The next level is to describe total orders that are the ordinal sum of a locally finite number of locally finite components. This leads precisely to $\mathbb{Z}^2$.

Continuing this process we can then get those total orders which are defined as the locally finite ordered sum of $\mathbb{Z}^2$ components. This includes ordinal numbers like $2\omega^2$, $2\omega^2+\omega$ and $\omega^2+2\omega+1$ as well as their inverses like $-2\omega^2$, $-2\omega^2-\omega$ and $-2\omega^2-\omega-1$. Ordinals of different types can be chained together to get orders like [$\omega$,$-\omega^2$] and [$\omega^2$,$-\omega$]. Another example that is defined by chaining together orders that aren't all ordinals is [$\omega^2, \mathbb{Z}, -\omega^2$]. All these orders defined so far, have been a finite combination of $\mathbb{Z}^2$ components. If we combine them together infintely we can get the ordinal number $\omega^3$ and the reverse ordinal $-\omega^3$ and continuing on infinitely in both directions we can get $\mathbb{Z}^3$. This is the order consisting of a locally finite amount of $\mathbb{Z}^2$ components. Continuing on in this manner we can get $\mathbb{Z}^4$, $\mathbb{Z}^5$, $\mathbb{Z}^6$, $\mathbb{Z}^7$,$\mathbb{Z}^8$, onwards to infinity to get $\mathbb{Z}^\omega$ which describes all scattered orders with a finite degree of nesting of locally finite components.

Considering everything that we have seen here we can now classify scattered total orders. The simplest type of scattered total order is the integers $\mathbb{Z}$ which are locally finite. The next simplest type of scattered total order is the $\mathbb{Z}^2$ which consists of a locally finite sum of locally finite components. This can be continued to some degree to get the powers of $\mathbb{Z}$ which are the orders $\mathbb{Z}^\alpha$ where $\alpha$ is some ordinal number. By an important theorem from Hausdorff, we know that the scattered total orders can be described by these general powers of the integers.

Order topology

Given a totally ordered set, we can form an open topology on that set from the set of open rays consisting of all the points that are either strictly greater or strictly less then a given point. The order topology also contains the open intervals of the set. The first concept that can be derived from the order topology is that of an isolated point. An isolated point is a singleton set of the order topology. A discrete total order consists entirely of isolated points. A point is considered to be near isolated if it always contains an isolated point in any open set containing it.

A scattered topological space is strictly near isolated. These scattered topological points consist of both isolated points, and limits of isolated points. Scattered topologies include discrete topologies as a special case. In this sense, they are somewhat of a generalization of discrete topologies. Points are often defined by the existence of a topological subspace that contains them. A scattered point is a point that is contained within some scattered topology. Scattered total orders are defined as total orders with a scattered topology.

A topological space that contains no isolated points is dense in itself, which makes it relatively less restricted then these other types of topological spaces. The other spaces are defined based upon forbidding dense subspaces. A space can include dense subspaces as well as isolated points and be neither type of topology. A point can be characterized based upon rather it is contained in a dense in itself. Dense total orders are defined as total orders with a dense in itself topology. The real numbers themselves have a dense in itself topology.

A metric space is defined based upon a totally ordered set of distances. The character that a metric space can take is determined by the order topology of its set of distances. If a metric space has a discrete set of distances then it is necessarily going to be a discrete metric. For example, the path metric on a graph uses only integer distances so it will necessarily only form a discrete metric. In the same sense, if a scattered set of distances is used, then the metric space will necessarily be scattered as well. As a result, being either discrete or scattered is transferred from the order topology of the distances to the metric space. In this sense, the order topology is perhaps the most fundamental concept in the theory of metric spaces.

It is useful to define a metric space associated with a given partial order. In a locally finite order this can be defined based upon the path metric of the covering graph. If the order has a different topology, however, then it is necessary to define a different type of metric space on it. In particular, if an order has a dense topology then the path metric may no longer suffice and it will be necessary to define some other concept of distance between points. So a dense metric can be created so that it can be associated with the dense order.

Subgraphs of connected graphs

Given a connected graph as well a subset of the vertices of the connected graph, we can form a subgraph of the connected graph containing only the vertices in that subset. This subgraph need not be connected itself, or even non empty as it could consist of disconnected points. The interesting property of the subgraph then is actually its metric rather then its adjacency relation. We can form a metric on the subgraph by determining the distance between each point in the parent graph based upon the shortest path metric.

2017 year in review

The theory of set systems continued this year. I realized early on in my own mathematical study is that set theory is the best foundation of mathematics, which naturally leads to the theory of set systems. Two types of set systems became of particular interest to me at this point in time: subclass closed set systems and moore families. These two types of set systems seem to play a foundational role, even in the theory of set systems themselves as we can consider subclass closed families of set systems, and moore families of set systems and their properties.

One thing that is worth realizing when dealing with these two types of set systems is that they both have a necessary rank associated with them, which determines the number related elements necessary to define any set in them. The necessary rank of a subclass closed system, is the smallest number of elements needed in a set to determine membership. The necessary rank of Moore family is the smallest number of elements needed to define the closure of a set together.

A power set is both subclass closed and a moore family. It is the smallest necessary rank for both types of set system, and it is trivially defined by its parent set, as it is rank complete, meaning it has no distinguishable elements. Clique families are defined by the cliques of a graph, and Alexandrov families are defined by setting the closure of any singleton set equal to the lower set that contains it in its preorder. Naturally, this demonstrates that graphs and preorders are among the structures that can be represented as set systems in this manner.

Sets of sets like these remain the most important area of study. It is worth mentioning the distance between elements in a graph is determined by the length of the shortest path between them. This naturally leads one to consider notions of distance. Starting in this year, I begun to gain a great interest in the theory of metric spaces and related subjects like geometry, topology, and analysis. My understanding of metric spaces reached only a most basic level, so it was necessary to continue studying it into the next year. This new interest in metric spaces is one of the major takeaways of this year.