dataesr/scientific-paragraphs-categorization huggingface dataset:
The interesting part of the interface is the interaction of this type parameter with the following function runST :: (∀ β. ST β α ) → α The runST function runs effectful computations and extracts the result from the ST monad. Notice the impredicative quantification of the type variable of runST. Finally, equality on references is decidable: (==) :: STRef β α → STRef β α → bool Notice that equality is an ordinary function, since it returns a boolean value directly, not a value of type ST β bool. Figure  1  shows how to compute the n-th term of the Fibonacci sequence in Haskell using the ST monad and, for comparison, in our model language STLang. Haskell programmers will notice that the STLang program on the right is essentially the same as the one on the left after the do-notation has been expanded.
Moreover, if e has type ∀β. ST β τ , with β not free in τ , the intuition is that runST e can allocate a fresh region, which e may use and then, since β is not free in τ , the resulting value of type τ cannot involve references in the region β. It is therefore safe to discard the region β and return the value of type τ. Since stateful computations intuitively are encapsulated in this way, this should also entail that the rest of the "pure" language indeed remains pure. For example, it should still be the case that for an expression e of type τ , running e twice should be the same as running it once. More precisely, we would expect the following contextual equivalence to hold for any expression e of type τ : let x = e in (x, x) ≈ ctx (e, e) ( * ) Note that, of course, this contextual equivalence would not hold in the presence of unrestricted side effects as in ML: if e is the expression y := !y + 1, which increments the reference y, then the reference would be incremented by 1 on the left hand-side of ( * ) and by 2 on the right.
Similar kinds of contextual equivalences and refinements that we expect should hold for a pure language should also continue to hold. Moreover, we also expect that the State-Independence theorem described above should hold. Notice that this intuitive explanation is just a conceptual model -the real implementation of the language uses a standard global heap with in-place update and the challenge is to prove that the type system still enforces this intended proper encapsulation of effects. In this paper, we provide a solution to this challenge: we define a higher-order functional programming language, called STLang, with impredicative polymorphism, recursive types, and a Haskell-style ST monad type with runST. The operational semantics uses a global mutable heap for stateful operations. We develop a logical relations model which we use to prove contextual refinements and equivalences that one expects should hold for a pure language in the presence of stateful computations encapsulated using runST.
Overview of Results and the Technical Development In §2 we present the operational semantics and the type system for our language STLang. In this paper, we focus on the encapsulation properties of a Haskell-style monadic type system for stateful computations. The choice of evaluation order is an orthogonal issue and, for simplicity (to avoid having to formalize a lazy operational semantics), we use call-by-value left-to-right evaluation order. Typing judgments take the standard form Ξ | Γ ⊢ e : τ , where Ξ is an environment of type variables, Γ an environment associating types to variables, e is an expression, and τ is a type. For well-typed expressions e and e ′ we define contextual refinement, denoted Ξ | Γ ⊨ e ⪯ ctx e ′ : τ. As usual, e and e ′ are contextually equivalent, denoted Ξ | Γ ⊨ e ≈ ctx e ′ : τ , if e contextually refines e ′ and vice versa.
With this in place, we can explain which contextual refinements and equivalences we prove for STLang. The soundness of these refinements and equivalences means, of course, that one can use them when reasoning about program equivalences. The contextual refinements and equivalences that we prove for pure computations are given in Figure  2. To simplify the notation, we have omitted environments Ξ and Γ in the refinements and equivalences in the Figure. Moreover, we do not include assumptions on typing of subexpressions in the Figure ; precise formal results are stated in §4. Refinement (Neutrality) expresses that a computation of unit type either diverges or produces the unit value. The contextual equivalence in (Commutativity) says that the order of evaluation e ⪯ ctx () : 1 (Neutrality) let x = e 2 in (e 1 , x) ≈ ctx (e 1 , e 2 ) : τ 1 × τ 2 (Commutativity) let x = e in (x, x) ≈ ctx (e, e) : τ × τ (Idempotency) let y = e 1 in rec f (x) = e 2 ⪯ ctx rec f (x) = let y = e 1 in e 2 : τ 1 → τ 2 (Rec hoisting) let y = e 1 in Λ e 2 ⪯ ctx Λ (let y = e 1 in e 2 ) : ∀X.
The contextual refinements (β reduction for rec) and (β reduction for Λ) express the soundness of β-rules for ordinary recursive functions and for type functions. In addition, we prove the expected contextual equivalences for monadic computations, shown in Figure  3. bind e in (λ x. return x) ≈ ctx e : ST ρ τ (Left Identity) e 2 e 1 ⪯ ctx bind (return e 1 ) in e 2 : ST ρ τ (Right Identity) bind (bind e 1 in e 2 ) in e 3 ⪯ ctx bind e 1 in (λ x. bind (e 2 x) in e 3 ) : ST ρ τ ′ (Associativity) The results in Figure  2  are the kind of results one would expect for pure computations in a callby-value language; the challenge is, of course, to show that they hold in the full STLang language, that is, also when subexpressions may involve arbitrary (possibly nested) stateful computations encapsulated using runST.
Summary of contributions. To sum up, the main contributions of this paper are as follows: • We present a logical relation for a programming language STLang featuring a parallel to Haskell's ST monad with a construct, runST, to encapsulate stateful computations. We use our logical relation to prove that runST provides proper encapsulation of state, by showing (1) that contextual refinements and equivalences that are expected to hold for pure computations do indeed hold in the presence of stateful computations encapsulated via runST and (2) that the State-Independence theorem holds. This is the first time that these results have been established for a programming language with an operational semantics that uses a single global higher-order heap with in-place destructive updates. • We define our logical relation in Iris, a state-of-the-art higher-order separation logic designed for program verification, using a new approach involving novel predicates defined in Iris, which we explain in §5.
THE STLang LANGUAGE In this section, we present STLang, a higher-order functional programming language with impredicative polymorphism, recursive types, higher-order store and a ST-like type. Syntax. The syntax of STLang is mostly standard and presented in Figure  4. Note that there are no types in the terms; following  [Ahmed 2006 ] we write Λ e for type abstraction and e _ for type application / instantiation. For the stateful part of the language, we use return and bind for the return and bind operations of the ST monad, and ref(e) creates a new reference, !e reads from one and e ← e writes into one. Finally, runST runs effectful computations. Note that we treat the stateful operations as constructs in the language rather than as special constants. Typing. Typing judgments are of the form Ξ | Γ ⊢ e : τ , where Ξ is a set of type variables, and Γ is a finite partial function from variables to types.
runST. This is why we define an auxiliary reduction relation, ⟨h, e⟩ ⟨h ′ , e ′ ⟩. This auxiliary relation is also defined using a head reduction and evaluation contexts K, which are distinct from the evaluation contexts for the main reduction relation. This auxiliary relation in "embedded" in the main one by the rule ⟨h, v⟩ ⟨h ′ , e⟩ ⟨h, runST {v}⟩ → h ⟨h ′ , runST {e}⟩ Notice that always reduces from a value: this is because values of type ST can be seen as "frozen" computations, until they appear inside a runST. The expression e on the right hand-side of the rule above can be a reducible expression, which is reduced by using K = runST{[]} as a context for the main reduction rule →. This operational semantics is new, therefore we include an example of how a simple program reduces. The program initializes a reference r to 3, then writes 7 into r and finally reads r.
Definition of the Logical Relation We now have enough logical machinery to describe the logical relation (pedantically, it is a family of logical relations) shown in Figure  7. The logical relation is a binary relation, which allows us to relate pairs of expressions and pairs of values to each other. We will show that if two expressions are related in the logical relation, then the left hand side expression contextually approximates the right hand side expression. Therefore, we sometimes refer to the the left hand side as the implementation and the right hand side as the specification. The value relation Ξ ⊢ τ ∆ is an Iris relation of type (Val × Val) → iProp and, intuitively, it relates STLang values of type τ. The value relation is defined by induction on the type τ. Here, Ξ is an environment of type variables, and ∆ is a semantic environment for these type variables, as is usual for languages with parametric polymorphism  [Reynolds 1983 ].
2017a ] allows us to prove the soundness of our logical relation: Extending Iris and IPM and instantiating them with STLang. The implementations of Iris and IPM in Coq are almost entirely independent of the choice of programming language. In practice, the only definitions that are parameterized by a language are the definitions of weakest-precondition and Hoare triples. To use these with a particular programming language, one needs to instantiate a data structure in Coq that represents the language. Basically, one is required to instantiate this data structure with the language's set of states (heaps in our case), expressions, values and reduction relation, together with proofs that they behave as expected (e. g. , values do not reduce any further). In this work we use IC predicates and IC triples instead of the weakest precondition and Hoare triples used in earlier work.
Therefore, we have also parameterized IC predicates and IC triples by a data structure representing the programming language. We instantiate these with STLang. The formalization of Iris in Coq is a shallow embedding. That is, the model of the Iris logic is formalized in Coq, and terms of the type iProp (propositions of Iris) are defined as well-behaved predicates over the elements of that model. The advantage of shallow embeddings is that one can easily introduce new connectives and modalities to the logic by defining another function with iProp as co-domain. For instance, our IC predicate is defined as follows in Coq. Definition ic__def {Λ Σ} `{ICState Λ, ICG Λ Σ} γ E e Φ : iProp Σ := (∀ σ1 σ2 v n, (⌜nsteps pstep n (e, σ1) (of__val v, σ2)⌝ * ownP__full γ σ1) - * |≫{E}=[n]=> Φ v n * ownP__full γ σ2)%I.
Here, ⌜ • ⌝ embeds Coq propositions into Iris and ownP__full γ σ is the full ownership of the physical state of the language (parameter Λ), equivalent to our heap γ (σ ). The %I at the end instructs Coq to parse connectives (e. g. , the universal quantification) as Iris connectives and not those of Coq. As discussed in  [Krebbers et al. 2017b ], IPM tactics, like the iMod tactic for elimination of modalities, simply apply lemmas with side conditions that are discharged with the help of Coq's type class inference mechanism. Extending IPM with support for the future modality and IC predicates essentially boils down to instantiating some of these type classes appropriately. Representing binders. We use de Bruijn indices to represent variables both at the term level and the type level; in particular, we use the Autosubst library  [Schäfer et al.
RELATED WORK The most closely related work is the original seminal work of  Launchbury and Peyton Jones [1994] , which we discussed and related to in the Introduction. In this section we discuss other related work. Moggi and Sabry [2001]  showed type soundness of calculi with runST-like constructs, both for a call-by-value language (as we consider here) and for a lazy language. The type soundness results were shown with respect to operational semantics in which memory is divided into regions: a runST-encapsulated computation always start out in an empty heap and the final heap of such a computation is thrown away. Thus their type soundness result does capture some aspects of encapsulation. However, the models in loc. cit. are not relational and therefore not suitable for proving relational statements such as our theorems above.
The authors write: "Indeed substantially more work is needed to establish soundness of equational reasoning with respect to our dynamic semantics (even for something as unsurprising as β-equivalence)"  [Moggi and Sabry 2001]. In contrast to  Moggi and Sabry [2001] , who also considered type soundness for a call-by-need language, we only develop our model for a call-by-value language. For call-by-need one would need to keep track of the dependencies between effectful operations in the operational semantics and only evaluate them if they contribute to the end result. These dependencies would also have to be reflected in the logical relations model. It is not clear how difficult that would be and we believe it deserves further investigation. It was pointed out already in  [Launchbury and Peyton Jones 1994]  that there seems to be a connection between encapsulation using runST and effect masking in type-and-effect systems à la  Gifford and Lucassen [1986].
This connection was formalized by  Semmelroth and Sabry [1999] , who showed how a language with a simplified type-and-effect system with effect masking can be translated into a language with runST. Moreover, they showed type soundness on their language with runST with respect to an operational semantics. In contrast to our work, they did not investigate relational properties such as contextual refinement or equivalence. Benton et al. have investigated contextual refinement and equivalence for type-and-effect systems in a series of papers  [Benton and Buchlovsky 2007; Benton et al. 2007 Benton et al. , 2009 Benton et al. , 2006] ]  and their work was extended by  Thamsborg and Birkedal [2011]  to a language with higher-order store, dynamic allocation and effect masking. These papers considered soundness of some of the contextual refinements and equivalences for pure computations that we have also considered in this paper, but, of course, with very different assumptions, since the type systems in loc.
cit. were type-and-effect systems. Thus, as an alternative to the approach taken in this paper, one could also imagine trying to prove contextual equivalences in the presence of runST by translating the type system into the language with type-and-effects used in  [Thamsborg and Birkedal 2011]  and then appeal to the equivalences proved there. We doubt, however, that such an alternative approach would be easier or better in any way. The logical relation that we define in this paper uses an abstraction of regions and relates regions to the concrete global heap used in the operational semantics. At a very high level, this is similar to the way regions are used as an abstraction in the models for type-and-effect systems, e. g. , in  [Thamsborg and Birkedal 2011]. However, since the models are for different type systems, they are, of course, very different in detail.
CONCLUSION AND FUTURE WORK We have presented a logical relations model of STLang, a higher-order functional programming language with impredicative polymorphism, recursive types, and a Haskell-style ST monad type with runST. To the best of our knowledge, this is the first model which can be used to show that runST provides proper encapsulation of state, in the sense that a number of contextual refinements and equivalences that are expected to hold for pure computations do indeed hold in the presence of stateful computations encapsulated using runST. We defined our logical relation in Iris, a state-ofthe-art program logic. This greatly simplified the construction of the logical relation, e. g. , because we could use Iris's features to deal with the well-known type-world circularity. Moreover, it provided us with a powerful logic to reason in the model.
ACKNOWLEDGMENTS The last author would like to thank  Georg Neis  for early discussions about the topic of this paper. We would like to thank the anonymous referees for their invaluable constructive comments. This research was supported in part by the  ModuRes Sapere Aude  Advanced Grant from The  Danish Council for Independent Research for the Natural Sciences (FNU) , by the  EUTypes funding ECOST- STSM-CA15123-150816-080859  and by the  Flemish Research Fund  grants  G. 0058. 13  (until June 2017) and G. 0962. 17N (since July 2017).
From phylogenetics to phylogenomics The last two decades have seen significant changes taking place in the practice of phylogenetic inference from molecular data. These changes have mostly been triggered by the ever-increasing size of the datasets being assembled and analysed in the form of supermatrices of concatenated genes  (Driskell et al. 2004 ). The evolution of the size and shape of these datasets, thanks to new technological advances in DNA amplification and sequencing, has been associated with different phases in the field of phylogenetic inference (Fig. 1 ). In the early days of molecular phylogenetics based on PCR amplification and manual Sanger sequencing of a handful of genes for a limited number of taxa, the field laid somewhat in the "uncertainty zone" dominated by stochastic error, even if some naïve over-interpretations did occur.
Finally, the development of genomics and transcriptomics (and more recently of high-throughput or next-generation sequencing technologies) allowed the field to enter an "optimal zone" by offering the opportunity to assemble phylogenomic datasets representing a good compromise between taxon and gene sampling and typically constituted by hundreds of genes for tens of taxa. However, the tempting up-scaling along these two axes resulted in an "overflow zone", where missing data steadily increase and computing requirements explode at all stages of the analysis (Fig. 1 ). In the mid-2000s, multigene phylogenetics therefore turned into phylogenomics  (Delsuc et al. 2005; Philippe et al. 2005a). As with the beginnings of molecular phylogenetics, the early days of phylogenomics (i. e. , the use of genome-scale data to infer phylogenetic relationships) started with a wave of optimism.
2004; Soltis et al. 2004; Jeffroy et al. 2006). First, genuine topological incongruence, i. e. , statistically supported contradictions, is in fact extremely rare when phylogenies are inferred from a limited set of characters, since stochastic error dominates in this case (this does not mean that weakly supported incongruences are not real, in particular these created by incomplete lineage sorting, and deserve consideration, see below). Second, systematic error naturally becomes more apparent at the genomic scale, simply, as a typical example of statistical inconsistency, in which the inference method converges towards an incorrect solution as more and more data are analysed. As a result, phylogenomics rather was "the beginning of incongruence" among studies based on different datasets and (especially) inference methods  (Jeffroy et al.
1. Evolution of phylogenetic reconstruction over time. Different zones can be delimited based on the number of genes (X axis) and number of taxa (Y axis) composing the supermatrix at hand. Generally speaking, the (upper) left part of the map has more to do with identifying species (as in barcoding studies), while the right part of the map corresponds to multigene and phylogenomic datasets assembled for recovering large-scale phylogenetic relationships. Each of these zones suffers from its own combination of issues (stochastic error, systematic error, data errors, computational requirements and missing data). Interestingly, the "optimal zone" in phylogenomics is not the one corresponding to the highest number of genes and taxa, because this computationally "intractable zone" is also the one where data errors and missing data are the most abundant.
The latter aspect is due to the continuous shrinking of the number of orthologous genes when considering increasingly more species, owing to gene loss, gene duplication and gene transfer events. phylogenies and should have been accompanied, as expected by some, by a decrease in systematic error obtained through efforts in improving inference methods. Unfortunately, it appears that genome-scale analyses also lead to the amplification of data errors, i. e. , errors that occurred during the construction of the datasets  (Philippe et al. 2011b; Laurin-Lemay et al. 2012). This is due to the fact that the flood of genomic data (often of decreasing quality) has become intractable for manual controls, while few bioinformatics tools have yet been adapted to the complexity of the genomic scale. In this paper, we discuss major pitfalls of phylogenomics and ways to limit their impact on phylogenetic inference.
Effects of data errors Single-gene and small multigene datasets could easily be curated thoroughly by hand, allowing researchers to remove almost all major errors before analysis and publication. The few remaining errors were often due to contaminations in the case of organisms that were difficult to make axenic  (Pawlowski et al. 1996; Bourlat et al. 2003). Of course, due to the limitations of ancient sequencing technologies, sequencing errors were frequent and sequence quality was quite variable in these early datasets. Highthroughput sequencing has greatly improved sequence quality, mainly through the large coverage of each nucleotide, but has simultaneously flooded researchers with an amount of data that is difficult, if not impossible, to handle by hand. While numerous custom scripts have been independently written to manage this deluge of data, there is currently no agreement in the community regarding the quality controls that should be implemented in phylogenomic dataset construction.
More problematically, the practice of phylogenetic research has continued at the genomic scale with more or less the same approaches as those used at the single-gene and small multigene scales. In order to illustrate data errors and their consequences for phylogenomic inference, we will explore three example datasets  (Dunn et al. 2008; Schierwater et al. 2009; Finet et al. 2010 ) that were carefully verified after their original publication  (Philippe et al. 2011b; Laurin-Lemay et al. 2012). The most frequent errors observed in the protein-coding genes of these datasets are frameshifts and contaminant sequences. Frameshifts are primarily due to sequencing errors (especially for transcriptomic data) and annotation errors (especially for genomic data). Sequence contamination occurred at the sampling step (i.
Given the large size of phylogenomic alignments, non-phylogenetic signal should be overwhelmed by the wealth of genuine phylogenetic signal. To test this hypothesis, we introduced contaminant sequences into a large supermatrix (30 517 positions and 48 species) and observed that phylogenetic inference is indeed relatively robust to such errors (unpublished results): when contamination was below 4%, at most 4 partitions were incorrect (on average ~2 for 3%). As expected, all clades with a relatively long ancestral branch were accurately recovered. This demonstrates that obtaining a phylogenomic tree in good global agreement with previous knowledge does not imply that the underlying dataset is errorfree. In contrast, clades with a short ancestral branch appear to be very sensitive to computationally introduced contaminations, whereas such clades are the very target of phylogenomics, smaller-scale approaches having insufficient statistical power to resolve them.