What is the best way to pass generic function that resolves to multiple types

Question

For the background: It's a variation on functional DI. Following Scott's post I wrote an interpreter. The twist is that my interpreter is generic and parametrized based on what you feed to it.

For testing purposes I'd like to pass another interpreter in, and therein lies the rub - how can I? Here's the simplified outline of the problem:

let y f =
    let a = f 1
    let b = f 2L
    (a,b)

f is my generic interpreter, but here it is obviously constrained by the first use to int -> 'a. In this simplified scenario I could just pass the interpreter twice, but in my actual implementation the type space is rather large (base type x3 output types).

Is there some F# mechanism that would let me do that, w/o too much overhead?

Answer 1

Please look at Crates.

Here is a quick snippet describing the crux of what you want to accomplish. I believe this snippet is valuable in it helps teach us how we can formally reason about using F# and other ML type systems, by using mathematical language. In other words, it not only shows you how, it teaches you the deep principle of why it works.

The issue here is that we have reached a fundamental limitation of what is directly expressible in F#. It follows that the trick to simulating universal quantification is, therefore, to avoid ever passing the function around directly, instead hiding the type parameter away such that it cannot be fixed to one particular value by the caller, but how might one do that?

Recall that F# provides access to the .NET object system. What if we made our own class (in the object-oriented sense) and put a generic method on that? We could create instances of that which we could pass around, and hence carry our function with it (in the form of said method)?

// Encoding the function signature...
// val id<'a> : 'a -> 'a
// ...in terms of an interface with a single generic method
type UniversalId = abstract member Eval<'a> : 'a -> 'a

Now we can create an implementation which we can pass around without the type parameter being fixed:

// Here's the boilerplate I warned you about.
// We're implementing the "UniversalId" interface
// by providing the only reasonable implementation.
// Note how 'a isn't visible in the type of id -
// now it can't be locked down against our will!
let id : UniversalId =
  { new UniversalId with
      member __.Eval<'a> (x : 'a) : 'a = x
  }

Now we have a way to simulate a universally quantified function. We can pass id around as a value, and at any point we pick a type 'a to pass to it just as we would any value-level argument.

EXISTENTIAL QUANTIFICATION

There exists a type x, such that…

An existential is a value whose type is unknown statically, either because we have intentionally hidden something that was known, or because the type really is chosen at runtime, e.g. due to reflection. At runtime we can, however, inspect the existential to find the type and value inside.

If we don’t know the concrete type inside an existentially quantified type, how can we safely perform operations on it? Well, we can apply any function which itself can handle a value of any type – i.e. we can apply a universally quantified function!

In other words, existentials can be described in terms of the universals which can be used to operate upon them.

This technique is so useful that it is used in datatype generic programming library TypeShape, which allows you to scrap your boilerplate .NET reflection code, as well as MBrace and FsPickler for "packing existential data types". See Erik Tsarpalis' slides on TypeShape for more on "encoding safe existential unpacking in .NET" and encoding rank-2 types in .NET.

A reflection helper library like TypeShape also intuitively should cover most if not all your use cases: dependency injection needs to implement service location under the hood, and so TypeShape can be thought of as the "primitive combinator library" for building dependencies to inject. See the slides starting with Arbitrary Type Shapes: In particular, note the Code Lens data type:

type Lens<'T,'F> =
{
    Get : 'T -> 'F
    Set : 'T -> 'F -> 'T
}

Finally, for more ideas, you may care to read Don Stewart's PhD dissertation, Dynamic Extension of Typed Functional Languages.

We present a solution to the problem of dynamic extension in statically typed functional languages with type erasure. The presented solution retains the benefits of static checking, including type safety, aggressive optimizations, and native code compilation of components, while allowing extensibility of programs at runtime.

Our approach is based on a framework for dynamic extension in a statically typed setting, combining dynamic linking, runtime type checking, first class modules and code hot swapping. We show that this framework is sufficient to allow a broad class of dynamic extension capabilities in any statically typed functional language with type erasure semantics.

Uniquely, we employ the full compile-time type system to perform runtime type checking of dynamic components, and emphasize the use of native code extension to ensure that the performance benefits of static typing are retained in a dynamic environment. We also develop the concept of fully dynamic software architectures, where the static core is minimal and all code is hot swappable. Benefits of the approach include hot swappable code and sophisticated application extension via embedded domain specific languages.

Here are some coarse-grained design patterns Don lays out for future engineers to follow:

1. Section 3.6.3: Specializing Simulators Approach.
   • Demonstrates how to apply program specialization techniques to Monte-Carlo simulation of polymer chemistry. This approach demonstrates how you can "inject" specialized code to address so-called "peephole optimizations".

and a general chart to help frame the "tower of extensibility":

Answer 2

You can't do this in F# with functions. Functions lose genericity when passed as values.

However, F# does have a mechanism for doing it anyway, albeit a bit awkwardly: interfaces. Interface methods can be generic, so you can use them to wrap your generic functions:

type Wrapper =
    abstract member f<'a> : 'a -> 'a

let y (w: Wrapper) = 
   let a = w.f 1 
   let b = w.f 2L 
   (a, b)

let genericFn x = x

// Calling y:
y { new Wrapper with member __.f x = genericFn x }

The downside is, you can't go back to higher-order functions, lest you lose genericity. You have to have interfaces all the way down to the turtles. For example, you can't simplify the instance creation by abstracting it as a function:

let mkWrapper f = 
   // no can do: `f` will be constrained to a non-generic type at this point
   { new Wrapper with member __.f x = f x }

But you can provide some convenience on the other side. At least get rid of type annotations:

type Wrapper = abstract member f<'a> (x: 'a): 'a

let callF (w: Wrapper) x = w.f x

let y w = 
   let a = callF w 1 
   let b = callF w 2L 
   (a,b)

(NOTE: there may be minor syntactic mistakes in the above code, as I'm writing on my phone)