Live data from Hacker News

So you want to learn type theory

purelytheoretical.com

21–30 of 51 posts

Re: So you want to learn type theory

#21
post #4
post #3

Ask yourself why. You want to do CS, prove theorems, do theoretical research? Then, by all means, go for it! It's hip and you use a functional language to write software? Well... It's probably just a whim. But sure, give it a try.

Well, of you want do implement a type system it could help too.

The academic type theory mentioned in this post is not really terribly important to implementing type systems for general purpose languages. There's this growing divide between the engineering discipline of type systems in general languages and the pure theory people who seem only interested in theorem provers and constructive math.

Re: So you want to learn type theory

#22
post #3

Ask yourself why. You want to do CS, prove theorems, do theoretical research? Then, by all means, go for it! It's hip and you use a functional language to write software? Well... It's probably just a whim. But sure, give it a try.

So I think you're right that you should have a good reason. Fashion isn't enough. Don't learn TT cause its "cool", that would be stupid.

For FP, tho.. I would say that you'll be a better functional programmer by knowing TT, even if you don't have a typed language. And if you do have a typed language, you'll want to understand your type system, so learning TT gives you the tools to do that properly.

But there's more than just that. Types offer a lot to the programmer from a practical perspective. Forget the whole thing about using types to prove your code works. You can do that, you can do certified programming if you want. Learn Coq, it's great for that. But types offer you something else:

    *** types help you figure out what the right program is ***
This is something that is often ignored or overlooked, but it's very important. Conor McBride (who's work you might want to look into once you know some TT) talks about this a lot.

A relatively trivial, but easy-to-understand example of this would be the simple programming problem of writing a program that can take a pair of type `A * B` (where `` is the pair product) and return a pair of type `B A`. That is, the flips its argument's elements around. Ok this is simple and we all know what the program is, right, but let's do a little programming in Agda to see how types help you here.

We'll start with a type declaration for the function, and the LHS of an equation that defines the function:

    swap :: A * B -> B * A
    swap p = {! !}0
Notice I put in this funny thing `{! !}0`. This is called a "hole": it's a part of the program that's missing. The 0 indicates its identity (this is hole 0). If we put the cursor in the hole, we can ask Agda to tell us about the hole, and it'll reply:

    Goal: B * A
    Context:
      p : A * B
The goal is the type of the value we have to supply for the hole, the context is all the variables in scope, together with their types.

Now, still with the cursor in the hole, we can ask Agda to pattern match on `p` and split the equation into as many patterns as it can. Because we have types, Agda knows all of the constructors that a type has, so it can automatically fill in the patterns for us. Since pairs have only one constructor, we simply get a slightly more complicated equation:

    swap :: A * B -> B * A
    swap (x , y) = {! !}0
Now let's again ask Agda about the hole:

    Goal: B * A
    Context:
      x : A
      y : B
Notice: `p` is gone, because we matched on it, and instead we have `x` and `y`, new variables binding the elements of the pair, and their types.

Now let's ask Agda to try filling in the hole a little bit. We can tell Agda to refine the hole, and because it knows the goal is a pair type, and pairs have exactly one constructor, it can chose that constructor to fill in part of the program for us:

    swap :: A * B -> B * A
    swap (x , y) = ({! !}1 , {! !}2)
Now we have two new holes, with goal types B and A respectively, and the same contexts as before. We can again ask Agda to work on these holes, and it will fill in:

    swap :: A * B -> B * A
    swap (x , y) = (y , x)
And we're done, we have a definition. And notice: the only code we wrote was to specify the type of `swap`, and put in an initial equation. The rest of the program came from Agda looking at the types, and then doing stuff based on that. This is a simple example, but it's exemplary of the "conversational" back and forth between the programmer and the type checker that you can get in a strongly typed program, where the types can actually help you FIND the right program.

Just as another more obnoxious example, here's the the type for an induction principle for lists (also called dependently typed "fold", or dependently typed "reduce", or whatever):

    listInduction : (A : Set) (P : List A -> Set)
                 -> P []
                 -> (forall (x : A) (xs : List A) -> P xs -> P (x :: xs))
                 -> forall (xs : List A) -> P xs
    
    listInduction A P n c xs = {! !}0
You can do the same thing as before, button mashing until you have no more holes, with this, and you get the right answer. In fact, there are exactly two right answers, and you can get both depending on a choice of which mashing you do. At no point do you actually have to figure out yourself that the following program is a solution:

    listInduction A P n c []        = n
    listInduction A P n c (x :: xs) = c x xs (listInduction A P n c xs)
because the type FORCES that to be one of only two solutions. This kind of ability to button-mash and get a correct solution has actually lead people to compare dependently typed programming to playing a video game.

The moral is: with strong types, the types HELP you, rather than smack you on the knuckles when you've messed up. So there really is something beyond just fashion and whim. It's actually practical!

Re: So you want to learn type theory

#23
post #12

Earlier quoted context omitted.

No, don't ask yourself why. Just learn. It's one human activity that never requires a reason

What I meant is it would be impractical to pick one special topic of CS to study just because it happens to be a mode of the day. It's like deciding to study number theory ("because, you know, cryptography!") in isolation instead of following a sensible math curriculum ("I'm not particularly interested in math") and learning the discipline as it was meant to be learned. In short, I can't think of a "type system speci…

Type theory specialists outside of CS usually fit under the banner of "Logician". Thats why they go under your radar :)

Re: So you want to learn type theory

#24
post #6

what about categorial semantics? hahaha!!!

Walk away now. Type Theory derailed my PhD studies. Seduced by constructivism, Curry-Howard, Martin-Löf and especially Girard's Proofs and Types, I wasted two years and subsequently abandoned my postgraduate studies. It's comp. sci. flavoured esoteric nonsense.

Re: So you want to learn type theory

#25
post #21
post #4

Earlier quoted context omitted.

Well, of you want do implement a type system it could help too.

The academic type theory mentioned in this post is not really terribly important to implementing type systems for general purpose languages. There's this growing divide between the engineering discipline of type systems in general languages and the pure theory people who seem only interested in theorem provers and constructive math.

This is really not true at all. Unless what you mean by "implementing type systems for general purpose languages" is a sort of weak, generally useless type system that punishes rather than helps.

This is ESPECIALLY false of Pfenning and co's work, which is aimed specifically at understanding how to apply type theoretic techniques to the design of PLs, so that you get a PL with exactly the sort of stuff you want.

I added a link to the page to PFPL, which is an entire book on how to implement programming languages using type theoretic tools. It even has sections on OO programming, if you're into that sort of thing. It's all the same toolkit, in the end.

Re: So you want to learn type theory

#26
post #16
post #14

Earlier quoted context omitted.

Type theory is a framework for doing logic that predates computers as we know them. If you have used first-order predicate logic before (e.g. ∀x∀y(P(f(x))→¬(P(x)→ Q(f(y),x,z)))), it performs a similar role to type theory and is the same sort of mathematical thing, it just has different properties. Logical frameworks are interesting to programmers and computer scientists because logical systems and programming languag…

> It concerns itself with identifying and understanding the core structures common to a large number of mathematical objects and operations such as the one shared by multiplication, the cartesian product, least common multiple, logical conjunction (&&), and structs (or record types) in programming. This structure is usually referred to as the categorical product. This sounds more like universal algebra ( http://www.e…

Category theory is about categories,. One notion which makes sense in the context of a category is the categorical product (http://en.wikipedia.org/wiki/Product_%28category_theory%29). All the examples given are examples of categorical products within suitable categories [e.g., Cartesian product within the category of sets and functions between them (amounting to multiplication of cardinals, if one just cares about the action on objects), least common multiple within the category of positive integers ordered by divisibility (a partial ordering being just a special kind of category), logical conjunction within the category of truth values (which can be thought of as sets with at most one element), and structs or record types in the category whose objects are the types of your favorite programming language and morphisms are the programs between them].

Re: So you want to learn type theory

#27
post #5
post #3

Ask yourself why. You want to do CS, prove theorems, do theoretical research? Then, by all means, go for it! It's hip and you use a functional language to write software? Well... It's probably just a whim. But sure, give it a try.

To be clear, most theoretical computer science research is not type theory. Not even close to it either.

Even most PL research is not type theory; it is its own field.

Re: So you want to learn type theory

#28
post #7

What's Type Theory and how's it different from Set Theory and Category Theory?

I want to disagree a little bit with chas here and just say that type theory as we know it today emerged out of a different, post-computer tradition than old-school Russellian type theory. Modern type theory comes arguably from Martin-Löf and the FP domain. As for what is type theory vs. set theory vs. category theory, I'd put it this way: type theory is a flavor of proof theory built on computational justification o…

How would you feel about something like

    type theory : "computing" :: FOL : set theory
where I mean to say "computing" as generally as you like.

Re: So you want to learn type theory

#29
post #3

Ask yourself why. You want to do CS, prove theorems, do theoretical research? Then, by all means, go for it! It's hip and you use a functional language to write software? Well... It's probably just a whim. But sure, give it a try.

So I think you're right that you should have a good reason. Fashion isn't enough. Don't learn TT cause its "cool", that would be stupid. For FP, tho.. I would say that you'll be a better functional programmer by knowing TT, even if you don't have a typed language. And if you do have a typed language, you'll want to understand your type system, so learning TT gives you the tools to do that properly. But there's more t…

Understanding the general ebb and flow of construction/induction is such a powerful technique for thinking about FP. Any time I'm stuck programming now my two questions are (1) do I have the right data available and, then, (2) what things should I be inducting over?

Re: So you want to learn type theory

#30
post #3

Ask yourself why. You want to do CS, prove theorems, do theoretical research? Then, by all means, go for it! It's hip and you use a functional language to write software? Well... It's probably just a whim. But sure, give it a try.

So I think you're right that you should have a good reason. Fashion isn't enough. Don't learn TT cause its "cool", that would be stupid. For FP, tho.. I would say that you'll be a better functional programmer by knowing TT, even if you don't have a typed language. And if you do have a typed language, you'll want to understand your type system, so learning TT gives you the tools to do that properly. But there's more t…

Reminds of how in basic physics, knowing the units of the result you're looking for helps you find the correct answer.

Eg : if you're computing a speed ( m/s), then you'd better divide something that has a distance unit by something that has a time unit.

Post reply on HN