Module v0

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.
• text
  The HUGR text representation.

Structs

• AliasDecl
  An alias declaration.
• ConstructorDecl
  A term constructor declaration.
• FuncDecl
  A function declaration.
• LinkId
  Index of a link in a hugr graph.
• MetaItem
  A metadata item.
• Module
  A module consisting of a hugr graph together with terms.
• Node
  Nodes in the hugr graph.
• NodeId
  Index of a node in a hugr graph.
• OperationDecl
  An operation declaration.
• Param
  A parameter to a function or alias.
• Region
  A region in the hugr.
• RegionId
  Index of a region in a hugr graph.
• TermId
  Index of a term in a hugr graph.

Enums

• ExtSetPart
  A part of an extension set term.
• GlobalRef
  A reference to a global variable.
• LinkRef
  A reference to a link.
• ListPart
  A part of a list term.
• LocalRef
  A reference to a local variable.
• ModelError
  Errors that can occur when traversing and interpreting the model.
• Operation
  Operations that nodes can perform.
• ParamSort
  The sort of a parameter (implicit or explicit).
• RegionKind
  The kind of a region.
• Term
  A term in the compile time meta language.