STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT

Not applicable to this application.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The invention relates to the field of programming, and more particularly to a system and method of constructing a compiler for computational systems, where computational systems consist of a combination of one or more programs implemented in software or in hardware and the software and hardware necessary to run them. The invention additionally relates to the particular field where that compiler is extensible via user-created programs conforming to certain specifications, which may direct the functioning of the compiler and which may, themselves, implement portions of the functionality of the compiler. The invention additionally relates to the particular field where that compiler automatically verifies the logical properties of the target system that the user has indicated must hold.

2. Description of the Related Art

Any discussion of the prior art throughout the specification should in no way be considered as an admission that such prior art is widely known or forms part of common general knowledge in the field. Current compiler systems do not model full systems, comprising multiple programs and their environments, and do not incorporate substantial user-defined operations at compile time.

Modern computational systems are often composed of many programs running as many communicating processes on many machines, both virtual and physical, dependent on different operating systems, configurations, libraries, files, networking, and other required artifacts (those operating systems, configurations, libraries, files, networking and other required artifacts collectively comprising the environment). Containerization, virtual machines, and so-called serverless computing have emerged as some examples of different schemes for combining programs with their dependencies in order to avoid problems associated with building programs separately from their environment and deploying them separately from the construction and deployment of the environment upon which they depend. However, even with the introduction of these techniques, the designers and programmers of computational systems still must deal with separate source artifacts for each program as well as separate source artifacts for some or all of the elements comprising the environment. In order to create and modify systems that maintain desired correctness properties, including basic functionality, scalability, error handling, security guarantees, maintainability, and extensibility, the system designers and programmers must construct a mental model of the interactions between all of the individual programs and their environments. In order to construct such a mental model, the designer or programmer is forced to piece together the programs and environment by looking at the source code of each program, applying their understanding of the methods by which environments are constructed, configuration is applied, how and where processes are deployed, and by what names or at which addresses and ports they are addressable. There currently exists no reified representation of the interactions between programs or between programs and their environment even though it is exactly that representation that the designers and programmers must mentally manipulate to build effective and safe computational systems.

Thus, a need exists for a compiler system that models multiple programs and their environments simultaneously, producing as output the full set of programs and environment configuration defined in the source code provided. Further, this system must permit expressive constraints to be placed upon the interaction between each component defined in the source code in order to ensure the proper functioning of the system produced.

BRIEF SUMMARY OF THE INVENTION

In view of the foregoing background, a system and method of constructing a compiler for computational systems is disclosed. One embodiment of the present disclosure relates to an electronic system that, having received (1) a properly-formatted representation of the scopes, modules, and flows (defined below) that comprise the target system, (2) a possibly-empty set of module combinators, abstract block tree simplifiers, scopes, runners, and runnable environment and artifact loaders (defined below), and (3) a possibly-empty set of logical assertions and requirements associated with modules and inputs and outputs of modules and flows as well as implication assertions to propagate logical assertions across arbitrary module and flow invocations, verifies the logical properties of the described system and generates one or more compiled artifacts that represent the scopes and flows defined in the input representation. In one embodiment, the system generates source code and configuration files that encompass the functionality defined by the provided flow definitions for every defined scope. The source code may conform to any computer language or languages, may make use of any features within that language or languages, and may be compiled by any compiler for that language or languages.

According to one aspect of the disclosure, the system generates an intermediate representation of the invocations comprising the portion of each flow that resides within each scope and then converts such intermediate representations into abstract syntax trees by querying the module combinator associated with each invocation to retrieve its portion of the abstract syntax tree. According to another aspect of the disclosure, each such abstract syntax tree may conform to any format that the associated scope accepts and the system then converts each such abstract syntax tree into program source code and configuration files by querying the scope containing the modules associated with the invocations from which the abstract syntax tree was derived. According to another aspect of the disclosure, the system directs the compilation of those generated source code and configuration files into compiled artifacts by querying the scope containing the modules associated with the invocations from which the source code and configuration files were derived. According to another aspect of the disclosure, the system directs the staging of those compiled artifacts in a staging environment. According to another aspect of the disclosure, the system directs the deployment of those compiled artifacts from the staging environment to a production environment by querying the specified deployment runners.

In another embodiment, the disclosed system enables the designers and programmers interacting with it to define logical properties that must be true of the data passed to the inputs of modules or flows, logical properties that are guaranteed of the outputs of modules or flows, logical properties that are assumed to be true of certain values, logical implications linking properties of inputs to modules or flows to properties of outputs of modules or flows, or logical properties required of data that passes into or out from a scope. In this embodiment, the logical properties and implications may be represented in any suitable language that represents a system of logic. Some examples of such languages include but are not limited to: Horn clauses, S-expressions with the and, or, not equality, etc. logical operators, or mathematical notation. According to one aspect of this system, such logical properties may be automatically proven to hold in all cases by showing that the logical assumptions and logical assertions on all inputs, combined with the logical implications, are sufficient to satisfy all logical requirements on outputs as well as all requirements of the values entering and exiting scope boundaries.

In another embodiment, the disclosed compiler system provides extension points at which user-created programs may be supplied to control the operation of the compilation of the user-defined computational system. The ability to run user-created programs in such a manner allows for the disclosed system to remain agnostic to the technologies that comprise the target computational system and provides the even more important advantage of allowing for a separation of concerns amongst subsets of designers and programmers. Some designers and programmers at some times may concern themselves solely with defining the properties of the runtime system as well as abstractions upon which feature-related functionality may be built. These more infrastructure-level concerns may often be confined to the user-provided extension code in scopes and module combinators, freeing the designers and programmers focused on feature-related functionality development to focus exclusively on that business logic. Further, future designers and programmers seeking to understand the target computational system are able to focus separately on the infrastructure-level structure or the business-oriented structure.

Terms

The following is a glossary of terms used in this disclosure. In no case are the specific names attributed to the invented classes of functionality intended to be limiting of the scope of the disclosure. The disclosed system is intended to encompass both the structural and functional equivalents thereof. In all instances where an element is said to be comprised of multiple sub-elements, it is intended to be the case that any of those sub-elements may or may not be present and any such combination is intended to fall within the scope of the present disclosure.

Scope—A scope may represent anything in a computational system that may contain state or may otherwise be said to exist for a duration that exceeds that of a single processing step. For example, operating system processes, containers (e.g. LXC or Docker containers), virtual machines, databases, firewalls, subnets, or even entire datacenters could be represented as scopes. Scopes may be arranged by the designer or programmer into hierarchies whereby one scope is said to “reside within” another scope. When defining scopes, the designer or programmer is really defining a template from which any number of incarnations of that scope may ultimately be realized when the scope is deployed or in the process of its ongoing operation. The disclosed system utilizes user-provided programs, provided in the form of runnable environments (defined below) to generate the compile-time artifacts of scopes. Scopes generate one or more of the following compile-time artifacts: generated source files, compiled artifacts, staged artifacts, configuration files, files to assist in the process of monitoring and debugging, or files to assist in the deployment of the incarnations of the scope.

Flow—A flow is a logical computation that may take place within one or more scopes and is composed of the invocation of one or more module instances (defined below), some of whose outputs are directed to the inputs of one or more other module instances, some of whose inputs are provided with each invocation of the flow as parameters to the flow invocation, some of whose outputs are returned from the flow invocation as the resulting output or outputs of the flow invocation, and some of whose inputs are set to be literal data provided at the time of the definition of the flow, possibly containing templated variables that are provided at a later compilation step but prior to deployment.

Module—A module comprises a source code library and associated metadata that the disclosed system uses to determine what inputs may be provided to invocations of the module and what sets of outputs may be returned by such invocations. Module source code is written in any programming language. Some modules may require some initialization logic which runs once upon the creation of their containing scope. Such modules are often thought of as stateful modules because their state must be initialized. Modules may define an initialization procedure that is run at the initialization of the scope. Furthermore, some modules may accept configuration information which may further direct the number and nature of the inputs and outputs of the module as well as the logical properties associated with it. Modules are instantiated in a scope and flows consist of invocations of such module instances. Each module invocation may produce only one set of output values but each module may declare the ability to produce any number of such output types. Module combinators (defined below) must be able to generate target source code that can determine the type of output a given invocation generated and continue the running program flow only for those subsequent module invocations that make use of that set of output values. By default, no module invocation may be passed two arguments where one argument is derived from one output type of any ancestor module and another argument is derived from another output type of the same ancestor module. Modules may, however, declare some sets of parameters as only requiring one of the given parameters to be provided. Such sets of parameters may be provided arguments that violate this identical output type requirement. Values derived from separate output types of the same module invocation may be provided as arguments to such sets of parameters. The resultant code will invoke the module regardless of which output type was produced. This allows for, for example, default values to be provided in place of error results. For example, a module (M) may declare itself able to produce an error output type that consists of an identifier (A) and a message (B) as well as a success output type that consists of a result (C) and a status (D). Each output type may contain any number of output values and a module may declare any number of output types. A subsequent module invocation (E) may take A and B as inputs. Invocation E will only be executed at runtime if the invocation of module M resulted in an error output type. Another subsequent module invocation (F) may take C and D as inputs. Invocation F will only be executed at runtime if the invocation of module M resulted in a success output type. If a module invocation (G) is defined to take A and C as inputs, the system would yield an error because A and C are from two separate output types. However, if module G was annotated to indicate that A and C are part of a parameter set, the invocation would be allowed and only one of A or C would be available to be provided as an argument at runtime.

Module Combinator—A module combinator is a computation that transforms a description of an invocation of a module instance, provided in a well-defined format herein labeled an abstract block, into a representation of a portion of an abstract syntax tree in a well-defined format, based on the type of scope that contains the invoked module. Module combinators are provided as runnable environments (defined below), which implement an ideal flow (defined below).

Runnable environment—A runnable environment comprises a data description of a set of runnable scopes (defined below) as well as a data description of a set of runnable flows (defined below) that may be invoked by an actor external to the runnable scopes. The disclosed system provides numerous extension points whereby designers or programmers making use of the system may inject their own functionality to direct the disclosed compilation process. In all cases, that injected functionality takes the form of invocations of runnable flows on specified runnable environments.

Runnable scope—A runnable scope comprises a data description of a means of loading a computational artifact in a computational environment (an artifact loader), a data description of the configuration of that artifact loader including an abstract “location” at which said artifact loader may find the desired computational artifact, and a data definition of a means of running that computational artifact in a computational environment (a runner). That computational environment may be the computer system presently executing the runnable environment in which the runnable scope is declared, it may be an external computer system that the computer system presently executing the runnable environment can connect to and control, it may be a virtualized computer system either on the computer system presently executing the runnable environment or external to it, or it may be any other system capable of performing computation. Similarly to scopes, a runnable scope is a template from which any number of incarnations may ultimately be realized when the runnable scope is run or in the process of its ongoing operation. For example, a runnable scope may consist of a specification pointing to the builtin URL download artifact loader, an artifact loader configuration specifying a URL from which the runnable scope artifact may be downloaded, and a specification pointing to the builtin native executable runner. When the disclosed system needs to launch such a runnable scope, the builtin URL download artifact loader will download the file at the provided URL to the local computation environment and the builtin native executable runner will execute the local file.

Artifact loader—An artifact loader is responsible for loading a computational artifact and may accept a data description of a configuration to direct the artifact loader's operation. The artifact loader may load a computational artifact from a remote system and it may place such an artifact on the computational system presently executing the runnable environment or on any other computational system. The artifact loader will usually render the computational artifact into a state such that it may be executed after the artifact loader completes its operation. Some examples of a computational artifact that an artifact loader may load are, without limitation and provided only for pedagogical purposes: an executable file containing a native software process, a bundle of code intended to be interpreted by an interpreter, a virtual machine image, a container image, a template for the creation of computational resources in a cloud environment, an image intended to be transferred to a hardware device such as an FPGA, a schematic intended to be fabricated into a custom piece of hardware, or any other artifact that may eventually perform some computation. In the disclosed system, there are two types of artifact loaders: builtin and custom. Builtin loaders are provided by an embodiment of the disclosed system and may be referred to by a name or other identifier in interactions between a designer or programmer and the disclosed system. Custom loaders are implemented as runnable environments that provide a well-known ideal flow (defined below) that may be invoked by the disclosed system to provide the functionality of an artifact loader. Since custom loaders are themselves runnable environments, the artifact loaders required in their runnable environments may also be either builtin or custom. Every such chain of artifact loaders must eventually end in a builtin loader. For example, a custom artifact loader may consist of a runnable environment that exposes a runnable flow that downloads files from an FTP site. That custom artifact loader may indicate in its runnable environment that it be loaded by the builtin artifact loader that downloads artifacts via HTTP GET requests. Thus, the custom artifact loader may be hosted at an HTTP address from which the builtin loader will download it and, when run, may download other artifacts via FTP.

Runner—A runner is responsible for running a computational artifact on a computational system. There are two types of runners: builtin and custom. Builtin runners are provided by an embodiment of the disclosed system and may be referred to by a name or other identifier in the interactions between a designer or programmer and the disclosed system. Custom runners are implemented as runnable environments that provide a well-known ideal flow (defined below) that may be invoked by the disclosed system to provide the functionality of a runner. Since custom runners are themselves runnable environments, the runners required in their runnable environments may also be either builtin or custom. Every such chain of runnable environments must eventually end in a builtin runner. For example, one type of runner may be implemented as a native executable that accepts arguments passed via operating system environment variables, invokes an HTTP endpoint with a request containing a JSON representation of the data in the environment variables, and returns the result of the HTTP invocation by writing that result in JSON format to its standard output file. That runner may declare in its runnable environment that it should be invoked by another runner that accepts arguments as protocol buffer-encoded data passed to its standard input file, invokes the runner that it wraps by passing those arguments via operating system environment variables to another native executable and translates the JSON-formatted data that that executable sends to its standard output file into protocol buffer-encoded data that it writes to its own standard output file. Finally, that runner may indicate in its runnable environment that it should be invoked by the builtin runner that invokes a native executable and passes the arguments the disclosed system provides it to the indicated executable as protocol buffer-encoded data written to its standard input file and returns data to the disclosed system by reading the protocol buffer-encoded data written to the invoked process's standard output file. With such a chaining of runners, any computational artifact, communicating via any means, may be invoked from the disclosed system.

Runnable flow—A runnable flow is a named set of functionality implemented within one or more runnable scopes that is exposed to invocation by external actors by means of a runner. Runnable flows may declare themselves to conform to one or more named ideal flows. For example, a runnable flow may be comprised of a web service that exposes an endpoint that accepts a JSON-formatted payload over the HTTP protocol on a particular TCP port of a runnable scope that is realized as a container. In that example, the runner would be responsible for creating an HTTP request with a JSON-formatted payload comprised of data from a provided data request to the correct TCP port at the IP address of the container and translating the corresponding response into a suitable data representation.

Ideal flow—An ideal flow comprises a globally-unique name and an associated expectation for the structure of the provided data, the structure of the returned data, and the transformation and side effects that result from such an invocation. The globally-unique name may be, by way of example only, a UUID or a reverse fully-qualified domain name. For example, an ideal flow named org.ulvm.artifacts.load might be used as the interface for any custom artifact loaders. Such custom artifact loaders may be expected to receive any map structure representing the configuration of the artifact loader, may be required to return any map structure representing the information needed to address the loaded artifact, and might be expected to preserve the invariant that, after returning, the information returned will address a valid artifact that has been properly staged for launching.

