Most instruction sets available in stock hardware are register-based, which means that programmers dealing with them need to manually perform register allocation. This manual register allocation is generally not as good as an optimizing compiler anyways, which performs liveness analysis, graph coloring, etc to appropriately allocate variables in registers. Stack machines on the other hand, avoid this issue, and provide programmers with an easy to use high level instruction set.
Stacks are a totally ordered data structure. On the other hand, the Lisp programming language, which was named for List processing, focuses on lists which are a also a totally ordered data structure. Lists and stacks are two types of representations of a totally ordered data structure. As a consequence, stack machines belong together with a Lisp dialect which corresponds to their instruction set. A Lisp compiler for a stack machine can be constructed with ease.
Well the majority of instruction sets available in stock hardware are register based, we can at least get high-level stack based architectures with virtual machines. In particular, there is the JVM and the CLR which are both stack based. Towards this end, I created Lisp flavoured Java, which is a Lisp dialect which corresponds directly to the Java virtual machine bytecode. Atomic forms in the language correspond to the push instructions in the virtual machine. Combiners correspond to atomic instruction classes or to macros, which generate simpler forms. This demonstrates that even a stack based machine like the JVM can be made isomorphic to a Lisp dialect.
The Lisp programming language championed the notion of homoiconicity, which means that code is written as data. This considerably simplifies the parsing phase of the complier. High level stack-based architectures, like the JVM or the CLR, are perhaps equally important as they simplify code generation as well. A Lisp dialect designed for a high level stack based architecture, can be compiled seamlessly.
No comments:
Post a Comment