Recursion Schemes in Dart.

[modulovalue]

I am trying to implement zero-cost recursion schemes in Dart.

I'm using a technique that, I believe, is formally known as type defunctionalization. The theory seems to be much more complex than what's necessary in practice, but I'll be referring to that technique within the context of Dart here as TD.

Using TD we can be more general than what the static type system currently supports and implement first class functors (functors in the functional programming sense).

Furthermore, using TD we can also implement a fixpoint type that allows us to generalize over recursive structures.

In addition to that, TD requires us to have a marker interface for the root of our recursive structures so that we can refer to them on the simulated kind level.

This is enough to implement recursion schemes. Recursion schemes are a way to generalize traversals over recursive structures. The benefits of expressing a problem in terms of recursion schemes are that the implementation becomes much more maintainable because any explicit recursion is removed and, among other things, it becomes clear which traversals can be merged to reduce N separate traversals to just one.

There are three categories of recursion schemes (folds, unfolds and refolds) and each can be expanded to support different problem domains. For simplicity, the code below implements a fold that is known as a catamorphism, but others such as anamorphisms, hylomorphisms and even more involved ones such as futumorphisms and histomorphisms are implementable in Dart as well.

The main issue with the implementation below is that we are forced to introduce a level of indirection via Fix when referring to an Expression that contains members of its own hierarchy. I was hoping that inline classes could help here, but it is not intended (dart-lang/sdk#51564 (comment)) for them to support implements clauses and so they will not be able to implement Fix to make the Fix here zero-cost.

I have tried other things, such as making the members of the expression hierarchy implement Fix themselves, but I always ran into some limitations.

This example code evaluates a simple expression hierarchy by using a catamorphism. Notice how the argument to invoke needs to wrap all expressions in a Fix which I would like to avoid.

Catamorphism 1

void main() {
  print(
    Catamorphism<ForExpression, int, int>(
      fold: (final e) => e.DExpr.match(
        value: (final v) => v.i,
        add: (final a) => a.lhs + a.rhs,
        mult: (final a) => a.lhs * a.rhs,
      ),
      fmap: (final value, final fn) => value.DExpr.match(
        value: (final self) => ExpressionValue(
          i: self.i,
        ),
        add: (final self) => ExpressionAdd(
          lhs: fn(self.lhs),
          rhs: fn(self.rhs),
        ),
        mult: (final self) => ExpressionMult(
          lhs: fn(self.lhs),
          rhs: fn(self.rhs),
        ),
      ),
    ).invoke(
      const Fix(
        unfix: ExpressionMult(
          lhs: Fix(
            unfix: ExpressionAdd(
              lhs: Fix(
                unfix: ExpressionValue(
                  i: 1,
                ),
              ),
              rhs: Fix(
                unfix: ExpressionValue(
                  i: 3,
                ),
              ),
            ),
          ),
          rhs: Fix(
            unfix: ExpressionValue(
              i: 5,
            ),
          ),
        ),
      ),
    ),
  );
}

class Catamorphism<FI, A, B> {
  final KindExpression<FI, A> Function(
    KindExpression<FI, KindFix<ForFix, FI>>,
    B Function(KindFix<ForFix, FI>),
  ) fmap;
  final B Function(KindExpression<FI, A>) fold;

  const Catamorphism({
    required this.fmap,
    required this.fold,
  });

  B invoke(
    final KindFix<ForFix, FI> a,
  ) {
    final KindExpression<FI, KindFix<ForFix, FI>> x = a.DFix.unfix;
    final KindExpression<FI, A> y = fmap(x, invoke);
    final B z = fold(y);
    return z;
  }
}

// Expression
abstract class KindExpression<F, A> {}

extension ExpressionFix<A> on KindExpression<ForExpression, A> {
  Expression<A> get DExpr => this as Expression<A>;
}

abstract class ForExpression {}

extension ExpressionMatcherExtension<F> on Expression<F> {
  Z match<Z>({
    required final Z Function(ExpressionValue<F> a) value,
    required final Z Function(ExpressionAdd<F> a) add,
    required final Z Function(ExpressionMult<F> a) mult,
  }) {
    final _ = this;
    if (_ is ExpressionValue<F>) return value(_);
    if (_ is ExpressionAdd<F>) return add(_);
    if (_ is ExpressionMult<F>) return mult(_);
    throw Exception(
      "Invalid State",
    );
  }
}

abstract class Expression<F> implements KindExpression<ForExpression, F> {}

class ExpressionValue<F> implements Expression<F> {
  final int i;

  const ExpressionValue({
    required this.i,
  });
}

class ExpressionAdd<F> implements Expression<F> {
  final F lhs;
  final F rhs;

  const ExpressionAdd({
    required this.lhs,
    required this.rhs,
  });
}

class ExpressionMult<F> implements Expression<F> {
  final F lhs;
  final F rhs;

  const ExpressionMult({
    required this.lhs,
    required this.rhs,
  });
}

// Fix
abstract class KindFix<F extends ForFix, A> {}

extension KindFixFix<W extends ForFix, F> on KindFix<W, F> {
  Fix<F> get DFix {
    return this as Fix<F>;
  }
}

abstract class ForFix {}

class Fix<A> implements KindFix<ForFix, A> {
  final KindExpression<A, KindFix<ForFix, A>> unfix;

  const Fix({
    required this.unfix,
  });
}

My goal is to eventually add support for recursion schemes to custom code generators and to investigate how I can make using the theory behind recursion scheme fusion practical, but the overhead of the Fix wrapper makes it hard for me to commit to such a solution, because I would like for it to be at least as performant as code that doesn't make use of recursion schemes.

Edit: below is an updated version that uses new features to simplify and make things safer (sealed classes, exhaustive matching, and class modifiers):

Catamorphism 2

void main() {
  print(
    Catamorphism<ForExpression, int, int>(
      fold: (final e) => switch (e.DExpr) {
        ExpressionValue(:final i) => i,
        ExpressionAdd(:final lhs, :final rhs) => lhs + rhs,
        ExpressionMult(:final lhs, :final rhs) => lhs * rhs,
      },
      fmap: (final value, final fn) => switch (value.DExpr) {
        ExpressionValue(:final i) => ExpressionValue(
          i: i,
        ),
        ExpressionAdd(:final lhs, :final rhs) => ExpressionAdd(
          lhs: fn(lhs),
          rhs: fn(rhs),
        ),
        ExpressionMult(:final lhs, :final rhs) => ExpressionMult(
          lhs: fn(lhs),
          rhs: fn(rhs),
        ),
      },
    ).invoke(
      const Fix(
        unfix: ExpressionMult(
          lhs: Fix(
            unfix: ExpressionAdd(
              lhs: Fix(
                unfix: ExpressionValue(
                  i: 1,
                ),
              ),
              rhs: Fix(
                unfix: ExpressionValue(
                  i: 3,
                ),
              ),
            ),
          ),
          rhs: Fix(
            unfix: ExpressionValue(
              i: 5,
            ),
          ),
        ),
      ),
    ),
  );
}

final class Catamorphism<FI, A, B> {
  final KindExpression<FI, A> Function(
    KindExpression<FI, KindFix<ForFix, FI>>,
    B Function(KindFix<ForFix, FI>),
  ) fmap;
  final B Function(KindExpression<FI, A>) fold;

  const Catamorphism({
    required this.fmap,
    required this.fold,
  });

  B invoke(
    final KindFix<ForFix, FI> a,
  ) {
    final KindExpression<FI, KindFix<ForFix, FI>> x = a.DFix.unfix;
    final KindExpression<FI, A> y = fmap(x, invoke);
    final B z = fold(y);
    return z;
  }
}

// Expression
final class KindExpression<F, A> {}

extension ExpressionFix<A> on KindExpression<ForExpression, A> {
  Expression<A> get DExpr => this as Expression<A>;
}

final class ForExpression {}

sealed class Expression<F> implements KindExpression<ForExpression, F> {}

final class ExpressionValue<F> implements Expression<F> {
  final int i;

  const ExpressionValue({
    required this.i,
  });
}

final class ExpressionAdd<F> implements Expression<F> {
  final F lhs;
  final F rhs;

  const ExpressionAdd({
    required this.lhs,
    required this.rhs,
  });
}

final class ExpressionMult<F> implements Expression<F> {
  final F lhs;
  final F rhs;

  const ExpressionMult({
    required this.lhs,
    required this.rhs,
  });
}

// Fix
sealed class KindFix<F extends ForFix, A> {}

extension KindFixFix<W extends ForFix, F> on KindFix<W, F> {
  Fix<F> get DFix {
    return this as Fix<F>;
  }
}

final class ForFix {}

final class Fix<A> implements KindFix<ForFix, A> {
  final KindExpression<A, KindFix<ForFix, A>> unfix;

  const Fix({
    required this.unfix,
  });
}

[eernstg]

This is cool! @modulovalue, thanks for building these bridges between the functional programming community and Dart! (I haven't had a chance to look into the details, I just wanted to respond to the fact that these things are brought up ;-)

[modulovalue]

I have updated the issue description to include an implementation that uses new Dart features. (Class modifiers make recursion schemes via simulated higher kinded types much safer, and sealed classes allow some boilerplate code to be removed.)

I also wanted to leave a pointer to a discussion around monomorphization (dart-lang/site-www#4998 & dart-lang/sdk#52722), because It looks like that topic is important to making such recursion schemes more efficient.

(If it is true that mixins can help with monomorphization, then the implementation in the issue description should use them. However, i think that injecting functions via constructors allows for a clearer presentation, so I chose not to do that.)