Luketopia

A veritable cornucopia of enlightening elucidation

Making XLinq Usable from F#

| Comments

Type providers are often the preferred mechanism for dealing with textual data in F#, but Linq to XML is still a very nice API when you need things to be a bit more dynamic or don’t want to pull in a type provider package. However, due to it’s reliance on implicit conversions, it can be somewhat awkard to work with in F#.

For instance, consider the following XML list of contacts:

<contacts>
    <contact first="John" last="Smith"/>
    <contact first="Susan" last="Jones"/>
</contacts>

In C#, we could parse it and print out the result thusly:

var doc = XDocument.Parse(xml)
foreach(var contact in doc.Element("contacts").Elements("contact"))
{
    Console.WriteLine("First: {0}, Last: {1}",
        contact.Attribute("first").Value
        contact.Attribute("last").Value)
}

A direct port to F#, however, does not compile:

let doc = XDocument.Parse(xml)
for contact in doc.Element("contacts").Elements("contact") do
    printfn "First: %s, Last: %s" 
            (contact.Attribute("first").Value) 
            (contact.Attribute("last").Value)

The reason it doesn’t compile is that the XLinq methods we’re calling don’t actually take strings, they take an XName. The XName type represents a qualified XML name, i.e. the local name and (optionally) the namespace. Rather than provide two overloads for every method, one taking a string and one taking an XName, the XLinq classes provide an implicit conversion from string to XName. Unfortunately this doesn’t work in F# because it doesn’t support custom conversions (implicit or explicit).

Thus, to get it to work, we need to modify it as follows:

let doc = XDocument.Parse(xml)
for contact in doc.Element(XName.Get "contacts").Elements(XName.Get "contact") do
    printfn "First: %s, Last: %s" 
            (contact.Attribute(XName.Get "first").Value) 
            (contact.Attribute(XName.Get "last").Value)

Typing XName.Get everywhere is a bit tedious and something which I would prefer to avoid. Fortunately, this is easy to rectify with a type extension. Type extensions allow us to define extension methods on a type like in C# and VB.NET but also support extension properties (and apparently extension events, since events are just properties in F#). Of course, these special extension members can only be consumed from F#, but that is all we care about for this purpose.

Therefore, I made a little module that you can import into any F# project where you want to be able to use XLinq, because I have wanted to use it in several instances. I started by providing equivalent string overloads for each method taking an XName in the XObject hierachy:

[<AutoOpen>]
module System.Xml.Linq.FSharpExtensions

open System
open System.Runtime.CompilerServices
open System.Xml.Linq

type XNode with
    member this.Ancestors(name) = this.Ancestors(XName.Get name)
    member this.ElementsAfterSelf(name) = this.ElementsAfterSelf(XName.Get name)
    member this.ElementsBeforeSelf(name) = this.ElementsBeforeSelf(XName.Get name)    

type XContainer with
    member this.Descendants(name) = this.Descendants(XName.Get name)
    member this.Element(name) = this.Element(XName.Get name)
    member this.Elements(name) = this.Elements(XName.Get name)

type XElement with
    member this.AncestorsAndSelf(name) = this.AncestorsAndSelf(XName.Get name)
    member this.Attribute(name) = this.Attribute(XName.Get name)
    member this.Attributes(name) = this.Attributes(XName.Get name)
    member this.DescendantsAndSelf(name) = this.DescendantsAndSelf(XName.Get name)
    member this.SetAttributeValue(name, value) = this.SetAttributeValue(XName.Get name, value)
    member this.SetElementValue(name, value) = this.SetElementValue(XName.Get name, value)

Notice that this module has the AutoOpen attribute and is placed directly in the System.Linq.Xml namespace, so that any time that namespaces is opened these methods are automatically available.

After adding the module, my first F# snippet compiles and runs, but there is still something missing. XLinq also provides extension methods to various closed types of IEnumerable<_> so that you can query over collections of XML objects. For instance, suppose we just wanted to retrieve all the last names from our document. We could do the following:

doc.Root.Elements().Attributes(XName.Get "last") 
|> Seq.map (fun a -> a.Value)

This depends on an Attributes() an extension method being defined on IEnumerable<XElement>, but we would like to provide our own method that takes a string rather than an XName. However, F# does not (yet?) allow us to define type extensions for closed generic types. Fortunately, there is a workaround.

In addition to supporting type extensions, F# supports standard extension methods like you have in C# and VB.NET. This is mainly a compatibility feature, and there is no special syntax for defining these in F#. However, if we want to define them we need only provide the Extension attributes that C# and VB.NET add to indicate extension methods. Thus, we expand our module as follows:

[<Extension>]
type XLinqSeqExtensions =
    [<Extension>] static member Ancestors(source:seq<XNode>, name) = source.Ancestors(XName.Get name)
    [<Extension>] static member AncestorsAndSelf(source:seq<XElement>, name) = source.AncestorsAndSelf(XName.Get name)
    [<Extension>] static member Attributes(source:seq<XElement>, name) = source.Attributes(XName.Get name)
    [<Extension>] static member Descendants(source:seq<XContainer>, name) = source.Descendants(XName.Get name)
    [<Extension>] static member DescendantsAndSelf(source:seq<XElement>, name) = source.DescendantsAndSelf(XName.Get name)
    [<Extension>] static member Elements(source:seq<XContainer>, name) = source.Elements(XName.Get name)

Now the code snippet given above will work without the call to XName.Get.

So now that we can read XML much more easily, what about writing? For example, what if we wanted to produce the above XML document using XLinq? Without making any changes, we could do the following:

XElement(XName.Get "contacts",
    XElement(XName.Get "contact",
        XAttribute(XName.Get "first", "John"),
        XAttribute(XName.Get "last", "Smith")),
    XElement(XName.Get "contact",
        XAttribute(XName.Get "first", "Susan"),
        XAttribute(XName.Get "last", "Jones")))

Getting rid of the XName.Get calls in this case is more difficult, because we would need to define an extension constructor. I tried the following:

type XElement with
    new(name, [<ParamArray>] content) = XElement(XName.Get name, content)

type XAttribute with
    new(name, value) = XAttribute(XName.Get name, value)

This doesn’t actually compile, but it parses. The compiler understands what we’re trying to do, but won’t allow such an extension on a type not defined in the same file. It gives the error FS0871: Constructors cannot be defined for this type.

But there is still hope! What if we just defined functions named XElement and XAttribute? It’s possible to have a type and function or value with the same name; for example you have the type string (actually an alias for System.String) and the function string that converts a value to that type. This is permissible in F# because type names and function or value names are used in different contexts.

This means we can just rewrite our constructors as functions:

let XElement(name, [<ParamArray>] content) = new XElement(XName.Get name, content)
let XAttribute(name, value) = new XAttribute(XName.Get name, value)

Alas, this doesn’t quite do what we want. The XAttribute one works fine. But the ParamArray attribute we used with the XElement doesn’t do anything. Intellisense actually shows the word params in front of the content argument, but we can’t specify multiple arguments, we still have to pass an array. It would be surprising if this did work, since XElement is just a function that takes a tuple and not a member.

So we’ll remove the ParamArray attribute, which will force us to call our function with a collection. This means we can also change to argument type to be a sequence type so we’re not restricted to passing just arrays:

let XElement(name, content) = new XElement(XName.Get name, Seq.toArray content)
let XAttribute(name, value) = new XAttribute(XName.Get name, value)

Now we can write the following:

XElement("contacts", 
    [ 
        XAttribute("test", "2")
        XElement("contact", 
            [ 
                XAttribute("first", "John")
                XAttribute("last", "Smith")
            ])
        XElement("contact", 
            [ 
                XAttribute("first", "Susan")
                XAttribute("last", "Jones")
            ])
    ])

That’s probably more whitespace than I’d like, but I couldn’t find a more optimal way to format it (I wish F# would have more tolerance for irregular indentation when nesting delimiters like [ and ] are being used).

One last thing: functions can’t be overloaded. The original constructors for the XElement and XAttribute were overloaded, but we’ve shadowed them with our new functions. Fortunately there are two syntaxes for calling constructors in F#. Constructors can be called as functions, or they can be prefixed with the new keyword as in a more traditional object-oriented language. If we use the latter syntax, then F# knows that we want to call a constructor rather than a function and the original constructors (that we shadowed) are still available to us.

So everthing worked more or less perfectly. Now you can use Linq to XML from your F# code with less annoyance. This source for this module is available here.

Multiple items
type XDocument =
  inherit XContainer
  new : unit -> XDocument + 3 overloads
  member Declaration : XDeclaration with get, set
  member DocumentType : XDocumentType
  member NodeType : XmlNodeType
  member Root : XElement
  member Save : fileName:string -> unit + 6 overloads
  member WriteTo : writer:XmlWriter -> unit
  static member Load : uri:string -> XDocument + 7 overloads
  static member Parse : text:string -> XDocument + 1 overload

Full name: System.Xml.Linq.XDocument

——————–
XDocument() : unit
XDocument(params content: obj []) : unit
XDocument(other: XDocument) : unit
XDocument(declaration: XDeclaration, params content: obj []) : unit
XDocument.Parse(text: string) : XDocument
XDocument.Parse(text: string, options: LoadOptions) : XDocument
val xml : string

Full name: Samples.xml
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
type XName =
  member Equals : obj:obj -> bool
  member GetHashCode : unit -> int
  member LocalName : string
  member Namespace : XNamespace
  member NamespaceName : string
  member ToString : unit -> string
  static member Get : expandedName:string -> XName + 1 overload

Full name: System.Xml.Linq.XName
XName.Get(expandedName: string) : XName
XName.Get(localName: string, namespaceName: string) : XName
Multiple items
type AutoOpenAttribute =
  inherit Attribute
  new : unit -> AutoOpenAttribute
  new : path:string -> AutoOpenAttribute
  member Path : string

Full name: Microsoft.FSharp.Core.AutoOpenAttribute

——————–
new : unit -> AutoOpenAttribute
new : path:string -> AutoOpenAttribute
namespace System
namespace System.Xml
namespace System.Xml.Linq
namespace System.Runtime
namespace System.Runtime.CompilerServices
type XNode =
  inherit XObject
  member AddAfterSelf : content:obj -> unit + 1 overload
  member AddBeforeSelf : content:obj -> unit + 1 overload
  member Ancestors : unit -> IEnumerable<XElement> + 1 overload
  member CreateReader : unit -> XmlReader + 1 overload
  member ElementsAfterSelf : unit -> IEnumerable<XElement> + 1 overload
  member ElementsBeforeSelf : unit -> IEnumerable<XElement> + 1 overload
  member IsAfter : node:XNode -> bool
  member IsBefore : node:XNode -> bool
  member NextNode : XNode
  member NodesAfterSelf : unit -> IEnumerable<XNode>
  …

Full name: System.Xml.Linq.XNode
type XContainer =
  inherit XNode
  member Add : content:obj -> unit + 1 overload
  member AddFirst : content:obj -> unit + 1 overload
  member CreateWriter : unit -> XmlWriter
  member DescendantNodes : unit -> IEnumerable<XNode>
  member Descendants : unit -> IEnumerable<XElement> + 1 overload
  member Element : name:XName -> XElement
  member Elements : unit -> IEnumerable<XElement> + 1 overload
  member FirstNode : XNode
  member LastNode : XNode
  member Nodes : unit -> IEnumerable<XNode>
  …

Full name: System.Xml.Linq.XContainer
Multiple items
type XElement =
  inherit XContainer
  new : name:XName -> XElement + 4 overloads
  member AncestorsAndSelf : unit -> IEnumerable<XElement> + 1 overload
  member Attribute : name:XName -> XAttribute
  member Attributes : unit -> IEnumerable<XAttribute> + 1 overload
  member DescendantNodesAndSelf : unit -> IEnumerable<XNode>
  member DescendantsAndSelf : unit -> IEnumerable<XElement> + 1 overload
  member FirstAttribute : XAttribute
  member GetDefaultNamespace : unit -> XNamespace
  member GetNamespaceOfPrefix : prefix:string -> XNamespace
  member GetPrefixOfNamespace : ns:XNamespace -> string
  …

Full name: System.Xml.Linq.XElement

——————–
XElement(name: XName) : unit
XElement(other: XElement) : unit
XElement(other: XStreamingElement) : unit
XElement(name: XName, content: obj) : unit
XElement(name: XName, params content: obj []) : unit
module Seq

from Microsoft.FSharp.Collections
val map : mapping:('T -> 'U) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

——————–
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>
Multiple items
type XAttribute =
  inherit XObject
  new : other:XAttribute -> XAttribute + 1 overload
  member IsNamespaceDeclaration : bool
  member Name : XName
  member NextAttribute : XAttribute
  member NodeType : XmlNodeType
  member PreviousAttribute : XAttribute
  member Remove : unit -> unit
  member SetValue : value:obj -> unit
  member ToString : unit -> string
  member Value : string with get, set
  …

Full name: System.Xml.Linq.XAttribute

——————–
XAttribute(other: XAttribute) : unit
XAttribute(name: XName, value: obj) : unit
val toArray : source:seq<'T> -> 'T []

Full name: Microsoft.FSharp.Collections.Seq.toArray

Interesting Active Patterns

| Comments

I wanted to do a quick post about active patterns in F#, specifically the usefulness of Single Total Active Patterns (STAPs?) for transforming and validating data.

One slightly annoying thing about the .NET BCL is the fact that there is no plain Date type. Oftentimes you only care about dealing with the date portion of a DateTime, and if there happens to be a stray time associated with it, any comparison might not work as expected.

In any case, I often want to work with the date and/or time portions separately, so I find myself doing things like this at the top of a method:

Of course, in F# we could condense this down to a single line with tuple destructuring:

let date, time = dateTime.Date, dateTime.TimeOfDay

Another approach is to define some active patterns to deal specifically with dates and times:

let (|Date|) (dateTime:DateTime) = dateTime.Date
let (|Time|) (dateTime:DateTime) = dateTime.TimeOfDay

This allows us to rewrite the first snippet as follows:

let Date date = dateTime
let Time time = dateTime

People coming from other languages might mistakenly think Date and Time are types in these declarations, but of course they are our active pattern names. The types of date and time are inferred. Again, we can condense this by using an AND Pattern (&) to combine the pattern matches.

let Date date & Time time = dateTime

Active patterns and pattern matching in general becomes more powerful when you realize that they’re not just limited to match/try ... with constructs, but every let binding and parameter is also a pattern match. So one interesting thing we can do with active patterns is reshape our data directly in a parameter declaration. For example, suppose we have a function that takes a DateTime parameter:

let f (dateTime:DateTime) = ...

We could extract the date portion right in the parameter declaration:

let f (Date date) = ...

Or we could bind both the date and time to separate values:

let f (Date date & Time time) = ...

Note that from the caller’s perspective this is still just one parameter. The only strange thing about this is that since our parameter is anonymous, we won’t get intellisense for the name of the parameter, or the compiler will give it an auto-generated name like _arg1 if it is in a separate assembly. I don’t know of any fix for this other than to use a signature file.

The usage of active patterns on arguments opens up other possibilities such as validation. For example, suppose we were to define the following patterns:

let (|NonEmptyString|) value =
    if String.IsNullOrEmpty value
    then failwith "String must be non-empty."
    else value

let (|GreaterThanEqual|) comparand value =
    if value < comparand
    then failwithf "Value must be greater than or equal to %A." comparand
    else value

Now we can use these to define preconditions on our function parameters:

let sayHello (NonEmptyString name) =
    printfn "Hello, %s." name

let rec factorial (GreaterThanEqual 0 n) =
    if n = 0 then 1
    else n * factorial (n - 1)

If we violate a precondition, such as by passing a -1 to our factorial function, then it will throw an exception. The only downside is that it doesn’t include the argument name. We could pass the argument name as an additional argument to the active pattern, but then that is getting kind of crufty.

I realize some of these examples are probably somewhat contrived, and I’m not sure I would do validation like this in a real application. Still, I hope it expands your view of the ways in which active patterns might be used to write more concise and expressive code.

val date : DateTime

Full name: Samples.date
val time : TimeSpan

Full name: Samples.time
val dateTime : DateTime

Full name: Samples.dateTime
property DateTime.Date: DateTime
property DateTime.TimeOfDay: TimeSpan
val dateTime : DateTime
Multiple items
type DateTime =
  struct
    new : ticks:int64 -> DateTime + 10 overloads
    member Add : value:TimeSpan -> DateTime
    member AddDays : value:float -> DateTime
    member AddHours : value:float -> DateTime
    member AddMilliseconds : value:float -> DateTime
    member AddMinutes : value:float -> DateTime
    member AddMonths : months:int -> DateTime
    member AddSeconds : value:float -> DateTime
    member AddTicks : value:int64 -> DateTime
    member AddYears : value:int -> DateTime
    …
  end

Full name: System.DateTime

——————–
DateTime()
   (+0 other overloads)
DateTime(ticks: int64) : unit
   (+0 other overloads)
DateTime(ticks: int64, kind: DateTimeKind) : unit
   (+0 other overloads)
DateTime(year: int, month: int, day: int) : unit
   (+0 other overloads)
DateTime(year: int, month: int, day: int, calendar: Globalization.Calendar) : unit
   (+0 other overloads)
DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int) : unit
   (+0 other overloads)
DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int, kind: DateTimeKind) : unit
   (+0 other overloads)
DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int, calendar: Globalization.Calendar) : unit
   (+0 other overloads)
DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int, millisecond: int) : unit
   (+0 other overloads)
DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int, millisecond: int, kind: DateTimeKind) : unit
   (+0 other overloads)
Multiple items
val Date : date:'a -> DateTime

Full name: Samples.Date

——————–
active recognizer Date: DateTime -> DateTime

Full name: Samples.( |Date| )
val date : 'a
Multiple items
val Time : time:'a -> DateTime

Full name: Samples.Time

——————–
active recognizer Time: DateTime -> TimeSpan

Full name: Samples.( |Time| )
val time : 'a
val f : dateTime:DateTime -> 'a

Full name: Samples.Incomplete.f
val value : string
Multiple items
type String =
  new : value:char -> string + 7 overloads
  member Chars : int -> char
  member Clone : unit -> obj
  member CompareTo : value:obj -> int + 1 overload
  member Contains : value:string -> bool
  member CopyTo : sourceIndex:int * destination:char[] * destinationIndex:int * count:int -> unit
  member EndsWith : value:string -> bool + 2 overloads
  member Equals : obj:obj -> bool + 2 overloads
  member GetEnumerator : unit -> CharEnumerator
  member GetHashCode : unit -> int
  …

Full name: System.String

——————–
String(value: nativeptr<char>) : unit
String(value: nativeptr<sbyte>) : unit
String(value: char []) : unit
String(c: char, count: int) : unit
String(value: nativeptr<char>, startIndex: int, length: int) : unit
String(value: nativeptr<sbyte>, startIndex: int, length: int) : unit
String(value: char [], startIndex: int, length: int) : unit
String(value: nativeptr<sbyte>, startIndex: int, length: int, enc: Text.Encoding) : unit
String.IsNullOrEmpty(value: string) : bool
val failwith : message:string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith
val comparand : 'a (requires comparison)
val value : 'a (requires comparison)
val failwithf : format:Printf.StringFormat<'T,'Result> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.failwithf
val sayHello : string -> unit

Full name: Samples.sayHello
active recognizer NonEmptyString: string -> string

Full name: Samples.( |NonEmptyString| )
val name : string
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
val factorial : int -> int

Full name: Samples.factorial
active recognizer GreaterThanEqual: 'a -> 'a -> 'a

Full name: Samples.( |GreaterThanEqual| )
val n : int

F# Symbolic Math, Part 2

| Comments

In a previous post, I showed how to represent mathematical expression trees using discriminated unions and gave an example of using them to compute derivitives. In this post, I endeavor to add pretty-printing capabilites to my expression trees.

One of the most difficult aspects of formatting mathematical expressions is dealing with precedence and associativity. However, it’s simple enough to write a basic formatting function that simply parenthesizes every operation:

let rec print expr =
    match expr with
    | Add(x, y) -> sprintf "(%s + %s)" (print x) (print y)
    | Sub(x, y) -> sprintf "(%s - %s)" (print x) (print y)
    | Mult(x, y) -> sprintf "(%s * %s)" (print x) (print y)
    | Div(x, y) -> sprintf "(%s / %s)" (print x) (print y)
    | Power(x, y) -> sprintf "(%s ** %s)" (print x) (print y)
    | Neg x -> sprintf "-(%s)" (print x)
    | Var x -> x
    | Con x -> string x

Here is an example of using that function to format an expression:

print <| (-x + 2) * (x ** y) ** z / -2;;
val it : string = "(((-(x) + 2) * ((x ** y) ** z)) / -2)"

This output, though technically correct, is not really what we want. We would like to include only the minimum number of parentheses, as in the original input expression.

Before we attempt to rectify this, it would be a good idea to try and remove all the duplication from our function. For example, it would be nice if we could handle all binary expressions in a single case, factoring out the parts that vary (such as the operator symbol). This will become more important as the function increases in complexity.

To this end, let’s add the following union types to represent each type of unary and binary expression:

[<RequireQualifiedAccess>]
type BinaryOp = Add | Sub | Mult | Div | Power

[<RequireQualifiedAccess>]
type UnaryOp = Neg

These differ from our main Expr type in that they only represent the type of expression and nothing else. The RequireQualifiedAccess attribute is used to avoid naming conflicts with the cases from the Expr type.

We can then augment our our union types with informational properties, such as for retrieving the operator symbol:

type BinaryOp with
    member this.Symbol =
        match this with
        | Add -> "+"
        | Sub -> "-"
        | Mult -> "*"
        | Div -> "/"
        | Power -> "**"

type UnaryOp with
    member this.Symbol =
        match this with
        | Neg -> "-"

Note that because these are members on the union types themselves, we are able to omit the type prefixes that would normally be required on the union cases due to the RequireQualifiedAccess attribute.

Now let’s define a multi-case active pattern to classify expressions into one of four categories: Binary, Unary, Variable, or Constant. This will enable us to match binary and unary expressions as a group, as opposed to needing to match each type of expression individually.

let (|Binary|Unary|Variable|Constant|) expr =
    match expr with
    | Add(x, y) -> Binary(BinaryOp.Add, x, y)
    | Sub(x, y) -> Binary(BinaryOp.Sub, x, y)
    | Mult(x, y) -> Binary(BinaryOp.Mult, x, y)
    | Div(x, y) -> Binary(BinaryOp.Div, x, y)
    | Power(x, y) -> Binary(BinaryOp.Power, x, y)
    | Neg x -> Unary(UnaryOp.Neg, x)
    | Var x -> Variable x
    | Con x  -> Constant x

Putting it all together, we can now simplify our print function as follows:

let rec print expr =
    match expr with
    | Binary(op, x, y) -> sprintf "(%s) %s (%s)" (print x) op.Symbol (print y)
    | Unary(op, x) -> sprintf "%s(%s)" op.Symbol (print x)
    | Variable x -> x
    | Constant x -> string x

This is much more concise than our original version, and it keeps the function focused on the single responsibility of formatting the expression rather than worrying about which operator goes with what expression type.

Now we’re ready to modify our function to drop some of the parentheses. However, we’ll want to retain the parentheses around the following types of expressions:

  1. A binary expression nested in either side of another binary expression with higher precedence.
  2. A binary expression nested in the left-hand side of a right-associative binary expression with equal precedence.
  3. A binary expression nested in the right-hand side of a left-associative binary expression with equal precedence.
  4. The operand of a unary expression, except for negation of a variable or non-negative constant.

With all this in mind, let’s first add some additional properties to the BinaryOp type, as well as an Associativity type:

type Associativity = Left | Right

type BinaryOp with
    member this.Precedence =
        match this with
        | Add | Sub -> 1
        | Mult | Div -> 2
        | Power -> 3
    member this.Associativity =
        match this with
        | Add | Mult -> None
        | Sub | Div -> Some Left
        | Power -> Some Right

We can now rewrite our print function to account for our new rules:

let rec print expr =
    let parensPrint innerExpr = sprintf "(%s)" (print innerExpr)
    match expr with
    | Binary(op, left, right) ->
        let printInner defAssoc innerExpr =
            let opAssoc = defaultArg op.Associativity defAssoc
            match innerExpr with
            | Binary(innerOp, _, _) when innerOp.Precedence < op.Precedence -> parensPrint innerExpr
            | Binary(innerOp, _, _) when innerOp.Precedence = op.Precedence && opAssoc <> defAssoc -> parensPrint innerExpr
            | _ -> print innerExpr
        sprintf "%s %s %s" (printInner Left left) op.Symbol (printInner Right right)
    | Unary(op, operand) ->
        match expr with
        | Neg(Var _) -> print operand
        | Neg(Con x) when x >= 0 -> print operand
        | _ -> parensPrint operand
        |> sprintf "%s%s" op.Symbol
    | Variable x -> x
    | Constant x -> string x

Now when we invoke the function with our test expression we get the expected result:

print <| (-x + 2) * (x ** y) ** z / -2;;
val it : string = "(-x + 2) * (x ** y) ** z / -2"

That’s all there is to formatting expressions. As you can see, discriminated unions and pattern matching allow for a very readable and elegant solution.

val print : expr:Expr -> string

Full name: Samples.print
val expr : Expr
union case Expr.Add: Expr * Expr -> Expr
val x : Expr
val y : Expr
val sprintf : format:Printf.StringFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.sprintf
union case Expr.Sub: Expr * Expr -> Expr
union case Expr.Mult: Expr * Expr -> Expr
union case Expr.Div: Expr * Expr -> Expr
union case Expr.Power: Expr * Expr -> Expr
union case Expr.Neg: Expr -> Expr
union case Expr.Var: string -> Expr
val x : string
union case Expr.Con: int -> Expr
val x : int
Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

——————–
type string = System.String

Full name: Microsoft.FSharp.Core.string
val x : Expr

Full name: Samples.x
val y : Expr

Full name: Samples.y
val z : Expr

Full name: Samples.z
Multiple items
type RequireQualifiedAccessAttribute =
  inherit Attribute
  new : unit -> RequireQualifiedAccessAttribute

Full name: Microsoft.FSharp.Core.RequireQualifiedAccessAttribute

——————–
new : unit -> RequireQualifiedAccessAttribute
union case Option.None: Option<'T>
union case Option.Some: Value: 'T -> Option<'T>
val defaultArg : arg:'T option -> defaultValue:'T -> 'T

Full name: Microsoft.FSharp.Core.Operators.defaultArg

F# and Output Parameters

| Comments

One perpetual source of annoyance in C# is output parameters. Normally, output parameters are used when multiple values need to be returned from a method. Within the BCL, it is common to have methods of the form TryXXXX, which have a boolean return value to indicate success or failure and an output parameter to hold the resulting value, if any. So you have Int32.TryParse, Dictionary<,>.TryGetValue, etc.

Why are out params annoying? Firstly because you’re forced to declare a variable to hold the parameter value in the advance of the method call, even if you don’t actually care about the value. Here’s an example of calling Int32.TryParse in C#:

int value;
if (int.TryParse(maybeInt, out value))
    Console.WriteLine("It's the number {0}.", value);
else
    Console.WriteLine("It's not a number.");

It seems silly to complain about needing to declare variables in advance, but then, programmers are flakey people who like to obsess over the minor details of how a code block looks. Apparently it was enough of a problem that inline declaration of out params is slated for inclusion in the next version of C#.

The real problem with out params, in my opinion, is simply that they are a kludge. In every case except for interoping with legacy code, out params are an attempt to compensate for the fact that C# and VB.NET methods don’t allow any natural way to return multiple values. That’s because those languages lack usable tuples and pattern matching.

If we were to reimplement Int32.TryParse in F#, we could simply have it return a tuple, which we could then destructure into two separate values:

let success, value = Int32.TryParse maybeInt

But Int32.TryParse is already implemented as a method with an out param. So one way to call it in F# is to follow the same pattern we used in C# using a mutable value:

let mutable value = 0;
if Int32.TryParse(maybeInt, &value) then
    printfn "It's the number %d." value
else
    printfn "It's not a number."

Rather than using a keyword, F# represents reference and out params with the byref<'T> type, which MSDN says is a managed pointer.

Another way to call a method with out params is by using a reference cell, represented by the ref<'T> type. A reference cell is simply a mutable value that is stored on the heap, and thus can survive the destruction of the scope in which it was created. You create a reference with the ref function:

let valueRef = ref 0;
if Int32.TryParse(maybeInt, valueRef) then
    printfn "It's the number %d." !valueRef
else
    printfn "It's not an integer."

Interestingly, reference cells can be created inline, which is nice for cases where we don’t care about the value:

if Int32.TryParse(maybeInt, ref 0) then
    printfn "It's an integer, but I don't care which."
else
    printfn "It's not an integer."

But not caring about the value is something of an edge case, so in most cases we’re stuck doing it the C# way.

Or are we? I said before that we don’t want to reimplement Int32.TryParse to have it return a tuple, but it turns out that we don’t have to. In F# you have the option of consuming methods with out params as if they return a tuple! So the destructuring snippet from above will work automatically, which also means that we can use a match expression in place of an if-else:

match Int32.TryParse maybeInt with
| true, value -> printfn "It's the number %d." value
| _ -> printfn "It's not a number."

Of course, in F# we’re used to consuming values that might or might not exist using the option<'T> type rather than this silly tuple. So one thing we might do is write a function to adapt the tuple to an option, since these TryXXXX methods are so common in .NET:

let opt tryResult =
    match tryResult with
    | true, value -> Some value
    | _ -> None

Now we can rewrite our parsing code as follows:

match Int32.TryParse maybeInt |> opt with
| Some value -> printfn "It's the number %d." value
| None -> printfn "It's not a number."

Another way we could clean things up is by using a multi-case active pattern:

let (|Success|Failure|) tryResult =
    match tryResult with
    | true, value -> Success value
    | _ -> Failure

This allows us to write it even more elegantly:

match Int32.TryParse maybeInt with
| Success value -> printfn "It's the number %d." value
| Failure -> printfn "It's not a number."

Now you may be thinking: “OK, so what’s the big deal? All he did was define some functions. I could have done the same thing in C#.” But you couldn’t have done most of these things, since C# doesn’t provide the automatic out param to tuple conversion, and thus writing a generic method to handle TryXXXX results is impossible. The fact that F# provides such a nice interface for dealing with an edge case points toward it being a well-designed, well-thought-out language.

Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

——————–
type int = int32

Full name: Microsoft.FSharp.Core.int

——————–
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
val maybeInt : string

Full name: Samples.maybeInt
type Console =
  static member BackgroundColor : ConsoleColor with get, set
  static member Beep : unit -> unit + 1 overload
  static member BufferHeight : int with get, set
  static member BufferWidth : int with get, set
  static member CapsLock : bool
  static member Clear : unit -> unit
  static member CursorLeft : int with get, set
  static member CursorSize : int with get, set
  static member CursorTop : int with get, set
  static member CursorVisible : bool with get, set
  …

Full name: System.Console
Console.WriteLine() : unit
   (+0 other overloads)
Console.WriteLine(value: string) : unit
   (+0 other overloads)
Console.WriteLine(value: obj) : unit
   (+0 other overloads)
Console.WriteLine(value: uint64) : unit
   (+0 other overloads)
Console.WriteLine(value: int64) : unit
   (+0 other overloads)
Console.WriteLine(value: uint32) : unit
   (+0 other overloads)
Console.WriteLine(value: int) : unit
   (+0 other overloads)
Console.WriteLine(value: float32) : unit
   (+0 other overloads)
Console.WriteLine(value: float) : unit
   (+0 other overloads)
Console.WriteLine(value: decimal) : unit
   (+0 other overloads)
type Int32 =
  struct
    member CompareTo : value:obj -> int + 1 overload
    member Equals : obj:obj -> bool + 1 overload
    member GetHashCode : unit -> int
    member GetTypeCode : unit -> TypeCode
    member ToString : unit -> string + 3 overloads
    static val MaxValue : int
    static val MinValue : int
    static member Parse : s:string -> int + 3 overloads
    static member TryParse : s:string * result:int -> bool + 1 overload
  end

Full name: System.Int32
Int32.TryParse(s: string, result: byref<int>) : bool
Int32.TryParse(s: string, style: Globalization.NumberStyles, provider: IFormatProvider, result: byref<int>) : bool
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
Multiple items
val ref : value:'T -> 'T ref

Full name: Microsoft.FSharp.Core.Operators.ref

——————–
type 'T ref = Ref<'T>

Full name: Microsoft.FSharp.Core.ref<_>
union case Option.Some: Value: 'T -> Option<'T>
union case Option.None: Option<'T>
Multiple items
val Failure : message:string -> exn

Full name: Microsoft.FSharp.Core.Operators.Failure

——————–
active recognizer Failure: exn -> string option

Full name: Microsoft.FSharp.Core.Operators.( |Failure|_| )

XML Transformations with F#

| Comments

Recently I needed to come up with a way to define transformations for importing different XML formats into an application. The traditional way to transform one XML format to another is with XSLT. However, XSLT is somewhat awkward and verbose, and few people understand it well. Sometimes it’s better to attack a problem with a full-fledged programming language rather than a specialized tool. So I decided to see if the data processing and scripting powers of F# could be better suited to the task.

The main F# feature that I was interested in (perhaps the killer feature, along with active patterns) was type providers. If you don’t already know, type providers are an extensible mechanism whereby you feed F# a data source, either a URL or example document, and it generates in-memory, Intellisense-enabled types on the fly to enable you write queries against that source.

For this example, consider the problem of flattening a data set. You have a file that looks like this:

<?xml version="1.0" encoding="utf-8" ?>
<Customers>
  <Customer name="ACME">
    <Order Number="A012345">
      <OrderLine Item="widget" Quantity="1"/>
    </Order>
    <Order Number="A012346">
      <OrderLine Item="trinket" Quantity="2"/>
    </Order>
  </Customer>
  <Customer name="Southwind">
    <Order Number="A012347">
      <OrderLine Item="skyhook" Quantity="3"/>
      <OrderLine Item="gizmo" Quantity="4"/>
    </Order>
  </Customer>
</Customers>

And you want to transform it to look like this:

<?xml version="1.0" encoding="utf-8" ?>
<OrderLines>
  <OrderLine Customer="ACME" Order="A012345" Item="widget" Quantity="1"/>
  <OrderLine Customer="ACME" Order="A012346" Item="trinket" Quantity="2"/>
  <OrderLine Customer="Southwind" Order="A012347" Item="skyhook" Quantity="3"/>
  <OrderLine Customer="Southwind" Order="A012347" Item="gizmo" Quantity="4"/>
</OrderLines>

To use the XML type provider we first need to reference the FSharp.Data assembly, which is available via NuGet. We can then declare our root XML type as follows:

type InputXml = XmlProvider<"input_sample.xml">

Where sample_input.xml is the example XML file, given above, that type provider will use to infer the schema and generate the corresponding types. This allows us to then write the following code with type safety and Intellisense:

let input = InputXml.Load("input_sample.xml")

for customer in input.GetCustomers() do
for order in customer.GetOrders() do
for line in order.GetOrderLines() do
    printfn "Customer: %s, Order: %s, Item: %s, Quantity: %d"
            customer.Name order.Number line.Item line.Quantity

That results in the following output:

Customer: ACME, Order: A012345, Item: widget, Quantity: 1
Customer: ACME, Order: A012346, Item: trinket, Quantity: 2
Customer: Southwind, Order: A012347, Item: skyhook, Quantity: 3
Customer: Southwind, Order: A012347, Item: gizmo, Quantity: 4

Now we just need to figure out how to output XML instead of text. One idea I had was to use the XML type provider again to generate types for the output model and use those to construct and serialize the result. Unfortunately, this doesn’t work. For example, the following snippet won’t compile:

let lines = [
    for customer in input.GetCustomers() do
    for order in customer.GetOrders() do
    for line in order.GetOrderLines() do
        yield OutputXml.DomainTypes.OrderLine(
            Customer = Customer.Name,
            Order = Order.Number,
            Item = Orderline.Item,
            Quantity = Orderline.Quantity)
]

It won’t compile because the generated OutputXml.DomainTypes.OrderLine type lacks a constructor. It might be possible for type providers to generate types with constructors, but the current version of XmlProvider doesn’t seem to.

So if we want to have serialization types for our output model we’ll have create them ourselves. This is a reasonable approach if we plan to create many transforms with the same output model.

Here’s a how we can create a record type for use with XmlSerializer:

[<XmlType("OrderLine")>]
type OrderLine = {
     [<XmlAttribute>] Customer: string
     [<XmlAttribute>] Order: string
     [<XmlAttribute>] Item: string
     [<XmlAttribute>] Quantity: int
}

And we could use it as follows:

XmlSerializer(typeof<OrderLine[]>, XmlRootAttribute("OrderLines"))
    .Serialize(stdout,
    [|
        for customer in input.GetCustomers() do
        for order in customer.GetOrders() do
        for line in order.GetOrderLines() do
            yield OrderLine(
                Customer = customer.Name,
                Order = order.Number,
                Item = line.Item,
                Quantity = line.Quantity)
    |])

Another option is to forget about the output types and generate the XML dynamically. We can do using with Linq to XML classes:

XElement(XName.Get "OrderLines", seq {
    for customer in input.GetCustomers() do
    for order in customer.GetOrders() do
    for line in order.GetOrderLines() do
        yield XElement(XName.Get "OrderLine",
            [
                XAttribute(XName.Get "Customer", customer.Name)
                XAttribute(XName.Get "Number", order.Number)
                XAttribute(XName.Get "Item", line.Item)
                XAttribute(XName.Get "Quantity", line.Quantity)
            ])
}).Save(stdout)

I may choose to go this dynamic route, since for my purposes the column names do not much matter. However, it is still a tad bit verbose with all that XLinq noise. We can clean things up a bit by creating some helper functions for creating XML nodes:

let element name children =
    XElement(XName.Get name, (children:XObject seq)) :> XObject

let attribute name value =
    XAttribute(XName.Get name, value) :> XObject

let text value =
    XText(value:string) :> XObject

This allows us to rewrite the previous example very cleanly as follows:

element "OrderLines" [
    for customer in input.GetCustomers() do
    for order in customer.GetOrders() do
    for line in order.GetOrderLines() do
        yield element "OrderLine" [
            attribute "Customer" customer.Name
            attribute "Number" order.Number
            attribute "Item" line.Item
            attribute "Quantity" (string line.Quantity)
        ]
] |> printfn "%A"

So those are the many possibilities and alternatives for transforming XML with F# and type providers. The other nice thing about using F# is that it doesn’t need to be compiled to an assembly; you can simply deploy the script and run it via fsi.exe. The one gotcha with type providers is that the example document you provide must be representative of the the documents you will receive at runtime. This is simple enough to achieve by simply tweaking the document to get the type projection that you expect. That is also the reason why I chose to include letters in my order numbers in this example, to avoid have them project as integers.

val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
Multiple items
type XmlTypeAttribute =
  inherit Attribute
  new : unit -> XmlTypeAttribute + 1 overload
  member AnonymousType : bool with get, set
  member IncludeInSchema : bool with get, set
  member Namespace : string with get, set
  member TypeName : string with get, set

Full name: System.Xml.Serialization.XmlTypeAttribute

——————–
XmlTypeAttribute() : unit
XmlTypeAttribute(typeName: string) : unit
Multiple items
type XmlAttribute =
  inherit XmlNode
  member AppendChild : newChild:XmlNode -> XmlNode
  member BaseURI : string
  member CloneNode : deep:bool -> XmlNode
  member InnerText : -> string with set
  member InnerXml : -> string with set
  member InsertAfter : newChild:XmlNode * refChild:XmlNode -> XmlNode
  member InsertBefore : newChild:XmlNode * refChild:XmlNode -> XmlNode
  member LocalName : string
  member Name : string
  member NamespaceURI : string
  …

Full name: System.Xml.XmlAttribute

——————–
type XmlAttributeAttribute =
  inherit Attribute
  new : unit -> XmlAttributeAttribute + 3 overloads
  member AttributeName : string with get, set
  member DataType : string with get, set
  member Form : XmlSchemaForm with get, set
  member Namespace : string with get, set
  member Type : Type with get, set

Full name: System.Xml.Serialization.XmlAttributeAttribute

——————–
XmlAttributeAttribute() : unit
XmlAttributeAttribute(attributeName: string) : unit
XmlAttributeAttribute(type: System.Type) : unit
XmlAttributeAttribute(attributeName: string, type: System.Type) : unit
Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

——————–
type string = System.String

Full name: Microsoft.FSharp.Core.string
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

——————–
type int = int32

Full name: Microsoft.FSharp.Core.int

——————–
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
Multiple items
type XmlSerializer =
  new : xmlTypeMapping:XmlTypeMapping -> XmlSerializer + 8 overloads
  member CanDeserialize : xmlReader:XmlReader -> bool
  member Deserialize : stream:Stream -> obj + 5 overloads
  member Serialize : textWriter:TextWriter * o:obj -> unit + 7 overloads
  event UnknownNode : XmlNodeEventHandler
  event UnknownAttribute : XmlAttributeEventHandler
  event UnknownElement : XmlElementEventHandler
  event UnreferencedObject : UnreferencedObjectEventHandler
  static member FromMappings : mappings:XmlMapping[] -> XmlSerializer[] + 2 overloads
  static member FromTypes : types:Type[] -> XmlSerializer[]
  …

Full name: System.Xml.Serialization.XmlSerializer

——————–
XmlSerializer(xmlTypeMapping: XmlTypeMapping) : unit
XmlSerializer(type: System.Type) : unit
XmlSerializer(type: System.Type, root: XmlRootAttribute) : unit
XmlSerializer(type: System.Type, extraTypes: System.Type []) : unit
XmlSerializer(type: System.Type, overrides: XmlAttributeOverrides) : unit
XmlSerializer(type: System.Type, defaultNamespace: string) : unit
XmlSerializer(type: System.Type, overrides: XmlAttributeOverrides, extraTypes: System.Type [], root: XmlRootAttribute, defaultNamespace: string) : unit
XmlSerializer(type: System.Type, overrides: XmlAttributeOverrides, extraTypes: System.Type [], root: XmlRootAttribute, defaultNamespace: string, location: string) : unit
val typeof<'T> : System.Type

Full name: Microsoft.FSharp.Core.Operators.typeof
Multiple items
type XmlRootAttribute =
  inherit Attribute
  new : unit -> XmlRootAttribute + 1 overload
  member DataType : string with get, set
  member ElementName : string with get, set
  member IsNullable : bool with get, set
  member Namespace : string with get, set

Full name: System.Xml.Serialization.XmlRootAttribute

——————–
XmlRootAttribute() : unit
XmlRootAttribute(elementName: string) : unit
val stdout<'T> : System.IO.TextWriter

Full name: Microsoft.FSharp.Core.Operators.stdout
Multiple items
type XElement =
  inherit XContainer
  new : name:XName -> XElement + 4 overloads
  member AncestorsAndSelf : unit -> IEnumerable<XElement> + 1 overload
  member Attribute : name:XName -> XAttribute
  member Attributes : unit -> IEnumerable<XAttribute> + 1 overload
  member DescendantNodesAndSelf : unit -> IEnumerable<XNode>
  member DescendantsAndSelf : unit -> IEnumerable<XElement> + 1 overload
  member FirstAttribute : XAttribute
  member GetDefaultNamespace : unit -> XNamespace
  member GetNamespaceOfPrefix : prefix:string -> XNamespace
  member GetPrefixOfNamespace : ns:XNamespace -> string
  …

Full name: System.Xml.Linq.XElement

——————–
XElement(name: XName) : unit
XElement(other: XElement) : unit
XElement(other: XStreamingElement) : unit
XElement(name: XName, content: obj) : unit
XElement(name: XName, params content: obj []) : unit
type XName =
  member Equals : obj:obj -> bool
  member GetHashCode : unit -> int
  member LocalName : string
  member Namespace : XNamespace
  member NamespaceName : string
  member ToString : unit -> string
  static member Get : expandedName:string -> XName + 1 overload

Full name: System.Xml.Linq.XName
XName.Get(expandedName: string) : XName
XName.Get(localName: string, namespaceName: string) : XName
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

——————–
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>
Multiple items
type XAttribute =
  inherit XObject
  new : other:XAttribute -> XAttribute + 1 overload
  member IsNamespaceDeclaration : bool
  member Name : XName
  member NextAttribute : XAttribute
  member NodeType : XmlNodeType
  member PreviousAttribute : XAttribute
  member Remove : unit -> unit
  member SetValue : value:obj -> unit
  member ToString : unit -> string
  member Value : string with get, set
  …

Full name: System.Xml.Linq.XAttribute

——————–
XAttribute(other: XAttribute) : unit
XAttribute(name: XName, value: obj) : unit
type XObject =
  member AddAnnotation : annotation:obj -> unit
  member Annotation<'T> : unit -> 'T + 1 overload
  member Annotations<'T> : unit -> IEnumerable<'T> + 1 overload
  member BaseUri : string
  member Document : XDocument
  member NodeType : XmlNodeType
  member Parent : XElement
  member RemoveAnnotations<'T> : unit -> unit + 1 overload
  event Changed : EventHandler<XObjectChangeEventArgs>
  event Changing : EventHandler<XObjectChangeEventArgs>

Full name: System.Xml.Linq.XObject
Multiple items
type XText =
  inherit XNode
  new : value:string -> XText + 1 overload
  member NodeType : XmlNodeType
  member Value : string with get, set
  member WriteTo : writer:XmlWriter -> unit

Full name: System.Xml.Linq.XText

——————–
XText(value: string) : unit
XText(other: XText) : unit

F# Symbolic Math, Part 1

| Comments

Introduction

Back in 2009 I attended a weekend course on F# put on by a local user group, and though I was intrigued by certain powerful features of the language, I was never able to put any of it to good use. Every time I tried to code anything in F#, even the most trivial ideas, I would quickly become frustrated with what seemed like flaws in the language and eventually lost interest.

Why can’t the type inference system actually infer my types, I would think? Why can’t numeric values implicitly convert like in all other languages? Why don’t .NET methods support partial application and piping like native F# functions? And what’s the deal with these “discriminated unions” – isn’t that just a fancy name for a type hierarchy that I can’t extend? It all felt kind of half-baked to me.

Recently I decided to try solving some of the Project Euler problems, and having had my interest in the language rekindled by the Try F# site, I decided I would try to use it for this. After three relatively sleepless nights, I have found solving problems using functional techniques to be extremely fun and addicting, and in some ways it feels more “natural” than procedural methods. The more I learn about F# (and functional programming in general) the more I realize that the “flaws” in the language were not actually flaws - they’re the way things have to work in order to support its powerful features!

So a few days ago I decided that I wanted to try and leverage the power of F# to write a little library for processing mathematical expressions. Discriminated unions would make it easy to represent my expression trees, and pattern matching would (hopefully) allow straight-forward implementations of things like pretty-printing, simplification, taking derivatives, etc. Happily, the language has exceeded all my expectations in this regard, and it was exceedingly easy (and fun!) to implement what I’ve implemented so far. In this post I’ll share some of what I’ve been able to achieve.

Expressions

The first thing I did was define a discriminated union to represent my expression nodes, which looks like the following:

type Expr =
    | Con of int
    | Var of string
    | Add of Expr * Expr
    | Sub of Expr * Expr
    | Mult of Expr * Expr
    | Div of Expr * Expr
    | Power of Expr * Expr
    | Neg of Expr

Now to construct the expression x * 3 + 4, I can type Add(Mult (Var "x", Con 3), Con 4). Fairly straightforward, but somewhat verbose. As Shenia Twain would say, that don’t impress me much. I wanted to see if I could clean things up a bit to make these expressions easier to write.

So the next thing I did was modify my Expr type to overload the arithmetic operators:

type Expr with
    static member (+) (x, y) = Add(x, y)
    static member (-) (x, y)  = Sub(x, y)
    static member (*) (x, y)  = Mult(x, y)
    static member (/) (x, y)  = Div(x, y)
    static member Pow (x, y) = Power(x, y)
    static member (~-) x = Neg x
    static member (~+) x = x

Notice I had to add a member Pow in order to overload the ** operator. For some reason, including a ** member directly on the type does not work for overloading that operator (it’s also the reason I named my union case Power rather than Pow as I wanted - to avoid a naming conflict). Also notice that I have prefixed the unary operators with a ~ to indicate to the compiler that I am overloading the unary as oppose to the binary forms of the operators.

This allows me to do the following (if you’re unfamiliar with F# Interactive, > is the prompt and ;; is what causes it to evaluate the expression. The subsequent line shows the result of the evaluation along with its type):

> Var "x" * Con 3 + Con 4;;
val it : Expr = Add (Mult (Var "x",Con 3),Con 4)

That’s somewhat of an improvement, but what if I wanted to be able to just say x * 3 + 4 and have it automatically convert to the corresponding expression tree? In order for this to work, I first had to define additional operators dealing with expressions and integers, as follows:

type Expr with
    static member (+) (x, y) = Add(x, Con y)
    static member (+) (x, y) = Add(Con x, y)
    static member (-) (x, y) = Sub(x, Con y)
    static member (-) (x, y) = Sub(Con x, y)
    static member (*) (x, y) = Mult(x, Con y)
    static member (*) (x, y) = Mult(Con x, y)
    static member (/) (x, y) = Div(x, Con y)
    static member (/) (x, y) = Div(Con x, y)
    static member Pow (x, y) = Exp(x, Con y)
    static member Pow (x, y) = Exp(Con x, y)

Note how I still don’t need to place any type annotations on the x and y parameters – the compiler can infer their types from how they are used within the case constructors.

Another thing I needed to do was create a few bindings for my variable names:

let x = Var("x")
let y = Var("y")
let z = Var("z")

This now allows me to enter the expression using its natural representation:

> x * 3 + 4;;
val it : Expr = Add (Mult (Var "x",Con 3),Con 4)

Application

So now that I have these wonderful self-parsing expression trees, what can I do with them? In the introduction I mentioned some possibilities, such as taking derivatives. As a quick example, I implemented the following recursive function that uses pattern matching to implement basic differentiation rules (notice there’s no “visitor pattern” weirdness!):

let rec deriv var expr =
    let d = deriv var
    match expr with
    | Var var -> Con 1                             // Identity Rule
    | Con x -> Con 0                               // Constant Rule
    | Mult(Con x, y) | Mult(y, Con x) -> Con x    // Constant Factor Rule
    | Add(x, y) -> d x + d y                      // Sum Rule
    | Sub(x, y) -> d x - d y                      // Difference Rule
    | Mult(x, y) -> d x * y + x * d y             // Product Rule
    | Div(x, y) -> (d x * y - x * d y) / y ** 2  // Quotient Rule
    | Power(var, Con x) -> x * var ** (x - 1)    // Elementary Power Rule
    | _ -> failwith "Sorry, don't know how to differentiate that!"

The ability to nest patterns, as exemplified by the “constant factor” and “power” rules above, is one thing that makes F# pattern matching extremely powerful. Note how I’m matching the general case of multiplication (product rule) and the case of multiplication by a constant (constant factor rule) separately. Although this is not necessary to get a correct result, it does result in a simplified expression for the constant factor case. That is another nice feature of pattern matching - you can handle certain cases specially while falling through to a more general rule.

Now let’s verify that the derivative of x3 + x is 3x2 + 1:

> deriv x (x ** 3 + x);;
val it : Expr = Add (Mult (Con 3,Power (Var "x",Con 2)),Con 1)

The output is not easy to read, since I haven’t added pretty-printing yet, but the result is correct.

There are many more possibilities, but I wanted to get this post up before it expands to any longer than it already is, so I’ll save those for future posts. In the mean time, I’ve posted the source for this post to the Try F# site so that you can test it out interactively and also created a Github repository in which I plan to develop this idea further.

Part 2

type Expr =
  | Con of int
  | Var of string
  | Add of Expr * Expr
  | Sub of Expr * Expr
  | Mult of Expr * Expr
  | Div of Expr * Expr
  | Power of Expr * Expr
  | Neg of Expr
  static member Pow : x:Expr * y:Expr -> Expr
  static member ( + ) : x:Expr * y:Expr -> Expr
  static member ( / ) : x:Expr * y:Expr -> Expr
  static member ( * ) : x:Expr * y:Expr -> Expr
  static member ( - ) : x:Expr * y:Expr -> Expr
  static member ( ~- ) : x:Expr -> Expr
  static member ( ~+ ) : x:'a -> 'a

Full name: Samples.Expr
union case Expr.Con: int -> Expr
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

——————–
type int = int32

Full name: Microsoft.FSharp.Core.int

——————–
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
union case Expr.Var: string -> Expr
Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

——————–
type string = System.String

Full name: Microsoft.FSharp.Core.string
union case Expr.Add: Expr * Expr -> Expr
union case Expr.Sub: Expr * Expr -> Expr
union case Expr.Mult: Expr * Expr -> Expr
union case Expr.Div: Expr * Expr -> Expr
union case Expr.Power: Expr * Expr -> Expr
union case Expr.Neg: Expr -> Expr
val x : Expr
val y : Expr
static member Expr.Pow : x:Expr * y:Expr -> Expr

Full name: Samples.Expr.Pow
val x : 'a
val failwith : message:string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith

Raspberry Pi GPIO via the Shell

| Comments

In my last post I mentioned my interest in using the Raspberry Pi as a microcontroller. I figured it would be easy to access the GPIO capabilities of the Pi, since most devices on Linux can be manipulated directly through the filesystem.

So when I first booted up my Pi I was surprised to not find anything relating to GPIO in the /dev directory, where block and character device nodes typically reside. However, I did notice a directory, /sys/class/gpio (/sys is a special in-memory directory that contains metadata about hardware devices; like /dev, it doesn’t actually exist on disk). By manipulating the files in this directory I was able to control the GPIO pins of the Pi.

The filesystem is only one way of accessing GPIO. It is also accessible through libraries or by writing directly to an address in memory, but I like the idea of the filesystem as it is readily accessible from any programming language and even the command-line.

The /sys/class/gpio folder contains two files, export and unexport, and a subdirectory called gpiochip0. Typing cat /sys/class/gpiochip0/ngpio into the shell will output the number of logical GPIO pins on the CPU, which is 54. Why so high a number? There are only 17 pins exposed on the GPIO header, but the CPU itself has many other pins that are not connected or are used to control other devices on the Pi.

The CPU pins that you can use for GPIO are 0, 1, 4, 7-11, 14, 15, 17, 18, 21-25 (pins 0, 1, and 21 become 2, 3, and 27, respectively, if you have the Revision 2 Pi). These numbers have nothing to do with the position of the pins on the GPIO header itself. Additionally, certain projects, such as such as Gordon Henderson’s WiringPi library, have adopting their own simplified numbering schemes. If you’re confused, there is a nice wiki article with a diagram that can help clear things up. It’s worth noting that some of the pins support more advanced I/O modes, such as RS-232 (serial), SPII2CPWM, and clock, none of which I’ve attempted to use as of yet.

To access any of these pins we first have to export them to the filesystem using the export file I mentioned above – for some reason they are not exposed by default. So if we want to be able to access pin 4, we would type echo 4 > /sys/class/gpio/export (all these commands must be run as root). This would cause a new directory entry, /sys/class/gpio/gpio4, to appear in the filesystem. There are several items in the gpio4 directory, but of immediate interest are direction and value. To specify that we want to use the pin as an output, we can do echo out > /sys/class/gpio/gpio4/direction. Then we can set the pin high or low by echoing a 0 or 1, respectively, to /sys/class/gpio/gpio4/value.

One of the mistakes that I made when I first started playing with the GPIO pins was thinking of them as either on or off (as I was taught to think of computers). In reality, a digital logic signal is either high (3.3V) or low (0V); both states allow current to flow between the pins, from high to low. Each of the GPIO pins is limited to 15mA, which is not very much current – your average LED is rated for a maximum of 20mA. Connecting the pins to a circuit without sufficient resistance (or to the 5V power pin) may damage the Pi. The 3.3V power pin is limited to 50mA (all these limits are discussed on the wiki page I previously linked to).

I decided to create a simple utility script for working with GPIO so that I don’t have to repeat the filesystem paths in all my scripts. The script can be called the command-line, or it can be sourced from within another script to allow direct access to its gpio function. It also allows the pin numbering to be remapped with the GPIO_PINS environment variable. Using my utility, a script to flash an LED would look like the following:

#!/bin/bash
source gpio
gpio mode 4 out
while true; do
    gpio write 4 1
    sleep 0.5
    gpio write 4 0
    sleep 0.5
done

I created a couple examples of using the utility, a LED chaser and a binary counter. I plan to continue updating the Github repository as I complete more projects.

Below is a picture of the binary counter in action. As you can see, I’m utilizing the Adafruit Pi Dish along with the Prototyping Pi Plate, since I find its headers easier to work with than the Cobbler Breakout.

Binary Counter

Watering Plants with .NET

| Comments

Introduction

I first became interested in microcontrollers after seeing a presentation by Ian Lee at the Nashville .NET User Group.  If you don’t know, a microcontroller is basically a programmable chip for controlling electronic circuits. Electrical engineers have been using microcontrollers like BASIC Stamp and PIC in their circuits for decades, but the Arduino has made them more accessible to consumers and hobbyists. The Arduino Uno is a development board containing an Atmel microcontroller chip as well as some supporting peripherals such USB and Ethernet ports. Arduino also provides an IDE that allows you to program the device using a C-like language.

There are now even microcontrollers targeting .NET developers. These allow you to program them in C# using the .NET Micro Framework. NETMF contains a subset of the .NET class libraries and adds its own APIs for microcontroller-related functionality.  Having lived comfortably in a bubble of Microsoft frameworks and managed code for a number of years, these seemed like an ideal starting point for me - I could explore the world of microcontrollers without even leaving Visual Studio!

There are currently two lines of .NET microcontrollers: Netduino and Fez. The original Netduino uses an Arduino-like form factor and headers meaning that it is theoretically compatible with the wide range of Arduino shields (extension boards) already in existence. The Fez uses a different type of extension socket based the Gadgeteer standard, which is supported by Microsoft. For my first project, I decided to go with the Fez.

Application

I was going on a couple of week-long trips and wanted a way to water my patio tomato plants while I was away. My basic idea was to use a microcontroller connected to small electric pumps to transfer water from storage buckets into my tomato pots once a day.

Here is my list of materials:

One nice thing about Gadgeteer is that it provides you with a visual design surface on which to lay out your components. It then generates a class containing references to all the component instances so that you do not need to create and configure them yourself. Here is the design for my relatively simple project:

Gadgeteer Board

I had two plants, so I used one relay to control each water pump. The code was pretty simple and looked similar to the following:

while (true)
{
  // Turn on first relay for 40 secods
  _relays.Relay1 = true;
  Thread.Sleep(pumpTime);
  _relays.Relay1 = false;

  // Turn on second relay for 40 seconds
  _relays.Relay2 = true;
  Thread.Sleep(pumpTime);
  _relays.Relay2 = false;

  // Wait for a day
  Thread.Sleep(delayTime)
}

One challenge in any type of project like this is getting components that do what you want. The biggest unknown in this project was the water pumps. I had difficulty locating a suitable pump (most of the ones I found were designed for fountains or aquariums and were AC-powered), but the ones I ordered off Amazon (with fingers crossed) worked surprisingly well. My only regret was that due to the varying diameters of the inlets and outlets, I couldn’t connect them in series for greater pumping power.

To drive the pumps, I could have connected them to another DC adapter, but I was paranoid about having water-immersed components connected to an outlet while I was away from home. Fortunately, I found a 12-volt lantern battery from Rayovak was readily able supply the level of current required by the pumps.

Here is a short video I made of the system in action:

Conclusion

Initially I had high hopes for this project. I was going to leverage the HTTP API of the NETMF to expose a web interface that I could use to monitor the system while I was away. Unfortunately, I had decided to use the newer Fez Hydra, and it so happened that the drivers for its associated ENC28 ethernet module were not ready for prime time, thus my plans were thwarted. So if you decided to invest in a Fez board, you might want to go with an older model like the Spider until the issues with the Hydra are resolved.

The Gadgeteer platform provides a nice turnkey solution to getting a simple project up and running quickly. However, if you want to interface a controller with your own circuits, you might want to look at a board with Arduino-style headers, such as the original Netduino or the Fez Cerbuino. That way you can use jumper wires to connect the device directly to your breadboard.

Being able to use .NET and C# to program the microcontroller is a nice amenity if you come from that background. However, if your project is just toggling relays or something like that then you probably don’t really need the full power of .NET. In that case you may want to look into the Arduino, since it has a larger community around it. Another advantage of the Arduino is that its \(5 DIP-style Atmel chip can be easily used independently of the Arduino board by sticking it on a breadboard, custom PCB, etc. Finally, with the release of the [Raspberry Pi](http://www.raspberrypi.org/), you can now get an entire computer running Linux and equipped with GPIOs for about\)30. I may just opt use the Pi as my “microcontroller” in future projects, since it seems like a very inexpensive and capable device.