KLS II(ID:5614/kls002)Knotted List Structures with enhancementsKnotted List Structures with enhancements J. Harold McBeth General Electric TEMPO Santa Barbara, 1963 Related languages
References: lem in list processing, as proposed by Collins ~ and incorporated in KLS 2 and SLIP 3 by Weizenbaum, is unsatisfactory. In the reference count system, each list carries a count of the number of references to the list in the system; i.e., this number is the num- ber of words which point to the list. When a new word is created which refers to a list, the reference counter for that list is incre- mented by one; similarly, when any such word is destroyed, the reference counter of the list is decreased by one. When the refer- ence counter becomes zero for a list the list itself is erased. Note that the reference counter for a list must be changed each time a word containing the name of the list is created, covered over, or destroyed. If a list is used as a sublist within its own structure--that is, if any list structure is circulai~the counter for that list can never become zero. This means that there is always the danger that entire list structures can take valuable memory space and yet be unaceessible within the KLS system. This holds also for SLIP. Mr. Weizenbaum recognized this difficulty, and in his article 2 he mentioned the solution, as follows: "An operation is provided which determines whether placing the name of a particular list on a list structure will result in circularity. If the answer is yes [to the question of circularity], then that name is put on the structure nonresponsibly and the corresponding counter is not tallied." This operation must involve tracing the entire structure in question, for there is no other way to discover a circularity. Clearly, each time a word containing the name of any list L is inserted into a list, the entire structure of L must be traced, in order to determine whether to tally the counter. This necessitates the use of so much extra machine time that the system becomes prohibitively expensive; for this reason KLS and SLIP provide no such safeguard against the loss of circular structures. A thorough revision of KLS has been made by the author of this note; this language, KLS II, avoids the difficulties here pointed out in KLS and SLIP, essentially by an application of McCar- thy's garbage collection method. KLS II extends and streamlines KLS in other ways as well. A write-up is forthcoming. DOI in [ACM] CACM 6(09) (September 1963) view details It is concluded that the data-base question-answerer has passed from initial research into the early developmental phase. The most difficult and important research questions for the advancement of general-purpose language processors are seen to be concerned with measuring meaning, dealing with ambiguities, translating into formal languages and searching large tree structures. DOI Extract: DEACON and KLS II The DEACON Breadboard. At General Electric's TEMPO, F. Thompson and J. Craig have reported on DEACON -- a data-based question answerer which is part of a man-machine communication system that, may eventually allow operators to communicate with each other and with the computer in a subset, of natural English. The question answerer is programmed in a special list-processing language, KLS-II, developed at TEMPO for this system. At this writing, many aspects of the natural-language programs have been checked out and the offers great potential for making inferences as well as for providing explicitly stored data. In general, DEACON depends on a list-structured data base. Thompson makes explicit the importance of a wellunderstood data structure and introduces a principle of equivalence between the word classes of syntactic analysis and the semantic categories of the data base. As a result his programs do not break neatly into a parsing system, a semantic analyzer, and a data processor, although these phases are still distinguishable. His language analysis parses a sentence into the names of lists and the calls to operations to be performed on the lists. These operations are performed immediately and the resulting sublists are tested for their truth value in the last phase of data processing. The TEMPO system accepts the occurrence of ambiguous analyses but usually these are resolved in terms of the data context of the sentence. Each remaining analysis is dealt with as a separate statement or question. It generalizes to a broad range of data and to a reasonably complex subset of English. The system is self-contained in that it both reads its own data and answers questions. It makes explicit the principles of structure and question analysis which although previously implicit in such systems as Baseball, SAD SAM and the PLM were not then fully conceptualized. It is theoretically important in showing the continuity between syntactic, semantic and symboliclogical analyses of English in a data base system. in [ACM] CACM 8(01) Jan 1965 view details |