Browse Prior Art Database

A COMPILER FOR AN ASSOCIATIVE OBJECT MACHINE

IP.com Disclosure Number: IPCOM000128408D
Original Publication Date: 1969-May-01
Included in the Prior Art Database: 2005-Sep-15

Publishing Venue

Software Patent Institute

Related People

Ash, William L.: AUTHOR [+3]

Abstract

This paper discusses the design and construction of a compiler whose source language consists of sentences of a restricted predicate calculus, and whose output object code operates on a simulated associative target machine. The source programs are characterizations of relations, used for deriving one relation from others, and for completing relations. A program realizes the completion of a relation when it defines that relation in terms of itself, i.e., when the definition is recursive.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 5% of the total text.

Page 1 of 23

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A COMPILER FOR AN ASSOCIATIVE OBJECT MACHINE

THE UNIVERSITY OF MICHIGAN Technical Report 17 William L. Ash

CONCOMP: Research in Conversational Use of Computers ORA Project 07449 F.H. Westervelt, Director

supported by: DEPARTMENT OF DEFENSE ADVANCED RESEARCH PROJECTS AGENCY WASHINGTON, D.C.

CONTRACT NO. DA-49-083 OSA-3050 ARPA ORDER NO. 716

administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR May 1969

ABSTRACT

This paper discusses the design and construction of a compiler whose source language consists of sentences of a restricted predicate calculus, and whose output object code operates on a simulated associative target machine. The source programs are characterizations of relations, used for deriving one relation from others, and for completing relations. A program realizes the completion of a relation when it defines that relation in terms of itself, i.e., when the definition is recursive.

The most significant feature of such a compiler is that there are two levels of operators and operands. The first level operators are the logical connectives whose operands are relations, which in turn have as their "operands" relational arguments. The lower level operands deter- mine the context-dependent interpretation of the higher level operators. The parse is further encumbered by the fact that the logical connectives in such a framework do not lend themselves to a production grammar. The situation is resolved by constructing a digraph to represent the definition of the relation. This construction proceeds using a back-up technique. The output of the compiler is an object program in the form of a macro definition, to be expanded for an interpretive associative target machine.

TABLE OF CONTENTS

ABSTRACT.....iii
l. INTRODUCTION.....1
2. THE ASSOCIATIVE OBJECT LANGUAGE: TRAMP.....5

University of Michigan Page 1 May 01, 1969

Page 2 of 23

A COMPILER FOR AN ASSOCIATIVE OBJECT MACHINE

3. OPERATIONAL BEHAVIOR WITH THE COMPILER.....11
3.1 Compiler Source Language.....13
4. THE TRAMP INFERENCE COMPILER.....17
4.1 An Overview.....l9
4.2 Phase 1.....21
4.3 Phase2.....27
Initial Table Construction.....29
4.3.1 Checks and Revisions to CHAIN.....33
4.4 Phase 3.....36
4.4.1 Transitive and Symmetric Relations.....46
4.4.2 Further Semantics.....49
REFERENCES.....53

LIST OF FIGURES

Figure 1. Sample Source Programs.....4
Figure 2. List Processing for Relations.....19

LIST OF TABLES

Table 1. CHAIN for Program(3).....31
Table 2. CHAIN for Program (4).....34
Table 3. CHAIN for Program (4); First Revision.....35
Table 4. CHAIN for Program (4); B Attached to A.....38
Table 5. CHAIN for Program (6).....40
Table 6. Final Table for Program (6).....1

[ Page x blank ]

[ chapter 1 ] 1. INTRODUCTION

An associative computer memory can effectively be employed to approximate "content addressability." By an associative memory we mean a memory that stores information in ordered n-tuples, called ass...