Higher-order functions in the API?

[tomsmeding]

Loose Haskell lambdas that the user writes are invisible to the tracing done in this library, but the moment the user tries to store a function inside an array, their code will be rejected. A question we should ask is: do we even want to support this? If we don't need to support arrays of functions, then as long as we use a tracing-based API, the library will never see a function value to differentiate.

If we do want to support this, here are some things to think about:

• Frontend: using NBE, we can transparently support function values in arrays without preventing the user from using Haskell lambdas and application directly. In a sense, we abuse NBE, because the usual point of NBE is to get normalisation, whereas here the normalisation is accidental and unwanted, but we can't not get it with a tracing API. (Experiments)
• Differentiation:
  • What to do in the first place? I recall some talk about an additional rank, but not sure what it was for.
  • How to avoid large overheads from missing vectorisation? Will a full source transform, you could do closure conversion first, so that you can track which function values might actually have different code and which will run the same code, just with different closures; this would then allow you to still vectorise in certain circumstances. With tracing, however, this might be harder. (Remember the importance of vectorisation stems from wanting the trace to be small, and not grow (much) with the size of the arrays.)

@Mikolaj feel free to edit this if you want to add stuff