INRIA project-team $\pi r^2$

Thematic team Algebra and computation

Thematic team Proofs and programs

## Semantics

#### Day, hour and place

#### Contact(s)

### Next talks

Semantics

Monday March 18, 2019, 2PM, Salle 3052

**Michel Schellekens** (University College Cork) *Expedient Algebra: Duality and Entropy Conservation*

We show that EXP-computations, made reversible through history-keeping, act as closed systems in which entropy is conserved. Thus modularity of timing is linked to entropy conservation of data flow, sharpening traditional entropy preservation guaranteed by the second law of thermodynamics for reversible systems. This type of conservation typically holds for the case of energy, but not for entropy. A salient point is that for algorithms satisfying distribution control, entropy is neither created nor destroyed, merely transferred from one form, i.e. quantitative entropy, to another, i.e. positional entropy.

We establish the Entropy Conservation Laws ECL-1 and ECL-2. ECL-1 expresses the inverse proportionality of positional and quantitative entropy for distributions over series-parallel orders and their duals. ECL-2, a computational version of entropy conservation, expresses that order established by the expedient product (with history) on labels is proportionally destroyed on indices by a shadow transformation in the dual space. The laws shed new light on the properties of algorithms for which distribution control, and hence modular timing, is guaranteed.

Semantics

Tuesday April 2, 2019, 10:30AM, Salle 3052

**Jérémy Dubut** (NII, Tokyo) *To be announced.*

### Previous talks

#### Year 2019

Semantics

Tuesday February 26, 2019, 10:30AM, Salle 3052

**Eric Finster** (INRIA) *L'algèbre universelle supérieur dans la théorie des types dependants*

Semantics

Friday February 1, 2019, 10:30AM, Salle 3052

**Nobuko Yoshida** (Imperial College London) *Behavioural Type-Based Static Verification Framework for Go*

POPL'17 Fencing off go: liveness and safety for channel-based programming ICSE'18 A Static Verification Framework for Message Passing in Go using Behavioural Types POPL'19 Distributed Programming Using Role Parametric Session Types in Go.

Go is a production-level statically typed programming language whose design features explicit message-passing primitives and lightweight threads, enabling (and encouraging) programmers to develop concurrent systems where components interact through communication more so than by lock-based shared memory concurrency. Go can detect global deadlocks at runtime, but does not provide any compile-time protection against all too common communication mismatches and partial deadlocks. We present a static verification framework for liveness and safety in Go programs, able to detect communication errors and deadlocks by model checking. Our toolchain infers from a Go program a faithful representation of its communication patterns as behavioral types, where the types are model checked for liveness and safety. We also present a recent code generation for Go.

Semantics

Tuesday January 29, 2019, 11AM, Salle 3052

**Giulio Guerrieri** (Università di Bologna) *Types by Need (joint work with Beniamino Accattoli and Maico Leberle)*

Semantics

Monday January 28, 2019, 11AM, Salle 3052

**Fredrik Dahlqvist** (UCL - Department of Computer Science) *Semantics of higher-order probabilistic programs with conditioning*

Semantics

Tuesday January 8, 2019, 10:30AM, Salle 3052

**Jean Bénabou** *Les multiples facettes de la « construction de Grothendieck »*

#### Year 2018

Semantics

Tuesday December 4, 2018, 11:20AM, Amphi Turing, Bâtiment Sophie Germain

**Eric Degiuli** (ENS) *Random Language Model: a path to principled complexity*

Semantics

Monday November 26, 2018, 10:45AM, Salle 3052

**Hendrik Maarand** (Tallinn University of Technology) *Derivatives of Existentially Regular Trace Languages*

Semantics

Tuesday November 6, 2018, 10:30AM, Salle 3052

**Rick Blute** (University of Ottawa) *Finiteness spaces and generalized power series*

In the present work, we take morphisms to be partial functions preserving the finitary structure rather than relations. The resulting category is symmetric monoidal closed, complete and cocomplete. Any pair of an internal monoid in this category and a ring induces a ring of generalized power series by an extension of the Ribenboim construction based on Ehrhard’s notion of linearization of a finiteness space. We thus further generalize Ribenboim’s constructions. We give several examples of rings which arise from this construction, including the ring of Puiseux series and the ring of formal power series generated by a free monoid. This is joint work with Cockett, Jacqmin and Scott.

We'll also present some results of Beauvais-Fiesthauer, Dewan and Drummond on the embedding of topological spaces into finiteness spaces and discuss how this might be of use in the analysis of etale groupoids and their C*-algebras.

Semantics

Tuesday October 16, 2018, 10:30AM, Salle 3052

**Thomas Ehrhard** (IRIF) *Une remarque sur les espaces cohérents probabilistes et la distance opérationnelle entre les programmes*

Semantics

Tuesday September 18, 2018, 10AM, Salle 3052

**Paul-André Mellies** (IRIF) *Template games: a model of differential linear logic*

Semantics

Tuesday September 18, 2018, 11AM, Salle 3052

**Jean-Simon Lemay** (University of Oxford) *Differential Categories Revisited*

Les catégories différentielles ont été introduites afin de fournir une sémantique catégorique minime pour la logique linéaire différentielle. Cependant, il existe trois approches d'axiomatiser la dérivée par les “deriving transformations”, “coderelictions”, “creation maps” - considérés pendant longtemps comme des notions distinctes. Récemment, avec Blute, Cockett et Seely, nous avons revisité les axiomes d’une catégorie différentielle et démontré que pour les modèles catégoriques de logique linéaire différentielle, les trois approches sont équivalentes. Il y a donc qu’une seule notion de différentielle.

Semantics

Tuesday May 15, 2018, 11AM, Salle 3052

**Tarmo Uustalu** (Reykjavik University and Tallinn University of Technology) *Nested and labelled sequent calculi for bi-intuitionistic propositional logic*

This is joint work with Luís Pinto (Universidade do Minho).

Semantics

Tuesday February 20, 2018, 11AM, Salle 3052

**Shin-Ya Katsumata** (National Institute of Informatics, Tokyo) *Codensity liftings of monads*

(Joint work with Tetsuya Sato; presented in CALCO 2015)

Semantics

Wednesday January 17, 2018, 10AM, Salle 3052

**Luc Pellissier** (ENS Lyon) *Intersection Types, Linear Approximations and the Grothendieck construction*

Based on a joint work with Damiano Mazza and Pierre Vial.

Semantics

Wednesday January 17, 2018, 11AM, Salle 3052

**Soichiro Fujii** (National Institute of Informatics (NII, Tokyo)) *A unified framework for notions of algebraic theory*

First I will explain how each notion of algebraic theory can be identified with a certain monoidal category, in such a way that theories correspond to monoids. Then I will introduce a categorical structure underlying the definition of models of theories. In specific examples, it often arises in the form of oplax action or enrichment. Finally I will uniformly characterize categories of models for various notions of algebraic theory, by a double-categorical universal property in the pseudo-double category of profunctors.

#### Year 2017

Semantics

Tuesday December 5, 2017, 10:30AM, Salle 3052

**Kenji Maillard** (INRIA et ENS) *F* : Dijkstra-monads at work*

Semantics

Wednesday November 29, 2017, 10:30AM, Salle 3052

**Simona Paoli** (University of Leicester) *n-Fold models of weak n-categories*

Semantics

Tuesday November 21, 2017, 10:30AM, Salle 3052

**John Baez** (UCLA Riverside) *Compositionality in Network Theory*

Semantics

Tuesday November 7, 2017, 10:30AM, Salle 3052

**Tobias Heindel** (Université de Leipzig) *Formal language theory beyond trees and forests*

Semantics

Tuesday October 31, 2017, 10:30AM, Salle 3052

**Nicolas Behr** (IRIF) *Combinatorial Hopf algebras and rewriting: the rule algebra framework*

Semantics

Thursday August 31, 2017, 2PM, Salle 3052

**Zoran Petric** (Mathematical Institute, Academy of Sciences, Belgrade) *Frobenius spheres*

The talk is based on the paper “Spheres as Frobenius objects”, co-authored with Djordje Baralic and Sonja Telebakovic, which is available at arxiv.

Semantics

Tuesday July 18, 2017, 2PM, Salle 3052

**Noam Zeilberger** (University of Birmingham) *Some bridges between lambda calculus and graphs on surfaces*

Semantics

Friday June 30, 2017, 4:30PM, Salle 3052

**Niccolò Veltri** (Laboratory of Software Science, Tallinn) *Partiality and container monads*

Semantics

Tuesday June 13, 2017, 11AM, Salle 2012

**Elaine Pimentel** (Universidade Federal do Rio Grande do Norte (Brasil)) *A uniform framework for substructural logics with modalities*

This is a joint work with Carlos Olarte and Björn Lellmann

Semantics

Tuesday February 28, 2017, 11AM, Salle 3052

**Ran Chen** (Inria) *Strongly Connected Components in graphs, formal proof of Tarjan1972 algorithm*

We present a human readable and rather intuitive formal proof for the classical Tarjan-1972 algorithms for finding strongly connected components in directed graphs. Tarjan’s algorithm consists in an efficient one-pass depth-first search traversal in graphs which traces the bases of strongly connected components. We describe the algorithm in a functional programming style with abstract values for vertices in graphs, with functions between vertices and their successors, and with data types such that lists (for representing immutable stacks) and sets. We use the Why3 system and the Why3-logic to express these proofs and fully check them by computer.

Semantics

Tuesday January 24, 2017, 11AM, Salle 3052

**Arnaud Spiwack** (Tweag I/O) *Retrofitting linear types*

I had always had the belief that to add linear types to a language was a rather intrusive procedure and that a language with linear types would basically be an entirely new language. The Rust language is a case in point: it has a linear-like type system, but it's a very different language from your run-of-the-mill functional language.

This turns out not to be the case: this talk presents a way to extend a functional programming language. We are targeting Haskell but there is little specific to Haskell in this presentation. I will focus mostly on the type system and how it can be generalised: among other things the type system extends to dependent types.

Semantics

Friday January 13, 2017, 2PM, Salle 3052

**Tarmo Uustalu** (Tallinn University of Technology) *Interaction morphisms*

Tarmo Uustalu, Tallinn U of Technology

I will propose interaction morphisms as a means to specify how an effectful computation is to be run, provided a state in a context. An interaction morphism of a monad T and a comonad D is a family of maps T X x D Y → X x Y natural in X and Y and subject to some equations. Interaction morphisms turn out to be a natural concept with a number of neat properties. In particular, interaction morphisms are the same as monoids in a certain monoidal category; interaction morphisms of T and D are in a bijective correspondence with carrier-preserving functors between the categories of coalgebras of D and stateful runners of T (monad morphisms from T to state monads); they are also in a bijective correspondence with monad morphisms from T to a monad induced in a certain way by D.

This is joint work with Shin-ya Katsumata (University of Kyoto).

Semantics

Tuesday January 10, 2017, 11AM, Salle 3052

**Fanny He** (Université de Bath, UK) *The atomic lambda-mu-calculus*

One approach for the former is to gain more control over duplication and deletion of terms, by introducing sharings of common subterms inside a lambda-term, similarly to optimal reduction graphs. This has been done by Gundersen, Heijltjes and Parigot, via the atomic lambda-calculus, a calculus extending the lambda-calculus with explicit sharings, and allowing duplications on individual constructors. It enjoys full-laziness, avoiding unnecessary duplications of constant expressions.

For the latter, an extension of the lambda-calculus linking classical formulas to control flow constructs via Curry-Howard correspondence, the lambda-mu-calculus, was developed by Parigot. New operators in the lambda-mu-calculus correspond to continuations, representing the remaining work in a program.

Can we combine sharing with control operators and thus obtain another extension of the lambda-calculus satisfying full-laziness and featuring control operators? A first challenge is to combine explicit sharings or substitutions with mu-reduction and substitution, and we introduce a right-associative application as in Saurin-Gaboardi's lambda-mu-calculus with streams to overcome this challenge. Another difficulty is to adapt the type system for lambda-mu with multiple conclusions, distinguishing one main conclusion (with a meta-disjunction connective), to a type system in which each rule can be applied to atoms (which corresponds to duplications on individual term constructors), and where no distinction is made between object and meta-level. I will present how to combine these two type systems in the simplest possible way.

I will present the atomic lambda-mu-calculus, which aims to naturally extend the two calculi presented above, giving the simplest type system combining and preserving their properties.

#### Year 2016

Semantics

Wednesday December 21, 2016, 11AM, Salle 3052

**Victoria Lebed** (Trinity College, Dublin) *Que savent les tresses sur les tableaux de Young ?*

Semantics

Tuesday December 20, 2016, 11AM, Salle 3052

**Clovis Eberhart** (LAMA, Chambéry) *Séquences justifiées et diagrammes de cordes : deux approches de la sémantique de jeux concurrents*

Semantics

Tuesday December 6, 2016, 11AM, Salle 3052

**Yann Régis-Gianas** (IRIF) *Explaining Program Differences Using Oracles*

We present a formal framework to characterize differences between deterministic programs in terms of their small-step semantics. This language-agnostic framework defines the notion of /difference languages/ in which /oracles/—programs that relate small-step executions of pairs of program written in a same language—can be written, reasoned about and composed.

We illustrate this framework by instantiating it on a toy imperative language and by presenting several /difference languages/ ranging from trivial equivalence-preserving syntactic transformations to characterized semantic differences. Through those examples, we will present the basis of our framework, show how to use it to relate syntactic changes with their effect on semantics, how one can abstract away from the small-step semantics presentation, and discuss the composability of oracles.

This is joint work with Thibaut Girka (IRIF - MERCE) and David Mentré (MERCE)

Semantics

Tuesday November 15, 2016, 11AM, Salle 3052

**José Espírito Santo** (University of Minho) *Call-by-name, call-by-value and intuitionistic logic*

Semantics

Tuesday November 8, 2016, 11AM, Salle 3052

**Gustavo Petri** (IRIF) *Safe and Scalable Cloud Programming*

Semantics

Tuesday October 18, 2016, 10:30AM, Salle 3052

**Pablo Barenbaum** (Université de Buenos Aires - CONICET) *Finite Family Developments for the Linear Substitution Calculus*

Semantics

Tuesday October 18, 2016, 11:30AM, Salle 3052

**Masahito Hasegawa** (Research Institute in Mathematical Sciences (RIMS)) *Traced star-autonomous categories are compact closed*

We also discuss what would happen if we remove symmetry, thus the following question: is there a non-symmetric star-autonomous category with a (suitably generalized) trace which is not pivotal? Our recent attempt suggests that the answer is again no, but the situation is much subtler than the symmetric case.

The result on the symmetric case is a joint work with Tamas Hajgato.

Semantics

Tuesday July 5, 2016, 11AM, Salle 3052

**Shane Mansfield** (IRIF) *Empirical Models and Contextuality*

Semantics

Tuesday June 7, 2016, 11AM, Salle 3052

**Thomas Leventis** (I2M Marseille) *Probabilistic lambda-theories*

In this talk we will recover this notion of presentation through equalities in the probabilistic lambda-calculus. We will show how some usual notions can be translated in the probabilistic world. In particular we will define a notion of probabilistic Böhm tree, and show a separability result. This will implies that just like in the deterministic setting the Böhm tree equality is the same as the observational equivalence.

Semantics

Tuesday June 7, 2016, 10AM, Salle 3052

**Antoine Allioux** (IRIF) *Krivine machine and Taylor expansion in a non-uniform setting*

We generalize this resource-driven Krivine machine to the case of the algebraic $\lambda$-calculus. The latter is an extension of the pure $\lambda$-calculus allowing for the linear combination of $\lambda$-terms with coefficients taken from a semiring. Our machine associates a $\lambda$-term $M$ and a resource annotation $t$ with a scalar $\alpha$ in the semiring describing some quantitative properties of the linear head reduction of $M$.

In the particular case of non-negative real numbers and of algebraic terms $M$ representing probability distributions, the coefficient $\alpha$ gives the probability that the linear head reduction actually uses exactly the resources annotated by $t$. In the general case, we prove that the coefficient $\alpha$ can be recovered from the coefficient of $t$ in the Taylor expansion of $M$ and from the normal form of $t$.

Semantics

Tuesday May 17, 2016, 11AM, Salle 3052

**Daniel Leivant** (Indiana University Bloomington) *Syntax directed coproofs for Propositional Dynamic Logic*

Contrary to proofs, which are generated inductively top-down, coproofs are generated coinductively bottom-up, and may have infinite branches. However, our inference rules allow this only via state-changes, and as a result are sound.

We also prove the semantic completeness of our formalism, and apply it to obtain new interpolation theorems for PDL.

Semantics

Thursday April 7, 2016, 4PM, Salle 3052

**Flavien Breuvart** (INRIA Focus (Université de Bologna, IT)) *L'encodage probabiliste: vers une formalisation systématique des langages probabilistes, déterministiques et potentiellement divergents.*

Semantics

Tuesday March 29, 2016, 10:30AM, Salle 3052

**Andrew Polonsky** (IRIF) *Interpreting infinite terms*

\f.f(Ω), \f.f^2(Ω), \f.f^3(Ω), …, \f.f^n(Ω), ….

The infinite term \f.f(f(f…)) is the limit of the above sequence, and in the infinitary lambda calculus all fpcs reduce to this term, which is an infinitary normal form. It would seem natural to extend the interpretation function to cover infinitary terms as well, however, naive attempts to do this fail. The problem is already present in the first-order case: finite terms over a signature ∑ can be interpreted by means of the initial semantics – where the free algebra of terms admits a canonical homomorphism to any other ∑-algebra. However, the infinite terms are elements of the cofinal coalgebra, which universal property concerns maps INTO the algebra, rather than out of it. We are thus faced with a “koan”:

- What does it mean to interpret infinite terms?*

While we shall not provide a (co)final solution to this koan, we will offer germs of some possible approaches, with the hope of starting a discussion that could follow this short talk.