Ontology of JVM instructions

The JVM opcodes by function helps users to better understand the opcodes of the Java virtual machine (JVM) by category. But this classification has its limitations, its a tree and therefore it doesn't include all the instruction types that may useful to the compiler developer. Additionally, there is a category of miscellaneous operations and array length is categorized as an object function rather then an array function. At the same time, instanceof and checkcast are object operations even though they can be applied to arrays. It is clear that there is a general type of references, and certain instructions are applicable to both types of references. The only functions that are truly reserved for object references are the instance field functions. The static field functions are not really related to references, and should therefore be grouped under atomic variables with the local variables.



In order to enable stack compatibility I decided to separately classify multi-valued instructions and uniquely-valued instructions. The only multi valued instructions are the duplication and swap instructions. The uniquely valued instructions have the same calling convention as methods, so they can be grouped together with them. In this sense, this classification of instructions is ultimately stack based and it deals with the fact that the JVM is a stack machine. Here is an alternate view of a hierarchical part of this ontology.

Uniquely valued stack instructions
    Constant push instructions
    Trivial procedures
Atomic variable instructions 
Reference allocation instructions (these return references)
    New, newarray, anewarray, multianewarray
Reference operations (these take references as arguments)
    Reference procedures (zero valued)
        Reference variable modification
        Unary reference procedures 
            throw, monitorenter, monitorexit
    Reference transformations (single valued)
        Reference variable access
        Unary reference operations 
            getfield, arraylength, reference type checkers
Primitive transformations (these take and return primitives)
    Unary primitive transformations
        Cast instructions
        Neg
    Binary primitive transformations
        Binary arithmetic instructions
        Logical instructions
        Comparison instructions

The atomic variables include both the local variables and the static variables, they are characterized by the fact that they do not require a reference as an argument to access them. The class of value push instructions, which are nullary single valued instructions, includes all the constant push operations, local variable access operations, and the class variable access operations. The class of value push instructions can be used to construct the atomic expressions in a Lisp dialect, like Clojure or Lisp flavoured Java. In this way, when an atomic expression like 2, 2.2, x, or class/name appears in the code then they are automatically converted to value push instructions. This is part of the correspondence between Lisp and a stack machine. The atomic expressions in Lisp correspond to their own instruction class (the value push instructions) and the combiners correspond to their own instruction classes as well separately.

In order to make Lisp correspond to the stack machine you only need to make it so that atomic expressions correspond to certain value push instructions, and the combiner forms correspond to certain uniquely valued instructions. All Lisp programs consist of these two types of components, just as a stack machine consistent of these different types of instruction classes, which makes it so effective to construct a correspondence between them. The only other nullary single valued instruction is a static method call that takes no arguments and returns something, basically a constant function or an object reference allocation. By convention, the constant function should be a call to a function like (Class/function) rather then appearing as an atomic term, so that effectively deals with the problem of atomic expressions.

Generic instructions:
When it comes to combiners on the other hand, in the JVM there are different combiners for different data types of arguments presented to the instruction on the stack. In order to make generic instructions available, it is useful to be able to have instruction classes corresponding to the different versions of an instruction that takes different types. For example, the add class could include iadd, ladd, fadd, and dadd instructions. Then when a generic combiner is presented to the Lisp flavoured Java developer, it is immediately known that it will produce some member of the generic instruction class dependent upon the types of the arguments given to it. This need for generic instruction classes, is especially important because of the typed nature of the JVM.

Generalized variable instructions:
The JVM actually has two types of variables avaiable to it: atomic variables and reference variables. The atomic variables do not take any arguments on the stack to get their value or any extra ones to set their value. The atomic variables can therefore be accessed as atomic expressions like in Lisp, hence their name. The atomic variables are the local variables and the class variables. The reference variables are the array variables as described by the array store and array load operations and the instance variables which are the fields of some object reference. Each of these different variable types have both the getters and accessors on them, so they can be both accessed and modified. Generalized variables correspond to the l-values in the Java programming language. By using the generalized variable instruction class, we can better understand how the setf operation can be implemented by the compiler.

Books on virtual machines

The Java virtual machine book is ideal for anyone wanting to learn about the Java virtual machine. The authors of this book also created Jasmin which is the standard assembly language for the Java virtual machine. So it is an ideal resource for learning about the assembly language of the JVM. In order to understand the JVM I read this book along with the Java virtual machine specification which can be found online.

When learning about the common language runtime (CLR) it is best to get a book by Serge Lindin like .NET IL Assembler. Serge Lindin appears to be the only author that is dealing extensively with the CLR virtual machine and its assembly language. His book has helped me to understand the CLR and its differences from the JVM. It has everything you need to know about the CLR and its instruction set. In particular, it has a classification of the instructions used by the CLR. It uses the assembler ilasm which comes with the CLR itself.

Block cut tree

One of the most important concepts in graph theory is the block cut tree of a graph. The block cut tree of a graph is determined by splitting up the components of a graph into two parts: the cut vertices whose removal disconnects the graph, and the blocks which are biconnected components that don't contain any cut vertices in their own graphs. The block cut tree determines the betweenness relations of the graph, and in particular it completely determines the total betweenness relations which are defined by the set of all points in paths between two points. To consider the block cut tree we will start with the example below.



One thing that is worth realizing about the block cut tree is that cut vertices are singular elements and all blocks have two or more elements in them. This suggests a way of representing the block cut tree as a set system, so I decided to represent it in this way. In order to get the block cut tree like this the function bcset can be used.

(= (bcset graph)
    #{#{0} #{1} #{2} #{3} #{7} #{8}
      #{0 4} #{7 3} #{6 2} #{1 5} #{7 8} 
      #{9 10 8} #{0 1 3 2}})

This produces a height two forest-comparability ordered set system in which cut vertices belong in the blocks associated with them. The block cut tree is merely the inclusion comparability of this set system, which as displayed below is a tree.



One characteristic of the block cut tree, is that every element is either a cut vertex or it is contained in some block. This relates the elements of the graph to the elements of the block cut tree. One interesting aspect of this set system representation is that the block or the cut of the point within the tree can be determined by getting the smallest set containing it. In other words, it can be computed by getting the intersection of the set of all sets that contained the point as a member. This is what the subdimembers function does with respect to the set system.

(= (subdimembers tree 2)
   #{2})
(= (subdimembers tree 10) 
   #{9 10 8})

This relates the members of the graph to the members of the block cut tree. The next thing to be computed is the path between two points in the block cut tree as determined by the sets corresponding to those points. This determines a path between any two points in the block cut tree of the graph. All points between two points can be determined by the union of the elements in this path set system.

(= (bcpath graph 0 9) 
   #{#{0} #{3} #{7} #{8} #{3 7} #{7 8} #{9 10 8} #{0 1 3 2}})
(= (bcinterval graph 0 9) 
   #{0 1 2 3 7 8 9 10})

This demonstrates how the problem of determining all points that are between any two points in the graph regardless of length can be determined by the block cut tree. As a tree is defined as a type of graph that has a unique path between any two points, all the paths between any two points have the same length, so the metric betweenness and the total betweeenness coincide. So well the total betweenness and the metric betweenness don't always coincide, they do coincide in the block cut tree which determines the total betweenness.

Directed and undirected trees

In both graph theory and order theory there is a concept of trees. In graph theory there an undirected trees and in order theory there are directed trees, which are given some root. A tree graph is shown below, its lack of direction is because it is a graph.



One interesting property of graphs is that they have a set of metric intervals associated with them, these metric intervals contain all points between any two points. When the graph is not traceable, then the set of metric intervals will not be upper bounded like it was with the path graph considered earlier. Well the metric intervals of the path graph form a triangular structure, only the maximal sets of the metric intervals of the tree form a triangular structure among there parts in the more general case as shown below.



Well that set of intervals of the tree graph can be considerably larger then the original graph (to a roughly triangular quadratic extent) it is interesting to consider how we can go from the original tree graph to a directed tree graph on the same number of vertices. In order to convert an undirected tree to a directed tree we need some special node to be the root. I realized that the directed version of a tree at some root is simply the set of intervals of the tree with the root as one of its endpoints. This turns into a lower tree with the root as the minimal element, as shown below for the case of the tree graph with the root chosen at zero.



Each set of intervals produced from some root produces a different directed version of the tree. The total set of intervals of the tree is therefore equal to the union of the different rooted orientations of the tree produced in this manner and the empty interval, with non trivial intervals repeated. This rooted set of intervals is also an order containment family. This means that the set of metric intervals centered around some point is also equal to the set of the principal ideals of the corresponding rooted tree.

Triangular family of intervals

Intervals are one of the most basic concepts arises from betweenness relations. A particular family of intervals is shown below. This sort of family can be formed even by metric betweenness on a path graph or order betweenness on a total order. This set system is an atomistic Moore family with a triangular structure. The number of points at some covering distance from the maximum is the covering distance plus one.



The triangular structure of the intervals has three edges. These correspond to the the join irreducibles and the meet irreducibles of the lattice. The edges on the side are the meet irreducibles and the bottom edge is the join irreducibles. The meet irreducibles are the rays and the join irreducibles are the singleton intervals. Every interval can be expressed as an intersection of rays or as a union of singleton intervals. The inner elements of the triangle. The triangular structure seems to be defining character of the set of intervals.

Concepts of betweenness in graph theory

Given a metric space, then metric betweenness can be defined by the metric betweenness formula. This states that a point is between two points if it going to through that point doesn't increase the distance to the endpoints, in other words, if it is in the shortest path between the two points. In the particular case of graphs, their metric can be defined by the shortest path length. Then this concept from the theory of metric spaces can be applied to the special case of graph theory.

$d(x,y)=d(x,z)+d(y,z)$

The actual formula $d(x,y)=d(x,z)+d(y,z)$ should be familiar from the triangle inequality, which is an axiom of the definition of metric spaces. It states that the distance between two points is less then the distance between the two points and a midpoint or it is equal to them in which case it is between them. With this in mind, the axioms of a metric space make perfect sense. The metric betweenness is the main concept of metrics used in both graph theory and metric geometry in general. A different notion is total betweenness defined by all paths rather then just the shortest paths.

Total betweenness:
The most basic context in which to consider total betweenness is trees, where there is only a single path between any two points. In this context, the total betweenness and the metric betweenness coincide. So for example, with a path graph the central vertex is between its two neighbors.


Total betweenness is totally defined by the cut vertices of a graph. To see this, consider that it is only when one reaches a cut vertex then one must make a choice of which direction to go to, which can limit the number of vertices that can be reached between any two points. In a biconnected graph, any points can be reached in a path between any other one. As a consequence, the total betweenness is entirely determined by the block cut tree of the graph. Given any two distinct vertices, all vertices in paths between them can be produced by determining all blocks and cut vertices between the two points in the block cut tree. As this is merely a process of determining betweenness on a tree which is determined by metric betweenness, it can be said that the metric definition is the main form of betweenness worth considering.

Metric betweenness:
Perhaps the simplest case to consider where metric betweenness is different then total betweenness is the case of the cycle graph on five elements. Given two non-adjacent points on this graph, there is a path between them of length three and another one of length four. All the points are between them in the context of total betweenness, but only one of them is under metric betweenness. This demonstrates that metric betweenness can give us more information in some cases.



Once we have a concept of betweenness like this, it is useful to consider convex sets, which are subsets of the graph in which all points between them are contained within the set. A closed metric interval is defined by the set of all points between them plus the endpoints. This leads to a better understanding of subsets of a graph. There is also a concept of betweenness on partial orders, which isn't considered here. This demonstrates how useful betweenness relations can be to a variety of different subjects in mathematics.

Metric recovery theorem

The metric recovery theorem proven by Malament is perhaps the most important theorem for understanding actual space and time, and the relation between order and metric in spacetime. Basically, general relativity describes the structure of spacetime using the metric tensor, which is a four dimensional symmetric bilinear form. This means that the matrix form of the metric tensor is defined by ten points at each point in spacetime. The metric tensor used in general relativity is different from a typical metric used in classical models of spacetime, the euclidean metric, because it carries with it a causal order structure on its points as well.

As the metric tensor used in special and general relativity has a causal factor associated with it, it is useful to consider which relativistic spacetimes can be recovered from a causal ordering relation. The metric recovery theorem basically demonstrates that the metric tensor can be recovered from the causal ordering up to a single conformal scale factor. So nine of the ten distinct terms of the metric tensor can be recovered. The only thing remaining is the conformal factor.

The basic issue of how to construct the conformal factor then is the most important thing that remains. Remember from order topology, that a given partially ordered set can have different topologies associated with it: discrete, scattered, or continuous. One aspect of a discrete partially ordered set, is that concepts like measure and volume come for free from it, and they don't need to be defined separately. It has thus been concluded that spacetime could be modeled as a discrete partial order, with the conformal factor being volume, and then there is no need for any extra structure. This is the program of causal set theory.

It has been said that spacetime looks awfully a lot like a discrete partially ordered set. Rather it is one or another is a separate issue, it certainly looks like one. On the other hand, one can attach a conformal scale factor to a continuous partially ordered in order to allow for an effective continuous model of spacetime. This leads to the metric tensor. In either case, spacetime can be modeled as a partial order. It is either a discrete partial order or a continuous partial order which is equipped with a conformal scale factor.

References: Malament, David B. (July 1977). "The class of continuous timelike curves determines the topology of spacetime". Journal of Mathematical Physics.