Toward a possible specialization scheme

[kyouko-taiga]

In the last team meeting we sketched a possible scheme to handle algorithm specialization that sounds worth exploring. We noted that to fit the constraints of Hylo's type system, we should perhaps take inspiration from dynamic dispatch and rely on partial evaluation to compute as many choices as possible ahead of time.

Looking at the documentation of many algorithms in the STL (e.g., std::partition), we can observe that many specialization opportunities can be determined at the point where an algorithm is defined. In a fully dynamic system, one way to take advantage of these opportunities would be to simply test whether or not a value satisfies the conditions necessary to apply a specialization. For example, in Python:

def suffix(xs, n):
  """
  Returns a slice with the `n` last elements of `xs`.

  - Complexity: O(1) if `xs` is a RandomAccessCollection. Otherwise, O(*n*)
    where *n* is the length of `xs`.
  """
  if isinstance(xs, RandomAccessCollection):
    return xs.slice_from(xs.position_offset(xs.end, -n))
  else:
    d = 0
    i = j = xs.start
    while j != xs.end:
      j = xs.position_after(j)
      if d >= n:
        i = xs.position_after(i)
      else:
        d += 1
    return xs.slice_from(i)

The test isinstance(xs, RandomAccessCollection) is essentially expressing a specialization option. If the test succeeds, we know that we can specialize the implementation to compute a result more efficiently than using the "slow path".

We could try to apply the same idea to Hylo:

subscript suffix<T is Collection>(xs: T, n: Int) -> T.Slice {
  inline if T is RandomAccessCollection {
    yield xs[xs.position(xs.end, offset_by: -n)...]
  } else {
    ...
  }
}

The construct inline if T is RandomAccessCollection { ... } else { ... } (tentative syntax) expresses a "dynamic" test on the conformances of T. It is a little special, though, because Hylo doesn't gather all possible conformances witness of a generic parameter. So the fact that the condition is inline also informs the compiler that a witness of RandomAccessCollection could be used. Because it doesn't appear in the signature, however, this witness is not necessary to type check the function. In other words, we can call suffix with an instance of a type that only satisfies Collection. If that type additionally satisfies RandomAccessCollection, then the test will succeed and the specialization will be applied.

From there we can imagine using partial evaluation with monomorphization to determine at compile-time whether or not the test will indeed succeed and drop the unspecialized branch.

I can see two interesting advantages of this approach:

1. It works within the constraints of our implicit resolution algorithm. That's because we get a closed set of conformances to resolve. If that set is open, the issue is that there is no way for resolution to determine whether it has exhausted all possible "better" results that might be more expensive to compute than the ones already found.
2. It works across resilience boundaries. That's because we can gather all the witnesses that we found and look for the ones we're interested in at run-time. Again, that is a consequence of the closed-world assumption.

There's no free lunch, though. This mechanism won't specialize an algorithm based on "unforeseen" opportunities, i.e., opportunities that were not explicitly stated somewhere in the definition.

[tothambrus11]

I think it makes sense if an algorithm defines a closed set of specializations. The standard library should define the most common traits that can make algorithms more or less efficient, and it's likely that new algorithms won't need to add new abstractions. I think it's a good practice to ask the implementer of an algorithm to think about the optimization opportunities, and to specify or create the necessary abstractions. If somebody has an idea for an even more efficient version, given some different abstractions, they can either

• contribute to the library and make this available to the whole ecosystem
• make it a separate algorithm, calling the base implementation except for the additional cases. I'm wondering whether this can be implemented efficiently.