## 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

 70 71 72 73 74 75 76 77 60 61 62 63 64 65 66 67 50 51 52 53 54 55 56 57 40 41 42 43 44 45 46 47 30 31 32 33 34 35 36 37 20 21 22 23 24 25 26 27 10 11 12 13 14 15 16 17 00 01 02 03 04 05 06 07

#### Bit 3

 70 71 72 73 74 75 76 77 60 61 62 63 64 65 66 67 50 51 52 53 54 55 56 57 40 41 42 43 44 45 46 47 30 31 32 33 34 35 36 37 20 21 22 23 24 25 26 27 10 11 12 13 14 15 16 17 00 01 02 03 04 05 06 07

#### Bit 1

 70 71 72 73 74 75 76 77 60 61 62 63 64 65 66 67 50 51 52 53 54 55 56 57 40 41 42 43 44 45 46 47 30 31 32 33 34 35 36 37 20 21 22 23 24 25 26 27 10 11 12 13 14 15 16 17 00 01 02 03 04 05 06 07

#### Bit 4

 70 71 72 73 74 75 76 77 60 61 62 63 64 65 66 67 50 51 52 53 54 55 56 57 40 41 42 43 44 45 46 47 30 31 32 33 34 35 36 37 20 21 22 23 24 25 26 27 10 11 12 13 14 15 16 17 00 01 02 03 04 05 06 07

#### Bit 2

 70 71 72 73 74 75 76 77 60 61 62 63 64 65 66 67 50 51 52 53 54 55 56 57 40 41 42 43 44 45 46 47 30 31 32 33 34 35 36 37 20 21 22 23 24 25 26 27 10 11 12 13 14 15 16 17 00 01 02 03 04 05 06 07

#### Bit 5

 70 71 72 73 74 75 76 77 60 61 62 63 64 65 66 67 50 51 52 53 54 55 56 57 40 41 42 43 44 45 46 47 30 31 32 33 34 35 36 37 20 21 22 23 24 25 26 27 10 11 12 13 14 15 16 17 00 01 02 03 04 05 06 07

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

 70 71 72 73 74 75 76 77 60 61 62 63 64 65 66 67 50 51 52 53 54 55 56 57 40 41 42 43 44 45 46 47 30 31 32 33 34 35 36 37 20 21 22 23 24 25 26 27 10 11 12 13 14 15 16 17 00 01 02 03 04 05 06 07

#### High Digit

 70 71 72 73 74 75 76 77 60 61 62 63 64 65 66 67 50 51 52 53 54 55 56 57 40 41 42 43 44 45 46 47 30 31 32 33 34 35 36 37 20 21 22 23 24 25 26 27 10 11 12 13 14 15 16 17 00 01 02 03 04 05 06 07

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

 64 04 14 24 26 16 06 66 05 65 34 44 46 36 67 07 15 35 74 54 56 76 37 17 25 45 55 75 77 57 47 27 21 41 51 71 73 53 43 23 11 31 70 50 52 72 33 13 01 61 30 40 42 32 63 03 60 00 10 20 22 12 02 62

#### Bit 3

 64 04 14 24 26 16 06 66 05 65 34 44 46 36 67 07 15 35 74 54 56 76 37 17 25 45 55 75 77 57 47 27 21 41 51 71 73 53 43 23 11 31 70 50 52 72 33 13 01 61 30 40 42 32 63 03 60 00 10 20 22 12 02 62

#### Bit 1

 64 04 14 24 26 16 06 66 05 65 34 44 46 36 67 07 15 35 74 54 56 76 37 17 25 45 55 75 77 57 47 27 21 41 51 71 73 53 43 23 11 31 70 50 52 72 33 13 01 61 30 40 42 32 63 03 60 00 10 20 22 12 02 62

#### Bit 4

 64 04 14 24 26 16 06 66 05 65 34 44 46 36 67 07 15 35 74 54 56 76 37 17 25 45 55 75 77 57 47 27 21 41 51 71 73 53 43 23 11 31 70 50 52 72 33 13 01 61 30 40 42 32 63 03 60 00 10 20 22 12 02 62

#### Bit 2

 64 04 14 24 26 16 06 66 05 65 34 44 46 36 67 07 15 35 74 54 56 76 37 17 25 45 55 75 77 57 47 27 21 41 51 71 73 53 43 23 11 31 70 50 52 72 33 13 01 61 30 40 42 32 63 03 60 00 10 20 22 12 02 62

#### Bit 5

 64 04 14 24 26 16 06 66 05 65 34 44 46 36 67 07 15 35 74 54 56 76 37 17 25 45 55 75 77 57 47 27 21 41 51 71 73 53 43 23 11 31 70 50 52 72 33 13 01 61 30 40 42 32 63 03 60 00 10 20 22 12 02 62

And for the octal digits...

#### Low Digit

 64 04 14 24 26 16 06 66 05 65 34 44 46 36 67 07 15 35 74 54 56 76 37 17 25 45 55 75 77 57 47 27 21 41 51 71 73 53 43 23 11 31 70 50 52 72 33 13 01 61 30 40 42 32 63 03 60 00 10 20 22 12 02 62

#### High Digit

 64 04 14 24 26 16 06 66 05 65 34 44 46 36 67 07 15 35 74 54 56 76 37 17 25 45 55 75 77 57 47 27 21 41 51 71 73 53 43 23 11 31 70 50 52 72 33 13 01 61 30 40 42 32 63 03 60 00 10 20 22 12 02 62

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 use the tag file on disk

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.