Tools and methods for real-time dataflow programming language

• US 10,127,022 B2
• Filed: 03/23/2017
• Issued: 11/13/2018
• Est. Priority Date: 03/23/2016
• Status: Active Grant

• Current Assignee: Tyco Fire & Security GmbH (Johnson Controls International plc)
• Original Assignee: Foghorn Systems, Inc. (Johnson Controls International plc)
• Inventors: Sharma, Abhishek, Lucas, Jason
• Primary Examiner(s): Wang, Philip
• Application Number:
  US15/467,318
• Publication Number:
  US 20170277521A1
• Time in Patent Office: 600 Days
• Field of Search: None
• CPC Class Codes: G06F 11/3664 Environments for testing or debugging software
• CPC Class Codes: G06F 11/3668 Software testing software testing in telephone exchanges H04M3/242, testing of hardware G06F11/22
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 8/31 Programming languages or programming paradigms
• CPC Class Codes: G06F 8/34 Graphical or visual programming
• CPC Class Codes: G06F 8/35 model driven
• CPC Class Codes: G06F 8/40 Transformation of program code
• CPC Class Codes: G06F 9/4498 Finite state machines
• CPC Class Codes: G06F 9/48 Program initiating; Program switching, e.g. by interrupt

Abstract

A dataflow programming language can be used to express reactive dataflow programs that can be used in pattern-driven real-time data analysis. One or more tools are provided for the dataflow programming language for checking syntactic and semantic correctness, checking logical correctness, debugging, translation of source code into a secure, portable format (e.g., packaged code), translation of source code (or packaged code) into platform-specific code, batch-mode interpretation, interactive interpretation, simulation and visualization of the dataflow environment, remote execution, monitoring, or any combination of these. These tools embody a method of developing, debugging, and deploying a dataflow graph device.

Claims

1. A method comprising:

providing a development environment for a dataflow programming language allowing specifying of at least one matcher state machine that can perform pattern matching in a received input stream and generate output data, wherein the development environment comprises a plurality of tools to perform at least one of the following;

identifying a plurality of potential data streams;

identifying a set of reactive functions and parameters corresponding to patterns of data in the streams;

identifying a set of handling functions and parameters for transforming data matching declared patterns;

identifying a set of timed events against which patterns of data flow are compared;

creating a dataflow program from expressed intent which describes the identified streams, reactions, functions, and timed events;

providing the dataflow program as input to a two-phase translation tool comprising a first-phase translation tool incorporating a matcher generator for translating program statements to corresponding matchers, data flow topologies, functions, and related symbolic components, and a second-phase translation tool for generating optimized platform-specific hardware instructions corresponding to the translated statements for execution on a hardware platform; and

receiving the output of each phase of the translation tool.

2. The method of claim 1 wherein the development environment has a graphical user interface allowing a user to add one or more compute blocks, wherein each compute block comprises a state machine.

3. The method of claim 2 wherein the graphical user interface allows the user to select an input block to connect to one or more added compute blocks.

4. The method of claim 3 wherein the graphical user interface allows the user to select an output from one or more added compute blocks to connect to an output block.

5. The method of claim 1 wherein the development environment comprises an interpreter component that uses the output of the first-phase translation tool comprising:

an instruction interpreter which emulates the hardware platform in the execution of platform-specific hardware instructions;

a dataflow simulator which emulates a streaming data environment, providing inputs to and collecting outputs from state machine streams; and

a program execution flow controller to examine computations and data in-flight and drive computations back and forth.

6. The method of claim 1 wherein the development environment comprises a live inspection component comprising:

an inspection method that instruments and attaches to a live running program on a particular hardware program, providing insights into the shape of a data graph; and

an inspection method, executing after attachment, then extracts the state of the dataflow computation of a running program which provides an extremely precise and direct insight into computation along with data in consideration.

7. The method of claim 1 wherein the development environment comprises a visualization and dataflow simulation graphical-based component comprising:

a graphical-based interface to allow a program to be authored or displayed or revised in a graphical fashion, thereby assisting a user to gain a more intuitive mental-model for streaming data analysis and thorough understanding of the action of the program; and

a dataflow simulation to test-drive an authored graphical program by visually simulating the actual flow of data via animations and links, with external control by injecting a notion of time allowing the fluidity to go back and forth in data-flow computation.

8. The method of claim 7 wherein the development environment comprises an interpreter component that uses the output of the first-phase translation tool comprising:

an instruction interpreter which emulates the hardware platform in the execution of platform-specific hardware instructions;

a dataflow simulator which emulates a streaming data environment, providing inputs to and collecting outputs from state machine streams; and

a program execution flow controller to examine computations and data in-flight and drive computations back and forth.

9. The method of claim 8 wherein the first-phase translation tool comprises a simulated publisher-subscriber multiplexer, commonly called a message broker, to facilitate the exchange of simulated messages from a plurality of publishers to a plurality of subscribers within a debugging environment.

10. The method of claim 8 wherein the development environment comprises a live inspection component comprising:

an inspection method that instruments and attaches to a live running program on a particular hardware program, providing insights into the shape of a data graph; and

an inspection method, executing after attachment, then extracts the state of the dataflow computation of a running program which provides an extremely precise and direct insight into computation along with data in consideration.

11. The method of claim 1 wherein the output of the first-phase translation tool may be used as an input to the second-phase translation tool, and the translation tool comprises:

a hardware instruction generator which translates instructions from the intermediate representation to a form suitable for execution by the target hardware platform;

a program organization module, which directs the generation of the output into a form suitable for use in a reactive program in a dataflow environment; and

libraries of runtime support components that allow execution on the target hardware platform.

12. The method of claim 11 wherein an output of the second-phase translation tool is an executable program suitable for use on the targeted hardware platform.

13. The method of claim 1 wherein the timed events comprise at least one of an interval of time in which data is to be collected or discarded or a specific point in time before or after which data is to be collected or discarded.

14. The method of claim 1 wherein the timed events comprise an interval of time in which data is to be collected.

15. The method of claim 1 wherein the timed events comprise an interval of time in which data is to be discarded.

16. The method of claim 1 wherein the timed events comprise a specific point in time before which data is to be collected.

17. The method of claim 1 wherein the timed events comprise a specific point in time after which data is to be collected.

18. The method of claim 1 wherein the timed events comprise a specific point in time before which data is to be discarded.

19. The method of claim 1 wherein the timed events comprise a specific point in time after which data is to be discarded.

20. The method or claim 1 wherein the timed events comprise at least one of intervals of time in which data are to be collected or discarded or specific points in time before or after which data are to be collected or discarded.

21. The method of claim 1 wherein the timed events comprise intervals of time in which data are to be collected.

22. The method of claim 1 wherein the timed events comprise intervals of time in which data are to be discarded.

23. The method of claim 1 wherein the timed events comprise specific points in time before which data are to be collected.

24. The method of claim 1 wherein the timed events comprise specific points in time after which data are to be collected.

25. The method of claim 1 wherein the timed events comprise specific points in time before which data are to be discarded.

26. The method of claim 1 wherein the timed events comprise specific points in time after which data are to be discarded.

27. A system for dataflow programming development platform comprising:

a graphical user interface that is displayed on a screen of a computer;

a declarations screen of the graphical user interface of the development platform where a user can specify declarations data types including streams, constants, functions, and patterns, wherein a pattern definition is used to specify a pattern to identify in a stream, and blocks representing the declarations data types are displayed on the screen so that the user can drag and drop the blocks into a desired position on the screen;

a reactions screen of the graphical user interface of the development platform where the user can interconnect the blocks of the declarations data types into a graphical representation of a dataflow program, wherein in the reactions screen, the user can specify and alter interconnects between the different blocks;

a compute block screen of the graphical user interface of the development platform where the user can view and specify an operation performed by a compute block, wherein the user can specify inputs to the compute block and computations on the inputs, and an output of the computer block; and

a code view screen of the graphical user interface of the development platform where the user can view and edit a computer code representation of the operation graphically represented in the compute block screen, wherein the computer code is automatically generated by the development platform.

28. The system of claim 27 comprising:

a compile command for the development platform interface, wherein the user uses compile command to direct the development platform interface to compile a dataflow program package representation of the dataflow program the user has specified using the development platform interface.

29. The system of claim 27 wherein a stream type block can be used as a producer of data and also as transducer, taking input data and outputting data.

30. The system of claim 27 comprising:

an instruction interpreter which emulates the hardware platform in the execution of platform-specific hardware instructions;

a dataflow simulator interface which emulates a streaming data environment, providing inputs to and collecting outputs from state machine streams;

a program execution flow controller to examine computations and data in-flight and drive computations back and forth; and

a simulated publisher-subscriber multiplexer to facilitate the exchange of simulated messages from a plurality of publishers to a plurality of subscribers within a debugging environment.

31. A method of developing a dataflow program comprising:

using a graphical user interface to specify a graphical representation of a dataflow program, the program comprising producer types, transducer types, and extractor types, wherein through the graphical user interface, the user can select and move the producer types, transducer types, and extractor types, represented using blocks, into various positions on a computer screen;

using the graphical user interface, allowing the user to interconnect via interconnection links the blocks representing the producer types, transducer types, and extractor types;

allowing the user to specify details of each of the blocks through the graphical user interface, wherein for a transducer type block, the user can specify an operation;

automatically generating computer source code that corresponds to the dataflow program the user specified using the graphical user interface;

allowing the user to view and edit the computer source code automatically generated in a textual interface; and

allowing the user to specify generating of a computer package of code executable on a target hardware platform that is an implementation of the dataflow program specified by the user using the graphical user interface.

32. The method of claim 31 wherein the operation in a transducer block is a pattern matching operation, and the automatically generating computer source code implements the operation using a state machine reflecting a technique that processes data of an input stream of a producer without backtracking.

33. The method of claim 31 wherein the operation in a transducer block is a pattern matching operation, and the automatically generating computer source code implements the operation using a state machine reflecting a technique that processes stream data from an input of a producer only once, and does not retain data previously read in a buffer to read again later.

34. The method of claim 31 comprising:

providing the user with performance semantic-level debugging capabilities.

35. A method comprising:

providing a development environment for a dataflow programming language allowing specifying of at least one matcher state machine that can perform pattern matching in a received input stream and generate output data, wherein the development environment comprises a plurality of tools to perform at least one of the following;

identifying a plurality of potential data streams;

identifying a set of reactive functions and parameters corresponding to patterns of data in the streams;

identifying a set of handling functions and parameters for transforming data matching declared patterns;

identifying a set of timed events against which patterns of data flow are compared, wherein the timed events comprise at least one of an interval of time in which data is to be collected or discarded or a specific point in time before or after which data is to be collected or discarded;

creating a dataflow program from expressed intent which describes the identified streams, reactions, functions, and timed events;

providing the dataflow program as input to a two-phase translation tool comprising a first-phase translation tool incorporating a matcher generator for translating program statements to corresponding matchers, data flow topologies, functions, and related symbolic components, and a second-phase translation tool for generating optimized platform-specific hardware instructions corresponding to the translated statements for execution on a hardware; and

receiving the output of each phase of the translation tool, wherein the development environment comprises a graphical user interface allowing a user to add one or more compute blocks, and each compute block comprises a state machine.

36. The method of claim 35 wherein the graphical user interface allows the user to select an input block to connect to one or more added compute blocks.

37. The method of claim 36 wherein the graphical user interface allows the user to select an output from one or more added compute blocks to connect to an output block.

38. A method comprising:

providing a development environment for a dataflow programming language allowing specifying of at least one matcher state machine that can perform pattern matching in a received input stream and generate output data, wherein the development environment comprises a plurality of tools to perform at least one of the following;

identifying a plurality of potential data streams;

identifying a set of reactive functions and parameters corresponding to patterns of data in the streams;

identifying a set of handling functions and parameters for transforming data matching declared patterns;

identifying a set of timed events against which patterns of data flow are compared, wherein the timed events comprise at least one of an interval of time in which data is to be collected or discarded or a specific point in time before or after which data is to be collected or discarded;

creating a dataflow program from expressed intent which describes the identified streams, reactions, functions, and timed events;

providing the dataflow program as input to a two-phase translation tool comprising a first-phase translation tool incorporating a matcher generator for translating program statements to corresponding matchers, data flow topologies, functions, and related symbolic components, and a second-phase translation tool for generating optimized platform-specific hardware instructions corresponding to the translated statements for execution on a hardware; and

receiving the output of each phase of the translation tool, wherein the development environment comprises an interpreter component that uses the output of the first-phase translation tool comprising;

an instruction interpreter which emulates the hardware platform in the execution of platform-specific hardware instructions;

a dataflow simulator which emulates a streaming data environment, providing inputs to and collecting outputs from state machine streams; and

a program execution flow controller to examine computations and data in-flight and drive computations back and forth.

39. A method comprising:

providing a development environment for a dataflow programming language allowing specifying of at least one matcher state machine that can perform pattern matching in a received input stream and generate output data, wherein the development environment comprises a plurality of tools to perform at least one of the following;

identifying a plurality of potential data streams;

identifying a set of reactive functions and parameters corresponding to patterns of data in the streams;

identifying a set of handling functions and parameters for transforming data matching declared patterns;

identifying a set of timed events against which patterns of data flow are compared, wherein the timed events comprise at least one of an interval of time in which data is to be collected or discarded or a specific point in time before or after which data is to be collected or discarded;

creating a dataflow program from expressed intent which describes the identified streams, reactions, functions, and timed events;

providing the dataflow program as input to a two-phase translation tool comprising a first-phase translation tool incorporating a matcher generator for translating program statements to corresponding matchers, data flow topologies, functions, and related symbolic components, and a second-phase translation tool for generating optimized platform-specific hardware instructions corresponding to the translated statements for execution on a hardware; and

receiving the output of each phase of the translation tool, wherein the development environment comprises a live inspection component comprising;

an inspection method that instruments and attaches to a live running program on a particular hardware program, providing insights into the shape of a data graph; and

an inspection method, executing after attachment, then extracts the state of the dataflow computation of a running program which provides an extremely precise and direct insight into computation along with data in consideration.

40. A method comprising:

providing a development environment for a dataflow programming language allowing specifying of at least one matcher state machine that can perform pattern matching in a received input stream and generate output data, wherein the development environment comprises a plurality of tools to perform at least one of the following;

identifying a plurality of potential data streams;

identifying a set of reactive functions and parameters corresponding to patterns of data in the streams;

identifying a set of handling functions and parameters for transforming data matching declared patterns;

identifying a set of timed events against which patterns of data flow are compared, wherein the timed events comprise at least one of an interval of time in which data is to be collected or discarded or a specific point in time before or after which data is to be collected or discarded;

creating a dataflow program from expressed intent which describes the identified streams, reactions, functions, and timed events;

providing the dataflow program as input to a two-phase translation tool comprising a first-phase translation tool incorporating a matcher generator for translating program statements to corresponding matchers, data flow topologies, functions, and related symbolic components, and a second-phase translation tool for generating optimized platform-specific hardware instructions corresponding to the translated statements for execution on a hardware; and

receiving the output of each phase of the translation tool, wherein the development environment comprises a visualization and dataflow simulation graphical-based component comprising;

a graphical-based interface to allow a program to be authored or displayed or revised in a graphical fashion, thereby assisting a user to gain a more intuitive mental-model for streaming data analysis and thorough understanding of the action of the program; and

a dataflow simulation to test-drive an authored graphical program by visually simulating the actual flow of data via animations and links, with external control by injecting a notion of time allowing the fluidity to go back and forth in data-flow computation.

41. The method of claim 40 wherein the development environment comprises an interpreter component that uses the output of the first-phase translation tool comprising:

an instruction interpreter which emulates the hardware platform in the execution of platform-specific hardware instructions;

a dataflow simulator which emulates a streaming data environment, providing inputs to and collecting outputs from state machine streams; and

a program execution flow controller to examine computations and data in-flight and drive computations back and forth.

42. The method of claim 41 wherein the first-phase translation tool comprises a simulated publisher-subscriber multiplexer, commonly called a message broker, to facilitate the exchange of simulated messages from a plurality of publishers to a plurality of subscribers within a debugging environment.

43. The method of claim 41 wherein the development environment comprises a live inspection component comprising:

an inspection method that instruments and attaches to a live running program on a particular hardware program, providing insights into the shape of a data graph; and

an inspection method, executing after attachment, then extracts the state of the dataflow computation of a running program which provides an extremely precise and direct insight into computation along with data in consideration.

44. A method comprising:

providing a development environment for a dataflow programming language allowing specifying of at least one matcher state machine that can perform pattern matching in a received input stream and generate output data, wherein the development environment comprises a plurality of tools to perform at least one of the following;

identifying a plurality of potential data streams;

identifying a set of reactive functions and parameters corresponding to patterns of data in the streams;

identifying a set of handling functions and parameters for transforming data matching declared patterns;

identifying a set of timed events against which patterns of data flow are compared, wherein the timed events comprise at least one of an interval of time in which data is to be collected or discarded or a specific point in time before or after which data is to be collected or discarded;

creating a dataflow program from expressed intent which describes the identified streams, reactions, functions, and timed events;

providing the dataflow program as input to a two-phase translation tool comprising a first-phase translation tool incorporating a matcher generator for translating program statements to corresponding matchers, data flow topologies, functions, and related symbolic components, and a second-phase translation tool for generating optimized platform-specific hardware instructions corresponding to the translated statements for execution on a hardware; and

receiving the output of each phase of the translation tool, wherein the output of the first-phase translation tool may be used as an input to the second-phase translation tool, and the translation tool comprises;

a hardware instruction generator which translates instructions from the intermediate representation to a form suitable for execution by the target hardware platform;

a program organization module, which directs the generation of the output into a form suitable for use in a reactive program in a dataflow environment; and

libraries of runtime support components that allow execution on the target hardware platform.

45. The method of claim 44 wherein an output of the second-phase translation tool is an executable program suitable for use on the targeted hardware platform.

46. A method of developing a dataflow program comprising:

using a graphical user interface to specify a graphical representation of a dataflow program, the program comprising producer types, transducer types, and extractor types, wherein through the graphical user interface, a user can select and move the producer types, transducer types, and extractor types, represented using blocks, into various positions on a computer screen;

using the graphical user interface, allowing the user to interconnect via interconnection links the blocks representing the producer types, transducer types, and extractor types;

allowing the user to specify a specification of each of the blocks through the graphical user interface, wherein for a transducer type block, the user can specify an operation;

automatically generating computer source code that corresponds to the dataflow program the user specified using the graphical user interface;

allowing the user to view and edit the computer source code automatically generated in a textual interface; and

allowing the user to specify generating of a computer package of code executable on a target hardware platform that is an implementation of the dataflow program specified by the user using the graphical user interface.

47. The method of claim 46 wherein the operation in a transducer block is a pattern matching operation, and the automatically generating computer source code implements the operation using a state machine reflecting a technique that processes data of an input stream of a producer without backtracking.

48. The method of claim 46 wherein the operation in a transducer block is a pattern matching operation, and the automatically generating computer source code implements the operation using a state machine reflecting technique that processes stream data from an input of a producer only once, and does not retain data previously read in a buffer to read again later.

49. The method of claim 46 comprising:

providing the user with performance semantic-level debugging capabilities.

50. A method of developing a dataflow program comprising:

using a graphical user interface to specify a graphical representation of a dataflow program, the program comprising producer types, transducer types, and extractor types, wherein through the graphical user interface, a user can select and move the producer types, transducer types, and extractor types, represented using blocks, into various positions on a computer screen;

using the graphical user interface, allowing the user to interconnect via interconnection links the blocks representing the producer types, transducer types, and extractor types;

allowing the user to specify internals of each of the blocks through the graphical user interface, wherein for a transducer type block, the user can specify an operation;

automatically generating computer source code that corresponds to the dataflow program the user specified using the graphical user interface;

allowing the user to view and edit the computer source code automatically generated in a textual interface; and

allowing the user to specify generating of a computer package of code executable on a target hardware platform that is an implementation of the dataflow program specified by the user using the graphical user interface.

51. The method of claim 50 wherein the operation in a transducer block is a pattern matching operation, and the automatically generating computer source code implements the operation using a state machine reflecting a technique that processes data of an input stream of a producer without backtracking.

52. The method of claim 50 wherein the operation in a transducer block is a pattern matching operation, and the automatically generating computer source code implements the operation using a state machine reflecting technique that processes stream data from an input of a producer only once, and does not retain data previously read in a buffer to read again later.

53. The method of claim 50 comprising:

providing the user with performance semantic-level debugging capabilities.

54. A method of developing a dataflow program comprising:

using a graphical user interface to specify a graphical representation of a dataflow program, the program comprising producer types, transducer types, and extractor types, wherein through the graphical user interface, the user can select and move the producer types, transducer types, and extractor types, represented using blocks, into various positions on a computer screen;

using the graphical user interface, allowing the user to interconnect via interconnection links the blocks representing the producer types, transducer types, and extractor types;

allowing the user to specify contents of each of the blocks through the graphical user interface, wherein for a transducer type block, the user can specify an operation;

automatically generating computer source code that corresponds to the dataflow program the user specified using the graphical user interface;

allowing the user to view and edit the computer source code automatically generated in a textual interface; and

allowing the user to specify generating of a computer package of code executable on a target hardware platform that is an implementation of the dataflow program specified by the user using the graphical user interface.

55. The method of claim 54 wherein the operation in a transducer block is a pattern matching operation, and the automatically generating computer source code implements the operation using a state machine reflecting a technique that processes data of an input stream of a producer without backtracking.

56. The method of claim 54 wherein the operation in a transducer block is a pattern matching operation, and the automatically generating computer source code implements the operation using a state machine reflecting technique that processes stream data from an input of a producer only once, and does not retain data previously read in a buffer to read again later.

57. The method of claim 54 comprising:

providing the user with performance semantic-level debugging capabilities.

58. A method of developing a dataflow program comprising:

using a graphical user interface to specify a graphical representation of a dataflow program, the program comprising producer types, transducer types, and extractor types, wherein through the graphical user interface, the user can select and move the producer types, transducer types, and extractor types, represented using blocks, into various positions on a computer screen;

using the graphical user interface, allowing the user to interconnect via interconnection links the blocks representing the producer types, transducer types, and extractor types;

allowing the user to specify operations represented by each of the blocks through the graphical user interface, wherein for a transducer type block, the user can specify an operation;

automatically generating computer source code that corresponds to the dataflow program the user specified using the graphical user interface;

allowing the user to view and edit the computer source code automatically generated in a textual interface; and

allowing the user to specify generating of a computer package of code executable on a target hardware platform that is an implementation of the dataflow program specified by the user using the graphical user interface.

59. The method of claim 58 wherein the operation in a transducer block is a pattern matching operation, and the automatically generating computer source code implements the operation using a state machine reflecting technique that processes data of an input stream of a producer without backtracking.

60. The method of claim 59 wherein the operation in a transducer block is a pattern matching operation, and the automatically generating computer source code implements the operation using a state machine reflecting technique that processes stream data from an input of a producer only once, and does not retain data previously read in a buffer to read again later.

61. The method of claim 59 comprising:

providing the user with performance semantic-level debugging capabilities.