Data processing: software development – installation – and managem – Software program development tool – Testing or debugging
Reexamination Certificate
2000-05-12
2003-10-14
Chaki, Kakali (Department: 2124)
Data processing: software development, installation, and managem
Software program development tool
Testing or debugging
C706S013000
Reexamination Certificate
active
06634019
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a fault tolerant and combinatorial software environment. More specifically, the present invention relates to a system, method and medium for providing and facilitating a virtual machine and instruction format that facilitates systematic or arbitrary alteration and recombination of portions of code (e.g., programs) at run-time. Instructions that comprise a language that can be used with the present invention can be individualized, allowing for differentiation of each instruction based on, e.g., usage, origin, authorship, or any other user-defined tag. The overall instruction set can be extended to include any object or procedure that can be represented by software. The invention is envisioned for use in applications such as those relating to automatic program creation (e.g. genetic programming), artificial/directed evolution of digital designs (graphic, industrial, mechanical, architectural, engineering, etc.), online adaptive software systems, product and process reliability testing, and simulation of biological, non-linear, and probabilistic processes.
2. Related Art
Numerous computer-programming languages exist today. These include assembly languages, and higher-level languages such as BASIC, Visual Basic, C, C++, Java, etc. Although many computer systems/languages are increasingly compared to DNA and genetics, they do not include many desirable attributes of biological “computation” systems and therefore are deficient for implementing robust, evolvable, life-like computer programs. Specifically in existing computer systems/languages:
Instructions must have proper syntax and execution context.
Instructions cannot be arbitrarily recombined to form new programs.
Superfluous, “junk”, instructions are not allowed within programs.
Translation of instructions is deterministic (i.e. it is not influenced by the environmental conditions at runtime nor is it probabilistic)
Although algorithms and programming methods have been specifically developed to emulate the evolutionary process (e.g. “Genetic Algorithms”, “Genetic Programming”), these also fail to provide the facilities of natural systems, are often cumbersome to deploy, and are not inherently designed to facilitate evolution. The deficiencies of Genetic Programming as a general purpose platform for evolving solutions to problems and for providing a computational platform with the facilities of molecular biology include:
Programs must be syntactically correct to be bred or evaluated.
Standard features of computer languages, such as looping, conditional logic blocks, and subroutines, cannot be implemented in the customary fashion.
Automatically created programs cannot themselves create, inspect, test, and terminate other automatic programs.
The behavior (number of inputs and outputs) of a program must be known in advance of breeding and evaluation.
Programs can't be marked to identify sites for mutation or other genetic operations.
The genetic lineage of programs can't be determined by examining the programs themselves.
Instructions are not interchangeable or redirectable.
Implementations do not provide for multi-tasking, e.g. the simultaneous evaluation of two or more evolvable programs.
The environment and instruction set cannot be altered while programs are running.
Genetic programming is a biologically inspired general-purpose search technique for discovering solutions to complex problems pioneered by John Koza. Typically implemented in LISP or C/C++, Genetic Programming involves creating a population of syntactically correct programs (in LISP) or data structures (in C), then breeding successive generations of syntactically correct programs or data structures guided by the Darwinian principle of “survival of the fittest.” Analogs of naturally occurring operations such as sexual recombination, mutation, and gene deletion are used to generate the programs. Utilizing this approach enables computers to develop solutions to a given problem without advanced knowledge of the form of the solution. For a further description of Genetic Programming see Koza, John R., “Genetic Programming III; Darwinian Invention and Problem Solving” (1999).
FIG. 1
demonstrates the concept of breeding programs. In this example, an application is contemplated that creates a picture by invoking two programs (A and B), which create an ellipse and a rectangle respectively. The concepts of “cross-over” and “mutation” are employed to generate variations of the original picture.
Referring now to
FIG. 1
, several pictures are set forth where each picture consists of two components, an ellipse (A) and a rectangle (B). In the original representation
102
, the application used coordinate data
50
50
150
150
to produce the ellipse, and
100
100
200
200
to produce the rectangle. Below original representation
102
are four exemplary representations depicting the concept of “cross-over.” For example, in representation
104
, it can be seen that the data elements after the first position have been exchanged. In other words, the four instructions following the first “50” in the ellipse program have been crossed over (i.e., swapped) with the four instructions following the first “100” in the rectangle program. The remaining three other such representations (
106
,
108
and
110
) have resulted from aspects of original representation
102
being crossed over in a similar fashion.
Representation
112
depicts the concept of mutation. Specifically, rather than simply moving around the same data provided by the original representation
102
, at least some of the data is mutated (i.e., changed), thus yielding different values, as shown. Thus, from using such concepts as cross-over and mutation, numerous “possibilities” can be created, one or more of which can then be selected by a designer according to his or her personal taste or objectively tested according to a machine-based fitness function such as maximizing the axial symmetry of the picture.
A fundamental problem in using genetic programming to evolve solutions to problems is that programs cannot be arbitrarily recombined without producing software with invalid syntax, nonsense logic, overflow errors, etc. Programs must have correct, balanced, “perfect” grammar to compile or even be interpreted. If a semicolon “;” is missing at the end of a line in a program written in C, or a “next” does not follow a “for” in a program written in BASIC, the software will not execute. For example, the code strip below returns the temperature in Fahrenheit given a Celsius value:
F
=(9/5*
C
)+32
If a cut is made after the multiply sign and the second part of the piece is recombined in front of the first part, the new code will appear as:
F=C
)+32(9/5*
If this new code were passed to a conventional computer for execution or a compiler for translation, the procedure would terminate at the second instruction “)” which has no meaning without a prior parentheses. Termination is an unrecoverable error that stops the entire computing process in the middle of execution and typically requires human interaction in order to resume. Traditional computing environments are therefore unsuitable for automatically evolving solutions to problems or designing a robust life-like computing system.
As noted above, existing virtual and silicon machines (computers) are not designed to process random code, and will halt execution on unhandled errors. In order to get around this problem, existing implementations of genetic programming impose rigid constraints on program breeding in order to ensure that programs will run. This restricts the space of potential programs to a sub-space of all grammatically correct or “legal” programs. This restriction may hinder the achievement of an optimal solution as all paths must be syntactically correct, thereby prohibiting “short cuts” or “trespasses” through the space of “illegal programs.”
In addition to syntactical errors, the arbitrary recombination of programs frequently
Bennett Gordon E.
Rice Todd M.
Chaki Kakali
Hale and Dorr LLP
Lamarck, Inc.
Vu Tuan Anh
LandOfFree
Toggling software characteristics in a fault tolerant and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Toggling software characteristics in a fault tolerant and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Toggling software characteristics in a fault tolerant and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3138101