Linearization via Rewriting Ugo dal Lago, Federico Olimpieri Abstract We introduce the structural resource λ \lambda -calculus , a new formalism in which strongly normalizing terms of the λ \lambda -calculus can naturally be represented, and at the same time any type derivation can be internally rewritten to its linearization. The calculus is shown to be normalizing and confluent. Noticeably, every strongly normalizable λ \lambda -term can be represented by a type derivation. This is the first example of a system where the linearization process takes place internally , while remaining purely finitary and rewrite-based . 1 Introduction Slightly less than a century since the pioneering contributions by Church and Gentzen, the study of proof theory, type systems and the \lambda -calculus has produced a multitude of logical and computational formalisms in which proofs and programs can be represented and the process of either eliminating cuts or evaluating a program by forms of rewriting can be studied directly within the system at hand, often giving rise to confluence and normalization results (see, e.g., [ Girard73 , Reynolds74 , ML80 , Parigot92 ] ). The considered systems are often very expressive, which is why the aforementioned normalization properties become logically non-trivial, and can hardly be carried out combinatorially. Since the mid-eighties, the situation sketched above has somehow changed: the advent of linear logic [ Girard87 ] has allowed a finer structure to be attributed to the underlying computation process. By identifying structural logical rules, and in particular contraction , as the bottleneck in the normalization results, linear logic gave rise to the introduction of proof and type systems in which structural rules are very severely restricted or not allowed at all . As a consequence, normalization properties can be proved by purely combinatorial means: rewriting and cut-elimination have the effect of strictly reducing the size of the objects at hand. Systems of this kind, which we will call quantitative — simply to distinguish them from the somehow qualitative systems we referred to in the previous paragraph — include not only multiplicative linear logic [ Girard87 , DanosRegnier89 ] , but also non-idempotent intersection types [ Gardner94 , DeCarvalho18 ] , the resource \lambda -calculus [ Boudol93 , EhrhardRegnier08 ] , and certain type systems based on restrictions of exponentials such as the so-called light logics [ GSS92 , Girard98 , Lafont04 ] . In quantitative systems, there is an aspect of finiteness absent in qualitative systems, which makes them particularly suitable to the characterization of complexity classes and in general whenever a fine control over the use of resources is considered necessary. A proof or program, in quantitative systems, is an object that reveals everything about its dynamics, i.e. , about the evolution it will undergo as a result of the evaluation. Since the early days of linear logic, there have been many attempts to relate quantitative and qualitative systems by studying how to transform proofs and programs in qualitative systems into equivalent objects in quantitative systems. Already in Girard’s original work [ Girard87 ] there is a trace of all this in the so-called approximation theorem , which states that every cut-free proof of multiplicative and exponential linear logic can be approximated, in a very natural sense, by a proof of multiplicative linear logic. We should also mention the line of work about linearizing the \lambda -calculus [ Kfoury00 , AlvesFlorido03 , AlvesFlorido05 , AlvesVentura22 ] , in which one studies to what extent pure \lambda -terms can be linearized into linear terms, establishing on one hand that this process can be applied to all normalizing terms following their reduction sequence, and that on the other hand a relationship exists between the emerging process and typeability in non-idempotent intersection types. We should also mention the crucial contribution of Ehrhard and Regnier [ EhrhardRegnier08 ] , who through an inductive and very elegant definition, provide a notion of Taylor expansion for any pure \lambda -term as the (infinite) set of its linear approximants. Continuing along the same vein, we must certainly mention the results on the extensional collapse of quantitative denotational models into qualitative models [ er:collapse ] . The collapse induces a categorical understanding of the relationship between idempotent ( i.e. , qualitative) and non-idempotent ( i.e. , quantitative) intersection types. However, this result does not directly yield an explicit program transformation. In all these attempts, the infinitary aspects of qualitative systems are either neglected by considering only cut-free proofs, or reflected in the target of the transformation, like in the Taylor expansion. In the case of Kfoury’s linearization [ Kfoury00 ] , in particular, the process of computing the linear approximant of a pure \lambda -term is delegated to a notion of expansion that, even if formally defined in terms of rewriting, is trivially not normalizing, because it consists in increasing the size of the right argument bag of an application, thus matching the number of arguments required by the related abstraction. In a certain sense, therefore, the linearization process remains fundamentally infinitary, similar to what happens in the Taylor expansion [ EhrhardRegnier08 ] . The same holds for the remarkable recent contribution by Pautasso and Ronchi [ PautassoRonchi23 ] , which introduces a quantitative version of the simple types in which derivations carry the same kind of quantitative information as in non-idempotent intersection types. The system turns out to be equivalent to the usual simply-typed \lambda -calculus in terms of typeability, but the proof of this fact is carried out externally to the system, and is nontrivial. Could linearization be made an integral part of the underlying system? Is there a way to compute a linear version of a program (or proof) so that this transformation happens within the system? The authors are strongly convinced of the interest of these questions and think that understanding to what extent all this is possible can help shedding some light on the relationship between qualitative and quantitative systems. The main contribution of the present paper is precisely to introduce a language and type system in which qualitative systems can be naturally embedded and an essentially quantitative fragment can be isolated. More specifically, terms typable in qualitative systems such as the simply-typed \lambda -calculus can be compositionally embedded into the calculus. Linearization, this is the real novelty, becomes a form of rewriting turning any term into a linear approximation of it. The role of this rewriting process, called exponential reduction, is to eliminate the use of structural rules without performing any \beta -reduction, the latter being part of the system itself. Crucially, exponential reduction is strongly normalizing. The calculus thus obtained can be seen as an extension of Boudol’s resource \lambda -calculus [ Boudol93 ] , and we call it the structural resource \lambda -calculus . Technically, the key ingredients in its definition are as follows. At the level of terms, there is both the possibility of having a nonlinear use of variables, but also of passing a bag of terms to an abstraction, in the style of the resource \lambda -calculus. Crucially, abstractions are labeled so as to identify the structural rules needed to fire the corresponding redex. An intersection type assignment system is an integral part of the calculus and guarantees the termination of each sequence of \beta -reduction steps. As already mentioned, the latter is not the only available reduction rule, and is complemented in an essential way by exponential reduction, giving rise to what we call structural reduction . In addition to the definition of the structural resource \lambda -calculus, the key technical contributions of this paper are proofs of confluence and strong normalization for structural reduction. Remarkably, every strongly normalizable \lambda -term can be represented in a natural way by a structural resource term, the embedding being based on idempotent intersection types [ dez:int ] . 2 A Bird’s Eye View on Linearization and Intersection Types The purpose of this section is to informally describe the process of linearization in the \lambda -calculus, anticipating some of the problems we have to face, at the same time introducing the non-specialist reader to the topic. We will proceed by analyzing a very simple example of a \lambda -term, which will also constitute a sort of running example in the rest of this manuscript. Let us consider the \lambda -term MN , where M\coloneqq\lambda x.w(x(xy))(xy)\qquad N\coloneqq\lambda z.qzz To the above term we can attribute simple types in the obvious way: w:o\rightarrow o\rightarrow o,y:o,q:o\rightarrow o\rightarrow o\vdash MN:o (1) The term MN is not a linear term at all, however, in particular due to the nonlinear use of the variables x and z by the terms M and N , respectively. Understanding the quantitative aspects of the dynamics of the term looking at its typing is not immediate, i.e., it is not possible in a direct way. By \beta -reducing the term, however, one realizes quite easily that the variable y , although occurring free only twice in the term, will occur free six times in its normal form. Depending on the use that w and q will make of their arguments, this number could grow or decrease. Would it be possible to account for the calculations above from within a type system ? The answer is positive: as is well-known, non-idempotent intersection types [ Gardner94 , DeCarvalho18 ] allow us to type the same term in the following way: w:\langle\langle o\rangle\multimap\langle o\rangle\multimap o\rangle,y:\langle o\rangle^{6},q:\langle\langle o\rangle\multimap\langle o\rangle\multimap o\rangle^{4}\vdash MN:o where the sequence \langle a_{1},\dots,a_{k}\rangle stands for the (commutative but not idempotent) intersection type a_{1}\cap\cdots\cap a_{k} , and \langle a\rangle^{n} stands for \langle a,\ldots,a\rangle , where a appears exactly n times. Once a term is typed in non-idempotent intersection types, its type derivation tells us everything there is to know about the dynamics of the term, including its length. If we want the size of the term itself to reflect the size of the derivation, that is, for the former to become a unique and canonical description of the latter, we must move to the so-called resource terms, where the second argument of each application is not a single term, but a bag of terms. Resource terms correspond to linear approximations of ordinary \lambda -terms. In our example, we obtain the resource terms s:=\lambda x.w\langle x\langle x\langle y,y\rangle,x\langle y,y\rangle\rangle\rangle\langle x\langle y,y\rangle\rangle and t:=\lambda z.q\langle z\rangle\langle z\rangle , getting the following typing for the application s\langle t\rangle^{4} : w:\langle\langle o\rangle\multimap\langle o\rangle\multimap o\rangle,y:\langle o\rangle^{6},q:\langle\langle o\rangle\multimap\langle o\rangle\multimap o\rangle^{4}\vdash s\langle t\rangle^{4}:o (2) How can we compute well-behaved linear approximations ( i.e. , typed resource terms) of a given \lambda -term? If one is only interested in the term’s semantics, and given the aforementioned connection between \lambda -term dynamics and its quantitative approximations, one possibility is to first compute the normal form of the term and then reconstruct the corresponding intersection type derivation. This can be seen as a rephrasing of Girard’s approximation theorem . However, this answer is not completely satisfactory, since it relies on the evaluation of the program. We can thus restate our question as: how do we compute linear approximations without reducing (to \beta -normal form) the considered program? Answering this question is the main goal of this paper. Our main contributions are precisely a language and type system in which all the above-mentioned type derivations can live and where we can define an appropriate notion of rewriting which performs linearization. Below, we describe informally how the transition from ( 1 ) to ( 2 ) can occur within the system. First, let us follow a naive proof-search heuristic to compute the non-idempotent intersection typing of our term. In order to do so, we first embed M and N separately in the resource calculus as terms u=\lambda x.x\langle x\langle y\rangle\rangle\langle x\langle y\rangle\rangle and v=\lambda z.q\langle z\rangle\langle z\rangle with \displaystyle w:\langle\langle o\rangle\multimap\langle o\rangle\multimap o\rangle,y:\langle o\rangle^{2} \displaystyle\vdash u:\langle\langle o\rangle\multimap o\rangle^{3}\multimap o \displaystyle q:\langle\langle o\rangle\multimap\langle o\rangle\multimap o\rangle \displaystyle\vdash v:\langle o\rangle^{2}\multimap o Now, our proof search gets stuck, since the type of the argument v is not the one the function u requires. This happens because v records the presence of two occurrences of z , while u only demands one input. One possible solution would be to extend the unification algorithm for simple types to the intersection type setting, which is precisely what has been done in [ PautassoRonchi23 ] . However, we follow a different path. The types \langle o\rangle^{2}\multimap o and \langle o\rangle\multimap o are different but coherent , in the sense that their syntactic tree is the same up to the number of copies of types occurring inside intersections. In particular, the two are connected by a nested structural rule, which is defined on the contraction c_{o}:\langle o\rangle\to\langle o,o\rangle. We then extend the syntax and the typing of the resource calculus in order to account for (nested) structural rules. In particular, we shall allow the following type inference: q:\langle\langle o\rangle\multimap\langle o\rangle\multimap o\rangle\vdash v:\langle o\rangle^{2}\multimap o c_{o}:\langle o\rangle\to\langle o,o\rangle q:\langle\langle o\rangle\multimap\langle o\rangle\multimap o\rangle\vdash p=\lambda z^{c_{o}}.q\langle z\rangle\langle z\rangle:\langle o\rangle\multimap o from which we can clearly infer the typing w:\langle\langle o\rangle\multimap\langle o\rangle\multimap o\rangle,y:\langle o\rangle^{2},q:\langle\langle o\rangle\multimap\langle o\rangle\multimap o\rangle\vdash u\langle p\rangle^{3}:o. The term u\langle p\rangle^{3} is not a linear approximation of MN , since we are allowing arbitrary structural rules to be used on bound variables. However, we shall recover the linear resource term s\langle t\rangle^{4} as the normal form of u\langle p\rangle^{3} under a novel notion of labelled rewriting, following which we allow for the transformation \lambda z^{c_{o}}.q\langle z\rangle\langle z\rangle:\langle o\rangle\multimap o\to_{c_{o}\multimap o}\lambda z.q\langle z\rangle\langle z\rangle:\langle o,o\rangle\multimap o. Note that we index the reduction with type morphisms connecting the typing of the two involved terms. We exploit an appropriate notion of transformation on type derivations, that consists of an action of the morphism c_{o}\multimap o on the term u, denoted as [c_{o}\multimap o]u . This transformation will track all the occurrences of the bound variable x in u , replacing their type \langle o\rangle\multimap o with \langle o,o\rangle\multimap o. In order to do so, the inputs of x are duplicated accordingly, obtaining the term s . The process consists then in a deterministic and confluent notion of structural rule elimination, which is performed only on-demand . It is worth noting that the rewriting does not perform any substitution. In particular, if s\to_{f}t the two terms s and t are coherent and, hence, are (generally non-linear) approximations of the same ordinary \lambda -term. 3 Some Mathematical Preliminaries Following [ tao:gen ] , we see intersection types as lists of types. This will allow us to obtain a simple and elegant categorical framework, where intersection plays the role of a (strict) tensor product, and morphisms are given by structural rules ( i.e. , permutations, copying, and erasing). In order to properly establish the formal framework, we first need to introduce categories of integers, from which the list construction naturally arises. 3.1 Categories from Natural Numbers We consider the category \mathbb{O}_{f}^{c} whose objects are natural numbers and in which \mathbb{O}_{f}^{c}(m,n):=[n]^{[m]} , where [n]=\{1,\dots,n\} for n\in\mathbb{N} . As a consequence, [0]=\emptyset (so the number 0 is the initial object, \emptyset being the unique map in [m]^{[0]} ). We generally denote composition of morphisms as either g\circ f or gf . The category \mathbb{O}_{f}^{c} is symmetric strict monoidal (cocartesian in particular), with tensor product given by addition. We define the subsets of symmetries of \mathbb{O}_{f}^{c}(m,n) as \mathbb{O}_{f}^{l}(m,n)=\{\alpha\in\mathbb{O}_{f}(m,n)\mid\alpha\text{ is bijective}\} . Evidently, \mathbb{O}_{f}^{l}(m,n) determines a subcategory of \mathbb{O}_{f}^{c} , the category \mathbb{O}_{f}^{l} of symmetries (or permutations ). In what follows, we work with the parametric category \mathbb{O}_{f}^{\spadesuit} , where \spadesuit\in\{c,l\}. 3.2 Lists We often work with (ordered) lists whose elements are taken from a given set X . Such lists are ranged over by metavariables like \vec{a},\vec{b},\vec{c}\dots , and one such list can also be written explicitly as \langle a_{1},\dots,a_{k}\rangle , where k\in\mathbb{N} and a_{1},\dots,a_{k}\in X . The list concatenation of \vec{a} and \vec{b} is indicated as \vec{a}\oplus\vec{b}. We write \lvert\vec{a}\rvert to denote the length of \vec{a} . Given a list \vec{a}=\langle a_{1},\dots,a_{k}\rangle and a function \alpha:[h]\to[k] , the expression \vec{a}^{[\alpha]} stands for the list of length h defined as \langle a_{\alpha(1)},\dots,a_{\alpha(h)}\rangle . This turns \alpha into a contravariant semigroup action on \vec{a} : given \mathsf{len}(\vec{a})=n,\alpha:[m]\to[n] and \beta:[l]\to[m] we have that (\vec{a}^{[\alpha]})^{[\beta]}=\vec{a}^{[\alpha\beta]} . Given a small category A , we define its \spadesuit - monoidal completion , \oc^{\spadesuit}(A) as follows: • \mathrm{ob}(\oc^{\spadesuit}(A))=\{\langle a_{1},\dots,a_{k}\rangle\mid k\in\mathbb{N}\text{ and }a_{i}\in\mathrm{ob}(A)\}. • \oc^{\spadesuit}(A)(\langle a_{1},\dots,a_{k}\rangle,\langle b_{1},\dots,b_{l}\rangle)= \{\langle\alpha;f_{1},\dots,f_{l}\rangle\mid\alpha\in\mathbb{O}_{f}^{\spadesuit}(l,k)\text{ and }f_{i}\in A(a_{\alpha(i)},b_{i})\text{ whenever }i\in[l]\}. The category \oc^{l}(A) is symmetric strict monoidal, while \oc^{c}(A) is cartesian strict monoidal. In both cases, the tensor product is given by list concatenation. Ground morphisms are morphisms of the shape \langle\alpha;\textsf{id},\dots,\textsf{id}\rangle , thus representing the composition of permutations, weakenings and contractions without nesting. Given a list \vec{a} , an integer k\in\mathbb{N} and a morphism \alpha\in\mathbb{O}_{f}^{\spadesuit}([\mathsf{len}(\vec{a})],[k]), we define the ground morphism induced by \alpha as the morphism \langle\alpha;\vec{\textsf{id}}\rangle\in\oc^{\spadesuit}(A)(\vec{a},\vec{a}^{[\alpha]}) . We shall often abuse the notation and denote \langle\alpha;\vec{\textsf{id}}\rangle as just \alpha . The family \alpha_{\vec{a}} for \vec{a}\in\oc^{\spadesuit}(A) is, moreover, a natural in \vec{a} . We use \sigma,\tau\dots for ground morphisms induced by permutations. Example 1 . We give some examples of morphisms in \oc^{c}(A) , where A=\{a,b,c\}. The following is a diagonal morphism (that we also call a contraction ) over A : c_{a}=\langle\alpha;\textsf{id}_{a},\textsf{id}_{a}\rangle:\langle a\rangle\to\langle a,a\rangle where \alpha is the only map from [2] to [1] . For all n\geq 1 we have a n -ary contraction c_{a}^{n}:\langle a\rangle\to\overbrace{\langle a,\dots,a\rangle}^{n\text{ times}} where for n=1 we have that c^{1}=\textsf{id}_{a} . Projections (that we also call weakenings ) are given as follows: \pi_{a_{i}}=\langle\alpha;\textsf{id}_{a_{i}}\rangle:\langle a_{1},a_{2}\rangle\to\langle a_{i}\rangle where \alpha:[1]\to[2] maps 1 to 1 . We denote as \mathtt{T}_{\vec{a}}:\vec{a}\to\langle\rangle the terminal morphism. Given sequences of lists \gamma=\vec{a}_{1},\dots,\vec{a}_{n} and \delta=\vec{b}_{1},\dots,\vec{b}_{n} we define their tensor product as pointwise list concatenation: \gamma\otimes\delta=\vec{a}_{1}\oplus\vec{b}_{1},\dots,\vec{a}_{n}\oplus\vec{b}_{n}. Typing contexts in our system will consist of sequences of lists. The tensor product between them will model context concatenation. The ground morphism induced by \gamma=\vec{a}_{1},\dots,\vec{a}_{n} consists of the sequence of ground morphisms of \vec{a}_{i} . Abusing the notation, we will use greek letters to denote also ground morphisms induced by sequences. Remark 1 . Consider the morphism on lists \langle\alpha;\vec{f}\rangle=\langle\alpha;f_{1},\dots,f_{l}\rangle:\vec{a}=\langle a_{1},\dots,a_{k}\rangle\to\vec{b}=\langle b_{1},\dots,b_{l}\rangle. By definition, we have that f_{i}:a_{\alpha(i)}\to b_{i} with i\in[l]. We remark that we can always factorize \langle\alpha;f_{1},\dots,f_{l}\rangle as follows: \langle\alpha;\vec{f}\rangle=\vec{f}\circ\alpha_{\vec{a}} with \vec{f}:\vec{a}^{[\alpha]}\to\vec{b} and \alpha_{\vec{a}}:\vec{a}\to\vec{a}^{[\alpha]} , defined as \alpha_{\vec{a}}=\langle\alpha;\textsf{id}_{a_{\alpha(1)}},\dots,\textsf{id}_{a_{\alpha(l)}}\rangle and \vec{f}=\langle\textsf{id};f_{1},\dots,f_{l}\rangle. We call \alpha_{\vec{a}} the ground fragment of \langle\alpha;\vec{f}\rangle , denoted as \mathsf{ground}(\langle\alpha;\vec{f}\rangle) and \vec{f} the nested fragment of it, denoted as \mathsf{nest}(\langle\alpha;\vec{f}\rangle) . We can extend the factorization to sequences of morphisms \theta=\langle\alpha_{1};\vec{f}_{1}\rangle,\dots,\langle\alpha_{n};\vec{f}_{n}\rangle in the natural way. 3.3 Labelled Transition Systems In the rewriting systems we deal with in this paper, reduction steps are labeled . A labelled reduction system consists of a labelled transition system \mathsf{R}=(\Lambda,\mathbb{S},\to) whose labels form a partial monoid \mathbb{S}=(S,\cdot,1). 1 1 1 We consider partial monoids because the labels of our rewriting systems will be morphisms in appropriate categories of types, where the monoidal product we want to consider is the composition of those morphisms. Given a labelled reduction system \mathsf{R}=(\Lambda,(S,\cdot,1),\to) , we abuse the notation by also writing s\to s^{\prime} to denote the relation \to\subseteq\Lambda\times\Lambda s.t. s\to s^{\prime} when there exists l\in S with s\to_{l}s^{\prime} . Given a labelled reduction system \mathsf{R}=(\Lambda,(S,\cdot,1),\to) , we say that \mathsf{R} is normalizing when, given s\in\Lambda, there exists a reduction sequence s=s_{0}\to s_{1}\to\dots\to s_{n} such that s_{n}\nrightarrow , and in this case we call s_{n} a normal form of s . We say that \mathsf{R} is strongly normalizing (or terminating ) when it is impossible to form an infinite reduction sequence s_{0}\to s_{1}\to s_{2}\to\ldots Definition 1 (Reflexive and Transitive Extension) . Let \mathsf{R}=(\Lambda,(S,\cdot,1),\to) be a labelled reduction system. We can thus build its transitive and reflexive extension \mathsf{R}^{\ast}=(\Lambda,(S,\cdot,1),\to^{\ast}) where \to^{\ast} is defined inductively by the following rules: s\to_{h}t t\to^{\ast}_{l}v l\cdot h\downarrow s\to^{\ast}_{l\cdot h}v s\to_{1}^{\ast}s Definition 2 (Labelled Confluence) . Let \mathsf{R}=(\Lambda,(S,\cdot,1),\to) be a labelled reduction system. We say that \mathsf{R} enjoys confluence if whenever t_{1}\prescript{\ast}{l_{1}}{\leftarrow}\;s\to_{l_{2}}^{\ast}t_{2} there exist h_{1},h_{2}\in S and u\in\Lambda such that t_{1}\to_{h_{1}}^{\ast}u\;\prescript{\ast}{h_{2}}{\leftarrow}t_{2} with h_{1}\cdot f_{1}=h_{2}\cdot f_{2} . If the hypothesis becomes t_{1}\prescript{}{l_{1}}{\leftarrow}\;s\to_{l_{2}}t_{2} , we say \mathsf{R} is locally confluent . The well-known Newman Lemma continues to hold even in presence of labels: local confluence together with strong normalization imply confluence, something which can be proved exactly as for abstract reduction systems [ Terese03 ] . 4 Types and Morphisms Intersection types are often defined equationally : the intersection type constructor a\cap b is given as a monoidal product satisfying some equations: associativity, commutativity and possibly idempotency. In this paper, we take a more refined viewpoint: the intersection connective is still a strictly associative tensor product, but we replace equations by concrete operations on types. For instance, commutativity is replaced by appropriate symmetries \sigma_{a,b}:a\cap b\to b\cap a. Idempotency becomes a copying operation c_{a}:a\to a\cap a. In order to formalize this idea, we identify the intersection type a_{1}\cap\cdots\cap a_{k} with the list \langle a_{1},\dots,a_{k}\rangle. Operations on intersection types become then structural operations on lists, seen as a categorical tensor product (see Section 3 ). Moreover, intersection types will appear on the left side of an application \langle a_{1},\dots,a_{k}\rangle\multimap a only, following the well-established tradition of strict intersection types [ bakel:strict ] . This allows us to define a syntax-directed type system. We define the set of resource types ( \mathcal{RT} ) and the set of intersection types ( \oc(\mathcal{RT}) ) by the following inductive grammar: \displaystyle\mathcal{RT} \displaystyle\ni a,b::=o\mid\vec{a}\multimap a \displaystyle\oc(\mathcal{RT}) \displaystyle\ni\vec{a}::=\langle a_{1},\dots,a_{k}\rangle\qquad(k\in\mathbb{N}) We define a notion of morphism of resource types by induction in Figure , parametrically on \spadesuit\in\{l,c\} . Morphisms of resource types can be seen as proof-relevant subtyping . Composition and identities of these morphisms are defined by induction in a natural way, exploiting the definition of composition induced by the \oc^{\spadesuit}(-) construction. Composition is associative and unitary. We can then define a category \mathcal{RT}^{\spadesuit}. \mathcal{RT}^{l} (resp. \mathcal{RT}^{c} ) is said to be the category of linear (resp. cartesian ) resource types in which objects are resource types and morphisms are linear (resp. cartesian ) morphisms of resource types. We remark that the inclusion of categories \mathbb{O}_{f}^{l}\hookrightarrow\mathbb{O}_{f}^{c} induces an inclusion \mathcal{RT}^{l}\hookrightarrow\mathcal{RT}^{c}. We will often denote the identity morphism \textsf{id}_{a}:a\to a by the type a itself, e.g., \vec{a}\multimap a:=\textsf{id}_{\vec{a}}\multimap\textsf{id}_{a}. Example 2 . We have a morphism (\langle o,o,\langle o\rangle\multimap o\rangle\multimap o)\to(\langle o,\langle o\rangle\multimap o\rangle\multimap o) in the category of cartesian resource types. The morphism is built out of c_{o}:\langle o\rangle\to\langle o,o\rangle , used in a contravariant way, since the intersection type is in negative position. 5 Resource Terms We now introduce the structural resource \lambda -calculus , which can be thought of as a non-uniform counterpart to the standard simply-typed \lambda -calculus in which the structural operations are kept explicit . Non-uniformity stems from the application rule, whereas a function can be applied to bags ( i.e. , lists) of inputs of non-uniform shape and type: e.g. , given a function s , we apply it to a list of arguments obtaining s\langle t_{1},\dots,t_{k}\rangle , where t_{1},\dots,t_{k} are arbitrary terms. In this way, our calculus becomes a refinement of both Boudol’s [ Boudol93 ] and Ehrhard and Regnier’s [ EhrhardRegnier08 ] resource calculi. The main difference is that we replace multisets of arguments with lists , making the operational semantics completely deterministic. In doing so, we build on several previous proposals [ tao:gen , mazza:pol , ol:group ] where resource calculi based on lists are considered. The novelty of our approach relies on the treatment of structural rules . The calculus is built in such a way as to separate the structural (and in particular exponential , in the sense of linear logic) side of \beta -reduction from the actual substitution operation, which remains linear. Definition 3 (Structural Resource Terms) . We fix a countable set of variables \mathcal{V} . We define the set of structural resource terms ( \Lambda_{r}^{\spadesuit} ) by the following inductive grammar, parametrically over \spadesuit\in\{l,c\} \Lambda_{r}^{\spadesuit}\ni s::=x\in\mathcal{V}\mid\lambda x^{f}.s\mid s\vec{t}\qquad\qquad\vec{t}\in\oc(\Lambda_{r}^{\spadesuit}) where f\in\text{hom}(\mathcal{RT}^{\spadesuit}) . Resource terms are considered up to renaming of bound variables. Elements of \oc(\Lambda_{r}^{\spadesuit}) are called bags of resource terms. Typing contexts, consisting of sequences of variable type declariations, are defined in Figure . A morphism of typing contexts consists of a sequence of morphisms between intersection types. Typing contexts and their morphisms determine a category that we denote as \mathsf{Ctx}^{\spadesuit} . Terms are considered up to renaming of bound variables. The tensor product of contexts consists of the pairwise concatenation of intersection types assigned to the same variable. Typing rules are given in Figure . Typing contexts in multiple-hypothesis rules are always assumed to be joinable, i.e. , they contain the same free variables. The type system admits two kinds of judgments: namely \vdash and \vdash_{b} . The former infers the typing of resource terms; the latter that of bags of resource terms. We note that bags of resource terms are typed with intersection types and they are not formally a part of the grammar of resource terms. Given a context of the shape x_{1}:\langle\rangle,\dots,x:\vec{a},\dots,x_{n}:\langle\rangle we shall often abuse the language and just denote it by \langle\alpha;\vec{f}\rangle . The main novelty of the structural resource calculus is the typing of abstractions: whenever we bound variables, we are allowed to decorate them with morphisms of intersection types. These morphisms express the (nested) structural rules that we are allowing on (the occurrences of) the considered bound variables. Remark 2 . The annotation of bound variables in a term like \lambda x^{f}.s intuitively retains the information about the (nested) structural operations being performed on the occurrences of the variable x . For instance, in the term s=\lambda x^{c_{o}}.v\langle x,x\rangle , where c_{o}:\langle o\rangle\to\langle o,o\rangle , we are performing a contraction on the two occurrences of x . Thus, if we take a term t of type o and apply it to s , it will be duplicated along the computation. This means that our reduction semantics should allow for s\langle t\rangle\to v\langle t,t\rangle . In the cartesian world, any structural operation is allowed; for example, we also have weakenings: \lambda x^{\mathsf{T}_{o}}z . In the linear world, however, the only allowed operations are permutations . Example 3 (Typing Some Resource Terms) . Consider the ground morphism \alpha=(\langle\langle o\rangle\multimap o\rangle\otimes c_{o}):\langle\langle o,o\rangle\multimap o,o\rangle\to\langle\langle o,o\rangle\multimap o,o,o\rangle, which performs a contraction on the type o while keeping the arrow type fixed. We can type the term \lambda x^{\alpha}.x\langle x,x\rangle as \vdash\lambda x^{\alpha}.x\langle x,x\rangle:\langle\langle o,o\rangle\multimap o,o\rangle\multimap o. Our system induces a strong correspondence between typed terms and their type derivations, as witnessed by the following result. Proposition 1 (Uniqueness of Derivations) . Let \pi be a derivation of \gamma\vdash s:a and \pi^{\prime} of \gamma\vdash s:a^{\prime} . Then a=a^{\prime} and \pi=\pi^{\prime} . Thanks to this result, we can just work with typed terms \gamma\vdash s:a , without the need of always explicitly referring to the whole type derivation.