System of type inference for tuple graph programs method of executing a tuple graph program across a network

• US 10,642,582 B2
• Filed: 08/24/2017
• Issued: 05/05/2020
• Est. Priority Date: 08/24/2017
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Thambidorai, Gautham, Rosencrantz, Matthew, Ghemawat, Sanjay, Petrovic, Srdjan, Posva, Ivan
• Primary Examiner(s): Chowdhury, Ziaul A
• Application Number:
  US15/685,048
• Publication Number:
  US 20190065154A1
• Time in Patent Office: 985 Days
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 8/31 Programming languages or programming paradigms
• CPC Class Codes: G06F 8/35 model driven
• CPC Class Codes: G06F 8/437 Type checking

Abstract

A programming model provides a method for type inference in programming operations. Information defining one or more attributes of an operation is received, the information specifying a field including a field name and a field type identifier for each of the attributes. Constraints for the operation are determined at least based on the attributes, wherein the constraints restrict at least one of a type of input for the operation or a type of output for the operation. Information defining an input for the operation is received, and it is determined, based on the constraints and the received information defining the input, the type of output for the operation. The type of output is associated with an output for the operation.

Claims

1. A method for type inference in a program, the method comprising:

receiving, by one or more computing devices, first type information for one or more input streams of the program, wherein the program includes a directed graph wherein nodes in the graph represent operators and wherein edges in the graph represent streams of tuples that flow from one operator to another along the edges during execution of the program;

receiving, by the one or more computing devices, for each operator, an output type annotation;

determining, for each operator in one forward pass through the graph, second type information for one or more output streams based on the first type information associated with one or more incoming streams of the operator and the output type annotation associated with the operator, wherein the second type information includes constraints that restrict the tuples included in the one or more streams; and

associating the second type information with the respective one or more output streams.

2. The method of claim 1, wherein the output type annotation includes at least one of “

+”

, “

special”

, a typespecifier, or combinations thereof, wherein the typespecifier specifies a type as a sequence of [fieldname;

typename] tuples.

3. The method of claim 1, further including the step:

raising an error if the output type annotation of the operator is not consistent with the first type information for one or more incoming streams of the operator.

4. A system for type inference in a program, the system comprising:

a memory; and

one or more processors configured to;

receive first type information for one or more input streams of the program, wherein the program includes a directed graph wherein nodes in the graph represent operators and wherein edges in the graph represent streams of tuples that flow from one operator to another along the edges during execution of the program;

receive, for each operator, an output type annotation;

determine, for each operator in one forward pass through the graph, second type information for one or more output streams based on the first type information associated with one or more incoming streams of the operator and the output type annotation associated with the operator, wherein the second type information includes constraints that restrict the tuples included in the one or more streams; and

associate the second type information with the respective one or more output streams.

5. The system of claim 4, wherein the output type annotation includes at least one of “

+”

, “

special”

, a typespecifier, or combinations thereof, wherein the typespecifier specifies a type as a sequence of [fieldname;

typename] tuples.

6. The system of claim 4, wherein the one or more processors are further configured to raise an error if the output type annotation of the operator is not consistent with the first type information for one or more incoming streams of the operator.

7. A non-transitory computer-readable medium storing instructions executable by one or more processors for performing a method for type inference in a program, comprising:

receiving first type information for one or more input streams of the program, wherein the program includes a directed graph wherein nodes in the graph represent operators and wherein edges in the graph represent streams of tuples that flow from one operator to another along the edges during execution of the program;

receiving, for each operator, an output type annotation;

determining, for each operator in one forward pass through the graph, second type information for one or more output streams based on the first type information associated with one or more incoming streams of the operator and the output type annotation associated with the operator, wherein the second type information includes constraints that restrict the tuples included in the one or more streams; and

associating the second type information with the respective one or more output streams.

8. The non-transitory computer-readable medium of claim 7, wherein the output type annotation includes at least one of “

+”

, “

special”

, a typespecifier, or combinations thereof, wherein the typespecifier specifies a type as a sequence of [fieldname;

typename] tuples.

9. The non-transitory computer-readable medium of claim 7, wherein the method further comprises raising an error if the output type annotation of the operator is not consistent with the first type information for one or more incoming streams of the operator.