News for hackers. Stuff that matters.
Re:Relation Between Type Theory, Category Theory and Logic by Kutta on Saturday July 11, 2015 @05:35AM (#9869171)
Another addendum to the discussion, from an angle more relevant to computer programmers: if we find a computational meaning for the univalence axiom, then it'll be a crazy nuclear weapon of generic programming and code generation.

The univalence axiom says that two types are equal if we can convert their values back and forth (without loss of information). For example, one Boolean type may be defined as an enum containing True and False. But we could rename the values to Foo and Bar and it would be still a fine implementation, because it's easy to convert between the two representations. We can imagine more far-fetched representations too, with more complicated conversion functions.

But in type theory, if two types are equal, then we can freely substitute one for another in any context! For example, if we have a function "Bool -> Bool", and we know that Bool is equal to Bool2, then we can coerce the function to type "Bool2 -> Bool2".

Imagine a complex program that uses a complex piece of data type. If we can provide a correct conversion function to another type (i. e. prove that the type is equivalent to another one), then the univalence axiom can take the conversion function and our program as input, and spits out a new program that uses the new data type, and also preserves all properties of the program. By our current standards of generic programming, this is just insane!

Now, the issue is that currently we don't actually have a computational interpretation for the univalence axiom, so the above magic doesn't yet work. But there is meaningful progress towards that, and there are already some experimental implementations that can do some magic, for example this one:

https://github.com/mortberg/cubicaltt

Re:Relation Between Type Theory, Category Theory and Logic by YorkshireSeason on Saturday July 11, 2015 @05:49AM (#9869203)
What is the state of the art of the research on the computational interpretation of univalence? What's working, what's not working? I seem to remember that A Jeffrey said not too long ago that he had a working interpretation.
Re:Relation Between Type Theory, Category Theory and Logic by gallabytes on Saturday July 11, 2015 @01:23PM (#9870658)
A lot of work was going into the cubical model, but IIRC they realized it was a dead end about a month and a half ago. Right now the most promising work looks to be formalizing the set theoretic model in NuPRL.
Re:Relation Between Type Theory, Category Theory and Logic by Kutta on Saturday July 11, 2015 @01:39PM (#9870752)
Could you give pointers wrt cubical model being a dead end? As yet I've heard nothing about this.
Re:Relation Between Type Theory, Category Theory and Logic by doall on Sunday July 12, 2015 @04:52PM (#9874921)
Re:Relation Between Type Theory, Category Theory and Logic by igravious on Saturday July 11, 2015 @05:59AM (#9869224)
When you think about it we do have a computational meaning and interpretation for the univalence axiom. Your very comment was such an exposition!

What we perhaps don't have is an automated implementation of your exposition. What you're talking about is typecasting where all the terms of one type map to all the terms of another type. And that once shown this the machine could perform type substitution kind of like how type inference works now. (And maybe the machine wouldn't always have to be shown??) Neat idea. Automatic type inference is pretty powerful. Automatic type substitution could be just as powerful perhaps.

Re:Relation Between Type Theory, Category Theory and Logic by tmvphil on Saturday July 11, 2015 @08:59AM (#9869600)
I must be missing something.

A proof that Bool and Bool2 are equal is a bijection f :: Bool -> Bool2. So given any g :: Bool -> Bool we have (f . g . f^-1) :: Bool2 -> Bool2. So it seems trivial.

Re:Relation Between Type Theory, Category Theory and Logic by Kutta on Saturday July 11, 2015 @11:10AM (#9870018)
A more interesting example: substitute natural numbers with binary trees. After all, they're equivalent. Now univalence would have to implement the binary tree analogue for every function on naturals, in a way that preserves semantics with respect to our conversion function.
Re:Relation Between Type Theory, Category Theory and Logic by jules on Saturday July 11, 2015 @10:14AM (#9869828)
Yes, that's pretty much it. Doing this systematically for all types including dependent types that quantify over Bool, as well as for user defined higher inductive types is another matter.
Re:Relation Between Type Theory, Category Theory and Logic by kazinator on Saturday July 11, 2015 @09:31AM (#9869694)
In C, you can convert back and forth between void * and some integer type, aliased as intptr_t since C99, so they must be equal under the univalence axiom.

Ah, "nuclear weapon" ... gotcha!

Re:Relation Between Type Theory, Category Theory and Logic by cbd1984 on Saturday July 11, 2015 @04:11PM (#9871376)
> The univalence axiom says that two types are equal if we can convert their values back and forth (without loss of information).

So strings are equivalent to everything, and vice-versa.

> Now, the issue is that currently we don't actually have a computational interpretation for the univalence axiom

JSON? Sexps?

Re:Relation Between Type Theory, Category Theory and Logic by rndn on Saturday July 11, 2015 @12:29PM (#9870387)
Doesn't the halting problem pose an obstacle in deciding whether two types act in an equivalent way (similar to how the equivalence between two programs is undecidable)?
Re:Relation Between Type Theory, Category Theory and Logic by eli_gottlieb on Saturday July 11, 2015 @01:37PM (#9870737)
No. Homotopy Type Theory is a total language, so even type-level programming simply has to terminate, or the proof-checker won't accept it.

Proving that nontrivially recursive programs terminate can be a bugger.

Re:Relation Between Type Theory, Category Theory and Logic by jonsterling on Saturday July 11, 2015 @02:16PM (#9870935)
You do not in general decide whether two types are equivalent. You prove it...
Re:Relation Between Type Theory, Category Theory and Logic by gallabytes on Saturday July 11, 2015 @01:21PM (#9870650)
Why would it do that? Univalence is unrelated to the halting problem.

What the univalence axiom says is that you can treat types you have proven isomorphic as equal.