Wednesday, April 20, 2011

Patterns in Chess Square Enumerations

In my bit manipulation post awhile back I posed a problem involving "closed form" calculation of chess endgame table indices. Back when I originally solved the problem, it was a big help to create some visualizations of some of the patterns embedded in the square numbering scheme. I had mentioned that I thought the patterns were interesting, so I thought I'd come back and elaborate on that statement.

One way of visualizing some of the patterns involved is to partition the squares according to the equivalence classes defined by the binary bits of the index. Bits 0-2 are the three low-order bits and bits 3-5 are the three high-order bits. Here are the equivalence classes defined by each of the bits of the natural square numbering.

Bit 0

7071727374757677
6061626364656667
5051525354555657
4041424344454647
3031323334353637
2021222324252627
1011121314151617
0001020304050607

Bit 3

7071727374757677
6061626364656667
5051525354555657
4041424344454647
3031323334353637
2021222324252627
1011121314151617
0001020304050607

Bit 1

7071727374757677
6061626364656667
5051525354555657
4041424344454647
3031323334353637
2021222324252627
1011121314151617
0001020304050607

Bit 4

7071727374757677
6061626364656667
5051525354555657
4041424344454647
3031323334353637
2021222324252627
1011121314151617
0001020304050607

Bit 2

7071727374757677
6061626364656667
5051525354555657
4041424344454647
3031323334353637
2021222324252627
1011121314151617
0001020304050607

Bit 5

7071727374757677
6061626364656667
5051525354555657
4041424344454647
3031323334353637
2021222324252627
1011121314151617
0001020304050607

Here we can clearly see the natural row and column oriented behavior of the index. Nothing earth shattering. If we take octal digits instead of binary digits to define our equivalence class, we get the following more colorful partition.

Low Digit

7071727374757677
6061626364656667
5051525354555657
4041424344454647
3031323334353637
2021222324252627
1011121314151617
0001020304050607

High Digit

7071727374757677
6061626364656667
5051525354555657
4041424344454647
3031323334353637
2021222324252627
1011121314151617
0001020304050607

Now on to the interesting stuff. Here are the same six equivalence classes of the less obvious square numbering for which I posed my puzzle.

Bit 0

6404142426160666
0565344446366707
1535745456763717
2545557577574727
2141517173534323
1131705052723313
0161304042326303
6000102022120262

Bit 3

6404142426160666
0565344446366707
1535745456763717
2545557577574727
2141517173534323
1131705052723313
0161304042326303
6000102022120262

Bit 1

6404142426160666
0565344446366707
1535745456763717
2545557577574727
2141517173534323
1131705052723313
0161304042326303
6000102022120262

Bit 4

6404142426160666
0565344446366707
1535745456763717
2545557577574727
2141517173534323
1131705052723313
0161304042326303
6000102022120262

Bit 2

6404142426160666
0565344446366707
1535745456763717
2545557577574727
2141517173534323
1131705052723313
0161304042326303
6000102022120262

Bit 5

6404142426160666
0565344446366707
1535745456763717
2545557577574727
2141517173534323
1131705052723313
0161304042326303
6000102022120262

And for the octal digits...

Low Digit

6404142426160666
0565344446366707
1535745456763717
2545557577574727
2141517173534323
1131705052723313
0161304042326303
6000102022120262

High Digit

6404142426160666
0565344446366707
1535745456763717
2545557577574727
2141517173534323
1131705052723313
0161304042326303
6000102022120262

Ahhhhhh....I don't know about you, but I think that's a beautiful square numbering. There's also plenty of group theory going on. What do you see here?

The Haskell code used to generate these tables is here.

Monday, April 18, 2011

Splice Subtleties

In the recent release of Heist 0.5.1, there was performance bug in my implementation of head merging. I turned off the head merging, and then fixed the bug but did not reenable head merging. If you want to turn it back on, you need to bind the html tag to the htmlImpl function from the Text.Templating.Heist.Splices.Html module. I think I'll continue to leave it off by default because it does have some potential to impact performance.

While analyzing the problem, I realized that it involves fairly obscure details of Heist internals that have not been mentioned in any of our tutorial materials. And if I, the original author of Heist fell prey to this problem, it's probably safe to assume that eventually someone else will too. So let's take a look at some details of Heist's internal behavior and the implications for splice developers.

As I alluded to in Heist in 60 Seconds, you can think of a splice as follows:

type Splice = Node -> m [Node]

The actual implementation is slightly different because we use a reader monad for the parameter node, but this is a useful mental model.

Heist is kind of like one big fmap on the whole DOM tree. If there were no splices bound, the fmapped function would be id. When you bind a splice to a tag <foo>, the splice function is applied to every occurrence of that tag. The whole tag and all its children become the splice's parameter, and they are replaced by the output of the splice in the rendered document.

Splices can be divided into two broad categorizations: substitutions and filters. Substitution splices are where the spliced tag disappears in the output. If the spliced tag is preserved in the output, then it's a filter splice.

Substitution splices probably the most common. All uses of the bind tag are substitutions. But my initial implementation of head merging in Heist 0.5.1.0 used a filter splice bound to the html tag. If you're writing a filter splice, you MUST call the stopRecursion function somewhere in the splice or you'll get either wrong or slow behavior! If you're not interested in the details behind this, you can stop reading now. Otherwise, let's look at the function Heist uses to process nodes.
runNode :: Monad m => X.Node -> Splice m
runNode (X.Element nm at ch) = do
    newAtts <- mapM attSubst at
    let n = X.Element nm newAtts ch
    s <- liftM (lookupSplice nm) getTS
    maybe (runKids newAtts) (recurseSplice n) s
  where
    runKids newAtts = do
        newKids <- runNodeList ch
        return [X.Element nm newAtts newKids]
runNode n                    = return [n]
The highlighted lines are the important ones here. First it does a lookup to see if there are any splices bound to the tag that we're currently processing. Then, if we found a splice, we call recurseSplice and pass it the current node. Here's the code for recurseSplice.
recurseSplice :: Monad m => X.Node -> Splice m -> Splice m
recurseSplice node splice = do
    result <- localParamNode (const node) splice
    ts' <- getTS
    if _recurse ts' && _recursionDepth ts' < mAX_RECURSION_DEPTH
        then do modRecursionDepth (+1)
                res <- runNodeList result
                restoreTS ts'
                return res
        else return result
  where
    modRecursionDepth :: Monad m => (Int -> Int) -> TemplateMonad m ()
    modRecursionDepth f =
        modifyTS (\st -> st { _recursionDepth = f (_recursionDepth st) })
The first highlighted line here executes the splice. The second one runs all the result nodes--which executes all the splices again. If the splice is a filter splice, then the the same splice will appear in the result list and you'll get infinite recursion.

As you can see, Heist does have checks to detect this situation and terminate if the recursion gets too deep. There is also a flag that can be set to prevent recursion altogether. You can set this flag inside your splices by calling the stopRecursion function. Recursion is turned on by default because that's what you usually want to happen for substitution splices. But remember this, and make sure you call stopRecursion if you're writing filter splices!

Friday, April 15, 2011

Heist Template Abstractions in a Nutshell

In the last post I discussed how logic and control flow can (and I argue should) be done in splices where types, higher order functions, and the full power of Haskell can be applied to the problem. In this post I want to take some time to think about the raw materials that are available in templates.

At the lowest level, we have just Text (...which is certainly /= Nothing). The templates are read in as Text and parsed into HTML DOM structures: elements, children, and attributes. Heist's abstractions for these entities are roughly analogous to the lambda calculus. The lambda calculus primitives are function definition and function application. HTML structures don't have any kind of representation for functions, so Heist uses lists of DOM tree nodes as the fundamental unit. Two different ways of representing them are splices and templates. The following table summarizes Heist's HTML abstraction tools.

Definition Application
/Evaluation
Splices <bind> use the tag
Templates file on disk <apply>

To define a splice, use the bind tag. To define a template, create a file on disk. To apply/evaluate a splice, just use the tag that you bound. To apply/evaluate a template, use the apply tag. The Heist tutorial has the details on how to use <bind> and <apply>. Splices and templates can both be thought of as functions because their methods of application allow data to be passed in to modify the output.

We've consciously avoided introducing generalized control flow that requires expressions and types--things that HTML is not suited for. But the abstractions that are available in templates work well with the primitives naturally available in the domain. This yields a powerful template system with syntax that designers already understand and can manipulate with existing tools.

Thursday, April 14, 2011

Looping and Control Flow in Heist

One of the most frequent questions I get about Heist is how to do loops or control flow in Heist templates. I usually respond that we've tried to avoid introducing these constructs into templates to encourage a better separation between view and model/controller. In this post I want to discuss the issue in more detail so that my thoughts are stored and I can refer people here in the future.

Since Haskell is pure and has a strong static type system, the first thing to think about when discussing this question is what types will be involved. Since templates are processed at runtime, they do not have access to Haskell's type system. This puts us square in the middle of byte-land. No generalized looping over things like the list of registered users or recent posts. No type-safe evaluation of arbitrary expressions. It is my contention that you're better off solving these problems with a language designed for that purpose...i.e. in Haskell splices, and not in HTML templates.

Let's continue the example of displaying blog posts used previously. We developed a function postSplice :: Splice m (don't worry about the 'm' for now) that our templates could use to render a single post using whatever markup the template designer specified. Now we want to use a looping structure to reuse that code for a list of posts. Where does this list come from? It comes from Haskell code (not templates), so it's logical to do our looping abstraction in Haskell. I would probably refactor the postSplice function as follows.

renderPost :: Monad m => Post -> Splice m
renderPost post = do
  runChildrenWithText [("postTitle", postTitle post)
                      ,("postBody", postBody post)]

Notice that this function is no longer a splice. It's a function that takes a Post as input and generates a splice as output. Now we can use the new mapSplices function introduced in Heist 0.5.1.0 to render a list of posts.

renderPosts :: Monad m => [Post] -> Splice m
renderPosts = mapSplices renderPost

That was easy. Now one more step gets us a splice that we can bind to the <recentPosts/> tag and use in our templates.

recentPostsSplice :: Splice Application
recentPostsSplice = getRecentPosts >>= renderPosts

This splice can be used in a template exactly the same way we did before. The only difference is that the view we passed into the splice is now applied to each post in the list and the results are concatenated.

I specialized this function to the Application monad which will contain functionality specific to your application that provides the necessary context for the getRecentPosts function. I left out the details of that function because those details aren't something the template author should worry about. And here we get to the main point. The core of Heist's keep-application-logic-out-of-the-view philosophy boils down to the idea that you're better off creating a domain-specific set of query functionality than exposing too much generality to the templates.

One likely avenue of domain-specific query generalization might be to look at only the posts with a certain tag. We might do something like this.

postsWithTag :: Text -> Splice Application
postsWithTag tag = getTaggedPosts tag >>= renderPosts

postsWithTagSplice :: Splice Application
postsWithTagSplice = do
    node <- getParamNode
    maybe (return []) postsWithTag $ getAttribute "tag" node
Then with the appropriate splice binding, we can do this in our templates.
<postsWithTag tag="heist"/>
Or, instead of getting the tag from an attribute of the param node, we could do this instead.
postsWithTagSplice :: Splice Application
postsWithTagSplice = do
    tag <- lift $ getParam "tag"
    maybe (return []) postsWithTag tag
In the Snap template project, Application has a MonadSnap instance, so we can lift the getParam function into the splice's monad. This gets the tag from the HTTP request parameters of whatever request is being processed when <postsWithTag> is rendered. This makes it easy to tie into values gathered from a form or even specified manually in the query string.

Hopefully this demonstrates how templates can interact with looping and control flow defined in Haskell code using the gorgeous syntax we all know and love, and how we can leverage Haskell's powerful abstraction constructs to create nice domain-specific markup languages that are easy for designers to incorporate into their web designs. In the next post I'll look more closely into the abstractions available exclusively in templates.

EDIT: To clarify, the splices in this post will be used in exactly the same way the <post> splice was used in the last post. The different splice just changes the context in which the passed-in parameters are used. For example:

<recentPosts>
<h1><postTitle/></h1>
<div><postBody/></div>
</recentPosts>

Wednesday, April 13, 2011

Views, Controllers, and Heist

A very common question when using Heist is how to specify views in a splice. There are three different approaches one can take:

1. Specify a splice's view in the Haskell code implementing the splice.
2. Get a splice's view from a template.
3. Pass the desired view to the splice as the spliced tag's child nodes.

Aproach #1 tends to be ugly and violates the principle of separating logic and view.  There are always exceptions to every rule, so we've done a little bit to ease the implementation of #1 by allowing xmlhtml DOM structures to be built with blaze-html syntax.  However, I believe that one of the other approaches will usually be preferable.

Approach #2 seems kind of awkward.  It would result in a whole bunch of small templates on disk that define little pieces of web pages.  An architecture like this might be desireable in some situations as a way to eliminate repetition (and it certainly fits into the functional programming mentality of lots of small functions), but it is quite different from the page-oriented structure most designers are used to.

Approach #3 is our recommended pattern.  It allows you to keep your view completely in the template and the logic completely in the splice.  Here's an example of how this might work.  Let's use the simple example of displaying blog posts.  We want to create a <post> splice.

data Post = Post
  { postTitle :: Text
  , postBody :: Text
  }

postSplice = do
  post <- getPostFromDatabase
  runChildrenWithText [("postTitle", postTitle post)
                      ,("postBody", postBody post)]

Then we might use it in a template like this:

<post>
  <h1><postTitle/></h1>
  <div><postBody/></div>
</post>

The template is basically saying, "Give me a post, but here's how I want it to look."  The splice is only responsible for getting the appropriate data and passing it back to the template as raw text.

The function runChildrenWithText makes this more convenient.  It binds a list of constant text splices before getting the children from the param node, "running" them to expand all referenced splices, and returning the result. After the child nodes are run, the newly bound splices are unbound. They only exist in the scope of the child nodes.

This model provides a nice division of labor between programmers and designers. The programmers build a library of splices that provide access to dynamic site data. This creates a domain-specific markup language with syntax that designers are already familiar with. It's similar to what Facebook has done with FBML. And I have found that from my perspective as a Haskell programmer, it even makes writing HTML kind of fun.

Monday, April 11, 2011

Heist in 60 Seconds

A template system is a bridge between static data (templates) and dynamic data.

Heist is a template system bridging HTML templates and Haskell code.

A splice is code that Heist binds to an HTML tag.

Every time the tag appears in a template, Heist runs the splice bound to that tag and passes the tag (including its attributes and its children) as input to the splice.

A splice's output is a list of tags that get substituted into the template in place of the original input tag.

Splices can be thought of as functions that can be called from templates to get dynamic data.

Splices can pass this dynamic data back to templates by (temporarily) binding new splices.

<bind> is a tag you can use in your templates to create new splices on the fly.

<apply> is a tag that lets you insert one template into another.


A more in-depth tutorial is here.