These are chat archives for scalajp/functional

14th
Jun 2016
taku0
@taku0
Jun 14 2016 12:14
Functionalではないのでここで良いのかわかりませんが、“illegal cyclic reference involving trait E”とか“class graph is not finitary because type parameter T is expansively recursive”とかのエラーメッセージについてなにかご存知でしょうか。
Java Generics are Turing Completeという論文( https://arxiv.org/abs/1605.05274 )があって、その中のコンパイルが止まらない型の例を単純化してJavaとScalaで書いてみました。そうしたところ、use-site varianceを使うと前者のエラーが出て、declaration-site varianceを使うと後者のエラーが出ました。
https://gist.github.com/taku0/4335f65eb20a54fb965fff58fd582878
Kota Mizushima
@kmizu
Jun 14 2016 20:39
実は自分も、use-site varianceの例、Kotlinで書いてみようとしたのですが
error: this type parameter violates the Non-Expansive Inheritance Restriction
interface E<T> : N<N<in E<in T>>>
            ^
こういう型エラーになります
Non-Expansive Inheritance Restrictionという語感からは、なんか型のサイズが膨らむような継承は許さないという制限っぽい感じがしますが
Kota Mizushima
@kmizu
Jun 14 2016 20:44
class graph is not finitary because type parameter T is expansively recursive”
どうも、似たようなメッセージですね…
illegal cyclic reference involving trait Eは
なんか、EがE自身を継承しているかのように見えているっぽいエラーですね…
Kota Mizushima
@kmizu
Jun 14 2016 20:49
実は、Java Genericsで例のコードが許されるのが逆に特殊なのではないかという気がしています…。
interface E<T> : N<N<in E<in T>>>
これは、E<T> : N< ... > を解決するには、E<in T>を具体化する必要があって、E<in T>を具体化するには、さらに、E<T>を具体化する必要があって…という感じになるのが、許されない、といった感じのような。
というか、これはKotlinの話なので、ちょっとスレ違いですね。
ただ、なんかKotlinもScalaも似たような制限を設けているような印象を受けます。
Kota Mizushima
@kmizu
Jun 14 2016 20:56
class graph is not finitary because type parameter T is expansively recursive
これについては、
stackoverflowに同様の質問がありました
Java Generics are Turing Completeからも参照されている
On Decidability of Nominal Subtyping with Variance
Kota Mizushima
@kmizu
Jun 14 2016 21:01
SLSにちょうどそのものずばりの記述があるのを見つけました
It is a static error if the inheritance closure of a class type consists of an infinite number of types. (This restriction is necessary to make subtyping decidable1).
どうも、Scala Genericsと(Kotlinも?)はKennedyとPierceの、サブタイピングを決定可能にするためのチェックを実装していて
Java Genericsはそれを実装していない、という話になる気がしてきました。
Kota Mizushima
@kmizu
Jun 14 2016 21:34
Kennedy and Pierceの07の論文は以前斜め読みしただけなので、何故これでいいのかはまだよくわかっていません…
Kota Mizushima
@kmizu
Jun 14 2016 21:53
なんか調べながら継ぎ足して書いていったので全然まとまりがないですが、参考になれば。