## Computational Logic and Applications

### Novi Sad, 26-27 May 2016

It is our pleasure to announce that the ninth workshop Computational Logic and Applications (CLA 2016) will be held on 26-27 May 2016 in Novi Sad, Serbia, as a satellite event of 22nd International Conference on Types for Proofs and Programs TYPES 2016. The workshop gathers researchers interested in quantitative aspects of mathematical logic and functional programming, including, but not limited, to topics such as:

• counting and generating terms, propositions and trees,
• random generation and Boltzmann samplers,
• generating functions and the asymptotic evaluation of term/proposition size,
• testing and optimizing compilers of functional programming languages.
All researchers are cordially invited to attend.

It is our pleasure to announce that
the programme is now available!

## Registration

The registration for CLA 2016 is now open! Participation is free of charge!

• Registration for participation only: 26.05.2016.

(*) Leave blank if you do not intend to give a talk.

# Venue

The conference will be held at the University of Novi Sad, University Central Building.

# Programme

### Thursday

 Time Speaker Talk 10:00 Open session 12:00 Lunch break 14:00 Pierre Lescanne The problem of counting and generating simply typed lambda terms This talk will state more problems than provide solutions. After describing the role of generating typed lambda terms, I will present several methods for counting lambda terms, several results mostly experimental obtained about counting and uniformly generating simply typed lambda terms and I will conclude with open questions. 14:45 Break 15:00 Sergei Soloviev Probabilistic distributions on formal objects with various constraints The talk is about work in progress where we are interested in probabilistic distributions on formal objects with various constraints: the case of Boolean games with random Boolean formula(e) representing pay functions, the case of isomorphisms and automorphisms of types in Type Theory etc. We are interested in facts that hold for (large) classes of distributions. 15:45 Break 16:00 Łukasz Lachowski On the Complexity of Translations of Lambda Calculus into Combinatory We study the complexity of all possible translations of lambda calculus into combinatory logic. First, we show that the space complexity of the standard translation is $\Theta(n^3)$. Then we investigate the lower bound for worst case size for all translations. Our main result states that any translation which preserves extensional equivalence of these models produces terms of the size $\Omega(n \log{n})$. We also present an algorithm which is asymptotically optimal. 16:45 Break 17:00 Agnieszka Łupińska Parallel standard translation between Lambda Calculus and Combinatory Logic The talk is about the parallel approach to the standard translation between Lambda Calculus and Combinatory Logic. Let L be a lambda-term and C be a combinator produced from L by the standard translation. Each lambda abstraction occurring in L, causes the linear expansion of some paths in the tree of the C combinator. We will show that the tree expansion can be performed parallel in logarithmic time on the path length. We will also discuss whether this procedure can be performed in the constant time.

### Friday

 Time Speaker Talk 10:00 Bernhard Gittenberger Enumeration of lambda terms according their de Bruijn index size John Tromp introduced the so-called 'binary lambda calculus' as a way to encode lambda terms in terms of binary words. Later, Grygiel and Lescanne conjectured that the number of binary lambda terms with $m$ free indices and of size $n$ (encoded as binary words of length $n$) is $O(n^{-3/2} \tau^{-n})$ for $\tau \approx 1.963448\ldots$. We generalize the proposed notion of size and show that for several classes of lambda terms, including binary lambda terms with $m$ free indices, the number of terms of size $n$ is $\Theta(n^{-3/2} \rho^{-n})$ with some class dependent constant $\rho$, which in particular disproves the above mentioned conjecture. A way to obtain lower and upper bounds for the constant near the leading term is presented and numerical results for a few previously introduced classes of lambda terms are given. 11:30 Break 11:45 Katarzyna Grygiel A natural counting of lambda terms We study the sequence of numbers corresponding to lambda terms of given size in the model based on de Bruijn indices. It turns out that the sequence enumerates also two families of binary trees, i.e. black-white and zigzag-free ones. We provide a constructive proof of this fact by exhibiting appropriate bijections. Moreover, we investigate the asymptotic density of lambda terms containing an arbitrary fixed subterm, showing that strongly normalizing terms are of density zero among all lambda terms. Joint work with M. Bendkowski, P. Lescanne, M. Zaionc 12:30 Lunch break 14:00 Maciej Bendkowski Quantitative aspects of normal-order reduction in combinatory logic In this talk, we introduce the concept of normal-order reduction grammars characterizing the set of weakly normalizing combinatory logic terms. Exploiting its algorithmic nature, we study the asymptotic density of combinatory logic terms reducting in $n \in \mathbb{N}$ normal-order reduction steps, providing an automated method of finding their relative densities. Finally, we present some super-computer cluster experimental results for large term sizes and reduction sequences. 14:45 Break 15:00 Matthieu Dien On the combinatorics of concurrent programs In this talk we will be interrested by two problems: counting the number of possible executions (runs) of a concurrent program generating randomly, with a uniform law, a possible run for a given program We will show different classes of concurrent programs for which we can solve one or the two problems efficiently. 15:45 Break 16:00 Paul Tarau A Logic Programming Playground for Lambda Terms, Types and Tree-based Arithmetic We overview our Prolog-based "playground" that collects algorithms for generating several lambda-term representations and families of combinators and their types, as well as computations ranging from type inference and normalization to arithmetic encodings. Our playground, built as an incrementally developed literate Prolog program is available at http://www.cse.unt.edu/~tarau/research/2015/play.pdf with extracted Prolog sources at http://www.cse.unt.edu/~tarau/research/2015/play.pro. The playground covers compact combinatorial generation algorithms for several families of lambda terms, including open, closed, simply typed and linear terms as well as type inference and normal order reduction algorithms. Among them we will focus on a Prolog-based combined lambda term generator and type-inferrer for closed well-typed terms of a given size, in de Bruijn notation. We overview a compressed de Bruijn representation of lambda terms and define its bijections to standard representations. Our compressed terms facilitate derivation of size-proportionate ranking and unranking algorithms of lambda terms and their inferred simple types. By taking advantage of Prolog's bidirectional execution model and sound unification algorithm, our generators can build customized'' closed terms of a given type. This "relational view" of terms and their types enables the discovery of interesting patterns about frequently used type expressions occurring in well-typed functional programs. Our study uncovers the most popular'' types that govern function applications among a about a million small-sized lambda terms and hints toward practical uses to combinatorial software testing. The S and K combinator expressions form a well-known Turing-complete subset of the lambda calculus. We specify evaluation, type inference and combinatorial generation algorithms for SK-combinator trees. In the process, we unravel properties shedding new light on interesting aspects of their structure and distribution. We study the proportion of well-typed terms among size-limited SK-expressions as well as the type-directed generation of terms of sizes smallerthen the size of their simple types. We also introduce the em "well-typed frontier of an untypable term" and we use it to design a simplification algorithm for untypable terms taking advantage of the fact that well-typed terms are normalizable. A uniform representation, as binary trees with empty leaves, is given to expressions built with Rosser's X-combinator, natural numbers, lambda terms and simple types. Using this shared representation, ranking/unranking algorithm of lambda terms to tree-based natural numbers are described. 17:00 Open discussion session

# List of Participants

• Maciej Bendkowski (Jagiellonian University, Kraków)
• Olivier Bodini (Paris-Nord University, France)
• Matthieu Dien (UPMC - LIP6)
• Silvia Ghilezan (University of Novi Sad)
• Bernhard Gittenberger (TU Wien, Austria)
• Katarzyna Grygiel (Jagiellonian University, Kraków)
• Philipp Haselwarter (University of Ljubljana)
• Bashar Igried (Swansea University)
• Łukasz Lachowski (Jagiellonian University, Kraków)
• Pierre Lescanne (École normale supérieure de Lyon)
• Agnieszka Łupińska (Jagiellonian University, Kraków)
• Michał Pałka (Chalmers University of Technology, Gothenburg, Sweden)
• Randy Pollack (Edinburgh and Cornell)
• Sergei Soloviev (IRIT, University of Toulouse)
• Paul Tarau (University of North Texas, USA)
• Marek Zaionc (Jagiellonian University, Kraków)

# Workshop Committee

Maciej Bendkowski (Jagiellonian University, Kraków, Poland)

Olivier Bodini (Paris-Nord University, France)

Daniele Gardy (Versailles University, France)

Antoine Genitrini (Pierre et Marie Curie University, Paris, France)

Alain Giorgetti (Franche-Comté University, Besançon, France)

Bernhard Gittenberger (TU Wien, Austria)

Zbigniew Gołębiewski (Wrocław University, Poland)

Katarzyna Grygiel (Jagiellonian University, Kraków, Poland)

Pierre Lescanne (École normale supérieure de Lyon, France)

Michał Pałka (Chalmers University of Technology, Gothenburg, Sweden)

Paul Tarau (University of North Texas, USA)

Brent Yorgey (Hendrix College, Arkansas, USA)

Marek Zaionc (Jagiellonian University, Kraków, Poland)

Noam Zeilberger (INRIA, Palaiseau, France)