Printer Friendly

Three new-generation software environments.

As a result of the Soviet computer project START, a number of intelligent software environments have been developed. In the heart of these environments lies structural program synthesis--an automatic program synthesis technique developed in the Estonian Academy of Sciences and initially implemented on old mainframe computers [4]. This program synthesis technique can be considered as a particular method of logic programming--propositional logic programming [12].

We accepted logic programming as a fundamental paradigm of the future generation of software development. However, we saw that attempts to build dedicated Prolog hardware as well as use Prolog as a single basic programming language for the next generation of computing were not successful. Therefore, we took a different and more general view of logic programming: we saw it as a way to exploit the structural similarity of constructive proofs and programs, without relying on Horn clause logic and resolution principle. Before starting this project, we had positive experience in practical program synthesis using the PRIZ programming system [4]. Because the logic background of our approach is the intuitionistic propositional calculus, we refer to our approach as propositional logic programming.

Our second software paradigm is merging several knowledge representation forms in a single system. This approach enabled us to build an intelligent programming environment called New Utopist (NUT [10]), where traditional programming tools like the C language are combined with object-oriented and logic programming facilities included in the NUT language. This language has been developed from the input language of the PRIZ system which was called UTOPIST. This language combines the basic features of Smalltalk (objects and classes), UTOPIST (propositional logic programming) and Prolog (Horn clause logic programming). The viability of combining various knowledge representations into a single knowledge-based system was demonstrated earlier by a software product called ExpertPRIZ. This is an intelligent software environment for personal computers developed in the START project and is now distributed also on the Western market.

NUT and ExpertPRIZ are two rather different knowledge-based programming environments, one being quite sophisticated and the other extremely simple; hopefully ExpertPRIZ is suitable for beginners in the AI field in the same way that the BASIC language is appropriate for beginners in the personal computing field. There is an intermediate system called C-PRIZ, which is an intelligent programming tool intended for software developers on workstations or sufficiently powerful personal computers. These three programming environments have to cover a wide range of needs of program development in the new generation computing--from personal computing to sophisticated software systems in computer-aided design.

Large-Scale Knowledge-Based

Programming

Our goal is to apply knowledge-based programming for constructing large application programs or, at least, practically useful programs in an interactive computing environment. Let us take (together with the user) a pragmatic view of a program: we will think of a program as a large modular entity rather than as an expression in a formal language. This is the view of a program represented in Figure 1. The user giving an input and getting an output sees only a small part of the program because it is hidden in the computer like an iceberg under water. Our goal is to build such icebergs, putting together small and large program modules and gluing them by means of calls or message sending.

Taking a closer look at a program, we see more details--data and control links between its pieces (see Figure 2). Five program modules a,b,c,d,e are shown in Figure 2a, connected by data links which are routes of passing values of variables (s,t, ... ,y). The variables u and v are linked with the module c in a special way. They are no input or output variables as all the other variables are. Different values of these variables can be passed repetitively during one execution of the module c. One can say that modules d and e must be called from c in accordance with the control structure programmed into c. It can be proved that a program schema in Figure 2b for a program computing y from x can be found by a simple algorithm from the description given in Figure 2a, which contains only data links of the program. We shall call the schema in Figure 2a together with interpretations of program modules program model, and the schema in Figure 2b control structure of a program.

It turns out that a language which contains no more details than are used in Figure 2a (i.e., which contains only a few kinds of data links between program modules) is sufficiently expressive for representing any algorithm (recursive function), provided we have two preprogrammed operators: iteration and minimization which can be copied and used many times as different instances of modules.

The data links designated by dotted lines in Figure 2a play an important role, providing generality to the language of program models. We call the pair of links from c to u and from v to c in Figure 2a a subproblem for c. The meaning of the subproblem is that c can be used in computations only if the problem "computers v from u" is solvable. Programs for solving subproblems must also be synthesized automatically and they appear as parameters for program modules with subproblems.

There are three levels of knowledge application for programming (see Figure 3). The lowest level corresponds to encoding of algorithms in the form of programs which can be efficiently run on a particular computer. This also includes program transformation and optimization. As an example, one can take local optimization of the assembler code; this is done by means of expert systems for supercomputers. Another example is using knowledge about a hardware configuration for code generation [8]. A number of works consider automatic programming as developing executable programs from given specifications which are more or less algorithmic representations of problems. On this level one needs knowledge about efficiency of computations [1].

The upper level that is also closest to the user is intelligent interface which requires yet another kind of knowledge--language knowledge as well as scenarios and dialogue models.

The central part of programming is building the algorithm itself. This requires knowledge about problem domain and will be discussed in more detail.

In this article we are primarily concerned with the second level, program synthesis, and with representation and usage of various kinds of problem-domain-oriented knowledge. Some attention is also paid to user-oriented languages, but hardware-oriented knowledge is almost completely ignored.

Program Synthesis

All knowledge-based programming environments considered in this paper include automatic program synthesis facilities for processing problem statements of the form:

[Mathematical Expression Omitted]

which means "knowing s compute y from [x.sub.l.], ... ,[x.sub.k]." The following is an example of the problem statement:

[Mathematical Expression Omitted]

It is assumed that given a specification of s it is possible to obtain the value of y depending on the given values of [x.sub.l], ... ,[x.sub.k].

Actually, any of these systems does more than calculate the value of y. It proves the solvability of the problem and from this proof derives a program which calculates the needed value. If the solvability cannot be proved, then we say that the problem statement is semantically in alid.

One needs very efficient theorem-proving methods for the purpose of program synthesis, because a theorem must be proved for every problem statement. We have developed a particular theorem-proving strategy which is applicable for a special class of theories which will be described next.

Let us start with a look at the representation of "pieces of programs" from which a resulting program has to be constructed (i.e., modules in our case and preprogrammed predicates in Prolog). Having a program with precondition P(x) and postcondition R(x,y) we can specify it in general by the formula:

(Ax) (P(x) [right arrow] (Ey)R(x,y)) (1)

which can be considered as a specific axiom of a theory about the problems

and programs of a particular problem domain.

In the case of Prolog the same information is represented by an atomic formula of which the following is an example:

Q(x,y).

In various contexts such a formula can be used in either of the following ways:

(Ax)(Ey)Q(x,y)

or

(Ay)(Ex)Q(x,y).

However, if we accept that the properties of preprogrammed functions are precisely represented by their programs and there is no need to specify in detail by axioms how the result y is related to the input x, then we can use simpler formulas as axioms, namely:

(Ax)(P(x) [right arrow] (Ey)R(y)). (2)

In this case we can remain in the scope of propositional calculus which is much simpler than predicate calculus. Indeed, the last formula is equivalent to:

(Ex)P(x) [right arrow] (Ey)R(y),

but (Ex)P(x) and (Ey)R(y), are closed formulas. It turns out that during the program synthesis we do not need to analyze the structure of these formulas; we can denote them simply by propositional variables, for instance, X and Y, obtaining axioms of the form

X [right arrow] Y

where X and Y mean respectively "there is a value x satisfying P" and "there is a value y satisfying R." This formula is an implication "X implies Y," but we will always use it with the following meaning:

"a value y satisfying R can be computed from any given value x satisfying P."

(We can interpret the same implication as an abbreviation for

(Ax)P(x) [right arrow] R(f(x)))

that explains the expansion (5) of the implication below.)

Restricting logical specifications of program modules to the formulas of form (2), a precise representation of the semantics of specifications can be given in a simple language which is still universal language of the intuitionistic propositional calculus [6]. The propositional variables X,Y etc. express the computability (existence) of values of objects presented by a specification. Let us denote the objects by small letters: a, b, x, y, [a.sub.1], [a.sub.2], . . . . For any object x we introduce a propositional variable X which denotes the computability of x. (X is true if x is computable or x already has a value.) The language includes only propositional formulas of the following forms:

[X.sub.1] & ... & [X.sub.k] [right arrow] Y, (3)

or in a shorter way: X [right arrow] Y; as well as

(X [right arrow] Y) [right arrow] W. (4)

From the computational point of view, these implications can be considered as functional dependencies. The formula (3) can be read simply "y is computable from [x.sub.1], ... ,[x.sub.k]." The formula (4) expresses functional dependency of a higher order (with function as argument) and can be read "w can be computed from a function realizing X [right arrow] Y."

To analyze the solvability of the computational problem given by a problem statement and to find the applicative structure of the resulting program, only the purely propositional structure shown explicitly in (3), (4) is essential. However, to write the resulting program in all details, formulas (3), (4) have to be expanded as follows

X [[right arrow].sub.f] Y (5)

and

(X [[right arrow].sub.g] Y) [[right arrow].sub.F(g)] W. (6)

Functions f, F in (5), (6) are realizations of (3), (4) respectively. The formula (5), for example, means that the realization of y can be computed from the realizations of [infinity] by means of f, or that f is a procedure for computing y from x. The formula (6) means that the procedure F produces from any function g computing y from x some new function F(g) computing w.

In this section we have specified a new language for representing program models in which each module and each subproblem is represented by an implication. The model in Figure 2a can be represented now as follows:

X [[right arrow].sub.a] S

S [[right arrow].sub.b] T

T & U [[right arrow].sub.d] W

W [[right arrow].sub.e] V

(U [right arrow] V) [[right arrow].sub.id] P

P & X [[right arrow].sub.c] Y

where id means an identity function.

Now we can also justify this statement that we can derive control structure of a program from its model. This control structure coincides with the structure of a proof of the formula X [right arrow] Y where X corresponds to the input x, and Y to the output y of the required program.

The logic of our program synthesis and its relation to program models is discussed more thoroughly in [11] where inference rules for building proofs are given. It may be interesting to note that there is a fine classification of theories which can be built in the propositional language described here [3]. If a parameter r show the maximal depth of nested module calls in texts of programs which are synthesized, then the time-complexity of the algorithm for proof search (and for program synthesis) is

O(l*[n.sup.r])

where l is size of a theory (i.e., number of instances of propositional variables in axioms), n is number of instances of modules with calls of other modules. This shows very clearly that an ordinary constraint propagation, when modules are executed one after another without calls of modules from inside other modules, needs only linear time (r = 0). But the general case of program synthesis, being equivalent to a P-space complete problem of proof-search in the intuitionistic propositional logic, has exponential time-complexity.

A Simple Specification

Language

Unlike Prolog, the logical language of specifications outlined here cannot be used as an input language for writing specifications by hand. It is a low-level language in which even small program specifications may contain a large number of axioms. This language appears only as an internal language of our systems for program synthesis. Special declarative input languages were developed for ExpertPRIZ, C-PRIZ and NUT. These languages have a common core which is presented in Figure 4.

A specification is of the form

a:t

where a is a name of a new object and t is a type specifier which can be any of the following:

* a primitive type,

* a name of an already specified object,

* a structured specification, containing possibly superconcepts, specifications of components of the object a and relations which represent the properties of a.

The relations can be in the form of algebraic equations and external specifications of functions.

Default typing of numeric objects enables us to drop specifications of numeric components and turns this language immediately into an equational language, in which we can write, for example, a specification of a concept "accelerated motion" in the following form:

motion: (f=m*a; v=a*t; s=t*v/2)

Any object can be used in this language as a prototype for specifying new objects, and amendments in the form of equalities can be made to prototypes:

falling: motion m=700, s=3.5, a=9.81; pushing: motion m=falling.m, s=0.05, v=falling.v

We can take the given four lines as a formal specification of the following situation:

"A body with the mass 700 kg falls from the height of 3.5m onto a pole and pushes the pole 5 cm deeper into the soil."

A number of problems can be solved on the basis of this specification by simply phrasing the question: if y is computable (or if y is computable from x) for any objects y (and x) specified by these two lines. (There are 14 such objects: falling, pushing and their components falling.f, falling.m etc.)

We are able to describe the precise semantics of this core language by giving rewriting rules for transforming any specifications S written in this language into a set of axioms sem(S) in our logical language. These rewriting rules are given in Figure 5.

Using sem(S) and the inference rules given in [11], we can get the answer to the question of whether y can be computed from x where x and y are any objects from the specifications S. If the answer is positive, then we get the needed algorithm from the derivation of the formula X [right arrow] Y which denotes the computability of y from x.

ExpertPRIZ

This is the smallest programming environment among the knowledge-based programming environments discussed here and it is for wide usage in personal computing. It has its own graphic interface and can be used under MS DOS directly. The highest priority was given to its user-friendliness and simplicity. It has already gained some recognition in the Soviet Union and is also known in Scandinavian countries [9].

The ExpertPRIZ combines a program synthesizer with an expert system shell and database management system, Figure 6. At any moment in time, the user can work with one expert knowledge base, one database file and one knowledge base for program synthesis. All parts of the system interact in the object-oriented way, passing messages to each other. A program library for graphics and data manipulation is accessible directly through the user interface of ExpertPRIZ.

The input language of ExpertPRIZ is a declarative language close to the core language described above. It differs syntactically in the sense that some punctuation marks are omitted. The primitive type undefined provides some restricted polymorphism facility and symbolic computation option is added. Besides equations and functional dependencies, data structures can also be represented as relations.

An example of programming in this language is shown in Figure 7 where various mechanisms are specified using a concept of a bar which is an interval of a straight line. Cumulative knowledge representation facility can be observed here. Starting with a simple concept of a point, the concepts of a bar and a connection of two bars (mchO) are specified. Thereafter, using super-concept facility, a slider-crank mechanism and a slotted-link mechanism are represented. Instances M1 and M2 of these mechanisms are specified and used for numeric and symbolic problem solving. Only the concept table is not specified immediately in this text and contains a preprogrammed module for iterative computation and tabulation of the component fun for various values of the component arg. This example demonstrates the following features of the language:

* multiple inheritance,

* usage of prototypes with amendments as type-specifiers,

* polymorphism,

* symbolic computations.

The usage of the language resembles object-oriented programming. However, classes and objects are not distinguished in Expert-PRIZ and any object could be used in the role of a class for specifying a new object. An object comes into existence immediately when its specification is processed, but its value may be partially or totally undefined (i.e., nil). Another difference is in the control flow between the program modules: a hilerarchical program representing a control structure for solving a given problem is synthesized in advance and no message passing is used in synthesized programs.

C-PRIZ

C-PRIZ is a personal programming environment which covers the capabilities of ExpertPRIZ and, additionally, contains conventional programming tools--C language and its libraries. This adds considerable flexibility to program development. One does not have to give a complete declarative specification of a problem, but can write by hand parts of a program for any particular problem. Based upon its functionalities, C-PRIZ is an intermediate system between ExpertPRIZ and NUT and will not be considered here in any detail.

NUT--An Object-Oriented

Programming Environment

The NUT programming environment has been developed for use on sufficiently powerful workstations with good graphics. In the framework of the START project, it has been implemented on workstations with Kronos processor [7]. It includes a general-purpose programming language supporting object-oriented programming style; and it combines several knowledge usage and programming techniques including the principal features of Smalltalk (objects and classes(, automatic program synthesis developed in programming systems of the PRIZ family, and Horn clause logic of Prolog. The latter is intended for meta-level reasoning about problems and specifications, not for low-level computations. That preserves computational efficiency when providing generality and logical power.

The basic concept of the NUT language is object. Programs, data types, files, etc. are objects. A user can manipulate objects by means of various commands. In general, any command initiates a complicated process which may involve a number of objects unknown directly to the user. Compared to other object languages, NUT includes more knowledge representation and usage mechanisms. Specifications in the NUT language are similar to specifications written in the core language described above and can be used in problem statements written anywhere in a program.

Environment

The NUT environment supports the following three levels of knowledge:

* abstract general (knowledge about a problem domain).

* abstract special (knowledge about a particular problem),

* concrete (knowledge about objects involved in the problem).

Abstract general knowledge is represented in packages which contain classes and rules. Abstract special knowledge is represented in a working context containing all active classes, rules and objects. Concerete knowledge is represented in the form of objects of a particular problem.

Classes are representations of concepts in the computer; for instance, we can specify the classes: triangle, maximum of a function, etc. Objects are instances of concepts--of a particular triangle, of a maximum of a particular kind of function, etc. Rules express general laws applicable to classes and objects and are used for meta-programming.

There are several operating modes of the NUT system corresponding to different levels of knowledge. Every mode has its own windows on the screen. Selection of a mode is done by activating its window.

The package specification mode supports functions for specifying a new package by defining new classes and rules directly in the NUT language, as well as by using the parts of existing packages.

Working context can be generated by selecting a package and a class which is then considered as a problem specification. The working context is generated and modified in a computational mode in which computations are performed with objects of the working context. Permanent knowledge of the NUT system is stored in a knowledge base which consists of packages and working contexts.

Classes and Objects

A class is a carrier of knowledge about the common properties of objects belonging to the class. When an object belongs to a class T, we also say that the object is of the type T. There are six predefined classes:

ool, numeric, text, array, prog and any.

A class represents the structure of objects belonging to this class and functions applicable to them. A class may also describe the initialization of components of objects. In the text below we briefly illustrate the following features of class specifications:

* inheritance

* initialization

* virtual components

* relations in the form of equations

* relations in the form of programs

* classes as prototypes

* amendments to prototypes

* polymorphism

In a simple case of a class specification, only components of the class are specified. The specification

point: (var x: numeric; y: numeric)

describes a new class of objects with two numeric components: x and y. A new class can inherit all properties of another class which is called superclass in this case:

zeropoint: (super point; init x:=0; y:=0)

It is specified also that when an object of this class is generated, its components are initialized to 0.

Functions are specified in the form of relations in the same way as in the core language. A relation may be either an equation or a program. The following specification of a class of complex numbers illustrates the use of equations:

compl: (var re: numeric; im: numeric; vir arg: numeric; mod: numeric; rel rl: cos (arg)=re/mod; r2: mod 2=re 2+im2)

In this example virtual components appeared which can be used in computations but are not parts of any object (i.e., they are not computed automatically when an object is computed). An object of the type compl has only two components--re and im, but it also has two virtual components--arg and mod--which can be used in computations. For instance, if arg and mod are known, the relations r1 and r2 can be used for computing re, im and the value of the whole object which is a pair (re, im).

The specification of a concept of set is another example of a class specification:

set: (var value: any; vir elem: any; key: any; selector: numeric; rel r1: value, selector [right arrow] [prog A]; r2: value, key [right arrow] elem [prog B]; put: value, elem [right arrow] value [prog C];

In this case we have three relations: r1, and r2 and put represented by programs A, B and C respectively. The relation r1 represents a function for finding an element from its number (selector); r2 represents a function for finding an element by the key; and the relation put adds a new element to the set which is represented by the component value.

Let us note that the relation put cannot be used automatically in a synthesized program because the implication.

VALUE & ELEM [right arrow] VALUE

is a tautology and will never be automatically included in any proof. But this relation can be called explicitly in programs and it is obviously useful for building a set step-by-step.

Any class can be used for specifying the types of components of new classes. For instance,

symmetricpoints: (var P: point; Q: point x=P.y, y=P.x)

is a new class of objects with two components of the type point. Amendments can be made in types represented by classes. They are written immediately after the class name as in the specification of the component Q of symmetricpoints.

The following is a more complicated example of an amendment where a type of a component is changed:

points: set elem=point;

This example demonstrates that the predefined class any provides polymorphism to the language. A component of this class can be bound to an object of any other class. We can also say that in the present example the component elem of the set class is regarded as a slot and the point class is substituted into this slot.

All computations in NUT are performed with objects. Every object belongs to a class and has a value (which may be nil). An object may have an external name. The class of object determines the operations which can be performed with the object. During the computations the objects can be treated, changed and deleted. The value of an object can be requested and assigned to another object.

When an object is generated, its components are initialized according to the specification of its class. If the initialization of a component is not specified, then its value is set to nil.

The following predefined objects exist:

1) numbers (integers and real numbers),

2) texts (any string is a text),

3) boolean values true and false,

4) the empty object nil,

5) some internal objects of the NUT system.

New objects are generated during the computations in the following three ways:

1) A predefined function new can be used, for instance: z:=new point; describing the generation of a new object which has a name z and a class point.

2) Objects can be generated implicitly when the specifications are processed. In particular, equations are regarded as program specifications and therefore objects of the type prog are generated when an equation is processed.

3) Objects can be generated as a result of operations on some other objects.

Programs

Programs are objects which belong to the class prog and can be created either explicitly or implicitly. An example of implicit generation of programs is processing of equations. Another way to generate a program implicitly is by processing problem statements (i.e., the automatic program synthesis). The NUT language has a well-developed procedural part for writing programs explicitly. Besides that, the C language can be used for writing procedures. Function new can be used for explicit generation of a program. For instance, a program max for finding the maximal value fmax of a function fun on the interval (from, to) can be defined in NUT as follows:

max.:=new prog (fun, from, to, step [right arrow] amax, fmax) begin fun (from, fmax); amax:=from; for x=from + step step step to to do fun (x,f); if f>fmax then fmax:=f; amax:=x; fi od end

The text:

(fun, from, to, step [right arrow] amax, fmax)

in the heading of a program specifies the type of the program. The program computes the value amax of the argument where the function takes its maximum and the maximum fmax. This program has a parameter fun of the type prog which will be found dynamically when the statement fun(from, fmax) or fun(x,f) is executed.

The object max can be used in two different ways:

1) Having an object f of the prog type, for instance:

f:=new prog (x[right arrow]y) begin y:=-(x 2) end,

we can immediately use the program max in the computational mode, writing:

max (f, -1, 1, 0.1);

2) The object max can be used in a specification of another relation as follows:

max1:(u[right arrow]v), x0, x1, dx[right arrow]xm, ym [prog max];

The relation max1 binds the objects x0, x1, dx, xm, ym in the same way as the relation max binds the objects form, to, step, amax, fmax. Besides that, it has a subproblem u[right arrow]v (i.e., compute v from u) the realization of which corresponds to fun of max.

A program can also be written immediately in the specification of a relation. For instance, the relation max1 could have the text of the program max instead of the reference prog max in its implementation part.

Finally, a program can be written and executed directly in dialogue in the window of a working context.

Productions

Productions in NUT have a form of Horn clauses. They represents facts and rules. Productions can be used for generating new facts and also for computations almost like Prolog. The following are the examples of facts:

[right arrow]father (John, Jack); [right arrow]father (Jack, Jim);

and this is a rule:

father@x, @y)&father@y, @z)[right arrow]grandfather (#@u, @x, @z);

The rules contain variables which are identifiers beginning with the character @. The rule given above enables us to produce a new fact:

[right arrow]grandfather (John, Jim);

from two given facts. The words father and grandfather denote predicates which can be:

* abstract predicates without any particular realization,

* names of programs,

* names of classes.

The latter case is especially useful for describing general laws for classes and objects.

For instance, the following rule

point(@u) & point(@v)[right arrow]bar(#@t, @u, @v)

says that if we have two objects of the class point, then we can form a new object of the class bar. This rather general rule can be applied for extending specifications in solving a number of geometric problems. Another example of this kind is a rule about distances on a straight line: if the distance from point A to point B is equal to L1 and the distance from B to point C is equal to L2, then the distance from A to C is L1 + L2. With a class distance:

(var A, B:point; L: length).

we can write a specification of the following form:

R: distance A = P, B = Q;

or, more briefly:

R: distance P, Q;

if we use positional binding of components of a class. (P is bound with the first and Q with the second component.)

We can use the class distance in a completely different way and write an atomic formula:

distance (@x, @y, @z).

This formula contains three variables @x, @y, @z which can be unified with the objects R, P, Q of the specification:

R:distance P,Q;

and the NUT system can transform it automatically into the following atomic formula:

distance (R,P,Q).

This can be used as a fact in production; for example, the law for distance can be written as follows:

colinear (@x,@y,@z) & distance (@u,@x,@y,@L1) & distance (@v,@y,@z,@L2) [right arrow] distance (# @w, @x, @z, @L1 + @L2);

This production means that whenever there are three colinear points @x, @y, @z and there is a distance @u of the length @L1 between the points @x and @y, and another distance @v of the length @L2 between the points @y and @z, then a new specification for distance can be introduced automatically for the points @x and @z.

Summary of the knowledge usage

A significant paradigm of knowledge edge-based systems is free reuse of knowledge. Speaking simply, what has been specified must be as widely and automatically applicable as possible. We summarize separately the ways of reusing of declarative and procedural knowledge in NUT.

The declarative knowledge is represented in the form of specifications of classes and can be used in the following five ways:

1) A class can be used as a superclass in a specification of another class: zeropoint:(super point; . . .);

2) A class contains knowledge about objects of this class which is used when objects are created or manipulated; P:=new point;

3) A class can be used as a prototype for specifying components of another class; bar:(var P:point; Q:point: . . .)

4) Any class can be used as a specification of predicates occurring in productions. It can be used to form a relation between any collection of its components and/or itself. The class point gives the predicates: "u is a point"--point(u) "u is an x-coordinate of the point v"--point(v,u) "u is an x-coordinate of a point"--point(,u) etc.

5) A class can be used as a specification of problem conditions in problem statements written within the text of a program. This feature of the NUT covers the problem-solving capabilities of the ExpertPRIZ system.

Only the first two ways of declarative knowledge reusage are implemented in conventional object-oriented systems. The remaining three cases are specific to the NUT system.

Also, produced knowledge can be used rather freely in NUT. First of all, programs can be written either in C-language or in NUT itself. Programs can appear as independent objects, initialization procedures of objects, as well as realization of relations.

Once represented as a relation, for example,

c:(. . . rel f: x[righ arrow][prog Q] . . .);

the procedural knowledge can be used in the following ways:

1) It can be used as a procedure f(u,v) or a function v:=f(d);

2) It can be used as "method" of any object q belonging to the class c q.f( ) or q.f(u);

3) It can be automatically included into a synthesized program as a realization of the axium X[right arrow]Y as soon as this axiom is used in the solvability proof of a problem.

This variety of application modes of relations required very careful implementation of program calls with detailed analysis of contexts.

Finally, let us look at the formalisms used in the NUT system for knowledge representation and usage (see Figure 8). Initially, all knowledge is represented in source language. The procedural knowledge can be translated directly into the executable form (1). The declarative knowledge is processed by means of a rewriting system and transformed into the internal form (2) which, in its turn, can be used by the object-oriented processor (3) or by the logical part of the program synthesizer (4). The output of the synthesizer is a program schema which is transformed into executable code by a code generator. At last, a producer (6) can be used for expanding the source code if prolems cannot be solved without the help of the producer.

The shortest path (1) from the source code to the executable code corresponds to conventional programming. The path (2,3) corresponds to object-oriented programming where specifications of classes are used at step (2). The program synthesis (as in C-PRIZ and ExpertPRIZ) is performed along the path (2,4,5). More general reasoning (6) can be used, both, in connection with object-oriented programming and program synthesis.

There are some other minor possibilities for extended knowledge usage in NUT--available largely as a result of the dynamic type checking and lazy evaluation: type coercion in bindings and use of structured objects with a single nonvirtual component in arithmetic, boolean and textual expressions.

A large knowledge base as well as a large program can be built only incrementally, step by step. This approach is well supported by the object-oriented paradigm. A question that appears in connection with incremental knowledge representation is knowledge encapsulation and hiding. In the NUT system we use the technique of conceptualization instead of hiding. Conceptualization means that the knowledge is divided into chunks which correspond to concepts well understood by the user. No class components are formally hidden from him or her, and import of functions into programs is not limited by dynamic binding of function names. Encapsulation which takes place in the NUT system can be called weak encapsulation. It is performed in the following ways:

* encapsulation into classes

* encapsulation into procedures

* encapsulation into objects

* encapsulation into relations.

Application Experiences

Applications of the systems described here can be roughly divided into three categories; prototyping, developing software products, and experiments in AI.

ExpertPRIZ has been intensely used for prototyping intelligent engineering software and personal CAD systems. Software packages for machine-part design, analysis of electric circuits, filter design, simulation of chemical processes have been prototyped [9]. Several packages have reached maturity and are now software products: calculation of gears, design of mechanical drives, selection of bearings, simulation of hydraulic systems [5].

All three programming environments have been used for developing some welfare products. The mosd popular application has been in database management. Actually, all three software environments have database management systems which were developed using their own program synthesizers. It is easy to see that automatic program synthesis can be directly used for synthesizing query programs for entity-relationship and functional databases. It was also shown that relational, network and hierarchical data models can be represented in the input languages of the systems described [2, 11]. A theoretically interesting application of the program synthesis used in NUT is the realization of languages described by attribute grammars [6].

The NUT system is most useful for experimental programming in AI. New ideas in combining interactive graphics with automatic program construction, functional programming and knowledge representation have been tested by means of the NUT system. At least one quite large software package was developed in the NUT environment--the package HYDRA for simulation of hydraulic systems. It has a domain-oriented graphic editor for drawing hydraulic schemas as shown in Figure 9. Every icon in the menu represents a class of devices and it is associated with the specification of this class in NUT. This enables the program to transform a graphical representation of a schema into the specification in the NUT language. For instance, the specification of the schema in Figure 9 consists of 335 lines. Writing a correct specification of this size by hand could take about 16 hours. The specification of a hydraulic schema is used automatically for synthesizing a simulation algorithm. The algorithm for the particular schema shown in Figure 9 contains 1,335 statements. The whole translation and simulation process takes 57 seconds on a Kronos workstation.

This can be considered as a typical application of the NUT system. Due to the nonprocedural nature of the specification language, the order of statements in the specification is inessential. This facilitates the translation of graphical representations into the specification language of the NUT system. Besides that, the specification language itself is well suited for representing schemas.

Acknowledgements

The problem-solving part of ExpertPRIZ was programmed by Mari Kopp who demonstrated the possibility of application of program synthesis on personal computers. Much of the logic of program synthesis used in these systems has been described by Grigori Mints to whom I am particularly indebted for helpful comments on several versions of this article.

References

[1] Barstow, D. An experiment in knowledge-based automatic programming. Artif. Intell. 12 (1979), 73-119.

[2] Haav, H.M. and Koov, M. ExpertPRIZ as an environment for developing expert database systems. In Proceedings of the 12th International Seminar on Database Management Systems (Suzdal, USSR, Oct.), 1989, pp. 89-94.

[3] Kanovich, M. Quasipolynominal algorithms of satisfyability and derivability of propositional formulas. Soviet Math. Doklady 290, 2 (1986), 281-286.

[4] Mints, G. and Tyugu, E. The programming system PRIZ. J. Symbolic Comput. 5 (1988), 359-375.

[5] Pahapill, J. Modelling of hydromechanical systems. In Application Software packages in PRIZ programming system. Tallinn (1988), 56-92.

[6] Penjam, J. Synthesis of semantic processors from attribute grammars. Syst. Prog. Comput. Softw. 1 (1983), 50-60.

[7] Tamm, B., et al. Integration of hardware and software in new generation workstations. In Man-Machine Systems. Oulu, 1988, 457-462.

[8] Terrano, A., Dunn, S., and Peters, J. Using an Architectural knowledge base to generate code for parallel computers. Commun. ACM 32, 9 (1989), 1065-1072.

[9] Tonisson, T. Expert System. Scandinavian PC Systems. Vaxjo, 1989.

[10] Tyugu, E., et al. NUT--an object-oriented language. Comput. and Artif. Intell. 5, 6 (1986), 521-542.

[11] Tyugu, E. Knowledge-based Programming. Addison-Wesley, N.Y., 1988.

[12] Tyugu, E. Propositional logic programming. Comput. Artif. Intell. 8, 4 (1989), 357-368.
COPYRIGHT 1991 Association for Computing Machinery, Inc.
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 1991 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Project START: Soviet Computing
Author:Tyugu, Enn
Publication:Communications of the ACM
Date:Jun 1, 1991
Words:6871
Previous Article:Concurrrency + modularity + programmability = MARS.
Next Article:Editorial pointers.
Topics:

Terms of use | Privacy policy | Copyright © 2018 Farlex, Inc. | Feedback | For webmasters