equi-recursive, not unlike my face
Feb. 22nd, 2015 08:40 pmThe usual story (e.g. TAPL chapter 20) is that either:
I'm looking at this now because the "All Your Evaluation Order" draft currently has no rolls and unrolls in the source language, which led me to write in the draft that it's "equi-recursive", which led me to go back to TAPL to make sure I'm talking about it correctly. And now I guess I'm not, because I don't intend to wave a mace around just so I can declare that two types connected only by some isomorphism are "equal".
If I don't get this sorted, I'm just going to start rolling around: the draft's target language does have "roll", and the value of saying "ha ha bidirectional typing doesn't need any silly explicit 'rolls' in the source language" is low thanks to some other design decisions I've made, so silly explicit "rolls" are The Construction to Which No One Will Object. (I have no implementation of any of the four type systems who have walked into thisbardraft, anyway, so it shouldn't matter too much if the source language is clunky in this respect.)
- You have explicit "roll" and "unroll" term constructors (or "fold" and "unfold" if, unlike a cat, you don't enjoy rolling around on the ground) to introduce and eliminate the μ connective. This means that μα. 1 + α is definitely not the same type as [(μα.1+α) / α](1 + α) = 1 + (μα. 1+α): the type μα. 1 + α is inhabited by
roll (inj1 ())
(but not by inj1()) and 1 + (μα. 1+α) is inhabited by inj1(), but not by roll (inj1 ()). And then you call what you have "iso-recursive", because (μα. 1 + α) ≠ 1 + (μα. 1 + α), though there is an isomorphism between them. Or… - You don't have "roll" and "unroll", so you make μα. A(α) ~definitionally equal~ to A(μα. A(α)), meaning that you can't tell them apart, they're just different ways of notating exactly the same type.
I'm looking at this now because the "All Your Evaluation Order" draft currently has no rolls and unrolls in the source language, which led me to write in the draft that it's "equi-recursive", which led me to go back to TAPL to make sure I'm talking about it correctly. And now I guess I'm not, because I don't intend to wave a mace around just so I can declare that two types connected only by some isomorphism are "equal".
If I don't get this sorted, I'm just going to start rolling around: the draft's target language does have "roll", and the value of saying "ha ha bidirectional typing doesn't need any silly explicit 'rolls' in the source language" is low thanks to some other design decisions I've made, so silly explicit "rolls" are The Construction to Which No One Will Object. (I have no implementation of any of the four type systems who have walked into this