Combination reduction processing method and apparatus

• US 4,734,848 A
• Filed: 07/15/1985
• Issued: 03/29/1988
• Est. Priority Date: 07/17/1984
• Status: Expired due to Term

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Takano, Akihiko, Yamano, Koichi
• Primary Examiner(s): Zache, Raulfe B.
• Application Number:
  US06/754,967
• Time in Patent Office: 988 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/300
• US Class Current: 717/149
• CPC Class Codes: G06F 8/311 Functional or applicative languages; Rewrite languages
• CPC Class Codes: G06F 9/4494 data driven

Abstract

A calculation processing system characterized by decomposing a program into tuples, functions and variables, including abstracting the decomposed program thereby to transform it into a combinator graph, assigning the program in the combinator graph to a plurality of process units, and executing the assigned program through reductions.

Claims

1. A data processing method in an information processing system having a processor means comprising the steps of:

transforming a program into an applicative graph which includes tuples, functions and variables;

abstracting said applicative graph to transform it into a combinator graph;

assigning the program in the combinator graph to a plurality of process units; and

executing an assigned program through reductions.

2. A data processing method according to claim 1, wherein said program is a functional program, and said combinator graph contains tuple structures and no variable.

7. A data processing method according to claim 1, including the further step of storing the program in the combinator graph in a random access memory for simultaneously reading out a plurality of sets and subjecting it to the reductions.

3. A data processing apparatus comprising means to transform a program into an applicative graph which includes tuples, functions and variables and to transform said applicative graph into a combinator graph, connected to means to assign the program in the combinator graph to a plurality of processors provided beforehand, and means connected to said assign means to execute a program assigned by said assign means through reductions.

4. A data processing method in an information processing system having a processor means comprising the steps of:

transforming a program into an applicative graph which includes products, functions, variables, constants and appliers;

subjecting said applicative graph to abstraction thereby to transform it into a combinator graph having a product structure and containing no variable; and

executing the program in the combinator graph having the product structure, through reductions.

5. A data processing method according to claim 4, wherein said step of executing the program through reductions is carried out by pointer caching registers.

6. A data processing method according to claim 5, wherein pointer caching includes the step of pipeline control.

8. A data processing method in an information processing system having processor means and a memory means and comprising the steps of:

abstracting by said processor means a program in said memory means to transform it into a combinator graph which has a product structure; and

executing said combinator graph through reductions.

9. A data processing method according to claim 8, wherein said program is a functional program, and said combinator graph has a product structure and containing no variable.

10. A data processing method according to claim 8, wherein said processor means has a plurality of processing units and said step of executing further includes the step of assigning said combinator graph into said processing units prior to said executing.

11. A data processor method according to claim 8, wherein said method includes the further step of decomposing a program into at least product and functions prior to said abstracting.

12. A data processing method according to claim 8, wherein said program is described in a functional or applicative programming language.

13. A data processing method according to claim 8, wherein said method includes the step of transforming the program into an applicative graph which includes products, functions variables, constants and appliers, prior to transforming said program into a combinator graph.

14. A data processing method according to claim 8, wherein said reductions are carried out by the further step of operating pointer caching registers.

15. A data processing method according to claim 14, wherein said step of pointer caching is performed by the step of pipeline control.

16. A data processing method according to claim 8, including the further step of storing said program, having a combinator graph, in a random access memory for simultaneously reading out a plurality of sets and is subjected to said reductions.

17. A data processing apparatus comprising:

transforming means to transform a program by abstracting into a combinator graph which has a product structure, and means to execute said combinator graph through reductions.

18. A data processing apparatus according to claim 17, wherein said means to execute further includes means to assign the program in the combinator graph to a plurality of processor, prior to executing said combinator graph through reductions.

19. A data processing apparatus according to claim 17, wherein said program is described in a functional or applicative programming language, and further includes means to transform said program into an applicative graph which includes products, functions, variables, constants and appliers prior to transforming said program into a combinator graph.