- Sets : cardinal numbers
- Multisets : multiplicities signature
Saturday, March 2, 2019
Foundational distributive lattices
An unordered collection can be either a set or a multiset. Unordered collections are the foundational core of mathematics, as well as the basis of all ontologies. All unordered collections form distributive lattices.
Sets and multisets also have an isomorphism types associated with them, for the sets it is the cardinal numbers, and for multisets it is the multiplicities signatures. In order for a set to be included in another its cardinality must be less then the cardinality of the other set. In order for a multiset to be included in another its signature must be less then the signature of the other multiset.
Sunday, February 24, 2019
Overview of trees in graph theory
The most basic way in which graphs are related to trees is through the block cut tree of the graph, which can be formed by any connected component. The most basic tree related property of a graph is the nature of its biconnected components. A tree is simply a graph whose biconnected components are all trivial. A cactus tree has the simplest biconnected components, and a clique tree or a block graph has the largest biconnected components. A pseudoforest is a cactus tree with only one biconnected component in each connected component.
- The block cut tree of a graph
- The modular decomposition tree of a graph
- Tree graphs
- Comparability graphs of trees
Modular decomposition
One of the basic concepts of graph theory is that of a module of a graph, which is a subset of the graph in which every element outside of the subset is either adjacent or non-adjacent to each member of the module. This generalizes the cotree consisting of connected components and their complements, as demonstrated by the graph below which is connected and so is its complement.
When a graph is a cograph, then it can be decomposed into atomic components by the modular decomposition. Otherwise, modules can occur that are unrelated to the connected components or their complements, in this case as Gallai showed the modular decomposition can be produced by the maximal modular subsets, which form a set partition of the component. This mechanism is used to produce the modular decomposition described below for the graph.
The first thing that one notices about this modular decomposition is that it is a laminar family. All the direct subsets of each module in the tree partition their parents. In fact, it is a nullfree laminar upper tree family. In this sense, the modular decomposition tree is like the parse tree of a graph.
When a graph is a cograph, then it can be decomposed into atomic components by the modular decomposition. Otherwise, modules can occur that are unrelated to the connected components or their complements, in this case as Gallai showed the modular decomposition can be produced by the maximal modular subsets, which form a set partition of the component. This mechanism is used to produce the modular decomposition described below for the graph.
The first thing that one notices about this modular decomposition is that it is a laminar family. All the direct subsets of each module in the tree partition their parents. In fact, it is a nullfree laminar upper tree family. In this sense, the modular decomposition tree is like the parse tree of a graph.
Monday, February 18, 2019
Parse trees as set systems
The task of parsing a data structure into its constituent components usually involves an ordered sequence of characters or bytes. When classifying subsets of an ordered sequence like a byte stream or a string, the most important thing about the sequence is its betweenness relation, as we can limit our parent set to the set of intervals of the sequence. This is what instaparse does, as it automatically gives you the intervals of characters in the parse tree of some string subject to some context-free grammar. To demonstrate this I will consider the simplest possible program.
As a set system the parse tree is a laminar family. As laminar families emerge in the study of parsing, they are a special class of families that should be studied further. It is also nullfree because it doesn't contain the empty set as a member.
Definition. a family of sets $F$ is called a laminar family if for every two elements $S_1, S_2$ either $S_1 \subseteq S_2$, $S_2 \subseteq S_1$, or $S_1 \cup S_2 = \emptyset$. In other words, every pair of elements is either order comparable or disjoint.
The class of laminar families is a set of sets of sets of rank two, which makes it a clique complex whose relation is defined by the union of the order comparability and disjointness. Every nullfree laminar family forms an upper forest, and connected nullfree laminar families form upper trees. So laminar families provide a general means of describing tree decompositions of structures.
(defn hi [args]
(prn "hello world"))
As a set system the parse tree is a laminar family. As laminar families emerge in the study of parsing, they are a special class of families that should be studied further. It is also nullfree because it doesn't contain the empty set as a member.
Definition. a family of sets $F$ is called a laminar family if for every two elements $S_1, S_2$ either $S_1 \subseteq S_2$, $S_2 \subseteq S_1$, or $S_1 \cup S_2 = \emptyset$. In other words, every pair of elements is either order comparable or disjoint.
The class of laminar families is a set of sets of sets of rank two, which makes it a clique complex whose relation is defined by the union of the order comparability and disjointness. Every nullfree laminar family forms an upper forest, and connected nullfree laminar families form upper trees. So laminar families provide a general means of describing tree decompositions of structures.
Saturday, February 16, 2019
Commutative aperiodic semigroups
Certain partial orders have semilattices associated with them. Semilattices are commutative idempotent semigroups that arise entirely from order theory. Commutative aperiodic semigroups are a generalization of semilattices, which can be used in a wider variety of cases. It is known that every commutative semigroup has an algebraic preorder associated with it, as described below. It can easily be seen that this is not a partial order, unless the semigroup is aperiodic.
\[ \exists z : x + z = y \implies x \le y \]
Set theory is based upon set union, which forms an idempotent commutative monoid. Well idempotence works well for set theory, it won't do for arithmetic. The natural numbers under addition $(\mathbb{N},+)$ can instead be modeled as an aperiodic commutative semigroup.This automatically generates the partial ordering on the natural numbers $(\mathbb{N},\le)$ because the addition operation only ever builds up a number by making it bigger, which is obviously not the case in a non-aperiodic semigroup like the integers. So set theory can be founded by an idempotent commutative monoid and arithmetic can be founded instead by an aperiodic commutative monoid.
It is interesting to consider the atoms in a commutative aperiodic semigroup like this. Atoms are defined as in order theory, as the elements that are only greater then the identity. The atoms in set theory are the individual members or singleton sets, which can be used to build up every element through set union. The atom in arithmetic is the singular unit, one which can be used to build up every natural number through addition. These are atomically generated semigroups. Atomically generated semigroups don't need to be atomistic lattices, as seen by the fact that the natural numbers are atomically generated. It is in this context that multisets can arise as values built up from a commutative aperiodic monoid, like sets are built up, except that the combiner operation is aperiodic rather then idempotent.
\[ \exists z : x + z = y \implies x \le y \]
Set theory is based upon set union, which forms an idempotent commutative monoid. Well idempotence works well for set theory, it won't do for arithmetic. The natural numbers under addition $(\mathbb{N},+)$ can instead be modeled as an aperiodic commutative semigroup.This automatically generates the partial ordering on the natural numbers $(\mathbb{N},\le)$ because the addition operation only ever builds up a number by making it bigger, which is obviously not the case in a non-aperiodic semigroup like the integers. So set theory can be founded by an idempotent commutative monoid and arithmetic can be founded instead by an aperiodic commutative monoid.
It is interesting to consider the atoms in a commutative aperiodic semigroup like this. Atoms are defined as in order theory, as the elements that are only greater then the identity. The atoms in set theory are the individual members or singleton sets, which can be used to build up every element through set union. The atom in arithmetic is the singular unit, one which can be used to build up every natural number through addition. These are atomically generated semigroups. Atomically generated semigroups don't need to be atomistic lattices, as seen by the fact that the natural numbers are atomically generated. It is in this context that multisets can arise as values built up from a commutative aperiodic monoid, like sets are built up, except that the combiner operation is aperiodic rather then idempotent.
Tuesday, February 12, 2019
CLR instruction classes
The classification of instructions provided by the CIL instruction set specification describes base instructions as well as object instructions, but a much better classification of the different types of CIL instructions was provided by Serge Lindin in his publications on the IL assembler. I modified the classification of CIL instructions a little bit to note some regularities of its opcodes. It can be noticed that the upper ontology of the CLR is relatively similar to the JVM because both of them have similar instruction classes at the highest level as they are both high level stack machines, but the differences between them come in the different instructions belonging to different instruction classes. Some of the differences of these instructions belonging to the six different types of instruction classes will be examined below, which can be used to make a full ontology of opcodes of the instruction set.
Stack operations:
The stack manipulation operations are relatively similar to their JVM counterparts. There are two types of stack manipulation operations, the operations that deal with stack manipulation and constant pushing. The stack manipulation operations are nop, pop, and dup. There are fewer stack manipulation operations in the CLR then in the JVM, there doesn't appear to be any swap operation and there are fewer forms of dup, but that is okay. The constant pushing operations are also very similar to the JVM, they mainly deal with pushing i4, i8, r4 and r8 values onto the stack as well as pushing strings and null.
Generalized local variables:
I describe these operations as dealing with generalized local variables because unlike the JVM the CLR has different types for arguments and local variables, which are both stored together in the JVM. In order to convert a JVM instruction to the CLR, you need to change the local variables in the arrays into argument variables and then store the remaining variables as local variables. The only other difference worth mentioning is that unlike the JVM which is a 32-bit machine, and which requires you to store 64-bit values with 2 locals, the CLR seems to be more generic. You can also get the addresses of variables with certain instructions. Along with static fields, these make up the atomic variables which along with constants can be pushed onto the stack directly with push instructions.
Transformations
The CLR has all the operations you need to deal with arithmetic, logic, conversion and related operations. One thing to note is that the operations in the CLR are generic, so you don't need to put the type of each instruction at its prefix. In place of comparison operations, the CLR has logical condition check operations, which allows you to check if two values are equal, greater, or less then one another without having to use control flow operations to do it. The only other thing worth noting is that the CLR has operations dealing with pointers like direct and indirect access operations as well as operations dealing with blocks, that do not appear in the JVM.
Vector operations
The CLR has all the vector operations you need in order to create vectors, like creating vectors, checking their length, and getting and storing the elements of them. As the values of vectors can be modified at any index, a system of generalized variable operations should include the vector operations along with static fields, instance fields, local variables, arguments, as types of variables with their own operations.
Classes and value types
All of these operations are object model instructions in the specification of the CLR instruction set. There are instructions for allocation, type checking, casting, throwing exceptions, and so on. One significant difference is that the CLR has a system of value types as well as reference types, rather then simply having only reference types and primitives. As a result, there are box and unbox operations built in at the instruction level, as well as other operations like sizeof twhich gets the size of some value type, and cpobj which copies value types. This is a significant difference, because the CLR has its own unique object model.
Control flow operations
The control flow operations are actually surprisingly similar to the JVM, you have unconditional branching instructions, unary conditional branching instructions, comparative branching instructions, and switch instructions as jump operations all of which appear in the JVM instruction set ontology. There is also the ret instruction which doesn't need to be prefixed by any type, because the operations in the CLR tend to be generic. There are also special operations for dealing with exception handling. The greatest difference appears to be in the operations that deal with method calls, like the tail prefix which allows for tail call optimization at the instruction level.
Stack operations:
The stack manipulation operations are relatively similar to their JVM counterparts. There are two types of stack manipulation operations, the operations that deal with stack manipulation and constant pushing. The stack manipulation operations are nop, pop, and dup. There are fewer stack manipulation operations in the CLR then in the JVM, there doesn't appear to be any swap operation and there are fewer forms of dup, but that is okay. The constant pushing operations are also very similar to the JVM, they mainly deal with pushing i4, i8, r4 and r8 values onto the stack as well as pushing strings and null.
Generalized local variables:
I describe these operations as dealing with generalized local variables because unlike the JVM the CLR has different types for arguments and local variables, which are both stored together in the JVM. In order to convert a JVM instruction to the CLR, you need to change the local variables in the arrays into argument variables and then store the remaining variables as local variables. The only other difference worth mentioning is that unlike the JVM which is a 32-bit machine, and which requires you to store 64-bit values with 2 locals, the CLR seems to be more generic. You can also get the addresses of variables with certain instructions. Along with static fields, these make up the atomic variables which along with constants can be pushed onto the stack directly with push instructions.
Transformations
The CLR has all the operations you need to deal with arithmetic, logic, conversion and related operations. One thing to note is that the operations in the CLR are generic, so you don't need to put the type of each instruction at its prefix. In place of comparison operations, the CLR has logical condition check operations, which allows you to check if two values are equal, greater, or less then one another without having to use control flow operations to do it. The only other thing worth noting is that the CLR has operations dealing with pointers like direct and indirect access operations as well as operations dealing with blocks, that do not appear in the JVM.
Vector operations
The CLR has all the vector operations you need in order to create vectors, like creating vectors, checking their length, and getting and storing the elements of them. As the values of vectors can be modified at any index, a system of generalized variable operations should include the vector operations along with static fields, instance fields, local variables, arguments, as types of variables with their own operations.
Classes and value types
All of these operations are object model instructions in the specification of the CLR instruction set. There are instructions for allocation, type checking, casting, throwing exceptions, and so on. One significant difference is that the CLR has a system of value types as well as reference types, rather then simply having only reference types and primitives. As a result, there are box and unbox operations built in at the instruction level, as well as other operations like sizeof twhich gets the size of some value type, and cpobj which copies value types. This is a significant difference, because the CLR has its own unique object model.
Control flow operations
The control flow operations are actually surprisingly similar to the JVM, you have unconditional branching instructions, unary conditional branching instructions, comparative branching instructions, and switch instructions as jump operations all of which appear in the JVM instruction set ontology. There is also the ret instruction which doesn't need to be prefixed by any type, because the operations in the CLR tend to be generic. There are also special operations for dealing with exception handling. The greatest difference appears to be in the operations that deal with method calls, like the tail prefix which allows for tail call optimization at the instruction level.
Saturday, February 9, 2019
Ontology of JVM instructions continued
In the previous post we classified JVM instructions, largely by considering their nature as operations in a stack machine. Two classes of operations stood out in this process : value push operations and generic generalizations of the typed operations of the JVM. The nullary push instructions (constant push instructions, local access, getstatic) correspond to the operands of a combiner. The generic instruction classes define classes of isomorphic operators that deal with different types, whose value can be determined by the compiler from operand types. These two things can be used to help build a language from the JVM instruction set.
One other detail worth considering is instruction parameters. A large percentage of the operations of the instruction set do not require instruction parameters, like the aforementioned value push instructions, the primitive transformations, the return instruction, instructions which take an array as a parameter, and various procedures among others. Others can have their instruction parameters eliminated through reflection. There are a few instructions, belonging to three different classes, that seem to be harder to eliminate. These instructions necessitate the use of extended prefix notation in any thin wrapper over the JVM.
Variable operations:
The variable operations require some variable information passed to them as an instruction parameter. The atomic variable modification operations require that the atomic variable is passed as an instruction parameter. The putfield requires that the field name as instruction parameter. Array store is distinguished from these others by the fact that it doesn't require any instruction parameters. I ultimately decided to solve this problem by introducing something like setf, which takes as an instruction parameter all the information about the generalized variable being modified.
The type operations require a type passed to them as instruction parameter. They come in two forms: the reference allocations and the reference type check operations. It is easy to see why the reference allocations are distinguished among the reference operations by the fact that they must have some type passed to them as an instruction parameter, because there isn't a reference created yet to do reflection on. With the reference type check operations, the entire operation is defined by some instruction type so they also belong to this category.
The jump operations require some label as an instruction parameter. This includes all process control instructions except for those that deal with method call and return. As the instructions are defined by jumping to a label, the label must be passed as an instruction parameter.
One other detail worth considering is instruction parameters. A large percentage of the operations of the instruction set do not require instruction parameters, like the aforementioned value push instructions, the primitive transformations, the return instruction, instructions which take an array as a parameter, and various procedures among others. Others can have their instruction parameters eliminated through reflection. There are a few instructions, belonging to three different classes, that seem to be harder to eliminate. These instructions necessitate the use of extended prefix notation in any thin wrapper over the JVM.
Variable operations:
The variable operations require some variable information passed to them as an instruction parameter. The atomic variable modification operations require that the atomic variable is passed as an instruction parameter. The putfield requires that the field name as instruction parameter. Array store is distinguished from these others by the fact that it doesn't require any instruction parameters. I ultimately decided to solve this problem by introducing something like setf, which takes as an instruction parameter all the information about the generalized variable being modified.
(def generalized-variable-modification
'#{fstore_1 lstore_3 sastore bastore dastore
dstore_3 dstore_1 istore istore_0 astore_2
fastore astore istore_2 istore_1 iinc castore
lstore_2 istore_3 dstore_2 lstore dstore_0
putstatic lstore_1 fstore_2 astore_0 dstore
astore_1 putfield fstore_0 lastore iastore
fstore lstore_0 fstore_3 aastore astore_3})
Type operations:The type operations require a type passed to them as instruction parameter. They come in two forms: the reference allocations and the reference type check operations. It is easy to see why the reference allocations are distinguished among the reference operations by the fact that they must have some type passed to them as an instruction parameter, because there isn't a reference created yet to do reflection on. With the reference type check operations, the entire operation is defined by some instruction type so they also belong to this category.
(def reference-allocation
'#{multianewarray new anewarray newarray})
(def reference-type-check
'#{instanceof checkcast})
Jump operations:The jump operations require some label as an instruction parameter. This includes all process control instructions except for those that deal with method call and return. As the instructions are defined by jumping to a label, the label must be passed as an instruction parameter.
(def jump
'#{ifeq iflt ifne ifgt ifnull ifle ifge ifnonnull
if_icmpgl if_icmple if_icmplt if_icmpne
if_acmpeq if_icmpeq if_icmpgt if_acmpne
jsr ret goto lookupswitch tableswitch})
Subscribe to:
Posts (Atom)