RLeisti

I’ve created a branch of the Haskell Crypto Library with an implementation of the Twofish cipher. The implementation is mostly based on the Twofish paper.

The code is accessible at http://darcs.ronleisti.com/haskell/crypto.

You can grab it with darcs using:
darcs get http://darcs.ronleisti.com/haskell/crypto crypto

I’ve started writing a couple small applications using the new Visual Studio 2010 Beta 2. I’m specifically looking at the data entity framework and MVC 2, to see what kind of angle Microsoft has taken with these patterns and what they have to offer. Also, I’m using this opportunity to put some more TDD experience under my belt.

So far, I’m fairly happy with the unit testing possiblities that the data entity framework provides. To be sure, this is mostly in comparison with the legacy architectural patterns that I deal with at work; especially having to work without an ORM framework. In fact, we’re currently stuck at Visual Studio 2005; so to me, 2010 is a refreshing leap into the present.

In theory the data entity framework makes it possible to construct and test your application’s logic in a way that doesn’t require a database connection. You can create ‘repository’ classes that imitate a DataContext: with methods for adding objects and providing data access via the IEnumerable interface. In practice though, I’ve run into a few problems with some of the behavioral quirks of the DataContext (quirks which you don’t find in straightforward collections):

• Calling SaveChanges() will throw an exception if there are any open data readers. This could happen, for instance, if you are iterating through the results of a query, and calling SaveChanges() inside that iteration. This isn’t too easy to replicate in your mock objects (you could write your own class implementing IEnumerable which reports on ‘open’ enumerations to your mock SaveChanges() method). Preventing it is fairly simple: either don’t call SaveChanges() while iterating through query results, or stuff the entire query results into a List first, then iterate (but I do like being able to test for these things, instead of having them surprise me later).So, for example (I haven’t tried compiling this), something like this might be generally what we need to do, in order to test for this behavior:

  
  class MockRepository {
    private List _foos;
    private int _numOpenReaders = 0;
  
    IEnumerable Foos {
      get {
        return new DataReaderSimulationEnumerable(_foos,
                                                  () => { _numOpenReaders += 1; },
                                                  () => { _numOpenReaders -= 1; });
      }
    }
  
    public void SaveChanges() {
      if (_numOpenReaders > 0) {
        throw new ApplicationException("Oops!  You can't do this because you've got a reader open.");
      }
    }
  }
  
  class DataReaderSimulatingEnumerable : IEnumerable {
    public DataReaderSimulatingEnumerable(List source, Notification readerOpen, Notification readerClosed) {
      _source = source;
      _readerOpen = readerOpen;
      _readerClosed = readerClosed;
    }
  
    private List _source;
    private Notification _readerOpen;
    private Notification _readerClosed;
  
    public IEnumerator GetEnumerator() {
      if (_readerOpen != null) {
        _readerOpen();
      }
      return new DataReaderSimulatingEnumerator(source.GetEnumerator(), readerClosed);
    }
  
    public delegate void Notification();
  }
  
  class DataReaderSimulatingEnumerator : IEnumerator {
    public DataReaderSimulatingEnumerator(IEnumerator source, Notification notificationHandler) {
      _source = source;
      _notificationHandler = notificationHandler;
    }
  
    public delegate void Notification();
  
    private IEnumerator _source;
    private Notification _notificationHandler;
  
    public bool MoveNext() {
      if (_source.MoveNext()) {
        return true;
      } else {
        if (_notificationHandler != null) {
          _notificationHandler();
        }
        return false;
      }
    }
  
    void Reset() {
      throw new NotSupportedException();
    }
  
    void Dispose() {
      _source.Dispose();
    }
  }
  	

• When you delete an object, it still appears in new queries until you call SaveChanges(). However, the DataContext does know that the object is deleted, and will throw an exception if you try to modify any of its properties. This can be simulated in your mock class by maintaining a separate list of items that have been deleted, and only removing them from the ‘main’ list when SaveChanges() is called.  As for throwing an exception when a property is modified, this would involve creating partial classes for each of your model classes, overriding certain methods in order to simulate this behavior (ugh!)

So, it seems that while there are some challenges, these aren’t insurmountable. I am becoming a fan of Linq; though beyond the SQL-like syntax sugar, it seems very similar to the standard list/sequence operations that you would find in any functional language. And you never know, Microsoft may even work out some of the issues themselves.

Dan and Mandi Butcher got hitched on the 22^nd of August in Simcoe, Ontario. It was a hot day that threatened to break into rain, but the weather co-operated and everyone had a great time.

A view from the front of the church. Parking was interesting, instead of individual parking spots the lot was divided into simple rows. We avoided this potential confusion by parking on the street.

It’s official! Behold Mr and Mrs Butcher.

Dan giving a wave to his admirers.

Truly, a special day.

The newly weds stepping into their wedding car. The burnout was a nice touch.

Reception was held at the Hungarian hall in Delhi.

Well, recently I’ve gotten stuck on problem 10 from projecteuler.net.  The problem is to find the sum of all primes that are less than 2 million. I was trying to generate primes by brute force, along the lines of:

isPrime :: Integer -> [Integer] -> Bool
isPrime x ps = not $ any (\p -> x `mod` p == 0) ps

The isPrime function basically takes a number and a list of pre-calculated primes all less than that number, and tells you if the number is prime (by trying to divide the number by any of the given primes less than it).

Fortunately for me, I took a number theory course in University, so I remembered about something called the Sieve of Eratosthenes. However, the most obvious way of implementing this algorithm is to use an array to keep track of all the numbers that aren’t prime. At my current level of experience with Haskell, I don’t want to start messing with mutable arrays; especially since (I think) that would force me to incorporate the IO monad into my algorithm, and I’d rather find a nice pure functional solution instead.

I looked around a bit on google to see if anyone else had tried to implement this number sieve in Haskell, and I found a few pages that said they did, but in fact only implemented the brute force method.

Then yesterday, I had an idea that I could store all the non-primes in a binary search tree. It wouldn’t be as efficient as an array, but it might just be fast enough to get a solution to the problem anyway. I tried a quick implementation of a naive tree that didn’t work so well. I didn’t feel like trying to figure out red-black trees, so I looked to the Haskell standard library and found Data.Set. Here is what I ended up with:

import qualified Data.Set as Set

primes :: (Integral a) => a -> [a]
primes max = genPrimes 2 Set.empty
    where genPrimes n nps
              | n > max          = []
              | Set.member n nps = genPrimes (n + 1) nps
              | otherwise        = n : (genPrimes (n + 1) (addPrime n (n + n) nps))
          addPrime n x nps
              | x > max   = nps
              | otherwise =
                  let x’   = x + n
                      nps’ = Set.insert x nps
                  in x’ `seq` nps’ `seq` addPrime n x’ nps’

What’s going on in primes is that we’re lazily building a list of prime numbers, while also building a set a of non-primes. The genPrimes function does the work of iterating through all the numbers from 2..max, filtering out the primes based on their not being in the set of non-primes. Every time a prime is encountered, it calls addPrime to add all multiples of it to the set (which are obviously non-prime).

There’s a bit of tricky business in addPrime where I’m using the seq operator to force the tail call to evaluate strict instead of lazy (which I learned how to do from Real World Haskell), because I had encountered a space leak for large values of max.

Unfortunately, I’m sure, to an experienced Haskeller my function probably looks like it was written by a caveman.  Such has been my experience reading through the wonderful book “Real World Haskell”, where I’m constantly amazed at the difference between the and immediately obvious and the elegant solution.  That’s why, to me, Haskell is wonderful language for people that love to learn.

Tags: haskell