SYSP: A New Programming Language for the Next Generation

1. IN'l'RODUCTION

The research of knowledge representation demands a new t ype programming language for AI which is highly structured and is able to represent various aspects of knowledge naturally and uniformly. On the other hand, the one of automatic programming does new type programming (methodology and language) which is also hi ghly structured and is able to make the process of programming more structured. These two trends aim at the same goal, for example, Sysp. It is a highly structured symbol manipula­ tion system(in. true sense, a general purpose computation system) based on Newell's physical symbol system hypothesis. Sysp consists of four co-ordi nates.

In followings, Sysp is outlined along Extension, Degeneration and Reduction co-ordinates.

GYSP A New Prograrruninr; Lunr;uuge to the Next (1eneraLion

Toshio Yokoi, Shooichi Yokoyama, Taisuke Satoo, Fumio Motoyoshi and Kazuhiro Fuchi

Machine Inference Section, Information Sciences Divi s ion Electrotechnical Laboratory 2-6-l, Nagata-cho, Chiyoda-ku, Tokyo, Japan

Sysp( Structured Symbol System Processer) is a base programming language for knowledge representation, and also a non-procedural and non-von Neumman style programmi ng language to the next generation. Logic prograrruning, functional programming , ob,j ect or i ented programming etc. are integrated into a simple and transparent mechanism based on the mes ­ sage passing computation(QA model of computation). An overview of Sysp 's framework i s presented using simple examples.

2 . EX'l'ENSION t o q,A model

Lambda calculus is a computation model whi ch is able to express the hi gher or der computat i on naturally. So, it is available so much for the basic mechanism and semantics description of various programming languages and is extended to make its ability more powerful for this purpose. Recursion, Landin's J-operator, Reynol ds 's escape expression, Steele & Sussman 's tai l transfer mechanism and continuation f unc t i on were introduced. These extensions were arr anged into message passing mechanism l i ke Ac t or for ­ malism etc.[l]. The distinctive feat ures of the mechanism are as follows .

• (a) By preserving execution environment on heap instead of stack, send and receive act i ons are able to express coroutine and parallel com­ putation directly.
• (b) Multiple-value return and naming without side effect become possible. The compos ition and decompos ition of data structure are ex­ pressed in non-procedural manner.
• (c) The history of computation i s preserved completely and easily, so that the well f itt ed mechanism to the evaluation of nondeterminist i c program is gained.
• (d) In co-operation with static binding mechanism, truly necessary execution environment for a computation is clearly specified .

Moreover, QA model of computation, puts its stress on well-formed communication(question an­ swering) mechanism for the natural and rigi d representation of a problem solving process(computation). So, appropriate syn­ chronization mechanism etc. are included i nherently and the communication mechanism is made mor e structured .

One method of making the mechanism more struc­ tured is on message sent and received. In natural lanv,uage , a sentence is classified into some types , declarative, interror,at ive, impera­ t i ve or exclamative, so that a l istener is able to understand the intention of a speaker so easily. And moreover, in interrogative sentence, i t is expressed clearly what sort of answer is expected , ye s-no or answer to interroga­ t ive (When... , Where... How many... , What kinds of ... etc.). Similarly, in QA model, various message types are provided. And a com­ putation is represented as a natural "question­ answering (QA) sequence".

'l'he other method of making the communication mechanism more structured is on QA sequence. First , QA sequence is r estricted to the fol­ l owing communication manners.

• (l) When a question is sent/received, the answer must be received/sent .
• (2 ) To send/receive the answer to the latest ~eceived/sent question.

Wi th these restrictions, sequences starting with an action on a question and ending in an act ion on the corre sponding answer are nested with one another . Such a sequence is called "well­ structured QA sequence". 1'he simplest well­ structured QA sequence is to send/ recei ve a question and then to receive /send the answer. These are called "atomic QA sequence".

QA sequence( computation) is reduced into some sub- QA sequence (subcomputation). Therefore, the de scription among sub-QA sequences Bives the structure of the original QA sequence. This description is called "compound QA sequence". !<'or example, factorial function in Lisp,

,is represented as QA sequence.

3. DEGENERATION to predicate calculus

I t is poss i ble to make two actions, to receive a question and to send the answer, degenerate into one action, to assert the fact. In the same manner, two actions, to send a question and to receive the answer, are made degenerate into one, to interrogate the fact. Futhermore, two actions, to assert a fact and to interrogate on the fact, are made degenerate into one object , a predicate(atomic formula).

By regarding assert and interrogate actions as atomic QA sequences, compound QA sequence is made degenerate. It is called "degenerate (com­ pound) QA sequence". The factorial function is transformed into a partially degenerate QA se­ quence.

In this sequence, variables in the messages have some sort of indication(input or output) and the evaluation order are fixed . Next, this is trans­ formed into a fully dep;enerate QA sequence.

In this one, the variables have no indication and the fixation of the evaluation order is taken aw~y. In order to make the meaning of Degener~tion clearer, the f actorial function is represented in Horn set,

Assert action corresponds to pos itive clause and interrogate action does to negative clause. And further, pattern directed invocation of assert action by interrogate action corresponds to the application of Resolution rule.

In the current research on logic programming[2], it has tried to make clear the correspondence between computation structures and proof strategies without any explicit construct for control structure. By the following reasons, however, it needs to introduce appropriate procedural aspects into logic programming.

1. Many computation sequences are condensed into one logical formula by abstracting certain aspectE of thP. sequences, but only some of them are able to have actual meanings. That is, it is hard to say that it represents computation ex­ actly .

1. Proof mechanism like Resolution is power­ ful as basic computation mechanism, but very primitive. So, higher structures of computation can not be represented by proof strategy only.

It is so easy to introduce procedural elements for claptraps, but never desirable. Sysp makes it possible to define strict meanings of procedural elements by introducing the succes­ sive Degeneration process from QA model to predicale calculus.

4. REDUCTION to algebraic formula

Along Extension co-ordinate, lambda calculus, an applicative computation system, is extended to include imperative features preserving the ad­ vantages as it is. And again, QA model is reduced into algebraic formula, a typical ap­ plicative system. But this never means that Ex­ tension co-ordinate is traced conversely.

Send action is reduced into the composite func­ tion of receiver and message. Receive action is reduced into environment modifier function. Namely, a message is regarded as a functional form and a variable is regarded as a function which yields the value from environment as well as in GEDANKEN. Receive action is regarded as a functional form which tests whether or not the actual argument matches the message pattern and, if matched, modifies the environment by naming. Continuation(next) relation is represented as the composition of functions. In this way, a simple QA sequence is reduced mechanically into an applicative form. And further, Reduction pr ocess goes on. The factorial function is par­ tially reduced to

Further , this is fully reduced into

through the transformation which simplifies en­ vironment modifier function and eliminates variables by substitution (introducing selector function). Thus, a QA sequence is reduced into an algebraic formula, its semantics is for­ malized as lows of algebra and it becomes possible to prove its various properties by for­ mula manipulation, as Backus etc. point out. For comparison, the example is represented in Backus's FP[3], Def !=eq·[id, 0"] -> T; *·[id, 1·-·[id, T]]

For each type of compound QA sequence, cor­ responding functional forms are provided. The applicative form obtained in this way is called "reduced QA sequence".

Functional programming is related to QA model through successive Reduction process. By this way, its weakpoints are covered up and its ability is extended as follows.

1. The appropriate and natural interpreta­ tion of functional form are obtained.
2. Advantages of other computation models, including history sensitivity, are added to in a very natural way.

5. CONCLUSION

The method for knowledge representation must be powerful, natural and formal. It must be power­ ful in order to represent complicated and higher order knowledge, natural in order to make it easy to use and understand, and formal in order to make possible for a computer to process represented knowledge mechanically. Sysp satis­ fies these three conditions sufficiently over a wide range by integrating four representative methods into one transparent mechanism. For ex­ ample, factorial function is able to give natural looks in Sysp,

At present the main part of Sysp is implemented on EPICS-Lisp. In other papers[4], Sysp is described in more details.

AKNOWLEDGEMENTS: The authors wish to express their gratitude for the encouragement from the head of their division, Dr. H. Nishino.