Veterans of AI programming are familiar with the following anecdote. When asked to translate biblical phrase “The spirit is willing but the flesh is weak,” an intelligent English-to-Russian translation algorithm produced something like “the vodka was fine, but the steak rotted.” Automated software engineering teaches us a similar important lesson: machine-generated code has bugs, and certainly not less in quantity than human-generated code. The good news is that bugs in machine-generated code are more systematic and classifiable than the errors introduced by humans creating new code or fixing legacy systems.
Organizations facing the Year 2000 crisis have overwhelmingly opted for software remediation as a more cost-effective solution than the complete rewriting of their legacy applications. Semi-automatic tools for program analysis and remediation have become more and more abundant. Some of these are merely scanning tools, but others use sophisticated algorithms to perform program analysis and transformation. The latter are sometimes referred to as second-generation tools.
Most professionals now agree that a completely automatic solution is not feasible, not even for a single homogeneous environment (Peter de Jager is probably the best champion of this claim). As productivity is the name of the game, tool vendors tend to flash various productivity metrics in promotional materials and demos. Let us assume the vendor of the tool suite “EasyMoney2000” says: “our tool does 75% automatic conversion”. It is important to realize exactly what this claim means: 25% of the code must be fixed manually. Moreover, the part of the code that could not be done automatically is very likely to involve those problems that are especially difficult for manual fixing as well. So even if you trust the vendor's numbers, how much of the work does the tool save you? 60%? Less than 50%?
A good tool should provide productivity gains for a developer solving the tough cases.
But what about an area agreed to be the toughest Year 2000 issues of all, Mainframe Assembler?
Today, anyone with experience in the Year 2000 problem knows that for most analysis and remediation tasks, merely scanning the textual code is not enough. In fact, the code text is probably the worse medium on which to apply transformation. Patching code based on string-searches will undoubtedly introduce new errors during the fix process because a strings-only fix process is unaware the impact of substitutions on the flow of data in a module. Analysis and remediation tools are needed which leverage an awareness of data- and control-flow in an application.
In the late eighties, The Programmer's Apprentice project was conducted in the MIT AI lab, and the principal investigators, Rich and Waters[3], invented the “Plan Calculus” representation of program structure as a part of their effort.
Simply stated, the Plan Calculus is a canonical, mathematical abstraction used to describe imperative programs, and is based on the insight that programs can be seen as the combination of their control-flow and data-flow. This underlying structure is consistent while the syntactic variations among programming languages are not essential for program understanding and manipulation. While it is straightforward for software engineers to grasp the meaning of the control-flow of a program, it is usually more difficult to quickly visualize the data-flow in a complex application (unless a data-flow language is being used). Plan Calculus allows an automated analysis in which the control-flow is abstracted from a program, and then the data-flow is abstracted. A “plan” in Plan Calculus is a superimposition of these two abstractions, which can be made human-readable with the use of a neat notation convention.
The Programmer's Apprentice was not transferred from the MIT AI lab into the real world until Yishai Feldman, a research scientist, brought this knowledge back with him to Israel. Since then, Sapiens International has tried to adapt this elegant technique into real world prototypes and commercial products such as: automatic translation from IBM Assembler to portable C [1]; automatic reengineering of database programs [2]; and automatic translation of 3GL programs into 4GL tools. The technique is now being extended to deal with object orientation and 4GL data-directed programming style.
The best proof that this is a truly useful, general paradigm came from the Year 2000 crises. When a tool for the analysis of Assembler code (for automatic translation to C) was implemented, the Year 2000 issue was not a part of the project. However, a simple analysis component for tracing date occurrences in Assembler code was derived in just four weeks. This component was incorporated into the translation system, replacing the translation-to-C component. This was enough to bring out an Alpha version of an analysis tool superceding, by far, any of the “first-generation tools.”
Any impact analysis must start with some first-level “seed” objects or Places from which further syntactical, lexical, or structural analysis can proceed to develop the “impacted code” identification. Several sources can be used as seeds, which we will call Primary Suspects: keyword patterns, user-supplied information, or cross-program information for example. The analysis shows how these variables impact other variables in the program code, thus generating Secondary Suspects. All other variables in the program may be regarded as Neutral, and should not join the impact graph. So far, this is what most first-generation tools do. However, due to the limitations mentioned above, I stress that we must accommodate user-supplied information or “tuning” in the analysis. To best accommodate this user input, the impact analysis must be implemented as a dynamic process, carried out as iterative refinement with user assistance. For this reason, we have two new types of state for Places: Primary Innocent, and Secondary Innocent.
The Primary Innocent are those that are forced by the user to be innocent, and the Secondary Innocent are those that become innocent due to the propagation of information on the impact graph. (Note that the user may often force new Suspects as well.) Here the mathematics become a little bit messy, and clear semantics are required, which is outside of our scope. It suffices to say that we usually don't want to regard suspect and innocent as symmetric. For this reason, for example, a Secondary Suspect behaves like a Neutral Place for all purposes. We have also discovered that, during information propagation, a Place should change to be Secondary Innocent if it has no directed path to any Primary Suspect.
We call each connected component of the impact graph a “Clique” (note that this usage is different from the “clique” term in graph theory). This concept makes its way into the program inspection methodology: if a developer wants to inspect a date-intensive program, she may first check if entire cliques were missed by the system. He or she can then proceed to trace each clique by itself, and see if it may be pruned or discarded as a whole. Typically, it is enough to inspect the seeds of the clique, or the points with minimum connectivity. This way, the developer may eliminate many positive- and negative-misses in one operation. Our experience reveals that even the smallest and simplest programs typically have a few large and complex cliques.
Indentifying the variables to be changed is only a first step. A fixing policy must to be decided upon, the exact date formats have to be defined, and a methodology of code replacement has to be chosen – all with an eye to minimizing the danger of causing side effects.
The most common remediation policies are “date-windowing” (fixed or sliding) and field expansion. While date-windowing is usually simpler, there are cases in which it cannot be used: when dates are used as keys, when the date range is higher than one hundred years, when federal laws require expansion, etc. This means that, in practice, many applications will be remediated according to a hybrid policy -- some of the variables will be expanded, some windowed -- and they may participate as operands of the same instruction. This is further complicated by the fact that the policy chosen for shared variables has a cross-program effect. This is another part of the remediation that might best be done manually, perhaps by a project manager. At a minimum it should allow for manual confirmation of the fix algorithm's recommendation.
Deciding which instructions need to be altered, under a given fixing policy, is usually straightforward. But even this becomes complicated when analyzing Assembler 370 code. We know that equal and non-equal comparisons do not require change, while greater-than and less-than comparisons do (in a windowing remediation scenerio). But in IBM Assembler, this takes place in several instructions: one instruction sets the condition code, and others check it and branch upon its value. These instructions may be non-consequent, and possibly remote. For example, assume the following code:
CLC YY1,YY2 ................... compare two date variables
BE L1 ............................... branch if equal
- code that does not set condition code -
BALR R14,CHECK2 ........... branch to routine CHECK2
A human developer (or a not-sophisticated-enough tool), may decide the compare instruction does not need intervention, since the condition tested for is strictly whether or not the values are equal. However, this may cause a subtle bug, if the condition code is tested inside the routine CHECK2, before it is reset:
CHECK2 DS 0H
- code that does not set condition code -
BH SOMEWERE ..........branch if 1st value was larger than 2nd value
This example serves to illustrate the importance of a complete control-flow and data-flow analysis. Note that the usage of the Plan Calculus perfectly fits this example; in fact, the information about the second and problematic usage of the condition code is a by-product of it.
An important concept in the Programmer's Apprentice project was that of the “programming-clich?.” A clich? is a generally used (and reused) algorithmic code fragment such as: sort a list, binary search, get the absolute value, etc. Theoretically, a program is a collection of such clich?s, and a programmer trying to understand and manipulate a program has to indentify these clich?s. When programs are transformed into the abstract representation of Plan Calculus, clich?s are simply sub-plans. The process of semantic extraction can then be implemented as a graph parsing algorithm.
In a previous paper in the AI Journal [2, with Yishai Feldman], we claimed that there is still a large gap between automatic program understanding demonstrated on toy problems in the laboratory, and the application of these techniques to large real-world programs. In other words, the techniques don't scale. However, the approach of the year 2000 provided an opportunity to try again. Luckily, we do not have to “automatically understand” complete programs; we try to concentrate only on the date-related clich?s, and this is a feasible effort.
Date-related clich?s may exist at several abstraction levels: from one instruction to several non-consequent instructions implementing a well-defined task. Clich?s may help to expose the exact date format of a variable, which is required for automatic transformation. Clich? matching may also be used to locate code fragments, to be automatically replaced by year 2000 compliant code including format conversion, validity check, or leap year computation.
Non-compliant code may be replaced inline by macros or by subroutine calls. In any case, it should be made certain that no harmful side effects are introduced. For this reason, complete control-flow and data-flow sensitivity is a must.
Unfortunately, a complete data-flow analysis of programs with aliasing (languages that allow pointers) is undecideable. (For non-mathematicians: this does not mean that the problem is difficult, or that it's a question of money – it means it is impossible.) That is, there may be cases where a specific code segment cannot be fully analyzed, meaning that the automatic alteration of code risks the introduction of new subtle bugs. The tool should at least be aware of these circumstances and issue a warning, or consult the user.
A more mundane and frequent problem might often occur: as changes are being made, the program starts growing. In this case performance effects are probably negligible, but in IBM Assembler another problem might be encountered: every code and data segment should be “based” by a general-purpose register. Each such register can base only 4096 bytes. There are only 16 such registers, and they are also heavily exploited for computations. Old programs typically use these registers up to the limit, and once the programs grows, even slightly, the programmer runs “out of registers”. Using program abstraction into Plan Calculus, it is straightforward to design a tool that suggests free registers and temporary variables, to assist both automatic and manual code replacement.
It now seems likely that the Y2K crisis will open a new market for automatic software conversion and transformation. On the one hand, the organizations surviving the crisis will understand the risk of old code. On the other hand, there will be many vendors who, having invested in their tools, are looking for additional revenue opportunities.
If quality wins, only the sophisticated, “second-generation” tools will survive. These can be easily and efficiently adjusted to carry out various maintenance tasks: language translation, automatic documentation, component reuse, and functional transformation. With attention changing focus from the development stages into the maintenance tasks, the software development community may finally address its real problems. The Year 2000 crisis may serve the software industry by forcing it to increment one generation in dealing properly with code maintenance. After all, what is the Year 2000 problem, if not a small and simple maintenance task?
Y. Cohen and Y. A. Feldman. Automatic high-quality reengineering of database programs by temporal abstraction. In Proc. Twelfth Automated Software Engineering Conf., Nevada, November 1997.
Y.A. Feldman and D.A. Friedman. Portability by automatic translation: A large-scale case study. Artificial Intelligence, To appear.
C. Rich and R.C. Waters. The Programmer's Apprentice. Adison-Wesley, Reading, MA, and ACM Press, Baltimore, MD 1990.
Doron A. Friedman is a research scientist at Tel Aviv University, specializing in applying Artificial Intelligence techniques and principles to the domains of software engineering and animated virtual environments. In the last year Doron has been been a consultant for Sapiens International in the creation of Falcon2000, a tool for automated analysis and remediation of IBM Assembler programs. For more information on Falcon2000, Sapiens site: www.sapiens.com, Email: info@sapiens..com, Voice: (800-774-2505).