ABSYS(ID:357/abs006)Aberdeen system declarative languageMichael Foster, University Aberdeen. Early declarative language, anticipated a number of features of Prolog. System for localisation of typed variables influential on POP-2 (Popplestone) Places Related languages
References: Introduction This paper considers some aspects of the problem of describing a certain class of objects as constructs formed from given primitive objects, and of recognizing realizations of a described object in a given environment of primitive objects. My interest in this problem stems from work done in collaboration with A.M.Murray on the design of programs which can acquire an increasing capability to play board games as a result of the program's own analyses of games which it has played and lost {see Elcock and Murray, 1967). The last part of this paper relates the present work to this earlier work. The simple formal language used for descriptions in what follows reflects this interest in particular board games. The design of a more comprehensive descriptive language (cf. Banerji, 1965) is an interesting problem, but will not be pursued in the present paper. For reasons which it is part of the function of the present paper to make clear, it is intended that such language design, together with the further development of the ideas reported here, will take place within the framework of an assertional programming system of the general kind discussed by J. M. Foster in this volume. The paper is in three parts. Part one introduces descriptions and considers the recognition process. Part two comments on certain features of sequencing in the recognition process. Part three briefly relates the presented view of description and recognition to the earlier work of A. M. Murray and myself on game-playing programs. Extract: Some Comments Some Comments (i) There are clear links between this kind of recognition process and some of the work of I. E. Sutherland and others in Computer Graphics. In particular there are links between a description as formulated here and Sutherland's concept of a constraint {see Sutherland, 1963). The essential difference would seem to be that Sutherland applies constraints only to 'appropriate' objects (e.g. the constraint 'square' to anotyect((a,b),(b,c),(c,d, ),(d,a))). Here one is interested in an arbitrary given object and asks for all sub-objects in the given object which meet the constraint (satisfy the description). Nevertheless, the following two comments are as relevant to Sutherland's concept of applying a constraint as to the present problem. (ii) It should be clear that in the recognition process as described, the particular order in which jobs are selected from the current set of alternative jobs is totally irrelevant to the end result. (iii) The particular sequencing can be, and usually is very relevant to the number of partial realizations (alternative jobs) generated and hence to the total amount of work done. Thus, in the context of the E used above let D={{w,x,y,z):((w,x),{x,y),(y,z),(z,w))} with the interpretation 'quadrilateral'. If the recognition process begins by setting up the partial realizations obtained by identifying (w,x) with successive primitives from Ev\ and if the next stage is lo set up for cuch of these purliul realizations the partial realizations obtained by identifying (y,z) with successive primitives from Ev, then a great deal of work is going to be done which could have been avoided by a different sequencing. In a situation like this one would like to be able to exploit the irrelevance of sequencing to the end result, without necessarily incurring penalties of inefficient processing. In stating the problem one would like not to be concerned with sequencing as a primary responsibility at all, but merely give the set of assertions which constitute the description, the set which constitutes the environment, and a generator of the required set of assertions of the kind ((a,b) is (x,j)) (where is is used with the meaning 'can be identified with') to initiate the process of recognition. The selection of which assertion to consider next might be left partially or entirely to the machinery which administers the assertional system by supplying or not supplying hints in the form of either an invariant 'badness' associated with particular assertions, or a dynamic 'badness' computable in the context of the current state of the assertion machine. The 'badness' in general would be a measure of the expected cost in time and space of considering the assertion (cf. Burstall, in chapter 22 of this volume). In his paper in this volume J. M. Foster discusses some aspects of a limited assertional machine. It is our intention to develop these ideas further. in Machine Intelligence 3 (ed) Michie, Donald Department of Machine Intelligence and Perception, University of Edinburgh, Edinburgh University Press, 1968 view details Introduction This paper describes a language for writing algorithms in which less information about the order in which the individual operations are carried out is given than is normal for programming languages. It is at present partly implemented on an Elliott 4120. Various other systems have been described and suggested (see Anderson, 1965; Laski and Buxton, 1962; Markowitz, Hausner, and Karr, 1962; and Opler, 1965). There are various motives for avoiding the giving of specific information about the order of the component statements of a program. First, it enables, transformations to be carried out more easily on the program. This is important both for compilation, where the processes of optimization and of translation into machine code are both transformations into equivalent algorithms, and for artificial intelligence, if we try to improve the computer's representation of its problem. Secondly, there exists a class of problems where the order of the operations cannot be easily specified in advance. This includes the recognition of complex objects, as in syntax analysis, and certain problems of simulation of events occurring in time. Extract: Assertions Assertions The basic elements in the system are not instructions to do something, as are the statements of Algol, but assertions about the data, such as a = b or a + b = c. The evaluation of a program of assertions is not the obeying in specified sequence of a set of instructions, but an attempt to find data which satisfies the assertions. For the purposes of exposition, let us consider the ordinary type of syntactic description of a computing language. < identifier list > :: < Identifier > | < identifier >, < identifier list > This means that an example of an identifier list may be constructed either from an identifier, or from an identifier followed by a comma followed by an identifier list. Looked at from the point of view of a syntax recognizer, this says that a program for recognizing an identifier list may be made from one which recognizes an identifier or an identifier and then a comma and then an identifier list. This could be written out in some such way as the following: identifier list=identifier or (identifier andthen comma andthen identifier list) Notice that the compound operator andthen means both that all the items so connected must be true (and) and also that they correspond in a particular sequence to the input (then). The normal relation between and and or, and the restriction to a particular stream of characters can be removed by introducing parameters. identifier list(a,b)~identifier(a,b) or {identifier(a,c) and comma(c,d) and identifier list(d,b)) where identifier list(a,b) means that from the place a (a tape index number) to the place b there is an example of an identifier list, and similarly for the other assertions. The identifiers c and d belong only to these assertions so they might be localized identifier list(a,b) new c,d= identifier (a,b) or (identifier (a,c) and comma(c,d) and identifier list(d,b)) The intention of the new part of the definition of the assertion is that the assertions in the body of the definition refer to the same new variables c and d. There need be no implication that the assertions are tested in any particular order. Extract: Example 1 Example 1. To write an assertion that between two specified places on an input stream there is an identifier followed by an equals sign followed by an identifier, and that the internal variables which correspond to the textual forms of the identifiers are equal. This can be imagined as part of a simple interpreter. F(s,u) new x,y,p,q,z,t=tape(s,x,y) and tape(y,' = \z) and tape(z,t,u) and lookup(x,p) and lookup(t,q) and p?q tape is a primitive assertion that between the places s andy (in the first example of it) there occurs a textual identifier which is the value of x. The primitive, lookup(x,p), is the assertion that the textual identifier which is the value of x corresponds with the variable p in the environment. The operator' -' is intended to mean 'is substitutablc for'. Thus the definition can be rewritten /'(.v.m) new \\y,p,z,t tapc(s,\,v) and tapc(y,' ~\z) and tapv(z,t,u) and looku/)(x,p) mid lookup(l,p) Extract: Example 2 Example 2. To write the assertion that between two specified places on an input stream there is the textual form of an expression and that, when the identifiers occurring in it are made to correspond with internal variables and the expression is evaluated, the resulting value is that of a particular variable. An expression is confined to identifiers and the + sign. E(a,b,c) new d,e,f,h,i,j=(tape(a,d,c) and lookup(d,b)) or (tape(a,e,f) and tape(f,' + ',i) and E(i,j,c) and lookup(e,h) andplus(h,j,b)) In this definition a and c are the places on the tape, and b is the variable of which the value is the value of the expression. The primitive/>lus(h,j,b) asserts ihath+j=b. Note that it is possible to carry out the following transformation on the above assertion. This transformation has a similarity to the distributive law, and is one that might add efficiency (by avoiding unnecessary evaluation). E{a,b,c) new d,f,h,i,j?tape(a,d,f) and ((lookup(d,b) and/=c)) or (lookup(d,h) and tape(f,' + ',i) and E(i,j,c) and plus(h,j,b)) Extract: Ordering Ordering There are three methods for deducing ordering information for attempting to test assertions, in the system. First, a number may be associated with an assertion to indicate the cost of attempting it. Clearly it is worth while to test assertions which immediately throw away information like ' = ' and ' + ' and there may be other costs known to the programmer from the nature of his problem. Second, each assertion has a number of pass sets associated with it. There is no point in attempting to satisfy tape(a,b,c) if none of the variables has a value, but if a has a value or if b and c have values or if a and b and c all have values, then it may be worth while attempting the assertion. In this case the pass sets would be a, b, c a b,c The effect of testing the assertion would be different in each of these cases. If all the variables had values, testing the assertion would be a check on its validity. If it were false, there would be no need to continue testing the other assertions connected to it by the operator and. If a alone had a value, then values could be supplied for b and c and the other assertions tested to see if they were consistent with these values. Likewise, if/? and c had values, a value could be generated for a. Suppose that the pass sets for lookup(x,y) are x x,y and those for plus {p,q,r) are P>9 P>r and consider the version of E(a,b,c) given at the end of Example 2. Suppose that the value of a alone is given. Then the tree structure below expresses the necessary ordering. In other cases, such as E{a,b,c) where all the arguments have values, the ordering cannot be expressed in so simple a tree structure. The third method of ordering is intended to prevent too uneconomical a use of the store. If two disjoint sets of assertions use one identifier each, then these two identifiers can share the same store provided that, as soon as one of the sets of assertions has been started, the other is locked out until the first is completed. However, there need not be any reason to choose one set to test lirst rather than the other. This corresponds to the locking out of sections of program from one another, which is normally done in interrupt control programs; however, the locking belongs to an identifier rather than to a segment of program. It may be that the use of this principle of ordering will lead to a situation in which nothing can be done, because every assertion is locked out. For example f(xa,ya) g(xa,yb) h(xb,ya) i(xb,yb) where xa and xb are sharing a store and so are ya and yb, will lead to an impossible situation. This can be resolved by copying one of the variable!, and by making nil references to this variable refer to the new copy. This is precisely what is done in recursion, where the use of a new variable of the same name as an old one leads to the use of a copy of the new item in schemes where a stack is used, and to a copy of the old item in schemes where the program refers to the same store and its contents are pushed down. in Machine Intelligence 3 (ed) Michie, Donald Department of Machine Intelligence and Perception, University of Edinburgh, Edinburgh University Press, 1968 view details Introduction Earlier papers (Elcock 1968, and Foster 1968) in this Workshop series introduced design aims and motivation for an assertional language. Briefly, in many problems concerned with complex but well-structured data, it is advantageous and certainly nearer to mathematical practice to be able to ,assert things about the structure of data, instead of being constrained to sequences of imperative statements to construct particular data. Absys 1 (Absys standing for Aberdeeb System) is a working on-line incremental compiler written by the Computer Research Group at Aberdeen for the Elliott 4120. The aim of this paper is to present, in an informal way, some of the main features of the implemented language, and to try to exhibit assertional programming by means of a few examples. The paper is not meant to be a complete description of the language, which will appear elsewhere. Extract: The 'AND' Connective The 'AND' Connective An individual assertion asserts a relation about data objects. Thus the assertion asserts that x and y satisfy an equality relation. The operator ' = ' is to be interpreted in the sense 'substitutable for', and as such has the expected properties of reflexivity, transitivity, etc. In the same spirit, the arithmetic operators have their expected properties so that, for example, the assertions a «■ h -I-1, a<* ] + /;, I + b?a, h + I «■ a are equivalent. A written program consists of assertions. The individual assertions of a program have an implicit (in that it is not written) 'and' connective between them, with properties similar to its logical counterpart. The system acts to construct data satisfying the conjunction of the assertions. Thus, the trivial program x=y y = 2 would make both x and y the datum 2. If the conjunction of the assertions of a program is found to be unsatisfiable then the program terminates unsuccessfully. The occurrence in a program of the assertions y=x, x?2 and 3=y would make that program terminate unsuccessfully, since no data x, y can be constructed to satisfy what has been asserted about x, y, 2 and 3. There are no type declarations in the language. Types are determined progressively and dynamically. Thus, after the assertion, a=b + c The types of a, b and c are constrained only to the set of types meaningful with the asserted ' + ' and ' = ' relations. Extract: Data Directed Control Data Directed Control A written assertional program places no explicit constraints on the order in which particular operations are performed. In particular, if data can be constructed to satisfy all the assertions about them, then these data are independent of the order in which the operations are performed. The on-line system is incremental in that, as assertions are accepted by the system, whatever processing can be done on the basis of data already present in the system is done. This lack of unnecessary concern with control in assertional programs is sufficiently novel to be worth elaborating in the context of a trivial example of list processing. Consider the following constructions in a conventional list processing language with assignment: (i) the constructor operation z<-cons(x,y) which the programmer must ensure is only processed in a data environment in which x and y have appropriate values and the current value of z is no longer needed, (ii) the selector operation x*~/icl(z) which the programmer must ensure is only processed in a data environment in which z has an appropriate value and tho current value of jc is no longer needed. (iii) a test such as equal (x,hd(z)) which the programmer must ensure is only processed in a data environment in which both x and z have values. In Absys 1 z=[x8cy] simply asserts that z is a list whose head is x and whose tail is y. Whether it acts to construct z, or to select x and y, or to test whether x, y and z satisfy the asserted relation, depends solely on the data in the system at the time this assertion is processed. If, at the time of processing the assertion, z is a known datum and it is a list, then the assertion acts as a selector in that x will be asserted to be equal to the head of the list and y will be asserted to be equal to its tail. If, on the other hand, at the time of processing the assertion z is an unknown datum, then the effect is to make z a list and again assert that x is equal to its head and y is equal to its tail, that is, to act as a constructor. In a less trivial example: the rather opaque assignment statement z2<-cons (cons (hd(zl), cons (hd(tl(zl)), cons (hd(tl(zl))),$),<{>)) expresses only one facet of the assertions zl = [ai[b;c]] z2=[[a;6];[c;c]] which asserts a simple relationship over the lists zl and z2. Extract: Functions Functions A lambda construction allows the assertion of functions other than primitive functions of the system. Lambda expressions are sufficiently well known for the features of the Absys 1 implementation to be discussed only briefly and by example. Thus the assertion /'=lambdax, j=>z begin x = [z &q']y = [z &/¡ö'] end introduces a new function/such that f(m,n) = b is equivalent to the compound assertion begin in¡ª [b &q'] n = [b &r'] end that is, an assertion that m and n are lists with the sum of first from h. The primes in the above Horvo to introduce new names, the textual scope of which are delimited by begin and end brackets. Functions may be introduced by partial application of other functions. Thus: /= lambda x, y=>z begin z=x+y end asserts that g is the function lambda y=> z begin z¡ªl+y end Extract: The 'OR' Connective The 'OR' Connective Before going on to discuss the use of lambda constructions for the assertion of recursive functions it is necessary to introduce the assertion of alternatives. Alternatives can be asserted by the construction {AlorA2} where AI and A2 are conjunctions of assertions. I he assertional (implicit) and and or distribute so that, e.g., A\ {A2 or A3} AA is equivalent to {AlA2A4orAlA3A4} The system attempts to construct distinct data to satisfy each conjunction of assertions. Unsatisfiable conjunctions disappear when unsatisflability is detected. To make this clear with a completely artificial example: after />=[1;2] {p = [ct;h] orp = [b;a]} there are two sets of distinct data. In one set a and b are the data 1 and 2 respectively whilst in the other set a and b are the data 2 and 1 respectively. II' we were now to assert, for example, a=b+\ one of the conjunctions will be unsatisfiable and will disappear from the system together with its associated data. By distribution, an assertional program can be transformed into a normal form of a disjunction of conjunctions of elementary assertions. In this form the conjunctions in effect constitute parallel non-interacting programs. Absys 1 distributes the and, or connectives in a way which attempts to minimise unnecessary duplication of processing. Extract: Recursive Functions and Keys Recursive Functions and Keys Let un use the or construction to introduce a function analogous lo the recursive list-processing function map. The intention is that map(p,f), where p is a lint and a function, should have the effect of asserting/'applied to euch item of the list. Consider the assertion map'=lambda p,f begin {null(p) orp = [r' &s']f(r) map(s,f)} end The two alternatives at each call of map are incompatible in that either the list is null or not and if this incompatibility is detected then only one, the intended, conjunction of assertions will be satisfiable. However, since there is no explicit ordering of processing it is possible that processing of map might give rise to further processing of map in the second of the or alternatives before processing the assertion p = [r' &s'] in that alternative. In this case the construction leads to processing which does not terminate. It is clearly not sensible to try to process map (p,f) unless the datum p is already present. Similar considerations apply to many other functions. The lambda construction above does not however express this information. The correct assertion for map is: map'=lambda p, /key p begin {null(p) orp = [r' 8is']f{r) map(s,f)} end The key statement indicates the data that must be present before evaluation of the function may take place. With this construction it is clear that there is no difficulty about termination, since the map(s,f) in the second alternative of the or will not be evaluated until the datum s is present. This datum is constructed only as a result of processing the assertion p = [r' &s'], which is the assertion incompatible with the assertion null(p) in the first alternative of the or. In the example of map above the or acts like a conditional. The following example makes fuller use of the possibilities of the or construction. First, a preliminary assertion: item'=lambda x=>z key x begin x = [p' &q'] {z=p or z= item (q)} end This function item is such that, for example, the assertion i=item ([I ;2;3]) is equivalent to asserting {/=1 or i=2 or i=3} Consider now the following problem. We are given three lists pi, p2 and /;3, and we wish to assert that the triples r, s, t, such that r is an item in pi, s in nn item in p2 and t is an item in p3, satisfy the relation r+s=t. The required assertion is simply r'il/eni(pl) s ? item(p2) t = itcni(p?>) r h.V"/ lu>r oxumplo, if the clulii p\, p2, pTi ulreucly exist uiul p\, p2, p3 arc respectively the lintN [l;2;5;61, |3;7;l|, 11();2;7;4J, then the result would bo throe distinct conjunctions of assertions with associated data r, s, t 1, 3, 4, 1, 1, 2 and 6, 1, 7 respectively. Each of these conjunctions would of course be subject to any further assertions made. in Meltzer, Bernard and Michie, Donald (eds) "Machine Intelligence 4" Edinburgh University Press, 1969 view details Extract: Absys In the late 1960's, a system called Absys l was implemented at the University of Aberdeen by Foster and Elcock (1969). This language was built on the concept of having the user specify assertions rather than commands. Thus, the user would write X = Y, Y = 2 in any order and the system would automatically assign the value of 2 to X. The system also causes programs to terminate unsuccessfully if the constraints are unsatisfiable. in Proceedings of the ACM SIGPLAN symposium on Very high level languages, March 28-29, 1974, Santa Monica, California, United States view details Golux was influenced by Absys, a declarative programming language developed at the University of Aberdeen and reported in a number of papers in the Machine Intelligence series. Absys anticipated a number of Prolog features, such as ?invertability,? ?negation by failure,? ?aggregation operators,? and the central role of backtracking. Like Golux it emphasized the separation of logic from control and the value of changing A by changing C. in [ACM] CACM 31(01) (Jan 1988). view details External link: Online copy Extract: ABSYS For the sake of establishing a historical record, it should be mentioned that the language Absys I (developed in the late 1960s at the University of Edinburgh) already incorporated some of the features currently used in CLP languages. Although non-determinism, the elimination of the occur test, and testing for satisfiability of systems of equations were already present in Absys I, the SL theory of Kowalski and Kuehner, and the illuminating set of examples of Prolog usage given by Colmerauer and his group were to appear only a few years later. The author considers the latter developments essential in providing the impetus for the establishment of LP as practiced today. in [ACM] CACM 31(01) (Jan 1988). view details External link: Online copy in [ACM] CACM 31(01) (Jan 1988). view details in Computational Logic - Essays in Honor of Alan Robinson 1991 view details |