AL(ID:1615/al:002)Associative Languagefor Associative Language Feldman, MIT Lincoln Labs 1966 Places Related languages
References: AL A ring-implemented data structure may be regarded as a collection of objects connected together in such a way as to express implicitly the relationships between those objects. Having built such a structure, one wishes then to be able to interrogate it, to ask such questions as What objects are coloured green? Who is the father of James? What relation is Jack of John? If the types of questions that will be asked of a data structure are known in advance, then that structure can be built in such a way as to answer those questions efficiently. However, it may often happen that questions will be asked for which the structure is not so well suited. This problem becomes aggravated when the structure is spread across several "pages," not all of which can be in core simultaneously. For example, if it were suddenly required to find the weights of a collection of objects and "weight" were a simple data attribute, it would be unlikely that all the relevant pages would be in core together when the tluestion was asked. An interesting solution to this retrieval problem has been embodied by Feldman in his language AL, and extended into a paged scheme by Rovner, whereby relationships are obtained not from the positions of the name (address) of the object in some sequences (as is the case for a ring structure) but from hash-coded functions of the object name. In Feldman's scheme, there is a collection of entities which may in turn be considered as Object or as Value, according to some Arribute. Thus: Father (John) = Jim Son (Jim) = John or generally: Attribute (Object) = Value (In the general case, the Values need not come from the same collection as the objects, i.e, one could have; Weight (Ball) = 2.4) In AL, one may ask six basic questions: 1. A(0) = ? A = Attribute 2. A(?) = V 3. ?(0) =V 0=Object 4. A(?)=? V=Value 5. ?(0) = ? 6. ?(?) = v AL reserves letters for use as (bound) variables, so that "nested" questions may be asked: for instance; UNCLES(JOHN) = X SONS(X) = ? answers the question, Who are the sons of John's Uncles? It can be seen that this is essentially the same as the Search and Find functions in CORAL and APL. The actual implementation is as follows: Attribute, Object and Value are stored as a triplet at an address obtained by hash-coding the internal name of Attribute with the internal name of Object. This address may not be unique, as: (a) The number of unique results from hash-coding set of Attributes with the set of Objects will in general be less than the number of possible Attribute-Object pairs, so that "multiple hits" will occur. (b) A given Attribute-Object pair may have multiple Values (e.g, Sons (John)= ?). All triplets which hash to the same address are therefore stored on a link ring, grouped by Attri- butes. There is also a use ring which threads through all the triplets which have a common Value (See Figure 10). The purpose of this is to answer questions such as A(?) = V and ?(0) = v in which the hash function cannot be calculated directly. The start of the use ring for any object also contains one data word for that object. This implementation cannot be paged conveniently as it stands, as the use ring will probably have its elements scattered randomly throughout the memory. Rovner has proposed a solution to this problem, whereby there are two classes of pages, A-pages and 0-pages. Each Attribute-Object-Value triplet is placed once in an A-page by Attribute, and twice (possibly) in an 0-page by the hash of Object and Value and by Value (clearly, these two may give the same page, as Rovner has 2 r Objects and 23 O- memory pages). The link rings are then built in these pages, and the idea is that, whatever is required to be found, the appropriate page(s) can be brought into core memory and page swapping in the course of an interrogation can be avoided. The price that is paid for this is of course the redundancy in the in- formation stored. Whether this sort of scheme is useful in any particular application depends of course on circumstances; it will be most advantageous when large complex structures are randomly interrogated, as search time is more or less independent of the size and complexity of the data structure. But it is worth noting that the extra calculation involved in hashing the addresses should be offset against the address calculations which must also be performed when a conventional ring structure is paged by software. Also, although it is in principle possible to build conventional ring structures in pages, in practice this either involves considerable intuition and foresight, or some prior calculation. in Proceedings A.C.M. National Meeting, 1967 view details |