chaource: (Default)
[personal profile] chaource
I'm trying to find a simple proof of parametricity theorems, without using relations. I hoped that I can use dinatural transformations https://en.wikipedia.org/wiki/Dinatural_transformation directly and prove that any purely functional code of type P[A, A] -> Q[A, A] is a dinatural transformation. However, after starting to write up a proof, I ran into a snag: dinatural transformations do not compose. For example, this paper shows some conditions for them to compose https://drops.dagstuhl.de/opus/volltexte/2018/9700/pdf/LIPIcs-CSL-2018-33.pdf But it seems that I can't restrict programs to those conditions. So I'm stuck.

Profile

chaource: (Default)
chaource

February 2026

S M T W T F S
123 45 67
8 910 11121314
151617181920 21
22232425262728

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Feb. 23rd, 2026 01:36 am
Powered by Dreamwidth Studios