1 |
Logic and handling of algebraic effectsPretnar, Matija January 2010 (has links)
In the thesis, we explore reasoning about and handling of algebraic effects. Those are computational effects, which admit a representation by an equational theory. Their examples include exceptions, nondeterminism, interactive input and output, state, and their combinations. In the first part of the thesis, we propose a logic for algebraic effects. We begin by introducing the a-calculus, which is a minimal equational logic with the purpose of exposing distinct features of algebraic effects. Next, we give a powerful logic, which builds on results of the a-calculus. The types and terms of the logic are the ones of Levy’s call-by-push-value framework, while the reasoning rules are the standard ones of a classical multi-sorted first-order logic with predicates, extended with predicate fixed points and two principles that describe the universality of free models of the theory representing the effects at hand. Afterwards, we show the use of the logic in reasoning about properties of effectful programs, and in the translation of Moggi’s computational ¸-calculus, Hennessy-Milner logic, and Moggi’s refinement of Pitts’s evaluation logic. In the second part of the thesis, we introduce handlers of algebraic effects. Those not only provide an algebraic treatment of exception handlers, but generalise them to arbitrary algebraic effects. Each such handler corresponds to a model of the theory representing the effects, while the handling construct is interpreted by the homomorphism induced by the universal property of the free model. We use handlers to describe many previously unrelated concepts from both theory and practice, for example CSS renaming and hiding, stream redirection, timeout, and rollback.
|
2 |
Infinitesimal models of algebraic theoriesBár, Filip January 2017 (has links)
Smooth manifolds have been always understood intuitively as spaces that are infinitesimally linear at each point, and thus infinitesimally affine when forgetting about the base point. The aim of this thesis is to develop a general theory of infinitesimal models of algebraic theories that provides us with a formalisation of these notions, and which is in accordance with the intuition when applied in the context of Synthetic Differential Geometry. This allows us to study well-known geometric structures and concepts from the viewpoint of infinitesimal geometric algebra. Infinitesimal models of algebraic theories generalise the notion of a model by allowing the operations of the theory to be interpreted as partial operations rather than total operations. The structures specifying the domains of definition are the infinitesimal structures. We study and compare two definitions of infinitesimal models: actions of a clone on infinitesimal structures and models of the infinitesimalisation of an algebraic theory in cartesian logic. The last construction can be extended to first-order theories, which allows us to define infinitesimally euclidean and projective spaces, in principle. As regards the category of infinitesimal models of an algebraic theory in a Grothendieck topos we prove that it is regular and locally presentable. Taking a Grothendieck topos as a base we study lifts of colimits along the forgetful functor with a focus on the properties of the category of infinitesimally affine spaces. We conclude with applications to Synthetic Differential Geometry. Firstly, with the help of syntactic categories we show that the formal dual of every smooth ring is an infinitesimally affine space with respect to an infinitesimal structure based on nil-square infinitesimals. This gives us a good supply of infinitesimally affine spaces in every well-adapted model of Synthetic Differential Geometry. In particular, it shows that every smooth manifold is infinitesimally affine and that every smooth map preserves this structure. In the second application we develop some basic theory of smooth loci and formal manifolds in naive Synthetic Differential Geometry using infinitesimal geometric algebra.
|
3 |
Διατήρηση κλάσεων πεπερασμένων ορίων από αριστερές επεκτάσεις KanΠροτσώνης, Γρηγόρης 31 August 2012 (has links)
Mελετάμε το πρόβλημα της διατήρησης κάποιας κλάσης πεπερασμένων ορίων από την αριστερή επέκταση Kan ενός συναρτητή. Παρουσιάζουμε αρχικά την περίπτωση για συναρτητές που λαμβάνουν τιμές στην κατηγορία των συνόλων. Η περίπτωση αυτή έχει μελετηθεί στην βιβλιογραφια, και ο χαρακτηρισμός τέτοιων επεκτάσεων Kan έχει να κάνει με την έννοια της επιπεδότητας του συναρτητή. Παρατηρώντας ότι η έννοια της επιπεδότητας μπορεί να ερμηνευτεί (με όρους εσωτερικής λογικής) σε μία κατηγορία η οποία είναι εφοδιασμένη με μία τοπολογία Grothendieck, μελετάμε το πρόβλημα στην γενικότητά του. Καθοριστικό ρόλο στην μελέτη μας, παίζει η έννοια του καθορισμένου συνορίου. Με αυτά τα εργαλεία καταλήγουμε σε ικανές και αναγκαίες συνθήκες για την διατήρηση πεπερασμένων γινομένων, πεπερασμένων συνεκτικών ορίων και όλων των πεπερασμένων ορίων από την αριστερή επέκταση Kan ενός συναρτητή που λαμβάνει τιμές σε μια κατηγορία η οποία είναι εφοδιασμένη με μία υποκανονική τοπολογία Grothendieck. Τέλος μελετάμε και την περίπτωση διατήρησης μονομορφισμών από αριστερές επεκτάσεις Kan μεταξύ αλγεβρικών κατηγοριών. / We study the problem of preservation of some classes of finite limits from the left Kan extension of a functor. Initially we present the case where the functor takes values in the category of sets. This case has been studied in the literature, and the characterization of such Kan extensions is related with the notion of flatness. Observing that the notion o flatness can be interpreted (with terms of internal logic) in a category which is equipped with a Grothendieck topology, we study the problem in its generality. Crucial role plays the notion of postulated colimit. With those tools, we conclude necessary and sufficient conditions for the preservation of finite products, of finite connected limits and all the finite limits from the left Kan extension of a functor which takes values into a category which is equipped with a subcanonical Grothendieck topology. Finally we study the case of preservation of monomorphisms from certain Kan extensions between algebraic categories.
|
Page generated in 0.0495 seconds