SYSTEM OF TYPE INFERENCE FOR TUPLE GRAPH PROGRAMS METHOD OF EXECUTING A TUPLE GRAPH PROGRAM ACROSS A NETWORK

• US 20190065154A1
• Filed: 08/24/2017
• Published: 02/28/2019
• Est. Priority Date: 08/24/2017
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Thambidorai, Gautham, Rosencrantz, Matthew, Ghemawat, Sanjay, Petrovic, Srdjan, Posva, Ivan
• Granted Patent: US 10,642,582 B2
• Time in Patent Office: 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 programming operations, comprising:

receiving information defining one or more attributes of an operation, the information specifying a field including a field name and a field type identifier for each of the attributes;

receiving information defining a behavior for the operation, the behavior being configured with reference to the one or more attributes;

determining, by one or more computing devices, constraints for the operation based on the attributes and the behavior, wherein the constraints restrict at least one of a type of input for the operation or a type of output for the operation;

receiving information defining an input for the operation;

determining, based on the constraints and the received information defining the input, the type of output for the operation; and

associating the type of output with an output for the operation.

2. The method of claim 1, wherein the behavior for the operation is defined at least in part by the input, and wherein the constraints determined for the output are based on the input for the operation.

3. The method of claim 1, wherein the behavior for the operation is defined at least in part by the output, and wherein the constraints determined for the input are based on the output for the operation.

4. The method of claim 1, wherein receiving information defining one or more attributes of the operation comprises receiving a tuple specifying two or more fields for the attribute.

5. The method of claim 4, wherein the constraints include a name field, the name field of the constraints corresponding to a type field of at least one of the input or output.

6. The method of claim 5, wherein the name field for a first constraint corresponds to the type field of the input, and wherein the name field for a second constraint corresponds to the type field of the output.

7. The method of claim 4, wherein the field type identifier includes one of:

bool, bytes, string, double, float, int32, uint32, int64, or uint64.

8. The method of claim 1, wherein automatically determining the constraints for the operation is performed when compiling code for the operation.

9. The method of claim 1, further comprising:

receiving information defining an output for the operation;

determining, with the one or more computing devices, whether the output is structured with a type that meets the constraints;

accepting the output when it is structured with a type that meets the constraints; and

rejecting the output when it is not structured with a type that meets the constraints.

10. The method of claim 9, wherein rejecting the output comprises flagging the input or output as containing an error.

11. The method of claim 9, wherein rejecting the output comprises forcing reentry of the information defining the input or output.

12. A method for type inference in a program including 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 program execution:

receiving first type information for one or more input streams of the program,

receiving, for each operator, an output type annotation;

determining, for each operator, 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.

13. The method of claim 12, wherein determining for each operator occurs in one forward pass through the graph.

14. The method of claim 12, 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.

15. The method of claim 12, 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.

16. A system for type inference in programming operations, comprising:

one or more processors configured to;

receive information defining one or more attributes of an operation, the information specifying a field including a field name and a field type identifier for each of the attributes;

determining constraints for the operation 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;

receive information defining an input for the operation;

determine, based on the constraints and the received information defining the input, the type of output for the operation; and

associate the type of output with an output for the operation.

17. The system of claim 16, wherein the one or more processors are further configured to:

receive information defining an output for the operation;

determine, with the one or more computing devices, whether the output is structured with a type that meets the constraints;

accept the output when it is structured with a type that meets the constraints; and

reject the output when it is not structured with a type that meets the constraints.

18. The system of claim 17, wherein rejecting the output comprises flagging the output as containing an error.

19. The system of claim 17, wherein rejecting the input or output comprises forcing reentry of the information defining the input or output.