Avatar
omochimetaru 8/4/2020 2:04 AM
2つのプロトコルを使って循環定義しててもなりそう
2:10 AM
プロトコル成約周りでコンパイラのバグをたくさん楽してきたけどやってもやっても新しい問題がみつかってきたけど
2:10 AM
これは背景にこの問題が決定不能だからっぽい、みたいな事を書いている
2:11 AM
We are also aware of examples where we don't manage to canonicalize types properly, causing miscompiles and crashes. We've been fixing these gradually over time, but we continue to discover more problems as we fix them. This was a strong hint that the underlying approach was not correct, which is why I spent some time thinking about the fundamentals of this problem. Indeed, we can now see that the reason we have struggled with correctness in this area of the language is that a solution is impossible in the general case.
2:18 AM
型を要素、型の中の型を参照する . オペレータを 関係 とする半群を考えると「語の問題」という既知の決定不能問題を含むことがわかる みたいな話の流れかな
2:20 AM
protocol Impossible { associatedtype A : Impossible associatedtype B : Impossible associatedtype C : Impossible associatedtype D : Impossible associatedtype E : Impossible where A.C == C.A A.D == D.A B.C == C.B B.D == D.B C.E == E.C.A D.E == E.D.B C.C.A == C.C.A.E }
2:21 AM
func isEqual<A>(_: A, _: A) -> Bool func foo<T : Impossible>(_: T) { let x: T = ... let y: T.A = ... let z: T.B.A.B = ... isEqual(y, z) }
2:21 AM
↑こんな感じで、 T: Impossible を起点に作れる型 (ABCDEの並び) が
2:22 AM
同じ型を指してるかどうか判定しないといけない (isEqualの型チェック) ときに
2:22 AM
この Impossible なケースで無理らしい
2:23 AM
令和になりました. 決定不能問題ギャラリー第12弾は「半群の語の問題」です. 有限表示半群において,生成元からなる2つの文字列が同じ元を表すかどうかは決定不能になります. https://t.co/98dOvD34X0 #たのしいけいさんろん
2:24 AM
ちょっと違うけど Tseitin半群 と同じ置換関係を持ってるように見える