5.1 Our extraction

The standard Coq extraction targets conventional general-purpose functional programming languages. Recently, there has been a significant increase in the number of languages that are inspired by these, but due to the narrower application focus are different in various subtle details. We have considered the area of smart contract languages (Liquidity and CameLIGO), web programming (Elm) and general-purpose languages with a functional subset (Rust). They often pose more challenges than the conventional targets for extraction. We have identified the following issues.

1. 1. Most of the smart contract languages ^{Footnote 6} and Elm do not offer a possibility to insert type coercions forcing the type checking to succeed.

2. 2. The operational semantics of ${\lambda_\square}{}$ has the following rule (Sozeau et al. Reference Sozeau, Boulier, Forster, Tabareau and Winterhalter2019, Section 4.1): if ${{\Sigma} \vdash {t_1} \triangleright {\square}}$ and ${{\Sigma} \vdash {t_2} \triangleright {\mathit{v}}}$ then ${{\Sigma} \vdash {\bigl(t_1~~t_2 \bigr)} \triangleright {\square}}$ , where ${{-} \vdash {-} \triangleright {-}}$ is a big-step evaluation relation for ${\lambda_\square}{}$ , $t_1$ and $t_2$ are ${\lambda_\square}{}$ terms, and $\mathit{v}$ is a ${\lambda_\square}{}$ value. This rule can be implemented in OCaml using the unsafe features, which are, again, not available in most of our target languages. In lazy languages, this situation never occurs (Letouzey Reference Letouzey2004, Section 2.6.3), but most of the languages we consider follow the eager evaluation strategy.

3. 3. Data types and recursive functions are often restricted. E.g. Liquidity, CameLIGO (and other LIGO languages) do not allow for defining recursive data types (like lists and trees) and limits recursive definitions to tail recursion on a single argument. Instead, these languages offer built-in lists and finite maps (dictionaries).

4. 4. Rust has a fully-featured functional subset, but being a language for systems programming, does not have a built-in garbage collector.

We can make design choices, concerning the point above, in such a way that the soundness of the extraction will not be affected, given that terms evaluate in the same way before and after extraction. In the worst case, the extracted term will be rejected by the type checker of the target language. However, some care is needed: the pretty-printing step still presents a gap in verification. A more careful treatment of the semantics of target languages would allow extending the guarantees. Some subtleties come from, e.g. handling of absurd pattern-matching cases and its interaction with optimisations. As for now, we apply the approach inspired by the standard extraction in such situations.

Let us consider in detail what the restrictions outlined above mean for extraction. The first restriction means that certain types will not be extractable. Therefore, our goal is to identify a practical subset of extractable Coq types and give the user access to transformations helping to produce well-typed programs. The second restriction is hard to overcome, but fortunately, this situation should not often occur on the fragment we want to work. Moreover, as we noticed before, terms that might give an application of a box to some other term will be ill-typed and thus, rejected by the type checker of the target language. The third restriction can be addressed by mapping Coq’s data types (lists, finite maps) to the corresponding primitives in a target language. The fourth restriction applies only to Rust and means that we have to provide a possibility to “plug-in” a memory management implementation. Luckily, Rust libraries contain various implementations one can choose from.

At the moment, we consider the formalisation of typing in target languages out of scope for this project. Even though the extraction of types is not verified, it does not compromise run-time safety: if extracted types are incorrect, the target language’s type checker will reject the extracted program. If we followed the work by Letouzey (Reference Letouzey2004), which the current Coq extraction is based on, giving guarantees about typing would require formalising of target languages type systems, including a type inference algorithm (possibly algorithm $\mathcal{M}$ ). The type systems of many languages we consider are not precisely specified and are largely in flux. Moreover, for the target languages without unsafe coercions, some of the programs will be untypable in any case. On the other hand, for more mature languages (e.g. Elm) one can imagine connecting our formalisation of extraction with a language formalisation, proving the correctness statement for both the run-time behaviour and the typability of extracted terms.

We extend the work on verified erasure (Sozeau et al. Reference Sozeau, Boulier, Forster, Tabareau and Winterhalter2019) and develop an approach that uses a minimal amount of unverified code that can affect the soundness of the verified erasure. Our approach adds an erasure procedure for types, verified optimisations of the extracted code and pretty-printers for several target languages. The main observation is that the intermediate representation ${\lambda^T_\square}$ corresponds to the core of a generic functional language. Therefore, our pipeline can be used to target various functional languages with transformations and optimisations applied generically to the intermediate representation.

Before introducing our approach, let us give some examples of how the verified erasure works and motivate the optimisations we propose.

produces the following ${\lambda_\square}{}$ code:

where the $\square$ symbol corresponds to computationally irrelevant parts. The first two arguments to the erased versions of fold_right are boxes, since fold_right in Coq has two implicit type arguments. They become visible if we switch on printing of implicit arguments:

In this situation we have at least two choices: remove the boxes by some optimisation procedure, or leave the boxes and extract fold_right in such a way that the first two arguments belong to some dummy data type. ^{Footnote 7} The latter choice cannot be made for some smart contract languages due to restrictions on recursion (fold_right is not tail-recursive), therefore, we have to remap fold_right and other functions on lists to the corresponding primitive functions. Generally, removing such dummy arguments in the extracted code is beneficial for other reasons: the code size is smaller and some redundant reductions can be avoided.

In the following example,

the square function erases to

The corresponding language primitive would be a function with the following signature: TargetLang.map: (’a → ’b) → ’a list → ’b list. Clearly, there are two extra boxes in the extracted code that prevent us from directly replacing Coq.Lists.List.map with TargetLang.map. Instead, we would like to have the following:

In this case, we can provide a translation table to the pretty-printing procedure mapping Coq.Lists.List.map to TargetLang.map. Alternatively, if one does not want to remove boxes, it is possible to implement a more sophisticated remapping procedure. It could replace Coq.Lists.List.map _ with TargetLang.map, but it would require finding all constants applied to the right number of arguments (or $\eta$ -expand constants) and only then replace them. Remapping inductive types in the same style would involve more complications: constructors of polymorphic inductive types will have an extra argument of a dummy type. This would require more complicated pretty-printing of pattern-matching in addition to the similar problem with extra arguments on the application sites.

By implementing the optimisation procedure we achieve several goals: make the code size smaller, remove redundant computations, and make the remapping easier. Removing the redundant computations is beneficial for smart contract languages since it decreases the computation cost in terms of gas. Users typically pay for calling smart contracts and the price is determined by the gas consumption. That is, gas serves as a measure of computational resources required for executing a contract. Smaller code size is also an advantage from the point of view of gas consumption. For some blockchains, the overall cost of a contract call depends on its size.

It is important to separate these two aspects of extraction: erasure (given by the translation CIC ^{Footnote 8} → ${\lambda_\square}{}$ ) and optimisation of ${\lambda_\square}{}$ terms to remove unnecessary arguments. The optimisations we propose remove some redundant reductions, make the output more readable and facilitate the remapping to the target language’s primitives. Our implementation strategy of extraction is the following: (i) take a term and erase it and its dependencies recursively to get an environment; (ii) analyse the environment to find optimisable types and terms; (iii) optimise the environment in a consistent way (e.g. in our ${\lambda^T_\square}$ , the types must be adjusted accordingly); (iv) pretty-print the result in the target language syntax according to the translation table containing remapped constants and inductive types.

The mechanism of remapping constants and inductive types is similar to the Coq functionality Extract Inlined Constant and . Since we run the extraction pipeline inside Coq, the we use ordinary Coq definitions to build a translation table that we pass to the pipeline. For example, the typical translation table would look as the following.

We use remap ≤ %% coq_def %%≥ “target_def" to produce an entry in the translation table, where the ≤ %% coq_def %%≥ notation uses MetaCoq to resolve the full name of the given definition. Note that the translation table is an association list with kername as keys. The kername type is provided by MetaCoq and represents fully qualified names of Coq definitions.

5.1.1 Erasure for types

Let us discuss our first extension to the verified erasure presented in Sozeau et al. (Reference Sozeau, Boulier, Forster, Tabareau and Winterhalter2019), namely an erasure procedure for types. It is a crucial part for extracting to a typed target language. Currently, the verified erasure of MetaCoq provides only a term erasure procedure which will erase any type in a term to a box. For example, a function using the dependent pair type ( $\Sigma$ -type) might have a signature involving , i.e. representing numbers that are larger than 10. Applying MetaCoq’s term erasure will erase this in its entirety to a box, while we are interested in a procedure that instead erases only the type scheme in the second argument: we expect type erasure to produce , where the square now represents an irrelevant type.

While our target languages have type systems that are Hindley-Milner based (and therefore, can recover types of functions), we still need an erasure procedure for types to be able to extract inductive types. Moreover, our target languages support various extensions, and their compilers may not always succeed to infer types. For example, Liquidity has overloading of some primitive operations, e.g. arithmetic operations for primitive numeric types. Such overloading introduces ambiguities that cannot be resolved by the type checker without type annotations. CameLIGO requires writing even more types explicitly. Thus, the erasure procedure for types is also necessary to produce such type annotations. The implementation of this procedure is inspired by Letouzey (Reference Letouzey2004).

We have chosen a semi-formal presentation in order to guide the reader through the actual implementation while avoiding clutter from the technicalities of Coq. We use concrete Coq syntax to represent the types of CIC. We do not provide syntax and semantics of CIC, for more information we refer the reader to Sozeau et al. (Reference Sozeau, Boulier, Forster, Tabareau and Winterhalter2019), Section 2. The types of ${\lambda^T_\square}$ are represented by the grammar below.

Here ${\overline{i}}$ represents levels of type variables, and range over names of inductive types and constants respectively. Essentially, represents types of an OCaml-like functional language extended with constructors ${\square}$ (“logical” types) and $\mathbb{T}$ (types that are not representable in the target language). In some cases both ${\square}$ and $\mathbb{T}$ can later be removed from the extracted code by optimisations, although $\mathbb{T}$ might require type coercions in the target language. Note also that the types do not have binders, since they represent prenex-polymorphic types. The levels of type variables are indices into the list of type variable names starting from the head of the list. E.g. the type ’a → ’b is represented as for the context $[a;b]$ . Additionally, we use colours to distinguish between the CIC terms and the target .

Definition 1 (Erasure for types).

The erasure procedure for types is given by functions ${\mathcal{E}^T}{}$ , $\mathcal{E}_{app}^T{}$ and ${\mathcal{E}_{head}^T}{}$ in Figure 2.

Fig. 2. Erasure from CIC types to ${\mathtt{box\_type}}$ .

The ${\mathcal{E}^T}{}$ function takes four parameters. The first is a context $\mathtt{Ctx}$ represented as a list of assumptions. The second is an erasure context $\mathtt{ECtx}$ represented as a sized list (vector) that follows the structure of $\mathtt{Ctx}$ ; it contains either a translated type variable $\mathtt{TV}$ , information about an inductive type $\mathtt{Ind}$ , or a marker $\mathtt{Other}$ for items in $\mathtt{Ctx}$ that do not fit into the previous categories. The last two parameters represent terms of CIC corresponding to types and an index of the next type variable. The next type variable index is wrapped in the $\mathtt{option}$ type, and becomes $\mathtt{None}$ if no more type variables should be produced. The function ${\mathcal{E}^T}{}$ returns a tuple consisting of a list of type variables and a .

First, we describe the most important auxiliary functions outlined on the Figure 2. An important device used to determine erasable types (the ones we turn into the special target types ${\square}$ and $\mathbb{T}$ ) is the function , where the return type $\mathtt{type\_flag}$ is defined as a record with two fields: $\mathtt{is\_logical}$ and $\mathtt{is\_arity}$ . The $\mathtt{is\_logical}$ field carries a boolean, while $\mathtt{is\_arity}$ carries a proof or a disproof of convertibility to an arity. That is, whether a term is an arity up to reductions. For the purposes of the presentation in the paper, we treat $\mathtt{is\_arity}$ as a boolean value, while in the implementation we use the proofs carried by $\mathtt{is\_arity}$ to solve proof obligations for the definition of ${\mathcal{E}^T}{}$ .

A type is an arity if it is a (possibly nullary) product into a sort: for and a vector of (possibly dependent) binders and types. Inhabitants of arities are type schemes.

The predicate $\mathtt{is\_sort}$ is not a field of $\mathtt{type\_flag}$ , but it uses the data of $\mathtt{is\_arity}$ field to tell whether a given type is a sort, i.e. . Sorts are always arities; we use $\mathtt{is\_sort}$ to turn a proof of converitibility to an arity into a proof of convertivility to a sort (or return $\mathtt{None}$ if it is not the case). Finally, a type is logical when it is a proposition (i.e. inhabitants are proofs) or when it is an arity into (i.e. inhabitants are propositional type schemes). As concrete examples, ${\mathtt{Type}}$ is an arity and a sort, but not logical. is logical, an arity, but not a sort. is neither of the three.

We use the reduction function ${\mathtt{red}_{\beta\iota\zeta}}$ in order to reduce the term to $\beta\iota\zeta$ weak head normal form. Here, $\beta$ is reduction of applied $\lambda$ -abstractions, $\iota$ is reduction of $\mathtt{match}$ on constructors, and $\zeta$ is reduction of the $\mathtt{let}$ construct. The $\mathtt{infer}{}$ function is used to recover typing information for subterms. We also make use of the destructuring $\mathtt{let}~(a,b) := \ldots$ for tuples and projections $\mathtt{fst}$ , $\mathtt{snd}$ .

The erasure procedure proceeds as follows. First, it reduces the CIC term to $\beta\iota\zeta$ weak head normal form. Then, it uses ${\mathtt{flag\_of\_type}}{}$ to determine how to erase the reduced type. If it is a logical type, it immediately returns ${\Box}$ , if not, it performs case analysis on the result. The most interesting cases are dependent function types and applications. For function types, if the domain type is logical, it produces ${{\square}}$ for the resulting domain type and erases the codomain recursively. If the domain is a “normal” type (not logical and not an arity), it erases recursively both the domain and the codomain. Otherwise, the type is an arity and we add a new type variable into $\Gamma_e$ for the recursive call and append a variable name to the returned list. For an application, the procedure decomposes it into a head term and a (possibly empty) list of arguments using ${\mathtt{decompose\_app}}{}$ . Then, it uses ${\mathcal{E}_{head}^T}{}$ to erase the head and $\mathcal{E}_{app}^T{}$ to process all the arguments. Note that in the Coq implementation, when we erase an application , we drop the arguments, if the head of the application is not an inductive or a constant. Other applied construtors would correspond to a not well-formed application. In the cases not covered by the case analysis, we emit $\mathbb{T}$ .

For example, the type of erases to the following.

One of the advantages of implementing the extraction pipeline fully in Coq is that we can use certified programming techniques along with the verified meta-theory provided by MetaCoq. The actual type signatures of the functions in Figure 2 restrict the input to well-typed CIC terms. In the implementation, we are required to show that the reduction machinery we use does not break the well-typedness of terms. For that purpose, we use two results: the reduction function is sound with respect to the relational specification, and the subject reduction lemma, that is, reduction preserves typing.

The termination argument is given by a well-founded relation since erasure starts with $\beta\iota\zeta$ -reduction using the ${\mathtt{red}_{\beta\iota\zeta}}$ function and then later recurses on subterms of the reduced term. This reduction function is defined in MetaCoq also by using well-founded recursion. Due to the use of well-founded recursion, we write ${\mathcal{E}^T}{}$ as a single function in our formalisation by inlining the definitions of $\mathcal{E}_{app}^T{}$ and ${\mathcal{E}_{head}^T}{}$ ; this makes the well-foundedness argument easier. We extensively use the Equations Coq plugin (Sozeau & Mangin Reference Sozeau and Mangin2019) in our development to help manage the proof obligations related to well-typed terms and recursion.

The difference with our previous erasure procedure for types given in Annenkov et al. (Reference Annenkov, Milo, Nielsen and Spitters2021) is twofold. First, we make the procedure total. That means that it does not fail in the cases when it hits a non-prenex type, instead, it tries to do its best or emits $\mathbb{T}$ if no further options are possible. That is, for rank2 from Section 5 we get the following type.

Clearly, the body of rank2 a f = f $\Box$ a cannot be well-typed, since the type of a is not $\mathbb{T}$ . However, in some situations, it is better to let the extraction produce some result that could be optimised later. For example, if we never used the f argument, it could be removed by optimisations leaving us with the definition whose that does not mention $\mathbb{T}$ .

In particular, we have improved the handling of arities that makes it possible to extract programs defined in terms of elimination principles. For example one can define map in the following way: . Where list_rect is the dependent elimination principle for lists.

Clearly, the type of list_rect is too expressive for the target languages we consider. However, it is still possible to extract a well-typed term for the definition of map above. The extracted type of list_rect looks as follows.

Second, we have introduced an erasure procedure for type schemes. The procedure allows us to handle type aliases, that is, Coq definitions that when applied to some arguments return a type. Type aliases are used quite extensively in the standard library. For example, the standard finite maps FMaps contain definitions like . In $\eta$ -expanded form it is a function that take a type and returns a type: . Without this extension, we would not be able to extract programmes that use such definitions.

Definition 2 (Erasure for type schemes).

The erasure procedure for type schemes is given by two functions ${\mathcal{E}^{TS}}{}$ and ${\mathcal{E}_\eta^{TS}}{}$ in Figure 3.

Fig. 3. Erasure for type schemes.

The signatures of ${\mathcal{E}^{TS}}{}$ and ${\mathcal{E}_\eta^{TS}}{}$ are similar to ${\mathcal{E}^T}{}$ but we also add a new context $\mathtt{ACtx}$ representing the type of a type scheme, which we call arity. So, for an arity $\forall (a : A) (b : B) \ldots (z : Z), \mathtt{Type}$ , we have $\Gamma_a = [(a,A); (b,B);\ldots;(z,Z)]$ . The ${\mathcal{E}^{TS}}{}$ function reduces the term and then, if it is a lambda-abstraction, looks at the result of ${\mathtt{flag\_of\_type}}$ for the domain type. If it is a sort (or, more generally, an arity) it adds a type variable. If the reduced term is not a lambda abstraction, we know that it requires $\eta$ -expansion, since its type is $\forall (a' : A'), t$ . Therefore, we call ${\mathcal{E}_\eta^{TS}}{}$ with the arity context $(a',A') :: \Gamma_a$ . In ${\mathcal{E}_\eta^{TS}}{}$ , we use the operation that increments the indices of all variables in t by one. The term denotes an application of a term $\mathit{{t}}$ with incremented variable indices to a variable with index ${\overline{0}}$ A simple example of a type scheme is the following:

It erases to a pair consisting of a list of type variables and a :

Type schemes that use dependent types can also be erased. For example, one can create an abbreviation for the type of sized lists.

which gives us the following type alias

where sig corresponds to the dependent pair type in Coq given by the notation . The erased type can be further optimised by removing the occurrences of ${\square}$ and irrelevant type variables.

The two changes described above bring our implementation closer to the standard extraction of Coq and allow for more programs to be extracted in comparison with our previous work. Returning $\mathbb{T}$ instead of failing creates more opportunities for target languages that support unsafe type casts.

Having defined the erasure procedure for types, we implement an erasure procedure for inductive definitions. Bringing it all together with the verified erasure of MetaCoq and the erasure for type schemes, we can define a procedure that erases lists of global declarations, which are called global environments. We enrich the representation of global environments of the MetaCoq’s erasure with the typing information we obtained using ${\mathcal{E}^T}{}$ and ${\mathcal{E}^{TS}}{}$ . Each entry in the global environment is represented by the following inductive type.

where constant_body adds the constant’s erased type (the cst_type field), which is absent in the corresponding definition of MetaCoq’s ${\lambda_\square}$ :

Moreover, mutual_inductive_body is enriched with typing information as well. We explicitly treat type aliases by having a separate entry TypeAliasDecl, which corresponds to type schemes. We call the representation above ${\lambda^T_\square}$ and use it as an intermediate representation.

5.1.2 Optimising extracted code

Our second extension of the verified erasure is deboxing—a simple optimisation procedure for removing some redundant constructs (boxes) left after the erasure step. First, we observe that removing redundant boxes is a special case of more general optimisation: dead argument elimination. Informally it boils down to the equivalence $(\lambda x.~t)~v \sim t$ when x does not occur free in t. Here $\sim$ means that both sides evaluate to the same value. Then, deboxing becomes a special case: $(\lambda A.~t)~\square \sim t$ . Where the A variable corresponds, for example, to the type abstraction $\lambda (A : \mathtt{Type}).~t$ . Erasure replaces the occurrences of A in t with boxes. ^{Footnote 9} Having in mind this equivalence, we implement in Coq a function with the following signature:

\begin{align*} \mathit{dearg}~:&~ \mathtt{ind\_masks} \rightarrow \mathtt{cst\_masks} \rightarrow \mathtt{term} \rightarrow \mathtt{term}\end{align*}

The first two parameters are lookup tables for inductive definitions and for constants defining which arguments of constructors and constants are unused. The information about unused arguments is represented using masks—lists of boolean values with true denoting the unused arguments. The type $\mathtt{term}$ represents ${\lambda_\square}{}$ terms. The $\mathit{dearg}$ function traverses the term and adjusts all applications of constants and constructors using the masks.

We define the following function that processes the definitions of constants:

\begin{align*} \mathit{dearg\_cst} ~:&~ \mathtt{ind\_masks} \rightarrow \mathtt{cst\_masks} \rightarrow \mathtt{constant\_body} \rightarrow \mathtt{constant\_body}\end{align*}

This function deargs the body using $\mathit{dearg}$ and additionally removes lambda abstractions in correspondence to the mask for the current constant. Note that, since the masks apply only to constants in the programme, we only remove dead arguments of top-level functions: abstractions representing closures are untouched. Additionally, as dearging removes arguments from the top-level function, we must adjust the type signatures produced by the type erasure correspondingly. For example, for the constant we get a mask mask = [ false; true; true] and the optimised constant

To generate the masks we implement an analysis procedure that finds dead parameters of constants and dead constructor arguments. For arguments of constants, we check syntactically if they do not appear in the body, while for constructor arguments we find all unused arguments in pattern matches and projections across the whole programme. This is implemented as a linear pass over each function body that marks all uses of arguments and constructor arguments in that function. As we noted above, the erased arguments will be unused and therefore this procedure gives us a safe way of removing many redundant boxes, cf. Letouzey (Reference Letouzey2004), Section 4.3.

The syntactic check is quite imprecise; for example, it will not remove a parameter if its only use is to be passed to another function in which it is also unused. To deal with this, the analysis and dearging procedure can be iterated multiple times, but since our main use of the dearging is to remove arguments that are erased, this is not necessary.

For definitions of inductive types, we define the function

\begin{align*} \mathit{dearg\_mib} ~ :~& \mathtt{mib\_masks} \rightarrow \mathbb{N} \rightarrow \mathtt{one\_inductive\_body} \rightarrow \mathtt{one\_inductive\_body}\end{align*}

which adjusts the definition of one inductive’s body of a (possibly) mutual inductive definition. With $\mathit{dearg\_cst}$ and $\mathit{dearg\_mib}$ , we can now define a function that removes arguments according to given masks for all definitions in the global environment:

\begin{align*} \mathit{dearg\_env}~:&~ \mathtt{ind\_masks} \rightarrow \mathtt{cst\_masks} \rightarrow \mathtt{global\_env} \rightarrow \mathtt{global\_env}\end{align*}

Dearging is then done by first analysing the environment to obtain $\mathtt{ind\_masks}$ and $\mathtt{cst\_masks}$ and then applying the $\mathit{dearg\_env}$ function.

We prove dearging correct under several assumptions on the masks and the program being erased. First, we assume that all definitions in the program are closed, which is a reasonable assumption given by typing. Secondly, we assume that the masks are valid, meaning that all removed arguments of constants and constructors should be unused in the program. By unused we mean that the argument does not syntactically appear except for in the binder. The analysis phase outlined above is responsible for generating masks that satisfy this condition, although currently, we do not prove this and instead recheck that the condition holds for the masks that were output. Finally, we assume that the programme is $\eta$ -expanded according to all the masks: all occurrences of constructors and constants should be applied to the arguments that are supposed to be removed. We implement a certifying procedure that performs $\eta$ -expansion and generates proofs that the expanded terms are equal to the original ones (see Section 5.2). The erasure procedure is a pruning transformation, meaning that it does not remove abstractions or arguments in applications, it just replaces some terms with ${\Box}$ . Therefore, $\eta$ -expanded terms are preserved by erasure. We, however, have not formalised this result and currently validate the terms after erasure to ensure that they are applied enough.

Our Coq formalisation features a proof of the following soundness theorem about the $\mathit{dearg}$ function. [

Theorem 1 (Soundness of dearging)

Let ${\Sigma}$ be a closed erased environment and t a closed ${\lambda_\square}{}$ -term such that ${\Sigma}$ and t are valid and expanded according to provided masks.

Then

implies

where dearging is done using the provided masks.

Here ${{-} \vdash {-} \triangleright {-}}$ denotes the big-step call-by-value evaluation relation of ${\lambda_\square}{}$ terms ^{Footnote 10} and values are given as a subset of terms. The theorem ensures that the dynamic behaviour is preserved by the optimisation function. This result, combined with the fact that the erasure from CIC to ${\lambda_\square}{}$ preserves dynamic behaviour as well, gives us guarantees that the terms that evaluate in CIC will be evaluated to related results in ${\lambda_\square}{}$ after optimisations.

Theorem 1 is a statement talking only about the dearging optimisation that is used by our extraction. The extraction pipeline itself is more complicated and works as outlined at the end of Section 5.1: it is provided a list of definitions to extract in a well-typed environment and recursively erases these and their dependencies (see the full pipeline in Figure 1). Note that only dependencies that appear in the erased definitions are considered as dependencies; this typically gives an environment that is substantially smaller than the original. Once the procedure has produced an environment, the environment is analysed to find out which arguments can be removed from constructors and constants, and finally, the dearging procedure is invoked.

MetaCoq’s correctness proof of erasure requires the full environment to be erased. Since we only erase dependencies, we prove a strengthened version of the erasure correctness theorem that is applicable for our case. Combining this with Theorem 1 allows us to obtain a statement about the extraction pipeline (starting from the PCUIC representation and excluding the pretty-printing).

Theorem 2 (Soundness of extraction)

Let ${\Sigma}$ be a well-typed axiom-free environment and let C be a constant in ${\Sigma}$ . Let be the environment produced by successful extraction (including optimisations) of C from ${\Sigma}$ . Then, for any unerasable constructor , if

it holds that

Here ${{-} \vdash_p {-} \triangleright {-}}$ denotes the big-step call-by-value evaluation relation for CIC terms. Informally, the above statement can be specialised to say that any program computing a boolean value will compute the same value after extraction. Of course, one still has to keep in mind that the pretty-printing step of the extracted environment is not verified, and there are discrepancies of ${\lambda_\square}{}$ and the target language’s semantics as we outlined in Section 5.1. We also discuss in Section 5.1.4 how the handling of absurd cases (e.g. False_rect) interacts with the dearging transformation. With the translation from the Template Coq representation to PCUIC (ongoing work in the MetaCoq team), we would have a complete end-to-end theorem covering all steps that happen after quoting a Gallina term and before printing the resulting code. The quote functionality would still remain the the TCB.

While the statement does not say anything about constructor applications, ^{Footnote 11} it does informally generalise to any value that can be encoded as a number, since it can be used to show that each bit of the output will be the same.

One of the premises of Theorem 2 is that the environment is axiom-free, which is required for the soundness of erasure as stated in MetaCoq and adapted in our work. In general, we cannot say anything about the evaluation of terms once axioms are involved. One possible way of fixing this issue is by following the semantic approach as in Letouzey (Reference Letouzey2004), Section 2.4.

While dearging subsumes deboxing we cannot guarantee that our optimisation removes all boxes even for constants applied to all logical arguments due to cumulativity. ^{Footnote 12} E.g. for it is tempting to optimise the extracted version into just inl, but the optimised definition of the sum type will still have the inl constructor that takes one argument, because its type is and the argument A is, in general, relevant for computation.

As mentioned previously, the dearging of functions removes parameters which means that it must also adjust the type signatures of those functions. In addition to this adjustment of type signatures, we also do a final pass to remove logical inductive type parameters. We define functions that perform deboxing of types and, eventually on the contents of the global environment.

Note that the deboxing of types does not affect the structure of arrow types, since these are connected to dearging. Instead, it recursively finds inductive types $\mathtt{I}$ and type constants C applied to boxes ${{\square}}$ and filters out the boxes. This step is completely orthogonal to the dearging of terms and serves only to remove useless type parameters. This does not affect the dynamic semantics, but mistakes in it might mean that the code does not type-check in the target language.

For a concrete example, sigma types are defined in Coq as

In the constructor, P is a type scheme while the argument of type P x is a proof, so these are erased by type erasure, resulting in the type . The analysis will show that the proof argument is never used since any use is also erased. This means the constructor is changed to as part of the dearging process, and any use of this constructor in a function (e.g. for pattern matching, or to construct a value) is similarly adjusted. Finally, removal of logical type parameters (deboxing of types) means that the type parameter P is completely removed from the type, giving the final constructor type as . Function signatures using sig are also adjusted correspondingly, having the P argument removed.

After applying the optimisations, we pretty-print the optimised code to several functional languages. We discuss issues related to extraction to Liquidity and CameLIGO in Section 5.3, to Elm in Section 5.4, and to Rust in Section 5.5.

5.1.4 Handling absurd cases

Our approach should be able to handle the cases when Coq programmes contain some unreachable code, originating from provably impossible cases. As an example let us consider the following program in Coq.

The type of the programme ensures that one always can take the first element of the input list. In the body of the programme, we have to deal with two cases for the given list. Clearly, we should never hit the empty list case. Therefore, we use that allows us to construct anything, provided we have a contradiction at hand. Using the tactic we construct such proof from the fact that length [] ≥ 0 is in fact a contradiction. In Coq, this definition gives us a total function safe_head, which we then can use in other definitions, provided that we can construct an element of {l : list A | length l ≥ 0}. For example, we can use it in the following program.

However, in the extracted code, safe_head must return some value of the appropriate type in the case of an empty list. It can be done in different ways, depending on the features available in a target language. One way of doing this would be to throw an exception in languages that support this kind of side effect. E.g. the standard Coq extraction to OCaml uses assert false for that purpose. For the languages that do not support exceptions, we can use non-termination for the same purpose. Therefore, once we encounter pattern-matchings on any empty inductive type (an inductive type with no constructors, e.g. False) we replace it with a construct that throws an exception or a call to a non-terminating function.

There is an issue, however, with this naive approach. It is related to subtle interactions of constants that eliminate from an empty type, like False_rect, with our dearging optimisation in eager languages. In our initial version, we produced masks for constants like False_rect that instructed the optimisation procedure to remove all arguments. Even though it is sound at the ${\lambda^T_\square}$ level by Theorem 1, at the pretty-printing stage, the body of False_rect will be replaced with something like assert false, which will be immediately evaluated in eager languages, leading to exceptions. That is, the soundness guarantees of Theorem 1 could be broken by the actual generated code. In our current implementation, we have adopted the following strategy, following Letouzey (Reference Letouzey2004), At the analysis stage, if all the arguments of a constant are logical (i.e. of type ${\square}$ or $\mathbb{T}$ ) we generate a mask that keeps one argument, guarding the constant’s body by a lambda abstraction. That is, we never remove all the arguments of constants that have purely logical arguments. This also applies to Acc_rect and related machinery for defining functions by well-founded recursion, where removing all arguments may lead to non-termination.

The separation of analysis and optimisation gives us a flexible way of implementing the standard fixes for such issues. However, these situations highlight the fact that the final extraction guarantees can be given only after careful consideration of the semantics of target languages. Formally, it can be fixed by connecting our development to formalisations of target languages, as we sketched in Section 2. We remark on how the pattern-matching on empty types is implemented in our targets in the corresponding sections.

5.1.5 The counter contract

As an example, let us consider a simple smart contract represented as a Gallina function. The state of the contract is an integer number and it accepts increment and decrement messages (Figure 4, ). The main functionality is given by the two functions inc_counter and dec_counter. We use subset types to encode the functional specification of these functions. E.g. for inc_counter we encode in the type that the result of the increment is greater than the previous state given a positive increment. Subset types are represented in Coq as dependent pairs ( $\Sigma$ -types). For example a positive integer is encoded as {z : Z | 0 ≤ ? z}, where the second component is a proposition 0 ≤ ? i = true (we use an implicit coercion from booleans to propositions). Similarly, we encode the specification dec_counter. The counter function validates the input and provides a proof that the input satisfies the precondition (of being positive). The functions inc_counter and dec_counter are defined only for positive increments and decrements, therefore, we do not need to validate the input again. Note that in order to construct an inhabitant of positive, we use the decidability of equality for booleans that gives us access to the proof of 0 ≤ ? i. We will use the example from Figure 4 in subsequent sections for showing how it can be extracted to concrete target languages.

Fig. 4. The counter contract.

5.2 Proof-generating transformations

The optimisation pass in our pipeline (see Figure 1) expects constants and constructors to be applied to all logical arguments in order to be valid. Moreover, some constants have types that are too expressive for the target languages that can make the extracted programs untypable. However, the constants can be specialised in a way that the extracted code is well-typed. In order to ensure that our input satisfies these and some other technical requirements, we apply transformation passes at the very beginning of our pipeline—at the Template Coq level (see Figure 1). These transformation passes are implemented as unverified functions transforming the Template Coq AST. In order to ensure that the passes are computationally sound, we apply the certifying approach to transformation. It is similar to how certifying compilers are used to produce proof-carrying code (Necula Reference Necula1997). The overall idea is that the transformation produces a new programme (in our case it is the same language) and a proof term that the desired property is preserved by the transformation. Each transformation in the Template Coq part of the pipeline has the following type

transform: global_env → Result global_env string

where global_env is the Template Coq global environment (list of top level declarations), Result is a error monad. Given a list of transforms, we can compose them using the fact that $\mathtt{Result}$ is a monad. In fact, we can reuse the same way of composing transformation for different passes in our pipeline and define a common type of transformations as As a result, we define the composition of transformation in the usual monadic way.

After successfully completing all the transformations, we can generate proofs that the definitions we transformed behave in the same way as the originals. All the transformations we have considered have one property in common: they produce terms that are definitionally equal to the originals. Definitional equality in Coq means that the two terms are convertible, i.e. equivalent with respect to $\beta\delta\iota\zeta$ -reduction, $\eta$ -expansion and irrelevant terms in SProp. ^{Footnote 13} Where $\beta$ and $\eta$ are standard and $\delta$ means constant unfolding, $\iota$ —reduction of on a constructor, reduction. From the computational point of view, convertible terms represent the same program. The fact that the terms are convertible gives us a simple way of generating the correctness proofs. Let trans be a transformation function and t0 : A a term. If trans t0 = Ok t1, i.e. the application of this function to t0 succeeds with some transformed term t1, we can construct the following proof term:

@eq_refl A t1 : t0 = t1

This proof term shows that we can prove that the two terms t0 and t1 are equal in the theory of Coq. Moreover, this term is well-typed only if t0 and t1 are convertible.

We use the following approach to generating the proof terms:

• Given a definition def, quote it along with all the dependencies, producing a global environment $\Sigma_0$ with quoted terms.

• Apply the composed transformations to all elements in the original global environment $\Sigma_0$ and get the transformed environment $\Sigma_1$ .

• For each constant from $\Sigma_0$ find a corresponding constant in $\Sigma_1$ .

• If a constant is found, compare the constant bodies for syntactic equality (it is possible since we operate in meta-theory). In case the bodies are not equal—add (unquote) a new definition from $\Sigma_1$ to the current scope; if they are equal, or constant not found—do nothing.

• If def or its dependencies were affected by the transformation, generate a proof term and add (unquote) it to the current scope.

The certifying approach is quite flexible wrt. changes and additions of new passes since no modifications of proofs are required, provided that the passes preserve convertibility. This is a big advantage in our setting when fine-tuning of the transformations is required for achieving the desired result (see, for example, the inlining transformation below). Potentially, the pass can be extended with more general optimising transformations like partial evaluation.

Below, we describe transformations currently implemented in our framework.

${\boldsymbol\eta}$ -expansion The idea is to find partially applied constants (or constructors) and expand them by introducing lambda-abstractions. For example for a term would be expanded (if we demand full $\eta$ -expansion) to . The extent to which the expansion is performed is controlled by lookup tables mapping the names of constants (or constructor information) to a number, indicating the number of arguments that should be added, and the constant’s (constructor’s) type. The typing information is required for introducing the lambda-abstractions since the Template Coq unquote functionality expects a fully specified term, and all binders typically have explicit types in the AST. Calling the type checker would introduce too much overhead, therefore, we keep the required information in the lookup tables. The transformation is mostly standard but requires a bit of care when dealing with types of lambda-abstractions. Let us consider an example, writing all relevant types explicitly. For the following code . Our expansion table will contain the type of . In order to introduce a lambda-abstraction, we need to know the type of the last argument of cons. Therefore, we need to specialise the type of cons wrt. the arguments it is applied to. We do so by substituting the arguments, to which the constant or a term is applied, into the term’s type.

Since our main use case for $\eta$ -expansion is to ensure that constants and constructors are applied to all logical arguments, we use the masks generated by the analysis phase for optimisations (see Section 5.1) to compute to which extent constants and constructors should be $\eta$ -expanded.

Since $\eta$ -equality is part of Coq’s conversion mechanism, the resulting terms will be convertible to the originals.

Expansion of branches. This transformation is tightly related to the representation of the construct in Coq. The branches are represented as a list with each position corresponding to a constructor of the type of the discriminee. ^{Footnote 14} Each element of the list of branches is a pair with the first component being a number of a constructor’s arguments, and the second—a term, that can be applied to the number of arguments, specified in the first component. The second component might be not $\eta$ -expanded. Let us consider a simple (contrived) example.

The internal representation of the branches is a list, admitting different ways of representing the second branch. For example, it is perfectly fine to just use the cons constructor applied only to the type of elements, but not to the other two arguments. This list looks as follows in term of the AST constructors (we abbreviate the MetaCoq representation of the list of natural numbers as LIST and the type of natural numbers as NAT).

The pretty-printing procedure expects that all the branches start with lambdas if the corresponding patterns have arguments. This invariant makes it possible to print the patterns in the usual way, with the top lambda-abstractions becoming pattern variables. Therefore, we would like to expand the second branch, so it has the following shape (we abbreviate the binder information for lambda-abstractions as X and XS):

Or, written in the concrete syntax fun (x : nat) (xs : list nat) =≥ cons x xs.

In most cases, writing a programme in Coq does not lead to unexpanded representation of branches, but we have noticed that certain automatically generated definitions, like eliminators, might contain branches that are not expanded enough. One example of such a definition is sig_rect, an eliminator for the sig type from the standard library of Coq. Without expansion, such definitions would prevent us from using our extraction pipeline.

The implementation of the branch expansion is similar to the $\eta$ -expansion pass with one subtlety. As we have noted before, we need to specify types for each binder introduced by lambda-abstractions. Getting the information about the type of branches is quite complicated and with the current representation of branches in Template Coq would require running type inference. Instead, we use a recent feature of Template Coq, called holes. Holes in Coq are represented by so-called existential variables, that can be manipulated by tactics and instantiated by the elaboration mechanism. In our case, the surrounding context provides enough information for these variables to be instantiated. Implementation-wise, due to similarities with the “regular” $\eta$ -expansion, the passes are defined together.

Inlining The motivation for having an inlining pass is that some definitions that are not typable in the extracted code, become typable after inlining and specialising the bodies. Inlining also helps to overcome some potential performance issues. We have two common examples of this kind.

• Dependent eliminators. The code produced after extraction might be not typable because the original type is more expressive than prenex polymorphism in our target languages. Languages like CameLIGO do not support polymorphism at all. Moreover, using eliminators like bool_rect (non-dependent version of it is essentially if_then_else) is impractical, because the target languages use the call-by-value evaluation strategy. Therefore, evaluating expressions like bool_rect_ branch1 branch_2 cond will effectively lead to evaluating both branches regardless of the condition, while we would like it to behave similarly to if_then_else. After inlining, bool_rect unfolds to pattern-matching and behaves as expected.

• General definition of a monad. The definition of a monad uses rank-2 polymorphism, which, again, goes beyond the supported types in the target languages. But inlining concrete instances of bind and allows us to avoid this issue and continue using high-level abstraction in Coq while extracting the well-typed code.

In our framework, the inlining function has the following signature.

template_inline : (kername → bool) → Transform global_env

The argument is a function indicating which constants should be inlined. Apart from just inlining the bodies of specified constants, we also perform $\iota$ and $\beta$ -reductions. The extent to which the term is reduced is determined empirically from the applications to extraction. Clearly, since inlining is $\delta$ -reduction, accompanied with $\iota$ - and $\beta$ -reductions, the resulting terms are convertible to the original ones since all these reductions are part of Coq’s conversion mechanism.

5.3 Extracting to liquidity and CameLIGO

Liquidity is a functional smart contract language for the Tezos and Dune blockchains inspired by OCaml. It compiles to Michelson ^{Footnote 15} —a stack-based functional core language supported directly by the blockchain, developed by Tezos.

LIGO is another functional smart contract language for Tezos that compiles to Michelson. LIGO has several concrete syntaxes: PascaLIGO, ReasonLIGO, and CameLIGO. We target the CameLIGO syntax due to its similarity with Coq.

Compared to a conventional functional language, Liquidity and CameLIGO have many restrictions, mostly inherited from Michelson. Hence, we briefly present the key issues when extracting to these languages.

In both Liquidity and CameLIGO, data types are limited to non-recursive inductive types, and support for recursive definitions is limited to tail recursion on a single argument. ^{Footnote 16} That means that one is forced to use primitive container types to write programs. Therefore, the functions on lists and finite maps must be replaced with “native” versions in the extracted code. We achieve this by providing a translation table that maps names of Coq functions to the corresponding Liquidity/CameLIGO primitives. Moreover, since the recursive functions can take only a single argument, multiple arguments need to be packed into a tuple. The same applies to data type constructors since the constructors take a tuple of arguments. Currently, the packing into tuples is done by the pretty-printers after verifying that constructors are fully applied.

Another issue is related to the type inference in Liquidity and CameLIGO. Due to the support of overloaded operations on numbers, type inference requires type annotations. We solve this issue by providing a “prelude” for extracted contracts that specifies all required operations on numbers with explicit type annotations. This also simplifies the remapping of Coq operations to the Liquidity/CameLIGO primitives. Moreover, we produce type annotations for top-level definitions.

In Coq are simply inductive types with one constructor. At the pretty-printing stage, we identify any such types and print them as native records. Liquidity does not allow records with only a single field, or inductive types with one constructor. In this case, we print the type as an alias for the type of the field/constructor. For example, consider the Coq record below, and the function get_x which retrieves the x field of the record using Coq’s built-in record projection syntax.

This printed to Liquidity as

Note in particular how the projection a.(x) is printed simply as a.

As a consequence of these restrictions on Liquidity, one should use either type aliases or single-field records in place of inductive types with one constructor in the Coq code. These restrictions only apply if the contract is to be extracted to Liquidity. For the other target languages, these restrictions do not apply.

Higher-order functions in Liquidity. Some standard functional programming patterns do not work in Liquidity due to some non-standard features of its type system. For example, the type of a closure contains information about the environment to which it is closed. ^{Footnote 17} For that reason, some programmes, which are completely unproblematic in many functional languages are not accepted by the Liquidity compiler. For example, the following programme refuses to compile

producing a type error Types ((int → int)[@closure :int]) and int → int are not compatible. The my_map function expects a function of type nat → nat, but the call of my_map in the body of bar gets a function of a different type: (int → int)[@closure :int], where :int refers to the type of the variable i. This makes using higher-order functions highly problematic. Moreover, this problem extends to closures returned from different branches of expressions, limiting the number of programs that one can extract to Liquidity without additional efforts.

Handling absurd cases. We follow the general strategy outlined in Section 5.1.4. Both Liquidity and CameLIGO feature an effectful operation failwith, which allows for interrupting the contract execution. We identify pattern-matchings with no branches at the pretty-printing stage and insert the failwith operation. However, inlining some constants (e.g. False_rect) is required in order to make examples like safe_head to compile with the CameLIGO compiler, otherwise, extraction produces polymorphic definitions, which are not supported. In Liquidity, however, we run into issues unrelated to the handling of absurd cases. The failwith works as expected, but closure types carry information about the environment wrt. which they are closed. Dependent pattern-matching in Coq produces code with many closures, which are not accepted by the Liquidity compiler. Therefore, extraction of programmes to Liquidity that extensively uses dependent pattern-matching is currently limited.

Explicit type annotations in CameLIGO. LIGO’s typechecker is not able to infer types in some instances. These are

• 0-ary constructors of primitive parametric types, e.g. None and the empty list [ $\,$ ];

• function types and in particular arguments of lambda expressions;

• the type of failwith.

Therefore we need to add explicit type annotations to these terms. To do this, we augment ${\lambda_\square}{}$ terms with their types, obtained using the erasure procedure for types Section 5.1.1. We designed a general annotation procedure that can add arbitrary data to the ${\lambda_\square}$ AST nodes without changing the AST representation itself. This is achieved using dependent types: we implement a procedure that for each AST node builds a (nested) product type recursively. The fragment of the procedure is given below.

For CameLIGO, we specialise our annotation machinery to box_type giving us the type of annotated terms annots box_type t for any term t of ${\lambda_\square}$ . This type-augmented representation is (optional) part of our intermediate representation ${\lambda^T_\square}$ .

The CameLIGO pretty-printer function recurses on the annotated terms and utilises the typing information whenever is necessary. Since the annotation pass is done separately and independently from the pretty-printer, it may be used for other purposes or new target languages in the future.

No polymorphic types in CameLIGO. Unlike Liquidity, CameLIGO does not currently support user-defined polymorphic types, but there is ongoing work to support polymorphic types in the near future. One possibility to circumvent this restriction is to implement a full specialisation pass that produces completely monomorphised code. However, with the prospect of support for polymorphic types, we instead simply ignore this restriction, although we are aware not all the examples will type check currently. ^{Footnote 18}

Integration. In order to generate code for a contract’s entry points (functions through which one can interact with the contract), we need to wrap the calls to the main functionality of the contract into a construction. This is required because the signature of the entry point in Liquidity and CameLIGO is params → storage → (operation list)* storage, where params is a user-defined type of parameters, storage a user-defined state and operation is a transfer of contract call. The signature looks like a total function, but since Liquidity and CameLIGO support a side effect failwith, the entry-point function can still fail. On the other hand, in our Coq development, we use the option monad to represent computations that can fail. For that reason, we generate a wrapper that matches on the result of the extracted function and calls failwith if it returns None.

The ChainBase type class represents an address abstraction, specifying which properties are required from a type of addresses for accounts. Smart contracts defined using the execution layer infrastructure are abstracted over a ChainBase instance. That means that types Chain and ContractCallContext, along with init and receive functions will get an additional parameter corresponding to the ChainBase instance. When printing the contract code, we need to remap Chain and ContractCallContext to their representation in the target language, and the dependency on ChainBase makes it problematic. We define a specialisation procedure that specialises all definitions dependent on ChainBase to an axiomatic instance and removes the corresponding parameter. Currently, this procedure is defined on PCUIC representation and is not verified.

Examples. The extracted counter contract code to Liquidity and CameLIGO is given, respectively, in Figure 5(a) and (b). We omit some wrapper code and the “prelude” definitions and leave the most relevant parts (see Appendices A and B for the full versions). As one can see, the extraction procedure removes all “logical” parts from the original Coq code. Particularly, the sig type of Coq becomes a simple wrapper for a value (type ’a sig_ = ’a in the extracted code). Currently, we resort to an ad hoc remapping of sig to the wrapper sig_ because Liquidity and CameLIGO do not support variant types with only a single constructor. The remapping is done using the translation table, as described in the end of Section 5.1. Ideally, this class of transformations can be added as an optimisation for inductive types with only one constructor taking a single argument. This example shows that for certain target languages optimisation is a necessity rather than an option.

Fig. 5. Extracted code.

We show the extracted code for the coq_inc_counter function and omit coq_dec_counter, which is extracted in a similar manner. These functions are called from the counter function that performs input validation. Since the only way of interacting with the contract is by calling counter it is safe to execute them without additional input validation, exactly as it is specified in the original Coq code.

Apart from the example in Figure 4, we successfully applied the developed extraction to several variants of the counter contract, the crowdfunding contract described in Annenkov et al. (Reference Annenkov, Nielsen and Spitters2020), the contracts from Sections 6 and 7 and an interpreter for a simple expression language. The latter example shows the possibility of extracting certified interpreters for domain-specific languages such as Marlowe (Lamela Seijas & Thompson Reference Lamela Seijas and Thompson2018), CSL (Henglein et al. Reference Henglein, Larsen and Murawska2020) and the CL language (Bahr et al. Reference Bahr, Berthold and Elsman2015; Annenkov & Elsman Reference Annenkov and Elsman2018). This represents an important step towards safe smart contract programming. The examples show that smart contracts fit well to the fragment of Coq that extracts to well-typed Liquidity and CameLIGO programmes. Moreover, in many cases, our optimisation procedure removes all the boxes resulting in cleaner code.

Gas consumption. Running smart contracts on a blockchain requires so-called “gas”, which serves as a measure of computational efforts. The execution environment calculates the gas consumption according to the cost of each operation and uses it to terminate the execution if the maximum gas consumption is reached. The caller pays a fee in the blockchain’s internal currency for calling a contract. If the fee is too low and the gas consumption is too high, there is a chance that the transaction will not be included in a block. This behaviour is slightly different from Ethereum, but we will not provide the details here.

We have deployed and executed some of our extracted contracts on test networks (these networks use the same execution model as the main one, but no real money is required to run contracts). Comparing the gas consumption shows that extracted contracts perform well in the realistic setting, even though, the extracted code consumes more gas compared to a hand-written implementation. We have compared the ERC20 token implementation against the Liquidity code from the online IDE. The extracted code consumes 2–2.5 times more gas, but the consumption is quite far from reaching the hard limit on a single contract call. We have also experimented with the prototype DSL interpreter extracted from our Coq developments on the Tezos network. The recommended fees, converted to US dollars were lower than $0.03$ even for DSL programmes with 100 instructions. Such transaction costs can be considered negligible. Most of the gas consumption can be attributed to type checking of a contract for each call, which, of course, depends on its length and complexity. However, gas consumption and the associated fees become smaller with each update of the Tezos network, making the transaction fees negligible for many common use cases. The threshold on gas consumption also increases, allowing for more expressive smart contracts. Therefore, our smart contract extraction is able to deliver verified code with reasonable execution costs.

5.4 Extracting to Elm

Elm (Feldman Reference Feldman2020) is a general purpose functional language used for web development. It is based on an extended variant of the Hindley–Milner type system and can infer types without user-provided type annotations in most situations. However, we generate type annotations for top-level definitions to make the extracted code more readable. Moreover, unlike Liquidity, there is no restriction in Elm regarding data types with one constructor. That allows implementing a simple extraction procedure for Coq records as data types with one constructor and projections defined as functions that pattern-match on this constructor. Compared to Liquidity and CameLIGO, Elm is a better target for code extraction, since it does not have some limitations pointed out in Section 5.3.

Extraction to Elm also poses some challenges. For example, Elm does not allow shadowing of variables and definitions. Since Coq allows for a more flexible approach to naming, one has to track scopes of variables and generate fresh names in order to avoid clashes. The syntax of Elm is indentation sensitive, so we are required to track indentation levels. Various naming conventions apply to Elm identifiers, e.g. function names start with a lower-case character, types and constructors—with an upper case character, requiring some names to be changed when printing.

Handling absurd cases. We follow the general strategy outlined in Section 5.1.4. Elm is a pure functional language and does not feature exceptions, which we could use to handle the absurd cases. However, there is one side-effect at our disposal, namely, non-termination. Therefore, we define the following constant.

At the pretty-printing stage, we identify pattern-matchings with no branches and insert a call to false_rec.

Examples We tested the extracted code with the Elm compiler by generating a simple test for each extracted function. We implemented several examples by extracting functions on lists from the standard library of Coq, functions using subset types and functions that eliminate absurd cases by exploiting contradictions. All our examples resulted in well-typed Elm code after extraction. Particularly, in Figure 6(b) one can see the safe_head function (a head of a non-empty list) from Section 5.1.4. The example uses the elimination principle False_rect in the case of an empty list, exploiting the contradiction with the assumption that the input list is non-empty. We used the usual style of writing functions with dependent types in Coq with the help of the tactic.

Fig. 6. Extracted test code in Elm.

As a result, the logical parts corresponding to proofs are erased and Coq’s implementation of subset types is extracted as a simple wrapper type Sig a = Exist a. In the impossible (absurd) case, safe_head calls false_rect, which is implemented in terms of false_rec, using our strategy of handling absurd cases. We also extract a example function that uses safe_head:

Clearly, it is always safe to take the first element from a list that is generated by repetition $1+n$ times. Therefore, the whole programme is safe to use and the absurd case will never be hit. When extracting programmes as libraries, one could move some static checks to runtime to ensure that the invariants, expected by dependently typed functions are preserved.

We also extract the Ackermann function ackermann : nat * nat → nat defined using well-founded recursion which uses the lexicographic ordering on pairs. This shows that extraction of definitions based on the accessibility predicate Acc is possible. Computation with Acc is studied in more detail in Sozeau & Mangin (Reference Sozeau and Mangin2019).

Verified Web Application We develop a more Elm-specific example in Coq: a simple web application. A typical Elm web application follows the Elm architecture (TEA):

1. 1. Model—a data type representing the state of the application.

2. 2. Update—a function that takes a message, a previous state (model instance) and returns a new state and, potentially, commands (e.g. sending data to a server, etc.)

3. 3. View—a function that turns the model into HTML. HTML is generated using special Elm functions, available as part of the Elm standard library.

If we look at the first two items, they look very similar to the smart contract execution model. At the moment, we do not provide an Elm-specific execution model as part of our framework, but we can leverage Coq dependent types to encode some invariants of the model and then use our extraction pipeline to produce an Elm web application. Therefore, we implement the model and the update functionality along with validation rules in Coq, extract it to Elm and combine it with hand-written rendering code (the view).

The example we consider is inspired by the Elm guide on forms. Our application consists of an input form, a validator and a view for rendering a list of valid items. The input form consists of three fields: a username, user’s password, and a field to re-enter the password. In Coq, we model it with the following code.

This part of the model contains “raw” data, as entered by a user. We define then “valid data” using the subset types of Coq.

We use the boolean versions of less-or-equal ( $\leq ?$ ) and equality (=?) on strings, which are implicitly coerced to propositions using is_true (p : bool) : Prop := p = true. This representation makes the interaction with the validation function easier. Then, we define a type of entries that we are going to store in the list of users in the model. In the same way, we define what it means to be valid for such stored entries.

Having defined ValidStoredEntry, we can then proceed with the definition of a model for the whole application.

As one can see, users in our model are represented as a list of valid entries without duplication of names. Next, we define the messages for updating the model.

Now, we can define a function that performs updates to the model by interpreting the messages it receives.

We use the record update notation that uses type classes and Template Coq-based generation of field setters (part of our development). We also use the standard way of working with subset types in Coq using command that allows writing code in the style of regular functional programming while manipulating richer types under the hood. inserts projections from the values of subset types and constructs values, leaving the proof component as an obligation that the user can prove later.

The main idea behind having valid entries is that most of the functionality of our web application manipulates valid data. This guarantees that no invariants can be broken by these functions. The validation is performed only once, at the “entry point” of our application, the updateModel function and it is driven by the validity predicates of the components of the model. Therefore, when writing a validation function, it would be impossible to miss some validation rule, because valid data requires explicit proofs of validity. Since the Elm architecture guarantees that the only way our model is updated when users interact with the web application is by calling the updateModel function, we know that in the extracted code the model invariant will not be broken.

The term produced by might be quite complex, due to the transformations and elaboration required to produce a fully typed term. Our extraction pipeline is able to cope with the terms generated by and can be run completely in Coq itself. We define the required remappings to replace the usage of standard functions with Elm counterparts. E.g. we remap Coq types string, list, bool and the product type to the corresponding types in Elm. We also remap natural numbers of Coq to type of bounded integers Int. In principle, using bounded numbers might be a problem, but in our case, the only use of numbers is for computing the password length, and String.length in Elm has type String → Int. Therefore, our choice is coherent with the assumptions about string length in Elm.

We use the inlining pass in the pipeline to inline some of the record update infrastructure. Inlining also prevents us from generating a type alias (related to the records update infrastructure) that is invalid in Elm due to an unused type parameter, which is not allowed.

Overall, we show that one can use the usual certified programming style in Coq in order to implement the logic of a web application that can be then extracted to a fully functional Elm web application (provided that the view functionality is written directly in Elm). The generated application is well-typed in Elm, even though we have used dependent types extensively.

5.5 Extracting to rust

Rust is a mixed paradigm general-purpose programming language that features many of the same concepts as functional programming languages. It is aimed at being a fast language with low overhead, which also makes it an attractive smart contract programming language. Therefore, it provides a lot of control and is also a relatively low-level programming language. The Concordium blockchain toolchain uses Rust as its primary programming language for writing smart contracts. The actual code that is executed on-chain is WebAssembly. WebAssembly is designed to be a safe, portable and efficient low-level language with well-defined semantics making it well-suited for verification in a proof assistant (Watt Reference Watt2018). Like Rust, WebAssembly does not feature a garbage collector, making it a good target for compiling Rust.

When writing smart contracts in Rust, the implementors have more ways of controlling performance. One of the most expensive operations on blockchains is updating the contract’s state. Rust allows for destructive updates of the mutable contract state with the precise control of the serialisation/deserialisation process allowing for careful performance tuning. Using the Concordium toolchain, smart contracts written in Rust are compiled to WebAssembly modules using LLVM. The WebAssembly modules can be then deployed and executed on-chain.

Rust has a powerful functional subset that includes

• Sum/product types

• Pattern matching

• Higher-order functions and closures

• Immutability by default

• Everything-is-an-expression

• A Hindley–Milner (without let-polymorphism) based type system

These features make Rust a suitable and relatively straightforward target for printing from ${\lambda^T_\square}$ . However, as Rust is a low-level language giving a lot of control, it also comes with its own set of challenges.

Extracting data types. The type system of Rust features the concept of ownership—variable bindings have ownership of what they bind. The ownership system is a substructural type system allowing for precise control of the resource usage: allocating, deallocating, copying, etc. It is used in Rust as a zero-cost abstraction allowing for safe memory management. The part of the compiler called the borrow checker checks that the resources are used according to the ownership rules.

In Rust, the programmer controls whether fields of data structures are stored by-value or through indirection. For recursive data structures, such as linked lists, it is necessary to use indirection since otherwise, the size of the data type would be infinite. Concretely, this means that a type such as

cannot be extracted in a straightforward way where the tail is just of type list A. Instead, it is necessary to use indirection to store a form of a pointer to the tail of the list. In Rust, there are several ways to store indirection, including C-like raw pointers, borrowed references, owned references, and through reference counting (the Rc and Arc types). The benefit of the Box, Rc, and Arc types is that ownership is managed implicitly, while for raw pointers and borrowed references it is necessary to store the data somewhere else. Borrowing means passing a reference to something without transferring the ownership. Roughly speaking, a borrowed reference can be seen as a pointer with additional static guarantees provided by the type system of Rust. An owned reference Box<T> is a smart pointer, pointing to the data allocated on the heap.

Since functional languages generally rely on sharing to perform well the same sharing should be supported in the final extracted Rust programme. In particular, this disqualifies owned references as those can only be shared through expensive copying. Reference counted types in Rust require explicit cloning to manually indicate when the reference count must be incremented. This complicates extraction significantly as extraction then has to determine that it needs to insert such clonings when passing arguments and when capturing local variables for closures.

As a result of these considerations, the extraction uses borrowed references to store nested data types. Such references are trivially copyable and can be shared freely, but require that the data be stored somewhere else. Additionally, this requires data structures to be generalised over a lifetime. Lifetimes are used by the borrow checker to determine how long references are valid. In some situations, they can be inferred by the compiler. However, storing references in data types require explicit lifetime parameters. For uniformity, we add a lifetime to all data types we extract. As Rust datatypes must use all lifetimes and type parameters they introduce, the extraction also adds “phantom” uses of these through the use of PhantomData, a zero-cost Rust type meant to specify to the Rust compiler that a lifetime or type parameter is allowed to be unused. For uniformity, such PhantomData types are emitted as the first member of all data types in all constructors, leading to a final extraction of lists as

where the ’a parameter is lifetime, and A is a type parameter. The &’a syntax corresponds to a borrowed reference with lifetime ’a.

Memory model differences. Rust is an unmanaged language without a garbage collector. When extracting from a language like Coq, in which all memory allocation is handled implicitly for the programmer, this leads to some challenges. This is made significantly easier when it is noted that smart contract execution is self-contained and very short-lived. Due to this, it is feasible to allocate as much memory as necessary during the execution and then clean up only after the execution is done, a technique known as region-based memory allocation. The extraction can thus use an off-the-shelf library that implements region-based memory allocation; in particular, the Bumpalo library is used.

For more general-purpose extraction of programmes that may be long-running, we are considering using a conservative garbage collector such as the Boehm–Demers–Weiser (Boehm & Weiser Reference Boehm and Weiser1988; Boehm et al. Reference Boehm, Demers and Shenker1991) garbage collector. Here the challenge lies in implementing the right heuristics to figure out when garbage collection should be invoked during an extracted program.

Extraction produces a structure Program that contains the region (or arena) of memory that can be allocated from. Structures are similar to records, but in addition to fields can have functions associated with them. Such functions are called methods. The first parameter of a method is , a reference to the instance of the . Methods are defined in the corresponding block.

We extract the entire programme as methods on the Program structure that can then access the region when memory allocation is required. As an example, consider the function . Note that we produce two versions of add: curried and uncurried. The curried version returns a closure implemented using dynamically dispatched trait objects of type . We discuss the details of closure extraction and partial applications below. The extracted code of the add function with all of its dependencies is presented in Figure 7.

Fig. 7. The add function extracted to Rust.

Our Rust extraction also supports remapping and that nat normally would be remapped to either a big-integer type or to the u64 type using checked arithmetic. With the example we have considered, including functions on lists and other inductive types, extracting a complete implementation of a program produces well-typed code, also wrt. ownership. However, we have not attempted to fully extract complex container libraries, such as FMaps.

It is sometimes necessary to remap Coq container types (lists, finite maps) to corresponding Rust libraries. In this case, one has to take care of the ownership issues manually for the corresponding remapped fragments of code. This can be done by first defining a wrapper function manually in Rust, having in mind the memory model of the extracted code. One can then make sure that the wrapper code compiles, so it can be added to a translation table for pretty-printing.

Handling ‘monomorphised’ closures. In order to handle polymorphic functions (functions with type parameters), the Rust compiler performs a transformation called monomorphisation. That means that the compiler generates copies of a generic function with parameters replaced with concrete types, used in the program. Rust implements closures in an efficient way by combining their code with the environment they capture into an anonymous type. Functions can be monomorphised with respect to these types, allowing the use of closures to be a zero-cost abstraction. For example, closures can be inlined as if they are normal functions or stored directly in data structures. However, the semantics of such closures are different from the semantics of closures in traditional functional languages.

In Coq, a closure behaves like any other function and is fully compatible with other functions of that function type. For example, it is possible and unproblematic to store multiple different closures of the same function type in a list. This uniform behaviour does not carry over to Rust’s default treatment of closures: when storing a closure in a list, the list must be typed over the anonymous closure type that the compiler has generated automatically. Therefore, it is not possible to store two different closures, even of the same function type, in such a list.

Rust still allows for semantics that match Coq’s at the cost of some performance through trait objects. Trait objects use virtual dispatch to allow for example closures to behave uniformly as functions, hiding away the associated environment. ^{Footnote 19} Trait objects can exist only as a reference and extraction must thus allocate closures and turn them into references. The extraction automatically provides the helper function closure that performs this allocation using the same region-based allocation as described above. In some cases, the Rust compiler requires annotations when using closures through allocated trait objects. Therefore, we use the following wrapper to aid the type inference.

The keyword denotes the fact that the trait object is dynamically dispatched. We conservatively insert the wrapper whenever the head of the application is not a constant, a constructor, or an application.

language=Coq

Partial applications. Rust requires all functions to be fully applied when called, unlike Coq which supports partial application. Partial applications can be emulated easily through closures, by generating both curried versions and uncurried versions of functions. However, using closures is less efficient, so as an optimization the extraction avoids closures when possible. Concretely, this results in both curried and uncurried versions as is seen in the extraction above, with the curried version calling into the uncurried version.

Internal fixpoints. Coq supports recursive closures through the construct. In comparison, Rust does not have similar support for recursive closures and supports only recursive local functions which do not allow capturing. This means that only top-level recursive Coq functions can straightforwardly be made recursive during extraction; when a fixpoint is used internally (for example, through a binding), there is no simple way to extract this. To work around this issue, we apply a technique known as “Landin’s knot” (Landin Reference Landin1964). Namely, our extraction uses recursion through the heap. Concretely, when an internal fixpoint is encountered, extraction produces code that allocates a cell on the heap to store a reference to the closure. The closure can access this heap cell and thus access itself when it needs to recurse. To exemplify, a straightforward definition of the Ackermann function in Coq uses nested recursion:

Non-mutual top-level fixpoints are extracted as a common special case by transforming the fixpoint’s arguments into lambda-abstractions before printing. See . The inner fixpoints are extracted using “Landin’s knot”. Our extraction produces the following Rust code.

Mutual internal fixpoints are also supported. In fact any mutual fixpoint is extracted as an internal fixpoint, even if it is a top-level definition.

Handling absurd cases. We follow the general strategy outlined in Section 5.1.4. The natural choice for implementing the elimination principle for an empty type is to use Rust’s panic! macro. In this case the elimination principle for False extracts to the following Rust code.

We identify pattern-matchings with no branches at the pretty-printing stage and insert the panic! macro.

Integrating with Concordium Concordium maintains the smart contract state in a serialised form, i.e. as an array of bytes. Similarly, when a smart contract is called, its message is passed as an array of bytes. To aid in conversion between the smart contract’s data types and these byte arrays, the Concordium toolchain provides automatic derivation of serialisers and deserialisers between arrays of bytes and standard Rust data types. This conversion, however, does not support references, as it is unclear how to deserialise into a reference. In addition, the ConCert smart contracts extracted are not immediately compatible with the signatures expected by Concordium.

To aid in connecting between ConCert and Concordium a standard library is provided by ConCert. This standard library includes several helper types that extracted smart contracts depend on, and additionally also provide procedural macros that can be used to derive serializers and deserializers that, through the use of regions, support deserialising references. When a smart contract is extracted, it automatically has serializers and deserializers derived for its structures, and the extraction takes care to generate glue code that properly performs deserialisation and serialization with a proper region. Finally, the glue code also connects between Concordium’s expected smart contract signature and the one extracted by ConCert.

We proceed to highlight some case studies using the ConCert framework.