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.
Tuesday, November 27, 2018
Saturday, November 24, 2018
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.
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.
Saturday, November 17, 2018
On virtual machines and computer architectures
There is a wide variety of different instruction set architectures being used today, with varying degrees of complexity. In particular, there are now reduced instruction set computer architectures (RISC) that are the most barebone, having only operations for dealing with the registers and transferring data between the registers and memory. These architectures are especially common in mobile devices, because it is believed that implementing more complex instructions will place greater demands on heat and power usage. Due to the increase in mobile devices, RISC is especially common. CISC architectures tend to offer a bit more complex instructions, like instructions that combine ALU operations and loads and stores. High level computer architectures offer even more complex operations, but they are much less common. The wide variety of different architectures is a necessary consequence of, if nothing else, the vast amount of people now involved in computing at this stage in history.
Due to this wide variety of instruction set architectures, there is no reason to expect any particular complex feature will be available in any given processor. Indeed, if you selected some computer processor there is a good chance it would be a RISC computer with no complex features at all but only the bare minimum available to perform basic operations. So the utility of a virtual machine, is its portability and the extent to which it makes its complex features portable. The best way to make a program portable, or to get high level features, is to use a virtual machine.
The enormous success of the JVM is due to its portability. It was the first to really push the motto "compile once, run anywhere." Any given program for the JVM in any compiled language, can be compiled directly to JVM bytecode, there is no need for compilation to separate platforms. Given a JVM program you can can send it to someone over the network without even knowing what platform they have, simply trusting they have a compliant JVM implementation. This is genuine, true portability. We live in a networked, interconnected world, so portability certainly cannot be ignored.
The historical trend seems to be that we originally had to start with simple computers and writing assembly language by hand for any given physical machine, which is one of the impetus for the development of higher level architectures which made it easier to write assembly code for the machine. But then compilers got better, making that less necessary, leading to more reduced instruction sets. At the same time the physical high level architectures that existed, died out due to among other things a lack of portability to other more compiler-dependent reduced instruction sets. The Lisp machines died out at this time.
The next development was the virtual machine, which adapted to the reality of highly networked machines. This was best exemplified by the JVM, which first allowed people to compile a program once and run it anywhere. Its success, well other systems failed, was due to this feature. Then the next thing that happened was that specialized hardware was created for the JVM. So the only successful high level computer architectures today are specialized processors designed to run a VM more efficiently. The only way to get a successful physical machine with high level features today is to create a specialized processor for an existing virtual machine. All that is to say you need a virtual machine.
I have in mind a garbage collected stack machine for the implementation of Lisp. At least these high level features will together make the implementation of a Lisp environment more effective. Of course, these features are hardly supported in stock hardware. Fortunately, the JVM (as well as the CLR) is already a stack machine with an excellent garbage collector. Its not clear what more features one could use to implement Lisp so the JVM may already be perfect as is. Hence, the utility of Clojure.
Due to this wide variety of instruction set architectures, there is no reason to expect any particular complex feature will be available in any given processor. Indeed, if you selected some computer processor there is a good chance it would be a RISC computer with no complex features at all but only the bare minimum available to perform basic operations. So the utility of a virtual machine, is its portability and the extent to which it makes its complex features portable. The best way to make a program portable, or to get high level features, is to use a virtual machine.
The enormous success of the JVM is due to its portability. It was the first to really push the motto "compile once, run anywhere." Any given program for the JVM in any compiled language, can be compiled directly to JVM bytecode, there is no need for compilation to separate platforms. Given a JVM program you can can send it to someone over the network without even knowing what platform they have, simply trusting they have a compliant JVM implementation. This is genuine, true portability. We live in a networked, interconnected world, so portability certainly cannot be ignored.
The historical trend seems to be that we originally had to start with simple computers and writing assembly language by hand for any given physical machine, which is one of the impetus for the development of higher level architectures which made it easier to write assembly code for the machine. But then compilers got better, making that less necessary, leading to more reduced instruction sets. At the same time the physical high level architectures that existed, died out due to among other things a lack of portability to other more compiler-dependent reduced instruction sets. The Lisp machines died out at this time.
The next development was the virtual machine, which adapted to the reality of highly networked machines. This was best exemplified by the JVM, which first allowed people to compile a program once and run it anywhere. Its success, well other systems failed, was due to this feature. Then the next thing that happened was that specialized hardware was created for the JVM. So the only successful high level computer architectures today are specialized processors designed to run a VM more efficiently. The only way to get a successful physical machine with high level features today is to create a specialized processor for an existing virtual machine. All that is to say you need a virtual machine.
I have in mind a garbage collected stack machine for the implementation of Lisp. At least these high level features will together make the implementation of a Lisp environment more effective. Of course, these features are hardly supported in stock hardware. Fortunately, the JVM (as well as the CLR) is already a stack machine with an excellent garbage collector. Its not clear what more features one could use to implement Lisp so the JVM may already be perfect as is. Hence, the utility of Clojure.
Subscribe to:
Posts (Atom)