Inventory of research, extension, and higher education conducted by the U.S. Department of Agriculture FY 81.
Inventory of research, extension, and higher education conducted by the U.S. Department of Agriculture FY 81.
United States. Dept. of Agriculture. Science and Education. Policy Analysis and Coordination Staff. [Corporate Author]
Access the full text:
NOT AVAILABLE
Inventory of research, extension, and higher education conducted by the U.S. Department of Agriculture FY 81.
United States. Dept. of Agriculture. Science and Education. Policy Analysis and Coordination Staff.
2012/OV/OV2012_9.rdf
Journal Article
In AGRIS since
Congratulations
Publications saved
Procurement
Governing Bodies
Country Offices
Follow us on
Download our App一道工程力学题。（单辉祖，谢传锋合编）4-21_工程力学吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：6,499贴子：
一道工程力学题。（单辉祖，谢传锋合编）4-21收藏
题4-21图所示构架由AG,BH,CF,CG,和FH五根杆组成。各杆在C,D,E,F,H处彼此用铰链连接。在A处作用一水平力F=2KN。各杆重量不计，是计算作用在横杆CF上四点C,D,E,F上的力。
登录百度帐号推荐应用Object-oriented, logic, and database programming tool with garbage collection
United States Patent 4989132
A programming tool is provided which integrates an object-oriented programming language system, a logic programming language system, and a database in such a manner that logic terms can be treated as objects in the object-oriented programming language system, objects can be treated as logic terms in the logic programming language system, and logic terms and objects are stored in the database in a common data structure format. Automatic management of the database is provided which is transparent to the user.
Inventors:
Mellender, Fredric H. (Rochester, NY)
Straw, Andrew G. (Fairport, NY)
Riegel, Stephen E. (Pittsford, NY)
Application Number:
Publication Date:
01/29/1991
Filing Date:
10/24/1988
Export Citation:
Eastman Kodak Company (Rochester, NY)
Primary Class:
Other Classes:
707/999.202,
707/999.206,
711/E12.009,
714/E11.21,
International Classes:
G06F9/06; G06F9/44; G06F9/45; G06F11/36; G06F12/00; G06F12/02; G06F17/30; (IPC1-7): G06F7/00
Field of Search:
364/513, 364/200
View Patent Images:
&&&&&&PDF help
US Patent References:
4736320Bristol364/3004635208Coleby et al.364/4914622545Atkinson340/7474570217Allen et al.364/1884546435Herbert et al.364/3003622762Dyer et al.235/150
Other References:
Pundy et al, Integrating an Object Server with Other Worlds, ACM Transactions, Jan. 1987.
Primary Examiner:
Macdonald, Allen R.
Attorney, Agent or Firm:
Close, Thomas H.
1. A program tool, comprising
a. a workstation having an operator interface, a mass memory, a CPU,
b. an object oriented programming language system including,
(1) an object oriented programming language, and
(2) object oriented language compiler means for translating source code written in the object oriented programming language into objects
c. a logic programming language system, having components representing terms, clauses, predicates, atoms, and variables, including,
(1) a logic programming language, and
(2) logic compiler means for translating source code written in the logic programming l
d. a database residing in said mass memory, for storing objects and components of a logic programming language as objects in a common data structure format, applications data, and applications stored as compi
e. object database management for representing objects and components of a logic program in said common data structure format as objects, and responsive to calls for retrieving and storing such objects in said database, and for automatically deleting objects from said data base when
f. interpreter means for executing said interpreter code and generating calls to said datab and
g. logic subsystem means for solving logic queries, said logic subsystem means treating any object as a term in the logic programming language.
2. The programming tool claimed in claim 1, wherein said object oriented programming language system includes means for calling subroutines written in another language and treating the call as an object.
3. The programming tool claimed in claim 1 or 2, wherein said logic programming language system includes means for processing attribute labels in a manner such that the attribute labels are taken as identical to object attribute names in the object programming language.
4. The programming tool claimed in claim 3, wherein said object oriented language compiler means comprises:
a. first phase means for performing compilation including parsing, optimization, and interpr
b. second phase means in communication with said first phase means for resolving global symbols and loading the database with objects
c. an assembler-like intermediate language for communication between said first and second phase means.
5. The programming tool claimed in claim 3, wherein said object-oriented programming language system includes a language that is a dialect of Smalltalk (Alltalk), and means for treating primitive in and wherein said logic programming language system includes a language that is an extension of Prolog (ALF), and means for treating attribute labels as identical to instance variable names, and means for typing logic variables using objects.
6. The programming tool claimed in claim 5, wherein said interpreter code comprises a plurality of types of bytecodes, and said interpreter includes a plurality of bytecode handler means, one such means for processing each type of bytecode.
7. The programming tool claimed in claim 6, wherein said bytecode types comprise:
execute a primitive,
send a message,
define a block,
evaluate a block,
return from a block or method,
branch, and
assign from one variable to another.
8. The programming tool claimed in claim 7, wherein said interpreter means includes means for maintaining blocks as C data structures, and for making blocks into objects when blocks are assigned to instance variables, or returned as the result of a message.
9. The programming tool claimed in claim 8, wherein said interpreter means includes means for maintaining contexts as C data structures, and for making blocks into objects if and when an associated block is made into an object.
10. The programming tool claimed in claim 9, wherein the bytecode handler means for the "define a block" type bytecode generates block stubs, and wherein said interpreter means creates active context(s) for a block stub, stored separately from said block stub, and wherein said active contexts associated with block stubs obey a stack discipline.
11. The programming tool claimed in claim 10, wherein said interpreter means maintains running data structures for object-oriented processes in an array, each element in the array representing one process, each element containing a stack of active contexts, a pointer to the current context in the stack, an array of block stubs, and a pointer to the next available block stub.
12. The programming tool claimed in claim 11, wherein said interpreter means manages processes by creating processes, switching processes, destroying processes, and performing optimizations on processes.
13. The programming tool claimed in claim 12, wherein said interpreter means performs optimization on processes by message flattening.
14. The programming tool claimed in claim 12, wherein said interpreter means performs optimizations on processes by treating each primitive as its own bytecode.
15. The programming tool claimed in claim 5, wherein said logic programming language includes a set of built in predicates SEND N and including means for sendng messages between the logic programming language system and the object-oriented programming system by employing said predicates SEND N.
16. The programming tool claimed in claim 15, wherein said set of built-in predicates take arguments "receiver", "answer", "selector", and n
wherein "receiver" is the receiver of the message to be sent, "answer" is the object returned from the message, and "selector" is that of the message send, and n remaining arguments are arguments to the message send itself.
17. The programming tool claimed in claim 5, wherein all clauses in the logic programming language are represented as instances of class "Clause", and are rules, facts and queries, and wherein included in the instance variables of class "Clause" are "head" and "tail"; if "head" is nil, the clause is a query, if "tail" is nil,
"head" is of class "Predicate", or a sub-class thereof, "tail" is of class "LinkedList" whose links are of class "Predicate", or a sub- and wherein values of the instance variables of the "head" and "tail links" can be arbitrary objects.
18. The programming tool claimed in claim 3, wherein said database management means includes:
a. object manager means employed by the object oriented language compiler, the interpreter means, primitives, and utilities for providing access to objects in the object database and for mainatining the orginization of obj
b. method fetcher means for calling the object manager means to fetch methods
c. access manager means for managing access to the database, and being called by,
(1) a buffer manager for retrieving objects from the database,
(2) a transaction manager for adding/updating objects in the object database at commit points, and
(3) the object manager for providing higher level inter
d. buffer manager means for,
(1) generating calls to the access manager means when called by the object manager means, and
(2) keeping an in-memory copy of objects when called by th
e. pool manager means for maintainin and
f. garbage collector means integrated with said object manager means and said interpreter means for identifying objects in main memory that are no longer reachable.
19. The programming tool claimed in claim 18, wherein said garbage collector means includes means for defining numbered regions for garbage collection, such that when a context is created, it is assigned a region number, each object created or accessed being assigned the region number of the context that created or accessed it, unless it was previously associated and when an object is returned from a called method to the calling method, the object being moved to the region of the calling method, and when a reference is made from a first object to a second object in another region, the second object being moved to the region of the first object, and when returning from a method, if the context to which it is returning belongs to a region whose number is at least two lower than that of the current region, then the said garbage collector means collects garbage in the regions with the higher numbers than that of the context to which return is being made.
20. The programming tool claimed in claim 19, wherein said garbage collector means includes region cleaning means for detecting when a region has accumulated an excessive number of objects and cleanng the region thus detected.
21. The programming tool claimed in claim 19, wherein said garbage collector means includes means for detecting when objects are shared across processes and for insuring that no object is discarded that is in use by another process.
22. The programming tool claimed in claim 19, wherein said garbage collector means includes an off-line mark/sweep collector means for periodically removing objects from the object database that have become unreachable by any other object in the database, by first marking all objects in the database that can be reached, and then sweeping the database to remove unmarked objects.
23. The programming tool claimed in claim 22, wherein said object database contains constants that are permanently marked such that they cannot be removed by said off-line mark/sweep collector means.
24. The programming tool claimed in claim 3, wherein said logic subsystem means performs unification of logic variables to answer logic queries, and in doing so, takes into account the typing of the logic variables to enable constraint of permissible values of logic variables.
25. The programming tool claimed in claim 3, further comprising debugger means for providing debugging functions comprising setting break points, stepping through program execution, tracing information (e.g. messages, blocks, bytecodes, processes), and displaying values of data structures, said debugger means being integrated with said interpreter means and including a set of C routines for performing tasks associated with the debugger commands, code within the interpreter, and a set of global variables and constants used to communicate between the C routines and the code in the interpreter.
26. The programming tool claimed in claim 3, wherein said object database comprises a key file and a prime file, the prime file having records of variable length containing objects, and the key file having records of fixed length containing the address and record length of objects in the prime file.
27. The programming tool claimed in claim 26, wherein objects in the prime file can be one of 6 types, including:
normal objects,
a symbol cross reference record that contains a string for a symbol and associated object identification of a symbol object,
a dictionary cross reference,
a control record,
a checkpoint integrity record, and
logically deleted objects.
28. In a heap based programming language system, having garbage collector means for removing objects from memory that are no longer reachable by the system, and improved garbage collector means, wherein the improvement comprises: means for defining numbered regions for garbage collection, such that when a context (representing the state of a method which is executing in the system) is created, it is assigned a region number, when an object is created or accessed by a method it is assigned the region number of the on context of the method that created or accessed it, unless the object was previously ass means for moving an object to the region of a calling method when an object is returned from a called method to the calling method, means for moving a second object to the region of a first object when reference is made from the first object to the second object assigned to another region and wherein said garbage collector means collects garbage when returning from a method, if the context to which it is returning belongs to a number at least two lower than the current region num the regions with the higher number than that of the context to which it is returning being collected (i.e. the objects in the regions are discarded).
29. The improvement claimed in claim 28 said garbage collector means includes region cleaning means for detecting when a region has accumulated an excessive number of objects, and cleaning the regions thus detected.
30. The improvement claimed in claim 28 wherein said garbage collector means includes means for detecting when objects are shared across processes for ensuring that no object is collected that is in use by another process.
31. The improvement claimed in claim 28, wherein said system further comprises an object database and wherein said garbage collector means includes off-line mark/sweep collector means for periodically removing objects from the database that have become unreachable by any other object in the database, by first marking all objects in the database that can be reached, and then sweeping the database to remove unmarked objects.
32. The improvement claimed in claim 31 wherein said object database contains constants that are permanently marked, and said off-line mark/sweep collector means includes means for recognizing said marks and preventing removal of said constants by said collector means from said database.
33. The improvement claimed in claims 28, 29, 30, 31, or 32, wherein said system further comprises an in-use table containing a list of objects that must be kept in-memory, said table including a field designating each object's region.
Description:
TECHNICAL FIELD OF THE INVENTIONThe invention relates to a programming tool that allows application programming in both logic and object-oriented style, and which provides integrated database support. BACKGROUND OF THE INVENTION Object-oriented programming, logic programming, and database facilities have all been shown to have significant power in the writing of applications to run on a computer. No single programming tool has successfully integrated all three facilities in such a way as to eliminate an explicit interface between them. Normally, one must convert between object data to logic data to use the logic programming system, and then convert the logic data back again in order to use the object-oriented system. Furthermore, one must normally make explicit calls to a database manager in order to retrieve and store application data. There have been some attempts to provide combined logic and object-oriented programming tools. For example, the Smalltalk/V (Smalltalk Tutorial and Programming Handbook, Digitalk, Inc., 1987) allows the user to invoke a logic programming tool (Prolog) from an object-oriented on (Smalltalk). However, the only kind of data (terms) that Prolog understands are strings, symbols, numbers, structures, and lists of any of the above. Furthermore, the Prolog structures are constrained to be a type of list from the object-oriented programming tool. Additionally, Smalltalk/V does not have database storage for the objects. There have also been attempts to provide database support for object-oriented tools. For example, the Gemstone system, a product of Servio- Logic, Inc., while supporting a database server that can be programmed in Smalltalk, does not allow the application to be written in Smalltalk in such a way that the database server is transparent: i.e. the application must make speciific calls to the database server (`Integrating an Object Server with Other Worlds`, by Alan Purdy et al, ACM Transactions on Office Information, Vol. 5, Number 1, Jan. 1987). Gemstone does not contain any logic programming tools. Some so-called "expert system shells"(e.g., Nexpert Object from Neuron Data, Inc.) allow for objects, rules and database features to be combined, but these tools are for the construction of a certain class of application ("expert systems"), and do not provide a general-purpose programming tool. It is the object of the present invention to solve the problem of providing a general purpose programming tool that smoothly integrates object-oriented and logic programming, and provides the user with database facilities that are transparent to the user. SUMMARY OF THE INVENTION The present invention solves the problem by providing a single programming tool (referred to herein as Alltalk) which allows the programmer to write applications in an object-oriented language (a dialect of Smalltalk, also referred to herein as Alltalk), a logic programming language, (which is an extension of Prolog, herein called ALF) or a combination of the object and logic programming languages which allows the logic programming language system to consider any object from the object-oriented programming language system as a term in the logic programming language, and which supplies database management on behalf of the programmer, without the need for any specific database management control statements to be supplied by the programmer. The main components of the Alltalk tool include a work station having an operator interface, a mass memory, and a CPU. An object-oriented programming language system running on the work station includes an object-oriented programming language and an object-oriented language compiler for translating source code written in the object-oriented programming language into objects and interpreter code. Also running on the work station is a logic programming system including a logic programming language having components of terms, clauses, predicates, atoms, and logic variables, and a logic language compiler for translating source code written in the logic programming language into objects. A database residing in the mass memory stores objects and components of logic programs as objects in a common data structure format, applications data, and application stored as compiled interpreter code. The database is managed by an database manager that represents objects and components of the logic programming language in the common data structure format as objects and is responsive to calls for retrieving and storing objects in the database and for automatically deleting objects from the database when they have become obsolete. An interpreter executes the interpreter code and generates calls to the database manager. A logic subsystem solves logic queries and treats objects as components of a logic program. According to a further aspect of the present invention, an improved database format is provided for an object-oriented programming language system. The database has a key file and a prime file. The prime file contains records of variable length for storing objects, and the key file contains records of fixed length for storing the address, record length, and type of object in the prime file. An improved database manager for managing this database includes an object manager employed by the compiler, interpreter, primitives and utilities for providing access to objects in the database, and for maintaining organization of objects in the database. An access manager is called by a buffer manager for retrieving objects from the database, a transaction manager for updating the database with new or changed objects at commit points, and for undoing changes to objects upon aborts, and the object manager for providing high level interface to the database. A buffer manager is called by the object manager for generating calls to the access manager, and by a pool manager for keeping an in-memory copy of objects. The pool manager maintains memory for buffers. According to another aspect of the present invention, an improved garbage collector is provided for a heap based programming language system. The garbage collector employs the concept of regions for garbage collection. When a context (representing the state of a method which is executing in the system) is created, it is assigned a region number. When an object is created or accessed by a method, it is assigned the region number of the context of the method that created or accessed it, unless the object was previously assigned a lower number. When an object is returned from a called method to the calling method, the object is moved to the region of the calling method. When reference is made from a first object to a second object assigned to another reigon, the second object is moved to the region of the first object. When returning from a method, if the context to which it is returning belongs to a number at least two lower than the current region number before returning, the regions with the higher number than that of the context to which it is returning are collected (i.e., the objects in these regions are discarded). According to a still further aspect of the present invention, the runtime performance of a Smalltalk programming language system is improved by implementing a technique called message flattening. The compiler flags any method which consists of a single return statement which returns either an instance variable, or the result of a primitive, for which the first argument is self, and the other arguments correspond to arguments to the method. The interpreter detects these flags at runtime and flattens any message that would normally invoke these methods, by replacing this message send in the first instance with an assign, and in the second instance with a primitive invocation.
BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a schematic diagram showing an overv FIG. 2 is a schematic dia FIG. 3 is a schematic diagram of the FIG. 4 is a schematic diagram showing initialized stacks for cont FIG. 5 is a schematic diagram showing the creat FIG. 6 is a schematic diagram showing FIG. 7 is a schematic diagram showing creati FIG. 8 is a schematic diagram showing the creat FIG. 9 is a schematic diagram showin FIGS. 10-13 illustrate the mode FIG. 14 shows the c FIGS. 15-16 illustrat FIGS. 17-18 show the relationships between the context stack, processes, regions, FIG. 19 is a schematic block diagram illustrating the functions of t FIG. 20 shows the in-use table's structure and in FIG. 21 shows the in-use table's relationships with the object table, the buffers, FIG. 22 shows how garbage is collected upon and FIG. 23 is a schematic block diagram illustrating the functions of the ALF compiler.
DESCRIPTION OF THE INVENTION A portion of the disclosure of this patent document contains material to which a claim of copyright protection is made. The copyright owner has no objection to the copying of the patent document or the patent disclosure, but reserves all other rights. 1. Introduction The Alltalk tool runs on workstation type hardware, such as a Sun 4/360 by Sun Microsystems, Inc., executing the UNIX operating system (UNIX is a trademark of AT&T). Referring to the Drawings, FIG. 1, the hardware includes an operator interface including a visual display (CRT) 10, a keyboard 12, and a pointing device 14, such as a 3 button mouse. The hardware also includes mass memory, such as a disk 16 on which the Alltalk database resides, as well as a CPU and main memory 18. The Alltalk software which is executed by the CPU and main memory 18 consists of an Alltalk compiler 20 for a dialect of the Smalltalk language (also called Alltalk) and an Alltalk runtime environment 22. The hardware components of the workstation are connected by a bus 24. 2. Overview The Alltalk compiler 20 is a program for translating Alltalk language source statements into interpreter code. The compiler is generated by the YACC and LEX utilities in the UNIX operating system, and contains subroutines written in the C programming language. Referring to the Drawings, FIG. 2, the compiler operates in 2 phases: the first phase 26 parses the source code written in the Alltalk language 28 and constructs an intermediate code 30. The second phase 32 takes the intermediate code and generates class objects, constant objects, and method objects and places these in a database 40. These objects are subsequently retrieved by the runtime environment 22 (see FIG. 1). The runtime environment 22 is written in the C programming language, and in Alltalk. Referring to the Drawings, FIG. 3, the logic language compiler 36 and the logic subsystem 38 are both written in Alltalk. These are compiled through the previously mentioned Alltalk compiler 20, and the output placed in the database 40 and hence available to the runtime environment 22. Other applications 42 written in Alltalk are similarly available to the runtime environment after compilation. Application programs 42 (called methods) are processed by an interpreter 44, which calls other components of the runtime environment, which includes: a transaction manager 46 which can commit and abort transactions, an object manager 48 which is called to create and retrieve objects, a method fetcher 50 which determines the correct method to execute next, and a garbage collector 52 which detects and removes unneeded objects from main memory. The object manager 48 calls upon a buffer manager 54 to determine if a requested object is in memory or needs to be fetched from the database. If the object is to be retrieved from the database, a pool manager 56 is called to find space in an appropriate buffer, after which an access manager 58 is called. It is the access manager 58 that accesses the disk 16 containing the database 40. 3. Compiler The Alltalk compiler 20 translates class descriptions written in a dialect of the Smalltalk language herein referred to as Alltalk into database objects for use by the Alltalk interpreter 44 during execution. 3.1. Synopsis The Alltalk compiler 20 takes a file containing one or more complete Alltalk class descriptions, and for each class generates:
1. A class object, containing a dictionary of the methods in the class and specification of the instance and class variables,
2. Compiled methods, each consisting of "bytecodes", which drive the runtime interpreter, and
3. Objects representing constants encountered during compilation, (numeric values, strings, etc.)which are placed in the database 40 for use by the interpreter 44 during execution. The Alltalk compiler 20 consists of two phases. The first phase 26 (see FIG. 2) does the compilation work, (parse, optimization, and code generation), while the second phase 32 resolves global symbols and loads the results into the database. The two phases communicate via intermediate code 30 (written in an assembler-like intermediate language) which can be examined and altered by the user, if desired. The following is a description of the organization of the internals of the Alltalk compiler 20, including code generation strategies and optimization techniques. 3.2. Phase 1 (kcom) 3.2.1. Parsing The first phase 26 of the Alltalk compiler 20 consists of two distinct processing stages:
1. Parse tree construction, and
2. Code generation, (including optimization).The parsing phase is implemented in a fairly straightforward manner using the UNIX yacc/lex parser generator/lexical analyzer tools. The primary goal of the parsing stage is to create an internal parse tree representation of the class description and its methods which can be analyzed using a relatively simple set of mutually recursive tree-walking routines. In addition, the grammer of the input file is checked and errors are reported to the user. The grammer specification of the object-oriented language is virtually identical to that specified in the syntax diagrams of the standard Smalltalk language reference, Smalltalk-80 The Language and Its Implementation, by Goldberg and Robson. The most notable variation in the Alltalk grammar is that of allowing a primitive invocation to be used as a primary expression and to have primary expressions as arguments, (this is adopted from Little Smalltalk, by Timothy Budd). This allows Alltalk primitives to be intermixed freely with the Alltalk language as if they were function calls which return a value, (which is essentially what the primitives really are), instead of as wholesale replacements for methods, as in standard Smalltalk. Additional productions have been included to allow for reading an entire class description from a file, (in a form roughly similar to Smalltalk "fileIn/fileOut" format). These additional productions include "header" information such as superclass specification, instance/class variable declarations, and instance/class method classification statements. While it is possible to build the entire analysis and generation mechanisms directly into the action portions of the yacc productions, the conciseness of the analysis and generation stage would be lost in that it becomes difficult to piece together how the parser actions interact to accomplish that stage when the controlling function is the yacc parser. Clarity is enhanced by having the analysis and generation functions make explicit their own walking of the parsed information, since it may vary from that of the parser at various points in the compilation. For example, more complex/global optimization techniques, such as inter-statement optimizations, may need to determine their own scope of applicability across several statements worth of parsed information. Such techniques are harder to embody as a single understandable function when mixed with the simple actions of parsing. The basic parse node is a simple binary node, (left and right child pointers), with placeholders for the node type constant, a source code line number, and a string pointer. Parse nodes are created via a function called makenode(), which allocates storage storage for the node, inserts the current source line number, and sets the other elements as specified by the user. The storage allocated for these nodes, (as well as for the class and method structures and copies of strings), is not tracked in the Alltalk compiler 20 since the compiler is expected to be run only for the duration of the compilation of a file. A sample parse tree for an Alltalk method is given in Table 3.1. Syntactical shorthand and default meanings, such as the return value of a method having no statements being "self", or a block having no statements being "nil", are fleshed out during the parse phase in order to limit the amount of special case logic in the analysis and generation phase.
__________________________________________________________________________
Parse Tree Example
__________________________________________________________________________
Method Code! SequenceableCollection methodsFor: 'enumerating'do: aBlock│ index length │index &- 0.length &- self size.[(index &- index + 1) &= length]whileTrue: [aBlock value: (self at: index)]
__________________________________________________________________________
Parse Treestatement
statementassign
assign"index"
"length"number
unary-- expr"0"
"size"identifier"self"statementkeyword---- exprkeyword-- arg"whileTrue:"block
blockstatement
statementbinary-- exprkeyword-- exprkeyword-- arg"&="
"value:"assign
identifieridentifierkeyword-- exprkeyword-- arg"index" "length""aBlock""at:"binary-- expr
identifieridentifier"+"
"index"identifiernumber"index" "1"
__________________________________________________________________________
A successful parse generates a parse tree for the statements of each method in the class. These parse trees are anchored in a method structure for each method, which are all, in turn, linked to a single class structure. When the parsing of a class is complete, the class structure is handed to analysis and code generation routines. 3.2.2. Code Generation The major components of this stage of the compiler are:
1. Symbol table (symbol.c)
2. Code generation (compile.c)
3. Code management (code.c)
4. Optimization (optimize.c)Generally, the processing steps involved in this stage, (implemented by a function called compileClass()), proceed as follows:
1. The symbol table is initialized with the instance and class variables available via the superclass chain for the class. These symbols are retrieved from a symbol file in the local directory. It is considered a fatal error if the superclass cannot be found in the symbol file, (i.e., the superclass must be compiled first).
2. The instance and class variables for the class are added to the symbol table. Name clashes involving superclass variables are also considered fatal.
3. Each method is compiled. During method compilation, bytecodes are collected into segments corresponding to groups of statements in the method: one for the method itself, and one for each block within the method. When method compilation is complete, the method code segment is emitted first, followed by the segments for each block.
4. After the methods have been successfully compiled, a record of the class' instance and class variables are written to the symbol file in the local directory. This makes the class available for use as a superclass in subsequent compilations.The method compilation step is the heart of the compilation task. Before describing this step in detail, a description of the compiler's view of symbolic references and the symbol table is given. 3.2.3. Symbols Throughout the Alltalk compiler 20, references to named symbols in the program being compiled, as well as references to unnamed runtime storage are represented in a uniform manner. This uniform representation allows the code generation stage to freely create and pass references between the recursive routines which implement this stage without regard for their type until a leaf routine which needs detailed type information is executed. The conciseness of the code generation routines is greatly enhanced with this representation scheme. There are nine reference types, as follows:
Named References
Instance Variable
Class Variable
Method Parameter
Formal Method Temporary
Block Parameter
Global Symbol ("true", "false", "nil", class name, etc.)
Unnamed References
Constant ("10", "3.14", `a string`, #symbol, etc.)
Compiler Temporary (used in evaluating intermediate
expressions) Block Stub/Closure (reference to storage holding the runtime id of the closure)The symbol table supports a subset of the named references, separating them into the three categories of: (1) class, (2) instance, and (3) temporary symbols. Temporary symbols encompass the method parameter, formal method temporary, and block parameter references. Global symbol references are never actually placed in the symbol table, but are materialized whenever the search for a name fails. These symbols are resolved by the second phase 32 of the Alltalk compiler 20, since the cross reference values for these names are actually present in the runtime system dictionary contained in the database 40. The symbol table interface routines contain the usual routines for the addition of symbols, (addSymbol()), and name-based search for symbols, (findSymbol()). An initialization routine, (initSymbols()), purges the table and then uses the globally specified superclass name to populate the table with "ref" structures for the instance and class variable symbols available via the superclass chain, as recorded in the symbol file in the local directory. A routine for writing the instance and class variable symbols, (writeSymbols()), to the local symbol file for the globally specified class, (i.e., the one being compiled), is also provided. Finally, a pair of general routines, (markSymbols() and releaseSymbols()), are available for get/set of placeholders in the symbol table. These are primarily used to record the starting position of method and/or block temporary symbols, so that they can be removed at the end of the compilation of the method and/or block statements. 3.2.4. Method Compilation In the runtime environment 22 (see FIG. 3), a method is executed with an associated "context" containing local storage organized as an array of temporary slots, analogous to a "stack frame" in a conventional language. This local storage is divided into the following five sections from the compiler's point of view:
1. The object id of the receiver, known as "self".
2. Method parameters.
3. Formal method temporaries, (named temporaries).
4. Compiler scratch area for intermediate expression evaluation.
5. Block stub/closure id storage for blocks in the method.A general mechanism for tracking the use of the temporary slots is implemented in the compiler using a set of macro routines. This set includes routines for: allocating a number of temporaries, (allocTemp()), which returns the starting slot for freeing a number of temporaries, (freeTemp()); get/set of temporary usage information, (getTempUse(); and setTempUse()); clearing usage information, (clearTempUse()); and requesting the high water mark for temporary usage, (maxTempUse()). Temporary usage is tracked with these routines for the first four kinds of temporaries listed above. Storage for block ids is tallied separately during method code generation since it is not known what the required number of compiler scratch temporaries will be until the method compilation has finished. Before the method statements are examined, several initialization steps are performed:
1. The symbol table is populated with the entries for "self", "super", the parameters, and the formal temporaries. The slot index for each entry is determined by allocating a temporary as each symbol is added to the table.
2. A code segment is allocated for the method statements and made to be the "active" segment. During compilation, generated code is placed in the "active" code segment, which is switched when compilation of a new list of statements, (e.g., a block), is started or completed.
3. Label generation is reset, (used for branch targets and block entry points).
4. The block count is reset.Also prior to commencing code generation, the parse tree of the method is examined to see if it can be tagged for "flattening" at runtime. "Method flattening" is a technique for determining whether a runtime message send can be avoided because the method is "trivial". A "trivial" method is one which contains a single statement returning either:
1. An instance variable, (can replace send with an assign), or
2. The result of a primitive for which first argument is self and the remaining arguments to the primitive invocation line up exactly with arguments to the method, (can replace send with primitive invocation).At this point, compilation of the method statements is initiated by calling compileStatementList() with a pointer to the first statement parse node of the method. This routine invokes compileExpr() to compile the expression associated with each statement in the list. CompileStatementList() is used to compile lists of statements for blocks as well as methods, generating appropriate return bytecodes when explicit return statements are encountered and after the last statement in the method or block. CompileStatementList() distinguishes between method and block statement lists by the value of active code segment id, which is -1 for a method or &=0 for a block. Provision is also made for the case of "inline" block code generation, which is used in optimization of certain messages involving blocks, (such as messages to booleans), described later. 3.2.5. Expressions Expression compilation is the center of most activity during the compilation of a method. CompileExpr() defines the compilation actions for all parse nodes other than statements in a concise manner. This routine is invoked with the node to be compiled and a destination specification for the result of compiling the expression indicated by the node in the form of a "ref" structure. The destination specification allows the calling routine to control placement of the expression's value, which is particularly useful for aligning values for message sends, minimizing unnecessary data movement at runtime. Simple expressions, such as identifiers and constants, are trivial compilations requiring only assignment of the value associated with the identifier or constant description to the specified destination. An explicit Alltalk assignment expression, (e.g., "a?b+c"), only requires compilation of the expression on the right of the "?", with the reference on the left as the destination, in addition to assigning this result into the specified destination for the assignment expression itself, (e.g., "d?(a?b+c)"), if indicated. The remaining expression types, (messages, cascades, primitive invocations and blocks), require somewhat more involved compilation steps, hence, these cases have been split into separate routines, (genSend(), genCascade(), genExecPrim(), and genBlock()). We now describe the compilation steps performed in each of these cases. 3.2.6. Messages and Cascades The runtime implementation of the send message bytecode requires that the receiver and arguments be present in a contiguous set of the sending context's temporaries. The location for the return value of the message send is also required to be a temporary in the sending context, though it need not be adjacent to the receiver and arguments. GenSend() ) complies with the first condition by allocating a contiguous set of temporaries, (via allocTemp() ), and compiling the receiver and argument expressions with each of these temporaries, (in order), as the specified destination. Hence, results of receiver and argument expressions are cleanly aligned with their use in containing message sends, eliminating unnecessary data re-positioning assignments. A simple optimization is also done at this point. If the receiver and argument temporaries already happen to line up,(detected by lineup() ), new temporaries are not allocated and the receiver and argument values need not be moved. The second condition, (destination must be a temporary), is honored by examining the specified destination reference and allocating a temporary to hold the result of the message send if the destination is not already a temporary. This situation is remembered and code is generated for moving the result from the allocated temporary to the actual destination after the message send. This implementation style allows for the addition of variations of the send message bytecode for non-temporary destionations, if the need arises. The previous comments also apply to cascaded message sends, (genCascade() ), except that the receiver expression is only evaluated once and the result placed in a temporary, to which the remaining messages in the cascade are sent, (genCascadeSend() ). 3.2.7. Primitive Invocations As with message sends, Alltalk's primitive invocations require that arguments to the primitive be in a contiguous set of the invoking context's temporaries, and the destination for the result be a temporary in the invoking context. GenExecPrim() ) handles the non-temporary destination and argument alignment cases, (using lineup() ), in the same manner as is done for message sends. Each primitive argument is compiled, allowing arbitrary expressions to be used as arguments. 3.2.8. Blocks Blocks are the most involved expression compilations in that they cause changes in the global state of the compiler. In Alltalk, a block is a list of statements which are to be executed with their own context when a "value" message is sent to it. The lexical aspects of a block allow it to refer to names available to the method in which the block is defined, as well as the names in any containing block. These names include the method's parameters and formal temporaries and any containing block's parameters. These semantics imply that a block is a static "object" of sorts which can potentially have muliple runtime activations, with each activation dynamically establishing variable name ?? storage bindings. Hence, from the compiler's point of view, a block is a separate list of statements to be compiled and "set-up" as an object, which may also include cross-context runtime references to be represented. GenBlock() ) alters the global state of the compiler to create the proper compilation conditions to meet the needs described above. The block being compiled is given a unique id within the method, and a new code segment is allocated and marked with this id and connected to the list of code segments generated for the method so far. The currently active code segment is saved, along with its temporary usage, (since the block will have its own context), and the new segment is made the active segment, (generated code is always placed in the active segment). The previous code segment and its temporary usage are restored when compilation of the block is completed. The symbol table is marked so that the block's symbols, (block parameter names), can be released at the end of the block's compilation, and the block's symbols are added to symbol table for proper scoping. Finally, a label is generated to mark the start of the block's code in the method. At this point, the state of the compiler has been properly altered, and compilation of the statements in the block is initiated via compileStatementList() ). Once the block has been compiled, all the information needed to describe the block's activation characteristics at runtime, (temporary usage and entry point), has been established. This information is supplied to the runtime interpreter 44 via the set up block bytecode. This bytecode causes the interpreter to copy this information and associate it with a unique runtime id, known as a block stub id. A block stub id can be manipulated much the same way as any other object id. In the case of returning a block stub, or assigning a block stub to an instance variable, Alltalk establishes an object for the block stub. The information associated with the block stub id is used to establish a context for executing the statements of the associated block whenever the "value" message is sent to this id, (i.e., the evaluate block bytecode is executed for the id). Note that this requires that a block must be "set up" before it can be "evaluated" at runtime. Alltalk choses placement of the set up bytecode for a specific block so that the bytecode is not executed an uncontrolled number of times. This is because the set up block implementation in the interpreter does not check for multiple "set ups" performed for the same block. The solution to the placement problem is to group the set up block bytecodes for any "top level" block, (i.e., any block encountered while generating code for the method statements), and its contained blocks, and place them in the method code segment ahead of the first use of the "top level" block. This technique avoids executing set ups for any block(s) which are not in the specific control flow path at runtime. GenBlock() ) implements this strategy by setting a pointer to a position in the method segment code at which the set up block bytecodes are to be "spliced" when a "top level" block is entered. 3.2.9. Message Optimizations Except for aiding the runtime environment for "method flattening", the rest of the compiler optimizations involve recognition of specific message selectors in the source code, (optimize.c). The optimization strategy for these selectors is to generate inline code to implement the specific semantics of the selector, (assuming a specific receiver class), in order to avoid sending the actual message at runtime. These optimizations are detected by the genOptiSend() ) routine which is invoked from compileExpr( ) ) when a message expression is compiled. If genOptiSend () ) can handle the message, the normal compilation via genSend() ) is avoided by compileExpr() ). The message selectors/receiver class combinations which are currently optimized are listed in Table 3.2.
______________________________________
Optimized Messages Class
______________________________________
perform:perform:with:perform:with:with:perform:with:with:with:Integer
valuevalue:value:value:value:value:value:value:value:value:value:value:value:value:value:value:whileTrue:whileFalse:whileTruewhileFalseTrue/False
ifTrue:ifFalse:ifTrue:ifFalse:ifFalse:ifTrue:and:or:not&│Object/
isNilUndefinedObject notNil
______________________________________
The complexity of these optimizations vary from simply generating special bytecodes, (e.g., Integer messages), to inline block code generation with conditional branch bytecodes for implementing looping constructs, (e.g., Block "while" messages). Due to the straightforward expression of these optimizations, they are not treated in detail here. However, one of the more complex optimizations, (optWhile() ), will be described to highlight and convey an understanding of some of the issues and supporting procedure structure involved in these optimizations. OptWhile() ) handles optimization of the various "while" messages which can be sent to blocks, (whileTrue:, whileFalse:, whileTrue, and whileFalse). This routine demonstrates the need to deal with:
1. Evaluation of literal or non-literal block objects in receiver and/or argument positions,
2. Proper placement of set up block bytecodes to avoid repeated set up of the same block(s), (described previously in the section on block expression compilation), and
3. Generation of additional code to implement the semantics of the message, (looping, in this case).Since the semantics of the "while" messages clearly involves sequenced evaluation of receiver and argument blocks, it is possible, if either block is literal, to treat the statements of that block as if they were in the statement list of the method or block containing the "while" message. This causes code to be generated directly into the currently active code segment, ("inline"), resulting in evaluation of that block in the current context at runtime, instead of setting up a separate context for evaluation of the block code. If either block is not a literal, (e.g., passed in as a parameter), that block must be evaluated in a separate context, (performed by the "evalb" bytecode). This situation of block code generation strategy arises in the optimization of many other of the messages listed in Table 3.2. OptBlock() ) determines the code generation strategy based on the type of the parse node representing the block in the parse tree. If the node represents a literal block in the source code, the statement list for the block is compiled into the active code segment using compileStatementList() ). Otherwise, a "value" unary message expression, with the node representing the block as the receiver, is constructed and compiled under the explicit assumption that the receiver will be a block, (genEvalBlock() ). Note that this assumption is not made, (and a different bytecode is generated), when the "value" message is encountered in the original source code, since the actural receiver may not be a block at runtime, in this case. Literal blocks which are part of the "while" message may be "top level" blocks, (i.e., outermost block of a nesting within a method). Beacuse of this, optWhile() ) must set the "splice point" in the method segment code for set up block bytecodes for any blocks contained in the "while" blocks, such that these bytecodes are placed outside the looping portion of the "while" code. This avoids the multiple "set up" problem for a block discussed in the previous section on block compilation. With the background of the preceding discussion, the implementation of the optimization of "while" messages is summarized in the following steps:
1. If the "while" message is encountered in the method statement list, set a marker to the current position in the code as the "splice point" for set up block bytecodes for blocks which are encountered during compilation of the "while" message.
2. Generate a label to mark the start of the condition block, (i.e., the receiver of the "while" message).
3. Compile the condition block, (using optBlock() ), with an allocated temporary as the destination for its evaluation result.
4. Generate a conditional branch to the end of the "while" message code, (step 7), based on the result of evaluating the condition block and the specific message being compiled.
5. Compile the body block, (using optBlock() ), with no destination for its evaluation result.
6. Place an unconditional branch back to the label generated in step 2 to close the loop.
7. Generate code to assign "nil" to the destination specified for the value of the "while" message expression, (the destination may be "none"). This is the defined value for a "while" message expression.
8. Free the temporary allocated for the result of the condition block in step 3.An example of the code generated for "while" message expressions with different combinations of literal and non-literal condition and body blocks is shown in Table 3.3.
______________________________________
"While" Message Code Generation Source Statement
Generated Code
______________________________________
[x & y]whileTrue: L1[x &- x + 1].send
t1[x],0,t5,2,#&jne
L2,t5,'truemov
t6,t1[x]mov
t6,0,t1[x],2,#+jmp
L1L2b1 whileTrue: [x &- x + 1].L5evalb
t3[b1],t5,1jne
L6,t5,`truemov
t6,t1[x]mov
t6,0,t1[x],2,#+jmp
L5L6[x & y] whileTrue: b2.L9send
t1[x],0,t5,2,#&jne
L10,t5,`trueevalb
t4[b2],t6,1jmp
L9L10b1 whileTrue: b2. L13evalb
t3[b1],t5,1jne
L14,t5,`trueevalb
t4[b2],t6,1jmp
______________________________________
The intermediate language is discussed further in the next section. 3.3 . Phase 2 (kasm) As noted in the synopsis, the second phase 32 of the Alltalk compiler 20 concerns itself with resolving symbols, and creating and loading the classes and methods into the database. 3.3.1. Intermediate Language The intermediate language expected as input for this phase consists of tokens representing bytecodes, along with directives for establishing the class, delimiting methods, and tracking the Alltalk source file name and line numbers. A summary of these tokens and directives are listed in Tables 3.4 and 3.5, respectively.
______________________________________
Intermediate Language Bytecode Tokens
______________________________________
Message Send/Returnsend
send messagesendp
send parameterized message, ("perform")mret
return from method, (" " in source code)Integer Arithmetic Optimizationsseq
send "=" messagesadd
send "+" messagesadd1
send "+ 1" messagessub
send "-" messagessub1
send "- 1" messageBlock Set-Up/Evaluation/Returnsetb
set up block stub/closureevalb
evaluate block (receiver must be a block)evalbo
evaluate block (receiver might not be a block)bret
return from blockData Movementmov
src/dest specified by "effective addresses"Primitive Invocationprim
execute specified primitiveControl Flowjeq
jump on target equal to constantjne
jump on target not equal to constantjmp
unconditional jump
______________________________________
______________________________________
Intermediate Language Directives
______________________________________
Class Information.class
start specified class.supervar number of inherited superclass variables.ivar
instance variable names defined in this class.cvar
class variable names defined in this classMethod Information.imethod
start instance method.cmethod
start class method.mparam
method parameter names.mtemp
method temporary names.mprim
"flattenable" primitive-only method.mattr
"flattenable" attribute-return method.mend
end methodSource File Tracking.file
source code file name.line
source code line number
______________________________________
In addition to the basic elements of the language, symbolic labels of the form "L&number&" are also available for use in the code, (for jeq, jne, jmp, and setb bytecodes), with target labels being required to start at the beginning of a line which contains no other tokens. Comments are allowed on any line, and are defined to be anything contained between a semicolon, (";"), and the end of the line. An example of this intermediate language for a method of a class call Foo, is shown in Table 3.6, which was constructed in order to demonstrate the variety of code and reference type representations generated by phase 1.
______________________________________
Intermediate Code Examples
______________________________________
MethodClass Foo :Object│ instvar Classvar ││do: aBlock│ a b │instvar &- Classvar.instvar associationsDo:[:assoc │ assoc value timesRepeat:[aBlock value: assoc key]].a &- `hi andy`.b &- #(2 ( foo `hi` $a ) `fred`).]Intermediate Language.file Foo.st.class Foo Object.supervar 0.ivar instvar.cvar Classvar.imethod do:.mparam aBlock.mtemp a bL0mov
i0[instvr],`Fooi1[Classvar]mov
t5,i0[instvar]setb
b0,L1,5setb
b1,L2,5mov
t5,0,t4,2,#associationsDo:mov
t2[a],`hi andy`mov
t3[b],( 2 ( #foo `hi` $a ) `fred`)mret
t0[self]L1evalbo
t1[assoc],t3,1send
t1[assoc],0,t3,1,#valuemov
t3,0,t2,2,#timesRepeat:bret
t2,mt1[aBlock]mov
t4,b0t1[assoc]send
t4,0,t3,1,#keyevalbo
t2,t1,2send
t2,0,t1,2,#value:bret
t1.mend 7 2
______________________________________
3.3.2. Effective Addresses References to various types of runtime variables and constants are represented in specific symbolic forms in the intermediate language which we call "effective addresses". These forms appear in the argument fields of many of the bytecode tokens, although not all forms are valid in specific argument positions of specific bytecodes. These effective address forms are summarized in Table 3.7, and the reader is again referred to the code in Table 3.6 for examples.
__________________________________________________________________________
Effective Address Forms Runtime Form
Example Type Description
__________________________________________________________________________
Numeric constant.$&char&
Character constant.`&chars&`
String constant.#&chars&
Symbol constant, (object id of symbol).`&name&
5 Global symbol cross reference constant, (objectidassociated with symbol name).#(&consts&)#(1 `hi`)1
Array constant, (can be nested).t&num&
Current context temporary.mt&num&
Owning method context temporary, (only found in10block code).b&num&
Block stub id as slot in owning method contexttemporary.i&num&
Instance variable slot.`&name&i&num&`Bagi24
Class variable. Combination of cross reference15constant, (the class name), and slot.b&num&t&num&b1t36
Block parameter reference. Generated only when ablock refers to a containing block's
__________________________________________________________________________
parameters. In the particular case of the "mov" bytecode, phase 2 translates both the source and destination effective address forms into one of six specific runtime reference types. 3.3.3. Operational Description Phase 2 maintains a global state around the current class and method being "assembled", resulting in method-at-a-time assembly and placement into the database. Ths class object is not given to the object manager until all methods described in the input file have been successfully translated and passed to the object manager. This insures that the old version of the class, (hence, its methods), is not replaced unless assembly of the new version is successful. In contrast to phase 1, this phase is very "flat", that is, it contains no recursive functions to walk parse trees, since each input statement is essentially a self-contained description. All the implementing functions, (assemble.c), are despatched directly from the parser on a per statement, (or group of statements), basis, resulting in a very simple control flow. Assembly of a method essentially consists of collecting the bytecodes described by the bytecode statements into a scratch area, (MethodBytes), and recording labels, references to labels, and block references in these statements for resolution when the end of the method is reached. Each bytecode statement has a corresponding translation routine, (assemble.c), which builds the runtime representation of the bytecode in the scratch area. When the end of the method is reached, (endMethod() ), all label and block references are resolved and the object manager is called upon to allocate space for the compiled method object. In this area, the instance variable slots for the method object are initialized, (noTemps, noParms, classOop, selectorSymbol, . . . , etc.), and the bytecodes are copied in from the scratch area. A dictionary entry relating the method selector symbol id of the method to the id of the compiled method object is also created and added to entries already established for other methods, (in the Methods global array). These dictionary entries are stored in the class object when the end of the class is reached, (i.e., when a new `.class` directive or end-of-file is encountered). When the end of the class is reached, (endClass() ), space is obtained from the object manager under the same object id as the previous version of the class, to cause replacement of that class. The class is then built in this area by filling in control information, including the object id of the first instance of the class obtained from previous version, the object id of the class name symbol, the id of the superclass and the size of the method dictionary for the class. The method dictionary entries are then closed-hashed, (by method selector symbol id), into a dictionary area in the class object. The class object is then flushed to the database, signaling completion of the assembly of the class, ending phase 2. 4. Interpreter The interpreter 44 (see FIG. 3) is that portion of the Alltalk runtime environment 22 which the user invokes to run Alltalk applications. The interpreter 44 decodes the object code generated by the compiler 20 (FIG. 2), and executes it, calling upon many of the other services of the runtime environment 22. The interpreter 44 also includes a debugger, described below, which allows the programmer to inspect the running program in a variety of ways. 4.1. Synopsis The previously described Alltalk compiler 20 for the Alltalk dialect of the Smalltalk language translates Alltalk source code into an intermediate representation, called bytecodes, and stores this representation in the database 40. Each bytecode represents an instruction for the interpreter 44, and consists of an operation code (a = bit integer) and a variable number of parameters. Applications are executed using the Alltalk interpreter 44. The Alltalk interpreter 44 uses the object manager 48 as the interface to the database 40. It also calls on the transaction manager 46 and the garbage collector 52. In addition, it invokes primitives which interface to the UNIX operating system to do things like operating on primitive data types (integer addition, floating point multiplication, string concatenation, etc.), performing file I/O, managing the display, and controlling keyboard and mouse input. The object manager 48, transaction manager 46, garbage collector 52, and primitives are described in later sections in more detail. The main functions in the interpreter 44 that are discussed in this section can be grouped into the following main categories:
(5) initial and
(6) the debugger. 4.2. Bytecode L