MATCHLESS(ID:2214/mat003)Sublanguage and internal language for Hewitt's PLANNER References: Preface PLANNER is a language for proving theorems and manipulating models in a robot. Although we say that PLANNER is a programming language, we do not mean to imply that it is a purely procedural language like the lambda calculus in pure LISP. PLANNER is different from pure LISP in that function calls can be made indirectly through recommendations specifying the form of the data on which the function is supposed to work. In such a call the actual name of the called function is usually unknown. Many of the primitives in PLANNER are concerned with manipulating a data base. The language will be explained by giving an over-simplified picture and then attempting to correct any misapprehensions that the reader might have gathered from the rough outline. The basic idea behind the language is a duality that we find between certain imperative and declarative sentences. For example consider the statement (implies a b). As it stands the statement is a perfectly good declarative statement. It also has certain imperative uses for PLANNER. For example it says that we should set up a procedure which will note whether a is ever asserted and if so to consider whether b should then be asserted. Furthermore it says that we should set up a procedure that will watch to see if it ever is our goal to try to deduce b and if so whether it is wise to make a subgoal to deduce a. Similar observations can be made about the contrapositive of the statement (implies a b). Statements with universal quantifiers, conjunctions, disjunctions, etc. also have both declarative and imperative uses. Of course if what we have described thus far were all there was to the language, then there would be no point. From the above observations, we have constructed a language that permits both the imperative and declarative aspects of statements to be easily manipulated. PLANNER uses a pattern directed information retrieval system that is more powerful than a retrieval system based directly on association lists. The language permits us to set up procedures which will make assertions and automatically draw conclusions from other assertions. Procedures can make recommendations as to which theorems should be used in trying to draw conclusions from an assertion, and they can recommend the order in which the theorems should be applied. Goals can be created and automatically dismissed when they are satisfied. Objects can be found from schematic or partial descriptions. Properly formulated descriptions have their own imperative uses for the language. Provision is made for the fact that statements that were once true in a model may no longer be true at some later time and that consequences must be drawn from the fact that the state of the model has changed. Assertions and goals created within a procedure can be dynamically protected against interference from other procedures. Procedures written in the language are extendable in that they can make use of new knowledge whether it be primarily declarative or imperative in nature. The logical deductive system used by PLANNER is subordinate to the hierarchical control structure of the language. PLANNER has a sophisticated deductive system in order to give us greater power over the direction of the computation. In several respects the deductive system is more powerful than the quantificational calculus of order omega. Our criteria for an ideal deductive system contrast with those that are used to justify resolution based systems. Having only a single rule of inference, resolution provides a very parsimonious logical system. Workers who build resolution systems hope that their systems can be made efficient through acute mathematical analysis of the simple structure of their deductive system. We have tried to design a sophisticated deductive system together with an elaborate control structure so that lengthy computations can be carried out without blowing up. Of course the control structure can still be used when we limit ourselves to using resolution as the sole rule of inference. Indeed, R. Burstall has suggested that we might try to implement some of the well known resolution strategies in PLANNER. Because of its extreme hierarchical control and its ability to make use of new imperative as well as declarative knowledge, it is feasible to carry out very long chains of inference in PLANNER. Extract: Matchmaker MATCHLESS MATCHLESS is a pattern directed programming language that is used in the implementation of PLANNER. MATCHLESS is used both in the internal workings of PLANNER and as a tool in the deductive system itself. The most important function in MATCHLESS is assign? which matches its first argument which is treated as a pattern to its second argument. The reason why the assignment function in MATCHLESS is called assign? will be explained later when we discuss functions that have values. The prefix operator $- indicates that the variable which follows it is to be assigned a value. The various types for variables and their abbreviations are: ptr for pointer, atom for atom, seg for segment, fix for fixed point number, float for floating point number, and expr for s-expression. A segment variable is always assigned the smallest possible leftmost segment. Below we give some examples of the values of pattern variables after assignment statements have been executed. We use the character - to delimit segments. The characters { and } are used to delinit function calls. {prog ((a ptr) (h atom) (c seg)) (assign? ($-a k $-h $-c) ((1) k b 1 a))] a gets the value (I) h gets the value b c gets the value -1 a- lprog ((c seg) (h atom) (a ptr)) {assign? ($-c $h k $-a) (a 1 b k q)31 c gets the value -a 1-h gets the value b a gets the value q {prog((first ptr) (middle seg) (last ptr)) {assign? ($-f irst$-middle$-last) (l&,3,4))} first gets the value 1 middle gets the value -2 3-last gets the value 4 {prog ((a ptr) (b ptr)) {assign? ($-a,$-b) (d)}} fails because there is only one element in (d). (prog ((a atom)) {assign? $-a (1 2)]] fails because (1 2) is not an atom. An expression that consists of the prefix operator $$ followed by a variable will only match an object equal to the value of the variable. Cprog ((a seg)) {assign? ($-a$$a) (1,2,3,1,2,3)}} a gets the value -1 2 3- {prog ((a seg) (b seg)) {assign? ($-a x $$a $-b)(abxdxabxdq)}} a gets the value -a b x d-b gets the value -q- An expression that consists of the prefix operator $? followed by a variable will match the value of the variable if it has one, otherwise the variable is assigned a value. We shall use the pseudo atom NOVALUE to indicate that a variable does not have a value. {prog ((a ptr)) {assign? $?a 3}} a gets the value 3 {prog (((a 5) ptr)) {assign? $?a 4}} a is initialized to 5 on entrance to the prog. Consequently the assignment statement fails. {prog ((a seg)) {assign? ($-a,$?a) (1 2 3 2 l)}} fails because once a is assigned a value, a can only match a segment that is equal to the value of a. If a pattern in an assignment statement cannot match the value of the second argument of the assignment statement then the assignment statement returns the value (), otherwise the value t. Examples of pattern functions are disj for disjunction, neg for negation, conj for conjunction, and star for Kleene star in general regular expressions. We use the characters < and > to delimit pattern expressions that are to be interpreted as segments. {prog ((a Ptr (b ptr) (c ptr)) {assign? (a {prop ((x seg) (c seg)) {assign? ($-x {prog ((x ptr)) {assign? ( Pattern functions do not produce values. It does not make any sense to evaluate {assign? (def palindrome (kappa (0) {disj [block ((x ptr)) ($-x The form kappa is like the lambda of LISP except that it is used in pattern functions. The above definition reads "a palindrome is a list such that it is () or it is a list which begins and ends with x with a palindrome in between." The pattern function block causes the variable x to rebound to the pseudo-atom NOVALUE every time that palindrome is called. The function reverse is defined to be such that (assign? {reverse $$XI $Sy} is true only if the value of X is the reverse of the value of y. The definition of reverse is (def reverse (kappa (((x ptr))) ({atomic}$$x) {block ((first-of-x ptr)(rest-of-x seg)) {assign? ($-first-of-xrest-of-x)$$x} ( Extract: Acknowledgements Acknowledgements The preceeding is a report on some of the work that I have done as a graduate student at Project MAC. Reproduction in full or in part is permitted for any purpose of the United States government. We would like to thank the various system "hackers" that have made this work possible: D. Eastlake, R. Greenblatt, J. Holloway, T. Knight, G. Mitchell, S. Nelson, and J. White. We had several useful discussions with H. V. McIntosh and A. Guzman on the subject of pattern matching. S. Papert and T. Winograd made suggestions for improving the presentation of the material in this paper. in Donald E. Walker, Lewis M. Norton (Eds.): Proceedings of the 1st International Joint Conference on Artificial Intelligence IJCAI-69, Washington, DC, May 1969. William Kaufmann, 1969 view details |