Feature Idea: Generic data

Generic data

Motivation

Candid cannot currently describe services or functions with a type-generic interface. That is a severe limitation that both we and users keep bumping into. For example, it is not possible to describe the interface of a generic key/value store, where the value could be any form of data (either homogeneously or heterogeneously).

Below I collect some thoughts from previous discussions for possible ways to lift this restriction.

Idea 0: Parameterised type definitions

Summary: Allow type parameters in type definitions.

Examples:

type list(t) = variant { nil; cons : record {t; list(t)} }

type kv_store(t) : {
  put : (key : text, val : t) -> ();
  get : (key : text) -> (val : opt t) query;
  fill : (list : vec record {key : text; val : t}) -> ();
}

Since types are structural, this essentially is a simple macro mechanism that avoids having to repeat the same type many times with different instantiations. It's a prerequisite to make generic functions practical.

However, this requires additional checks to make sure that type recursion is well-founded and not diverging. If not restricted somehow, that is a significant extra burden on decoders (unless this is a text-only convenience, and types are duplicated in the serialised value, but that would be wasteful).

Idea 1: Dynamic data type

Summary: Extend Candid with a new type dyn, which can carry any type of data. It is represented as a nested, self-contained Candid blob, complete with its own type description. (Type-theoretically, dyn = exists X. X)

This probably is the simplest approach. It essentially assigns a special type to blobs that contain nested Candid encodings.

Example:

service gen_kv_store : {
  put : (key : text, val : dyn) -> ();
  get : (key : text) -> (val : opt dyn) query;
  fill : (list : vec record {key : text; val : dyn}) -> ();
}

Pros: very simple
Cons:

• does not convey much intention (e.g., are all vals expected to have homogeneous type?)
• might be inefficient by repeating the same type many times (e.g., if the dyn vals in fill all share the same type, but this type is rather large; they cannot share any type defs with the outer blob either)

Idea 2: Polymorphism encoded as dyn

Summary: Add syntactic sugar on top of dyn for expressing polymorphic functions with universally quantifed parameters. A value of parameter type is represented like dyn, but with the assumption that its internal type matches the instantiation of the type parameter.

Example:

service gen_kv_store : {
  put : (type t) (key : text, val : t) -> ();
  get : (type t) (key : text) -> (val : opt t) query;
  fill : (type t) (list : vec record {key : text; val : t}) -> ();
}

Parameter types can be referred to by other parameters.
They are not represented in the serialised argument tuple.

Pros: still relatively simple; conveys intention
Cons: maintains potential representation inefficiencies as dyn

Idea 3: Polymorphism with separately serialised types

Summary: Introduce a type type that actually is backed by a serialised type. Values of parameter type are represented as serialised Candid blobs, but without repeating the type information -- that is taken from the separately serialised type.

Example (as before):

service kv_store : {
  put : (type t) (key : text, val : t) -> ();
  get : (type t) (key : text) -> (val : opt t) query;
  fill : (type t) (list : vec record {key : text; val : t}) -> ();
}

Parameter types can be referred to by other parameters.
They are represented by a serialised type (without a value) as part of the serialised argument tuple.

Pros: conveys intention; avoids unnecessary type repetition in the wire format
Cons: somewhat more complicated to implement (not simply a nested decoder)

Idea 4: Add existential polymorphism

Both idea 2 and 3 can be combined with 1, making type dyn available for non-parametric use cases or to encode existentially quantified use cases.

Instead (or additionally), existential types could be introduced more explicitly. Two possibilities are:
(a) Also allow 'type results' right of the array: get : (key : text) -> (type t) (val : opt t) query
(b) Allow type fields in records: get : (key : text) -> opt record {type t; val : opt t} query

In the latter case, dyn becomes expressible as

type dyn = record {type t; val : t}

---

Thoughts?

No files, tests, or entry points are named. Start by reviewing the Candid type-system and serialization implementation, then use the five proposed approaches to identify the design that is actually wanted; done means a selected approach with defined type-checking and wire-format behavior.