Dart 中的类型推断......有错误吗？

Question

以下程序在前段时间运行良好。现在类型推断似乎有一个错误。在报告错误之前，我想确保类型推断的问题不是我的错。

该程序是 Scala 13.0 版标准蹦床库 (TailCalls.scala) 的转录本。因此，我假设飞镖程序的正确性。

abstract class TailRec<A> {
  A value;

  A result() {
    TailRec<A> tr = this;
    while (!(tr is _Done<A>)) {
      if (tr is _Bounce<A>) {
        tr = (tr as _Bounce<A>).continuation();
      } else if (tr is Cont) {
        var a = (tr as Cont).a;
        var f = (tr as Cont).f;
        if (a is _Done) {
          tr = f(a.value);
        } else if (a is _Bounce) {
          tr = a.continuation().flatMap<A>(f);
        } else if (a is Cont) {
          var b = a.a;
          var g = a.f;
          tr = b.flatMap<A>((x) => g(x).flatMap<A>(f));
        } else {
          throw new Exception("#1");
        }
      } else {
        throw new Exception("#2");
      }
    }
    return tr.value;
  }

  A compute() {
    TailRec<A> res = this;

    while (!res._isDone) {
      final _Bounce<A> bounce = res;
      res = bounce.continuation();
    }
    _Done<A> done = res;
    return done.value;
  }

  bool get _isDone;



  TailRec<B> map<B>(B Function(A) f) {
    return flatMap((a) => new _Bounce(() => new _Done<B>(f(a))));
  }

  TailRec<B> flatMap<B>(TailRec<B> Function(A) f) {
    if (this is _Done) {
      return new _Bounce(() => f(this.value));
    } else if (this is _Bounce) {
      return new Cont(this, f);
    } else if (this is Cont) {
      Cont<A, B> c = (this as Cont<A, B>);
      return new Cont<A, B>(c.a, (A x) => c.f(x).flatMap(f));  
      /*
      in the application of flatMap the falsely required type is:
        TailRec<B> TailRec.flatMap<B>(TailRec<B> Function(B) f)
      this is at odds with the definition of flatMap
      the correct type given is:
        TailRec<B> Function(A) f
      */
    } else {
      throw new Exception("#3");
    }
  }
}

class Cont<A, B> extends TailRec<B> {
  Cont(this.a, this.f);
  TailRec<A> a;
   TailRec<B> Function(A x) f;
  @override
  bool get _isDone => false;
}

class _Done<A> extends TailRec<A> {
  _Done(this.value);
  @override
  final A value;
  @override
  final bool _isDone = true;
}


class _Bounce<A> extends TailRec<A> {
  _Bounce(TailRec<A> Function()f) {
    this.continuation = f;
  }
  TailRec<A> Function()continuation; 
  @override
  final bool _isDone = false;
}

TailRec<A> done<A>(A x) => new _Done<A>(x);

TailRec<A> tailcall<A>(TailRec<A> continuation()) => new _Bounce(continuation);

flatMap应用中错误要求的类型是：

flatMap<B>(TailRec<B> Function(B) f)

flatMap 的定义显示了正确需要的类型：

flatMap<B>(TailRec<B> Function(A) f) {

因此，正是这应该确定所需的类型。

类型推断错误地得出 'B' 而不是 'A'。

正确给出的类型是：

TailRec<B> Function(A) f

我使用的是 dart 版本 2.4.1

Answer 1

您不能考虑

形式的 Dart 表达式

if (tr is _Bounce) {
  ...
} else if (tr is Cont) {
  ...
} ...

与 Scala 标准库中相应的匹配表达式相当：前者会在第一个块中将 tr 提升为 _Bounce<dynamic>，在第二个块中提升为 Cont<dynamic, dynamic>，等等。

相比之下，Scala 匹配受制于静态分析，这将对模式匹配项执行类型推断，并且它们允许您表示类型参数，即使它们是未知的。

（例如，来自 here uses the type a1, which is the unknown type that Slava called ? here 的 case c: Cont[a1, b1] => Cont(c.a, (x: a1) => c.f(x) flatMap f)）

但是，可以通过使类型可用于静态分析的方式来表达 Scala 库（取自 here）。

请注意，我发现的 Scala 库版本使用 Either，因此我添加了几个框架声明以使生成的代码自包含。

代码如下：

// ------------------------------ Skeleton emulation of Scala standard stuff.

class Either<A, B> {}

class Left<A, B> implements Either<A, B> {
  Left(this.value);
  A value;
}

class Right<A, B> implements Either<A, B> {
  Right(this.value);
  B value;
}

abstract class Option<A> {
  A get value;
  const Option();
  B Function(B Function(A)) fold<B>(B ifEmpty()) =>
      (B f(A a)) => isEmpty ? ifEmpty() : f(value);
  bool get isEmpty;
}

class Some<A> extends Option<A> {
  final A value;
  Some(this.value);
  get isEmpty => false;
}

class _None extends Option<Null /*soon: Never*/ > {
  get value => throw "Attempt to do None.value";
  const _None();
  get isEmpty => true;
}

const None = _None();

// ------------------------------ TailCall.

typedef LazyTailRec<X> = TailRec<X> Function();

abstract class TailRec<A> {
  TailRec<B> map<B>(B Function(A) f) =>
      flatMap((a) => _Call(() => _Done(f(a))));
  TailRec<B> flatMap<B>(TailRec<B> Function(A) f);
  A get result;
  Either<LazyTailRec<A>, A> get _resume;
  B _result1<B>(_Cont<A, B> c);
  Either<LazyTailRec<B>, B> _resume1<B>(_Cont<A, B> c);

  static C _result0<D, C>(TailRec<D> b, _Cont<D, C> c) => b._result1(c);
  static Either<LazyTailRec<C>, C> _resume0<D, C>(
          TailRec<D> b, _Cont<D, C> c) =>
      b._resume1(c);
}

class _Call<A> extends TailRec<A> {
  final LazyTailRec<A> rest;
  _Call(this.rest);
  flatMap<B>(f) => _Cont(this, f);
  get result => rest().result;
  get _resume => Left(rest);
  _result1<B>(c) => rest().flatMap(c.f).result;
  _resume1<B>(c) => Left(() => rest().flatMap(c.f));
}

class _Cont<B, A> extends TailRec<A> {
  TailRec<B> b;
  TailRec<A> Function(B) f;
  _Cont(this.b, this.f);
  flatMap<C>(g) => _Cont(b, (B x) => f(x).flatMap(g));
  get result => TailRec._result0<B, A>(b, this);
  get _resume => TailRec._resume0<B, A>(b, this);
  _result1<C>(c) => b.flatMap((B x) => f(x).flatMap(c.f)).result;
  _resume1<C>(c) => b.flatMap((B x) => f(x).flatMap(c.f))._resume;
}

class _Done<A> extends TailRec<A> {
  final A value;
  _Done(this.value);
  flatMap<B>(f) => _Call(() => f(value));
  get result => value;
  get _resume => Right(value);
  _result1<B>(c) => c.f(value).result;
  _resume1<B>(c) => c.f(value)._resume;
}

TailRec<A> tailcall<A>(TailRec<A> rest) => _Call(() => rest);
TailRec<A> done<A>(A result) => _Done(result);

我们正在考虑使用显式和严格静态检查的方差扩展 Dart（参见 this issue），您可以在类型上添加一些 out 和 inout 修饰符参数得到完全严格的检查，但我相信上面的形式是你今天在 Dart 中可以拥有的最严格检查的形式。

这是一个例子：

// -------------------------------------------------- Test.

TailRec<int> test(int a) => a > 10
    ? tailcall(Some(true).fold(() => test(a - 1))((_) => test(a - 2)))
    : done(-1);

main() => print(test(11).result); // -1.

PS：我并不担心有这个的原始点，即属性某些调用位于 Scala 编译器可以识别并生成跳转的尾部位置比要求； Dart 编译器无论如何都不会这样做，与控制堆栈高度相比，我更感兴趣的是表达输入情况的能力。

Dart 中的类型推断......有错误吗？

Type-inference in Dart ... is there a bug?

type-inference

dart