Skip to content

Instantly share code, notes, and snippets.

@jack-pappas
Last active August 29, 2015 14:05
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save jack-pappas/48f83f6f1887fdcf7028 to your computer and use it in GitHub Desktop.
Reproduction case for F# 3.0 (and possibly newer) type inference bug
// Created by Jack Pappas
// This code is a reproduction case for an F# 3.0 / 3.1 compiler bug related
// to type parameter/variable propagation.
// To compile this code, create a new F# application project, reference the
// 'FParsec' NuGet package, then paste this code into the Program.fs created for
// the project.
module internal TypeVariableRepro =
open FParsec
open FParsec.Primitives
open FParsec.CharParsers
//
let punctuation<'T> : Parser<char, 'T> =
anyOf "()[]{}," <?> "punctuation"
//
let symbolic<'U> : Parser<char, 'U> =
anyOf "~'!@#$%^&*-+=|\\:;<>.?/" <?> "symbolic"
//
let alphanum<'V> : Parser<char, 'V> =
lower <|> digit <|> pchar '_' <|> pchar '\'' <?> "alphanum"
//
let token<'W> : Parser<string, 'W> =
//
many1Chars symbolic
//
<|> many1Chars alphanum
// Or, a single punctuation character
<|> (punctuation |>> string)
// Error string
<?> "token"
(* Part 1:
The value below does not use an explicit type variable. It uses the 'token' value,
which does have a type variable ('W), so the F# type inference algorithm should infer a
fresh type variable on 'tokenWithWhitespace', which would then be used when instantiating
the 'token' value.
However, if you hover the mouse over the 'tokenWithWhitespace' identifier, IntelliSense shows
that the type of the value is inferred as:
Parser<string, 'Foo>
This doesn't make sense -- where is 'Foo coming from? The 'tokenWithWhitespace' value
is only used within the expression bound to 'tokenWithParens', so it must be propagating
from there. Renaming the type variable and type annotation of 'tokenWithParens' to
something else, e.g., 'Baz, then hovering the mouse over the 'tokenWithWhitespace'
identifier again shows the type is now inferred as:
Parser<string, 'Baz>
Finally, I noticed one other interesting aspect of this bug. The 'tokenWithParens' value
has an explicit type parameter and a type annotation using the explict type parameter.
If you rename the type parameter to 'Baz but leave the type annotation as Parser<string, 'Foo>,
the error message on 'tokenWithParens' disappears and a new error message appears on
'tokenWithWhitespace':
The value 'tokenWithWhitespace' has been inferred to have generic type
val internal tokenWithWhitespace : FParsec.Primitives.Parser<string,'_Foo>
Either make the arguments to 'tokenWithWhitespace' explicit or, if you do not intend for it to be generic, add a type annotation.
Given the order in which the F# type inference algorithm works, the type annotation of a value
needs to be satisfied by the expression being bound to the value. The error message seems to
indicate that the type parameter is propagating from the type annotation for 'tokenWithParens'
into the environment and attaching itself to 'tokenWithWhitespace'.
*)
let tokenWithWhitespace = spaces >>. token .>> spaces
//
let lexer<'Bar> : Parser<string list, 'Bar> =
(* Part 2:
Comment out the first line of code below and uncomment the second;
the error message currently attached to the 'tokenWithParens' value (below) will
move up to the 'lexer' identifier instead; both uses of 'tokenWithWhitespace' in 'tokenWithParens'
get a new error message:
Type mismatch. Expecting a
Parser<string,'Foo>
but given a
Parser<string,'Bar>
The type ''Foo' does not match the type ''Bar'
This provides another bit of evidence that the typing environment is being corrupted
during the type-checking process. Adding an explicit type parameter 'Z to 'tokenWithWhitespace'
and applying it to token gives a binding that looks like this:
let tokenWithWhitespace<'Z> = spaces >>. token<'Z> .>> spaces
Once 'tokenWithWhitespace' has an explicit type parameter like this, all error messages
disappear and compilation will succeed.
*)
many (spaces >>. token .>> spaces)
//many tokenWithWhitespace
//
let private tokenWithParens<'Foo> : Parser<string, 'Foo> =
(between (pstring "(") (pstring ")") tokenWithWhitespace) <|> tokenWithWhitespace
[<EntryPoint>]
let main argv =
printfn "%A" argv
0 // return an integer exit code
@dsyme
Copy link

dsyme commented Oct 9, 2014

This appears to be a manifestation of the value restriction - I don't think it's a bug. The fact that 'Foo escapes is reported with the "escapes its scope" message. One approach is to make tokenWithWhitespace generic, e.g.

  let tokenWithWhitespace<'Foo> : Parser<string, 'Foo> = spaces >>. token .>> spaces

to make it properly generic.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment