Wow! We really got into some depth on these topics. We spent both a long discussing streaming data and anamorphisms, and then a long time discussing simply typed lambda calculus, especially previewing question #5 from the upcoming exercises.
I pointed out that the "anamorphism" discussed in the slides is really a particular anamorphism for streams, and is not the general definition of anamorphism. In general, an anamorphism (unfold) starts with a seed value and incrementally builds some sort of data structure through recursive application of a transition function. This could be a stream, or a tree, or any sort of data structure. This is the opposite of a catamorphism (fold), which takes a data structure and recursively breaks it down into a single value. It turns out that Wikipedia has a really nice explanation with some examples in Haskell: https://en.wikipedia.org/wiki/Anamorphism
I showed a Haskell function ana from the Data.Fix library which is generalized to work for any sort of data structure. Unfortunately, that generalization makes it a bit more difficult to understand. You need to start with a special non-recursive version of the recursive data type you want to generate. Let's call that non-recursive version F. Then the recursive datatype you want to generate would be the greatest fixed point of F, denoted Fix F. To define an anamorphism, we need a function from a seed value to a value of type F; this is called an F-coalgebra.
In the case of infinite streams, the type F could be defined as:
data StreamF a = ConsF a b
Note how this is a small, finite data structure. It has only two values. The actual infinite stream type is
type Stream a = Fix (StreamF a)
This is like applying the Y combinator, but at the type level. To build a stream, one simply needs a function from some type b to the type StreamF a. You can think of the type b as the seed/state value. And type a represents the element value. So, let's say we want to write natsFrom, the function that produces natural numbers starting from an initial value. We can define it as:
natsFrom :: Nat -> Stream Nat
natsFrom n0 = ana (\n -> ConsF n (succ n)) n0
How does this correspond to what the slides said about anamorphisms? They said we needed to define two functions: an observation function f and a transition function t. Well, we have both here - they're just encoded slightly differently. Our observation function is just the identity function, and the transition function is the successor function. We've collapsed them into one function by using a datatype that lets us produce both results at once - the first value in the ConsF being the result of the observation function, and the second value in the ConsF being the result of the transition function.
By using this pattern, we can define anamorphisms for any singly-recursive data structure, not just streams.
Matt pointed out that infinite streams need to be constructed differently in ML. Due to the strict evaluation, they cannot be represented quite so compactly.
Simply Typed Lambda Calculus
We got a little confused about the base type "o" from the slides. The slides say there are "no closed terms" of that type. I'd seen other formulations of STLC where there were some primitive base types such as Nat or Bool. But here we have some abstract, apparently empty type. If there are no terms of type o, can there be terms of type ? Well, the identity function, is such a term. But if there are no terms of type o, what would we ever substitute in for ? The book chapter makes no such claim that the type o has no closed terms. Ed pointed out that the side condition on the variable rule deriving is a bit awkward and unnecessary. One could simply write the conclusion as , mirroring the notation used in other rules.
The slides mention weak normalization but do not define it. A weakly normalizing term is one there exists a finite reduction sequence that will lead to normal form. A strongly normalizing term is where any reduction order will lead to the normal form in a finite number of steps. In untyped lambda calculus, some terms are non-normalizing, some are weakly normalizing, and some are strongly normalizing. In STLC, all terms are strongly normalizing.
The chapter (5) also confused us a bit by showing us a language with Nat, Bool, if/then/else, and other constructs. We were trying to understand whether 'succ' in that context was a constructor, or a function. And was 'pred' another constructor? That question turned out to be meaningless, as we realized that this was not the lambda calculus, but just some arbitrary language being defined to show us how it could be typed.
Homework exercise 5
We skipped ahead to look at one of the exercise for next time: Exercise 5 from Exercise Set 3. It's a bit confusing. Matt had spent some time trying to define the pair type in terms of A, B, C, and the arrow operators. We came to the conclusion that it probably wasn't possible. However, I see the exercise as asking us instead to extend the grammar, so that
. The product type is not to be defined in terms of the other types, but taken as its own, primitive type constructor. Then you can use angle brackets to write values, thus:
. Then you need to write the new typing rules for products.
The reason we decided you can't implement pair/fst/snd using just arrow types is that the pairs must take either a selector of type
and return an
, or a selector of type
, and return a
. But how can they do both? What type would you give to the pair?
One thing that's confusing us a bit is the type variables. In STLC, there are no polymorphic types. So, a function can't have a type
, for example. The type variables are really a template for the sorts of functions we can construct. In the meeting insisted that the
in one function's type was not the same as the
in another function's type. But I was wrong. They are the same because our type
, however chosen, applies to all instances in the template - that is, the signatures of all the functions.
Let's look at the proposed types of the functions:
But then, for pair to work,
has to match both type
. It's not possible that they represent two distinct types.
On the other hand, suppose we're using the polymorphic lambda calculus, where each function can have its own separately quantified variables. Then we can make it work:
Now when we apply a pair to fst, pair's type
will unify with
, which will also unify with type
. When we apply a pair to snd, pair's type
will unify with
, which will also unify with type
. The pair is polymorphic, with type
, which lets it unify type
with either type
each time it is applied.
Hope to see you next time, when we'll go over all the exercises!