The number of available processors

In order to parallelize a function that has a well-defined product decomposition, such as the map function or one of its variants it is good that we should determine how many processors are available in a given system. This can be achieved on the JVM using the availableProcessors method of the Runtime class.

Java:

public class ProcessorCounter {
    public static void main(String[] args) {
        int processorsCount = Runtime.getRuntime().availableProcessors();
        System.out.println("The number of available processors is:" + Integer.toString(processorsCount));
    }
} 

Clojure:

(let [runtime (Runtime/getRuntime)
      processors-count (.availableProcessors runtime)]
  (println "The number of available processors is: " (str processors-count)))

Limits to parallelism:
There are two limits to parallelism:

• The number of available processors, which is determined by the available processors method.
• The overhead of threading, which states that sometimes the cost of launching parts of a computation into separate threads can outweigh the advantages of parallelism.

It doesn't make much sense to parallelize a computation if you don't have the available processors to take advantage of that. On the other hand, the overhead of threading is one reason why it isn't always good to use pmap in Clojure.

Compilation of Java operators

When implementing a language on the JVM, inevitably you are going to want to implement a similar set of basic operators as those provided by the Java language. Most of these Java operators correspond one-to-one with their JVM counterparts, so in this post I will focus only on the interesting tidbits.

Addition

The addition operator is one interesting case where Java doesn't directly correspond to its underlying bytecode. In the case when you are adding two integers it does, but for Strings it produces a different command using invokedynamic instead.

class ArithmeticOperators {
	
	// special behaviour of addition
	public static int add(int n, int m) {
		return n + m;
	}
	
	public static String add(String n, String m) {
		return n + m;
	}

}

We are then going to be looking at compiled bytecode like this:

  public static int add(int, int);
    Code:
       0: iload_0
       1: iload_1
       2: iadd
       3: ireturn

  public static java.lang.String add(java.lang.String, java.lang.String);
    Code:
       0: aload_0
       1: aload_1
       2: invokedynamic #7,  0              // InvokeDynamic #0:makeConcatWithConstants:(Ljava/lang/String;Ljava/lang/String;)Ljava/lang/String;
       7: areturn

This demonstrates that whilst addition operates normally on integers, it produces a special invokedynamic instruction on Strings using the java.lang.invoke.StringConcatFactory. This is a special change of Java 9 because before that it used StringBuilders as you would expect.

Bitwise not

There is no bitwise not operator on the JVM, so that is another case where there is a slight difference between language and bytecode.

class BitwiseOperators { 
	public static int bitwiseCompliment(int n) {
		return ~n;
	}   
}

Of course, we can get around this by using bitwise not with negative one which happens to be the largest bit set in the twos complement representation of integers.

  public static int bitwiseCompliment(int);
    Code:
       0: iload_0
       1: iconst_m1
       2: ixor
       3: ireturn

So thats pretty easy to get around using the bitwise xor operator. All the other bitwise operators like &, |, ^ all compile directly to their corresponding JVM opcodes: and, or, xor, etc. The only difference is that the static type information determines the exact opcode for the JVM type system.

Logical operators

There are no logical operators in the JVM instruction set. This is very easy to get around using conditional jump instructions like this.

class LogicalOperators {
	public static boolean logicalAnd(boolean x, boolean y) {
		return x && y;
	}
	
	public static boolean logicalOr(boolean x, boolean y) {
		return x || y;
	}
	
	public static boolean logicalNot(boolean x) {
		return !x;
	}
}

The ifeq operator in fact only checks if the top value on the stack is zero. So to implement logicalAnd we simply perform two checks on each value to see if they are zero, and in either case we return false and otherwise we return one. The logical or does the same thing but it checks for truth instead. The conditional jumps implement short-circuiting evaluation.

  public static boolean logicalAnd(boolean, boolean);
    Code:
       0: iload_0
       1: ifeq          12
       4: iload_1
       5: ifeq          12
       8: iconst_1
       9: goto          13
      12: iconst_0
      13: ireturn

  public static boolean logicalOr(boolean, boolean);
    Code:
       0: iload_0
       1: ifne          8
       4: iload_1
       5: ifeq          12
       8: iconst_1
       9: goto          13
      12: iconst_0
      13: ireturn

  public static boolean logicalNot(boolean);
    Code:
       0: iload_0
       1: ifne          8
       4: iconst_1
       5: goto          9
       8: iconst_0
       9: ireturn

So we can get around the lack of dedicated JVM opcodes for logical operators by using conditional jumps. The basic point is that the operators && and || are short circuiting so they need to be implemented using conditional jumps.

Assignment operators

The assignment operator = in the Java programming language is not as simple as you would think because it takes into account lvalues. Assignment operators can be compiled to putfield,putstatic,store, or astore depending upon the context.

import java.awt.Point;

class AssignmentOperators { 
	public static void assignment(Point[][] coll) {
		coll[0][0].x = 10;
	}
}

This modifies the value of the x field in the Point class by first getting the place in the array in which it is stored using aaload.

  public static void assignment(java.awt.Point[][]);
    Code:
       0: aload_0
       1: iconst_0
       2: aaload
       3: iconst_0
       4: aaload
       5: bipush        10
       7: putfield      #7                  // Field java/awt/Point.x:I
      10: return

So this demonstrates the lvalue support in the javac language compiler, which goes a long way to making Java as nice as it is to use. You have a unified interface which saves you from having to worry about the differences between global variables, local variables, array locations, and instance fields.

Relational operators

Instead of relational operators, the JVM has conditional jump opcodes like ifeq, ifne, ifgt, ifge, ifle, and iflt. There is a pretty straight forward translation from the relational operators to their JVM conditional jump instructions.

References:
String Concatenation with Invoke Dynamic

Sieve of Eratosthenes in Jasmin

I have hand written a number of programs in pure Java bytecode. So for example, the sieve which I implemented before in Java is something I have written out in bytecode before by hand. In particular, what you will notice about this code is the high amount of documentation and structure for JVM bytecode.

; Compute the sieve of an integer
; @param(0) the integer argument
; @local(1) the boolean array
; @local(2) the current index
; @local(3) the limit
; @local(4) the other index
.method public static sieve(I)[Z
    .limit stack 8
    .limit locals 8

    iload_0
    iconst_1
    iadd
    newarray boolean    
    astore_1

    iload_0
    i2d
    invokestatic java/lang/Math.sqrt(D)D
    d2i
    iconst_1
    iadd
    istore_3
        
    iconst_2    
    istore 4

    aload_1
    iconst_0    
    iconst_1    
    bastore

    aload_1
    iconst_1
    iconst_1
    bastore
    
    aload_1
    iconst_2
    iconst_0
    bastore

    bipush 4
    istore_2
initialization_loop:
    iload_2 
    iload_0
    if_icmpgt initialization_loop_breakpoint

    aload_1
    iload_2
    iconst_0
    bastore

    iinc 2 1
    goto initialization_loop
initialization_loop_breakpoint:
    iconst_2
    istore_2

loop:
    iload_2
    iload_3
    if_icmpge loop_breakpoint
    
    aload_1
    iload_2
    baload
    ifne inner_loop_breakpoint

    iload_2
    iload_2
    imul
    istore 4

inner_loop:
    iload 4
    iload_0
    if_icmpgt inner_loop_breakpoint

    aload_1
    iload 4
    iconst_1
    bastore    

    iload 4
    iload_2
    iadd
    istore 4
    goto inner_loop
inner_loop_breakpoint:

    iinc 2 1
    goto loop
loop_breakpoint:
    
    aload_1
    areturn
.end method

; @locals
; @param(0) the array argument
; @local(1) the count
; @local(2) the current index
; @local(3) the array argument length
.method public static falseCount([Z)I
    .limit stack 4
    .limit locals 4  

    iconst_0
    istore_1
    
    iconst_0
    istore_2
    
    aload_0
    arraylength
    istore_3
loop:
    iload_2
    iload_3
    if_icmpge loop_breakpoint

    aload_0
    iload_2
    baload
    ifeq is_false
    goto is_false_breakpoint

is_false:
    iinc 1 1
is_false_breakpoint:

    iinc 2 1
    goto loop
loop_breakpoint:
    iload_1
    ireturn
.end method

; Get the true indices of a boolean array
; @param(0) the argument array
; @local(1) the return array
; @local(2) the current index
; @local(3) the argument array length
; @local(4) the return array index
.method public static falseIndices([Z)[I
    .limit stack 4
    .limit locals 5

    aload_0
    invokestatic Sieve/falseCount([Z)I
    newarray int
    astore_1
    
    iconst_0
    istore_2
    
    aload_0
    arraylength
    istore_3
    
    iconst_0
    istore 4
loop:
    iload_2
    iload_3
    if_icmpge loop_breakpoint

    aload_0
    iload_2
    baload
    ifeq is_false
    goto is_false_breakpoint

is_false:
    aload_1
    iload 4
    iload_2
    iastore
    iinc 4 1
is_false_breakpoint:    

    iinc 2 1
    goto loop
loop_breakpoint:
    aload_1
    areturn
.end method

Adjacency matrices

In order to better demonstrate Clojure-Java interop I will create an adjacency matrix class for computations in graph theory, and then I will call its methods from Clojure. Java and Clojure can call each other because in the end their method calls both compile to the same JVM opcodes: invokevirtual, invokestatic, etc.

Graph data structures:

Basically, graph data structures typically come in three different forms, and the appropriate one can be chosen based upon performance requirements. Adjacency matrices are more efficient for dense graphs, and adjacency lists are preferably for sparse ones.

• Adjacency matrices
• Incidence matrices
• Adjacency lists

Adjacency lists are the closest to the representation of graphs in classical set theory. On the other hand, in categorical set theory and topos theory, a graph might be represented as a set-valued functor on the double arrow category. I will demonstrate an adjacency matrix data structure.

An adjacency matrix class:

This creates a mutable adjacency matrix class in Java that uses a multidimensional boolean array internally. The boolean array is then manipulated by for loops, which compile to JVM bytecode in the obvious manner.

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class AdjacencyMatrix {
    boolean[][] edges;

    public AdjacencyMatrix(boolean[][] edges) {
        this.edges = edges;
    }

    public AdjacencyMatrix(int n) {
        this.edges = new boolean[n][n];
    }

    public void setEdge(int x, int y, boolean val) {
        edges[x][y] = val;
    }

    public void swapEdge(int x, int y) {
        edges[x][y] = !edges[x][y];
    }

    public void clear() {
        for(int x = 0; x < edges.length; x++) {
            for(int y = 0; y < edges.length; y++) {
                setEdge(x,y,false);
            }
        }
    }

    public void fill() {
        for(int x = 0; x < edges.length; x++) {
            for(int y = 0; y < edges.length; y++) {
                setEdge(x,y,true);
            }
        }
    }

    public void complement() {
        for(int x = 0; x < edges.length; x++) {
            for(int y = 0; y < edges.length; y++) {
                swapEdge(x, y);
            }
        }
    }

    public void symmetricClosure() {
        for(int x = 0; x < edges.length; x++) {
            for(int y = 0; y < edges.length; y++) {
                setEdge(x, y, edges[x][y] || edges[y][x]);
            }
        }
    }

    public void symmetricComponent() {
        for(int x = 0; x < edges.length; x++) {
            for(int y = 0; y < edges.length; y++) {
                setEdge(x, y, edges[x][y] && edges[y][x]);
            }
        }
    }

    public void randomize() {
        var r = new Random();
        for(int x = 0; x < edges.length; x++) {
            for(int y = 0; y < edges.length; y++) {
                setEdge(x, y, (r.nextInt(2) == 1));
            }
        }
    }

    public void transpose() {
        // we need to duplicate the old matrix so that we
        // don't get stopped out by side effects.
        var oldMatrix = new boolean[edges.length][edges.length];
        for(int i = 0; i < edges.length; i++) {
            oldMatrix[i] = edges[i].clone();
        }

        for(int x = 0; x < edges.length; x++) {
            for(int y = 0; y < edges.length; y++) {
                edges[x][y] = oldMatrix[y][x];
            }
        }
    }

    public int order() {
        return edges.length;
    }

    public boolean containsEdge(int x, int y) {
        return edges[x][y];
    }

    public int size() {
        int rval = 0;
        for(int x = 0; x < edges.length; x++) {
            for(int y = 0; y < edges.length; y++) {
                if(edges[x][y]) {
                    rval++;
                }
            }
        }
        return rval;
    }

    public String toString() {
        return Arrays.deepToString(edges);
    }

    public byte[] getBytes() {
        var l = edges.length;
        var rval = new byte[(int) Math.pow(l,2)];

        for(int x = 0; x < edges.length; x++) {
            for(int y = 0; y < edges.length; y++) {
                rval[x*l + y] = (byte) ((this.edges[x][y]) ? 1 : 0);
            }
        }

        return rval;
    }

    public static AdjacencyMatrix fromBytes(byte[] coll) {
        var l = (int) Math.sqrt(coll.length);
        var edges = new boolean[l][l];

        for(int x = 0; x < l; x++) {
            for(int y = 0; y < l; y++) {
                edges[x][y] = (coll[x*l + y] == 1);
            }
        }

        return new AdjacencyMatrix(edges);
    }

    public Set edgeSet() {
        Set rval = new HashSet();

        for(int x = 0; x < edges.length; x++) {
            for(int y = 0; y < edges.length; y++) {
                if(edges[x][y]) {
                    rval.add(new int[]{x,y});
                }
            }
        }

        return rval;
    }

}

This is notable because it is a mutable class which means it would be hard to recreate exactly in Clojure, which tries to use immutable and persistent data structures for everything. It might pay off to have both an adjacency matrix value and a separate mutable matrix class, but we will leave that aside for now. I will now demonstrate a little bit about how to use this class from Clojure.

Managing adjacency matrices from Clojure

Creating an adjacency matrix
The key to create an adjacency matrix now is to use the make-array function to create a boolean array in order to call the constructor. A new AdjacencyMatrix is created using the new opcode, and then initialized by a call to invokespecial with the appropriate constructor method handle.

(def arr (make-array Boolean/TYPE 4 4))

We can then manipulate the boolean array using the Clojure Java interop methods aget and aset which correspond to the aload and astore instructions of the Java virtual machine.

(aset (aget arr 0) 0 true) 
(aset (aget arr 2) 2 true)

Now that we have sufficiently manipulated the data of the adjacency matrix we can pass it to the constructor, in order to initialize an instance of the AdjacencyMatrix class.

(def ^AdjacencyMatrix adjacency-matrix
    (AdjacencyMatrix. arr))

The Adjacency matrix constructor is actually overloaded, so assuming that you don't want to do any operations on the input multidimensional boolean array before passing it to the constructor, you can just call the version that uses an integer as its main parameter.

(def ^AdjacencyMatrix adjacency-matrix
    (AdjacencyMatrix. 4))

Type hinting the adjacency matrix after you created it ensures that the Clojure code will typically compile to an invokevirtual call with the appropriate method signature, rather than going through reflection.

Manipulating the adjacency matrix
I have now prepared a number of Java methods that can be called to manipulate an adjacency matrix instance from Clojure. For example, clear sets all entries to false.

(.clear adjacency-matrix)

On the other hand, fill does the opposite and it sets all the entries in the adjacency matrix to true. In each case, we can call a Java method using the same sort of dot method call syntax as Java.

(.fill adjacency-matrix)

The fill operation is equivalent to using clear combined with complement which switches each boolean entry in the adjacency matrix to its opposite value.

(doto adjacency-matrix
    (.clear)
    (.complement))

A final method I created that you can call is transpose. It was actually the hardest to implement because of the nature of its side effects.

(.transpose adjacency-matrix)

Of course, many more methods could be added and are not included here but this demonstates the basic principles of Clojure Java interop.

Storing a matrix to a file:
One interesting thing I added in the Java class is the ability to take the adjacency matrix and convert it to a byte array. The whole point of this is so that I can use it to store an adjacency matrix to a file. Its not an elaborate serialisation method or anything, but it works.

(import java.io.File)
(import java.nio.Files)

(def current-file 
    (File. (str (System/getProperty "user.home") "/output.bin")))

(Files/write (.toPath current-file) (.getBytes adjacency-matrix))

In order to then get back the data of the adjacency matrix later, all we need to do is call java.nio.Files/readAllBytes and then use the fromBytes method provided in the Java class provided earlier.

(def adjacency-matrix
    (AdjacencyMatrix/fromBytes (Files/readAllBytes current-file)))

That should be sufficient for now to demonstrate this basic adjacency matrix. I envision creating thousands of Java classes for various objects of mathematics - like Young diagrams, transformationts, permutations, etc for use in Clojure.

Clojure java interop

The Java virtual machine is a general building material for programs, not necessarily tied to any language or programming paradigm. All that matters is that you can produce JVM bytecode. Since it is all the same in the end, it is worth asking what advantages the Java language has for generating JVM bytecode.

• Support for variable names and distinguished argument lists.
• Type deduction in opcode generation. In particular, you don't have to distinguish between iadd, ladd, fadd, and dadd when adding two numbers. Likewise, for the other arithmetic operations, loading and storing values in arrays, returning values, casting, etc. By the same token, you don't have to fully specify method signatures.
• The import statement saves you from always having to fully specify java class names. There is no corresponding import opcode for the Java virtual machine, so this is purely a Java language feature.
• The Java language doesn't force you to have to distinguish between different opcodes when loading constants. The Java virtual machine supports the different opcodes to make more compact bytecode. Any high level language (including the ASM bytecode library) should handle this automatically.
• Java provides control flow constructs in the place of goto and conditional jumps. Part of this is the uniform condition system, which prevents you from having to determine which conditional jump opcode to use.
• A uniform call syntax so you don't have to distinguish between invokestatic, invokevirtual, invokeinterface, and invokespecial.
• Built in support for l-values and generalized place forms, so you can use a general assignment form on local variables, array indices, and static and instance fields. You can even set values in multidimensional arrays and the Java compiler will produce the correct combination of opcodes for you for that.
• Last but not least, the Java language automatically handles arguments on the stack for you. This can be useful for example when dealing with mathematical expressions.

The Java language does a lot when you put it like that, but this by no means that Java virtual machine bytecode is hard to use. The Java virtual machine is still a high level architecture which is easier to use than any C-machine. Hopefully this explains why you might use the Java language to generate JVM bytecode, but it is all the same if you want to use something else or even write you or own compiler as I have.

Setting up a mixed project:
So in order to set up a mixed Java and Clojure project I suggest using Intellij IDEA. Intellij is the only Java focused IDE that also has good support for Clojure. Then you just need to create separate Java and Clojure folders and configure Leiningen to specify your Clojure folder in :source-paths and your Java folder in :java-source-paths.

Creating a Java class:
In order to create a first example of Java and Clojure interop, I have chosen the special case of defining a prime number sieve. Obviously, you could easily do this in Clojure, but perhaps some mathematical functionality should be written in Java so that they are more performant.

import java.util.BitSet;

public class NumberUtilities {

    public static int[] sieve(int n) {

        BitSet primes = new BitSet(n+1);
        primes.flip(2, n+1);

        for(int p = 2; p*p <= n; p++) {
            if(primes.get(p)) {
                for(int i = p*p; i <= n; i += p) {
                    primes.set(i, false);
                }
            }
        }

        return primes.stream().toArray();
    }

}

I mentioned that the Java language is just a tool for generating Java virtual machine bytecodes. Its kind of like an M-expression syntax for the JVM, and Lisp Flavoured Java is an S-expression syntax. Clojure is a different beast entirely from either of them. For the purposes of this demonstration, lets examine the output bytecode as it appears with Jasmin.

.class public NumberUtilities

.method public static sieve(I)[I
    .limit stack 4
    .limit locals 4

; initialize the bit set
    new java/util/BitSet
    dup
    iload_0
    iconst_1
    iadd
    invokespecial java/util/BitSet.(I)V

; flip the possible primes to true
    astore_1
    aload_1
    iconst_2
    iload_0
    iconst_1
    iadd
    invokevirtual java/util/BitSet.flip(II)V

; initial the first prime to two
    iconst_2
    istore_2

; start a loop in order to do the sieve on the main bit set
loop:
    iload_2
    iload_2
    imul
    iload_0
    if_icmpgt loop_breakpoint

; ensure that this number is a prime before starting the inner loop
    aload_1
    iload_2
    invokevirtual java/util/Bitset.get(I)Z
    ifeq inner_loop_breakpoint

; initialize the current multiple to the first non flipped index
    iload_2
    iload_2
    imul
    istore_3

; flip all multiples of the current prime to false
inner_loop:
    iload_3
    iload_0
    if_icmpgt inner_loop_breakpoint

; set the current index to false
    aload_0
    iload_3
    iconst_0
    invokevirtual java/util/BitSet.set(IZ)V

    iload_3
    iload_2
    iadd
    istore_3
    goto inner_loop

inner_loop_breakpoint:

    iinc 2,1
    goto loop
loop_breakpoint:

    ; convert the bitset into an int array containing all true indices and return
    aload_1
    invokevirtual java/util/BitSet.stream()Ljava/util/stream/IntStream;
    invokeinterface java/util/stream/IntStream.toArray()[I
    areturn
.end method

The advantages of the Java language can clearly be seen by comparing the Java language code to the Java virtual machine bytecode. Whenever someone says that Java is verbose, I just remember how much typing it saves from having to write JVM bytecode in hand, which I have a done a lot. Too much.

A notable aspect of this is how the compiler structures the output of for loops. There is quite a lot to unpack when using a for loop, and its logic appears all over the place in the compiled output. That is why some parts of the for loop appear before the loop starts, at the start of the loop, and at the end. Once you unpack all of that it is fairly easy to see how Java code corresponds to bytecode. In that sense, Java is one of the easier languages to understand in terms of its compiler output.

Calling Java functions from Clojure
All the countless hours spent reading the documentation of the Java virtual machine, the Java language, and the thousands of classes in the Java standard library are finally rewarded by using Clojure, which has seamless Java interop.

(prn (seq (NumberUtilities/sieve 1000)))

The execution of the sieve function written in Java produces the first prime numbers up to a thousand, which confirms our memory of the smallest primes.

(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 
71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 
149 151 157 163 167 173 179 181 191 193 197 199 211 223 
227 229 233 239 241 251 257 263 269 271 277 281 283 293 
307 311 313 317 331 337 347 349 353 359 367 373 379 383 
389 397 401 409 419 421 431 433 439 443 449 457 461 463 
467 479 487 491 499 503 509 521 523 541 547 557 563 569 
571 577 587 593 599 601 607 613 617 619 631 641 643 647 
653 659 661 673 677 683 691 701 709 719 727 733 739 743 
751 757 761 769 773 787 797 809 811 821 823 827 829 839 
853 857 859 863 877 881 883 887 907 911 919 929 937 941 
947 953 967 971 977 983 991 997)

Clojure is able to call the Java sieve function because they both speak the same basic language: Java virtual machine bytecode. We saw the JVM output of the Java class. The corresponding Clojure class produces the same sort of opcodes, starting with a call with invokestatic to call the sieve function. The only difference is that Clojure might have to use reflection if not enough type information is provided to it.

In this case that isn't necessary because NumberUtilities doesn't use method overloading, but in general the most important performance benefit you can add to your Clojure code is to use type hints so you don't have to use reflection to determine method signatures at runtime. Finally, after calling sieve we use seq in order to print it, because sequences produce better output when converted to Strings. A more Java like solution would be to use java.util.Arrays/toString.

The Java language and Clojure perfectly complement each other, because Clojure isn't just another copy of Java. Java is static, imperative, heteroiconic, etc while Clojure is dynamic, functional, and homoiconic. The fact that two languages that are so different from one another can come together is the ultimate testament to the power of the Java virtual machine.

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.

(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})

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.

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.