Browse Prior Art Database

An Architecture that Efficiently Updates Associative Aggregates in Applicative Programming Languages

IP.com Disclosure Number: IPCOM000148951D
Original Publication Date: 1985-Sep-30
Included in the Prior Art Database: 2007-Mar-30
Document File: 28 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

O'Donnell, John T.: AUTHOR [+2]

Abstract

An Architecture that Efficiently Updates Associative Aggregates in Applicative Programming Languages

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 28

An Architecture that

Efficiently Updates Associative Aggregates in Applicative Programming Languages

by

John T. O'Dannell

Computer Science Department Indiana University Bloomington, IN 47405

  TECHNICAL REPORT NO. 180
An Architecture that Efficiently Updates Associative Aggregates in Applicative Programming Languages

by

John T. O'Donnell

September, 1985

To appear in The Proceedings o/ the IFIP International Conference on F'unctiond Program- ming Languagca and Computer Architeeturn in Nancy, fiance, September 16-19, 1885.

[This page contains 1 picture or other non-text object]

Page 2 of 28

[This page contains 1 picture or other non-text object]

Page 3 of 28

An Architecture that

Efficiently Updates Associative Aggregates in Applicative Programming Languages

John T. O'Donnell

Computer Science Department 101 Lindley Hall
Indiana University
Bloomington, Indiana 47405

Abstract

   Applicative (also called functional) programming systems prohibit side effects, in- cludin g assignments to variables. This restrict ion has several advantages, including referential transparency and potential parallel program execution. A major disadvan- tage, however, is that aggregate data structures become very expensive to maintain: when the programmer updates a single element in an aggregate, many applicative lan- guage implementations must completely recopy the aggregate. This paper solves the aggregate update problem with a two-level architecture: a microprogram maintains "associative aggregate" data structures, and a hardware memory design (the Associa- t ive Aggregate Machine) implements powerful insert ion, deletion and searching oper- ations required by the microprogram. The Associative Aggregate Machine contains a linear sequence of cells comprising storage and combinational logic. Each cell is con- nected to its predecessor and successor, so the sequence of cells forms a shift register that supports insertion and deletion. In addition, a binary tree of combinational logic nodes performs fast associative searching through tbe sequence of cells. The Associa- tive Aggregate Machine architecture is extremely regular and is well suited for VLSI implementation.

[This page contains 1 picture or other non-text object]

Page 4 of 28

1. Introduction

   Purely applicative languages (also called functional languages) have many advan- tages, but their implementation raises several problems. This paper introduces a new solution to one of them, the "aggregate update problem". We define an associative aggregate data structure that satisfies the representation and accessing requirements of lists, vectors and environments, and we show how to implement the aggregate access functions very efficiently (all aggregate accesses require a constant number of storage cycles). Our solution does not rely on compile-time analysis of the applicative program. Instead, i...