Saturday, April 30, 2011

Graduation day

Graduation Day

So, 32 years after taking Part III of the Maths Tripos, I've finally received a degree for it, the MMath, the most junior of the three Masters degrees I hold from Cambridge.

With this batch of retrospective degrees, my old college -- Emmanuel -- wanted to make big celebration of it, so as well as going to be admitted to the degree in person, it was an occasion to take up, for the very first time, my MA dining rights. And with such a retrospective grant there were people ranging from retirees to those who had still to take the MA -- but comparatively few who had actually done much mathematical for long after Part III! Stranger still to see some people for the first time in half a lifetime or more -- "Did I used to supervise you?"

The weather was bright and rather breezy, though the Chapel Court, where the photo was taken (if only I'd noticed I'd still not untucked the bands from under the hood), was quite still, so while waiting for the reception before lunch we waited in the shade in New Court -- admiring the roses and irises already blooming in the sheltered and sunny parts. And it was at that point that I realised that the stitching had failed down the side of both of my new pair of shoes...

There was discreet disabled access into the Old Library for the drinks, and then, in Hall, Karen was seated at the end of one table, avoiding any problems with the benches.

After lunch we separated as I went to get placed into the correct order in the crocodile, have the ceremony rehearsed, and then marched to the Senate House. Once inside it was possible to discreetly dab at the perspiration from a brisk walk in the sun in all the gear -- graduation days are usually either hot or wet -- while waiting our turn.

After having been processed, without tripping over my gown, or losing bits of shoe, time to go out onto the lawn, get some professional photos, chat with other people I knew also getting the MMath, before heading off, handing back the hood and gown (Karen was wearing our joint MA gown, as a Member of the University attending a Congregation), and then, at last, taking off the shoes that were just about holding upper and soles together, to go barefoot back to the car.

After a short pause to recover, I then cycled back into town for Hall dominated by newly minted MMath graduates; a very pleasant meal followed by cheese, fruit and chocolates with coffee port and Madeira in the parlour, all with a great deal of reminiscence.

And then, about half past ten, back on the bike to cycle back home in the pleasantly cool evening, and with surprisingly little traffic on any of the roads.

Friday, April 15, 2011

Applying IEnumerable to chunked IEnumerable in F# -- Cipher Feedback mode

Having developed the supporting infrastructure to pull data from any IEnumerable into a sequence fixed length buckets, we can now apply it to some practical use. One such is to perform encryption of an input byte sequence in a block-cipher feeback (CFB) mode.

CFB mode is so simple, it almost feels like cheating. Given an initialization vector (IV) -- an arbitrary block of bytes -- as the 0-th ciphertext block, the iterative definition is that the n-th ciphertext block is the encrypted value of the n-1-th block XOR'd with the n-th plaintext block; and by the symmetry of XOR, the n-th plaintext block is recovered from the n-th ciphertext block by the same XOR.

So, let's implement it, and do a simple test that we can easily work out the cipherstream for -- and doesn't actually involve real encryption. So let's take 128-bit blocks, all zeros for the IV, and the identity transformation for our "encryption", and have the integers 0 to 41 as input.

The first ciphertext block will be all zeroes (IV encrypted) XOR'd with 0-15, i.e. 0-15. That XORs with 16-31 to give a second block of all 16s; the final block is 32-41 XORd with 16s, i.e. 48-57.

So, armed with expectations we can write the implementation with appropriate self-test code, thus --

where I've renamed the previous private Ratchet class to the public StreamingSequence type -- a more self-explanatory name for possible re-users; and exposed the Dispose method of the constant (reference, mutable internal state) IEnumerator for end-of-enumeration use.

Here, Seq.collect is being used to flatten the sequence after the block-level operation has been done.

CFB mode is so simple that -- having already done the hard work of breaking any sequence into blocks -- the only thing that stopped the test running through first time was forgetting to re-initialize the CFB operation for the decryption pass.


Actually, the decryption operation shouldn't be working -- but somehow it does, even when I push in random input, and replace the identity encryption operation with a one-way hash! Something weird is going on here.

Wednesday, April 13, 2011

F# under the covers XIII -- Sequence expressions

After more than a year since the previous instalment...

A C# method that returns an enumerator via yield return generates a synthetic class that looks like this:

where I omit unimportant detail based on the particular enumeration, but draw attention to how the other IEnumerator methods are implemented.

The F# result from a sequence expression is very different, with an explicit close and dispose:

and in GeneratedSequenceBase we have

The Close method renders the enumeration non-functional, though the closed enumerator does not throw, it simply yields no more. That the resulting sequence has an active Dispose behaviour, unlike the C# case, explains why in the Window example I needed to add the Controlled wrapper to block that, so that the Stream based enumeration written as a sequence expression would draw more than one tranche before stopping.

By contrast, you don't need the Controlled wrapper for windowing the BCL derived array-as-enumerator; presumably that has a no-op Dispose.

Tuesday, April 12, 2011

Generalized IEnumerable to chunked IEnumerable in F#

F# sequence expressions, under the covers, are complicated beasts; for the purposes of today's exercise, the factor of interest is that they Dispose() internal enumerators aggressively, unlike in the C# case, so the simple Ratchet wrapper isn't enough by itself. So, with some refactoring, we get

Note that this version closes the stream after the iteration completes -- we could leave the management of the stream entirely outside the iterator if we wished. Since we are re-using our Enumerator instance, we only have the one left for garbage collection, so suppressing the disposal doesn't litter too badly.

Overall, if you're in the simple use-case of pulling chunks out of a file in order, the earlier version of the system will suffice.


Edit 1-May-11 : Comparing with 2#4u's Seq.breakBy I get on my laptop

  • Real: 00:00:03.948, CPU: 00:00:03.946 for Seq.breakByV1
  • Real: 00:00:00.345, CPU: 00:00:00.374 for Seq.breakByV2
  • Real: 00:00:00.910, CPU: 00:00:00.904 for Chunk.Window

making the functional Chunk.Window implementation about 2.4 times slower than the faster -- but with more internal mutability -- of the the two.

Generalized IEnumerable to chunked IEnumerable

As noted in the comments to the previous post, if you're not using the Window on an Enumerable that maintains its own internal state (so that the different IEnumerator yielded up each time will always be at the start of the iteration), it will loop forever. So if you're not using the two in conjunction for the purpose of "read a file in chunks for e.g. passing over a network" or similar, you want this variant:

where the Ratchet type ensures that the same IEnumerator instance is yielded up each time -- at this point you have to be rather Jesuitical about what is immutable anyway, the sequence that returns you different mutable objects or the one that returns you the same object you may already have mutated...

F# is less convenient for this one, though :(

Saturday, April 09, 2011

App.config or app.exe.config? Open Question.

Another thing that caught me on W2k3, 64-bit, recently, is that on some, but not all, systems if I have an application appname.exe which is C#, .net 3.5 sp1, compiled in AnyCPU mode, but installed to Program Files (x86), if you get the configuration file path by

var path = ConfigurationManager.OpenExeConfiguration(ConfigurationUserLevel.None).FilePath

it may report appname.config, as opposed to the more usual appname.exe.config as the file name.

And when that happens, it is not joking -- if your installer puts a file at appname.exe.config on such a system, your program will not read it. If you manually move the file to appname.config and restart the application, all will be well.

The internet hasn't been very forthcoming in either cause or remedy -- I did find several copies of a similar issue for 32-bit apps on Vista x64, but no resolution.

There's a similar bug report against .net 3.5 -- but by observation the issue only happens in a minority of cases. The only difference I've spotted between two machines where one shows the bug and the other doesn't is that the bug shows in the one with .net 3.0 and 3.5 sp1 not fully patched up to date -- but the patches don't touch any of the libraries that are likely to be involved (System.Configuration and dependencies).

More than you wanted to know about sc.exe and service isolation in Windows 2k3 SP2

At the level of Win2k3 SP2 unpatched, sc.exe did not support the sidtype parameter for setting a per-service SID. If you issue

sc.exe sidtype MyService Unrestricted

it spits out help text, then pauses for user input

Would you like to see help for the QUERY and QUERYEX commands? [ y | n ]:

At patch MS09-012/KB959454 (or maybe KB956572), if not before, sc.exe was upgraded to interpret this parameter. However...

If on 64-bit Win 2k3 with that patch, you run the 32-bit -- Program Files (x86) -- version, that will accept the sidtype parameter and do nothing, at least on the various systems I've tested on.

Friday, April 08, 2011

Stream to IEnumerable; IEnumerable to chunked IEnumerable

I may have missed these in F#, and they don't seem at all obvious in C# standard libraries. A couple of handy functions/extension methods with simple tests using the Should.Fluent assertion library.

In F#:

In C#:

Wednesday, April 06, 2011

Q1 in books

More fiction reading than I usually do these days, mainly from the grotty weather and having spotted a bunch of titles of interest to add to the Christmas list:

The Quantum Thief by Hannu Rajaniemi

Somewhat reminiscent of early Roger Zelazny -- definitely not the Egan-esque fare suggested by other reviews -- as if Zelazny had been handed Schroeder's Lady of Mazes and a genre trope update for the next 40-odd years when he was starting to write Today We Choose Faces.

Good, not great.

Kraken by China Miéville

After The City and the City, doing yet another magical London seems rather a return to the formulaic. At least he resisted -- given the title and the main character's name -- doing any "Billy the Squid" jokes.

Only pedestrian by comparison with his other works.

The Quiet War/Gardens of the Sun by Paul McAuley

You just have to take the next couple of hundred years future history in this set-up as a given, to provide the backdrop for a high-tech, solar-system spanning tale of Byzantine politics, interspersed with travelogue, the latter possibly becoming a bit repetitive each time we are shown a new piece of airless real-estate.

The ending is fortunately not telegraphed -- whether the not-so-bad guys or the greasy-pole climbers will win out is finely balanced almost all the way.

Wayland's Principia by Richard Garfinkle

This time, he takes on the old staple of First Contact, weaving the alien into territory more usually seen in myth -- it's all about its construction of aliens and where the not-human becomes a monster, and how the gulf might be bridged.

As such it's not set up as something that can have a tidy end, but rather fades out into the future, the narrative sort of pulling back and speeding up in the last few pages, until it rather petered out in the end. A good and interesting book, but not, I feel, his best work.

Full Spring

After several weeks where the weather has been generally miserable -- at best leaden skies and wind, though not so bad as to stop me putting in a a few days of cycling to work -- and unexpected fire-fighting at work has been sapping my energies, today was, after a dull start, full of promise of summer. Let's hope it doesn't turn into one of those years where Q2 is put on back-to-front.

In the garden, the forsythia is finishing, the earliest tulips have finished, but the daffs, grape hyacinths and main tulips are in full flower; while the primroses carry on. And a fair number of new plants from last year failed to overwinter -- one of the lavenders, most of the geraniums, despite the latter being in a notionally frost-free greenhouse.

Still, the weather was mild enough weekend before last to take the surviving plants out, and fumigate the greenhouse; and I could then use the space to dry out the lawn weed-and-feed that had gotten damp in the shed over the winter. So the lawn dressing belatedly happened last weekend, a couple of weeks later than usual. And now the first of the orders of plants arrived, so there are tomatoes in pots, and chilis and overwintered perpetual spinach in the greenhouse; with salad leaves and basil planted as seeds.

Out in the rest of the garden, the bed for annuals has been dug, raked & weeded, so is ready for scattering seed, sunflowers are in a seed-tray, waiting to germinate, and the green bin full to the brim again, with over a week to the next collection -- showing how suddenly I have to make up for lost time (some years gardening started in mid-February, so I'm at least a month behind, plus having still to catch up from the abruptly truncated autumn).

Using LINQ/Extension methods with IronPython 2.7's clr.ImportExtensions method

Woefully underdocumented on the internet, I worked this one out by analogy to the IronRuby using_clr_extensions method: