Saturday, February 26, 2011

Password strength, entropy, and compression

For some reason a couple of days ago I got hooked up with password strength stuff.

First, a disclaimer: I'm no security or math expert. There's some handwaving here, and it's been too many years since I studied this, but I hope I didn't make any gross conceptual errors. If I did, please tell me.

Now, if you look around you'll find lots of password strength checkers, but most of them work with a set of rules, each adding a fixed number of 'points' for password length, using numbers, symbols, etc. That's good enough for many cases, but we can do better.

The better way involves calculating the entropy of the password. In a nutshell, information entropy is a measure of unpredictability/uncertainty. 

For example, random bytes are unpredictable. Truly random bytes (i.e. not pseudo-random) would make terrific passwords if it weren't because nobody can remember them. "902c5cce62e11db18264" (10 random bytes represented in hex, courtesy of random.org) is a pretty good password. Its entropy is high. But it's also very hard to remember, so it's not very practical.

On the other hand, there's plain text. Text is much more memorable, but it's also more predictable, so plain text passwords are usually easily guessable. Unless they're long enough, but then they aren't memorable.

So there's a tension between password strength and usefulness, which prompts some to claim that passwords are broken, and gurus to refute that. Most people pick trivial memorable passwords, while security experts recommend creating strong passwords and writing them down. One way to do that would be using password managers.

Anyway, back to password strength checkers. One of the best I found is this one in Javascript. It checks a dictionary for common words (in English), and also calculates entropy using a table of letter pair frequencies in English. The character set is semi-dynamic depending on the input password. It's pretty sophisticated.

A cheaper way (for my little brain that is, not necessarily for the computer) to estimate entropy indirectly is by using compression. Entropy and compression rate are directly related: the higher the entropy in a piece of data, the harder it is to compress it, so the resulting compressed data will be longer. (EDIT: turns out this is theoretically incorrect, see discussion below)

This of course relies on having built-in compression in your platform, which Javascript on browsers has not, but in .NET we can easily write (F#):

open System.IO
open System.IO.Compression
let compressedLength (s: string) =
    use buffer = new MemoryStream()
    use comp = new DeflateStream(buffer, CompressionMode.Compress)
    use w = new StreamWriter(comp)
    w.Write(s)
    w.Flush()
    buffer.Length

Let's see how this function behaves for various potential passwords:

["a"; "god"; "123456"; "password"; "password1"; "password12"; "password1!"; "q!1[Ba5"; "902c5cce62e11db18264"; "iloveyou"; "ILoveYou"; "qwerty123456"; "q1w2e3r4t5y6"; "this is a good password"; "12345678"; "111111"; "letmein"; "qwerty"]
|> List.map (fun p -> p,compressedLength p) |> List.sortBy snd
Password Compressed length
a 98
god 100
111111 100
123456 104
password 104
iloveyou 104
letmein 104
qwerty 104
password1 106
password12 106
q!1[Ba5 106
ILoveYou 106
12345678 106
password1! 108
qwerty123456 110
q1w2e3r4t5y6 110
this is a good password 116
902c5cce62e11db18264 118

Due to header overhead, even a single character compresses to 98 bytes. Still, the results reflect quite nicely most of the common recommendations for passwords: make them as long as possible; use letters, numbers and symbols; mix upper and lower case; don't repeat characters.

I wouldn't accept a password that 'scores' less than 106. Requiring 108+ is safer but might piss off some users.

Note that this is highly platform-dependent. For example, on Python:

import zlib
p = ["a", "god", "123456", "password", "password1", "password12", "password1!", "q!1[Ba5", "902c5cce62e11db18264", "iloveyou", "ILoveYou", "qwerty123456", "q1w2e3r4t5y6", "this is a good password", "12345678", "111111", "letmein", "qwerty"]
l = [(w,len(zlib.compress(w,1))) for w in p]
sorted(l, key=lambda a:a[1])


Password Compressed length
a 9
god 11
111111 11
123456 14
qwerty 14
q!1[Ba5 15
letmein 15
password 16
iloveyou 16
ILoveYou 16
12345678 16
password1 17
password12 18
password1! 18
qwerty123456 20
q1w2e3r4t5y6 20
902c5cce62e11db18264 28
this is a good password 29

And there could be differences even between .NET versions. It would be safer to compare against some reference values instead of comparing with a 'magic' value.

Of course, entropy is but one dimension of password strength that only considers brute-force attacks, you still have to couple this with a dictionary check to filter out common passwords. And some even go as far as saying that password entropy is rarely relevant any more!

Thursday, February 10, 2011

Running Solr on .NET

Many people are reluctant to use Solr in .NET applications because it requires installing a Java runtime. It might complicate deployment for an otherwise all-Microsoft application, which is one of the reasons why the Stackoverflow team chose to use Lucene.NET instead. Personally, I think the advantages of Solr, like:

  • Much less code to develop and maintain compared to an in-house implementation of features like faceting, caching, suggestions, etc
  • Interface simpler than Lucene, yet flexible and powerful.
  • Web console.
  • Easy scaling.

(just to name a few), more than make up for the deployment hassle, at least for my applications. In other words, I think the problem of deploying Solr is easier than the problem of coding faceting, caching, suggestions, etc over Lucene(.net) efficiently. I'd rather not reinvent this wheel.

But I understand that things would be simpler if Solr just ran somehow directly on .NET. I see three ways to make that happen:

  1. Manually port the source code to .NET. Many well-known projects ported from Java took this path: log4net, Quartz.NET, NHibernate, Lucene.NET, GitSharp to name a few.
  2. Automatically port the source code to .NET. NGit and db4o use this approach, using Sharpen.
  3. Automatically convert Java bytecode to .NET IL.

All these options have their pros and cons:

Option 1 gives you the most freedom but requires the most effort, both for the initial port and for keeping up with the original code.

Option 2 still requires manual tweaks (Lluis mentions modifications both to Sharpen itself and its generated code), and generates java-ish code, whereas in the first approach you're free to translate things as you see fit. It may be convenient to write a usability layer on top of the generated code.

Option 3 is the most automatic of them all. Using IKVM you can just get the JARs, run them through ikvmc and get .NET DLLs as a result. It requires the least effort, and almost no coding at all (you still might have to wrap some Java-specific APIs). However it also requires having the whole IKVM runtime and OpenJDK at runtime which can be cumbersome and may have some negative performance impact.

In the particular case of Solr, the IKVM+OpenJDK dependency isn't really a big deal, because it's a server, not a library, and it's easily xcopy-able and not as heavy as a full Java runtime (for a standard Windows install, that is). Sure, Solr can also be embedded in Java apps, but not even the Solr team recommends it for general usage.

I actually started experimenting with Solr and IKVM back in June 2009. I ran into ClassLoader issues, and since I didn't really need it, I gave up. I've seen many people express interest in having Solr running on .NET, and I did point them to my incomplete solution, yet nobody did anything (I'm actually a bit ticked off by this).

Anyway, a few days ago I accidentally bumped into this article by Kevin Miller where he explains how to use IKVM to run Tika on .NET. I'm not (yet) interested in Tika itself, but the article also contained the solution for my ClassLoader problems.

So I got back to working on this and actually got it to a usable state. It has four modes of operations:

  1. Embedded, just like you would embed it in a Java app
  2. Server, using the embedded Jetty (launched from command-line)
  3. Server, as Windows Service (also using the embedded Jetty)
  4. Server, as a IHttpHandler, so it can be hooked up to IIS as a regular ASP.NET app.

The ASP.NET mode still needs some work: queries work, but updates don't. There's probably something wrong in the Servlet-ASP.NET adapters.

Honestly, I haven't tested it much. I still don't need it, so I don't intend to put much time on it. I haven't done any performance tests. I don't expect this to be as fast as the original Java Solr of course, since there's the whole IKVM runtime and OpenJDK in the middle, but I do believe it will have acceptable performance.

Consider this a call for contributors: SolrIKVM is currently quite usable, but I wouldn't call it production-quality yet. If you really want Solr on .NET, fork the project, try it, test it, fix the issues. Make it happen. Feel free to ask me any questions about it.

By the way, huge kudos to Jeroen Frijters, it's pretty awesome that IKVM can run Jetty and Solr like this.

Project is on github.

Tuesday, February 8, 2011

Validation in formlets

Last time, we broke up formlets into primitive applicative functors, then composed these primitives to produce formlets.

So far, if someone entered an unexpected value in our little implementation of formlets (e.g. "abc" in an int Formlet), we'd get a nasty exception and there wasn't much we could do about it because we couldn't trace the exception to the formlet that was producing it. What we want, instead of an exception, is something that accumulates errors without interrupting the computation flow. Applicative functors, being oblivious, are perfect for that. More concretely, we want to:

  1. Know if the formlet was able to collect the value or not, and 
  2. if it couldn't, get the formlet rendered with the values the user entered and error messages, so we can re-display this second form, giving the user a chance to correct his mistakes.

The first item is a job for the option type. We'll return Some v if the formlet was successful and None if it wasn't.

For the second, we already have a XmlWriter applicative, so we could just reuse it to build this "error form".

Recall the type of formlets as we defined it last time:

type 'a Formlet = 'a Environ XmlWriter NameGen

Adding the two concerns we just mentioned, the signature becomes:

type 'a Formlet = 'a Error XmlWriter Environ XmlWriter NameGen

where Error is the Maybe monad in applicative form (remember that every monad is also an applicative functor).

This is what I was talking about when I mentioned formlets being extensible: you can extend formlet features by composing additional applicatives.

By the way, here's the same formlet type expressed using C# bracket style (which F# also supports):

type Formlet<'a> = NameGen<XmlWriter<Environ<XmlWriter<Error<'a>>>>>

See now why I prefer ML syntax? Bracket style looks quite messy once you start nesting many types.

Anyway, it's not enough to compose these applicatives, we also need some way to define how to validate things and how to show error messages. Let's define a validator type:

/// Validator type. 
/// Fst determines if value is valid 
/// Snd builds an error message 
type 'a Validator = ('a -> bool) * ('a -> xml_item list -> xml_item list)

and a function that attaches a validator to a formlet:

satisfies : 'a Validator -> 'a Formlet -> 'a Formlet

(I'm not going to bore you with implementation details in this post)
So we can now write:

let isInt = Int32.TryParse >> fst 
let intErrorMsg a xml = xml @ [ Tag("span", ["class","error"], [Text(sprintf "'%s' is not a valid number" a)]) ] 
let inputInt = input |> satisfies (isInt, intErrorMsg) |> lift int

When rendered the first time, this formlet doesn't show anything different:

printfn "%s" (render inputInt)

<input name="input_0" value=""/>

If we enter an invalid value, validation kicks in:

let env = EnvDict.fromValueSeq ["input_0","abc"] 
match run inputInt env with 
| _, Some v -> printfn "Formlet successful, value %d" v 
| errorForm, None -> printfn "Formlet unsuccessful, error form: \n%A" (XmlWriter.render errorForm)

This will print:

Formlet unsuccessful, error form: 
<div> 
    <input name="input_0" value="abc" /> 
    <span class="error">'abc' is not a valid number</span> 
</div>

We might want to wrap all that XML/HTML manipulation in order to make defining validators easier, for example:

/// <summary> 
/// Constructs a validator 
/// </summary> 
/// <param name="isValid">Determines if value is valid</param> 
/// <param name="errorMsg">Builds the error message</param> 
let err (isValid: 'a -> bool) (errorMsg: 'a -> string) : 'a Validator = 
    let addError value xml = 
        [ Tag("span", ["class","errorinput"], xml) 
          Tag("span", ["class","error"], [Text(errorMsg value)]) ]
    isValid, addError

Now we can code inputInt as:

let inputInt = input |> satisfies (err isInt (sprintf "'%s' is not a valid number")) |> lift int

We can chain as many validators as we want for any formlet. For example, here's a formlet that checks that the submitted value falls within a specified range:

let isInRange min max n = n >= min && n <= max
let inputRange min max = inputInt |> satisfies (err (isInRange min max) (fun _ -> sprintf "Value must be between %d and %d" min max))
let input10to40 = inputRange 10 40

Note how I used inputInt as the starting point for inputRange. inputInt is already validated for integers, so any non-integers values fed to inputRange will fail with the same error message as before. inputRange adds further validation on top of inputInt's validation. This is another example of the composability of formlets.

I put up a fully-fledged implementation of formlets, including validation, on github. There are some minor differences with what I've written so far about formlets. I'll blog about these differences soon.

As with all my previous articles on formlets, I have to give credit to the Links team; these blog posts and code are mostly just a rehash of their papers, which I can't recommend enough.

Tuesday, January 25, 2011

A factored implementation of formlets in F#

In my last post I showed a bare bones implementation of formlets. You may have noticed that formlets do a lot of stuff:

  • Generating form element names
  • Handling submitted values
  • Building and rendering HTML

That's a lot of responsibilities for a single module. Even the type of a formlet reflects this, it's pretty complex:

type 'a Formlet = int -> (xml_item list * ((string * string) list -> 'a) * int)

And we haven't even looked at adding validation, which would complicate things further. Bottom line: there is no clear separation of concerns.

The good news are: we already have identified those concerns (the bulleted list above), and applicative functors are easily composable, so we can model each of those concerns as independent applicative functors, then compose them to yield formlets.

HTML building

As usual, we start by defining types: the same definition for XML trees:

type xml_item =
    | Text of string
    | Tag of string * (string*string) list * xml_item list

And the type of the applicative functor itself:

type 'a XmlWriter = xml_item list * 'a

A XML forest and something else. That 'something else' is what will enable the composition of this applicative with others.

Finally, the implementation. If you compare this with the implementation of formlets described in the previous post, function by function, you'll see that this is effectively a stripped down applicative that only deals with XML.

module XmlWriter =
    let puree (v: 'a) : 'a XmlWriter = [],v
    let (<*>) (f: ('a -> 'b) XmlWriter) (a: 'a XmlWriter) : 'b XmlWriter =
        fst f @ fst a, (snd f) (snd a)
    let lift f a = puree f <*> a
    let lift2 f a b = puree f <*> a <*> b
    let plug (f: xml_item list -> xml_item list) (a: 'a XmlWriter) : 'a XmlWriter =
        f (fst a), snd a
    let xml (e: xml_item list): unit XmlWriter = e,()
    let text (s: string) : unit XmlWriter =
        xml [Text s]
    let tag (t: string) (attr: (string*string) list) (v: 'a XmlWriter) : 'a XmlWriter =
        plug (fun x -> [Tag(t, attr, x)]) v

    open System.Xml.Linq
    let render (xml: xml_item list) : XDocument =
        let (!!) t = XName.op_Implicit t
        let xtext (s: string) = XText s :> XObject
        let xattr (name, value) = XAttribute(!!name, value) :> XObject
        let xattrs attr = List.map xattr attr
        let xelem name attr children = XElement(!!name, attr @ children) :> XObject
        let rec renderForest x =
            let render' =
                function
                | Text t -> xtext t
                | Tag(name, attr, children) -> xelem name (xattrs attr) (renderForest children)
            List.map render' x
        let root = xelem "div" [] (renderForest xml)
        XDocument root

The only additional function here is plug, which maps the XML forest in a XmlWriter applicative. It's not of much use here and could be inlined, but it will be useful later to implement validation (in a future post).

Environment handling

The environment (or collector) applicative is one that fetches (collects) a value from the environment (usually Request.Form in ASP.NET). As such, its type is

type 'a Environ = (string*string) list -> 'a

The implementation:

module Environ =
    let puree v = fun env -> v
    let (<*>) (f: ('a -> 'b) Environ) (a: 'a Environ) : 'b Environ =
        fun env ->
            let g = f env
            g(a(env))
    let lift f a = puree f <*> a
    let lookup (n: string) : string Environ =
        fun env ->
            match List.tryFind (fun (k,_) -> k = n) env with
            | Some (_,v) -> v
            | _ -> failwithf "Key %s not found in environment" n

Note the lookup function, it's an Environ constructor that implements the core functionality of "given this key and this environment, give me the corresponding value". It's pretty much a dictionary in applicative form.

We'll also add here a helper function to convert a NameValueCollection (like Request.Form) to an environment:

    open System.Collections.Specialized
    let fromNV (a: NameValueCollection) =
        a.AllKeys
        |> Seq.collect (fun k -> a.GetValues k |> Seq.map (fun v -> k,v))
        |> Seq.toList

Name generation

We've seen how formlets automatically generate form element names. While the actual generation is provided by nextName, the counter used is carried over from application to application, since this is purely functional code, without state:

type 'a NameGen = int -> 'a * int
module NameGen =
    let puree (v : 'a) : 'a NameGen = 
        fun gen -> v,gen
    let (<*>) (f: ('a -> 'b) NameGen) (a: 'a NameGen) : 'b NameGen = 
        fun gen ->
            let v,gen = f gen
            let w,gen = a gen
            v w, gen
    let lift f a = puree f <*> a
    let lift2 f a b = puree f <*> a <*> b
    let nextName : string NameGen =
        fun gen ->
            "input_" + gen.ToString(), gen+1
    let run (c: 'a NameGen) : 'a = fst (c 0)

Here's a simple example of name generation:

> open NameGen;; 
> let names = puree (printfn "%s %s") <*> nextName <*> nextName;; 
> run names;; 
input_0 input_1

Composing applicatives

Applicative functors are easily composable, and the composition of any two applicatives is an applicative (math people say they're closed under composition). Interestingly, monads are not closed under composition, which as far as I understand is the reason for having monad transformers, but this doesn't seem to be a problem in F# since monads aren't as ubiquitous as in Haskell anyway.

Composing two applicatives is as simple as applying one applicative's pure to the other applicative's pure, and lifting <*>. Again, since we can't abstract type constructors, we can't perform composition generically, but we can always do it ad-hoc.

type 'a EnvironXmlWriter = 'a Environ XmlWriter

Expanding the types, this means

type 'a EnvironXmlWriter = xml_item list * ((string * string) list -> 'a)

The implementation:

module EnvironXmlWriter =
    let puree (v: 'a) : 'a Environ XmlWriter = 
        v |> Environ.puree |> XmlWriter.puree 
    let (<*>) (f: ('a -> 'b) Environ XmlWriter) (a: 'a Environ XmlWriter) : 'b Environ XmlWriter = 
        XmlWriter.lift2 Environ.(<*>) f a
    let lift f a = puree f <*> a

We'll also add a refine function that lets us build the composition from the "wrapping" applicative (in our case XmlWriter). Building it from the nested applicative is as easy as applying XmlWriter.pure.

    let refine (x: 'a XmlWriter) : 'a Environ XmlWriter =
        XmlWriter.lift Environ.puree x

Example:

let input : string Environ XmlWriter =  
    let xml = [Tag("input",["name","firstname"],[])] 
    let lookup = Environ.lookup "firstname"
    xml,lookup

This is almost a formlet. Just like a fully-fledged formlet, it has a XML part that can be rendered, and an associated collector. The only thing missing here is the automatic name generation applied to both the XML element and the collector.

Finally Formlets

All we have to do now is compose EnvironXmlWriter with NameGen to yield Formlets. Its type is:

type 'a Formlet = 'a EnvironXmlWriter NameGen

or

type 'a Formlet = 'a Environ XmlWriter NameGen

or if we expand each type:

type 'a Formlet = int -> (xml_item list * ((string * string) list -> 'a) * int)

which is exactly what we had in the last post. As you can see, factoring it to primitive applicatives has given us a clearer definition.

The implementation of formlets is almost trivial now:

module Formlet =
    let puree v : _ Formlet = v |> EnvironXmlWriter.puree |> NameGen.puree
    let (<*>) (f: ('a -> 'b) Formlet) (a: 'a Formlet) : 'b Formlet =
        NameGen.lift2 EnvironXmlWriter.(<*>) f a
    let lift f a : _ Formlet = puree f <*> a
    let lift2 f a b : _ Formlet = puree f <*> a <*> b
    let ( *>) f a : _ Formlet = lift2 (fun _ z -> z) f a
    let ( <*) f a : _ Formlet = lift2 (fun z _ -> z) f a
    let xml (x: xml_item list) : unit Formlet =
        NameGen.puree (EnvironXmlWriter.refine (XmlWriter.xml x))
    let text (s: string) : unit Formlet =
        xml [Text s]
    let tag (t: string) (attr: (string*string) list) (f: 'a Formlet) : 'a Formlet =
        NameGen.lift (XmlWriter.tag t attr) f
    let input : string Formlet =
        let xml name = XmlWriter.tag "input" ["name",name]
        let lookup name = XmlWriter.puree (Environ.lookup name)
        let tag name = xml name (lookup name)
        NameGen.lift tag NameGen.nextName
    let br: unit Formlet = xml [Tag("br",[],[])]
    let run (f: 'a Formlet) : 'a Environ =
        NameGen.run f |> snd

    open System.Xml.Linq
    let render (f: _ Formlet) = 
        NameGen.run f |> fst |> XmlWriter.render
F# Web Snippets

Factoring formlets like this not only has the advantage of producing cleaner code, but also enables the reusability of each applicative functor and extending formlets more easily, as we'll see in a future post.

Full source code is here. This implementation is interchangeable with the one in my last post, the project includes both implementations so you can compare them side by side. Most of this code was taken almost verbatim from the original papers on formlets.

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

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

--------------------

type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>

  type: int<'Measure>
  implements: System.IComparable
  implements: System.IConvertible
  implements: System.IFormattable
  implements: System.IComparable<int<'Measure>>
  implements: System.IEquatable<int<'Measure>>
  inherits: System.ValueType


--------------------

type int = int32

Full name: Microsoft.FSharp.Core.int

  type: int
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<int>
  implements: System.IEquatable<int>
  inherits: System.ValueType
val puree : 'a -> int -> 'a * int

Full name: Formlets.NameGen.puree
val v : 'a
type 'a NameGen = int -> 'a * int

Full name: Formlets.NameGen<_>
val gen : int

  type: int
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<int>
  implements: System.IEquatable<int>
  inherits: System.ValueType
val f : ('a -> 'b) NameGen
val a : 'a NameGen
val v : ('a -> 'b)
val w : 'a
val lift : ('a -> 'b) -> 'a NameGen -> 'b NameGen

Full name: Formlets.NameGen.lift
val f : ('a -> 'b)
val lift2 : ('a -> 'b -> 'c) -> 'a NameGen -> 'b NameGen -> 'c NameGen

Full name: Formlets.NameGen.lift2
val f : ('a -> 'b -> 'c)
val b : 'b NameGen
val nextName : int -> string * int

Full name: Formlets.NameGen.nextName
Multiple items
val string : 'T -> string

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

--------------------

type string = System.String

Full name: Microsoft.FSharp.Core.string

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>
Multiple overloads
System.Object.ToString() : string
System.Int32.ToString(provider: System.IFormatProvider) : string
System.Int32.ToString(format: string) : string
System.Int32.ToString(format: string, provider: System.IFormatProvider) : string
val run : 'a NameGen -> 'a

Full name: Formlets.NameGen.run
val c : 'a NameGen
val fst : ('T1 * 'T2) -> 'T1

Full name: Microsoft.FSharp.Core.Operators.fst
type 'a Environ = (string * string) list -> 'a

Full name: Formlets.Environ<_>
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>

  type: 'T list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<'T>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<'T>
  implements: System.Collections.IEnumerable
val puree : 'a -> 'b -> 'a

Full name: Formlets.Environ.puree
val env : 'b
val f : ('a -> 'b) Environ
val a : 'a Environ
val env : (string * string) list

  type: (string * string) list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<string * string>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<string * string>
  implements: System.Collections.IEnumerable
val g : ('a -> 'b)
val lift : ('a -> 'b) -> 'a Environ -> 'b Environ

Full name: Formlets.Environ.lift
val lookup : string -> (string * string) list -> string

Full name: Formlets.Environ.lookup
val n : string

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------

type List<'T> =
  | ( [] )
  | ( :: ) of 'T * 'T list
  with
    interface System.Collections.IEnumerable
    interface System.Collections.Generic.IEnumerable<'T>
    member Head : 'T
    member IsEmpty : bool
    member Item : index:int -> 'T with get
    member Length : int
    member Tail : 'T list
    static member Cons : head:'T * tail:'T list -> 'T list
    static member Empty : 'T list
  end

Full name: Microsoft.FSharp.Collections.List<_>

  type: List<'T>
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<'T>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<'T>
  implements: System.Collections.IEnumerable
val tryFind : ('T -> bool) -> 'T list -> 'T option

Full name: Microsoft.FSharp.Collections.List.tryFind
val k : string

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>
union case Option.Some: 'T -> Option<'T>
val v : string

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>
val failwithf : Printf.StringFormat<'T,'Result> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.failwithf
namespace System
namespace System.Collections
namespace System.Collections.Specialized
val fromNV : NameValueCollection -> (string * string) list

Full name: Formlets.Environ.fromNV
val a : NameValueCollection

  type: NameValueCollection
  implements: System.Collections.ICollection
  implements: System.Collections.IEnumerable
  implements: System.Runtime.Serialization.ISerializable
  implements: System.Runtime.Serialization.IDeserializationCallback
  inherits: NameObjectCollectionBase
type NameValueCollection =
  class
    inherit System.Collections.Specialized.NameObjectCollectionBase
    new : unit -> System.Collections.Specialized.NameValueCollection
    new : System.Collections.Specialized.NameValueCollection -> System.Collections.Specialized.NameValueCollection
    new : System.Collections.IHashCodeProvider * System.Collections.IComparer -> System.Collections.Specialized.NameValueCollection
    new : int -> System.Collections.Specialized.NameValueCollection
    new : System.Collections.IEqualityComparer -> System.Collections.Specialized.NameValueCollection
    new : int * System.Collections.IEqualityComparer -> System.Collections.Specialized.NameValueCollection
    new : int * System.Collections.Specialized.NameValueCollection -> System.Collections.Specialized.NameValueCollection
    new : int * System.Collections.IHashCodeProvider * System.Collections.IComparer -> System.Collections.Specialized.NameValueCollection
    member Add : System.Collections.Specialized.NameValueCollection -> unit
    member Add : string * string -> unit
    member AllKeys : string []
    member Clear : unit -> unit
    member CopyTo : System.Array * int -> unit
    member Get : string -> string
    member Get : int -> string
    member GetKey : int -> string
    member GetValues : string -> string []
    member GetValues : int -> string []
    member HasKeys : unit -> bool
    member Item : string -> string with get, set
    member Item : int -> string
    member Remove : string -> unit
    member Set : string * string -> unit
  end

Full name: System.Collections.Specialized.NameValueCollection

  type: NameValueCollection
  implements: System.Collections.ICollection
  implements: System.Collections.IEnumerable
  implements: System.Runtime.Serialization.ISerializable
  implements: System.Runtime.Serialization.IDeserializationCallback
  inherits: NameObjectCollectionBase
property NameValueCollection.AllKeys: string []
module Seq

from Microsoft.FSharp.Collections
val collect : ('T -> #seq<'U>) -> seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.collect
Multiple overloads
NameValueCollection.GetValues(index: int) : string []
NameValueCollection.GetValues(name: string) : string []
val map : ('T -> 'U) -> seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map
val toList : seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.Seq.toList
type xml_item =
  | Text of string
  | Tag of string * (string * string) list * xml_item list

Full name: Formlets.xml_item

  type: xml_item
  implements: System.IEquatable<xml_item>
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<xml_item>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
union case xml_item.Text: string -> xml_item
union case xml_item.Tag: string * (string * string) list * xml_item list -> xml_item
type 'a XmlWriter = xml_item list * 'a

Full name: Formlets.XmlWriter<_>
val puree : 'a -> 'a XmlWriter

Full name: Formlets.XmlWriter.puree
val f : ('a -> 'b) XmlWriter
val a : 'a XmlWriter
val snd : ('T1 * 'T2) -> 'T2

Full name: Microsoft.FSharp.Core.Operators.snd
val lift : ('a -> 'b) -> xml_item list * 'a -> 'b XmlWriter

Full name: Formlets.XmlWriter.lift
val lift2 : ('a -> 'b -> 'c) -> xml_item list * 'a -> xml_item list * 'b -> 'c XmlWriter

Full name: Formlets.XmlWriter.lift2
val b : 'b XmlWriter
val plug : (xml_item list -> xml_item list) -> xml_item list * 'a -> 'a XmlWriter

Full name: Formlets.XmlWriter.plug
val f : (xml_item list -> xml_item list)
val xml : xml_item list -> unit XmlWriter

Full name: Formlets.XmlWriter.xml
val e : xml_item list

  type: xml_item list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<xml_item>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<xml_item>
  implements: System.Collections.IEnumerable
type unit = Unit

Full name: Microsoft.FSharp.Core.unit

  type: unit
  implements: System.IComparable
val text : string -> unit XmlWriter

Full name: Formlets.XmlWriter.text
val s : string

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>
val tag : string -> (string * string) list -> xml_item list * 'a -> 'a XmlWriter

Full name: Formlets.XmlWriter.tag
val t : string

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>
val attr : (string * string) list

  type: (string * string) list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<string * string>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<string * string>
  implements: System.Collections.IEnumerable
val v : 'a XmlWriter
val x : xml_item list

  type: xml_item list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<xml_item>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<xml_item>
  implements: System.Collections.IEnumerable
namespace System.Xml
namespace System.Xml.Linq
val render : xml_item list -> XDocument

Full name: Formlets.XmlWriter.render
val xml : xml_item list

  type: xml_item list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<xml_item>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<xml_item>
  implements: System.Collections.IEnumerable
type XDocument =
  class
    inherit System.Xml.Linq.XContainer
    new : unit -> System.Xml.Linq.XDocument
    new : obj [] -> System.Xml.Linq.XDocument
    new : System.Xml.Linq.XDeclaration * obj [] -> System.Xml.Linq.XDocument
    new : System.Xml.Linq.XDocument -> System.Xml.Linq.XDocument
    member Declaration : System.Xml.Linq.XDeclaration with get, set
    member DocumentType : System.Xml.Linq.XDocumentType
    member NodeType : System.Xml.XmlNodeType
    member Root : System.Xml.Linq.XElement
    member Save : string -> unit
    member Save : System.IO.TextWriter -> unit
    member Save : System.Xml.XmlWriter -> unit
    member Save : string * System.Xml.Linq.SaveOptions -> unit
    member Save : System.IO.TextWriter * System.Xml.Linq.SaveOptions -> unit
    member WriteTo : System.Xml.XmlWriter -> unit
    static member Load : string -> System.Xml.Linq.XDocument
    static member Load : System.IO.TextReader -> System.Xml.Linq.XDocument
    static member Load : System.Xml.XmlReader -> System.Xml.Linq.XDocument
    static member Load : string * System.Xml.Linq.LoadOptions -> System.Xml.Linq.XDocument
    static member Load : System.IO.TextReader * System.Xml.Linq.LoadOptions -> System.Xml.Linq.XDocument
    static member Load : System.Xml.XmlReader * System.Xml.Linq.LoadOptions -> System.Xml.Linq.XDocument
    static member Parse : string -> System.Xml.Linq.XDocument
    static member Parse : string * System.Xml.Linq.LoadOptions -> System.Xml.Linq.XDocument
  end

Full name: System.Xml.Linq.XDocument

  type: XDocument
  implements: System.Xml.IXmlLineInfo
  inherits: XContainer
  inherits: XNode
  inherits: XObject
type XName =
  class
    member Equals : obj -> bool
    member GetHashCode : unit -> int
    member LocalName : string
    member Namespace : System.Xml.Linq.XNamespace
    member NamespaceName : string
    member ToString : unit -> string
    static member Get : string -> System.Xml.Linq.XName
    static member Get : string * string -> System.Xml.Linq.XName
  end

Full name: System.Xml.Linq.XName

  type: XName
  implements: System.IEquatable<XName>
  implements: System.Runtime.Serialization.ISerializable
XName.op_Implicit(expandedName: string) : XName
val xtext : (string -> XObject)
type XText =
  class
    inherit System.Xml.Linq.XNode
    new : string -> System.Xml.Linq.XText
    new : System.Xml.Linq.XText -> System.Xml.Linq.XText
    member NodeType : System.Xml.XmlNodeType
    member Value : string with get, set
    member WriteTo : System.Xml.XmlWriter -> unit
  end

Full name: System.Xml.Linq.XText

  type: XText
  implements: System.Xml.IXmlLineInfo
  inherits: XNode
  inherits: XObject
type XObject =
  class
    member AddAnnotation : obj -> unit
    member Annotation<'T> : unit -> 'T
    member Annotation : System.Type -> obj
    member Annotations<'T> : unit -> System.Collections.Generic.IEnumerable<'T>
    member Annotations : System.Type -> System.Collections.Generic.IEnumerable<obj>
    member BaseUri : string
    member Document : System.Xml.Linq.XDocument
    member NodeType : System.Xml.XmlNodeType
    member Parent : System.Xml.Linq.XElement
    member RemoveAnnotations<'T> : unit -> unit
    member RemoveAnnotations : System.Type -> unit
  end

Full name: System.Xml.Linq.XObject

  type: XObject
  implements: System.Xml.IXmlLineInfo
val xattr : (string * 'a -> XObject)
val name : string

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>
val value : 'a
type XAttribute =
  class
    inherit System.Xml.Linq.XObject
    new : System.Xml.Linq.XName * obj -> System.Xml.Linq.XAttribute
    new : System.Xml.Linq.XAttribute -> System.Xml.Linq.XAttribute
    member IsNamespaceDeclaration : bool
    member Name : System.Xml.Linq.XName
    member NextAttribute : System.Xml.Linq.XAttribute
    member NodeType : System.Xml.XmlNodeType
    member PreviousAttribute : System.Xml.Linq.XAttribute
    member Remove : unit -> unit
    member SetValue : obj -> unit
    member ToString : unit -> string
    member Value : string with get, set
    static member EmptySequence : System.Collections.Generic.IEnumerable<System.Xml.Linq.XAttribute>
  end

Full name: System.Xml.Linq.XAttribute

  type: XAttribute
  implements: System.Xml.IXmlLineInfo
  inherits: XObject
val xattrs : ((string * 'a) list -> XObject list)
val attr : (string * 'a) list

  type: (string * 'a) list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<string * 'a>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<string * 'a>
  implements: System.Collections.IEnumerable
val map : ('T -> 'U) -> 'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map
val xelem : (string -> 'a list -> 'a list -> XObject)
val attr : 'a list

  type: 'a list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<'a>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<'a>
  implements: System.Collections.IEnumerable
val children : 'a list

  type: 'a list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<'a>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<'a>
  implements: System.Collections.IEnumerable
type XElement =
  class
    inherit System.Xml.Linq.XContainer
    new : System.Xml.Linq.XName -> System.Xml.Linq.XElement
    new : System.Xml.Linq.XName * obj -> System.Xml.Linq.XElement
    new : System.Xml.Linq.XName * obj [] -> System.Xml.Linq.XElement
    new : System.Xml.Linq.XElement -> System.Xml.Linq.XElement
    new : System.Xml.Linq.XStreamingElement -> System.Xml.Linq.XElement
    member AncestorsAndSelf : unit -> System.Collections.Generic.IEnumerable<System.Xml.Linq.XElement>
    member AncestorsAndSelf : System.Xml.Linq.XName -> System.Collections.Generic.IEnumerable<System.Xml.Linq.XElement>
    member Attribute : System.Xml.Linq.XName -> System.Xml.Linq.XAttribute
    member Attributes : unit -> System.Collections.Generic.IEnumerable<System.Xml.Linq.XAttribute>
    member Attributes : System.Xml.Linq.XName -> System.Collections.Generic.IEnumerable<System.Xml.Linq.XAttribute>
    member DescendantNodesAndSelf : unit -> System.Collections.Generic.IEnumerable<System.Xml.Linq.XNode>
    member DescendantsAndSelf : unit -> System.Collections.Generic.IEnumerable<System.Xml.Linq.XElement>
    member DescendantsAndSelf : System.Xml.Linq.XName -> System.Collections.Generic.IEnumerable<System.Xml.Linq.XElement>
    member FirstAttribute : System.Xml.Linq.XAttribute
    member GetDefaultNamespace : unit -> System.Xml.Linq.XNamespace
    member GetNamespaceOfPrefix : string -> System.Xml.Linq.XNamespace
    member GetPrefixOfNamespace : System.Xml.Linq.XNamespace -> string
    member HasAttributes : bool
    member HasElements : bool
    member IsEmpty : bool
    member LastAttribute : System.Xml.Linq.XAttribute
    member Name : System.Xml.Linq.XName with get, set
    member NodeType : System.Xml.XmlNodeType
    member RemoveAll : unit -> unit
    member RemoveAttributes : unit -> unit
    member ReplaceAll : obj -> unit
    member ReplaceAll : obj [] -> unit
    member ReplaceAttributes : obj -> unit
    member ReplaceAttributes : obj [] -> unit
    member Save : string -> unit
    member Save : System.IO.TextWriter -> unit
    member Save : System.Xml.XmlWriter -> unit
    member Save : string * System.Xml.Linq.SaveOptions -> unit
    member Save : System.IO.TextWriter * System.Xml.Linq.SaveOptions -> unit
    member SetAttributeValue : System.Xml.Linq.XName * obj -> unit
    member SetElementValue : System.Xml.Linq.XName * obj -> unit
    member SetValue : obj -> unit
    member Value : string with get, set
    member WriteTo : System.Xml.XmlWriter -> unit
    static member EmptySequence : System.Collections.Generic.IEnumerable<System.Xml.Linq.XElement>
    static member Load : string -> System.Xml.Linq.XElement
    static member Load : System.IO.TextReader -> System.Xml.Linq.XElement
    static member Load : System.Xml.XmlReader -> System.Xml.Linq.XElement
    static member Load : string * System.Xml.Linq.LoadOptions -> System.Xml.Linq.XElement
    static member Load : System.IO.TextReader * System.Xml.Linq.LoadOptions -> System.Xml.Linq.XElement
    static member Load : System.Xml.XmlReader * System.Xml.Linq.LoadOptions -> System.Xml.Linq.XElement
    static member Parse : string -> System.Xml.Linq.XElement
    static member Parse : string * System.Xml.Linq.LoadOptions -> System.Xml.Linq.XElement
  end

Full name: System.Xml.Linq.XElement

  type: XElement
  implements: System.Xml.IXmlLineInfo
  implements: System.Xml.Serialization.IXmlSerializable
  inherits: XContainer
  inherits: XNode
  inherits: XObject
val renderForest : (xml_item list -> XObject list)
val render' : (xml_item -> XObject)
val children : xml_item list

  type: xml_item list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<xml_item>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<xml_item>
  implements: System.Collections.IEnumerable
val root : XObject

  type: XObject
  implements: System.Xml.IXmlLineInfo
val puree : 'a -> 'a Environ XmlWriter

Full name: Formlets.EnvironXmlWriter.puree
Multiple items
module Environ

from Formlets

--------------------

type 'a Environ = (string * string) list -> 'a

Full name: Formlets.Environ<_>
Multiple items
module XmlWriter

from Formlets

--------------------

type 'a XmlWriter = xml_item list * 'a

Full name: Formlets.XmlWriter<_>
val f : ('a -> 'b) Environ XmlWriter
val a : 'a Environ XmlWriter
val lift : ('a -> 'b) -> xml_item list * 'a Environ -> 'b Environ XmlWriter

Full name: Formlets.EnvironXmlWriter.lift
val refine : xml_item list * 'a -> 'a Environ XmlWriter

Full name: Formlets.EnvironXmlWriter.refine
val x : 'a XmlWriter
type 'a Formlet = 'a Environ XmlWriter NameGen

Full name: Formlets.Formlet<_>
Multiple items
module NameGen

from Formlets

--------------------

type 'a NameGen = int -> 'a * int

Full name: Formlets.NameGen<_>
type AutoOpenAttribute =
  class
    inherit System.Attribute
    new : unit -> AutoOpenAttribute
    new : path:string -> AutoOpenAttribute
    member Path : string
  end

Full name: Microsoft.FSharp.Core.AutoOpenAttribute

  type: AutoOpenAttribute
  implements: System.Runtime.InteropServices._Attribute
  inherits: System.Attribute
Multiple items
module Formlet

from Formlets

--------------------

type 'a Formlet = 'a Environ XmlWriter NameGen

Full name: Formlets.Formlet<_>
val puree : 'a -> 'a Formlet

Full name: Formlets.Formlet.puree
module EnvironXmlWriter

from Formlets
val f : ('a -> 'b) Formlet
val a : 'a Formlet
val lift : ('a -> 'b) -> 'a Formlet -> 'b Formlet

Full name: Formlets.Formlet.lift
val lift2 : ('a -> 'b -> 'c) -> 'a Formlet -> 'b Formlet -> 'c Formlet

Full name: Formlets.Formlet.lift2
val b : 'b Formlet
val f : 'a Formlet
val a : 'b Formlet
val z : 'b
val z : 'a
val xml : xml_item list -> unit Formlet

Full name: Formlets.Formlet.xml
val text : string -> unit Formlet

Full name: Formlets.Formlet.text
val tag : string -> (string * string) list -> 'a Formlet -> 'a Formlet

Full name: Formlets.Formlet.tag
val input : string Formlet

Full name: Formlets.Formlet.input
val xml : (string -> 'a XmlWriter -> 'a XmlWriter)
val lookup : (string -> string Environ XmlWriter)
val tag : (string -> string Environ XmlWriter)
val br : unit Formlet

Full name: Formlets.Formlet.br
val run : 'a Formlet -> 'a Environ

Full name: Formlets.Formlet.run
val render : 'a Formlet -> XDocument

Full name: Formlets.Formlet.render