Programmer 7500

home *** CD-ROM | disk | FTP | other *** search

/ Programmer 7500 / MAX_PROGRAMMERS.iso / CLIPPER / MISC / AIE8911.ZIP / SPECS.COL < prev next >

Wrap

Text File | 1989-08-31 | 12.5 KB | 284 lines

NOVEMBER EXPERT TOOLBOX Note to editor: is used to mark the start of italics. <R> is used to mark the end of italics. Do not leave these in the text. For example, if I write the halt<R> predicate you would put the halt predicate in the text with 'halt' in italics. ------------- Column starts here --------------------------------- EXECUTABLE SPECIFICATIONS One of the big problems in software development is the Catch 22 of system specifications. On a project of any size it is necessary to write specs to guide the implementation. In theory, the implementation follows the specs and the resulting system does what you want. However, in practice you are never 100% sure that a system meets its specs. There is also no way of knowing if the specs themselves are correct. This is because correct specs are those for which a true implementation does what the user wants -- something you can't test, since the system isn't implemented yet. One way out of this dilemma is specification testing. Put the specifications in an executable form, for example a rapid prototype, and run them to see if they do what you want. Executable specs have several advantages: * You can spot bugs in the specs early on, when the cost of fixing them is relatively small. * End users can see if the system appears to meet their goals before implementation starts. * A new development or maintenance programmer can use the executable specs to learn about the system. Running a model system gives you an overview that is hard to get by reading a bunch of data flow diagrams. However, executable specs also have drawbacks: * The programming needed to make specs executable may not become part of the final system. This specification programming, for example to develop a rapid prototype, is an extra up-front cost, which may or may not be recovered by having fewer errors in the final system. * The programming language gobbledygook needed to make the specs executable also clutters them up. Instead of reading English or looking at diagrams, you may have to read code. It may be hard to separate the particulars used to execute the specs from the more abstract properties desired in the final system. To provide the advantages of executable specs while minimizing the drawbacks -- which can not be entirely eliminated -- I have written a specification interpreter (SI) in Prolog. Advantages of this approach are: * Prolog code is semi-logical in nature. In addition to implementing executable specs, the code describes logical properties of the system. Programming details are less visible in Prolog code, because Prolog handles many control and data structure details automatically. * The specification interpreter also executes system components described in English, by analyzing the description and using the information to construct a simulation. This lets the SI execute specs before the more exact and detailed Prolog has been written, or when the user just wants a high-level view of the system. * The SI works on partially complete -- in fact very incomplete -- specs, by generating and calling simulation code for the missing parts of the system. We exploit Prolog's tools for code generation to help the analyst check out partially complete specs. SOME EXAMPLES Before we bog ourselves down in implementation details, let's look at some examples, shown in Listing 1. Each process in the target system is defined by a stub<R>, and optionally also by Prolog code. The stub contains some minimal information about the process: its purpose<R>, an English phrase describing what the process does, and its call<R>, a term showing how the process is called. When we execute a specification, the process requested directly by the user and each subprocess called during the resulting computation is executed using either Prolog or stub definitions. Processes defined in Prolog are generally executed in Prolog, while those defined by stubs are executed using stubs. (The user may, however, use stubs instead of Prolog to obtain a detail-free view of an executing system. For details, see the complete SI program on the AI Expert and Instant Recall BBSs -- (301) 983-8439 for Instant Recall). Specification 1 is a very minimal specification for checking housing survey data. The specification interpreter recognizes that the process is defined as a stub only, and that this stub describes an action, rather than a branch, loop or other specialized process. Therefore the SI turns the purpose<R> of the process over to an action simulator, which does all that can be done with so little information: tell the user that the process would be done at this point when the system runs. Now suppose the systems analyst works another minute or two on the housing specs, producing the more elaborate Specification 2. Here the top level process is defined by Prolog as well as a stub. Using information in the subprocess stubs, this Prolog translates into If the data is collected for a record, put it in the sample. Otherwise, write an error message. Even if you don't write Prolog, you can read it with a few minute's practice; it's an uncluttered notation for expressing relations among the subprocesses -- and it executes in a Prolog interpreter. Actually, we'll execute Specification 2 not in an ordinary Prolog interpreter, but an enhanced one, the specification interpreter, which looks for stubs as well as code. When we do this, we get the second execution trace shown in Listing 1. The increased detail of this trace reflects the increased detail of the second spec. Notice also that the SI recognizes data_collected_q<R> as a branch, and interprets its stub accordingly. The third example shows a process defined only by a stub. However the purpose<R> of this process describes a loop, and the specification interpreter executes a loop, simulating the process inside the loop. THE EXTENDED INTERPRETER Listing 2 shows the top level of the specification interpreter. The top level predicate do_goal<R> is essentially just a simplified Prolog interpreter in Prolog. In fact, if you left out the first 2 rules of do_goal<R>, you would have left a very no-frills Prolog interpreter -- one with no cut<R>s or or<R>s in the rules. (You can add these features with some additional rules for do_body<R>.) As an extended Prolog interpreter, do_goal<R> has to recurse and backtrack. do_goal<R> recurses because do_goal<R> calls do_body<R> and do_body<R> calls do_goal<R>. do_goal<R> backtracks because the Prolog rules which define it and its helper predicates backtrack. What transforms do_goal<R> from "Prolog in Prolog" into a specification interpreter is the first rule of do_goal<R>. This says that if there is a stub matching a Prolog goal, and it is appropriate to use it, then interpret the stub, for example because there is no Prolog rule matching the goal. The top level of the stub interpreter appears in Listing 3. The stub interpreter looks at the purpose<R> of the stub, an English sentence fragment, and decides what kind of process is described, e.g. branch, loop, action, etc. Then the stub interpreter calls a specialized helper procedure to interpret that kind of process. Listing 4 shows you how loops are executed based on stub information. This predicate (Prolog procedure) extracts the information it needs, such as the action inside the loop, from the English-language purpose<R> in the stub. Then it uses this information to synthesize the Prolog code needed to simulate the loop described in the stub. For the stub from Specification 3 in Listing 1, the generated loop code is shown in Listing 5. If you need to generate a little code at runtime, Listing 4 shows you how to do it in Prolog. The general plan is * get rid of any old code that might confuse the system, using the built-in predicate abolish<R> * Use patterns to construct the new code * Assert the code into the Prolog database * Call the top level goal of the new code There are a couple details to observe in doing this: * You can put variables in your patterns. If the variables stand for program segments, you can define the value of those segment variables before or after their owner patterns -- as long as the segments are defined before you put the rules containing them in the Prolog database. * If you define patterns as I did, with terms of the form <variable> = <pattern>, it's a good idea to put parentheses around the pattern, to make sure the '=' is performed after all operators in the pattern. * If you define the rules of a predicate in their intended order -- the sensible thing to do -- put them in the database with the queuing predicate assertz<R> rather than the stacking predicates asserta<R> or its synonym assert<R>. (Some Prologs make assert<R> a synonym of asserta<R> and some of assertz<R>; I avoid it for this reason.) LINGUISTICS FOR ENGINEERS Many of the helper predicates of the stub interpreter use information from the English purpose<R> in the stub. The predicates that extract this information are in Listing 6. We have used really hokey predicates to find the verb and object of the stub purpose<R>. We could get away with this because we require the user to write process descriptions as the predicate (in the grammatical sense) of a single English sentence. This requirement still affords the analyst a lot of descriptive freedom, but limits the amount of linguistic processing needed for the spec interpreter. It is important to limit linguistic requirements, so development effort can be directed to the more crucial area of simulating additional process classes (e.g. menus and file I/O) and data descriptions to the SI. With the analyst restricted to sentence predicates, let's look at the questions we have to answer from the purpose<R> of a stub: Does the stub describe a branch? A loop? Some other special kind of process? To find out, look up the verb in a list process-classifying words. Because we have limited the literary creativity of the specification writer, the verb is the first word in the purpose<R>. Is the action performed on a single item or a loop? To find out, see if the head of the main noun phrase of the verb object is plural. This is the first noun phrase after the verb. The specification interpreter also has to do transform the purpose<R> into an action-completed message, to inform the use when a process in a loop has been performed. The code that does this is in Listing 7. Again, from a linguistic standpoint the code is very incomplete. It overgeneralizes regular verbs in forming the past tense of verbs, as a small child does. The result is somewhat inelegant, but understandable and simple to implement. The singular rule is the most obviously incomplete -- and for a reason. While the rule fails to find the singular of mass nouns like sand<R>, this failure is really a kind of conservatism built into the system. For if a processed item is identified as plural, it is processed in a loop. By recognizing only unmistakable plurals (OK, I know it messes up words like pants<R> -- fix it if it matters) the system simulates a loop only when there is strong evidence for one. AN AI DEMO FOR ANALYSTS This specification interpreter illustrates the potential for AI to help in the software production process. It also illustrates how current AI tools -- in this case Prolog -- make symbolic programming easy. The whole program took less than 2 days, although I did start with some code from Instant Recall's Prolog Tools. The specification interpreter also illustrates a particular design philosophy, which I will call the Schultheisz approach, in honor of our firm's business manager: Wait and see if you really need something before investing in it. It would be easy to improve the SI's natural language processing, but is that the most important improvement to make? Instead of making every part of the system smart, build a minimal system and let the domain specialist tell you what should be improved. His or her judgement is almost certainly better on this than that of an AI expert without domain expertise. By starting with a minimal expert system and letting the domain expert guide development, effort goes where it most improves the system.