Nature of value restriction

Introduction

Value restriction is an error that firstly makes a direct hit in the brain of non-prepared developer. It has no straight analogues in the majority of mainstream languages and thus very confusing. Fortunately error message produced by compiler contains comprehensive solution. However IMO good developer cannot use the tool without having a knowledge how it works under the hood. Otherwise programming becomes some sort of magic… This is not the way of Jedi.

Let’s start from the very beginning. In addition to other useful and interesting features F# supports parametric polymorphism. This means that we can define data types or functions that handle all arguments in the uniform way without depending on its actual type. For example:

// declare type parameters explicitly
let len<'T> (l : 'T list) = List.length l // 'T list -> int
// F# type inference mechanism infers most generic type 
let len2 l = List.length l // 'T list -> int

let l1 = len [1;2;3]
let l2 = len ["1";"2";"3"]

let l3 = len2 [1;2;3]
let l4 = len2 ["1";"2";"3"]

Len and Len2 are polymorphic functions; they can operate on arbitrary lists.

In addition to polymorphic functions and data types F# allows to declare polymorphic values, the most well-known example is empty list.

let nil = [] // 'a list
let a = 1::nil // int list
let b = "1"::nil // string list

In the sample above nil acts as a value of int list and string list. Another piece of code, at that time with option:

let none = None // 'a option
let intRes = defaultArg none 1 // int
let stringRes = defaultArg none "1" // string

Everything is cool and safe, but note – we’ve used only immutable values. The following sample is hypothetical, it doesn’t compile (due to value restriction) but nicely demonstrate the potential problems when mutability and side effects are allowed.

let v = ref None

Imagine that this piece of code is valid and v has type ref option<’T>. Then next few harmless statements will cause crash of application in runtime.

do v := Some 1
let r = defaultArg !v "A" // kaboom!!1 (we take int value from reference cell and try to treat it as a string)

Type checker thinks that these statements are perfectly correct because v is polymorphic. Luckily F# doesn’t let this happen and it is achieved by the value restriction.

Value restriction

The idea behind the solution is pretty simple; we need to divide all let bindings into two groups: first – that can be polymorphic and second – that should be bound to one particular type. The principle of splitting is based on the syntactic definition of values, automatic generalization is performed only on syntactic functions and on simple immutable values. All other bindings are not classified as values and so cannot be automatically generalized, basically compiler will suffer from lack of sufficient type information in a non-generic construct. Some general samples:

// applying polymorphic function to polymorphic value
let v = id []
// partial application
let map_id = Seq.map id

// create object with constructor inferring of type arguments 
type A<'T>() = class end 
let v1 = A<_>()

// create object omitting type arguments
type A<'T>() = class end 
let create<'T> = A<'T>()
let a = create

Note: these samples cover all cases from the MSDN library. Also there is an error in MSDN article: code from case 1 compiles and executes without any problems.

Taming value restriction

As we now know what causes value restriction then we have a number of solutions on the pockets.

1. Compiler doesn’t have all necessary information regarding types of the expression – we can give him a hint by annotating types explicitly

   let v : int list = id []
   let map_id : string list -> string seq = Seq.map id
   
   type A<'T>() = class end 
   let v1 = A<int>()
   
   let create<'T> = A<'T>()
   let a = create<string>

   Simple solution but non-efficient in general cases - we lose polymorphism

2. It is possible to convert non-value to value (syntactic function) by performing eta-conversion

   // added fake unit argument
   let v () = id []
   // added l (list) argument
   let map_id l = Seq.map id l

3. Sometimes value restriction can be removed by reordering code elements so missing type information can be obtained from latter usage.

   // comments annotates operations that helps type inference engine
   
   let v = id []
   let intList  = 1::v // cons operation 
   
   let map_id = Seq.map id
   let res = map_id [1;2;3] // particular type of list
   
   type A<'T>() = 
       let mutable v = Unchecked.defaultof<'T>
       member x.Value 
           with set(value) = v <- value
       
   let a = A<_>()
   a.Value <- 10 // type of property (and of entire type) is inferred from assigned value

   Note: This approach is often cannot be used in FSI sessions due to specific of FSI (type for input expressions should be inferred immediately).

4. F# standard library offers very interesting possibility to run generalization process by applying GeneralizableValue attribute to so-called type functions. Type function is let binding with generic arguments and empty argument list. F# spec defines designation of type functions:

   Type functions are typically used for:

   • Pure functions that compute type-specific information based on the supplied type arguments
   • Pure functions whose result is independent of inferred type arguments, e.g. empty sets and maps

   Type function can be annotated either with RequireExplicitTypeArgumentsAttribute (generic arguments should be set explicitly) or GeneralizableValueAttribute (generic arguments will be inferred).

   type A<'T>() = class end
   [<GeneralizableValue>]
   let create<'T> = A<'T>()
   let r = create
   printfn "%s" (r.GetType().FullName) 

   Combination of type function and GeneralizableValueAttribute can be very confusing. Imagine:

   [<GeneralizableValue>]
   let none<'T> : 'T option ref = ref None

   The fact that none can be used without type parameters makes it appear like simple value. Don’t let this view fool you – this is function that returns new ref to None on every call.

   printfn "%O" (Option.isNone !none) // true
   none := Some(1)
   printfn "%O" (Option.isNone !none) // true