Wednesday, November 26, 2014

Issues with F# type inference

This week I continued my recent code rewrite efforts and was unhappy to note that F#'s type inference is still a bit flaky.

I had written a parser+type inference for an experimental functional language before I wrote my introduction-to-stateful-monads presentation. And although the original code was already lifting state monads (the last part of the presentation), it was doing so in a limited and heavy manner.  One of the ideas I have had for some time was to write an optimizer for specialized monadic code. Therefore, I thought it would be nice to rewrite my code to be fully "state lifting" centric because that would be closer to the type of code I would like to optimize.

To illustrate what I mean, the type inference monadic state has a counter. This counter is incremented to generate new free variables during the type inference. In my rewrite,  I tried to implement this increment function as:
let incVarCounter = liftState varCounter' (mapState inc)
let varCounter' f s = 
  let (r,x') = f s.varCounter
  (r,{s with varCounter=x'})
let mapState f = fun s -> (), f s
let liftState f m = fun s -> f m s 
(hopefully this is correct because I simplified the code for this blog).

varCounter is a field of a record with two type variables. Call it R<'a,'b>.
Unfortunately, the code above is inferred to the following by the F# compiler:
R < obj , obj > -> unit*R< obj , obj >
obj is the generic object type used when the type inference fails to deliver.

On the other hand, add a dummy unit argument to the function, as follow:
let incVarCounter() = liftState varCounter' (mapState inc)
This infers to:
unit -> R<'a,'b> -> unit*R<'a,'b>
which is has the correct type details.

These type details are needed because obj types are unusable. Adding the dummy unit argument is a work around; The question is "why do we still need workarounds for a language that is now at version 4"?  And more esthetically, if I want a monad, I want a monad, not a function that delivers a monad.

No comments: