F# and statically checked union cases

Question

Soon me and my brother-in-arms Joel will release version 0.9 of Wing Beats. It's an internal DSL written in F#. With it you can generate XHTML. One of the sources of inspiration have been the XHTML.M module of the Ocsigen framework. I'm not used to the OCaml syntax, but I do understand XHTML.M somehow statically check if attributes and children of an element are of valid types.

We have not been able to statically check the same thing in F#, and now I wonder if someone have any idea of how to do it?

My first naive approach was to represent each element type in XHTML as a union case. But unfortunately you cannot statically restrict which cases are valid as parameter values, as in XHTML.M.

Then I tried to use interfaces (each element type implements an interface for each valid parent) and type constraints, but I didn't manage to make it work without the use of explicit casting in a way that made the solution cumbersome to use. And it didn't feel like an elegant solution anyway.

Today I've been looking at Code Contracts, but it seems to be incompatible with F# Interactive. When I hit alt + enter it freezes.

Just to make my question clearer. Here is a super simple artificial example of the same problem:

type Letter = 
    | Vowel of string
    | Consonant of string
let writeVowel = 
    function | Vowel str -> sprintf "%s is a vowel" str

I want writeVowel to only accept Vowels statically, and not as above, check it at runtime.

How can we accomplish this? Does anyone have any idea? There must be a clever way of doing it. If not with union cases, maybe with interfaces? I've struggled with this, but am trapped in the box and can't think outside of it.

Answer 1

Strictly speaking, if you want to distinguish between something at compile-time, you need to give it different types. In your example, you could define two types of letters and then the type Letter would be either the first one or the second one.

This is a bit cumbersome, but it's probably the only direct way to achieve what you want:

type Vowel = Vowel of string
type Consonant = Consonant of string
type Letter = Choice<Vowel, Consonant>

let writeVowel (Vowel str) = sprintf "%s is a vowel" str
writeVowel (Vowel "a") // ok
writeVowel (Consonant "a") // doesn't compile

let writeLetter = function
  | Choice1Of2(Vowel str) -> sprintf "%s is a vowel" str
  | Choice2Of2(Consonant str) -> sprintf "%s is a consonant" str

The Choice type is a simple discriminated union which can store either a value of the first type or a value of the second type - you could define your own discriminated union, but it is a bit difficult to come up with reasonable names for the union cases (due to the nesting).

Code Contracts allow you to specify properties based on values, which would be more appropriate in this case. I think they should work with F# (when creating F# application), but I don't have any experience with integrating them with F#.

For numeric types, you can also use units of measure, which allow you to add additional information to the type (e.g. that a number has a type float<kilometer>), but this isn't available for string. If it was, you could define units of measure vowel and consonant and write string<vowel> and string<consonant>, but units of measure focus mainly on numerical applications.

So, perhaps the best option is to rely on runtime-checks in some cases.

[EDIT] To add some details regarding the OCaml implementation - I think that the trick that makes this possible in OCaml is that it uses structural subtyping, which means (translated to the F# terms) that you can define discriminated union with some mebers (e.g. only Vowel) and then another with more members (Vowel and Consonant).

When you create a value Vowel "a", it can be used as an argument to functions taking either of the types, but a value Consonant "a" can be used only with functions taking the second type.

This unfrotunately cannot be easily added to F#, because .NET doesn't natively support structural subtyping (although it may be possible using some tricks in .NET 4.0, but that would have to be done by the compiler). So, I know understand your problem, but I don't have any good idea how to solve it.

Some form of structural subtyping can be done using static member constraints in F#, but since discriminated union cases aren't types from the F# point of view, I don't think it is usable here.

Answer 2

It looks like that library uses O'Caml's polymorphic variants, which aren't available in F#. Unfortunately, I don't know of a faithful way to encode them in F#, either.

One possibility might be to use "phantom types", although I suspect that this could become unwieldy given the number of different categories of content you're dealing with. Here's how you could handle your vowel example:

module Letters = begin
  (* type level versions of true and false *)
  type ok = class end
  type nok = class end

  type letter<'isVowel,'isConsonant> = private Letter of char

  let vowel v : letter<ok,nok> = Letter v
  let consonant c : letter<nok,ok> = Letter c
  let y : letter<ok,ok> = Letter 'y'

  let writeVowel (Letter(l):letter<ok,_>) = sprintf "%c is a vowel" l
  let writeConsonant (Letter(l):letter<_,ok>) = sprintf "%c is a consonant" l
end

open Letters
let a = vowel 'a'
let b = consonant 'b'
let y = y

writeVowel a
//writeVowel b
writeVowel y

Answer 3

My humble suggestion is: if the type system does not easily support statically checking 'X', then don't go through ridiculous contortions trying to statically check 'X'. Just throw an exception at runtime. The sky will not fall, the world will not end.

Ridiculous contortions to gain static checking often come at the expense of complicating an API, and make error messages indecipherable, and cause other degradations at the seams.

Answer 4

Classes?

type Letter (c) =
    member this.Character = c
    override this.ToString () = sprintf "letter '%c'" c

type Vowel (c) = inherit Letter (c)

type Consonant (c) = inherit Letter (c)

let printLetter (letter : Letter) =
    printfn "The letter is %c" letter.Character

let printVowel (vowel : Vowel) =
    printfn "The vowel is %c" vowel.Character

let _ =
    let a = Vowel('a')
    let b = Consonant('b')
    let x = Letter('x')

    printLetter a
    printLetter b
    printLetter x

    printVowel a
//    printVowel b  // Won't compile

    let l : Letter list = [a; b; x]
    printfn "The list is %A" l

Answer 5

Thanks for all the suggestions! Just in case it will inspire anyone to come up with a solution to the problem: below is a simple HTML page written in our DSL Wing Beats. The span is a child of the body. This is not valid HTML. It would be nice if it didn't compile.

let page =
    e.Html [
        e.Head [ e.Title & "A little page" ]
        e.Body [
            e.Span & "I'm not allowed here! Because I'm not a block element."
        ]
    ]

Or are there other ways to check it, that we have not thought about? We're pragmatic! Every possible way is worth investigating. One of the major goals with Wing Beats is to make it act like an (X)Html expert system, that guides the programmer. We want to be sure a programmer only produces invalid (X)Html if he chooses to, not because of lacking knowledge or careless mistakes.

We think we have a solution for statically checking the attributes. It looks like this:

module a = 
    type ImgAttributes = { Src : string; Alt : string; (* and so forth *) }
    let Img = { Src = ""; Alt = ""; (* and so forth *) }
let link = e.Img { a.Img with Src = "image.jpg"; Alt = "An example image" }; 

It has its pros and cons, but it should work.

Well, if anyone comes up with anything, let us know!

Answer 6

You can use inline functions with statically-resolved type parameters to yield different types depending on context.

let inline pcdata (pcdata : string) : ^U = (^U : (static member MakePCData : string -> ^U) pcdata)
let inline a (content : ^T) : ^U = (^U : (static member MakeA : ^T -> ^U) content)        
let inline br () : ^U = (^U : (static member MakeBr : unit -> ^U) ())
let inline img () : ^U = (^U : (static member MakeImg : unit -> ^U) ())
let inline span (content : ^T) : ^U = (^U : (static member MakeSpan : ^T -> ^U) content)

Take the br function, for example. It will produce a value of type ^U, which is statically resolved at compilation. This will only compile if ^U has a static member MakeBr. Given the example below, that could produce either a A_Content.Br or a Span_Content.Br.

You then define a set of types to represent legal content. Each exposes "Make" members for the content that it accepts.

type A_Content =
| PCData of string
| Br
| Span of Span_Content list
        static member inline MakePCData (pcdata : string) = PCData pcdata
        static member inline MakeA (pcdata : string) = PCData pcdata
        static member inline MakeBr () = Br
        static member inline MakeSpan (pcdata : string) = Span [Span_Content.PCData pcdata]
        static member inline MakeSpan content = Span content

and Span_Content =
| PCData of string
| A of A_Content list
| Br
| Img
| Span of Span_Content list
    with
        static member inline MakePCData (pcdata : string) = PCData pcdata
        static member inline MakeA (pcdata : string) = A_Content.PCData pcdata
        static member inline MakeA content = A content
        static member inline MakeBr () = Br
        static member inline MakeImg () = Img
        static member inline MakeSpan (pcdata : string) = Span [PCData pcdata]
        static member inline MakeSpan content = Span content

and Span =
| Span of Span_Content list
        static member inline MakeSpan (pcdata : string) = Span [Span_Content.PCData pcdata]
        static member inline MakeSpan content = Span content

You can then create values...

let _ =
    test ( span "hello" )
    test ( span [pcdata "hello"] )
    test (
        span [
            br ();
            span [
                br ();
                a [span "Click me"];
                pcdata "huh?";
                img () ] ] )

The test function used there prints XML... This code shows that the values are reasonable to work with.

let rec stringOfAContent (aContent : A_Content) =
    match aContent with
    | A_Content.PCData pcdata -> pcdata
    | A_Content.Br -> "<br />"
    | A_Content.Span spanContent -> stringOfSpan (Span.Span spanContent)

and stringOfSpanContent (spanContent : Span_Content) =
    match spanContent with
    | Span_Content.PCData pcdata -> pcdata
    | Span_Content.A aContent ->
        let content = String.concat "" (List.map stringOfAContent aContent)
        sprintf "<a>%s</a>" content
    | Span_Content.Br -> "<br />"
    | Span_Content.Img -> "<img />"
    | Span_Content.Span spanContent -> stringOfSpan (Span.Span spanContent)

and stringOfSpan (span : Span) =
    match span with
    | Span.Span spanContent ->
        let content = String.concat "" (List.map stringOfSpanContent spanContent)
        sprintf "<span>%s</span>" content

let test span = printfn "span: %s\n" (stringOfSpan span)

Here's the output:

span: <span>hello</span>

span: <span><br /><span><br /><a><span>Click me</span></a>huh?<img /></span></span>

Error messages seem reasonable...

test ( div "hello" )

Error: The type 'Span' does not support any operators named 'MakeDiv'

Because the Make functions and the other functions are inline, the generated IL is probably similar to what you would code by hand if you were implementing this without the added type safety.

You could use the same approach to handle attributes.

I do wonder if it will degrade at the seams, as Brian pointed out contortionist solutions might. (Does this count as contortionist or not?) Or if it will melt the compiler or the developer down by the time it implements all of XHTML.