HOFs

HOFs with Dynamic Apply

The idea of dynamic apply is to have a tree that will self-specialize when unrolled in templates.

DynApply[F](f: F, a1: F.T1): F.R

While HOFs get compiled to specific types:

val f1 = {(x: Int) => x+1 }: F$41
val f2 = {(x: Int) => x+1 }: F$42

FunctionTemplate will treat DynApply depending on the following cases:

1. if F is generic: as a uninterpreted function,
2. if F is instantiated with a concrete HOF type, e.g. F$41: as the corresponding static body

Main Idea

This works well when passing closures to function calls, as types will get specialized when unrolling:

def apply[T1, T2, F](f: F, a: T1): T2 = DynApply(f, a)

within the context of apply, f() is typed F which is generic and unknown, so DynApply(f, a) will be treated like an uninterpreted function.

When invoking apply with a concrete closure:

apply(f1: F$41, 12)

FunctionTemplate will instantiate apply for its type parameters, and will be able to specialize DynApply

def apply[Int, Int, F$41](f: F$41, a: Int): Int = { x => x + 1 }(a)

Issues

Disambiguation

While passing HOFs is possible, other uses of HOFs are problematic because they generally do not allow type-disambiguation:

def test(a: Int) = {
  val f1 = { (x: Int) => x + 1 } : F$43
  val f2 = { (x: Int) => x - 1 } : F$44
  val fun = if (a>0) f1 else f2
  DynApply(fun, a)
} ensuring { _ != 0 }

Type specialization will not allow us to handle this case as fun will not get its type refined to either F$43 or F$44 depending on a. As a consequence, DynApply will remain uninterpreted and test will not verify.