Abstract machine mode
(Published in "programmer" 2003 No. 1)
Written / Julio García-Martín Miguel SUTIL-MARTíN
Universidad Politécnica de Madrid [1]
Translation / Marvida
Summary
Because the difference between modern advanced programming languages and existing hardware, it is often necessary to introduce intermediate languages and build an abstract machine on topmost hardware. This paper describes the abstract machine, a structural pattern that captures the essential characteristics of the abstraction; these characteristics give the definition of the abstraction. This mode describes the static characteristics and dynamic characteristics of the abstraction as separate components and also considers the semantics of the instruction set and these instructions, and other important components of this mode.
intention
Define a universal template for the design of the abstract machine. This mode captures the essential characteristics (other, data zones, programs, instructions, etc.), and separates their mutually separated, loosely coupled components into the structural mode. In addition, this paper also provides a collaborative structure of each component of an abstract machine.
Alias
Virtual Machine, Abstract State Machine.
motivation
Today, Java is a fashionable discourse in computer science. Although Java is an object-oriented language for distributed and GUI applications, it is increasing new very useful programming features and tools almost every day. As a fact, in Java's success, the use of virtual machine technology has extremely significant [2]. As is well known, Java Virtual Machine, JVM) is software-based abstraits that work on different microprocessor machines (that is, independent of hardware). JVM designers must comply with JVM specification, perform the necessary processing, and connect the JVM virtual environment bridge to the specific operating system and microprocessor. This "bridge" after the virtual environment allows software developers "Write Once, Run Anywhere" (Write Once, Run Anywhere) (Write Once) [1], because no matter what the underlying microprocessor is, JVM must be based on JVM standard specification Work in the same way.
Because the difference between modern advanced programming languages and existing hardware, it is often necessary to introduce intermediate languages and build an abstract machine on topmost hardware. However, in many cases, differences are so large that we are difficult to see how the source language is associated with intermediate languages, or it is difficult to see how the intermediate language is associated with hardware. Unfortunately, in many cases, the abstract machine is only represented as a collection of registers, memory and machine instruction sets, only very few or no correspondence with the source language.
Figure 1 Example of abstract machine: Abstract-Wam [3]
The goal of this work is dual: a) First, for the inventive method of the design machine; second, b) use this methodology to describe a mode-based architecture for designing the programming language compiler. The use of such implementation techniques (i.e., the use of abstract machines) allows the compilation task to plan a progressive optimization process, so that high performance characteristics can be obtained step by step according to the relationship between the intermediate abstraction. This process also maintains the identity between an abstract machine and the next abstract machine. Each compilation step explicitly generates some new features and changes, and increases it to the global compilation process (see Figure 2).
* Can also be "definition"
Figure 2 Compiling the compilation process by the virtual machine progressive optimization
This process gives a method of constructing more abstract and system constructor. In addition, it also promotes the understanding of the compilation process and simplifies the prior design optimization and multiplexing tasks. An (prototype) compiler or less likely to be automatically exported as an marginal effect of an abstract machine design. applicability
The abstract machine mode is suitable for any of the following:
l When we want to define an abstract machine. This mode provides a universal skeleton to prepare advanced specifications, allowing programmers to focus more on the components of the definition of abstract machines, rather than worrying their merging (this can be "free"). The specification written can be formally or non-form.
l When we want to compile the language by using abstract machine technology. The abstraction provides an appropriate framework to describe the compilation process (that is, prototype development) through the progressive optimization of the intermediate language. In such a process, the relationship between the intermediate languages (that is, the abstraction) defines the entire compilation process.
l When we want to define the compiler obtained by applying the abstract machine. This is the result of combining the above two cases.
l When we want to test different semantics of the same instruction. You can define different semantics for the same instruction, and similarly, you can also achieve different implementations of the same semantic.
l When we want to test different instruction sets of the same abstract machine. You can define different instructions for the same aberrator. Moreover, progressive optimization of the compilation process means that each intermediate abstraction defines a more optimized instruction set than the instruction set managed by the previous abstraction.
l When we want to simulate our procedure. The program simulation enforces the visualization tool and the debugging tool into the process. It is easy to treat these view components and other features as participants in abstract machine mode. In particular, execution code related to visualization or debug can be defined by enhanced instructions of the abstraction.
structure
The structure of the abstract machine mode is shown in Figure 3.
Figure 3 Abstract machine mode (structure)
Participant
The abstraction can be abstractly defined as a combination of two parts: (i) static part, composed of components associated with state (state), (ii) dynamic part, determines elements associated with the behavior of the abstraction. The abstract machine mode will organize and locate components of its structure.
The status of the abstract machine consists of the following components:
1. Abstract-Machine Factory: It is an operational declaration interface for creating Abstract DataArea and Abstract Program.
2. Abstract DataArea: It declares the interface for the data area object type to configure the abstraction. It declares two abstract operations:
l init operation to determine the initial configuration of the data area, and
l STOP operation, determine if the execution of the abstract machine has ended. If the end condition does not depend on the data area, the STOP operation returns True.
3. Concrete DataArea: It defines the specific data area object. The specific data area can be a simple object or complex object structure (object container). This component must provide an implementation of the Abstract DataArea interface.
4. Abstract Program: It declares the universal interface for the assembler. It defines a series of instructions (Abstract INSTRUCTION) and an Instruction Set. In addition, it also declares four abstract operations:
l init operations to determine the initial configuration of the assembler.
l STOP operations to determine if the abstract machine reaches its final phase. If the termination condition does not depend on any program configuration, the STOP operation returns True.
l LoadProg operation is responsible for constructing assembly instructions for abstract machine programs. This operation reads text representation from the input stream and translates each instruction into a Concrete INSTRUCTION object.
l CurrentInst operation Returns the instruction to be executed by the abstraction.
5. Concrete Program: It defines a specific program object. It is defined as a collection of specific instructions and some program counters. It must be implemented in Init, STOP, and CurrentInst operations defined in Abstract Program.
6. Abstract INSTRUCTION SET: It declares a universal interface to represent a set of abstract instructions.
7. Concrete INSTRUCTION SET: It defines a set of objects through the Concrete Instruction object. The specific instruction set is associated with the specific data area and the specific program. It must implement the operations of Abstract Instruction Set.
8. Abstract INSTRUCTION: It declares that the general interface used to represent the abstract machine instruction.
9. Concrete INSTRUCTION: It defines a specific instruction object. The specific instructions are directly linked to the specific data area and specific procedures. It must implement the operations of Abstract Instruction.
In the aspect of the abstract machine, it relies on some operations that work on the static component. These operations are part of the definition of abstract machine status, which is responsible for describing different states arriving in the abstraction during the execution process. These operations are as follows:
1. Abstract-Machine State: As a result of compiling Concrete INSTRUCTION, it coordinates the interaction between DataArea and Program. Thus, it has a role similar to the Mediator mode [4]. Abstract machine status can reach three different phases (INITIAL, EXECUTING, and FINAL), they are connected to the following:
L init operation, it is used to determine the initial state of the abstraction when executed.
l STOP operations to determine whether to execute the final state of the abstract machine.
l Transition operations to complete the execution of the abstract machine program. It is defined as a WHILE loop control structure; each round of cycles execute instruction points to the program counter (CURRENTINST). Transition operations are executed from the initial abstract machine configuration status and continue until the final stage is reached.
2. Abstract & Concrete INSTRUCTION: Abstract and specific instructions:
L Si operation (semantic function) determines how the abstract machine evolves with the execution of the instruction. Each instruction defines its own Si semantic function and determines how the abstract machine changes (change the data area and / or program). In order to complete these changes, each directive must be able to access components on the current state. This is done by a copy-reference (copy reference) of the abstract machine state; the copy-reference is passed as a parameter to the instruction.
cooperation
The abstract machine may reach three different phases during execution: Initialization, Transition, and Ending. Figure 4, 5, 6 taught these stages. Stage 1: Initialization
Figure 4 Initialization phase (collaboration)
The abstract machine is initialized at this stage. Result DataArea and Program will be initialized. The initialization of Program is done by the init operation and involves setting their components to the initial value (that is, the program counter, instruction array, etc.). The LoadProgram operation of the assembler is responsible for assembler loading (i.e., text representing the text representation of the assembly instruction from the InputStream) is executed. On the other hand, the Init operation is initialized to the components (other, data registers or control registers, etc.) in DataArea.
Phase 2: Transition
Figure 5 Migration Stage (Collaboration)
As mentioned earlier, the Transition operation completes the abstract machine. Thus, the Transition operation (via the CurrentInst operation) requests the instruction to be executed from the program, which is directed by the program counter. The execution of each directive constitutes the execution of the abstraction until the end state is reached. Each abstract machine instruction is responsible for defining its own semantics. Thus, each instruction provides Si operation - depends on whether the instruction changes the program and / data area - it performs changes to the abstract machine (that is, the program and / or data area). Changing the completed order is only determined by the semantics of the instruction.
Stage 3: Ending
Figure 6 Final stage (collaboration)
The abstract machine reaches the end state when any of its two components (or both) reaches the end state (for example, a specific stop command, data area overflow, etc.) arrives at the end phase. This state is evaluated to DataArea and Program's STOP operation and combine their results.
effect
The abstract machine mode shows the following superiority:
l Provides a framework for developing an abstract machine. This mode defines the advanced and flexible design used to develop abstract machines.
l Provides a framework for developing a compiler with progressive optimization by an abstract machine. The optimization step during the compilation process can be expressed according to the structure of the abstract machine or the optimization of its components.
l Coupling the relationship between the participants of the abstraction. Abstract Machine Factory helps Abstract Machine State and specific data area and program implementation. Abstract Machine State operates them through an abstract interface of each instance. On the side of Abstract Instruction Set, it is used as an abstract factory for executive set by the program.
l Provides a framework for testing different instruction sets. This mode makes the transform instruction set easier, allowing the data area and the program to maintain independently of any particular instruction set. To change the specific instruction set, just reconfigure the abstraction.
l Provides a framework for testing different instruction semantics or implementation of the same machine instruction. Because the semantic package is in the instruction (Si operation), we can redefine them without affecting the data area and / or programs.
l Provides a higher level of abstract machine multiplexing. In most cases, all or part of the abstract machine can be highly reused in new development.
l Advocate a methodology for the most systematic abstract machine development. By separating the participants of the abstraction in each component (that is, the data area, the program, the instruction set and the instruction semantic), we introduce some design constraints, forced users to follow systematic methods. The abstract machine mode also shows the following:
l Generates inefficient implementation.
l The communication overhead is triggered between Abstract-Machine State and Abstract Instruction.
achieve
Consider the following implementation issues:
1. Create specific Data Area and Program. Abstract-Machine Factory is only a interface for creating a Data Area and a Program object. Follow the similar prompt given for Abstract-Factory mode [4].
2. Concrete Data Area can have complex object components. Follow the same implementation problem in composite mode [4].
3. Define Abstract Data Area, Abstract Program, Abstract INSTRACT Program, and Abstract INSTRUCT SET as an interface. For example, follow Java conventions:
Public Interface AbstractInStructionTRUCTION
{
Public void si (AbstractMachinestate State);
Public String Name ();
Public int Numarguments ();
Public String Tostring ();
Public void process (string args [])
}
Public Interface AbstractInStructionSTRUCTIONSET
{...}
Public Interface AbstractProgram
{
Public Abstractinstruction CurrentInst ();
Public void init ();
Public boolean stop ();
Public void loadingprogram (stream assemblercode);
}
Public Interface AbstractDataArea
{
Public void init ();
Public boolean stop ();
}
The Abstract Instruction interface provides two ways to determine information related to the instructions (that is, Name, Numarguments); method Si declares the instruction semantics; information. The SI method will receive the reference to Abstract Machine State as a parameter.
The Abstract Instruction Set Define the command set that can be managed by the program. The component can be a directory name, an enumeration set, a package, module, and so on ... The operation defined in the Abstract Instruction Set interface is only concerned about the selected representation.
Abstract Program defines the general interface of the assembler. The CurrentInst operation is used to access the instructions to be executed. In addition, the LoadProgram operation is responsible for building the Concrete Instruction object that will be joined in the program.
4. ABSTRACTDATAAREA, AbstractProgram, and AbstractInStruction as template parameters. In class C syntax, as shown below:
Class AbstractInStructiontruction
{..}
Template
Class AbstractProgram
{..}
Class AbstractDataArea
{..}
Template
Class AbstractMachinestate Class AbstractProgram {..} 5. omit the Abstract-Machine State class. It is similar to the Mediator mode [4]. 6. Primitive Operation. Some of the operations defined in Abstract DataArea, Abstract Program, and Abstract Instrute are original. Thus, they must be redefined. For example, they can be declared as a pure virtual function (C method), or part of the interface (Java method). Operation in Abstract-Machine State Init, Transition, and STOP cannot be redefined. Sample code The following example code gives the Java implementation of certain parts of the abstract machine mode. 1. First, we define each interface corresponding to Abstract DataArea, Abstract Program, and Abstract Instruction (see Implementation). 2. An abstract class (in C or Java javel) means an optional implementation of Abstract Program. In this case, the abstract class can provide some additional functions (eg, program counters P and instruction sets). Import AbstractInStruction; Import abstractinstructionset; Public Abstract Class AbstractProgram { Public int P; Private Vector Program; // A Container of AbstractInStruction PRIVATE ABSTRACTICTINSTRUCTIONSET INSTSET AbstractProgram (Abstract InstructionSet Insts) { This.instSet = INSTSET; } Public void init () { P = << init program address >>; Program = new vector (); } Public void loadingprogram (stream assemblercode) { << Load instructions from the assembler code >> } Public Abstractinstruction CurrentInst () { Return Program.get (P); } Public void next () { P ; } Abstract public boilean stop (); } 3. Realization of Abstract Machine Factory: Import AbstractDataArea; Import Abstractprogram; Public Interface AbstractMachpenFactory { Public AbstractDataArea CreateDataArea (); Public Abstractprogram CreateProgram (); } 4. Implementation of Abstract Machine State: Import AbstractDataArea; import abstractprogram; Import Abstractinstructiontruction Public Class AbstractMACHINESTATE { Private AbstractDataArea DA; Private abstractprogram prog; Public AbstractMachineState (AbstractMachineFactory Factory) { PROG = Factory.createProgram (); Da = factory.createdataArea (); } Public AbstractDataArea DataArea () { Return DA; } Public AbstractProgram Program () { Return PROG; } Public void init (stream s) { da.init (); PROG.INIT (); PROG.LOADPROGRAM (s); } Public boolean stop () { Return prog.stop () && da.stop (); } Public void transition () { While (! stop ()) { PROG.CURRENTINST (). Si (this); } } } 5. To create a specific Abstract Machine State (for example, the WAM abstract machine described in the Motivation section), you can use a series of instructions: Import AbstractStateMachine; Import wam_factory; Import Wam_instructionSet; Class Wam_Client { Static Public Void Main (String Args []) THROWS IOEXCEPTION { FileInputStream Targetcode = New FileInputStream (arg [0]); Wam_factory factory = new wam_factory; AbstractMachineState Machine = New AbstractMachinestate (Factory); Machine.init (targetcode); Machine.Transition (); } } 6. As shown in Figure 1, the WAM State data area is defined as a collection of data components (that is, Orstack, HEAP, and Registers). Import orstack; Import HEAP; Import Registers Public Class Wam_DataArea Implements AbstractDataArea { Public Orstack Orstack; Public Heap HEAP; Public Registers Regs; Public wam_dataarea () { Orstack = new ibo (); HEAP = new heap (); Regs = new registers (); } Public void init () { Orstack.init (); HEAP.INIT (); Regs.init (); } Public boolean stop () { Return True; } } 7. On the side of Wam Program, it is defined as an instance of Abstract Program for the specific Wam Instruction set. Moreover, Wam Program extends Abstract Program with a new program counter (CP). Public Class Wam_Program Extends AbstractProgram { Public int CP; file: // Wam_program (AbstractInStructionset Insts) { Super (Instset); } Public void init () { P = 0; CP = 0; } Public int consult_cp () { Return CP; } Public boolean stop () { Return CurrentInst (). Name (). Equals ("stop"); } } 8. Finally, we describe examples of some instructions in the WAM instruction. Let us imagine how each of the following is changed by changing the Wam State (that is, Wam DataArea and / or Wam Program) (how the WAM abstraction evolves). a) The following code describes the Java implementation of the WAM command "Allocate N". The execution of the instruction (its semantics) assigns N unused variables in the OR-STACK of the WAM abstraction. Then, the instruction moves the program counter to the next instruction (call the next next to the WAM Program). Public Class Allocate Implements AbstractInStruction { Private int numvars = 0; Allocate () {} Public String Name () { Return "allocate"; } Public int NUMARGUMENTS () { Return 1; } Public String Tostring () { Return Name () " Numvars; } Public void si (AbstractMachinestate State) { Wam_dataarea wam_da = (wam_dataarea) state.dataarea (); Wam_program wam_prog = (wam_program) state.program (); // Implementation of Allocate Semantics Wam_da.orstack.push (numvars); Wam_prog.next (); } Public void process (string args []) { // proces the text representation of the instruction // arguments INTO An Int Value. Numvars = INTEGER.VALUEOF (args [0]). INTVALUE (); } } b) The following code description WAM command "Call Public Class Call Implements AbstractInStruction { Private Int PROGADDR; ... Public void si (AbstractMachinestate State) { Wam_dataarea wam_da = (wam_dataarea) state.dataarea (); Wam_program wam_prog = (wam_program) state.program (); //Mplementation of call semantics Wam_da.orStack.set_cp (Wam_Prog.cp); Wam_prog.cp = p; Wam_prog.p = pRogAddr; } ... } c) Now I envisage a new version of the CALL instruction that supports visualization tools. We demonstrate a new ViewCall class from the previous class and redefine Si operations as follows: Public Class ViewCall Extends Call { Public void si (AbstractMachinestate State) { Super.si (state); // Execute The Call Semantics State.notify (); // notify the change and redraw } } Use The patterns described herein have been used to form and implement a abstract compiler in the ProLog language [2]. As the result of this work, we have obtained a multi-stage compilation method based on abstract machine technology. In addition, we have found that the abstract machine mode is very suitable for easily contain visual tools and commissioning mechanisms and tools in the abstract machine in an abstract machine in a non-invasive manner [3]. Related mode The work introduced in [5] studied the definition of mode language used to build a virtual machine. Unlike [5], our recommendations are more focused on providing a higher level design architecture, rather than so much description of the low level of the virtual machine. The abstract machine mode combines some modes introduced in [4]: l ABSTRACT MACHINE State, a variant of Mediator mode, which belongs to this situation. l Abstract Machine Factory and Abstract Instruction Set belong to the Abstract Factory mode, l On the other hand, there is a hidden Strategy mode behind the Si operation (in Abstract Instruction), and l Finally, in the Abstract Machine State in the Abstract Machine State is a significant instance of the Template Method mode. references [1] Arnold & gosling. The Java Programming Language. Addison-Wesley, Reading, Massachusetts, 1996. [2] García J. & Moreno J.J. Visualization as Debugging: Understanding / Debugging the WAM, Automated and Algoritmic Debugging (AADEBUG'93), Lecture Notes in Computer Science (LNCS 749), Springer-Verlag, 1993. [3] García J. & Moreno J.J. A Formal Definition of An Abstract Prolog Compiler, Amast'93. Workshops In Computer Science, LeCTure Notes in Artificial Intelligence (LNAI), Springer-Verlag, 1993. [4] Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides. Design Patterns. Elements of reusable object-oriented software. Addison-Wesley, Reading, MA, 1995. [5] Jacobsen, EE & Nowack, P. A Pattern Language . 2th European conf. pattern languages of programming, irs (germany), July 1996. [6] READE, C, Elements of Functional Programming, Addison-Wesley, 1989. [7] Warren, D. H.d, An Abstract Prolog Instruction set. Tec. Note 309, Sri International, Menlo Park, California, October 1983. [1] LSIIS Department, Facultad de Informática, Campus de Montegancedo, Boadilla Del Monte, 28660 Madrid, Spain. Email: juliog@fi.upm.es [2] In the past, in Java's prosperous prosperity ago, many of the work of Declarative Programming had pointed out that an abstract machine is a successful implementation of a common implementation technology. An example like ProLog [7] or SML [6] is a good example of high performance programming languages by abstract machines. Today, express use "virtual machine" is very common.
