Archive for November, 2008

Call-by-push-value

Friday, November 21st, 2008 by Wouter

I talked about my recent attempts to understand call-by-push-value, a typed lambda calculus that is very precise about when evaluation occurs.

The idea underlying CBPV is to distinguish the type of values and computations. You can think of a value as a fully evaluated Int, String, pair of values, etc. Functions, on the other hand, are computations abstracting over values. I’ve put together an overview of all the types, terms, typing judgements, and evaluation rules (forgive me, but I’d much rather edit large formulas in latex directly than WordPress)

My motivation for this is very different from Paul Levy’s: I’m dreaming of a language with enough laziness to be interesting, but with more predictable memory usage than Haskell. The next step is to figure out how to add (value) data, and (computational) codata, effects (no IO monad), and enough syntactic sugar that you don’t need to be explicit about every thunk/force. There’s a relationship with Conor’s ideas about Frank and the recent work about focussing and duality at CMU that I haven’t managed to nail it down.

The origin of species

Wednesday, November 19th, 2008 by Thorsten

The theory of species was originally conceived by Andre Joyal and is used to analyze combinatorial structures in terms of their generating functions. In my talk on Friday I showed how the theory of species can be developed from a functional programming perspective with a view towards using them to analyze datatypes. I am diverging a bit from the classical definitions in defining a generalisation of species which matches with a specialisation of the notion of a container.

A generalized species is given by a family A : \mathbb{N} \to \mathrm{Set}, the idea is that A\,n is the set of structures which have n positions. E.g. consider the species of leaf-labelled binary trees \mathrm{BT} : \mathbb{N}\to\mathrm{Set}: BT\,3is the set of the two binary trees, which have 3 leafs (insert picture here). Given a species A we assign a functor [\![A]\!] : \mathrm{Set} \to \mathrm{Set} by [\![A]\!]\,X = \Sigma n:\mathbb{N}.A n \times X^n. The definition corresponds to the generating function, but this is a function on the reals not on sets (see my recent posting on sets and numbers). Note that X^n is just n \to X where we identify a natural number with the set of numbers smaller than it (usually called Fin in dependently typed programming).

Category question: If species are the objects, what are the morphisms? Let’s define a category \mathbb{S}. Given species A,B:\mathbb{N}\to\mathrm{Set}, a morphism is given by a triple [math](f,g,h)[/math]:

  •  f : \Pi n:\mathbb{N}, A n \to \mathbb{N}
    Calculating the numbers of positions.
  •  g : \Pi n:\mathbb{N}, a: A n, B\,(f\,n)
    Calculating the new shape.
  •  h : \Pi n:\mathbb{N}, a: A n, (f n) \to n
    Assigning source positions to target positions.

I leave it as an exercise to define identity and composition of those morphisms.

The definition of morphisms hopefully becomes clear when we give their interpretation as natural transformations, i.e. to every species morphism (f,g,h) : \mathbb{S}\,A \,B we assign a natural transformation  [\![f,g,h]\!] : \Pi X:\mathrm{Set},[\![A]\!]\,X \to [\![B]\!]\,X:
 [\![f,g,h]\!]\,X\,(n,a,\mathbf{x}) = (f\,n\,a,g\,n\,a,\mathbf{x}\circ (h\,n\,a)).

Operations on species: Given species A, B : \mathbb{N}\to\mathrm{Set}:

  • Coproducts are easy:
    (A + B)\,n = A\,n + B\,n
  • Products are a bit more involved:
    (A \times B)\,n = \Sigma i,j:\mathrm{Nat},i+j=n \times A\,i\times B\,j
  • Composition is also interesting:
    (A \circ B)\,n = \Sigma m:\mathbb{N},f:m \to \mathbb{N},(\Sigma i:m,f\,i = n),A\,m \times \Pi i:m.B\,(f\,i)

Given a species A : \mathbb{N} \to \mathrm{Set} we can construct its initial algebra \mu A : \mathrm{Set}.

to be continued

Numbers vs Sets

Friday, November 7th, 2008 by Thorsten

To simplify: Mathematics has to do with numbers, while Computer Science is more concerned with types (let’s call them sets). On the level of the natural numbers there is a nice equivalence identfying a finite set with the number of its elements. The operations of addition and multiplication on numbers correspond to coproduct (or disjoint union) and (cartesian) product of sets. Indeed we even use the same symbols + and \times. Exponentiation b^a corresponds to function space a \to b, indeed category theoreticians use the exponential notation for the latter.

But then the ways part and the schism begins. For the Mathematicians the natural numbers are only half of the story (indeed a semiring) and they hasten to add the negative numbers. If we want to keep exponentiation, we can’t stop at the integers, we get the rational numbers 1/2 = 2^{-1}, algebraic reals \sqrt{2} = 2^{1/2} = 2^{2^{-1}} and even algebraic complex numbers i = (-1)^{1/2} = (-1)^{2^{-1}. The intuitive completion of these constructions are the complex numbers.

Negative sets don’t really make sense, we are more interested in infinite sets. E.g. we would like to have a fixpoint of successor: \mu X.1+X = \mathbb{N}. Combining this with exponentiation leeds to larger sets like \mathbb{N} \to \mathbb{N} or ordinal notations
\Omega = \mu X.1 + X + \mathbb{N}\to X. This time the intuitive completion are sets.

But the story may have a happy ending. Once we start to analyze operations on those spaces, a new analogy seems to emerge. E.g. differentiation is well known as an operation on complex functions, but as Conor McBride observed it also makes sense as an operation on functors, i.e. operations on sets. Not on all functors, but then differentiation doesn’t work on all functions either. The analogy carries further, and indeed we can use a variation of Taylor’s theorem to analyze datatypes. Hence, here we seem to have a new union, the glimpse of a generalized calculus applicable to operations in numbers and sets.

One of the areas where this analogy has been exploited is the theory of species, where ideas from calculus are exploited to prove theorems about the combinatorics of structures. To me much of the literature seems to be written from the perspective of Mathematicians who know numbers and try to use them to analyze sets. I’d prefer to do it the other way around, start with sets and see whether we can steal ideas from conventional calculus.

This is basically the introduction to a more technical talk about generalized species which I will post separately.