Rowan Bohde blog

Integrating a Broan Ventilator into Home Assistant

2023-12-07T21:21:10Z

My home has an energy recovery ventilator (ERV) as a part of its HVAC system in order to provide a source of filtered, fresh air without adding too much to heating and cooling loads. It's been beneficial and really makes the air feel less stagnant without opening a window.

The provided controls for the ventilator only let you choose between the static configs of high, low, or high for 20 minutes per hour. However, the ventilation loads in my house are dynamic and sometimes need more or less runtime depending occupancy and other conditions. On top of this, since the ventilator uses the same ductwork as the air conditioner, running it in the summer actually causes household humidity to increase when the fresh air provided by the ventilator blows over the coils, causing the stored water to evaporate.

Because of this, I wanted to better control when the ventilator ran, taking into account the state of the HVAC system and CO2 levels in the house. I have this data in my home automation platform, Home Assistant, but the manufacturer of the ventilator doesn't provide any integration with Home Assistant, or official documentation on how to integrate it into a smart home system.

My first attempt was to configure the ventilator to always run on high, and use the off-the-shelf smart plug to turn off the power to the ventilator when I didn't want it to run. However, the ventilator has an internal motorized damper that won't close when power is lost, so this method wouldn't work that well.

My second attempt was to reverse engineer how the control panel worked and replicate that. The control panel is wired through a connector on the bottom of the ventilator, through the wires labeled Y, R, G & B. Through some testing with a multimeter, the Y provides 12V DC to power the control panel, B is ground, and G is the control. I'm unsure of what R does, but I didn't need it. When the control panel is set to high, it runs 12V over the G wire. When it's set to off, 0V is run over the G wire.

I could emulate this setup with a relay that was configured to connect Y to G when the system wanted the ventilator to be on, and to disconnect them when the ventilator should be off. To do this, I used a 2 channel relay board. This device supported wifi, could integrate into HomeAssistant via ESPHome, and could be powered with 12V so that I didn't need an external power source. I needed to solder headers on the board to enable the serial programming interface. Once I did that, I was able to flash the example config using a serial adapter. Then I jumpered GPIO5 to RY1 to enable support of Relay 1 on the board. After that, I was able to power the device using my serial adapter, see it join the network, and control the relay via a switch in Home Assistant.

Once I confirmed the board was controllable, I then disconnected the wiring from the ventilator to the control panel, and connected it to the relay board like so:


Ventilator	Relay
Y	7-80V
B	GND
Y	COM1
G	NO1

Once I reconnected the plug, the relay booted and joined the network. Toggling the previously configured switch in Home Assistant would now cause the ventilator to turn on and off. From here, I was able to setup a high-level fan object using the template in Home Assistant and build scheduling and trigger automations based upon the air conditioner state and CO2 levels in my house.

Home Assistant has been controlling the ventilator using these automations for a couple of months now, and it's been very reliable, and managed to consistently keep CO2 levels in the house low while avoiding running when it doesn't need to.

Staying Fast Under Load

2019-01-13T19:19:00Z

As systems approach their capacity, they experience higher latency. This is because they have queues scattered throughout, such as network buffers, in front of thread pools, or CPU instruction pipelines. These queues fill up under load, causing more and more wait time before processing, resulting in longer delays.

Load Shedding

We can avoid issue of full queues by preemptively shedding load in response to latency getting too high. This can be a very effective technique, especially if the request is user initiated. After a certain point, the user might retry or leave, and there's no point in serving this request.

One technique I've seen used is a circuit breaker. After a percentage of requests start to timeout, the circuit breaker opens, preventing new requests from being serviced. This allows for those requests to be drained, at which point the circuit breaker can close and resume normal service. This approach is simple and reliable, but does have a few downsides:

No requests are serviced while the breaker is open.
In prolonged adverse conditions, the breaker may repeatedly open and close.

Active Queue Management

The problem of long queue delays happens in in networking, and is addressed by dropping a portion of packets before the queue is entirely full. This is called active queue management and allows successfully delivery of a large percentage of packets, while avoiding high latencies.

One techniques for active queue management is Controlled Delay or CoDel. It uses the minimum queue delay over a time window to determine if a queue is good or bad. When it's bad, it drops a single packet and shortens the time window for the next check. It's a simple control mechanism that can handle short bursts without dropping, and adapts to both increases and decreases in downstream throughput.

CoDel is referenced in Chapter 22 of the SRE book in the section on load shedding, but I couldn't find an implementation of it for Go. It's useful for a some applications, so I wrote an open source version called codel. It's designed to be easily dropped in to your existing HTTP handlers or client libaries.

import (
    "context"
    "github.com/bohde/codel"
)
 
c := codel.New(codel.Options{
    // The maximum number of pending acquires
    MaxPending: 100,
    // The maximum number of concurrent acquires
    MaxOutstanding: 10,
    // The target latency to wait for an acquire.
    // Acquires that take longer than this can fail.
    TargetLatency: 10 * time.Millisecond,
})
 

func ExampleHandler() {
    // Attempt to acquire the lock, with a 100ms deadline
    ctx, cancel := context.WithTimeout(context.Background(), 100 * time.Millisecond)
    err := c.Acquire(ctx)
    cancel()
 
    // if err is not nil, acquisition failed.
    if err != nil {
        return
    }
 
    // If acquisition succeeded, we need to release it.
    defer c.Release()
 
    // Do some process with external resources
}

Performance

I used a simulation of a single threaded server that can handle 1000 requests per second to test the above configuration. For comparison, I've also tested a bounded FIFO queue with the same 100ms deadline.

Here's the graph of 95th percentile of RTT latency compared to incoming requests per second. codel does not exhibit the sharp uptick in latency as the FIFO queue, because it starts to shed small amounts of load when the queue delay grows.

Here's the graph of throughput, demonstrating how codel throughput limits increase the closer it gets to capacity. It's also able to handle sustained overload periods by shedding load over capacity.

Try it out

This technique is a good fit to test on either high volume but low value requests, or requests where failure can be handled in graceful manner, such as showing stale results.

Before using codel in production, you'll want to determine at what percentage of capacity you want to start dropping a portion of requests. This is a function of the TargetLatency parameter, and the specific latency distributions of your application. If you already have target 95th percentile latency, that's probably a safe place to start.

Pattern Matching on Records in Haskell

2018-04-05T02:51:58Z

If you've ever written a function that pattern matches on a record, and then added a field to that record, you've seen a message like the following:

• The constructor ‘User’ should have 4 arguments, but has been given 3
• In the pattern: User name _ (Just favoriteFood)
  In an equation for ‘greet’:
      greet (User name _ (Just favoriteFood))
        = "Hey, "
          ++ show name ++ "! Have some " ++ show favoriteFood ++ "!"

Dealing with this just busy work: every function that pattern matches on our changed record, we need to add yet another '_' to. We can avoid this by just using record syntax in our pattern matching:

greet :: User -> String
greet User{name=name, favoriteFood=Just food} = "Hey, " ++ show name
                                              ++ "! Have some " ++ show food ++ "!"
greet User{name=name}                         = "Hello, " ++ show name ++ "."

Now, whenever we add or delete a field we're not using in greet, our code will still compile.

If we want to go ever further, we can use Record Puns by enabling the NamedFieldPuns extension. This lets us remove the name=name part, making our function look like this:

greet :: User -> String
greet User{name, favoriteFood=Just food} = "Hey, " ++ show name
                                         ++ "! Have some " ++ show food ++ "!"
greet User{name}                         = "Hello, " ++ show name ++ "."

By doing this by default, we can eliminate a source of boring work and focus on more interesting things.

Haskell Refactoring

2018-04-03T12:13:19Z

When we write Haskell, we love to talk about the correctness of our code. The focus on using equational reasoning let's us reason about our code. This is amazing thing to have in our toolbox when we have a piece of code we want to analyze, but what about when we want to change some piece of code?

We often use the term refactoring, to loosely mean "changing a program", but it's original definition requires that the new code is functionally equivalent to the old code. If we were model this in Haskell, we'd get the following:

data Program = Program
 
run :: Program -> Input -> Output
 
type Refactoring = (Program -> Program)
 
-- A given Refactoring r must satisfy the following property
-- run program input ≡ run (r program) input

If we require our refactorings to have this property, we know that we did not accidently introduce a bug (or accidently fix a bug!) whenever we apply it. This means it's always safe to apply a refactoring, and we don't need to think about the correctness of it, only how it impacts the design.

Refactorings also compose:

a :: Refactoring
b :: Refactoring
 
c :: Refactoring
c program = b (a program)
-- equivalent to
-- c = b . a
 
-- We still satisy the property
-- run program input ≡ run (a program) input ≡ run (b (a program)) input

Because of this, we know we can apply any number of refactorings to our program, and we'll never change the correctness of it. Feasibly, if we could make huge changes to our program safely by defining a set of refactorings to get us what we wanted.

Types of Refactorings

Much of the refactorings defined has been done in languages like Java or Ruby, but they really aren't language specific. Almost all of the refactoring catalog apply to Haskell with some slight modifications (e.g. use function instead of methods and typeclasses instead of interfaces).

What makes Haskell really interesting from a refactoring standpoint, is that every equivalence we have is also a valid refactoring. For instance, in the documentation for id, there's the following line:

id x = x

This is the definition for id, but also an equivalence. I know that whenever I see id x I can replace it with x . I also know that for any arbitrary expression x, I can replace it with id x and it will work.

Various libraries will define these, and they are useful to have when refactoring.

An Example

Let's consider a small module that we want to refactor to use lens.

module User (
  User(..), hasValidEmail
) where
 
import qualified Email
 
data User { email :: Email.Email }
 
hasValidEmail :: User -> Bool
hasValidEmail = Email.isValid . email

lens is documents a lot of the properties in the comments of the function. For example, view defines the equivalence view . to = id

Let's use this to refactor hasValidEmail to use lens:

-- id x = x
 
hasValidEmail :: User -> Bool
hasValidEmail = Email.isValid . (id email)
 
-- view . to = id
 
hasValidEmail :: User -> Bool
hasValidEmail = Email.isValid . ((view . to) email)
 
-- (f (g a)) = (f . g) a
 
hasValidEmail :: User -> Bool
hasValidEmail = Email.isValid . (view (to email))
 
-- Extract Function
 
hasValidEmail :: User -> Bool
hasValidEmail = Email.isValid . (view emailGetter)
  where
    emailGetter = to email
 
-- `view` only requires a `Getting`, so we can
-- use a `Lens` instead of a `Getter`
-- https://hackage.haskell.org/package/lens-4.16.1/docs/Control-Lens-Getter.html#t:Getting
 
hasValidEmail :: User -> Bool
hasValidEmail = Email.isValid . (view emailGetter)
  where
    emailGetter = lens email (\u e -> u{email=e})
 
-- since `emailGetter` is no longer a `Getter`, rename it
-- Rename Function
 
hasValidEmail :: User -> Bool
hasValidEmail = Email.isValid . (view emailLens)
  where
    emailLens = lens email (\u e -> u{email=e})

That was a lot of work for a relatively small change! But, since each change was just applying a refactoring, we know that we never broke the code.

Combining Refactorings

Doing that every time is really tedious, but we don't need to work at the level every time. Once we have a higher level refactoring combining multiple steps, we can use that as a refactoring itself.

If we wanted to make our entire program use lens, here are the 5 steps we'd need to do:

1. Add lens for a record field email

emailLens = lens email (\r a -> r{email=a})

2. Change every use of the email field as a function to use the lens

email = view emailLens

3. Change every use of the email field to assign to use the lens

r { email = v } = set emailLens v r

4. At this point, there should be a single consumer of the record field: the lens. We can rename it to _email

emailLens = lens _email (\r a -> r{_email=a})

5. With the email identifier no longer in use, we can rename our lens.

email = lens _email (\r a -> r{_email=a})

With that, our code is as if we designed it as a lens from the beginning, and we have a high level process to do this in other places.

Cool Things About Go From A Haskell Perspective

2018-03-08T11:29:35Z

Go gets a pretty bad reputation among Haskell programmers, and it's really not fair. I've been using both of them for several years now, and am in the pretty unique position of working on a Go compiler in Haskell.

Go has a lot of really nice features and tooling that make my day to day life developing it really great. Here are a some of them:

Compile times

They are pretty fast, so much so that I'm more likely to recompile in Go than in Haskell when developing.

Static linking

I (almost) never need to worry about LD_LIBRARY_PATH (which is not a huge problem in Haskell), or operating system dependencies.

Cross compilation

I use Linux. If I need a coworker to test on their Mac, it's trivial to build and send a binary. This is made way easier by static linking, since I don't need to worry about their library setup.

`gofmt`

Use gofmt and your team will never have a review comment asking for formatting changes. It's fast enough to be run on save without any noticeable latency, which I cannot say for any Haskell formatters.

`goimports`

Go's imports are qualified by default. Because of this, you can setup goimports, and never think about your import lines again.

`go test`

Having a default test runner inside the compiler means adding tests is way easier in Go. Combined with the test file convention (files ending in _test.go will only be built during test), makes adding tests to a package way less friction.

As a bonus, the test framework includes a benchmark runner.

`quick`

The standard library comes with a small property testing framework, quick. It's not as fancy as quickcheck, but it can still catch bugs. If you want a proper property testing framework, use gopter.

Build tags

Build tags let files be conditionally compiled. This lets us avoid C preprocessor hacks.

This is how the test runner knows what files are considered to be parts of tests: the _test.go suffix signals the file should be built during test.

Package structure

All the Go files in a given directory are considered part of a package. There also is not a distinction between modules and packages, like in Haskell. Combined with build tags, this lets us avoid a lot of extra modules for test or certain build conditions. It also cleanly decouples the file size from the module size, as there's no need to make a new module if the file is getting too large.

As a result, managing namespaces is a whole lot less fussy in Go than other languages. If I want to test a single module, the test runner can do that, while only compiling the files I need.

tools

A whole lot of compiler internals are just exposed as libraries and binaries. This makes tooling like gofmt and goimports easier to write.

Optimizing Queries with Applicatives

2014-05-27T12:43:35Z

I was learning about free monads recently, and how they allow separation of the generation of a program from the interpretation. A neat example of this is Cool Idea: Free Monads for Testing Redis Calls, where Michael Xavier shows how to model calls to Redis, and interpret them different ways, allowing for better testing of code.

Another benefit of modeling calls this way is that we have full access to data structures before execution, allowing us to optimize the model, eliminating redundant calls, or batching calls that allow it.

A Key Value Store

In case you'd like to run these examples yourself, this post is Literate Haskell. Copy and paste the body into a file with a .lhs extension, and you can run it in ghci, assuming you have free installed.

> {-# LANGUAGE DeriveFunctor, FlexibleInstances, OverlappingInstances  #-}
> module Main where
> import Control.Monad (liftM2)
> import Control.Applicative (Applicative, (<$>), (<*>), pure, liftA2)
> import Control.Monad.Free (Free(..), iterM, liftF)
> import Control.Monad.IO.Class (liftIO)
> import Control.Monad.State (gets, modify)
> import qualified Control.Monad.State as ST
> import Data.Map (Map, intersection, union)
> import qualified Data.Map as M
> import Data.Maybe (isJust)
> import Data.Monoid ((<>))
> import Data.Set (Set)
> import qualified Data.Set as S
> import Data.Traversable (traverse)

We start with a small key value store functor, similar to the Redis one, but with the inclusion of a bulk get command through GetMulti.

> data StoreF next = Get String (Maybe String -> next)
>                  | GetMulti (Set String) (Map String String -> next)
>                  | Put String String next
>                  deriving (Functor)
> type Store = Free StoreF

Then we'll need functions corresponding to our commands. We could use TemplateHaskell for this, but I've included them for clarity.

> get :: String -> Store (Maybe String)
> get s = liftF $ Get s id
 
> getMulti :: Set String -> Store (Map String String)
> getMulti s = liftF $ GetMulti s id
 
> put :: String -> String -> Store ()
> put k v = liftF $ Put k v ()

We can write a simple interpreter to run against a Map, and print out the operations as they occur

> type MapDB = Map String String
 
> interpret :: Store a -> MapDB -> IO a
> interpret = ST.evalStateT . (iterM run)
>   where
>     run (GetMulti ids next) = do
>       liftIO $ putStrLn $ "looking up " ++ show ids
>       next =<< filterKeys ids <$> ST.get
>     run (Get i next) = do
>       liftIO $ putStrLn $ "looking up " ++ show i
>       next =<< gets (M.lookup i)
>     run (Put k v next) = do
>       liftIO $ putStrLn $ "putting " ++ k ++ " " ++ v
>       modify (M.insert k v) >> next

We can test the interpreter in ghci:

λ: interpret (get "1") (M.singleton "1" "Hello World")
looking up "1"
Just "Hello World"
 
λ: interpret (getMulti $ S.fromList ["1", "2"]) (M.singleton "1" "Hello World")
looking up fromList ["1","2"]
fromList [("1","Hello World")]
 
λ: interpret (put "1" "Hello") M.empty
putting 1 Hello

Now we can write a simple program to get two keys and store their concatenation into a third key.

> program :: Store ()
> program = do
>   first <- get "1"
>   second <- get "2"
>   let val = liftM2 (++) first second
>   case val of
>     Just v -> put "3" v
>     _ -> return ()

λ: interpret program $ M.fromList [("1", "hello "), ("2", "world!")]
looking up "1"
looking up "2"
putting 3 hello world!

Assuming that a Get request has no side effects, there's no reason why we had to make two separate requests. The bulk api should let us do this more efficiently. We can rewrite the above to use it:

> program' :: Store ()
> program' = do
>   m <- getMulti $ S.fromList ["1", "2"]
>   let val = liftM2 (++) (M.lookup "1" m) (M.lookup "2" m)
>   case val of
>     Just v -> put "3" v
>     _ -> return ()

λ: interpret program' $ M.fromList [("1", "hello "), ("2", "world!")]
looking up fromList ["1","2"]
putting 3 hello world!

That's nicer from a request count perspective, but we had to rewrite it to something that is less clear. If you look at the original implemenation of program, second doesn't depend on the value of second, so we can rewrite using <*> from Applicative, which is less powerful than >>= but allows analyzing the computation before it happens.

> program'' :: Store ()
> program'' = do
>   val <- liftM2 (++) <$> get "1" <*> get "2"
>   case val of
>     Just v -> put "3" v
>     _ -> return ()

λ: interpret program'' $ M.fromList [("1", "hello "), ("2", "world!")]
looking up "1"
looking up "2"
putting 3 hello world!

The implementation of Applicative that Free provides us doesn't know about our domain, so it can't optimize it, but we can provide this. We'll write a <*> that collapses mutliple Get and GetMultis into one single GetMulti request.

I'm going to use OverlappingInstances to demonstrate, but a production implementation should probably write different types.

First a few functions to convert receiving functions:

> -- filter the map to just a set of keys
> filterKeys :: (Ord k) => Set k -> Map k v -> Map k v
> filterKeys is m = M.filterWithKey (\k _ -> S.member k is) m
 
> -- filter the keys to a merged GetMulti
> justKeys :: Set String -> (Map String String -> t) -> Map String String -> t
> justKeys is n m = n $ filterKeys is m
 
> -- Adapt the next from a Get to accept a Map
> toMap :: String -> (Maybe String -> a) -> Map String String -> a
> toMap i n m = n $ M.lookup i m

And some boilerplate for combining two MultiGets:

> combineGet
>  :: Set String
>     -> (Map String String -> Store (a1 -> a))
>     -> (Map String String -> Store a1)
>     -> Store a
> combineGet is f g = Free $ GetMulti is $ \m -> f m <*> g m

Using the definition of Applicative for Free, we can add in specific instances for that we want to collapes:

> instance Applicative (Free StoreF) where
>   pure = Pure
>   Pure a <*> Pure b = Pure $ a b
>   Pure f <*> Free mb = Free $ fmap f <$> mb
>   Free (Get i n) <*> Free (Get i' n') = combineGet s m m'
>     where s = (S.fromList [i, i'])
>           m = (toMap i n)
>           m' = (toMap i' n')
>   Free (Get i n) <*> Free (GetMulti is' n') = combineGet s m m'
>     where s = (S.insert i is')
>           m = (toMap i n)
>           m' = (justKeys is' n')
>   Free (GetMulti is n) <*> Free (Get i' n') = combineGet s m m'
>     where s = (S.insert i' is)
>           m = (justKeys is n)
>           m' = (toMap i' n')
>   Free (GetMulti is n) <*> Free (GetMulti is' n') = combineGet s m m'
>     where s = (is' <>  is)
>           m = (justKeys is n)
>           m' = (justKeys is' n')
>   Free ma <*> b = Free $ (<*> b) <$> ma

With this definition our program'' now makes just one GetMulti request:

λ: interpret program'' $ M.fromList [("1", "hello "), ("2", "world!")]
looking up fromList ["1","2"]
putting 3 hello world!

Examples

We can also test to makes sure that the results of GetMulti return an appropriate Map:

> program2 :: Store (Map String String)
> program2 = intersection
>            <$> getMulti (S.fromList ["a", "b", "c"])
>            <*> getMulti (S.fromList ["c", "d"])

λ: interpret program2 $ M.fromList $ map (\k -> (k,k)) ["a", "b", "c", "d"]
looking up fromList ["a ","b ","c","d"]
fromList [("c","c")]

> program3 :: Store (Map String String)
> program3 = union
>            <$> getMulti (S.fromList ["a", "b", "c"])
>            <*> getMulti (S.fromList ["c", "d"])

λ: interpret program3 $ M.fromList $ map (\k -> (k,k)) ["a", "b", "c", "d"]
looking up fromList ["a","b","c","d"]
fromList [("a","a"),("b","b"),("c","c"),("d","d")]

We can still express dependence upon previous values using (>>=), and prevent batching:

> program4 :: Store (Maybe String)
> program4 = get "key" >>= (maybe (return Nothing) get)

λ: interpret program4 $ M.fromList [("key", "second-key"), ("second-key", "hello!")]
looking up "key"
looking up "second-key"
Just "hello!"

A final example of code that I often see in real world applications, for an example User model

> data User = User {
>   _id :: Int,
>   username :: String,
>   email :: String
>   } deriving (Show)

Let's say we store all of this in our store, with a scheme of <id>:name and <id>:email for the user data.

To lookup a single record we would could use <*> and batching of Gets would occur:

> lookupUser :: Int -> Store (Maybe User)
> lookupUser i = liftA2 (User i) <$> get (pre ++ ":name") <*> get (pre ++ ":email")
>   where pre = show i

λ: interpret (lookupUser 0) $ M.fromList $ [("0:email", "test@example.com"), ("0:name", "testuser")]
looking up fromList ["0:email","0:name"]
Just (User {_id = 0, username = "testuser", email = "test@example.com"})

We can expand this to looking up multiple users with traverse, and all of the Gets will be collapsed:

> lookupUsers :: [Int] -> Store [Maybe User]
> lookupUsers ids = traverse lookupUser ids

λ: let sampleUser k = [(k ++ ":email", "test" ++ k ++ "@example.com"), (k ++ ":name", "testuser" ++ k)]
λ: let db = M.fromList $ [0..4] >>= sampleUser . show
λ: interpret (lookupUsers [1..4]) db
looking up fromList ["1:email","1:name","2:email","2:name","3:email","3:name","4:email","4:name"]
[Just (User {_id = 1, username = "testuser1", email = "test1@example.com"}),Just (User {_id = 2, username = "testuser2", email = "test2@example.com"}),Just (User {_id = 3, username = "testuser3", email = "test3@example.com"}),Just (User {_id = 4, username = "testuser4", email = "test4@example.com"})]

This collapsing works very naturally with (>>=). Let's say we verify emails, and for some reason, store this some result under a key like <email>:verified. If we have a user, we can look this up like so:

> verified :: User -> Store Bool
> verified (User _ _ e) = (get $ e ++ ":verified") >>= return . isJust

If we just have an id, we'll need to look up the user first:

> idVerified :: Int -> Store Bool
> idVerified i = lookupUser i >>= (maybe (return False) verified)

With valid user, we have two Gets.

λ: interpret (idVerified 1) (M.insert "test1@example.com:verified" "verified" db)
looking up fromList ["1:email","1:name"]
looking up "test1@example.com:verified"
True

With an invalid user, we do just one:

λ: interpret (idVerified 5) (M.insert "test1@example.com:verified" "verified" db)
looking up fromList ["5:email","5:name"]
False

Once again, we can handle lists via traverse:

> idsVerified :: [Int] -> Store [Bool]
> idsVerified ids = traverse idVerified ids

Running this we see that Get requests are batched whenever they can, and that we don't need to write specific logic for batching multiple requests versus a single request.

λ: interpret (idsVerified [1..5]) (M.insert "test1@example.com:verified" "verified" db)
looking up fromList ["1:email","1:name","2:email","2:name","3:email","3:name","4:email","4:name","5:email","5:name"]
looking up fromList ["test1@example.com:verified","test2@example.com:verified","test3@example.com:verified","test4@example.com:verified"]
[True,False,False,False,False]

Thoughts

I think this technique is pretty awesome, because it solves common issues like the "n+1 problem", without changing the original code, assuming it used <*> in the first place.

There's a lot of related work around this:

Kvle pointed out that this may break some existing code that relied on sequencing of effects, for example:

λ: interpret (get "a" *> put "b" "goodbye" *> get "b") (M.singleton "b" "hello")
looking up fromList ["a","b"]
putting b goodbye
Just "hello"

I'm not really sure how these changes to the definition of Applicative affects whether the laws still hold. Related to this, embedding logic into the Applicative definition isn't the best. I'm looking into using free applicative instead, and moving the optimizations to another function, but I haven't figured out how to combine this with the nice do syntax.

Self Hosting Git

2014-03-22T11:59:35Z

For awhile I've been pretty unhappy with hosting my code at Github. They have enourmous cultural capital, but use it irresponsibly, as evidenced by "harcore forking action", the meritocracy rug, and drinkups. The recent news about their sexist culture and treatement of Julie Ann Horvath made me look into alternative hosting options.

I looked into a few prepackaged options, such as GitLab or Gitorious, but settled on a combination of gitolite, gitweb, and git-daemon.

Throughout all the following examples, I'll be using git.rowan.computer as my server, but you should change that to your own server.

Gitolite

Install gitolite was straight forward, I just followed the instructions from their docs.

Configuring gitolite took awhile, I ended up setting up wild repos. This let me create new repos by just setting the origin, and pushing.

After this is setup, you can run commands to interact with your repositories through ssh, e.g. ssh git@git.rowan.computer help will show all the commands.

One thing that I spent a bit of time on was figuring out how to delete a repo. For this I had to uncomment the "D" command in gitolite.rc in the git users home directory. From there ssh <your_git_host> D -h will show how to delete a repo.

Gitweb

I installed gitweb directly from apt. From there I added the following config options:

$projectroot = "/home/git/repositories";
$projects_list = "/home/git/projects.list";
$strict_export = "true";
$export_ok = "git-daemon-export-ok";
@git_base_url_list = ('git://git.rowan.computer');
$feature{'highlight'}{'default'} = [1];

This will display any repo in gitweb that the gilolite user gitweb can read. You can add these permissions via ssh <your_git_host> perms <repo_name> + READERS gitweb

There is a more advanced config for authorizing users, but I only care about public repos being shown.

Gitweb uses cgi, so you'll need a web server to actually serve it. I use nginx, with this config.

For the theme, I accidently stumbled upon gitweb-theme, and ran the install process

Git-Daemon

Installing from apt didn't work, so I wrote an upstart script based upon the docs.

Like gitweb, you can make a repo publicly cloneable by allowing the daemon user to read, e.g: ssh <your_git_host> perms <repo_name> + READERS daemon

Migrating

I manually migrated a handful of private repos, and used a script for all my public stuff.

I wrote a quick python script to parse Github's API output

import json
import sys
import pipes
 
for repo in json.loads(''.join(sys.stdin)):
    print pipes.quote(repo['name']),
    print pipes.quote(repo['git_url']),
    print pipes.quote(repo['description'] or '')

And used it to generate a list of all my repos.

curl "https://api.github.com/users/bohde/repos?type=owner" | python convert.py >> repos

I had two pages of repos, so I had to do it again with the url "https://api.github.com/users/bohde/repos?type=owner&page=2".

I used the following script to clone a repo:

set -e
git clone --bare https://github.com/bohde/$1.git
cd $1.git
git push --mirror ssh://git@git.rowan.computer/rowan/$1.git
cd ..

To clone them all, I ran cd /tmp; cat repos | xargs -L 1 bash clone.sh

To setup descriptions, and public access, I wrote the following script:

ssh <your_git_host> desc rowan/$1 "$3"
ssh <your_git_host> perms rowan/$1 + READERS daemon
ssh <your_git_host> perms rowan/$1 + READERS gitweb

To run this over them all, I ran cat repos | xargs -L 1 bash access.sh

Thoughts

I'm still looking for a good way to setup issues and pull requests, but I get so few of those that it isn't a high priority.

For backups, Pete Keen has written how to mirror to s3.

An immediate benefit I've noticed is that I'm no longer constrained by the low number of private repos, so I'm more likely to put something I don't want to be public in git now. I also was less affected by the recent Github outage.

The total size of my repos was around 60 MB. This would be an awesome use for a spare Raspberry Pi.

Don't Design the API to the Client

2012-09-17T09:17:35Z

A problem I often see with first production versions of HTTP APIs is they are tightly coupled to the client code. This is especially easy to do in web applications where both the client and server source are contained in the same repository.

A few signs in development you should watch out for:

Display changes on the client cause a change in the API
API resources that are only a combination of other resources
Client views and API resources have a one-to-one relationship

These hint that the API may be too specialized to the client. This make other clients harder to develop, and makes changing the current client difficult. Instead, let client development push the API to develop flexibility, instead of assumptions on how it will be used.

Document Summarization using TextRank

2012-09-02T00:55:35Z

For a gift recommendation side-project of mine, I wanted to do some automatic summarization for products. A fairly easy way to do this is TextRank, based upon PageRank. In this example, the vertices of the graph are sentences, and the edge weights between sentences are how similar the sentences are.

To go from an string of text to a list of scored sentences based upon how much they represent the overall text, we need to go through several steps:

Tokenize the text into sentences
Tokenize each sentence into a collection of words
Convert the sentences into graphs
Score the sentences via pagerank

Sentence Splitting

To get started, we'll need to split the document into sentences. For this, we'll use nltk's included Punkt module, and the opening paragraph of Sir Authur Conan Doyle's A Scandal In Bohemia.

>>> from nltk.tokenize.punkt import PunktSentenceTokenizer
 
>>> document = """To Sherlock Holmes she is always the woman. I have
seldom heard him mention her under any other name. In his eyes she
eclipses and predominates the whole of her sex. It was not that he
felt any emotion akin to love for Irene Adler. All emotions, and that
one particularly, were abhorrent to his cold, precise but admirably
balanced mind. He was, I take it, the most perfect reasoning and
observing machine that the world has seen, but as a lover he would
have placed himself in a false position. He never spoke of the softer
passions, save with a gibe and a sneer. They were admirable things for
the observer-excellent for drawing the veil from men’s motives and
actions. But for the trained reasoner to admit such intrusions into
his own delicate and finely adjusted temperament was to introduce a
distracting factor which might throw a doubt upon all his mental
results. Grit in a sensitive instrument, or a crack in one of his own
high-power lenses, would not be more disturbing than a strong emotion
in a nature such as his. And yet there was but one woman to him, and
that woman was the late Irene Adler, of dubious and questionable
memory.
"""
>>> document = ' '.join(document.strip().split('\n'))
 
>>> sentence_tokenizer = PunktSentenceTokenizer()
>>> sentences = sentence_tokenizer.tokenize(document)

Bag of Words

Before we can do any analysis, we need to convert the document into a bag-of-words, which is an unordered collection of word counts.

For the first sentence, we should have something like the following:

{'always': 1,
 'holmes': 1,
 'is': 1,
 'she': 1,
 'sherlock': 1,
 'the': 1,
 'to': 1,
 'woman': 1}

A simple implementation for converting a sentence to a bag-of-words can be done via the base Python datastructures:

from collections import Counter
 
def bag_of_words(sentence):
    return Counter(word.lower().strip('.,') for word in sentence.split(' '))

An alternative way to a bag-of-words is in a vector, where each column corresponds to a word. Instead of the previous dictionary, we'd have something like the following:

[1, 1, 1, 1, 1, 1, 1, 1]

The package scikit-learn provides text feature extraction, allowing us to build SciPy matrices out of a collections of texts.

>>> from sklearn.feature_extraction.text import CountVectorizer
 
>>> c = CountVectorizer()
>>> bow_array = c.fit_transform([sentences[0]])
>>> bow_array.toarray()
[[1 1 1 1 1 1 1 1]]

The resulting array is a bit different, since hyphens are not included in words, and the stopword "a" is excluded.

We can apply this to the entire collection, and get back a matrix.

>>> from sklearn.feature_extraction.text import CountVectorizer
 
>>> c = CountVectorizer()
>>> bow_matrix = c.fit_transform(sentences)
>>> bow_matrix
<11x127 sparse matrix of type '<type 'numpy.float64'>'
   with 183 stored elements in COOrdinate format>

Converting to a Graph

Now we have a matrix where the rows are sentences and the columns are words. We need to transform this into a graph relating the sentences to each other. To do this, we'll first normalize our matrix using Scikit-learn's TfidfTransformer.

>>> from sklearn.feature_extraction.text import TfidfTransformer
>>> normalized_matrix = TfidfTransformer().fit_transform(bow_matrix)

This will re-weight each word is based upon its tf-idf, which will dimish the effect of words common to each sentence.

>>> similarity_graph = normalized_matrix * normalize_matrix.T
>>> similarity_graph.toarray()
array([[ 1.        ,  0.        ,  0.13737879,  0.04767903,  0.04305016,
         0.04345599,  0.03330044,  0.05261648,  0.07798958,  0.        ,
         0.20047419],
       [ 0.        ,  1.        ,  0.0842143 ,  0.07819597,  0.        ,
         0.05171612,  0.        ,  0.        ,  0.        ,  0.        ,
         0.05807146],
       [ 0.13737879,  0.0842143 ,  1.        ,  0.        ,  0.07004069,
         0.09648614,  0.1069042 ,  0.06701793,  0.09437203,  0.20474295,
         0.1197599 ],
       [ 0.04767903,  0.07819597,  0.        ,  1.        ,  0.07558987,
         0.18678911,  0.05853972,  0.09249592,  0.10892262,  0.09110741,
         0.24159019],
       [ 0.04305016,  0.        ,  0.07004069,  0.07558987,  1.        ,
         0.07055583,  0.02370685,  0.07272032,  0.17253418,  0.08262451,
         0.17789849],
       [ 0.04345599,  0.05171612,  0.09648614,  0.18678911,  0.07055583,
         1.        ,  0.12952649,  0.06859301,  0.06837492,  0.13015945,
         0.15423071],
       [ 0.03330044,  0.        ,  0.1069042 ,  0.05853972,  0.02370685,
         0.12952649,  1.        ,  0.06307559,  0.03194234,  0.02852116,
         0.11271501],
       [ 0.05261648,  0.        ,  0.06701793,  0.09249592,  0.07272032,
         0.06859301,  0.06307559,  1.        ,  0.09411725,  0.        ,
         0.07702234],
       [ 0.07798958,  0.        ,  0.09437203,  0.10892262,  0.17253418,
         0.06837492,  0.03194234,  0.09411725,  1.        ,  0.12388421,
         0.14327969],
       [ 0.        ,  0.        ,  0.20474295,  0.09110741,  0.08262451,
         0.13015945,  0.02852116,  0.        ,  0.12388421,  1.        ,
         0.04706138],
       [ 0.20047419,  0.05807146,  0.1197599 ,  0.24159019,  0.17789849,
         0.15423071,  0.11271501,  0.07702234,  0.14327969,  0.04706138,
         1.        ]])

This is a mirrored matrix, where both the rows and columns correspond to sentences, and the elements describe how similar the two sentences are. Scores of 1 mean that the sentences are exactly the same, while scores of 0 mean the sentences have no overlap.

Pagerank

With a graph of sentences, we can use pagerank to score them. To do this, we'll use the pagerank function from NetworkX.

>>> import networkx as nx
>>> nx_graph = nx.from_scipy_sparse_matrix(similarity_graph)
>>> scores = nx.pagerank(nx_graph)
>>> scores
{0: 0.08671319149370108,
 1: 0.08316523582097997,
 2: 0.09513943890606882,
 3: 0.09440660636561657,
 4: 0.08968582008434481,
 5: 0.0949290548524502,
 6: 0.08616430411108938,
 7: 0.086273427821944,
 8: 0.09263320827229513,
 9: 0.08808392628885832,
 10: 0.10280578598265173}

This gives us a mapping of sentence indices to scores. We can use associate these back to our original sentences and sort them.

>>> ranked = sorted(((scores[i],s) for i,s in enumerate(sentences)),
                reverse=True)
>>> ranked[0][1]
'And yet there was but one woman to him, and that woman was the late '
'Irene Adler, of dubious and questionable memory.'

We can combine all of this into one function as follows:

import networkx as nx
import numpy as np
 
from nltk.tokenize.punkt import PunktSentenceTokenizer
from sklearn.feature_extraction.text import TfidfTransformer, CountVectorizer
 
def textrank(document):
    sentence_tokenizer = PunktSentenceTokenizer()
    sentences = sentence_tokenizer.tokenize(document)
 
    bow_matrix = CountVectorizer().fit_transform(sentences)
    normalized = TfidfTransformer().fit_transform(bow_matrix)
 
    similarity_graph = normalized * normalized.T
 
    nx_graph = nx.from_scipy_sparse_matrix(similarity_graph)
    scores = nx.pagerank(nx_graph)
    return sorted(((scores[i],s) for i,s in enumerate(sentences)),
                  reverse=True)

Using this technique, we have a simple way of choosing relevant sentences from a text. This model can also be adapted to find keywords that are important in a text, or used as part of more sophisticated scoring methods.

Programming With Only Functions

2012-02-23T21:55:41Z

Python's lambda keyword does not get the love it deserves. It can only execute expressions, instead of statements. With this restriction, we can still make something interesting.

A Tiny Computation System

The lambda calculus is a system of computation based on mathematical functions. It is the foundation for functional languages. This contrasts to the Turing machine, which is the foundation for imperative languages. It turns out that, in Python, all we need to implement the lambda calculus is the lambda keyword.

The identity functions would be:

identity = lambda x: x

Encoding

identity isn't very interesting, so let's do some calculations. Since we have only functions, we need some way to encode numbers as functions. Let's start with zero.

zero = lambda f: identity

zero takes a function f, and returns the identity function. For clarity, this expands to:

zero = lambda f: lambda x: x

After zero, we have one:

one = lambda f: lambda x: f(x)

And then, two, three, and four:

two = lambda f: lambda x: f(f(x))
three = lambda f: lambda x: f(f(f(x)))
four = lambda f: lambda x: f(f(f(f(x))))

Do you see the pattern yet? For a given number n, we can encode it as

n = lambda f: lambda x: f(f(f(....f(x)...)))

Such that there are n fs. This is method of encoding numbers is known as Church encoding.

Decoding

In order to turn an encoded number into a Python number, we need to decode it using a function of the form:

decode = lambda num: num(f)(x)

We know that decode(zero) should be 0 and that zero ignores f. Therefore x should be 0. We also know that f(0) should be 1 and f(f(0)) should be 2, and so on. Therefore f should be lambda x: x + 1. Substituting this, we get our definition of decode:

decode = lambda n: n(lambda x: x + 1)(0)

We can check this real quick:

assert decode(zero) == 0
assert decode(one) == 1

Successors

It would be rather tedious if we had to type out every definition of every number we needed. Is there a way we can get the successor of a number from just the definition of the number? Something like the following:

one = succ(zero)

We know a number definition requires two lambdas, so we'll need three in order to accept the original number. Therefore our definition will look like this:

succ = lambda n: lambda f: lambda x: ????

We know from the definition of decode that we can get the value of a number n by calling it it like n(f)(x). In order to get the successor of n, we'll need one more f. Therefore we have:

succ = lambda n: lambda f: lambda x: f(n(f)(x))

For easy testing, let's declare the following helper function:

equals = lambda x, y: decode(x) == decode(y)
assert equals(succ(zero), one)

Now we can easily define more numbers:

two = succ(one)
three = succ(two)
four = succ(three)
five = succ(four)
six = succ(five)

Addition

Now let us define a function plus that implements addition. An example usage:

assert equals(plus(two)(three), five)

If we think about it, succ could have been defined as plus(one). Is there a way we can include a one in the definition fo succ?

succ = lambda n: lambda f: lambda x: one(f)(n(f)(x))

For plus, we'd like to be able to specify numbers besides one, so we'll add another lambda:

plus = lambda m: lambda n: lambda f: lambda x: m(f)(n(f)(x))

Multiplication

When defining plus, we saw that if we have a a number m, m(f)(x) will add the decoded m to x. We also know that one(f)(x) adds 1 to x. Therefore, m(one(f))(x) should be equivalent to m(f)(x). We can use this to define multiplication:

mult = lambda m: lambda n: lambda f: lambda x: m(n(f))(x)
assert equals(mult(two)(three), six)

Exponents

We've started to combine these base functions we have in interesting ways. Since we know that m(n(f)) in the defintion of mult repeats the addition of n a total of m times, and that plus(n) is the addition of n, we can rewrite mult to use fewer lambdas:

mult = lambda m: lambda n: m(plus(n))(zero)

Since using multiplication to define exponents is a similar to using addition to define multiplication, we should be able to adapt this definition of mult for exp:

exp = lambda m: lambda n: n(mult(m))(one)
equals(exp(two)(two), four)

More Encodings

We aren't limited to just natural numbers when using the lambda calculus. We can encode boolean logic and lists, allowing us to write programs with control flow and data structures.

Combinators in Python

2012-02-20T18:19:35Z

Inspired by the Coffeescript library Katy, I've been exploring using combinators with Python. The result can be found in my Functional Python repository.

In my previous post on Function Python, I was attempting to translate the following imperative code into different styles.

def imperative_style(xs):
    results = []
    for x in xs:
        if x >= 7: 
            break
        if x < 2:
            result = 4 * x
            results.append(result)
    return results
 
assert imperative_style(range(10)) == [0, 4]

By using the linked Combinators class, we can translate that to the following:

from itertools import takewhile
 
def fluent_combinator_style(xs):
    return bw(xs).chain()\
                 .R(takewhile, lambda x: x < 7)\
                 .R(filter, lambda x: x < 2)\
                 .R(map, lambda x: 4 * x)\
                 .value()
    
assert fluent_combinator_style(range(10)) == [0, 4]

The combinator methods work by altering the form of function calls. The R method transforms bw(wrapped_value).R(takewhile, lambda x: x < 7) into the call takewhile(lambda x: x < 7, wrapped_value).

What I find interesting about this style is that it allows the end user of a class to add something that looks like a method to an object.

As I experimented using this class wrapping iterables, it began to remind me of Underscore.js. This resulted in a tiny (69 line) iterable wrapper It. Using It, we can redefine the above like so:

from itertools import takewhile
 
def it_style(xs):
    return It(xs).chain()\
                 .R(takewhile, lambda x: x < 7)\
                 .filter(lambda x: x < 2)\
                 .map(lambda x: 4 * x)\
                 .value()
 
assert it_style(range(10)) == [0, 4]

Notice how It doesn't support takewhile out of the box, but the user can easily add it to the method chain. It provides flexibility on the level of the object instance, allowing the user to add functionality in a lightweight manner.

Simple REST URIs

2012-02-11T00:55:35Z

When talking about REST APIs, one of the frequent questions pertains to the benefits of using an Accept header, rather than file extensions, to do content negotiation. Often, the benefits of the Accept header don’t seem to outweigh the familiarity of file extensions.

An Example Application

Let's say I have a small command line application that prints out issue information from an issue tracker corresponding to a local feature branch in Git. Usage may look like so:

$ git-issue-branch some-issue
Found a bug

I'm having a problem with this.

I could store the information in SQLite with a schema like this:

CREATE_TABLE issue_branches (
   id integer primary key,
   branch text,
   issue_uri text       
);

The script to do this would have very simple logic: lookup the issue_uri from the db, do an HTTP GET, parse the response, and print the title and body of the issue.

Transitioning the application

Let's say that this application uses an XML API, but I'd rather use JSON. The incidental complexity associated with this change depends on how the server handles representations. If the API honors Accept headers, this is easy: the client changes a header.

If the API doesn't honor these headers and instead relies on file extensions, things become more complex: the client developer needs to parse the URIs, replace the old extension with the new extension, test the URIs to make sure they are well-formed and functional, and perform data migration.

Client Simplicity

Allowing file extensions to determine the content type is fine, and it can be helpful in environments that don't allow setting headers. By allowing only file extensions to determine the content type, though, the API designer forces a more complex implementation on the client developer.

As API designers, we often focus on designing for a specific client, when we need to focus more on allowing the client developer decide implementation details.

Functional Python

2012-02-06T14:19:35Z

It seems to me that Python as a language has a weird relationship to functional programming. Things such as the itertools module and the builtin map, filter, and reduce rely heavily a functional style, yet these approaches are often not idiomatic.

As I explore other languages, I wonder what would Python written in a functional style would look like. An evening spent hacking on it has produces some interesting results. These techniques probably shouldn't be seriously used, but this code is just for fun.

Let's examine a short imperative script

def imperative_style(xs):
    results = []
    for x in xs:
        if x >= 7: 
            break
        if x < 2:
            result = 4 * x
            results.append(result)
    return results
 
assert imperative_style(range(10)) == [0, 4]

Whenever I see code like the above imperative_style, I mentally file it as point of possible complexity and bugs, especially as requirements change and more logic is tacked on.

As a comparison, let's look at a simple functional version. First, we're going to need takewhile from itertools, which will allow us to build something like the break statement

After that, we have the function definition, utilizing two builtins, map and filter, as well as takewhile to break the problem down into logically independent parts. Notice that the conditional in the takewhile is inverted.

from itertools import takewhile
 
def functional_style(xs):
    return map(lambda x: 4 * x,
               filter(lambda x: x < 2,
                      takewhile(lambda x: x < 7, xs)))
 
assert functional_style(range(10)) == [0, 4]

There are less moving parts here, but it seems too much like a Christmas tree for me. Can we make it flatter?

For this, we're going to need more tools for working with functions. First is compose, which let's us feed the result of one function as the argument of another. I'm always surprised that Python doesn't have this builtin. In more functional languages this is a basic feature, with Haskell making it one character (.)

def compose_two(g, f):
    """Function composition for two functions, e.g. compose_two(f, g)(x) == f(g(x))"""
    return lambda *args, **kwargs: g(f(*args, **kwargs))
 
assert compose_two(lambda x: x * 2,
                   lambda y: y + 4)(1) == 10
 
def compose(*funcs):
    """Compose an arbitrary number of functions left-to-right passed as args"""
    return reduce(compose_two, funcs)

With compose, we need one more function, partial, which can be used to provide only some of a function's arguments.

from functools import partial
composition_style = compose(
    partial(map, lambda x: 4 * x),
    partial(filter, lambda x: x < 2),
    partial(takewhile, lambda x: x < 7))
 
assert composition_style(range(10)) == [0, 4]

There's a quite a bit of boilerplate in this definition. Can we abstract out a reusable pattern?

from itertools import starmap
def composed_partials(*partial_funcs):
    return compose(*starmap(partial, partial_funcs))
 
composed_partials_style = composed_partials(
    (map, lambda x: 4 * x),
    (filter, lambda x: x < 2),
    (takewhile, lambda x: x < 7))
 
assert composed_partials_style(range(10)) == [0, 4]

This is less noisy, but it's a bit difficult to read the logic in reverse order. Can we change that?

def pipe(*partial_funcs):
    return composed_partials(*reversed(partial_funcs))
 
pipe_style = pipe(
    (takewhile, lambda x: x < 7),
    (filter, lambda x: x < 2),
    (map, lambda x: 4 * x))
 
assert pipe_style(range(10)) == [0, 4]

This definition is more dataflow oriented, much like using pipes in a shell, or Clojure's -> macro. If you look at it just right, this definition looks a bit like a lisp with currying.

This may be too far, but looking at the definition for composed_partials and pipe, they follow a similar structure. Can we extract that out?

def transform_args(func, transformer):
    return lambda *args: func(*transformer(args))
 
composed_partials = transform_args(compose, partial(starmap, partial))
pipe = transform_args(composed_partials, reversed)
 
assert composed_partials_style(range(10)) == [0, 4]
assert pipe_style(range(10)) == [0, 4]

With that, our final complete version is the following:

from itertools import takewhile, starmap
from functools import partial
 
def compose_two(g, f):
    """Function composition for two functions, e.g. compose_two(f, g)(x) == f(g(x))"""
    return lambda *args, **kwargs: g(f(*args, **kwargs))
 
def compose(*funcs):
    """Compose an arbitrary number of functions left-to-right passed as args"""
    return reduce(compose_two, funcs)
 
def transform_args(func, transformer):
    return lambda *args: func(*transformer(args))
 
composed_partials = transform_args(compose, partial(starmap, partial))
pipe = transform_args(composed_partials, reversed)
 
pipe_style = pipe(
    (takewhile, lambda x: x < 7),
    (filter, lambda x: x < 2),
    (map, lambda x: 4 * x))

It's a bit longer than the original version, but provides small reusable parts that can be quickly assembled into larger programs.

Using Pushstate with Backbone.js and Django

2011-12-30T20:54:35Z

After working on a few projects with Django and Backbone, I really wanted to replace my hash-driven apps with pushstate. Django-pjax is a library aimed at making this easier for more traditional projects, but would require me to duplicate my display logic server side, without using my current mustache templates. After a few iterations, I've settled on an approach that is DRY enough for my taste. You can view the work in my django-backbone-example project.

One way to keep the project keeps templates DRY is through a template tag that renders mustache templates inline. Combined with a client side template engine, templates can be shared between the client and server. Example usage:

<div class="tweet">
  {%mustache "path/to/my/tweetTemplate" tweet%}
</div>

By using Tastypie Resources in the view, the same data preparation can be used for both methods. The view from the example project is as follows:

class DetailView(TemplateView):
    template_name = 'index.html'
 
    def get_detail(self, pk):
        tr = v1.canonical_resource_for('tweet')
 
        try:
            tweet = tr.cached_obj_get(pk=pk)
        except Tweet.DoesNotExist:
            raise Http404
 
        bundle = tr.full_dehydrate(tr.build_bundle(obj=tweet))
        data = bundle.data
        return data
 
    def get_context_data(self, **kwargs):
        base = super(DetailView, self).get_context_data(**kwargs)
        base['data'] = self.get_detail(base['params']['pk'])
        return base

When adapting a client that already supports the hash-driven routing, it should just be a matter of altering the call to Backbone.history.start() to

Backbone.history.start({
    silent: true,
    pushState: true
});

Client Performance Monitoring with Boomerang and CouchDB

2011-06-04T17:20:16Z

A project that that interested me awhile ago, but I only recently got around to trying was Boomerang from Yahoo! It's a Javascript library that calculates the round trip time to load a page from the user's browser, using either cookies or the WebTiming API if it's available.

This project is exciting since it measures the time from when the user navigates away from the page to when the page has loaded, which could be affected by any number of things, such as latency, download speeds, or uncached static files. While there are best practices and tools to help improve client performance (YSlow, Chrome's built-in performance tools, DOM Monster), they aren't able to provide recommendations based upon real users' performance.

This data is can serve as an constant benchmark, which combined with the VCS data, can allow you to detect changes that result in performance regressions. This also opens up the possiblity of doing split tests on website performance.

Here are a few quick test ideas:

Testing of competing CDN solutions with actual users.
Script loaders versus traditional script tags.
Testing bundle combinations.

Round trip time isn't all that you can measure with Boomerang. It comes with bandwidth, latency, and DNS latency plugins, as well as instructions on how to make more granular timers.

Getting started with Boomerang is pretty easy. For this blog, I wrote a quick node.js app that translated the GET params Boomerang sends into a JSON document and uploads it to CouchDB. The code for this app is available on Github. I went with CouchDB because of the flexibility from it being schemaless, combined with near realtime reports from the incremental map reduce views.

First I grabbed a recent version of Boomerang from the repo, including it in the head. Then, I added the following configuration:

BOOMR.addVar('revision', '{{REVISION}}');
BOOMR.init({
  beacon_url: '{{ANALYTICS_SERVER}}',
  site_domain: "{{site.full_url}}", 
  BW: { enabled: false  }
  });

Here I'm doing a standard Boomerang setup, disabling the bandwidth test because it requires a bit more work, and adding REVISION, a custom Hyde variable, allowing me to keep track of the current git commit.

Here's an example CouchDB view I'm using to monitor this blog.

Map:

function(doc) {
    var timestamp = new Date(Date.parse(doc.timestamp)),
        time_done = parseInt(doc.t_done);
 
    if(timestamp && time_done){
        emit([timestamp.getFullYear(), timestamp.getMonth(), timestamp.getDate()],
             time_done);
    }
}

Reduce: _stats

And some example stats:

{"rows":[
    {"key":[2011,4,30],"value":{"sum":68474,"count":24,"min":146,"max":18990,"sumsqr":520080894}}
]}

With this combination of tools, it's easy to generate quick reports and tests. I'm looking forward to using Boomerang for upcoming projects.

Async Workers in Django with Celery

2011-02-10T22:09:41Z

Celery, the distributed task queue framework, recently introduced asynchronous workers in the 2.2 release. I found that when I tried to use the eventlet worker using Celery's Django integration, it started to hang after making some database calls, at least when using the psycopg2 database backend.

I found that I could get around this by applying eventlet's monkey patch before Django starts loading. I did this by writing a separate manage.py, like the following.

Now I'm able to run ./async_manage.py celeryd -P eventlet -c 100, and not have it hang on database calls.

I've not tried this method with gevent, but a similar approach should work.

Backbone.js and Django

2010-11-25T20:54:35Z

NOTE: Since this post, both Backbone.js and Tastypie have gone through a lot of changes. As of December 30th, 2011, the reference repo on Github has been updated to the latest versions, and changed to use backbone-tastypie, which provides an nice compatibility layer, and stays updated better than the examples in this post.

I've been using backbone.js recently, mostly with node.js, or with the localstore bundled with the example Todo application for quick prototypes. However, I wanted to integrate it within some existing Django applications, but had some trouble.

Since Backbone assumes a REST architecture, I needed some way to expose my Django models. For this, I went with Tastypie, which is the easiest way I've found to write a RESTful API for your app.

I've put together a sample application using Backbone and Tastypie, viewable on Github, though I'll do a quick walkthrough of the code.

Here's the models.py, which defines an overly simple tweet.

from django.db import models
 
class Tweet(models.Model):
    username = models.CharField(max_length=25)
    message = models.CharField(max_length=140)
    timestamp = models.DateTimeField(auto_now_add=True)

Using Tastypie for our API, we setup a resource

from tastypie.resources import ModelResource
from tastypie.authorization import Authorization
from tweets.models import Tweet
 
class TweetResource(ModelResource):
    class Meta:
        queryset = Tweet.objects.all()
        authorization = Authorization()

Then we setup some urlpatterns to access our data.

from django.conf.urls.defaults import *
from tweets.api import TweetResource
 
tweet_resource = TweetResource()
 
urlpatterns = patterns('',
    (r'^$',
     'django.views.generic.simple.direct_to_template',
     {'template':'index.html'}),
    (r'^api/', include(tweet_resource.urls)),
)

From here, you should be able to use curl to test out the api, like so:

$ curl -H 'Accept: application/json' http://localhost:8000/api/tweet/
{"meta": {"limit": 20, "next": null, "offset": 0, "previous": null, "total_count": 0}, "objects": []}

In the above urls, there was a direct to template view, which will be our simple app. This will load Backbone and dependencies, ICanHaz.js for templating, and define a template for displaying tweets, and the basic structure of our page.

{%load verbatim%}
<!doctype html>
<html lang="en">
  <head>
    <title>Django + Backbone.js</title>
 
    <link rel="stylesheet"
          href="http://yui.yahooapis.com/3.2.0/build/cssreset/reset-min.css">
    <link rel="stylesheet" href="{{MEDIA_URL}}css/style.css">
 
    <script src="//ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.js"></script>
    <script src="http://cachedcommons.org/cache/underscore/1.1.0/javascripts/underscore-min.js">
    </script>
    <script src="{{MEDIA_URL}}js/ICanHaz.min.js"></script>
    <script src="{{MEDIA_URL}}js/backbone-min.js"></script>
    <script>
      TWEET_API = "{%url api_dispatch_list resource_name="tweet"%}";
    </script>
    <script src="{{MEDIA_URL}}js/app.js"></script>
 
    {%verbatim%}
    <script type="text/html" id="tweetTemplate">
      <a class="username">{{username}}</a>
      <p class="message">
        {{message}}
      </p>
      <abbr class="timestamp">{{timestamp}}</abbr>
    </script>
    {%endverbatim%}
  </head>
 
  <body>
    <div id="app">
      <div id="input">
        <strong>What's going on?</strong>
        <textarea id="message"></textarea>
        <button class="tweet">Tweet</button>
      </div>
      <h2>Timeline</h2>
      <ul id="tweets">
      </ul>
    </div>
  </body>
</html>

Notice there is a nonstandard tag, {%verbatim%}, which is used to escape the Mustache templates. This tag is by ericflo, and can be found on Github.

Finally, we need to setup our application code in Javascript. First we'll change Backbone's sync function, to do a GET upon receiving a HTTP CREATED. This requires 2 requests to do a create, so you may want to use some other method in production.

var oldSync = Backbone.sync;
 
Backbone.sync = function(method, model, success, error){
    var newSuccess = function(resp, status, xhr){
        if(xhr.statusText === "CREATED"){
            var location = xhr.getResponseHeader('Location');
            return $.ajax({
                       url: location,
                       success: success
                   });
        }
        return success(resp);
    };
    return oldSync(method, model, newSuccess, error);
};

Next, we'll define our Tweet model. Since we have so little logic in this application, we'll just define the url attribute so we can talk to the server. Tastypie will give the individual tweets a resource_uri attribute, but if it hasn't been persisted to the server, it should default to the collections url. We do this because a POST to the collection should add produce a new tweet. Tastypie also namespaces the resulting JSON, so we'll need to define a parse function on the collection that will return the objects attribute in the data returned from the server.

window.Tweet = Backbone.Model.extend({
  url: function(){
     return this.get('resource_uri') || this.collection.url;
  }
});
 
window.Tweets = Backbone.Collection.extend({
  url: TWEET_API,
  parse: function(data){
      return data.objects;
  }
});

Next are the views that define our application, the first is responsible for displaying the individual tweets on the page.

window.TweetView = Backbone.View.extend({
  tagName: 'li',
  className: 'tweet',
 
  render: function(){
      $(this.el).html(ich.tweetTemplate(this.model.toJSON()));
      return this;
  }
});

Last, we have a top level view that handles the user interaction. It is responsible for creating the collection of tweets, loading and display them. It also listens for a click event on the button that says "Tweet", and will create a new tweet in the collection.

window.App = Backbone.View.extend({
  el: $('#app'),
 
  events: {
      'click .tweet': 'createTweet'
  },
 
  initialize: function(){
      _.bindAll(this, 'addOne', 'addAll', 'render');
      this.tweets = new Tweets();
      this.tweets.bind('add', this.addOne);
      this.tweets.bind('refresh', this.addAll);
      this.tweets.bind('all', this.render);
      this.tweets.fetch();
  },
 
  addAll: function(){
      this.tweets.each(this.addOne);
  },
 
  addOne: function(tweet){
      var view = new TweetView({model:tweet});
      this.$('#tweets').append(view.render().el);
  },
 
  createTweet: function(){
      var tweet = this.$('#message').val();
      if(tweet){
          this.tweets.create({
                                 message: tweet,
                                 username: "Test User"
                             });
          this.$('#message').val('');
      }
  }
});
 
window.app = new App();

And with that we've got a (admittedly very) simple Twitter clone working with our Django model. Hopefully this helps you in creating applications with Django and Backbone.

Using Thread Locals in Django

2010-09-26T23:25:36Z

The Django docs are pretty clear on threadlocals. One good use I can think of for threadlocals is for Basecamp style subdomains.

This seems like a great way to use Django's sites framework, except it requires the SITE_ID to be set in the settings. You can use a middleware that uses threadlocals to set this per request, such as the one provided by django-multisite. This is mostly a drop-in solution, but requires you to think of where your querysets are being built.

Let's take the following example models:

from django.db import models
from django.contrib.sites.models import Site
from django.contrib.sites.managers import CurrentSiteManager
 
class Author(models.Model):
    name = models.CharField(max_length=200)
    active = models.BooleanField()
    site = models.ForeignKey(Site)  
    on_site = CurrentSiteManager()

With the following form:

from django import forms
from models import Author
 
class ExampleForm(forms.Form):
    author = forms.ModelChoiceField(queryset=Author.on_site.filter(active=True))

Unfortunately, this may not work. The queryset will be built using the SITE_ID that is in effect when the form class is declared, resulting in the same SITE_ID being used process-wide.

You can enforce the SITE_ID to be evaluated in the proper context, assuming you aren't doing anything tricky, by changing the queryset upon the form initialization.

class ExampleForm(forms.Form):
    author = forms.ModelChoiceField(queryset=Author.objects)
 
    def __init__(self, *args, **kwargs):
        super(ExampleForm, self).__init__(*args, **kwargs)
        self.fields["author"].queryset = Author.on_site.filter(active=True)

This is just one example of how values in threadlocals may yield application errors when you aren't aware of the context the code is executed in.

Speeding Up Mingus

2010-03-18T03:32:29Z

Inspired by Cody Soyland's excellent post on caching in Django, I decided I was going to work on speeding up Mingus.

In the spirit of Mingus, I decided to use a reusable Django application to achieve this. My choice was StaticGenerator.

With the provided middleware, generating the static pages is simple. Cleaning this up, however, isn't as easy. Mingus leverages a very modular design for building pages, making it a great candidate for template tag and view level caching. Many individual parts are cached and reused for different pages, really decreasing the number of database queries.

My initial strategy was to clear the static cache of any changed pages using Django's Signals. It was simple, if a bit tedious, to set up. And it was incomplete.

Consider what happens when a user visits some page that caches the list of posts in memory, right before a new post is published. If the home page is visited before the cache expires, the new post will not show up in the list of posts, but will be shown in the body of the home page.

With direction from this Django Snippet, I added the ability to clear template caches on update, fixing this problem. Unfortunately, it currently requires hardcoding the template fragment names, making the cache invalidation logic dependent on the templates. I want to get rid of this, but haven't thought of an elegant way to solve this.

As I was writing this post, I stumbled upon another problem. If I saved a post as a draft, then visited it, StaticGenerator would allow anyone to see it. Luckily, Jon Smelquist on Github had a commit that added the ability to generate static pages only for anonymous users. With that and a few more checks, my own fork of StaticGenerator addresses this problem.

This is far from an optimal solution, however. One part of the Mingus home page I haven't been able to solve is the right hand popular links feed. Using full page caching without some sort of time-based clearing, these links are going to be out of sync from page-to-page. I've chosen to drop that module for now. Also, the Requests app doesn't receive data on cached pages. I don't see this as too much of a loss, as Google Analytics reports more information for those pages.

For the curious, here's a quick benchmark of the home page. I'm making no claims about this data, only publishing it.

$ ab -n 10000 -c 100 http://rowan.computer/
... 
Document Path:          /
Document Length:        4975 bytes
 
Concurrency Level:      100
Time taken for tests:   1.097 seconds
Complete requests:      10000
Failed requests:        0
Write errors:           0
Total transferred:      51994488 bytes
HTML transferred:       49869400 bytes
Requests per second:    9118.79 [#/sec] (mean)
Time per request:       10.966 [ms] (mean)
Time per request:       0.110 [ms] (mean, across all concurrent requests)
Transfer rate:          46301.44 [Kbytes/sec] received
 
Connection Times (ms)
              min  mean[+/-sd] median   max
Connect:        2    5   0.5      5       7
Processing:     3    6   0.9      6      10
Waiting:        2    5   1.0      5       8
Total:          8   11   0.8     11      13
 
Percentage of the requests served within a certain time (ms)
  50%     11
  66%     11
  75%     12
  80%     12
  90%     12
  95%     12
  98%     12
  99%     13
 100%     13 (longest request)

If you're interested you can view this code here. As always, I encourage forking and bug reports.

Herbie Hancock and the Headhunters - Watermelon Man

2010-03-12T21:17:35Z

Some days you just need some funk.

Rowan Bohde blog

Integrating a Broan Ventilator into Home Assistant

Staying Fast Under Load

Load Shedding

Active Queue Management

Performance

Try it out

Pattern Matching on Records in Haskell

Haskell Refactoring

Types of Refactorings

An Example

Combining Refactorings

More Reading

Cool Things About Go From A Haskell Perspective

Compile times

Static linking

Cross compilation

gofmt

goimports

go test

quick

Build tags

Package structure

tools

Optimizing Queries with Applicatives

A Key Value Store

Examples

Thoughts

Self Hosting Git

Gitolite

Gitweb

Git-Daemon

Migrating

Thoughts

Don't Design the API to the Client

Document Summarization using TextRank

Sentence Splitting

Bag of Words

Converting to a Graph

Pagerank

Programming With Only Functions

A Tiny Computation System

Encoding

Decoding

Successors

Addition

Multiplication

Exponents

More Encodings

Combinators in Python

Simple REST URIs

An Example Application

Transitioning the application

Client Simplicity

Functional Python

Using Pushstate with Backbone.js and Django

Client Performance Monitoring with Boomerang and CouchDB

Async Workers in Django with Celery

Backbone.js and Django

Using Thread Locals in Django

Speeding Up Mingus

Herbie Hancock and the Headhunters - Watermelon Man

`gofmt`

`goimports`

`go test`

`quick`