Language Oriented Programming in F#

Last Tuesday I gave a talk to the .NET Developers Association entitled Language Oriented Programming in F# . You can find a video of the presentation here*. This essay is the written version of that presentation, which unfortunately doesn’t translate to the web so well. In fact, I’m going to go ahead and apologize now for this crazy-long post.

 

What is Language Oriented Programming

Let me start by saying that Language Oriented Programing (LOP) is a nebulous term, like meta-programming. Rather than trying to pin it down concretely, I’ll define it in broad terms and then provide many examples.

To understand what LOP is first you must understand the concept of a Domain Specific Language or DSL. A DSL is a programming language designed to solve problems within a narrowly-defined problem domain. (Opposed to a General Purpose programming language, like C# or F#, which can solve problems in any domain.) An example of a DSL would be Excel. To write a formula that adds the contents of two cells you write “= A1 + B1”, no need for defining data types, functions, conversion routines, etc. The Excel language has the concept of a spreadsheet cell baked into the language, so you don’t need to describe what ‘A1’ means in terms of anything else. In C# on the other hand, you can’t write ‘A1’ you need to write something like “MasterSheet.GetCell(new CellObject(Row = “A”, Column = 1));”.

The main advantage of a DSL is that the code is always much simpler than its general purpose programming language counterpart. With a DSL you don’t need to write the ‘scaffolding’ you normally would in order to express your ideas, since all the key concepts of the problem domain are baked into the language.

DSLs have two major drawbacks however. First, DSLs force you to learn a new language. Second, somebody needs to define that language and build the compiler for it.  For simple problem domains these drawbacks aren’t much of a problem. But if you wanted your DSL do describe the business rules for your entire company however, then you can see how DSLs fail to scale. If you are interested in building DSLs however Toolkits do exist.

So what is LOP then? To provide a great example, let me introduce a project called FsUnit over on Google code. It is a simple library for writing Unit Tests in F#, but rather than the standard ‘Assert.IsTrue(x)’ you can write:

 // Equality
1 |> should (equal 1)

// Checking existence in a collection
[| "item1" |] |> should (contain "item1")
[| "item1" |] |> should (notContain "item2")

// Size of a collection
personList |> should (have 4 "people")Some text matches a regular expression: 

// RegEx patterns
"test infected" |> should (matchThePattern "inf")

// Other primitives
true |> should (be True)
false |> should (notBe True)
"" |> should (be Empty)
"a string" |> should (notBe Empty)
null |> should (be Null)
anObj |> should (notBe Null)

 

FsUnit allows you to write F# code, but using words and concepts in a different language. (In this case, English.) Armed with this example I will define what LOP is: Language Oriented Programming is a style of programming that tries to produce code that looks like it came from a Domain Specific Language but is still valid in a general purpose programming language.

The rest of this essay will provide examples of LOP in F# and how using LOP results in simpler code that better expresses the problem at hand. I’ll my examples along three major themes:

  • Abstract Representation.  Features in F# that allow you to represent domain-specific concepts in your F# code without needing to introduce a new layer of abstraction.
  • Concrete Representation. Features in F# that allow you to describe your problem in another language and load that into F#.
  • Computational Representation. Finally I’ll go into features in F# that enable you to write code to process concepts in some other language without resorting to a third, more specialized language.

 

Part I – Abstract Representation

One problem facing programmers using modern Object Oriented languages is how to represent concepts in their language. C# only has facilities to express concepts in terms of objects and their behaviors, which makes it difficult to accurately express abstract ideas. Having a class for ‘Cat’ with methods Meow() and Purr() makes sense. But how would you write the concept of ‘Happiness’ in C#? Would there be methods ‘CheerSomethingUp(object thing)’?

By Abstract Representation I’m talking about the ability to represent concepts in your F# code as naturally as possible.

Type Abbreviations

The first feature I'll go into is Type Abbreviations. In F# you have the ability to create an alias for another type, which at compile time will be replaced with the underlying core type. Meaning that type abbreviations only exist at design-time. Using Type Abbreviations you can write code in terms of problem-domain concepts without needing to introduce custom types. For example I'll create a type alias for 'int' called CustomerID. Now if I write a function that takes type CustomerID I know exactly what it expects, rather than a function taking type 'int’ and me needing to guess at what that integer represents.

type CustomerID = int

let alice = 98123
let bob = 78435 : CustomerID

// With the type annotation the value 'customer' appears as to
// have type 'CustomerID' but at compile time that is replaced
// with 'int'. You can pass both alice and bob to function
// getCustomerOrders.
let getCustomerOrders (customer : CustomerID) =
printfn "%d has ordered 5 items."customer

Type abbreviations are especially helpful when you are dealing with more complex generic types. Consider Dictionary<string, string>. It has some use, but from just the type signature you have no idea what the key, value pairs correspond to. But with type abbreviations you can call it something more meaningful.

 open System.Collections.Generic
type TeamCityLookup = Dictionary<string, string>

// A TeamCityLoop is a better description for the type than Dictionary<string, string>
let teamLookup = new TeamCityLookup()
teamLookup.Add("Mariners", "Seattle")
teamLookup.Add("Reds",     "Cincinati")
teamLookup.Add("Dodgers",  "Los Angeles")

teamLookup.["Mariners"]

 

Discriminated Unions

Consider the following C# code used to express the concept of a card suit.

 enum CardSuit
{
    Club,
    Spade,
    Diamond,
    Heart
}

While the code looks simple and clear, it actually introduces many problems because enumerations alone aren't sufficient for expressing the idea of a mutually-exclusive set of values. It is easy to write C# code that violates the principle that a card can only have one possible suit.

 CardSuit invalid1 = CardSuit.Club | CardSuit.Heart;
CardSuit invalid2 = (CardSuit) (-1);

In order to write the concept of a card suit in C# you need to write some slightly more complex code. You can see how in chapter 21 of Effective Java . In F# though, you can express this concept without any fuss.

 type Suit = 
    | Diamonds 
    | Hearts
    | Spades 
    | Clubs

// An instance of 'Suit' can only have one of four possible values
let printSuitName suit =
    match suit with
    | Diamonds -> printfn "Suit is a Diamond"
    | Hearts   -> printfn "Suit is a Heart"
    | Spades   -> printfn "Suit is a Spade"
    | Clubs    -> printfn "Suit is a Club"

Moreover, in F# Discriminated Unions can also attach data making them much more powerful than enumerations without sacrificing any of their ease of definition.

 // Discriminated Unions can hold data too!
type Card =
    | ValueCard of int * Suit  // Value 2 - 10 and Suit
    | Jack      of Suit
    | Queen     of Suit
    | King      of Suit
    | Ace       of Suit
    | Joker
    
// Simple syntax for defining instances of Disc Unions
let myPokerHand = 
    [ 
        ValueCard(2, Hearts) 
        ValueCard(5, Spades) 
        Joker                
        ValueCard(4, Clubs)  
        Ace(Clubs)
     ]

 

Option Type

Sorry to rag on C# some more, but here’s another instance where .NET adds confusion where there shouldn’t be. Consider the following code where I get an instance of your pet and print its name if you have one.

 Pet yourPet = you.GetPet();

if (yourPet != null)
    Console.WriteLine("You have pet named " + yourPet.Name);

The code looks simple enough. But where in the real world does null exist? Is that in the problem domain? If I asked you if you had a pet wombat would you say ‘null’? No, null is an artifact of the programming language used to represent the absence of something or an uninitialized value. But in LOP we are trying to represent ideas without any overhead. F# has the option type that will represent the concept of nothing in a more natural way.

 type Pet =
    | GoldFish
    | Dog
    | Cat
    
// Takes a 'Person' type and returns an option, of their pet type
let getPetType person =
    match person with
    | Me           -> Some(Dog)
    | SomebodyElse -> Some(GoldFish)
    | You          -> None

If you have a pet Some(…) is returned, meaning there is something. If you don’t have a pet you return None. Another big advantage to the option type is that it communicates intent. If you call the ‘GetPet’ method in C#, it is unclear what the result will be if you don’t have a pet. Will the method throw an exception or simply return null? In F# using the option type means that it will return None should you not have a pet.

 

Pattern Matching

Pattern matching is another way we can express what we mean clearly in code. In C# you can use a switch statement, but that only works on constant values. In F# however, Pattern Matching can do much more than compare a value against a constant. It can, for example, compare against the structure of the data. Here we match against the length of a list:

 // Structure of data
let shortList = ['a'; 'b'; 'c']

let printListLength list =
    match list with
    | []      -> printfn "List is empty"
    | [_]     -> printfn "List has 1 element"
    | [_;_]   -> printfn "List has 2 elements"
    | [_;_;_] -> printfn "List has 3 elements"
    | _       -> printfn "List too long"

In addition, Pattern Matching can also capture variables as part of the match.

 // Match contants and capture variables
let sayHello (first, last) =
    match (first, last) with
    // Match constants
    | "Bill", "Gates"
    | "Steve", "Balmer"
        -> printfn "Steve and Bill, wazzzup!"
    
    // Match first against constant, capture second
    | "Chris", last
        -> printfn "Hello Chris. Your last name is %s" last
    
    // Capture both values
    | first, last
        -> printfn "Hello %s %s" first last

 

Demo

Now that we have the building blocks to represent ideas in F#, we have all the power we need to represent a real world problem in the language of mathematics.

 // This Discriminated Union is sufficient to express any four-function
// mathematical expression.
type Expr =
    | Num      of int
    | Add      of Expr * Expr
    | Subtract of Expr * Expr
    | Multiply of Expr * Expr
    | Divide   of Expr * Expr
    
// This simple pattern match is all we need to evaluate those
// expressions. 
let rec evaluate expr =
    match expr with
    | Num(x)             -> x
    | Add(lhs, rhs)      -> (evaluate lhs) + (evaluate rhs)
    | Subtract(lhs, rhs) -> (evaluate lhs) - (evaluate rhs)
    | Multiply(lhs, rhs) -> (evaluate lhs) * (evaluate rhs)
    | Divide(lhs, rhs)   -> (evaluate lhs) / (evaluate rhs)

// 10 * 10 - 25 / 5
let sampleExpr = 
    Subtract(
        Multiply(
            Num(10), 
            Num(10)),
        Divide(
            Num(25), 
            Num(5)))
        
let result = evaluate sampleExpr

In this simple example we were able to represent and evaluate a four-function mathematical expression using only a discriminated union and a pattern match. You would be hard pressed to write the equivalent C# in as few lines of code because you would need to add additional scaffolding to represent these concepts.

 

Part II – Concrete Representation

Concrete Representation means expressing your problem conceretely in another language and loading that into your F# program. By allowing you to work in both your Domain Specific Language and F#, you can express your problem in specific terms and then do any processing required in F#.

 

fslex and fsyacc

The simplest way to deal with a concrete representation of another language is to build a parser and ‘load it’ just like a compiler. Lex and Yacc have been standard tools for generating parsers for thirty years. FsLex and FsYacc are implementations of Lex and Yacc that generate F# parsers. I won’t go into too much deal here, but if you are interested in learning more refer to my previous blog post.

Lex and Yacc are DSLs for describing compiler parsers and lexers, or tools which break down ‘source’ into a series of tokens and then convert that token stream into an Abstract Syntax Tree. For example, here is the Lex code for converting a string like “10 * 8 + 5.0” into tokens [INT32(10); ASTER; INT32(8); PLUS; FLOAT(5.0)]

 rule tokenize = parse
| whitespace    { tokenize lexbuf }
| newline       { tokenize lexbuf }
// Operators
| "+"            { PLUS }
| "-"            { MINUS }
| "*"            { ASTER }
| "/"            { SLASH }
// Numberic constants
| ['-']?digit+  { INT32 (Int32.Parse(lexeme lexbuf)) }
| ['-']?digit+('.'digit+)?(['e''E']digit+)?   { FLOAT (Double.Parse(lexeme lexbuf)) }
| eof   { EOF }

The corresponding Yacc parser file would look something like this, which would match tokens against grammar productions and create AST nodes.

 Prog:
    | Expr EOF                  { $1 }

Expr: 
    | Expr PLUS Term            { Plus($1, $3) }
    | Expr MINUS Term           { Minus($1, $3) }
    | Term                      { Term($1) }

Term:
    | Term ASTER Factor         { Times($1, $3) }
    | Term SLASH Factor         { Divide($1, $3) }
    | Factor                    { Factor($1) }

Factor:
    | FLOAT                     { Float($1) }
    | INT32                     { Integer($1) }

If none of this Lex and Yacc jazz made sense to you don’t worry. The point is that if you wanted to, there are tools available that will allow you to write F# programs that can parse any other language you want. So if you wanted to write a parser for all mathematical equations (“1^5 + cos(PI)”) you could. If you wanted to parse structured log files, you could. If you wanted to write a parser for F# code so  you could manipulate it in an F# program, you could. With fslex and fsyacc you can write a parser for any domain specific language you want, and load its abstract representation into your F# program.

 

Active Patterns

The next feature I’ll talk about which allows you to convert a concrete representation of a language into F# is Active Patterns. (WhichI’ve blogged about this before.) The easiest way to think about Active Patterns is that they are a way to convert data from one representation to another, typically via a pattern matching.

Active Patterns come in three main flavors: single-case, multi-case, and partial.

 Single-case Active Patterns

Single-case Active Patterns take an input of one type of data and convert it into something else. In the following example we convert strings to integers. Notice the result of the Active Pattern is at the end of the 'match clause’.

 // SingleCase Active Patterns

// Covnert a string to an int
let (|IntValue|) input = Int32.Parse(input)

// Given a string print its integer representation.
let printValue (str : string) =
    match str with
    | IntValue 0 -> printfn "str is zero"
    | IntValue 1 -> printfn "str is one"
    | IntValue 2 -> printfn "str is two"
    
    // Variable capture of AP output
    | IntValue x -> printfn "str is %d" x

Multi-case active Patterns

Multi-case Active Patterns convert the input into one of several types of output, dividing the input space into several regions. For example, we can convert an integer into one of three categories: Odd, Even, or Zero.

 // Multi-Case Active Patterns
let (|Even|Odd|Zero|) x =
    if x = 0       then Zero
    elif x % 2 = 0 then Even
    else                Odd

// Takes an int and prints its status
let printStatus x =
    match x with
    | Zero -> printfn "%d is zero" x
    | Even -> printfn "%d is even" x
    | Odd  -> printfn "%d is odd " x

Partial Active Patterns

Partial Active Patterns are just like Single-case Active Patterns, but they don’t always succeede. In our previous example we converted strings to integers, but a string cannot always be converted into an integer. For example “foo”. Partial Active Patterns use Option types to represent whether or not the data was convertered. Here we will convert strings into either Integers or Floating point numbers.

 // Partial Active Pattern
let (|ToInt|_|) str = 
    let (parsed, result) = Int32.TryParse(str)
    if parsed then Some(result)
    else           None

let (|ToFloat|_|) str = 
    let (parsed, result) = Single.TryParse(str)
    if parsed then Some(result)
    else           None

// Takes a string and prints whether it is an int or float
let parseValue str =
    match str with
    | ToInt   x -> printfn "str is an int with value %d" x
    | ToFloat x -> printfn "str is a float with value %f" x
    | _         -> printfn "str is neither an int nor a float"

Demo

Here is an example of how you can leverage Active Patterns to convert a concrete representation of a language into F#. The example is from a demo from a research paper by Don Syme, Margetson and Gregory Neverov which introduced the concept of Active Patterns. Since code is really complicated, but I’ll just point out the black magic. Given this XML doc we can extract all meaningful information from it, that is attributes and nested elements, in just one line of code.

 // Concrete language
let xmlDoc = 
    let temp = new System.Xml.XmlDocument()  
    let superHerosXmlDoc = 
        "<?xml version=\"1.0\" encoding=\"utf-8\"?>
        <Scene>
            <Sphere r='3' x='4' y='3' z='0' />
            <Intersect>
                <Sphere r='2' x='1' y='0' z='0'/>
                <Intersect>
                    <Sphere r='2' x='4' y='0' z='0'/>
                    <Cube d='1' x='6' y='7' z='8' />
                    <Sphere r='2' x='-3' y='0' z='0'/>
                </Intersect>
                <Cube d='2' x='-2' y='1' z='0'/>
            </Intersect>
        </Scene>
        "
    temp.LoadXml(superHerosXmlDoc)
    temp

// Abstract representation
type GeometricScene =
| Cube      of float * float * float * float
| Sphere    of float * float * float * float
| Intersect of GeometricScene list

// Mach an XML element
let (|Elem|_|) name (inp: #XmlNode) =
    if inp.Name = name then Some(inp)
    else                    None

// Get the attributes of an element
let (|Attributes|) (inp: #XmlNode) = inp.Attributes

// Match a specific attribute
let (|Attr|) attrName (inp: XmlAttributeCollection) =
    match inp.GetNamedItem(attrName) with
    | null -> failwith (attrName + " not found")
    | attr -> attr.Value

// Convert a string to a float
let (|Float|) s = Float.of_string s

// Parses a vector out of an attribute collection
let (|Vector|) inp =
    match inp with
    | (Attr "x" (Float x) & 
       Attr "y" (Float y) & 
       Attr "z" (Float z)) 
        -> (x,y,z)

// Parses a GeometricScene from an XML node
let rec (|ShapeElem|_|) inp =
    match inp with
    // By using nested Active Patterns we can parse all attributes on one line!
    // (Attributes (Attr "r" (Float r))) gets the Attributes of the node, then gets
    // the attribute "r", then finally converts its string value into a float.
    | Elem "Sphere" (Attributes (Attr "r" (Float r) & Vector (x,y,z)))
        -> Some (Sphere (r,x,y,z))
    
    | Elem "Intersect" (ShapeElems(objs))
        -> Some (Intersect objs)
    
    // This is what the cde would look like without nested Active Patterns
    | Elem "Cube" xmlElement
        -> match xmlElement with
           | Attributes xmlElementsAttributes 
               -> match xmlElementsAttributes with
                  | Attr "d" dAttrib & Vector (x, y, z)
                      -> match dAttrib with
                         | Float d -> Some(Cube(d, x, y, z))

    // Did not recognize XmlNode as Shape element
    | _ -> None 

 

While the use of Active Patterns aren’t the easiest thing to read, they certainly allow you to easily convert data.

 

Part III – Computation Representation

This is the last part of Language Oriented Programming and definitely the most complicated. The theme of this essay has been that two languages are better than one; that using a domain-specific description the your problem makes the coding easier. The only thing better than two languages to represent your problem is not having to use three.

Consider the common Forms-Over-Data application. You have a database, CustomerInfo, and you have your application written in C#. With any luck you’re using LOP in your programming and so you can represent your customer entities naturally, but you run into a problem as soon as you try to interface with your database. Namely, having your app talk to the database requires you using another language – SQL.

With Visual Studio 2008 this problem was solved for a few specific scenarios with Linq, but in F# you can solve this problem even more generally.

This final aspect of LOP I’ll talk about is where you write F# code and manipulate the computation which that code represents. In other words, you write some F# code that does something interesting and then manipulate the computation representation of that code to either execute that code in a unique way or convert that code into a different language.

The F# language features Quotations and Workflows will undoubtedly be the subject of numerous articles, blog posts, and maybe even books in the future. So if I do a terrible job explaining what these features do, don’t fret.

Quotations

Writing .NET code is great and all, but the implicit restriction is that your code is executing on computer running the .NET framework. That doesn’t sound like a big requirement, but think for a moment on how limiting that is. If you wanted to write code that executed on your GPU you would have to resort to some other language. Or let’s say you were multiplying two sparce matricies and wanted to optimize out all the zero-multiplications, leading to a more efficent code. You can’t. Because all the code you write in .NET must execute on the .NET platform… or at least it had to before F# came along.

In F# the Quotations feature allows you to get access to the compiler’s representation of a block of code, enabling you to process that code as you wish. For example, you could write a Quotation-to-GPU converter and write programs in F# which could execute on your graphics card. Or, given a function that operates on a sequence of data, convert those operation into SQL code and automatically query the server. (A la DLinq.)

 

I won’t go into details about how the code all works, but I’ll point out the key concepts. First, the funky “<@@ … @@>” code starts a quotation. Anything inbetween the <@@ and @@> is what is ‘quoted’. So the result of <@@ x @@> is the compiler’s representation of x. Second, once you have some quoted data you will can use Active Patterns to convert the compiler’s representation into something more useful. In the simplest example, we will take the quotation of a constant value and use an Active Pattern to convert the compiler’s representation of that into the value itself.

 #light

open Microsoft.FSharp.Quotations
open Microsoft.FSharp.Quotations.Typed
open Microsoft.FSharp.Quotations.Raw

// The compiler represents the code “1” as an Int32 literal.
let quot1 = <@@ 1 @@>

let printQuotation x =
    match x with
    | Int32 v  -> printfn "The quoted code is an int with value %d" v
    | String v -> printfn "The quoted code is a string with value %s" v
    | _        -> printfn "I don't know what x is..."

You can then move onto bigger, more complicated expressions by matching more types of expressions using Active Patterns. Here we break down an entire function.  (The [<ReflectedDefinition>] attribute is required for the function to be used inside of a quotation.)

 // Functions
[<ReflectedDefinition>]
let checkTemp temp =
    if   temp < 60 then printfn "Too cold"
    elif temp > 80 then printfn "Too hot"
    else                printfn "Just right"

let rec printQuotation2 expr =
    match expr with
    | ResolvedTopDefnUse(_,body) 
        -> printfn "The expr is a Top Definition Use..."
           printQuotation2 body

    | Lambda(_, body) 
        -> printfn "The expr is a Lambda..."
           printQuotation2 body
           
    | Cond(_, body, nextCond)
        -> printfn "The expr is a Conditional..."
           printQuotation2 nextCond
           
    | App(info, body) 
        -> printfn "The expr is a function application..."
   
    | _ -> printfn "I don't know what the expr is"

printQuotation2 <@@ checkTemp @@>

Here is an example from Expert F# (Apress, 2007) which uses Quotations to compute the error range for floating point calculations. Given an inexact number such as p = 3.141 +/- 0.001, repeated operations on p will result in a compounded error. Such as p + p = 6.282 +/- 0.002. Given the quotation of a function, the code will walk the compiler’s interpretation of the code and calculate an error estimate.

 // Example from Expert F# by Don Syme, Adam Granicz, and Antonio Cisternino
// Pg. 251

open Microsoft.FSharp.Quotations
open Microsoft.FSharp.Quotations.Typed
open Microsoft.FSharp.Quotations.Raw

type Error = Err of float

// Estimate the error for a given expression, t.
// env is a map of identifiers to their values. E.g., "pi" -> 3.14159
let rec errorEstimateAux t (env : Map<_,_>) =

    match t with
    // If the quoted expression matches the function application of
    // +, -, *, or / calculate the left and right hand sides and
    // compute the resulting error.
    | GenericTopDefnApp <@@ (+) @@> (tyargs,[xt;yt]) ->
        let x, Err(xerr) = errorEstimateAux xt env
        let y, Err(yerr) = errorEstimateAux yt env
        (x + y, Err(xerr + yerr))

    | GenericTopDefnApp <@@ (-) @@> (tyargs,[xt;yt]) ->
        let x, Err(xerr) = errorEstimateAux xt env
        let y, Err(yerr) = errorEstimateAux yt env
        (x - y, Err(xerr + yerr))

    | GenericTopDefnApp <@@ ( * ) @@> (tyargs,[xt;yt]) ->
        let x, Err(xerr) = errorEstimateAux xt env
        let y, Err(yerr) = errorEstimateAux yt env
        (x * y, Err(xerr * abs(x) + yerr * abs(y) + xerr * yerr))

    | GenericTopDefnApp <@@ ( / ) @@> (tyargs,[xt;yt]) ->
        let x, Err(xerr) = errorEstimateAux xt env
        let y, Err(yerr) = errorEstimateAux yt env
        (x / y, Err(xerr * abs(x) + abs(1.0 / y) / yerr + xerr / yerr))

    | GenericTopDefnApp <@@ abs @@> (tyargs,[xt]) ->
        let x,Err(xerr) = errorEstimateAux xt env
        (abs(x), Err(xerr))

    // If the quoted expression introduced a new value. E.g.,
    // let e = 2.71828
    | Let((var,vet), bodyt) ->
        let varv, verr = errorEstimateAux vet env
        errorEstimateAux bodyt (env.Add(var.Name, (varv, verr)))

    | App(ResolvedTopDefnUse(info,Lambda(v,body)),arg) ->
        errorEstimateAux  (MkLet((v,arg),body)) env

    | Var(x) -> env.[x]
    | Double(n) -> (n,Err(0.0))

    | _ -> failwithf "unrecognized term: %A" t

let rec errorEstimateRaw (t : Expr) =
    match t with
    | Lambda(x,t) ->
        (fun xv -> errorEstimateAux t (Map.of_seq [(x.Name,xv)]))
    | ResolvedTopDefnUse(info,body) ->
        errorEstimateRaw body
    | _ -> failwithf "unrecognized term: %A - expected a lambda" t

let rec errorEstimate (t : Expr<float -> float>) = errorEstimateRaw t.Raw

// ----------------------------

[<ReflectedDefinition>]
let poly x = x+2.0*x+3.0/(x*x)

errorEstimate <@ poly @> (3.0, Err(0.1))
// Evaluates to: (9.333333333, Err 0.5821493625)

errorEstimate <@ poly @> (30271.3, Err(0.0001))
// Evaluates to: (90813.9, Err 3.02723)

 

Work flows

Workflows are the most exciting language feature in F#, and represent perhaps the most powerful way to apply LOP in your code. But rather than telling you what they are I’ll build up to it.

Consider this code, which is called a Sequence Expression. It produces a seq of the first 10 integers. The second example is a more complex sequence expression, which uses recursion to walk every file under a given directory. Note the use of recursion requires the ‘yield!’ keyword.

 // Sequence Expressions

// Numbers one through ten
let numbers = seq { for i in 1 .. 10 do
                        yield i }

// All files under a given directory (notice the use of recursion)
open System.IO

let rec allFiles dir = 
    seq {   for file in Directory.GetFiles(dir) do
                yield file
            for subdir in Directory.GetDirectories dir do
                yield! (allFiles subdir) }
            
allFiles @"C:\Windows\System32\"

Just to show that you can do powerful things with Sequence Expressions, here is some code to compute all prime numbers under 1,000. (The Sieve of Eratosthenes in F#.)

 // Complex Sequence Expression
let primesUnder1K = 
    seq { 
        // First prime 
        yield 2 

        let knownComposites = ref (Set.empty)
        
        // Loop through all odd numbers; evens can't be prime 
        for i in 3 .. 2 .. int 1000 do 
            
            // Check if its in our list, if not, its prime 
            let found = (!knownComposites).Contains(i) 
            if not found then 
                yield i 

            // Add all multiples of i to our sieve, starting 
            // at i and irecementing by i. 
            do for j in i .. i .. int 1000 do 
                knownComposites := (!knownComposites).Add(j)
    } 

Seq.take 20 primesUnder1K

So to review, Sequence Expression produce seq objects and are use a seemingly limited subset of the F# language. Simple enough.

Sequence Expressions however are just a specialization of a concept known as Computation Expression or Workflow. The Computation Expression was everything between the curly braces { and }. The ‘seq’ in front was the workflow builder which I’ll come back to in a moment.

So why are Computation Expressions important? Because in F# you can you define how the Computation Expression gets executed by using a builder object. In the previous examples the ‘seq’ builder takes the Computation Expression and produces a sequence of values. But you can implement far more interesting builders. You could for example write a builder that logged every action that was taken, in order to better diagnose a failure in the code. Or even transfer the computation to a different machine and execute the code in the cloud. Computation Expressions / Workflows are a powerful new concept that open up a lot of possibilities for powerful language oriented concepts.

The most practical application of workflows is in asynchronous programming. Normally if you want concurrent code you need to write it with a bunch of callbacks, manage thread states, deal with synclocks, and other unpleasantries. But using F# Asynchronous Workflows, all you need to do is write your code in a Computation Express and pass that computational representation of your code to the Async Workflow object. It will then execute that code doing all the async goo for you. That’s right, in F# you can write async code without even trying.

Here’s an example of an async workflow in F# from Expert F#. (Which for the record is a much better resource for teaching F# than my blog :)

 // Example from Expert F# by Don Syme, Adam Granicz, and Antonio Cisternino
// Pg. 366

open System.Net
open System.IO
open Microsoft.FSharp.Control.CommonExtensions

let museums = ["MOMA",           "https://moma.org/";
               "British Museum", "https://www.thebritishmuseum.ac.uk/";
               "Prado",          "https://museoprado.mcu.es";
               "SAM",            "https://www.seattleartmuseum.org/"]

// Fetch the museum website and print info to the console asynchronously
let fetchAsync (name, url:string) =
    async { do printfn "Creating request for %s..." name
            let req  = WebRequest.Create(url)

            let! resp  = req.GetResponseAsync()

            do printfn "Getting response stream for %s..." name
            let stream = resp.GetResponseStream()

            do printfn "Reading response for %s..." name
            let reader = new StreamReader(stream)
            let! html = reader.ReadToEndAsync()

            do printfn "Read %d characters for %s..." html.Length name }

for (name, url) in museums do
    Async.Spawn (fetchAsync(name,url))

That’s it. Seriously. The code will loop through all the museums specified, and asynchronously download the HTML of their homepages. All the work you needed to was write it inside of a Computation Expression and pass it to an ‘async’ builder. Async.Spawn will take the result and execute it asynchronously.

 

Conclusion

I’ve shown that language features in F# enable Language Oriented Programming and provide all the power you need write succinct code that maps directly to your problem domain. No unnecessary code required. I fully expect that Language Oriented Programming becomes the driving force for F# adoption as developers discover the true expressiveness of the language and leverage these facilities.

 

*Actually, in a poor attempt at humor you’ve been Rick Rolled.