Pretty-Printed Code Blocks in LaTeX

I came across PLT Scribble which appears to be the best tool available today for writing documentation. You write text with some Scheme in it, it generates HTML and LaTeX. Without much ado, I could use PLT Racket to define a lexer for F# that pretty-prints code blocks. It worked beautifully for HTML, but in LaTeX I hit a problem – how do I define a macro that typesets its argument with preserved whitespace and mono-space font, while keeping other commands as-is?

Note, verbatim does not work – it types inner commands verbatim, instead of applying them to, say, make keywords blue. There is alltt and fancyvrb but they do not work either: somehow they change the reader too much. Scribble generated commands of the form “\char’146” that LaTeX accepts in default mode but fails to accept inside alltt or Verbatim from fancyvrb.

I knew then I had no choice but to roll my own..

Enter 1970-s text processing technology. Without proper documentation either, because I do not currently have a copy of the TeX book handy. Anyhow, here is what I got after more time than I care to admit:

Groking HOAS in F#

It is 3 AM in Budapest and, quite typically, I cannot sleep since my mind is actively engaged in remembering all the functional programming tricks I have read about. So, tonight it is HOAS, or Higher Order Abstract Syntax. If you have ever implemented a De Bruijn-indexed AST for Scheme and spent a few days catching indexing bugs, you surely would appreciate the beauty of this:

Where F#/.NET Falls Short: Higher Kinds

Every programmer thinks their favorite language has a problem. I am no exception. I used to think that F# misses an ML module system or Haskell-style typeclasses, but I came to realize that the complaint is really about a feature called higher-kinded polymorphism. Without this feature, there is a lot of very beautiful, general, and type-safe code in OCaml and Haskell that cannot be expressed in type-safe F#. It can be expressed, but you are facing a tradeoff:

• Sacrifice generality – this is what workflow builders do. In effect, F# has no true monads, because you cannot easily write code generalized over an arbitrary monad.
  
• Sacrifice type safety by using downcasts and rely on convention.

Option #1 is by far the most popular, but very detrimental to the F# ecosystem, as it encourages duplication of specific code that could have otherwise been expressed by a single, general definition.

Option #2 is controversial. I have attempted a few encodings I personally have not yet found a practical one, and in practice usually fall back to Option #1.

To illustrate, suppose we have this Haskell code:

Functor type class is parameterized over f, which is itself generic. This is exactly the piece that .NET and F# are lacking. If one really insists on writing code that is generic in every possible Functor, not just a concrete Functor instance, one ends up having to rely on downcasts and convention:

As you can see, this approach (1) has a run-time cost and (2) gets annoying very quickly as the complexity of the code grows.

It is sad.

The Sad State of fshtmldoc – Can We Do Better?

If you ever tried to generate HTML documentation to document the API of F#-produced assemblies, you have likely tried fshtmldoc, a tool that is a part of F# PowerPack. It does a few things well and another couple of things not so well, there is a single overarching problem this tool. It uses System.Reflection.

Why is System.Reflection evil? In fact it is not, it is simply an API designed for a purpose vastly different from ours (HTML API report generation). The side effects of using these APIs are: the runtime needs to load the documented assemblies, and their references, which is slow and error-prone. fshtmldoc often crashes as it cannot find a reference. Also, the runtime cannot unload these assemblies. So, using this from an MS Build task, for example, is not an option, as it can make your Visual Studio session leak memory.

Is there an alternative? A non-alternative is to use C#-centric tools such as monodoc or SandCastle. These tools do not know anything about F# constructs, and are likely to produce output that will easily confuse you for code that is highly functional – full of function types, unions, records.

Enter Mono.Cecil. There is the alternative reflection and bytecode-manipulation library. It addresses all of the above problems. Could we base a documentation tool on Cecil? Yes. All that needs to be done, is to detect F# constructs from metadata.

The good news is I have almost completed this – remaining tasks are fairly minor. I am testing this out on a bunch of our IntelliFactory assemblies. More coming soon..

Home-made Regular Expressions in F#: Thompson NFA

Russ Cox re-discovered and popularized an old (originating in a 1968 paper by Thompson) technique for implementing regular expressions: http://swtch.com/~rsc/regexp/regexp1.html. The article offers a wonderfully simple to understand presentation, and I just could not resist trying it in F#.

First, the regular expressions themselves: the source language can be nicely described with a union type, encompassing the empty string, choice, concatenation, the Kleene star, and a token parser. The  algorithm is general enough to accept the Filter case, which generalizes over character classes and the like.

The first step is to compile this definition to a non-deterministic finite automaton (NFA). As a first cut, the state of an NFA could look like this:

When writing the compiler function, however, I realized that I would want two more features for the NFA state. First, compiling the Kleene star makes it hard to tie the knot, making one wish the language was Haskell. As a workaround, I simulate mutable union fields with a helper record. Second, it is nice to be able to compare state values to use binary search trees later in the game. To do this, I label every state with an integer and use it for comparison:

The compiler looks like this:

The key insight is that the NFA corresponds to a deterministic (DFA) machine. Whenever our machine encounters choice (Branch), it follows both options simultaneously. So then, the state of this machine (DFA state) is a set of NFA states. You can easily write a transition function that takes an input token and produces a transformation on the DFA state. Moreover, this function can be cached by token and input state. Once caching is introduced, we obtain a simple yet fascinating, lazily-constructed DFA machine.

The definition of the DFA state is not surprising:

In addition to token-based transitions, I also cache IsMatch information which can be obtained by traversing the NFA states and testing if any of them contains a Match case.

Here is the sketch of the transition function:

What remains is to write an interpreter for the DFA. I will post it in the next article when it is more tested. Perhaps I will also simplify the above definitions a bit. It is typical for me to find that the first code that I write for any problem is much more complicated than necessary.

WebSharper B5 with Extensions

We have finally released the next beta (5) of WebSharper that can run the samples I have been demonstrating on the blog. In addition, the download page now lets you play with an exciting set of extensions: Google Maps, Visualization, Info Vis Toolkit, Protovis, Raphael, jQuery Mobile and jQuery UI. Check it out: http://www.websharper.com/

WebSharper Sitelets Cont’d: Developing a Blog Service

The previous article might have left you with an erroneous impression that WebSharper sitelets only support a static set of URLs. This is not the case. In fact, the user-defined Action type can be an arbitrary data structure that maps to a URL. This comes particularly handy when designing a blogging website, since the set of blogs and their URLs is not statically bounded. Something like this would do:

Now you would need to write a router, which is roughly a bijection between Action values and URLs. A boring way to do so might look like this:

Writing routers by hand you get full control – you can inspect an Http.Request value when routing, and generate any URL when linking. However writing the above code is not much fun. If you do not particularly care for the exact URLs, there is a much shorter way to get there:

The Infer function inspects the Action type by reflection to derive a router automatically. It is smart enough to handle records, unions, most scalar types, lists, and options. In our case it derives the following mapping:

A smart thing to do would be to alter it just a little bit, for example by making ShowRecentBlogs available at the root. This can be done by combining a simple table router with the inferred router:

This is much better: 80% of the benefit with 20% of the work.

Now that URL routing is out of the way, you can finally get down to the blog service itself. I present the most interesting thing first, the controller:

The controller simply handles actions (Action values) and returns responses (Content values), no surprises here. Together with a router, the controller forms a sitelet, a self-contained website ready to go by itself or be embedded in a bigger application:

For the model in this example, you can use the simplest thing that can possibly work in a development environment, namely a static mutable variable (see the listing at the end of the article). Now, views are quite straightforward as well. The only thing of interest is the use of WebSharper Formlets (client-side form combinators) to build the UI for editing and creating the blogs. I build a simple control that renders the form and talks to the model directly over RPC, redirecting to the homepage when done:

Time to try it out:

And here is the complete code listing: