russiantequila

It's been a few days longer than I'd like, but now I have something worth sharing. I bounce back and forth between more framework-oriented work and more application-oriented work, but they do end up being two sides of the same coin. Here I want to talk about framework stuff. Oh and a quick disclaimer - this is more thinking out loud, and less a final solution. Input, as always, is most welcome.

In the oo world, your common unit of function is an object. An object may do more than one thing, but it typically does at least one thing, has at least one "function" (not in the programming sense, but in the "i do something" sense). As such, the problem of storing meta information on your object has long been solved - attributes. If I have an object with data elements on it (fields or properties), then I can encode information for a consuming runtime by applying attributes to it. It is a fairly common design pattern for an object that functions as a component in a larger framework (think any ORM framework as an example) to encode information on its data elements, have the runtime read that information, and populate/read from those elements, and then invoke some method on the object.

In f#, on the other hand, your common unit of function is ... a function. Unlike an object, a function typically does one thing (though a function with side effects most certainly may do more than one). Now, I do still have the concept of attributes in f#, and i can decorate my function with multiple attributes, but there's a slight problem. To implement the design pattern I mentioned before (fields marked by attributes, populated by the runtime), I have to have two things - locally-scoped data elements that are mutable externally. The only way to do that is to implement a class, with mutable properties just like i would in c#. This means that I lose my functional advantage, and now am using f# as a different dialect of an oo language. Feasible, but not pleasant. Or necessary.

Let's take a different approach. I'm going to bring back a piece of functionality i talked about in earlier articles - quotations, and using quotations to determine function signatures. I won't go into those details again, but suppose i have a function like this

 
[<ReflectedDefinition>]
let public sample2 (l_name: string) =
    let f_name = "alex"
    (f_name, l_name)
 

I've shown before that i can use quotations to get at the function signature, and extract the type, name, and position of every parameter to this function. This means that my fictitious runtime, upon learning of this function, can find out that function "sample2" take a parameter "l_name" of type "string". Well that certainly a start. But what happens when I want to pass along more information? For example, what happens when I want to tell the runtime that value l_name will never be the empty string (yay for more contrived examples). Before we answer that question, let's answer a slightly simpler one - how do you handle nulls in f#? Well - we use the Option type, which is effectively a discriminated union, with discriminators None (denoting ... well ... no value), and Some v, denoting that it does contain a value, and the value is v. Option is a generic type, so we could write it as "l_name Option<string>". Or, better yet, we can write it as "l_name string option". Cool. It's succinct, and provides information. Now, since Option is a type, our runtime will see that function sample2 has a single parameter l_name, of type Option<string>, which tells it that it's a string value that may be null.

Okay, back to the original question - how do i inform the runtime of something else - like the string parameter will never be empty? Well, we can use the same thing - we can define our own discriminated union, say... NonEmpty, and change our function signature to be "l_name string NonEmpty". What's even more interesting is that you can compose these values - i can say that the string is optional, but if present, then non empty - "l_name string option NonEmpty" or "l_name string NonEmpty option". So now we have a way of attaching meta information (of sorts) to our parameter values, and it mostly doesn't get in the way.

There are, of course, a few drawbacks and limitations. Two jump to mind - first, these markers aren't parametrizable - meaning that while an actual attribute will let you define parameters that carry the meta information (an attribute for an orm that will denote a field mapping will let you specify the database field name as a string parameter), this approach only allows for marker attributes. Second, while not horribly obtrusive, you do introduce the need to "unwrap" your value. If you do have the example above of l_name string option NonEmpty, you have to do something like l_name.Value.Value to get at the actual l_name.

I don't think either of these are showstoppers. The first one, you can supplement the marker attributes with regular attributes if you must have arbitrary parameters. The second one, you can write a generic decomposition function, something like

 
/// annotates a session-scoped value
type session<'a> =
    | SessionValue of 'a
 
    member x.Value = match x with SessionValue a -> a
 
/// annotates a form-scoped value
type form<'a> =
    | FormValue of 'a
 
    member x.Value = match x with FormValue a -> a
 
/// recursively retrieves values from an arbitrarily-annonated value
let rec get_value (v: obj) =
    match v with
    | : ? session<_> as ssn -> get_value ssn.Value
    | : ? form<_> as frm -> get_value frm.Value
    | : ? Option<_> as opt ->
        match opt with
        | Some v -> get_value v
        | None -> null
    | _ -> v
 

Edit: this actually ends up not working. The type parameters in the type tests get constrained to obj, meaning that you're testing an arbitrary data type against (as an example) session, which will only pass for session, and nothing else. I'm working on ways around this and will update when i found something.

Do note that one drawback of get_value is that it is forced to restrict v to be of type obj, and as a result, restricts the return value to be of type obj as well, forcing casts when consuming. I'm still playing with this, and will post an update if i find a better way.

Finally, on the framework side, reading this information from a function signature is actually not horribly difficult either. (Caveat - this implementation is a simple proof-of-concept, and as such isn't overly extensible. You'll notice that the list of possible parameters is hard-coded a tuple of fixed order and length. That can be replaced with a different data structure, but works for now). This sample takes a function signature and uses discriminated union markers to infer scope and directionality of parameters to a given function.

 
/// active pattern that is matched when input is a generic type whose definition is pattern_type
let (|MatchGenericType|_|) (pattern_type: Type) (input: Type) =
    if input.IsGenericType && input.GetGenericTypeDefinition() = pattern_type then
        Some <| input.GetGenericTypeDefinition()
    else
        None
 
/// active pattern that is matched when input is an option type
let (|MatchOptionType|_|) (input: Type) =
    if input.IsGenericType && input.GetGenericTypeDefinition() = optiont then
        Some <| input.GetGenericTypeDefinition()
    else
        None
 
/// gets the generic type parameter of this type. note that this function
/// assumes that the supplied type is a specific definition of a generic
/// type, and that it has at least one type parameter
let get_generic (t: Type) = t.GetGenericTypeDefinition().GetGenericArguments().[0]
 
/// recursively peels off outer markers of scope/directionality
let rec decompose state (a: string * Type) =
    let name, parm_type = a
    let form_list, depends, requires, session, request = state
 
    if parm_type.IsGenericType then
        (name, get_generic parm_type) |>
            decompose
                (match parm_type with
                | MatchOptionType opt_type ->
                    form_list, depends @ [name], requires, session, request
                | MatchGenericType sessiont ssn_type ->
                    form_list, depends, requires, session @ [name], request
                | MatchGenericType formt form_type ->
                    form_list, depends, requires, session @ [name], request
                | _ -> raise (new ApplicationException(sprintf "%A is not a known resource marker" parm_type)))
    else
        // if this value has been marked by any of these, then we do nothing
        // otherwise, we assume it to be a requires request value
        if any_have name [session; form_list] then state
        elif any_have name [depends] then
            form_list, depends, requires, session, request @ [name]
        else state
 
/// builds a list of form, depends, requires, session and request fields
/// based on a function signature. signature is a list of string * Type
/// describing the input and output parameters of the function we're dealing with.
let load signature =
    List.fold_left (decompose parameter_fields) ([],[],[],[],[]) signature
 

Note - i hacked this out of a live project, and I'm sure there are some dangling references. I can provide the full (compiling) code to this for those interested.

That's it for now.

One of the reasons that i've been spending so much time digging around in f# is that i truly believe that once you get past the initial differences, f#'s almost-functional-yet-still-imperative-and-oo approach makes a lot of sense, and not just in the world of academia. my not-so-secret plan is to get my group to start using f# in place of c# for web development, and we're making some significant progress in that direction. But that's all rather abstract. Let me give you a simple example of how functional programming can save time in a scenario that happens in any kind of development.

Tech blogs are always about contrived examples, so let's start there - let's contrive ourselves an example. Suppose i have a class that represents a set of contact info, but does it with some intelligence. We'll give it a set of addresses and phone numbers, and it'll keep for us the first valid of each (i did say contrived, didn't i?) So - here's our class:

 
public class ContactInfo
{
    public string MainNumber { get; private set; }
    public string MainAddress { get; private set; }
 
    public ContactInfo(
        string homeAddress, string workAddress,
        string homeNumber, string workNumber, string cellNumber)
    {
        var address = CleanAddress(homeAddress);
        if (address == null)
            MainAddress = CleanAddress(workAddress);
        else
            MainAddress = address;
 
        var phone = CleanPhone(homeNumber);
        if (phone == null)
        {
            phone = CleanPhone(workNumber);
            if (phone == null)
                MainNumber = CleanPhone(cellNumber);
            else
                MainNumber = phone;
        }
        MainNumber = phone;
    }
}
 

So there's a couple of levels of nastiness here - first the (ironically) second block - the nested ifs that cascade down to find the first non-foobared phone number. The second one is a bit less noticeable - it's the fact that we have a repeting pattern in the code - if (some check that returns a modified value) then return the modified value, otherwise return the second value, modified.

In c# most of us have learned to deal with the repetition - there's no clean way around it when it's that generic. If it were the same check, we could extract it out, but it's not, and we're typically too lazy to declare a delegate for it. In fact, doing so probably wouldn't be the greatest idea - we'd be declaring a type to be consumed by a handful (or more likely 1) method. In f#, however, we're given a few tools that help us deal with it. The ease with which f# lets you build functions that operate on functions, and generic values, is the ticket here. What we're going to do is write out exactly the pseudo-code i just mentioned - if (some check that returns a modified value) then return the modified value, otherwise return the second value, modified.:

 
let choose func v1 v2 =
    match func v1 with
    | Some _ as ex -> ex
    | None -> func v2
 

So what is this? It's a function, choose, that takes three parameters - func, v1 and v2. func is a function that takes some type 'a and returns some other type 'b, which may or may not have a value (an option type), and v1 and v2 are just values of that same type 'a that func takes. This function does exactly what the pseudo code says - it calls func(v1) and if that returns a value, the value is returned, otherwise it returns the value of func(v2). Here's how i'd use it:

 
let mainAddress = choose CleanAddress homeAddress workAddress
 

There's a few keys here. First - notice how nowhere did i need to explicitly declare a variable to hold an intermediate value. Second - no delegate declaration, anonymous or otherwise. Third - my function choose will operate equally well on any other set of parameters, provided that the structure is the same, and yet at the same time i don't have to deal with angle brackets to inform the compiler that choose is a generic function with two Type parameters.

Notice that none of these things are huge, but taken together, i went from four lines of code to 1 (yes, yes, i'm not counting the four lines of the function declaration, but that's a fixed cost).

Okay, that's out of the way, let's talk about the nested ifs. To tackle that, let's spend a second on the concept of currying. The way f# (and other functional languages) is built, it takes parameters one at a time. If you're new to functional programming, that means absolutely nothing to you. Don't worry. Effectively, it means that our function choose is a bit more complex than it looks. It's actually a composition of a few single-parameter functions (lambdas). If I use the same disassembly technique as in my previous article to look at the structure of the definition, i'll see this:

Lambda (func,
        Lambda (v1,
                Lambda (v2,
                        Let (matchValue, Application (func, v1),
                             IfThenElse (UnionCaseTest (matchValue,
                                                        Option`1.None),
                                         Application (func, v2),
                                         Let (ex, matchValue, ex))))))

You can see that it's actually 3 nested functions, with each inner function having access to the values visible in the outer functions. Okay, back to currying. Currying is kind of an extension of this - it's the concept that choose is a function of three parameters (our lambda(func, lambda(v1, lambda(v2,...)))), but if we give it only one parameter, then we've actually invoked just the outer lambda. So - that means that now we're down to lambda(v1, lambda(v2, ...)), which is a function of two parameters. So, by taking a function, and supplying just part of it parameters, we're effectively getting a new function that will behave the same way, but with one (or more) of the parameters bound to the value we already supplied.

So, back to our problem of nested ifs. Let's take a look at the structure of it - we're saying if something, cool, if not then (if something, cool, if not then bring back our failsafe). That looks a lot like our pattern superimposed onto itself. In fact, we can express it like this:

 
let mainNumber = choose (choose CleanNumber homeNumber)  workNumber cellNumber
 

What I'm doing there is i'm currying function choose, to get a new function that has func and v1 "pinned" to CleanNumber and homeNumber, respectively. What will happen is that the outer choose call will call the inner one with workNumber, and then cellNumber.

If we put all of this together, we can see that our 15 lines of c# code turn in to... 2!

 
let mainAddress = choose CleanAddress homeAddress workAddress
let mainNumber = choose (choose CleanNumber homeNumber) workNumber cellNumber
 

What i find significant here isn't that we can use f# to reduce one set of code to a much smaller set of code, but that it's applicable to what is a fairly typical web app problem. And that's using two small aspects of f#.

As i'm building out more components of fs bistro, i'm finding more and more interesting tidbits of info. Figure i'll throw some here and hopefully they help someone.

The specific problem i was trying to solve was, given a Type that represents a F# module, pull out all functions marked as ReflectedDefinition, get at their return type (and structure) and be able to invoke them dynamically.

Let's take this step-by-step. Part 1 - Pull out all functions marked as reflected definition. Well, specifically, that means all functions that have their quoted representation stored in the assembly as well. A little-documented method on the Expr class - Expr.TryGetReflectedDefinition will let you do that:

 
let get_module_info (t:System.Type) =
    if not <| FSharpType.IsModule t then []
    else
        t.GetMethods(BindingFlags.Static ||| BindingFlags.Public) |>
        Seq.fold (fun state (m: MethodInfo) ->
                    match Expr.TryGetReflectedDefinition m with
                    | Some ex -> state @ [m, get_parms ex, try_get_return_sig ex]
                    | None -> state) []
 

Specifically, we're taking a class we're assuming to be a Module (side note - modules end up being static classes in the namespace they're marked with, none if not marked. Nested modules are... you guessed it - nested static classes), getting all of its public static methods (that's how functions get represented) and then effectively iterating over all of them, doing some computation when Expr.TryGetReflectedDefinition resolves is Some. TryGetReflectedDefinition will give you an entry point (if there's one to be had) into the expression tree.

The expression tree is actually a very interesting glimpse into how even imperative constructs get realized as functional compositions. Given a function like this

 
[<ReflectedDefinition>]
let public sample3 (ctx: IExecutionContext) (p2: string option) =
    let now_ts = System.DateTime.Now
    let p =
        match p2 with
        | None -> "empty"
        | Some v -> v
 
    ctx.RenderWith ("Test.template")
    (now_ts, p)
 

the expression tree looks like this

Lambda (ctx,
        Lambda (p2,
                Let (now_ts, PropGet (None, System.DateTime Now, []),
                     Let (p,
                          Let (matchValue, p2,
                               IfThenElse (UnionCaseTest (matchValue,Option`1.Some),
                                           Let (v,PropGet (Some (matchValue),
                                                         System.String Item, []),v), Value ("empty"))),
                          Sequential (Call (Some (ctx),
                                            Void RenderWith(System.String),
                                            [Value ("Test.template")]),
                                      NewTuple (now_ts, p))))))

If you take a look at the arguments of Let, you'll see that it's bind site, value and next statement. That type of chaining glues your functions together. But I digress...

So, right now, we have our expression tree and we have a MethodInfo object. That method info is the same type of method handle we would expect from any other static method. That means that we can invoke it much the same way we would -

 
// mi being our method info object, and parm_list being... well... the parameter list
let ret_val = mi.Invoke(null, parm_list)
 

So that's 2 of three. We got our expression tree, we know how to invoke our method, but what are we actually getting back?

Chances are, that's not a question you'll need to answer often, but it's still a useful piece of info. The Quotations.Patterns (at time of writing, f# ctp 1.9.6.2) namespace contains a list of active patterns that match up to the expression "function calls" that we saw in our expression tree. That means that we can recursively pattern match over our expression tree to get at its structure. We can either use specific cases to look for certain patterns

 
/// returns the first non-None result of invoking func with v1 or v2
let choose func v1 v2 =
    match func v1 with
    | Some _ as ex -> ex
    | None -> func v2
 
/// attempts to locate the return type of the given expression tree
let rec try_get_return_sig = function
| Lambda (_,ex) -> try_get_return_sig ex
| Let (_,_,cont) -> try_get_return_sig cont
| IfThenElse (_,t,e) -> choose try_get_return_sig t e
| NewTuple e -> Some <| List.map (fun (ex: Expr) -> ex.ToString(), ex.Type) e
| Sequential (f,s) -> choose try_get_return_sig f s
| TryFinally (tr,fn) -> choose try_get_return_sig tr fn
| TryWith (tr,_,wt,_,fn) -> choose (choose try_get_return_sig fn) wt tr
| Var var as ex -> Some [(ex.ToString(), ex.Type)]
| _ -> None
 

or we can use the ExprShape patterns to traverse the tree without concerning ourselves with the actual components we're navigating. What the piece of code up above is doing, is it's looking for return values that are explicit Tuple creations. I had a need to analyze functions returning tuples and peek inside their definitions to know the names of the components they're returning. This way, the user can return an arbitrary data structure, but i still get my hands on the names of the individual components i'm getting back. The pattern matches that i have listed out are the tree branches that i care about. Lambda, Let, etc can result in the production of a Tuple, and NewTuple is the actual production. Everything else (there's a significant number of other components) does things that i don't care about (like call out to other functions which may not be marked for quotation, etc), so i just ignore it.

that's it.

Alright, so i threw that blurb out there a few days back, with little more than zOMG! THIS IS COOL!!!ONE!11!. I figured a bit more detail wouldn't hurt.

One of the things that has made F# a bit more difficult to learn for me is that outside of the more basic concepts, everything is explained on a rather theoretical level. It makes sense, really - that's where functional came from, but it does make it more difficult to visualize the feature and understand their applicability. Let's see if i can do any better.

So - f# quotations are simply the full representation of the syntax tree of a fragment of code, available run-time. That means that you have access to anything within <@ @> or marked with a ReflectedDefinition attribute. The common use case that you read everywhere is that you can write code in f# and then execute it elsewhere. And that's certainly cool, but it's only one aspect. One that i've found incredibly useful is the ability to gather more information from dynamically loaded code than previously possible.

With standard reflection you get to see the shell. You get member names, method signatures (as an ordered list of types) and inheritance info (there's more, but these are the core elements). However, with quotations, i can see much more. I can get parameter names, i can get local variables i can get the full source of the block i'm evaluating!

My use for this? In bistro, I used to make the developer decorate his class with member attributes that gave me information about how that member was used. Now, I can pull that information straight from a function signature, and not require any additional markup. Here's how:

Sample target function:

 
#light
open Microsoft.FSharp.Reflection
open System.Reflection
 
module NestedProgram =
    module Program =
        [<ReflectedDefinition>]
        let public sample f_name p2 =
            printf "sample {%A}\r\n" f_name
 

Code:

 
#light
 
open System
open System.Reflection
open DefaultControllers.NestedProgram.Program
 
open Microsoft.FSharp.Quotations.Patterns
open Microsoft.FSharp.Quotations.DerivedPatterns
open Microsoft.FSharp.Quotations
 
open Microsoft.FSharp.Reflection
 
let strip (text: string) = match text.IndexOf "@" with | -1 -> text | _ as i -> text.[..i-1]
 
let rec get_parms exp =
    match exp with
    | Lambda (var,body) ->
        [strip var.Name] @ get_parms body
    | _ -> []
 
let get_info (t:System.Type) =
    if not <| FSharpType.IsModule t then failwith <| sprintf "%A is not a module" t
    else
        let funcs = t.GetMethods(BindingFlags.Static ||| BindingFlags.Public)
 
        Array.iter (fun (m: MethodInfo) ->
            match Expr.TryGetReflectedDefinition m with
            | Some ex ->
                printf "\t%s.%s %s\r\n" t.FullName m.Name (String.concat " " (get_parms ex))
            | None -> ()) funcs
 
let rec searchTypes t =
    if FSharpType.IsModule t then get_info t
 
AppDomain.CurrentDomain.GetAssemblies() |>
Array.iter (fun (asm: Assembly) ->
                printf "asm: %s\r\n" <| asm.GetName().Name
                Array.iter searchTypes (asm.GetTypes())
                )
 
ignore <| System.Console.Read()
 

This code will go through the entire loaded assembly list, find all types and give me the function signatures. How i consume that is now up to me, but it's there for the taking.

As a side note - I'm going to try and blog more about the real-world applicability of f#. I think that the notion of f# or functional programming not being applicable to web development and the like is a misconception, and hopefully i'll be able to illustrate that.

Quick blurb, more later. This is simply cool. 5 lines of code that can give you the signature of a function, with parameter names.

 
open Microsoft.FSharp.Quotations.Patterns
open Microsoft.FSharp.Quotations.DerivedPatterns
 
[<ReflectedDefinition>]
let sample f_name p2 =
    printf "sample {%A}\r\n" f_name
 
let rec get_parms exp =
    match exp with
    | Lambda (var,body) ->
        [var.Name.[..var.Name.IndexOf("@")-1]] @ get_parms body
    | _ -> []
 
List.iter (printf "%A\r\n") (get_parms <@ sample @>)
ignore <| System.Console.Read()
 

the cool thing is that because of the ReflectedDefinition attribute, I can use "sample" as both a quotation and a regular function.

Jeebus.