IC-Prolog(ID:851/icp002)for Imperial College Prolog Clark & McCabe, Imperial College 1979. Logic language with coroutining. Imperial College. A Prolog with multithreading, TCP primitives for interprocess communication, mailboxes, and an interface to Parlog. Related languages
References: in Tarnlund, S.-A. Proceedings of the Logic Progranming Workshop, Hungary, John von Neumann Computer Science Society, July 1980 view details in Tarnlund, S.-A. Proceedings of the Logic Progranming Workshop, Hungary, John von Neumann Computer Science Society, July 1980 view details Extract: A Language based upon Unification A Language based upon Unification Uniform is based upon the idea of an extensible unification procedure. All programs are extensions to the unification process. Unification piavs the roles of pattern matching, evaluation, message passing, inheritance, and symbolic evaluation. In the process of unifying the factorial of 3 with an integer n, n is unified with 6. The concatenation of x and the list (c d) unifies with the list (a b c d), resulting in x being unified with the list (a b). Unifying the nth element of the list of all prime numbers with 5 results in n unified with 3. Unifying the reverse of a list of variables x and y with a list z, unifies z with a list of v and x. Unifying a member of set x with 3 member of set y yields a member of the intersection of x and y. Unifying a description of red chairs with a description of big chairs produces a description of big red chairs. And so on. Extract: Unification — What it is Unification - What it is Unification was invented for use in resolution theorem provers [Robinson 1965] and has since been used in a few programming languages. Two well-known examples are Prolog which is a programming language based upon resolution theorem proving [Warren 1977] and Qlisp [Sacerdoti 1976]. In these languages unification is only one facility among others. In Uniform unification is augmented so that no other mechanism such as resolution, automatic-backtracking, or evaluation is needed. Unification is the process of generating the most general common instance of a set of descriptions. It is implemented as a process that returns a "unifier" which if applied to any of the original descriptions produces the sought after instance. In the most common case, the unifier is simply an environment describing variable bindings and it is applied to a description by substituting its values for the variables in the description. It is the use of unifiers, rather than actualiv constructing instances, which makes the process computationally feasible in much the same wav that environments replace lambda substitution in Lisp. As an example, (unifier-of(foo x 'a r) (foo 'b v r)) produces "(unifier (x 'b) (y 'a))" which if substituted into either description produces the instance "(foo 'b 'a r)". Unification is defined to produce the most general instance which means that the instance produced must unify with all other possible instances. Pattern matching, which has played such a large role in most AI languages, is a special case of the unification of two descriptions. The pattern is a description containing variables which is matched against a description without any variables. If the match succeeds, the unifier produced is a set of match bindings which when substituted into the pattern produces the other description. Unification has three advantages over pattern matching. 1. There is no distinction between patterns which bind variables and patterns which use the value of variables. This allows the meaning of a pattern to be determined dynamically and is crucial in using programs in multiple ways and directions. 2. Patterns can be matched against patterns. This is important for dealing with partial information. For example, in a unification-oriented database one can have a demon which triggers whenever a cube is put on a ball and then add the "pattern" (on (ball 'a) (cube x)) and the demon will be triggered even though x has no value (it represents an undetermined cube upon ball a). It is also useful in determining if one pattern is a special case of another. Uniform uses unification this way so that by default more specific knowledge is used first. 3. The order in which sub-problems (recursive calls to unify) are made does not affect the outcome. This gives the implementation a freedom of optimization not possible in most pattern matchers. Parallel implementations of unification which could take advantage of the parallel hardware of the future are also possible. Extract: How Unification is Augmented in Uniform How Unification is Augmented in Uniform Unification is a syntactic process. Its only concern is that forms have the same "head", their arguments unify, constants are equal and recursively that bindings unify. It cannot unify the sum of x and 3 with 7 by unifying x with *. Uniform's augmented unification leaves it up to the forms involved to unify as they see fit where the traditional syntactic unification process is used only as a default. Except for a small set of primitive forms this augmentation is described in Uniform by the user. The only constraint upon augmentations to the unification of two descriptions is that the resulting unifier produce equivalent descriptions when applied. For example, the unifier describing x as » produces 7 and the sum of Uniform's augmented unification not only has the unusual features of delegating to the forms involved but is based upon a new very parallel algorithm. Sub-unifications of corresponding arguments are computed independents and the resulting unifiers are unified. A unifier is a virtual set of possible bindings where further possibilities are computed only upon need. This mechanism replaces the automatic backtracking in Prolog and Qlisp. In addition, when the descriptions cannot be unified the algorithm produces failure descriptions which are used internally and by the user for debugging. Unification is also used to implement the occur check and the "ground" primitive. The algorithm is described further in [Kahn forthcoming] Extract: Uniform and Actor Languages Uniform and Actor Languages Computer languages based upon computational entities called "actors" offer modularity, parallelism, full extensibility of both data and functions and a simpie but powerful computational semantics. An early version of Uniform was attempted in Act 1 Act I is a message passing language based upon the convention that actors be able to respond to "eval" and "match" messages. Uniform can be viewed as a language in which forms pass "unify" messages between themselves and their parts. As we saw in the previous section, unification subsumes evaluation. Unification clearly subsumes the match messages in Act 1 since pattern matching is just the special case of unification where one of the forms contains no variables. One of the important features of actor languages is the ability to describe a new data structure and have old programs use it without modification. This is a consequence of the fact that programs depend only upon the behavior of data in response to messages. A list is any actor which can answer "first" and "rest" messages. The analogous statement about Uniform is that a list is any form that can unify with "(cons x y)". For example, suppose we want to define a new kind of list which internally is represented by two lists, one for the original members and one for those deleted. The advantage of these "delete lists" is that deletion becomes a very cheap and pure operation in return for a little overhead on other operations. They can be defined as follows in Uniform: (assert (= {delete-list deleted (cons first rest)) (rules first ((member deleted) ;is already deleted so skip it (delete-list deleted rest)) ((?) ;otherwise the first element is ok (cons first (delete-list deleted rest)))))) This is all that is needed to run any program that works on lists since it provides a path from "delete-list" to "cons". For example, List's "delete" operation defined below will work on these lists. (as sert (= (delete x (cons first rest)) (rules x (first (delete x rest)) ((?) (cons first (delete x rest)))))) (assert (= (delete x ()) ())) The whole point of having "delete lists", however, is to delete elements efficiently. This can be done as follows: (assert (= (delete x (delete-list deleted memb e r s ) ) (delete-list (cons x deleted) member s)) ) Notice that this way of implementing lists as anything that can unify with a cons of two variables subsumes the inheritance mechanism in languages like SmallTalk and Director. If nothing is known about how to do some operation upon a particular kind of list then the same operation upon lists in general will be used. Uniform always tries first the shortest path between two structures. The path to delete list's delete operation is shorter than one through cons's delete so It is followed first. Of course sub-ciasses are possible. If x-lists oniy unify directly with y-lists which unify with "cons", then definitions of operations upon x-Iists will be used before those for y-lists which in turn will be used before cons's definitions. This same mechanism works for multiple super classes. If we define how horizontal-dashed- lines unify with horizontal-lines and with dashed-lines then operations upon either one can be applied to horizontal-dashed-lines. Since Uniform follows shortest paths first, the multiple super classes are searched in a breadth-first fashion. One very important part of some of the actor languages is the user definable control structures and ability to compute in parallel [Hewitt 1977] [Lieberman draft]. This is a serious deficiency of Uniform. The plan is to add such information as advice to the interpreter as to how to go about doing the unifications. This approach is similar to one taken in Metalog [Dincbas 1980]. The appeal of separating logic from control is that a user can develop and test the logic or competence of a program before adding control information to improve its performance [Kowalski 1979] [Pratt 1977]. Also different uses of the same program may be helped by different control information. Extract: Uniform and Logic Programming Uniform and Logic Programming In recent years a number of logic programming languages have appeared. Most notable is Prolog, a programming language which resembles Planner [Warren 1977]. Programs in Prolog are axioms in the first-order predicate logic restricted to Horn clauses. Programs are executed by a resolution theorem prover. What is special about Prolog is that it is intended as a general purpose programming language meant to compete with compiled Lisp as well as with Planner-like languages. The objection to logic as being an excessively constrained manner of reasoning is irrelevant to its worth as a pronramming language. One would not want to buiid AI programs upon an "informal" Lisp. The objection to logic that it is not concerned with control over the use of knowledge is a serious one. There are manv advantages however, to having a programming language based upon logic with a separate control component for improving performance such as IC-Prolog [Clark 19SO] or Metalog [Dincbas 1980]. When compared with Lisp, Prolog has many advantages and a few very serious disadvantages. Prolog shares with Uniform the ability to use the same program in many ways. For example, the Prolog definition of "append" can be used not only to compute the result of appending two lists together but can also be used as a predicate to verify that the result of appending two lists is a third list, as a generator of pairs of lists that append to a particular list, as a wav of finding the difference between two lists, and as a generator of triples of lists such that the first two append to form the third. Prolog has a few other features which Lisp lacks. Among them are the ability to compute with partially instantiated structures, a convenient way to handle multiple outputs, and the use of pattern matching instead of explicit list construction and selection. On the negative side, Prolog implementations are the result of a much smaller implementation effort than the major Lisp dialects and correspondingly lack good programming environments, i/o facilities, adequate arithmetic, and the like. Attempts to embed Prolog in Lisp (e.g. Uniform was developed with the goal of capturing and improving these positive aspects of Prolog. Uniform supports all the uses of a definition that Prolog does and an additional few. For example. Uniform's definition of "append" is equivalent to Prolog's and can also be used as an implementation of segment patterns. In addition, it is all the knowledge about "append" the system needs to answer questions about program equivalence. For example, work is under way so that Uniform can successfully unify the following for all lists x and y. (= (append (reverse x) y) (reverse (append (reverse y) x))) In Uniform one can augment the unification of relations other than the "=" relation and so can write in Prolog's relational, as opposed to a functional, style. The following is a Uniform program for defining the "grandparent" relation (which can be used as the "grandchild" relation too). (assert (grandparent-of grandchild grandparent) ;the above is true if the following holds (parent-of a-parent grandparent) (parent-of grandchild a-parent)) The program says that two variables are in the grandparent relation if a child of the first variable unifies with a parent of the second. As in Prolog the variables "grandparent" and "grandchild" are universally qualified and "a-parent" is existential (by virtue of not being in the "head"). It is equivalent to the Prolog program: grand parent_of(Grandchild,Grandparent) :-parent_of(A_parent,Grand parent), parent_of(Grandchild,A_parent). Despite the similarity, the two programs are executed differently. Uniform executes programs using augmented unification. Inside the unification it computes with virtual sets of all possible unifiers and performs searches in a shortest-first manner. Shortest-first search combined with the use of virtual sets of unifiers replaces Prolog's resolution theorem prover which depends upon svntactic unification and automatic backtracking. More details about Uniform's implementation can be found in [Kahn forthcoming] Extract: Conclusions and Future Research Conclusions and Future Research A surprising result of this research is that unification, a process of generating the most general instance of a set of descriptions, can be such a powerful basis for a programming language. Unification unifies the essence of Lisp, Act 1, and Prolog into a simple coherent framework. Uniform is far from complete/ Some of the major avenues of future research follow. 1. Developing and incorporating the dual of unification, generalization, into the language. The duality between unification and generalization is striking and the ability to implement them both using the same mechanism is surprising. 2. A shortcoming of Uniform and Prolog is their inability to use negative information. In the previous example of association lists we cannot prevent a key from having more than one association. Uniform will be extended to use the following: (assert (not (= (association-of key (cons (list key value) rest)) (not value)))) This would cause the unification to fail if the key is found but the values do not unify. Negative information can be used in a default strategy which concurrently tries to unify two descriptions and to show that they are not unifiable. 3. In the process of unification a variable may acquire multiple constraints. As a default, Uniform simply conjoins them. If later an attempt is made to give the variable a value, then the constraints disappear if the value satisfies them, otherwise it fails. Inconsistent constraints do not cause failure unless there is an attempt to use them. If the constraints have a unique solution then only that value can unify with them, but the system does not compute that value. The unification of constraints appears to be a natural place to use some of the constraint satisfaction techniques found in systems such as Thinglab [Borning 1979], Steele and Sussman's constraint system [Steele 1980] and the XPRT system [Steels 1979]. These systems provide evidence for the general usefulness of describing much of computation in terms of constraints. 4. We have explored the unification of descriptions of programs. Exploring the unification of other complex structures such as frames, scripts, and units should be equally valuable. Much of what systems such as FRL, XPRT, SAM and KRL do is match complex declarative structures with others. Unification, a more general and powerful process than pattern matching, promises to be very useful for dealing with these structures. 5. As has been pointed out elsewhere [McCarthy 1968] [Hayes 1973] [Pratt 1977] [Kowalski 1979] there is much to be gained by separating the control and logic components of an algorithm. Uniform programs have much less control information in them than equivalent Lisp or Act 1 programs. A general search strategy is used as a default so that the factual or competence component of programs can be developed and tested without the added complexity of being concerned with efficiency. The efficiency can be put in later and kept lexically separate from the rest of the program. A compiler is planned which will be written in Uniform and produce Lisp code. 6. It is very difficult to evaluate the worth of computer language based solely upon small programs. Prolog, for example, becomes less desirable as the size of the programs grow due to its impoverished notion of errors and debugging and its reliance upon automatic backtracking. Work has been done to alleviate these particular failings in Uniform, but experience in using Uniform is lacking. Concurrent with the research suggested above, Uniform needs to be tested bv writing large complex programs in it. In this respect Uniform is way behind Lisp et. al. in Tarnlund, S.-A. Proceedings of the Logic Progranming Workshop, Hungary, John von Neumann Computer Science Society, July 1980 view details in Clark, K.L. et al eds, Logic Programming, Academic Press 1982. view details in Clark, K.L. et al eds, Logic Programming, Academic Press 1982. view details Resources
|