dagit.o

A phantom type is a type that has no value associated with it, such as the following:

data P phantom = P Int


Above, the type “phantom'’ has no value associated with it on the right-hand side of the equal sign. This means that whenever we construct a value of type P we also need to give a type for phantom, but because it has no value associated with it to constrain its type the type system can make it unify with anything.

For example these are all valid:

P 5 :: P String
P 5 :: P [Int]
P 5 :: P (IO ())


The reason we care about phantom types is that they allow us to embed extra bits of information in our types. In this regard, you can think of phantom types as a tagging system for types. This allows you to, for example, encode a simpler type system within Haskell’s types. You could use this when making an evaluator for a language in Haskell.

Now, there is a well known problem with the unification above. The problem is that P can be made to unify with all kinds of things. So people often use smart constructors to control the unification. For example, P would be declared in a module and the data constructor would not be exported from that module and instead you’d export functions like this:

mkIntP :: Int -> P Int
mkIntP n = P n


mkStringP :: String -> P String
mkStringP s = P (length s)


Now you’ve controlled how the unification of the phantom type by not allowing users of your data type to choose how it unifies.

Suppose we don’t know the full extent of the types that the user wants the phantom to unify with. Which is to say, there are an unbounded number of types for which the phantom can unify but you want to give the user of your code a way to control the unification.

Let’s talk about existentials for a moment. We can give existential types by using a language extension that allows us to explicitly give a “forall” in the type. Now the oddity of giving an existential with a universal quantification is well documented but I won’t discuss it here. You might create a Seal type like this:

data Seal a = forall x. Seal (a x)


Now when we put a value inside a Seal we forget everything we know about the type x. The only thing we remember about x is that it exists. This means that when we open up the seal:

f :: Seal a -> ()
f (Seal a) = ()


We have to invent a new type for x. Here the type system is smart and creates a new fresh name, let’s call it an eigenvariable, for x inside the pattern match of f.

This eigenvariable for x is distinct. The only type it is equal to is itself. This is because when we put x in the Seal we agreed to forget everything we ever knew about it–except that it exists.

We could try this:

g :: Seal a -> a x
g (Seal a) = a


Here the type system is very smart and complains. The error message is a bit confusing, but what it is trying to tell us is that we cannot safely let the eigenvariable for x escape to a higher scope. Letting this happen has implications I won’t go into.

Now, remember what I was saying about letting phantom types unify and wanting to control the unification? Well, Seal gives us a way to let the user put whatever types they want in the phantom type and it gives the user a way to control how that type unifies!


mkSealP :: a -> Seal P
mkSealP a = Seal (P a)


Now the user of our code can make a P with an arbitrary phantom type that we didn’t have to anticipate with a smart constructor and the user gains back control over how the phantom type of P will unify. With the current bit of code it won’t unify with much :)

Now we’ve moved the problem from unifying with too much to not unifying with anything. Next time I’ll discuss some strategies for recovering information about x so that you can do something meaningful with that type.

The weekend of 24-25 October 2008 was an International darcs hacking sprint! The sprint was a lot of fun and we’ll be having more. The sprint provides a very productive atmosphere for hacking.

We had a team in Brighton with posts from Day 1 and Day 2. We also had team in Paris but I don’t have a link for them.

Here are just some of the highlights from the Portland Team:

• Adding language pragmas in all files:
  • makes the code cleaner when it’s time to drop ghc6.6 support
  • all required language extensions are now known
  • makes it easier to check for Haskell’ compatibility
• Removed OldFastPackedStrings
• Replaced FastPackedStrings api in favor of Data.ByteString api
  • lots of small optimizations, less pack/unpack, more standard
    ByteString code
  • removed a fair bit of C code, new code compiles to same or
    faster assembly (Don checked)
• cabalization:
  • no autoconf or make needed
  • cabal install tested and working on linux / osx, windows testing
    soon to follow
  • builds out of the box w/ 6.8 and 6.10
  • configure is much faster
• module graph (depends on cabalization)
• Duncan improved zlib
  • soon to be available on hackage
  • allows us to replace our own implementation of zlib bindings
    with the main stream one
  • will make building on windows easier
  • can use lazy bytestrings

Here are some random pictures from the Portland Sprint.

Packages we should consider:

The TODO list we made on the first day:

Checking on Team Brighton:

Duncan and Jason looking at the projector:

Ah, beautiful Portland in fall:

I’m clearing out some unfinished posts I have. Here are two points that struck a cord with me from a speech by Richard Hamming.

From http://www.cs.virginia.edu/~robins/YouAndYourResearch.html

I think this first bit is good advice for all of us. Instead of summing it up, I’ll just let you read it the way Hamming intended it to be said:

To end this part, I’ll remind you, “It is a poor workman who blames his tools - the good man gets on with the job, given what he’s got, and gets the best answer he can.'’ And I suggest that by altering the problem, by looking at the thing differently, you can make a great deal of difference in your final productivity because you can either do it in such a fashion that people can indeed build on what you’ve done, or you can do it in such a fashion that the next person has to essentially duplicate again what you’ve done. It isn’t just a matter of the job, it’s the way you write the report, the way you write the paper, the whole attitude. It’s just as easy to do a broad, general job as one very special case. And it’s much more satisfying and rewarding!

This next bit is very personally humbling. I’ve lost track of the number of times in my life when I’ve found myself as the “second-rate fellow'’ he describes below. For me it often comes up in dealing with things that I label as “political'’. I don’t mean Republicans versus Democrats, but by political I mean things which matter but are related to policy not theory or technical details.

Many a second-rate fellow gets caught up in some little twitting of the system, and carries it through to warfare. He expends his energy in a foolish project. Now you are going to tell me that somebody has to change the system. I agree; somebody’s has to. Which do you want to be? The person who changes the system or the person who does first-class science? Which person is it that you want to be? Be clear, when you fight the system and struggle with it, what you are doing, how far to go out of amusement, and how much to waste your effort fighting the system. My advice is to let somebody else do it and you get on with becoming a first-class scientist. Very few of you have the ability to both reform the system and become a first-class scientist.

Hamming is absolutely right. If you want to be good at a particular thing, don’t fight your battles else where. Be balanced, objective and reasonable. Bark less and wag more :)

People often want to understand how commute on patches works. Usually we start by saying:
Given two patches, A and B, if A and B commute then: AB <--> B’ A’, for some B’ and A’.

Naturally people ask, “But what is the relationship between A and A’ or B and B’?”

This is a very important question and I’ll provide you with some insight.

Suppose we have a repository with 2 files, a and b. We could then make the following operations:
mv b c
mv a b
mv c a

You can think of each operation as a transformation on the ’state’ of your repository.

Suppose also, that we make an edit to a, and an edit to b.

Let’s name the above, using T for transformation:
T_bc = mv b c
T_ab = mv a b
T_ca = mv c a
T_a = edit a
T_b = edit b

You can imagine that if I gave the diff for T_a and the diff for T_b that you could apply those diffs in either order to your repository and get the same final ’state’. Meaning, a and b are the same whether you update a first or b first.

But, suppose instead that I performed T_bc, T_ab, and then T_ca. This has the effect of swapping a and b by name. Now suppose you applied the diffs T_a and T_b. What would you want the outcome to be?

It turns out, that it matters which operations were created first. If you created the diffs T_a and T_b *before* you did the operations of the swap, then you should expect that after the swap the diff for T_a actually modifies b, whereas T_b should modify a. On the other hand, if you created the diffs T_a and T_b *after* the swap, then you expect T_a to modify a and T_b to modify b.

We have an intuitive idea of ‘context’ now. As in, what is the context that T_a and T_b were created in? Knowing this will tell us how they transform the repository state.

Intuitively, it seems as though we need to remember the ‘context’ in which T_a and T_b were created. So let’s say that the operations performed up to the point where T_a is created is the context of T_a. In other words, the context for T_a is sequence of transformations that existed when T_a was created. Similarly, since T_a is a transformation, creating it results in a new context, which is the old context plus T_a. We could say that T_b has this context. Going a bit further, it seems like we should talk about how T_a has a pre-context and it also has a post-context.

For example, if we created T_a before doing the swap, then the pre-context might include two transformations, one that creates a and another one that creates b. The post-context would then include those two transformations and T_a itself. If we created T_a after doing the swap, the pre-context and post-contexts of T_a would include T_bc, T_ab and T_ca also.

Now a side note about commutative functions. Consider the function created by composing T_a and T_b, let’s write T_a . T_b. Recall, that with function composition parameters start on the right and pass through the sequence to the left. As discussed in the intro, T_a . T_b is equal to T_b . T_a. This is because T_a and T_b are independent of each other. Thus, we would say that the functions T_a and T_b are commutative functions. This means, that changing their order of application does not change the result.

We are saying that:
T_a . T_b = T_b . T_a

Because T_a and T_b are commutative it doesn’t matter which order we compose them. If we restrict our view to just the repository above with only the files a, b and no c, then on this restricted set of repository state how do these two compare?
T_b . T_a
T_a . T_b . (T_ca . T_ab . T_bc)

In plain English, the first one edits a and then b, the second one swaps a and b, edits b and finally edits a.

As far as the mathematics of it is concerned, the first one will edit a and b, while the second one will have T_a editing a different a than the first one and T_b editing a different b than the second one.

Going a bit further, let’s say that T_a and T_b were created without any of T_bc, T_ab or T_ca in their context. So we could have two scenarios.

We could, for example, start with T_b and T_a, swap their order and then do the swap of a and b afterwards. That would give us:
T_b . T_a
and
(T_ca . T_ab . T_bc) . T_a . T_b

Intuitively, it seems like T_a and T_bc are commutative functions, eg., T_bc . T_a = T_a . T_bc. So we could rewrite the second one as this:
T_ca . T_ab . T_a . T_bc . T_b

Now, suppose when we commute the function T_a with T_ab, that we replace T_a with T_a’. T_a’ is like T_a except that T_a’ makes the edits of T_a to b instead of a. After all, this results in T_a’ editing the correct file after the rename. Similarly, when we commute T_b with T_bc, T_b is replaced with T_b’ that edits c instead of b. When we commute T_b’ with T_ca we replace T_b’ with T_b'’ that edits a instead of c.

So, the above goes through these steps:
T_ca . T_a’ . T_ab . T_bc . T_b (commute T_a to the left)
T_a’ . T_ca . T_ab . T_bc . T_b (commute T_a’ to the left)
T_a’ . T_ca . T_ab . T_b’ . T_bc (commute T_b to the left)
T_a’ . T_ca . T_b’ . T_ab . T_bc (commute T_b’ to the left)
T_a’ . T_b'’ . T_ca . T_ab . T_bc

The last one will then have T_a’ and T_b'’ making edits the same file contents as T_a and T_b respectively, even though the names of the files were changed by the swap.

So, if you’ve followed me to this point, then you now have the intuition for what we mean when two patches A and B, commute to B’ and A’, as AB <--> B’ A’. You can think of a patch as being one of the above transformations along with the context of the transformation. You might also notice that commute of patches must be doing something to the context of the patches.

Patch commute has the potential to update the context and transformation the patches it swaps OR it could update the context and leave the state transformations equal to what they were in the input. Patch commute can also fail, but we’re ignoring that case for the moment.

Thinking back to how we arrived at the need for context, you might notice that for each context, that is each sequence of operations, we get one unique repository state. This is a very important property of context. Without it, context wouldn’t really be useful. Also, notice that the opposite is not true, repository state does not determine the context. Which makes sense, because there are lots of operations you can do that get the repository to a particular state, so given a state how do you know what was done?

The next important property we want for commuting patches is that once two patches have been commuted, you can commute them again to undo the commutation. In fact, it turns out the examples above are saying we want contexts to determine the same state if you commute the patches inside the context (again, context is a sequence of patches!).

For R to be an equivalence relation, we need three things:
1) x R x, is true for all x
2) if x R y then y R x
3) if x R y and y R z then x R z

Here, we replace x R y with “the sequencing, or order, of x can be obtained by commuting adjacent elements of y”. Roughly how to prove each:
1) either claim that 0 commutes satisfies definition of R or check that commute is self-inverting
2) relies on self-inverting nature, I think
3) messier but should still be provable

I’m pretty sure both (2) and (3) could be done with a brute force proof that considered all the pairings of patch types in their general cases. Start with all sequences of length 2, then 3 and I think at that point you could make an inductive argument to hit sequences of length n. This would be a lot of work, and I’m not convinced it could be fully automated.

Why would we want to show the above? Showing that R is a relation would tell us that sequences of patches are equivalent under commute. Now, combine this with the idea that context determines the state uniquely and now we know sets of patches uniquely determine your repository.

Thanks to Eric Kow, Duncan Coutts and Ian Lynagh we have some great timing data for using darcs2 and darcs1 to push patches over ssh.

Eric wrote a script to test three different scenarios of using darcs to push patches:

1. Scenario l1r1:

This is a local darcs1 client talking to a remote darcs1 executable.

2. Scenario l1r2:

This is a local darcs1 client talking to a remote darcs2 executable.

3. Scenario l2r2:

This is a local darcs2 client talking to a remote darcs2 executable.

Next, Duncan and Ian provided us with access to 131 real-world repositories hosted at http://code.haskell.org. We ran the script to push patches to each repository, this gave us a ton of times. Then in Excel we crunched these numbers to see that not only is scenario l2r2 no worse than the other two, it’s actually faster on the time consuming cases!

The one caveat we found is that the minimum start-up time for the first two scenarios is 1 second and in the last scenario it’s 2 seconds. I’m confident we can shave off this 1 second difference in the future.

This is a histogram that shows you how the push times distribute, click on it for a large image. Along the bottom we have how many seconds the push took, and along the vertical axis we have the number of data points in that range. At a glance you can see that most repositories take just a few seconds to push. We can also see that darcs2 is slower on small pushes by about one second. Darcs2 in this chart corresponds to l2r2 and darcs1 corresponds to l1r1.

On a side note, we also tested converting all the repositories to darcs2 repository format and that worked great as well. Converting all the repositories at once takes less than 20 minutes on my laptop without a single error. There were a few warnings, but that’s to be expected as potentially exponential merges are fixed in the new darcs2 format, but darcs emits a warning when fixing them.

For anyone that wants to see the raw numbers click here. The link does work, but not all web browsers are showing the numbers. Opera and FF3 work on some platforms and not others.

Today I ran in my first marathon, the Eugene marathon. The experience was truly amazing and surpassed my wildest expectations. Those of you who know me personally know I’ve been training consistently for the past 11 months or so with only a month and a half break during that time. My training has come with injuries but has always been tempered by an almost blind devotion to running.

First a bit of background. I truly love running and I’m so great full to have it back in my life after taking almost a decade off. Until last year I hadn’t enjoyed a consistent workout schedule since I was in the middle of high school. When I was in high school I ran cross country on the suggestion of my algebra teacher, who saw me run a mile in PE class one day and beat one of his runners. My teacher was also the coach of a surprisingly good cross country team. This teacher/coach is someone I came to admire during high school and someone I found to be a real inspiration. He is largely responsible for my decision to major in math in college and he has left a huge impression on my life.

The marathon started at 7am, but I needed to get to the parking lot between 6 and 6:30 to catch a ride to the starting line. My day started at 4am. I arrived in Eugene quite a bit earlier than I had intended (about 5:40). On my way to Autzen stadium I took a wrong turn (not sure I’ll ever learn to read signs). I noticed a fire in the distance as soon as I took the wrong turn. As I got closer I came to a parking lot with truck which had a camper in the back in flames. Next to the truck was an older man, later I found out his name was Mel. I pulled up to see if Mel needed help, he was fine and had just checked the camper for people, but on one answered.

We called the fire department and they dispatched someone to put out the fire immediately. From here Mel and I walked to the starting line. We chatted a bit on the way. I could sense this was not Mel’s first marathon and we talked about marathoning a bit. He ran his first marathon when he was 50. Once we got to the starting line I lost track of Mel and made a new friend Jeff.

Jeff and I ran for a while. It was his first half marathon, but eventually I couldn’t hold back and I lost Jeff in the crowd as I sailed on toward the 4th mile. Somewhere around the 6th mile I caught up with Mel again as did one of his buddies from a past marathon. His buddy asked him which marathon he was on today. Today was his 308th marathon! Simply amazing. He started when he was 50 and he was on his 308th! I also found out he is a 4 star marathon maniac. Apparently the first rank involves running 3 marathon is one month and the challenges just get harder from there. Unfortunately Mel was injured and fading fast, so he told me to run on without him and that was the last we spoke.

The rest of the run was pretty uneventful until about the half marathon point. By the time I reached the half marathon I realized I was passing people right and left who were dragging their feet, panting or otherwise showing fatigue. Yet there I was trying to tell them how beautiful the day was or pointing out pretty birds. I realized at this point I had been holding back maybe too much so I kept increasing my speed. Starting slow and increasing pace for as long as you feel good was a trick my coach taught me years ago.

Around mile 18 or 20 I realized I would finish the whole marathon regardless of whether or not my injuries came back and my time would be good too. This is when I started to day dream about who I could call and brag too as soon as I got back to my phone. I went through a mental list and I kept coming back to the idea of calling my coach and telling him what I had done.

Around mile 21 or 22 I hit the dreaded wall. At first all my leg muscles started to burn, next the burn became painful whenever I ran. Pretty soon I was taking walk breaks because it was exhausting to fight the pain of lifting my legs. After another mile or two this pain was present even when walking. I knew even if I wanted to walk off the course I’d still have to walk the same distance so I trucked on. This is also the point at which the 4 hour pace runner passed me. I caught back up with him twice but I was fading and the wall really is hard to overcome. It doesn’t help that I’m a big wimp. I can handle some fatigue, but when fatigue hurts I’m a big baby. I have to say, the pace runner was very inspirational and he gave me another half mile of running just with his encouraging words.

So, there I was around 25 miles, walking with no intent of running anymore today. I was done, and even without breaking 4 hours, today had been an amazing day. I knew I had done what I came to do today. I had proof that at 7am my 11 months of training had put me within finishing distance. A grueling 26.2 miles.

And there, at the 26 mile marker was a familiar face sitting on the sides cheering for people. We both did a double take. My old coach was sitting there. I almost walked off the course to talk to him and he shouted, “I’ll talk to you AFTER you finish.” I was still speechless so I just gave him a thumbs up, reached into my last reserves of will power and pain tolerance, and ran the last 385 yards to finish with a time of 4:03:08. Not a bad time at all for a first marathon. I finished ahead of over half the runners. As soon as I took care of the formalities (getting a finisher medal and grabbing food) I walked (quickly) back to my old coach and gave him a great big hug. The marathon could not have had a happier ending for me. I’m writing this nearly 9 hours later and I can barely believe it all happened today.

Here are some statistics for my own record:
Time: 4:03:08
Bib#: M1259 (significant because 1259 is prime!)
Overall place: 692/1496
Division place(?): 79/119 (probably for my age group?)
Sex place: 489/835
Pace: 9:17
10K: 56:29
Half: 154:33
20Mile: 2:54:34
Last10k: 1:08:35 (you can tell I hit the wall after 20 some miles)

Recently I started using QuickCheck but things were a bit hard to get working so I’ll help write down what I’ve learned now that it’s working nicely.

I wanted to store all my tests in one file, say, Tests.hs and only mention them once in the entire code base. So, once a test is defined I want everything else to be automated, I don’t want to have to list it for inclusion in a harness or any of that junk.

Prerequisites

My setup requires Template Haskell (TH) and a Haskell parser which means you’ll need GHC. You’ll need quickcheck and a desire to test :-) I don’t assume any knowledge of TH, quickcheck, cabal or parsing haskell but I don’t really explain them either. If you get lost by my lack of details shoot me an email or post a comment and I’ll be happy to clarify.

Setup

Template Haskell has a restriction on top level splices that says you cannot use a function in a splice if the function was defined in the same module as the splice. I already have a file in my project called “Utility.hs” where I store my general purpose and misc. functions so this is where I place things to be used in top level splices. This will make more sense when we get to mkCheck.

When you define a test for QuickCheck the name always begins with “prop_”. Here is an example test:

-- from Tests.hs
prop_lrotate1 xs = lrotate (length xs) xs == xs
  where types = xs :: [Int]

This test says, whenver you rotate a list by its length you better get the original list back (obviously we are assuming a finite list). This test, also known as a property in quickcheck terminology, goes into Tests.hs.

In Utility.hs I’ve defined some functions to read over Tests.hs and pull out the names of any properties. I decided to use a Haskell98 parser just to be safe, but you could use regular expressions here.

-- From Utility.hs
{- | looks in Tests.hs for functions like prop_foo and returns
  the list.  Requires that Tests.hs be valid Haskell98. -}
tests :: [String]
tests = unsafePerformIO $
  do h <- openFile "src/Tests.hs" ReadMode
     s <- hGetContents h
     case parseModule s of
       (ParseOk (HsModule _ _ _ _ ds)) -> return (map declName (filter isProp ds))
       (ParseFailed loc s’)            -> error (s’ ++ ” ” ++ show loc)

{- | checks if function binding name starts with @prop_@ indicating
 that it is a quickcheck property -}
isProp :: HsDecl -> Bool
isProp d@(HsFunBind _) = “prop_” `isPrefixOf` (declName d)
isProp _ = False

{- | takes an HsDecl and returns the name of the declaration -}
declName :: HsDecl -> String
declName (HsFunBind (HsMatch _ (HsIdent name) _ _ _:_)) = name
declName _                                              = undefined

Why do I need the unsafePerformIO? Well, that’s to get around a little problem I was having with top level splices. Perhaps if I were a little bit better with Template Haskell I wouldn’t need it. In this case it’s perfectly fine because we won’t be changing Tests.hs while we’re compiling the testsuite so the list of tests will not change while we’re using this function. Now that we have a list of test names we can build an AST to execute the tests. This is where Template Haskell comes in.

-- From Utility.hs
mkCheck name = [| putStr (name ++ ": ")
               >> quickCheck $(varE (mkName name)) |]

mkChecks []        = undefined -- if we don't have any tests, then the test suite is undefined right?
mkChecks [name]    = mkCheck name
mkChecks (name:ns) = [| $(mkCheck name) >> $(mkChecks ns) |]

You can get fancier if you like, but I simply output the name of the test right before the status. That way when a test fails it’s easy to see which one.

Next we create a very simple module, Unit.hs, to run the tests for us.

{-# OPTIONS_GHC -fno-warn-unused-imports -no-recomp -fth #-}
module Unit where

import Utility -- our TH functions
import Tests -- our test cases

runTests :: IO ()
runTests = $(mkChecks tests)

The GHC options will take a bit of explaining. I’ll get back to why -no-recomp is there when I talk about cabal. The -fth is for template haskell, you’ll need that in Utility.hs also. If you compile with -Wall -Werror then -fno-warn-unused-imports keeps GHC from complaining about importing Tests. You need the import because we splice the test cases in but the unused imports check doesn’t know about what we’re doing with TH.

Alright, at this point all you need to do build and run your tests is:

ghc --make Unit.hs -main-is Unit.runTests -o unit

Followed by

unit

(or use unit.exe if you’re on windows)

Cabal

I went a step further and made things work with Cabal.

To do this, go into Setup.hs and make these changes:

import Distribution.Simple
import System.Cmd
import System.Exit

main = defaultMainWithHooks (defaultUserHooks { runTests = quickCheck } )
  where
  quickCheck _ _ _ _ = do ec <- system $ "ghc --make -odir dist/build -hidir dist/build -idist/build:src src/Unit.hs -main-is Unit.runTests -o unit"
                          case ec of
                            ExitSuccess -> System “unit”
                            _           -> return ec

Here I’m assuming you keep your source code in the “src” directory relative to the .cabal file. Now after you build, you should be able to test with, “runghc Setup.hs test”. I mentioned I’d talk more about that -no-recomp option in Unit.hs. I noticed that whever I compiled my program then compiled Unit.hs everything went smoothly but when I compiled Unit.hs in the normal flow of compiling my program that I would get errors about undefined symbols when I typed “runghc Setup.hs test”. To force ghc to always rebuild Unit.hs you just need to add -no-recomp. Another option would be system “touch src/Unit.hs” right before the ghc line in quickCheck above.

Note: The setup described here matches mine as close as possible without some extra details specific to my project (I have a rule in my cabal file for building a dll. I didn’t show it here, but I’d be happy to send it to you if you need such a thing :). So it’s possible I’ve left out something simple like an import somewhere. So if you try these steps and get stuck let me know.

One of the most common things I hear from my programming buddies is, “I wish I knew more math.” I think I tend to hear this from my friends because when I was an undergrad earning my BS in CS I took my time to also pick up a BS in math. Most of my friends know this and so they tend to ask me questions about math and learning it.

Well guess what? Even with a four year degree in math, I feel the same way. Oh, perhaps I’d say it differently, “I wish I could remember and pickup more math” but it’s the exact same feeling. As programmers, math is very important and we know that even when we’re just writing SQL statements or producing XML transformations.

So how do we learn more of this math? Well, it’s going to take time and commitment and I admit I don’t have it all figured out, yet, but I’ve been spending some brain time on it trying to figure ways to get there.

There are several important ingredients you’ll need, but before I dive into that let me explain some of the ways my learning style changed as I studied math in my undergrad. I consider these changes you might try to bring about in yourself so that you’ll pick up the math more easily.

1. Learn to learn. Simply put, reading it and thinking about it are not enough. As an aside, if learning the math doesn’t feel difficult, you’re probably not actually learning it. To really learn something and expand your mind is hard work and you’ll get tired, frustrated and discouraged. Just remember, your mind is similar to a muscle. You have to exercise it and let it rest and recover. Exercise is hard work, but the benefits are worth it.

2. Definitions are probably the most important thing you’ll ever learn in math. See point 1 for my definition of “learn”. When you really get the definition of something, many theorems just make sense and after you get point 4, proving them is just a matter of explaining to someone why the theorem makes sense to you. Of course not all theorems are this way, and you should definitely try to capture any clever reasoning behind named proofs. These patterns of reasoning will resurface in your later proofs.

3. Write it all out, everytime. Primarily I mean definitions and statements of theorems. Also, think about it while you write it. Stop and pause, think about where you could take short cuts in phrasing the definition of something. Does that change the meaning? Why do you suppose the definition bothers to include unique identity instead of just identity? Are there theorems you’ve learned about this object that would fail to hold?

4. Work the exercises, and write out all the details of the proof, even if the proof is given in the book and you think the omited details are “obvious”. Learning to phrase the “obvious” mathematically is immensly important. Additionally, you may discover something by exploring the “obvious”. Entire branches of mathematics have been discovered by people exploring the “obvious”. See the history of non-Euclidean geometry for background (some info here: http://universe.sonoma.edu/activities/geometry.html).

5. Infinity, sequences and real numbers (aka real analysis), induction, and group theory. When you learn each of these concepts your understanding of programming will actually improve. You’ll see things in new ways. Even things in nature. There’s probably a million other things that you can learn to expand your mind in the same way, but I learned the above list in that order and it changed me and my way of seeing the world. I’m confident it will do the same for you because I witnessed similar changes in friends that I studied with.

Now, on to the things you’ll need to in order to be more successfull in your studies.

6. You need good text books. Text books are not created equally. What makes a text book good is hard to define. Basically, the definitions need to be good and progress nicely. The book needs to start where you are and lead you where you want to go. Some of the theorem and exercises should contain typos and incorrect solutions. This is highly counter intuitive but very important if you want to learn the subject.

Since you’re trying to learn the material, not just absorb it, you’re going to be hand checking the theorem proofs and working the exercises until the logic makes sense.

Here is one possible outcome I’ve experienced several times with flawed exercises: When you come to one that has a flaw you might at first go with it. Then you might work it a bit more and realize you’re not getting it. This stuff is confusing. But then you think, “wait, I made it this far, why is this stuff confusing?” Back to the definition you go. Do you really get the definition? Yeah, I guess so but if that’s the case, then this is really a bad way to put it. Oh wait, it’s not just a bad way, but it should be this way. Oh! I get it, and that theorem over there seems so trivial now…

Another possibility is that you think you have found a typo, but even after “fixing” it, it’s still not quite right. In this case, often you’re wrong and you have to figure it out! Doesn’t this sound familiar? It’s like this, you read it, interpreted it, wrote it down and now it doesn’t work like you wanted and you have to spot the problem and figure out the solution. Oh, I just described debugging something you programmed. Look, learning math can actually improve your programming without teaching you anything specific to the code you’re working on.

One last comment on the text book. I don’t know how to get good text book recommendations. Perhaps amazon reviews are okay, but I want to trust the reviewers and know that they will recognize a good text book before I trust them here. Perhaps it would work to find a quality researcher and look at their books.

7. People to talk to. You need friends that you can talk to about the ideas you’re learning. Now that I don’t have classrooms full of other math undergrads to talk with I don’t know what to do about this aspect. Perhaps I need to go back to school or maybe I can find forums online. I should look into this and let you know what I learn.

8. Subjects that you care about. Ever dreamed of cracking some crypto system? Ever wondered why a Turing machine is capable of computation? What is type inference? How does the four color theorem work? I’m sure you’ve wondered one of these or similar questions. But perhaps you don’t care at all about Fermat’s last theorem. So just to state the obvious, remember to pick something that has a pay off for you emotionally. It fills a curiousity or dream. You’ll need this as motivation when the learning gets hard.

9. Learn time budgeting. The best time budgeting technique I have picked up is this: Take a calendar that gives your week in tabular form. Each day is a column and the days are split into rows about 30 minutes per row. Whenever you have something that you’d normally stick on your TODO list, block out a chunk of time on your calendar. Let’s say you need to go to work, wash the dishes, cook dinner, take out the trash and study your math. Well, you start by blocking out the time for work, then fill in 30 min for chores and an hour to cook and eat dinner. Suddenly you see that you really can’t afford to spend 2 hours with your math book tonight. Maybe you block in 30 min with your book. Even though you want to get through chapter 3 before you crack open your other book you won’t be able to do it this week. But that’s okay, because you’ll be making lots of these appointments with your book and eventually you’ll get through it.

Now if you do this for each day of your week and try to live out the schedule exactly as it’s written you’ll start to feel like a robot and there is a solution to that feeling. I’ll explain with an example. On Tuesday you’re supposed to be cleaning the bath tub at 6pm but you really want to watch a movie (scheduled for Wednesday). So here is the rule: You can change activities on your calendar as long as you follow some law of conservation. In this case, you could swap the days of the activities. Just live up to it. There’s no point in bothering with this sort of time budgeting if you can’t keep the promises you make with your calendar. In fact, you probably won’t get much done of what you mean to.

10. Change your life gradually. The most lasting ways of changing your life generally happen gradually — not over night. So work up from one math text a year to one every 3 months. Start at something reasonable and increase the load as your interest increases. Sink or swim works for some things, but I find it unlikely that it will work here.

I’ve been using Haskell to work with SpreadSheetML. There is a nice XML library called HaXml which comes with a tool to convert DTDs into Haskell code (gives you code for reading, writing and manipulating XML in your schema).

When I hand coded a spreadsheet using the definitions provided by HaXml I found it to be too verbose. Fortunately, dtd2haskell is covered by the GPL. I grabbed the source code and after just a few hours of hacking I had fixed one bug and I added named records to most of the generated datatypes (there is one case that my dtd doesn’t use which I didn’t bother to extend). Now that I have named records I can add constructor functions for all the elements so that optional and default parameters are assumed, meaning you’ll only need to specify the attributes/children that you care about. This should reduce my 1200 line hand coded spreadsheet to probably about 10-15 lines of code.

Next I’ll probably also add functionality so that dtd2haskell generates instance declarations for the “Data” type class ala “Scrap Your Boilerplate“
(this was a suggestion from someone on Haskell-Cafe).
It’s so nice that I’m able to customize my tool to help me.

The moral of the story seem so be that open source tools enable you to help yourself. In this case, I didn’t have to wait for the original authors to add features for me. I was able to step into the source, add what I need and then go back to hacking the important features.

Today I discovered that SpreadSheetML has a very minimalistic requirement for indexing of cells and rows. Whenever cells or rows are adjacent the index of the cell/row to the right/bottom doesn’t need an explicit index attribute. Numbering is assumed to start from 1 if the first row or cell doesn’t give an index. This also works for skipping rows and cells without having to describe empty cells. I wanted to give an example, but I just discovered I don’t know how to quote xml fragments in this blog system yet…

This sounds really great until you find out that you can merge cells. When cells are merged the upper left corner cell is marked with some combination of the attributes, mergedown and mergeacross (probably should have been mergeright). So, if a cell has the attribute mergedown=”1″, then that cell takes up two spaces — one in the row it’s in and one in the row below it. If you try to put anything in the row below it, excel will complain that your spreadsheet is invalid. To get around this you have to use cell indexes to explicitly skip over that column. This means that to correctly generate any row given a sequence of adjacent cells you have to look at all the mergedown attribute in all the cells in the column above your cell. Actually, it gets worse…
Remember I mentioned mergeacross? Well, it turns out that merges can be rectangular regions. To correctly skip over “used” cells from a mergeacross, mergedown combination you’ll need to look at all the cell attributes for cells that are in a row before your row and all the columns upto your column.

Perhaps the moral of the story is not to try to generate a row of adjacent cells alone but to instead store the cells as a grid in memory taking into account merges. The disappointing thing for me is that I wanted to transform database queries into SpreadSheetML using xslt. The xslt would weave in the style information for me. Of course, I wanted to have merged cells in the headers columns of my generated spreadsheets. The number and size of the merged columns depends on the data and quickly I see that this can get tricky.

Oh well…back to the design table.