LogC(ID:1694/log004)Logic C C extension incorporating rule-oriented programming, for AI applications. Production rules are encapsulated into functional components called rulesets. Uses a search network algorithm similar to RETE. Structures: Related languages
References: Introduction Different paradigms of programming available in computer science community today are usually embedded in different languages. New software technologies often force the development of new paradigms, or incorporating two or more of the conventional programming paradigms, for example, C++ programming language[5] supports data abstraction and object oriented programming in addition to procedure oriented programming; LOOPS system[l] combines features of the LISP functional, rule oriented and object oriented paradigms. The multiparadigm systems are being created to give programmers the flexibility of choosing the right tools for specific requirements of problems. LogC is designed to incorporate the rule oriented programming to the traditional C programming for the system designs in artificial intelligence. Our experience proves that programs for intelligent problem solving are easier to build in a language when procedure oriented and rule oriented paradigms both are available from the same language. The programs may respond to pattern-directed problems simply by a ruleset, rather than using a prespecified inflexible instructions; meanwhile, procedures are still often needed to deseribe heuristic functions or some functional computations. It will benefit a lot in case that these two of paradigms coexist together within a program. LogC is in fact an extension of C. The decision to extend existing language rather than to invent a new language is based on pragmatic considerations. We felt we could focus more effectively on the new and interesting issues of knowledge inference if we did not have to redesign basic language features, and we felt that the building on the basis of a widely-used language like C would facilitate the use of LogC outside our own research group. In the course of development of artificial intelligence technology, there has been a variety of intelligent software appeared to meet requirements from different aspects of applications. LogC is designed as an integrated programming environment to support such AI programming. In addition to general characteristics in traditional software environments, LogC provides, in particular, new features for heuristic inference controls, which make lots of benefits for system designs. The sections in the following outline the LogC design features and demonstrate some results about inference efficiency by comparison with other AI languages. Extract: The Language The Language LogC language is designed to easy the systematic programming for intelligent problem solving. It has the programming language C as a subset, so it can be used easily by experienced C programmers. However, LogC is a multiparadigm language. A ruleset can be defined in LogC programs as a functional component. LogC supports the programming in procedure oriented and in rule oriented paradigms. In order to improve the capability of symbolic processing, LogC augments an extra data type 'list' and includes a predefined C-package for list processing. Programs in LogC are organized around some sets of pattern-action rules for the purpose of intelligent problem solving. Every ruleset consists of its name, meta controls and a set of production rules. ? Data representations Every ruleset has an associate working memory which is partitioned into classes. A class is a collection of elements which are of the same data type. We think that an identical data representation formalism should be used by both procedure and rule based parts of the language, therefore, the working memories can contain objects of any data type from C and the objects can be referred to by procedure code. No conversions or cumbersome access mechanisms are needed. ? Production rule A production rule is similar to the IF statement in traditional C language, but it uses the different method to encode the computing. The test part of each rule is a sequence of C expression, and the action part is a sequence of statements which may be C functionalities or some special form of statements to make or remove objects from given classes. Production rules are encapsulated into rulesets. The LogC interpreter or compiler executes a ruleset by performing a sequence of operations (mateh-select-acteycles) until no applicable rules are found or the functionality 'return' is called in action parts. In the Init phase of inference cycle, the executor evaluates the LHSs of rules on the current working memory to determine which are satisfied, collects all pairs of satisfied rule and instantiations into a conflict set and sorts them in the order of priorities according to a certain control strategy; and then in the next phase, selects the unique one with the highest priority from the conflict set; finally in the third phase, instantiates the selected rule and perform the actions specified in the RHS. ? Meta controls LogC provides a flexible control mechanism to support heuristic inferences. There are three main kinds of meta controls: the priority functions are used for computing the priority of each class object at its creation or modification; the selection functions are used to select the 'best' rule and instantiations among the conflict set for the current execution, the selection strategy could be 'byrule', 'bydata' or 'bytime' ; the recta control ' backtracking' is used to indicate if the inferences require backtracking or not. In the case of backtracking, it is necessary to save historical information about the changes of working memory, and restore them for their use later. The history and backtracking facilities could be used to help programmers in finding good heuristic functions. During a process of inference, the changes of a working memory or an object in a class are often reversible, which may cause the inference failed into an infinite loop. The LogC recta controls 'statecheck' and 'classcheck' could be used to avoid such infinite loops in most cases. There are some other meta controls provided to control inference steps etc. It is demonstrated that heuristic inferences could be controlled by using these meta controls singly or combinedly. For example, combining a heuristic priority function in C for a class and the selection mode ' bydata', we could make a best first search strategy for the class space; however, if we clean current class space during every inference step, we get a local-best first search strategy. If the heuristic function is designed by powering with length of inference path, i. e. the priority values of class elements dependent mainly on their inference depths, then the inference process is inclining to depth searching; conversely, the heuristic function could be designed to make the inference process inclining to breadth searching. Here is a part of program to solve the eight puzzle problem in LogC. Extract: The Conclusions The Conclusions The LogC programming language is designed to make the task of AI programming more enjoyable for serious programmers. It has the C programming language as a subset, so it can be used immediately by C programmers. A LogC program can include any of C programs and libraries. Howcvcr, the main strength of LogC lies in its facilities to support heuristic inferences based on rule oriented programming. LogC is also an integrated cnvironment for multiparadigm programming. In addition to general fcatures of traditional programming environments, LogC provides an extensive set of facilities to support knowledge inferences. LogC version 1.6 has been implemented on SUN-station, U-station and pc386 under UNIX. It is demonstrated that the LogC environment is convcnient for programmers in designing expert systems, transformation systems, games and other Knowledge based systems. Extract: Inference Efficiency Inference Efficiency The execution efficiency is one of main problems for languages with rule based paradigms. In the matching phase of each inference cycle, a collection of conditions in LHSs of rules is compared to a collection of objects in working memory. Unfortunately, it can be very slow when large number of conditions or objects are involved. However, it is noticed that an execution of a rule only changes in most case a few of objects; It is similar to RETE algorithm developed by C. L. Forge[5], LogC uses a sorting network to determine all of possible matches, it is efficient even though it processes large sets of objects. The algorithm does not have to iterate over the conditions of rules because it contains the sorting network to index them; moreover, the algorithm does not have to iterate over the working memory because it maintains the state information as each object updates and stores it as long as the object remains in the data space. The details of the algorithm is described in [7]. As the features described above in the LogC design and implementation, LogC could support heuristic inferences exclusively more efficient than other AI languages like PROLOG. This is illustrated by the following figures. Table I gives the result of efficiency comparison between LogC and PROLOG to solve the eight-puzzle problem, here LOGCE is the LogC interpreter; while LOGCC is the LogC complier. Table 2 gives the result of efficiency comparison on another side. To solve traveling salesman problem, the complexity of algorithm by using branch and bound method is O(n22"), n is the number of cities. However by using heuristic inference in LogC, it is demonstrated that the time cost of obtaining a quite approximate solution could be less than n 3. The bigger the number n, the better the efficiency enhancement. in SIGPLAN Notices 27(11) November 1992 view details |