Зміст
Добірка наукової літератури з теми "Inductive types"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся зі списками актуальних статей, книг, дисертацій, тез та інших наукових джерел на тему "Inductive types".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Дисертації з теми "Inductive types"
1
Bruin, Peter Johan de. "Inductive types in constructive languages." [S.l. : [Groningen] : s.n.] ; [University Library Groningen] [Host], 1995. http://irs.ub.rug.nl/ppn/128570415.
Повний текст джерела
2
Grimley, Allan. "Inductive types in functional programming." Thesis, University of Kent, 1990. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.253737.
Повний текст джерела
3
Kaposi, Ambrus. "Type theory in a type theory with quotient inductive types." Thesis, University of Nottingham, 2017. http://eprints.nottingham.ac.uk/41385/.
Повний текст джерелаАнотація:
Type theory (with dependent types) was introduced by Per Martin-Löf with the intention of providing a foundation for constructive mathematics. A part of constructive mathematics is type theory itself, hence we should be able to say what type theory is using the formal language of type theory. In addition, metatheoretic properties of type theory such as normalisation should be provable in type theory. The usual way of defining type theory formally is by starting with an inductive definition of precontexts, pretypes and preterms and as a second step defining a ternary typing relation over these three components. Well-typed terms are those preterms for which there exists a precontext and pretype such that the relation holds. However, if we use the rich metalanguage of type theory to talk about type theory, we can define well-typed terms directly as an inductive family indexed over contexts and types. We believe that this latter approach is closer to the spirit of type theory where objects come intrinsically with their types. Internalising a type theory with dependent types is challenging because of the mutual definitions of types, terms, substitution of terms and the conversion relation. We use induction induction to express this mutual dependency. Furthermore, to reduce the type-theoretic boilerplate needed for reasoning in the syntax, we encode the conversion relation as the equality type of the syntax. We use equality constructors thus we define the syntax as a quotient inductive type (a special case of higher inductive types from homotopy type theory). We define the syntax of a basic type theory with dependent function space, a base type and a family over the base type as a quotient inductive inductive type. The definition of the syntax comes with a notion of model and an eliminator: whenever one is able to define a model, the eliminator provides a function from the syntax to the model. We show that this method of representing type theory is practically feasible by defining a number of models: the standard model, the logical predicate interpretation for parametricity (as a syntactic translation) and the proof-relevant presheaf logical predicate interpretation. By extending the latter with a quote function back into the syntax, we prove normalisation for type theory. This can be seen as a proof of normalisation by evaluation. Internalising the syntax of type theory is not only of theoretical interest. It opens the possibility of type-theoretic metaprogramming in a type-safe way. This could be used for generic programming in type theory and to implement extensions of type theory which are justified by models such as guarded type theory or homotopy type theory.
4
Altenkirch, Thorsten. "Constructions, inductive types and strong normalization." Thesis, University of Edinburgh, 1993. http://hdl.handle.net/1842/11967.
Повний текст джерелаАнотація:
This thesis contains an investigation of Coquand's Calculus of Construction, a basic impredicative Type Theory. We review syntactic properties of the calculus, in particular decidability of equality and type-checking, based on the equality-as-judgement presentation. We present a set-theoretic notion of model, CC-structures, and use this to give a new strong normalisation proof based on a modification of the realizability interpretation. An extension of the core calculus by inductive types is investigated and we show, using the example of infinite trees, how the realizability semantics and the strong normalisation argument can be extended to non-algebraic inductive types. We emphasise that our interpretation is sound for <I>large eliminations</I>, e.g. allows the definition of sets by recursion. Finally we apply the extended calculus to a non-trivial problem: the formalization of the strong normalisation argument for Girard's System F. This formal proof has been developed and checked using the LEGO system, which has been implemented by Randy Pollack. We include the LEGO files in the appendix.
5
Pavaux, Alice. "Inductive, Functional and Non-Linear Types in Ludics." Thesis, Sorbonne Paris Cité, 2017. http://www.theses.fr/2017USPCD092.
Повний текст джерелаАнотація:
Cette thèse est consacrée à une exploration des types de la ludique. S’inscrivant dans un contexte marqué par la correspondance de Curry–Howard, la ludique est un cadre permettant d’étudier l’aspect dynamique de la logique et de la programmation. Les objets de base, appelés desseins, sont des preuves infinitaires non-typées qui peuvent également être vues comme des stratégies sous l’angle de la sémantique des jeux, et un type ou comportement est un ensemble de desseins se conduisant de la même manière du point de vue de l’interaction. On s’intéresse aux propriétés interactives des comportements. Notre attention se porte en particulier sur les comportements représentant les types de données et de fonctions, et sur les comportements non-linéaires qui permettent la duplication d’objets. Un nouveau résultat de complétude interne pour les unions infinies dévoile la structure des types de données inductifs. Grâce à une analyse des chemins visitables,c’est-à-dire des possibles traces d’exécution, on prouve que les comportements inductifs et fonctionnels sont réguliers, ouvrant la voie pour une caractérisation de MALL en ludique. On montre également qu’un comportement fonctionnel est pur, une propriété garantissant la sûreté du typage, si et seulement si ce n’est pas un type de fonctions prenant des fonctions en argument. Enfin, on pose les bases d’une étude précise de la non-linéarité en ludique en retrouvant une forme de complétude interne et en discutant des chemins visitables<br>This thesis investigates the types of ludics. Within the context of the Curry–Howard correspondence,l udics is a framework in which the dynamic aspects of both logic and programming can be studied. The basic objects, called designs, are untyped infinitary proofs that can also beseen as strategies from the perspective of game semantics, and a type or behaviour is a set of designs well-behaved with respect to interaction. We are interested in observing the interactive properties of behaviours. Our attention is particularly focused on behaviours representing the types of data and functions, and on non-linear behaviours which allow the duplication of objects. A new internal completeness result for infinite unions unveils the structure of inductive data types. Thanks to an analysis of the visitable paths, i.e., the possible execution traces, we prove that inductive and functional behaviours are regular, paving the way for a characterisation of MALL in ludics. We also show that a functional behaviour is pure, a property ensuring the safety of typing, if and only if it is not a type of functions taking functions as argument. Finally,we set the bases for a precise study of non-linearity in ludics by recovering a form of internal completeness and discussing the visitable paths
6
Ko, Hsiang-Shang. "Analysis and synthesis of inductive families." Thesis, University of Oxford, 2014. http://ora.ox.ac.uk/objects/uuid:2bc39bde-ce59-4a49-b499-3afdf174bbab.
Повний текст джерелаАнотація:
Based on a natural unification of logic and computation, Martin-Löf’s intuitionistic type theory can be regarded simultaneously as a computationally meaningful higher-order logic system and an expressively typed functional programming language, in which proofs and programs are treated as the same entities. Two modes of programming can then be distinguished: in externalism, we construct a program separately from its correctness proof with respect to a given specification, whereas in internalism, we encode the specification in a sophisticated type such that any program inhabiting the type also encodes a correctness proof, and we can use type information as a guidance on program construction. Internalism is particularly effective in the presence of inductive families, whose design can have a strong influence on program structure. Techniques and mechanisms for facilitating internalist programming are still lacking, however. This dissertation proposes that internalist programming can be facilitated by exploiting an interconnection between internalism and externalism, expressed as isomorphisms between inductive families into which data structure invariants are encoded and their simpler variants paired with predicates expressing those invariants. The interconnection has two directions: one analysing inductive families into simpler variants and predicates, and the other synthesising inductive families from simpler variants and specific predicates. They respectively give rise to two applications, one achieving a modular structure of internalist libraries, and the other bridging internalist programming with relational specifications and program derivation. The datatype-generic mechanisms supporting the applications are based on McBride’s ornaments. Theoretically, the key ornamental constructs — parallel composition of ornaments and relational algebraic ornamentation — are further characterised in terms of lightweight category theory. Most of the results are completely formalised in the Agda programming language.
7
Diehl, Larry. "Fully Generic Programming Over Closed Universes of Inductive-Recursive Types." PDXScholar, 2017. https://pdxscholar.library.pdx.edu/open_access_etds/3647.
Повний текст джерелаАнотація:
Dependently typed programming languages allow the type system to express arbitrary propositions of intuitionistic logic, thanks to the Curry-Howard isomorphism. Taking full advantage of this type system requires defining more types than usual, in order to encode logical correctness criteria into the definitions of datatypes. While an abundance of specialized types helps ensure correctness, it comes at the cost of needing to redefine common functions for each specialized type. This dissertation makes an effort to attack the problem of code reuse in dependently typed languages. Our solution is to write generic functions, which can be applied to any datatype.
Such a generic function can be applied to datatypes that are defined at the time the generic function was written, but they can also be applied to any datatype that is defined in the future. Our solution builds upon previous work on generic programming within dependently typed programming.
Type theory supports generic programming using a construction known as a universe. A universe can be considered the model of a programming language, such that writing functions over it models writing generic programs in the programming language. Historically, there has been a trade-off between the expressive power of the modeled programming language, and the kinds of generic functions that can be written in it. Our dissertation shows that no such trade-off is necessary, and that we can write future-proof generic functions in a model of a dependently typed programming language with a rich collection of types.
8
Ciaffaglione, Alberto. "Certified reasoning on real numbers and objects in co-inductive type theory." Vandoeuvre-les-Nancy, INPL, 2003. http://docnum.univ-lorraine.fr/public/INPL_T_2003_CIAFFAGLIONE_A.pdf.
Повний текст джерелаАнотація:
Nous adoptons des Méthodes Formelles basées sur la Théorie de Type pour raisonner sur la sémantique des programmes: le but final est montrer qu'un fragment de logiciel répond à ses spécifications formelles. Les domaines d'application de notre recherche sont le type des données des Nombres Réels et les Langages orientés Objets. Dans la première partie nous construisons les réels en utilisant des streams, c. -à-d. Des suites infinies, de chiffres signés. Nous mettons en application les Nombres Réels dans Coq en utilisant les streams, qui sont contrôlés en utilisant des jugements coinductifs et des algorithmes corecursifs. Puis nous présentons une axiomatisation constructive et nous l'employons pour prouver l'adéquation de notre construction. Dans la deuxième partie nous étudions les calculs basées objets avec effet de bord, nous concentrant sur imp[sigma] d'Abadi et de Cardelli. Nous reformulons imp[sigma] en utilisant des techniques de codage modernes, comme la Syntaxe Abstraite d'Ordre Supérieur et des systèmes de preuve Coinductifs en Déduction Naturelle. Enfin nous formalisons imp[sigma] dans Coq et nous prouvons la correction des types<br>We adopt Formal Methods based on Type Theory for reasoning on the semantics of computer programs: the ultimate goal is to prove that a fragment of software meets its formal specification. Application areas of our research are the Real Numbers datatype and the Object-oriented Languages based on Objects. In the first part we construct the Real Numbers using streams, i. E. Infinite sequences, of signed digits. We implement the Reals in Coq using streams, which are managed using coinductive judgments and corecursive algorithms. Then we introduce a constructive axiomatization and we use it for proving the adequacy of our construction. In the second part we approach Object-based Calculi with side-effects, focusing on Abadi and Cardelli's imp[sigma]. We reformulate imp[sigma] using modern encoding techniques, as Higher-Order Abstract Syntax and Coinductive proof systems in Natural Deduction style. Then we formalize imp[sigma] in Coq and we prove the Type Soundness
9
Giorgino, Mathieu. "Inductive representation, proofs and refinement of pointer structures." Toulouse 3, 2013. http://thesesups.ups-tlse.fr/2076/.
Повний текст джерелаАнотація:
Cette thèse s'intègre dans le domaine général des méthodes formelles qui donnent une sémantique aux programmes pour vérifier formellement des propriétés sur ceux-ci. Sa motivation originale provient d'un besoin de certification des systèmes industriels souvent développés à l'aide de l'Ingénierie Dirigée par les Modèles (IDM) et de langages orientés objets (OO). Pour transformer efficacement des modèles (ou graphes), il est avantageux de les représenter à l'aide de structures de pointeurs, économisant le temps et la mémoire grâce au partage qu'ils permettent. Cependant la vérification de propriétés sur des programmes manipulant des pointeurs est encore complexe. Pour la simplifier, nous proposons de démarrer le développement par une implémentation haut-niveau sous la forme de programmes fonctionnels sur des types de données inductifs facilement vérifiables dans des assistants à la preuve tels que Isabelle/HOL. La représentation des structures de pointeurs est faite à l'aide d'un arbre couvrant contenant des références additionnelles. Ces programmes fonctionnels sont ensuite raffinés si nécessaire vers des programmes impératifs à l'aide de la bibliothèque Imperative_HOL. Ces programmes sont en dernier lieu extraits vers du code Scala (OO). Cette thèse décrit la méthodologie de représentation et de raffinement et fournit des outils pour la manipulation et la preuve de programmes OO dans Isabelle/HOL. L'approche est éprouvée par de nombreux exemples dont notamment l'algorithme de Schorr-Waite et la construction de Diagrammes de Décision Binaires (BDDs)<br>This thesis stands in the general domain of formal methods that gives semantics to programs to formally prove properties about them. It originally draws its motivation from the need for certification of systems in an industrial context where Model Driven Engineering (MDE) and object-oriented (OO) languages are common. In order to obtain efficient transformations on models (graphs), we can represent them as pointer structures, allowing space and time savings through the sharing of nodes. However verification of properties on programs manipulating pointer structures is still hard. To ease this task, we propose to start the development with a high-level implementation embodied by functional programs manipulating inductive data-structures, that are easily verified in proof assistants such as Isabelle/HOL. Pointer structures are represented by a spanning tree adorned with additional references. These functional programs are then refined - if necessary - to imperative programs thanks to the library Imperative_HOL. These programs are finally extracted to Scala code (OO). This thesis describes this kind of representation and refinement and provides tools to manipulate and prove OO programs in Isabelle/HOL. This approach is put in practice with several examples, and especially with the Schorr-Waite algorithm and the construction of Binary Decision Diagrams (BDDs)
10
Arkoudas, Kostas. "On the termination of recursive algorithms in pure first-order functional languages with monomorphic inductive data types." Thesis, Massachusetts Institute of Technology, 1996. http://hdl.handle.net/1721.1/39074.
Повний текст джерела