Module v0

Expand description

Version 0 (unstable).

Warning: This module is still under development and is expected to change. It is included in the library to allow for early experimentation, and for the core and model to converge incrementally.

§Terms

Terms form a meta language that is used to describe types, parameters and metadata that are known statically. To allow types to be parameterized by values, types and values are treated uniformly as terms, enabling a restricted form of dependent typing. The type system is extensible and can be used to declaratively encode the desired shape of operation parameters and metadata. Type constraints can be used to express more complex validation rules.

§Tabling

Instead of directly nesting structures, we store them in tables and refer to them by their index in the table. This allows us to attach additional data to the structures without changing the data structure itself. This can be used, for example, to keep track of metadata that has been parsed from its generic representation as a term into a more specific in-memory representation.

The tabling is also used for deduplication of terms. In practice, many terms will share the same subterms, and we can save memory and validation time by storing them only once. However we allow non-deduplicated terms for cases in which terms carry additional identity over just their structure. For instance, structurally identical terms could originate from different locations in a text file and therefore should be treated differently when locating type errors.

§Plain Data

All types in the hugr model are plain data. This means that they can be serialized and deserialized without loss of information. This is important for the model to be able to serve as a stable interchange format between different tools and versions of the library.

§Arena Allocation

Since we intend to use the model data structures as an intermediary to convert between different representations (such as text, binary or in-memory), we use arena allocation to efficiently allocate and free the parts of the data structure that isn’t directly stored in the tables. For that purpose, we use the 'a lifetime parameter to indicate the lifetime of the arena.

§Remaining Mismatch with `hugr-core`

This data model was designed to encode as much of hugr-core as possible while also filling in conceptual gaps and providing a forward-compatible foundation for future development. However, there are still some mismatches with hugr-core that are not addressed by conversions in import/export:

Some static types can not yet be represented in hugr-core although they should be.
hugr-model does not have constants for runtime types as hugr-core does (#1425). The rationale for this is that runtime values can not be represented except at runtime (they might e.g. be qubits or part of some extension in which values lack any semantics in forms of sets altogether). We might resolve this by introducing ways to use static values as “blueprints” for runtime values.
The model does not have types with a copy bound as hugr-core does, and instead uses a more general form of type constraints (#1556). Similarly, the model does not have bounded naturals. In both cases, we import these types with the most permissive bound for now.
The model allows nodes to have multiple child regions, including for custom operations. hugr-core does not support multiple regions, or any nesting for custom operations (#1546).
hugr-core has rows with multiple row variables, which can be in arbitrary positions in the row. hugr-core rows correspond to lists in the model, and only support a single variable at the end. The same applies to extension sets (#1556).
In a model module, ports are connected when they share the same link. This differs from the type of port connectivity in the graph data structure used by hugr-core. However, hugr-core restricts connectivity so that in any group of connected ports there is at most one output port (for dataflow) or at most one input port (for control flow). In these cases, there is no mismatch.
hugr-core has no support for constraints and does not make a distinction between explicit and implicit parameters.
hugr-core only allows to define type aliases, but not aliases for other terms.
The model does not have a concept of “order edges”. These ordering hints can be useful, but expressing them via the same mechanism as data and control flow might not be the correct approach.
Both hugr-model and hugr-core support metadata, but they use different encodings. hugr-core encodes metadata as JSON objects, while hugr-model uses terms. Using terms has the advantage that metadata can be validated with the same type checking mechanism as the rest of the model (#1553).
hugr-model have a root region that corresponds to a root Module in hugr-core. hugr-core however can have nodes with different operations as their root (#1554).

Modules§

binary: The HUGR binary representation.
scope: Utilities for working with scoped symbols, variables and links.
text: The HUGR text representation.

Structs§

LinkId: The id of a link consisting of its region and the link index.
LinkIndex: Index of a link in a hugr graph.
Module: A module consisting of a hugr graph together with terms.
Node: Nodes in the hugr graph.
NodeId: Id of a node in a hugr graph.
Param: A parameter to a function or alias.
Region: A region in the hugr.
RegionId: Id of a region in a hugr graph.
RegionScope: Information about the scope defined by a closed region.
Symbol: A symbol.
TermId: Id of a term in a hugr graph.
VarId: The id of a variable consisting of its node and the variable index.

Enums§

ExtSetPart: A part of an extension set term.
ListPart: A part of a list term.
ModelError: Errors that can occur when traversing and interpreting the model.
Operation: Operations that nodes can perform.
RegionKind: The kind of a region.
ScopeClosure: Type to indicate whether scopes are open or closed.
Term: A term in the compile time meta language.
TuplePart: A part of a tuple term.

Constants§

COMPAT_CONST_JSON: Constructor for JSON encoded constants.
COMPAT_META_JSON: Constructor for JSON encoded metadata.
CORE_ADT: Runtime algebraic data types.
CORE_BYTES_TYPE: Type of bytes literals.
CORE_CALL: Operation to call a statically known function.
CORE_CALL_INDIRECT: Operation to call a functiion known at runtime.
CORE_CONST: The type for runtime constants.
CORE_CONSTRAINT: The type of constraints.
CORE_CONST_ADT: Constants for runtime algebraic data types.
CORE_CTRL: Type of a control flow edge.
CORE_CTRL_TYPE: The type of the types for control flow edges.
CORE_EXT_SET: The type of extension sets.
CORE_FLOAT_TYPE: Type of float literals.
CORE_FN: Core function types.
CORE_LIST_TYPE: The type for lists of static data.
CORE_LOAD_CONST: Operation to load a constant value.
CORE_MAKE_ADT: Operation to create a value of an algebraic data type.
CORE_META: The type of metadata.
CORE_META_DESCRIPTION: Constructor for documentation metadata.
CORE_NAT_TYPE: Type of natural number literals.
CORE_NON_LINEAR: The constraint for non-linear runtime data.
CORE_STATIC: The type of static types.
CORE_STR_TYPE: Type of string literals.
CORE_TUPLE_TYPE: The type for tuples of static data.
CORE_TYPE: The type of runtime types.

Type Aliases§

VarIndex: An index of a variable within a node’s parameter list.

Module v0Copy item path