Steve's Tech Talk

C# Porting Strategies

This is going to be a quick guide for porting a C# codebase to different platforms.

Wait, what?

Isn’t C# portable on its own?

No – there are two aspects to C# – the language itself and the target platform.  Even though .NET is ostensibly the target, the question is what flavor?  .NET running on a desktop machine or a server?  Windows Mobile?  Silverlight?  Mono?

All of these are going to present some interesting issues on how to create a unified code base that is easy to maintain.

Here’s a challenge: VisualStudo doesn’t support conditional assembly references.  Project files do, but the UI doesn’t this means that in order to work with different assembly references you need to have different projects for each target set of assemblies.  This can be confusing in that the same files will be a part of several different projects.

To start, what you should do is create a project for each target platform and add the appropriate references.  Then you should create a set of conditional compilation symbols that represent your targets as well as symbols that represent certain features you want to expose (or not).

Strategy #1 – Use Preprocessor Symbols

I don’t like doing this – it hurts readability, but it gets you going quickly.  If you find yourself doing something like this:

#if HAS_SERIALIZABLE
[Serializable]
#endif
#if HAS_FORMS
public Form GenerateForm()
#else
public AdaptedForm GenerateForm()
#endif
{
   // ...
}

then you’re doing something wrong – you should make a goal to use the preprocessor symbols as little as possible – and when you do they should be around the largest unit of code that you can – hopefully an entire file.

Strategy #2 – Refactor Classes

You can do this by putting as much platform-neutral functionality into a base class and then have each target platform define the actual concrete class for that platform:

public class WidgetBase {
    public WidgetBase() { }
    public int Weight { get; set; }
}
#if TARGET_SILVERLIGHT
public class Widget : WidgetBase { }
#endif
#if TARGET_DESKTOP
[Serializable]
public class Widget : WidgetBase, IDrawable {
    public Draw(Graphics g) { /*...*/ }
}
#endif

Strategy #3 – Partial Classes

Generally speaking, I don’t like partial classes.  I think that when I start dividing up my classes into partials, that the class is too big and needs to be refactored.  However, you can do some nice things in partial classes.  Partial classes merge all attributes from all classes as well as all interfaces, so we can revisit the sample in the first strategy and clean it up.

// main file
public partial class SomeUIElement
{
   // ... implementation
}
// serializable file
#if HAS_SERIALIZATION
using System.Runtme.Serialization;
[Serializable]
public partial class SomeUIElement
{
  // .... more implementation
}
#endif
// GDI file
#if HAS_GDI
using System.Drawing;
public partial class SomeUIElement
{
    void Draw(Graphics g) { /* ... */ }
    void Draw(Bitmap bm) { /* ... */ }
}
#endif

Strategy #4 – Type Aliasing

This is useful when you have a large establish code base and you are moving it to Silverlight where you discover that that you don’t have System.Drawing.Rectangle (at least not in the same form).

using System;
#if !SILVERLIGHT
using System.Drawing;
#else
using System.Windows;
using Rectangle = System.Windows.Rect;
#endif
namespace MyNameSpace {
   public class MyUIElement {
      public Rectangle CalculateBounds() { /* ... */ }
   }
}

This now lets me use my existing Rectangle definitions as long as Rect is more or less compatible.

 

Strategy #5 – Neutral Interfacing and Abstract Factories

This is standard OOP practice – you define a neutral interface that defines how an object behaves and then use a factory to make the appropriate object.

Solving the Expression Problem with OOP

Yesterday I watched a presentation by Dr. Ralf Lämmel about The Expression Problem.  The problem is, in a nutshell, how do you build an extensible data model and an extensible operation model that meets three goals:

1. Code-level modularization
2. Separate compilation
3. Static type safety

In watching his presentation, I was perturbed by his dismissal of OO approaches to solve this problem.  To my eyes he used strawman arguments by presenting several techniques which don’t work.  The reason that I found this upsetting is that I have worked on many large systems that were built in C that had all of these things.  One of the benefits of working at Adobe in the 1990’s was that I got to work on and look at four different modular extensibility models: PhotoShop, Acrobat, Premiere, and Illustrator.  Each of these presented fairly complicated data models and allowed the addition of extensions that manipulated existing objects, extended them, presented new objects, and new functionality.  All of this was done in a way that was type-safe and had to have modularization and separate compilation.  And while the extension model in PhotoShop was fairly primitive, the Premiere extension model was such that the actual application for Premiere was nothing more than a host for plug-ins and a small amount of code to facilitate communication with an abstract operating system layer.  The first time I saw that, my jaw dropped that the actual application was nearly nothing.

So how is this accomplished?  In the expression problem, you can do this by making a clear separation between your data and your operations.  In fact, it’s a fairly good model to think of the work needed as an orthogonal grid:

	Operations
Data	Eval	PrettyPrint	Compile
Add	EvalAdd	PPAdd	CompileAdd
Sub	EvalSub	PPSub	CompileSub
Mul	EvalMul	PPMul	SompileMul

You see that if I add a new data type, I need to add a set of operations as well.  Similarly, if I add a new operation, I need to define that operation of each existing data type.

The overall operational model is one that I like to think of as Everlasting Gobstopper (or jaw breaker, if you prefer).  Here is what a jawbreaker looks like when you cut it open:

It’s a set of shells layered on top of each other.  This is the model that we’ll work with (it’s actually a little weirder than this), in that any given delivery of code is considered to be a solidified API and extensions that build on this work with ONE particular shipment in order to add to it.  Each new shipment is a new set of extensions that build a new delicious layer on the existing code.  To do otherwise is to create a very hard to support system – it can be done, but there will be runtime checks for inconsistency and contingency plans to handle them.

How can we make this work?  Let’s start with a base Expr class:

public class Expr { }

and then let’s create a repository for them:

public ExprRepository {
   public ExprRepository() { Expressions = new List<ExprPackage>(); } 
   public List<ExprPackage> Expressions { get; private set; }
}

I haven’t defined ExprPackage.  It probably will be little more than an Expr type but it could be a factory method as well.  Now I’m going to define an interface and a class to represent operations:

public interface IVerbPackage { }
public class Verb {
    public Verb() { Implementations = new VerbRespository(); }
    public string Name { get; set; }
    public VerbRepository Implementations { get; private set; }
    public Type ReturnType { get; set; }
}

So the question is, what is a VerbRepository?  A VerbRespository is a collection of objects that contain a Type object for the class EType where EType inherits from Expr and a MethodInfo for a method that has the following signature, where RType is the return type.  I’m not going to define that – I’ll hand wave it away.  It could be a Dictionary mapping EType to an object that contains the MethodInfo – that would be fine.

public RType SomeMethod(Dispatcher d, Verb v, ETtype e);

So now we have some holes to fill in.  I just introduced a Dispatcher object.  What does that do?  Simply, it executes a particular verb for a particular expression type:

public class Dispatcher {
    public object Dispatch(Verb v, Expr e) {
        MethodInfo mi = v.Implemtations.GetMethod(e.Type);
        if (mi == null) { throw new ArgumentException("Incomplete implementation for Verb " + v.Name;); }
        object target = v.Implementations.GetInstance(e.Type);
        object[] args = new object[] { this, v, e };
        // in actuality, this needs to be in a try/catch
        object returnVal = mi.Invoke(target, args);
        return returnVal;
    }
}
        

So now I have code that based on the type of e looks up the appropriate method implementation for the given verb and executes it.

So how do create verbs?  Like this:

public PrettyPrintImpl : IVerbPackage {
    [Verb("PrettyPrint")]
    public string Add(Dispatcher d, Verb v, ExprAdd e)
    {
        string lhs = d.Dispatch(v, e.Left) as string;
        string rhs = d.Dispatch(v, e.Right) as string;
        return lhs + " + " + rhs;
    }    
}

The hosting application looks at all available assemblies and pulls any classes that implement IVerbPackage, then it extracts MethodInfo objects that are decorated with VerbAttribute and uses the string to label the verb (there are other ways to do this).  Now my implentation is type strong.  The only thing I don’t like is the cast – it’s cruft.  By defining the first method that implements a verb named PrettyPrint, I’m defining how all verbs should act.  I should instead define Dispatch like this:

public T Dispatch<T>(Verb v, Expr e) {
    MethodInfo mi = v.Implementations.GetMethod(e.Type);
    if (mi == null) { throw new ArgumentException("..."); }
    object target = v.Implementations.GetInstance(e.Type);
    object[] args = new object[] { this, v, e };
    object returnVal = mi.Invoke(target, args);
    return (T)returnVal;
}

This lets me rewrite PrettyPrint like this:

[Verb("PrettyPrint")]
public string Add(Dispatcher d, Verb b, ExprAdd e)
{
    string lhs = d.Dispatch<string>(v, e.Left);
    string rhc = d.Dispatch<string>(v, e,Right);
    return lhs + " + " + rhs;
}

I’ve moved the cast to a more appropriate place and now I’m honoring the contract.  I will get a runtime error if I use the wrong flavor of Dispatch – sorry, that’s a practical limitation.

So what happens when the world starts?

Some code scans a directory for assemblies and finds all assemblies that have classes that inherit from Expr and classes that implement IVerbPackage.  The system attempts to build the orthogonal collection of Verbs for the given Expr.  When this is complete, the system can now start executing verbs on the data.  What do you do on non-orthogonal Verbs?  There are a number of choices.  The most obvious ones are nothing or throw – I can’t say I like either of these.  Another option might be to allow a method to define default behavior – another method maybe decorated as [VerbDefault(“name”)] and to use this, if it exists, for the verb, otherwise disqualify the Verb.

There are three bad things about this implementation.  The first is that I could easily forget to implement a given Verb for a given Expr.  This is avoidable – imagine that Dispatcher contained in it a method called DefineVerb(Type t, string name, ProgrammingLanguage lang), which when executed generates an entire verb set for a given Expr type t.  This is effectively using the extension system to write your next extension.  Awesome.

The second bad thing is two developers who are in parallel writing new extensions – one writes a new verb, the other writes a new Expr.  Both extensions can’t co-exist because they didn’t know about each other when they were written.  This is effectively applying two new layers onto the gobstopper simultaneously.  Reject one – or either could fix the incomplete implementation.  Having default verb implementations goes a long way to help this problem.  I understand that this is an ongoing problem with people who create complicated Ruby Gems.

The final problem is human error on calling Dispatch.  What if I dispatch on the wrong type?  Fail.  Can’t the compiler catch this?  The better way, I think is to try to code to avoid the problem.  One way is to instead of providing a dispatcher, provide a delegate that does the dispatching and is thus fixed on return type.  The code that scans for verbs would only accept methods of this form:

public ReturnType Method(Dispatcher d, Func<Dispatcher, Verb, Expr, ReturnType> del, Expr e);

And in this, I eliminate the Dispatch method in Dispatcher as I’m passing it in to the function.  Now my prettyprint looks like this:

[Verb("PrettyPrint")]
public string Add(Dispatcher d, Func<Dispatcher, Verb, Expr, string> del, Verb v, AddExpr e)
{
    string lhs = del(d, v, e.Left);
    string rhs = del(d, v, e,Right);
    return lhs + " + " + rhs;
}

And tada, I have compiler/runtime enforced type safety.  Now, where does that Func<> come from?  I write it on the fly. That’s not exactly beginner code, but it’s straight forward to do.

I would like to point out now that for a production system, this extensibility model not sufficient.  Generally speaking the best models operate in terms of published APIs.  Clients of an API request from a host an API by name (or type) and by version.  This allows APIs to exist with legacy versions as well as revisions.  This gives you non-breaking legacy support for (nearly) free.  Also, any good extension model should have the facility to load/unload extensions on the fly.  This requires an event model to allow clients to deal with their APIs going away.  Finally there is a missing tier in the Expression Problem – there is the sense of data and operation, but missing is the notion of meaning.  For example, Add(Expr1, Expr2) is perfectly valid as long as Expr1 and Expr2 are numeric, but what if Expr1 is and array?  A function declaration?  A sequence expression?  An argument list?  There is nothing to handle this well in the model.  Nor is there a coherent generic factory model for constructing expressions.  Hopefully that would be addressed too.

Extensibility is not a new concept in software engineering.  By looking at the tools that are available in modern OOP systems, it is possible to create a solution to the Expression Problem that is compact, type-safe, and readable – all elements of practical engineering.

Using a Proxy Class to Fix F# Protected Access Limitation

In this previous entry, I presented a workaround to F# not having support for protected members.  Upon thinking on it further, I decided that this could nearly be fixed with an adapter class.  The adapter class would be implemented in C# and would override all protected members and call optional/non-optional delegates to perform the actual work.

If you wanted to implement an ImageCommand from dotImage in F#, you would start with a C# class like this:

using System;
using System.Drawing;
using Atalasoft.Imaging;
using Atalasoft.Imaging.ImageProcessing;
using System.Runtime.Serialization;
namespace DelegatedImageCommander
{
    public delegate AtalaImage PerformActualCommandDelegate(AtalaImage source, AtalaImage dest, Rectangle area, ref ImageResults results);
    public abstract class DelegatedImageCommand : ImageCommand
    {
        Func<AtalaImage, AtalaImage> _constructChangedSourceImage, _constructFinalImage;
        Func<ImageResults> _constructImageResults;
        Func<AtalaImage, PixelFormat, AtalaImage> _getChangedPixelFormat;
        PerformActualCommandDelegate _performActualCommand;
        Func<AtalaImage, PixelFormat, PixelFormat[], PixelFormat> _selectBestAlternatePixelFormat, _selectPreferredPixelFormat;
        Action<AtalaImage> _verifyProperties;
        protected DelegatedImageCommand(PerformActualCommandDelegate performActualCommand,
            Action<AtalaImage> verifyProperties,
            Func<AtalaImage, AtalaImage> constructChangedSourceImage,
            Func<AtalaImage, AtalaImage> constructFinalImage,
            Func<ImageResults> constructImageResults,
            Func<AtalaImage, PixelFormat, AtalaImage> getChangedPixelFormat,
            Func<AtalaImage, PixelFormat, PixelFormat[], PixelFormat> selectBestAlternatePixelFormat,
            Func<AtalaImage, PixelFormat, PixelFormat[], PixelFormat> selectPreferredPixelFormat)
        {
            if (performActualCommand == null)
                throw new ArgumentNullException("performActualCommand");
            _performActualCommand = performActualCommand;
            _verifyProperties = verifyProperties;
            _constructChangedSourceImage = constructChangedSourceImage;
            _constructFinalImage = constructFinalImage;
            _constructImageResults = constructImageResults;
            _getChangedPixelFormat = getChangedPixelFormat;
            _selectBestAlternatePixelFormat = selectBestAlternatePixelFormat;
            _selectPreferredPixelFormat = selectPreferredPixelFormat;
        }
        protected DelegatedImageCommand(PerformActualCommandDelegate performActualCommand, Action<AtalaImage> verifyProperties)
            : this(performActualCommand, verifyProperties, null, null, null, null, null, null)
        {
        }
        protected override AtalaImage ConstructChangedSourceImage(AtalaImage image)
        {
            if (_constructChangedSourceImage != null)
                return _constructChangedSourceImage(image);
            return base.ConstructChangedSourceImage(image);
        }
        protected override AtalaImage ConstructFinalImage(AtalaImage image)
        {
            if (_constructFinalImage != null)
                return _constructFinalImage(image);
            return base.ConstructFinalImage(image);
        }
        protected override ImageResults ConstructImageResults()
        {
            if (_constructImageResults != null)
                return _constructImageResults();
            return base.ConstructImageResults();
        }
        protected override AtalaImage GetChangedPixelFormat(AtalaImage sourceImage, PixelFormat newFormat)
        {
            if (_getChangedPixelFormat != null)
                return _getChangedPixelFormat(sourceImage, newFormat);
            return base.GetChangedPixelFormat(sourceImage, newFormat);
        }
        protected override AtalaImage PerformActualCommand(AtalaImage source, AtalaImage dest, Rectangle imageArea, ref ImageResults results)
        {
            return _performActualCommand(source, dest, imageArea, ref results);
        }
        protected override PixelFormat SelectBestAlternatePixelFormat(AtalaImage sourceImage, PixelFormat sourceFormat, PixelFormat[] formats)
        {
            if (_selectBestAlternatePixelFormat != null)
                return _selectBestAlternatePixelFormat(sourceImage, sourceFormat, formats);
            return base.SelectBestAlternatePixelFormat(sourceImage, sourceFormat, formats);
        }
        protected override PixelFormat SelectPreferredPixelFormat(AtalaImage sourceImage, PixelFormat sourceFormat, PixelFormat[] formats)
        {
            if (_selectPreferredPixelFormat != null)
                return _selectPreferredPixelFormat(sourceImage, sourceFormat, formats);
            return base.SelectPreferredPixelFormat(sourceImage, sourceFormat, formats);
        }
        protected override void VerifyProperties(AtalaImage image)
        {
            if (_verifyProperties != null)
                _verifyProperties(image);
        }
    }
}

Then in F#, instead of inheriting from ImageCommand, you would inherit from DelegatedImageCommand and provide a set of delegates to perform the actual work.  In ImageCommand, you can get away with default behavior for everything except PerformActualCommand and you’re good to go.  I provided two constructors: one with all the delegates and one with the most common case.  Now an F# class that inherits from DelegatedImageCommand will present the correct interface to the world.  Almost.

I say almost because ImageCommand is serializable, and as such you are supposed to create a constructor that is protected which takes a SerializationInfo object and a StreamingContext object.  F# doesn’t let you make protected constructors, so this approach won’t work properly.  It turns out that the protected constructor can be public – it is only suggested that it is protected.

However, if you want to do this properly, you would need to define a shell class in C# that has the correct public interface and data/property model and then do the actual work in F#.

Protect Yourself

I’ve been looking at F# to assess how well it plays with the .NET ecosystem and I’ve found a number of blemishes.  Most recently, I found that F# has no equivalent to the C# protected access on members/classes.  Why should we care about protected?

One of my favorite patterns as an author of an API is template pattern.  In this pattern, a base class, typically abstract, defines the way that a process should happen but doesn’t define certain steps.  These steps are left as an exercise to concrete implementations.  The steps, like the steps in sausage making, are meant to stay out of the public eye.

At one point, I refactored the dotImage class ImageCommand to use that pattern.  There are six steps in a typical image command, some optional/default, some not.  Rather than make every command implement every single step on its own, I made a template that handles all this for you in the Apply() method (side note, Apply() is virtual, so if you don’t like it you can replace it).  Most of the templated methods are protected since they need to be visible to subclasses, but shouldn’t be public.  Many, but not all, have reasonable default implementations that handle 80% of all cases.

The problem is that if I implement an image command in F# all this protected methods magically become public.  This is contrary to the language reference, which says:

The access specifier protected is not used in F#, although it is acceptable if you are using types authored in languages that do support protected access. Therefore, if you override a protected method, your method remains accessible only within the class and its descendents.

I have verified that this is false – override a protected member and it magically becomes public.

There is hope in the future – the language reserves the keyword ‘protected’ so I think someone has the intent of putting it in.  Meantime, I’m left holding the bag.  What to do?

One solution is to label things that need to be protected, disassemble the output, run a regular expression to search/replace the accessibility and reassemble.  This is straight forward, but fragile.  I’d use this only for a last-ditch solution.

I’d prefer to use an assembly editor of some kind.  I initially looked at CCI and wrote a simple module visitor to do what I wanted, but my first test broke CCI – it’s just not ready yet.  Instead, I tried out Cecil, part of the Mono project and found it worked fine.  Here is my solution.

First, define a custom attribute for your code base that can be used to label protected members (at present, I have it configured to only be used on methods and constructors – I don’t have much used for protected fields, but I could see protected properties):

open System
[<AttributeUsage(AttributeTargets.Method ||| AttributeTargets.Constructor, AllowMultiple=false, Inherited=true)>]
type AtalaProtectedAttribute() =
    inherit System.Attribute()

Next, create a small C# console application that uses Cecil to apply the change.  Most of the app is error checking, so I’ll just paste in the meat (note: in the CLI, protected is called “family”):

    ModuleDefinition module = ModuleDefinition.ReadModule(sourceFile);
    foreach (TypeDefinition type in module.Types)
    {
        foreach (MethodDefinition method in type.Methods) 
        {
            int attrIndex = attributeIndex(method.CustomAttributes);
            if (attrIndex < 0)
                continue;
            method.CustomAttributes.RemoveAt(attrIndex);
            if (method.IsPublic)
                method.IsPublic = false;
            if (method.IsPrivate)
                method.IsPrivate = false;
            method.IsFamily = true;
        }
    }
// and later
static int attributeIndex(Collection<CustomAttribute> coll)
{
    if (coll == null)
        return -1;
    for (int i = 0; i < coll.Count; i++)
    {
        CustomAttribute attr = coll[i];
        if (attr.AttributeType.Name == "AtalaProtectedAttribute")
            return i;
    }
    return -1;
}

Finally, a call to module.Write() produces an assembly with protected access.

All that remains is the human error of neglecting to put in the [<AtalaProtected>] attribute.  This is easily remedied with a unit test that reflects on all assemblies, finds classes that inherit and override protected members and have mismatched protection.

Limit Your Memoization, Please

Memoization is a great pattern.  We’ve known about it for years outside of functional programming.  It is essentially a combination of a cache and a function pointer.  For some input, x, you look up x in the cache and if it’s there, you return the found value.  If not, you call the function on x, cache the result then return it.  This is especially exciting when you look at F# where working with functions as data is natural.

Referring to Don Syme’s and Matthew Podwysocki’s blogs, you can find some canonical examples of memoization.  Each of these, and the version in Chris Smith’s Programming F# book are based on Dictionary objects and end up looking like this:

    let memoize (f: 'a -> 'b)=

        let cache = new Dictionary<_, _>()

        fun x ->

            let ok, res = cache.TryGetValue(x)

            if ok then res

            else

                let res = f x

                cache.[x] <- res

                res

which is OK as far as demonstrating how memoization works for a CS 200 level class or demonstrating the power of using memoization on expensive functions.  It is, however, a solidly poor choice when dealing with real world problems.

Therefore, I’m going to present a real-world problem that lends itself to memoization and is not something you would ever, ever want to ship to clients using the above pattern.

Since we’re in image processing, we care a lot about how our algorithms perform.  Image processing is a funny domain because things that you might dismiss as cheap blow up when then need to be performing hundreds of millions of times – especially things that involve memory.

Consider this problem – I have a 24 bit continuous color image that I would like represented as an 8 bit paletted image, with a specific palette applied.  To do this, I need a function that given a color gives me the best matching entry in that palette.

Working with Color objects can be a bit of a bummer and having to do abstract Palette look ups will also slow us down, so we’ll build an array of tuples that matches a palette:

    let inline tupledColor (c:Color) = ((int c.B), (int c.G), (int c.R))

   

    let paletteToTupleArray (sourcePalette:Palette) =

        let limit = sourcePalette.Colors-1

        let result:(int*int*int)[] = Array.zeroCreate sourcePalette.Colors

        for i in 0..limit do

            result.[i] <- sourcePalette.GetEntry(i) |> tupledColor

        result

I’m also promoting the byte values of the colors to ints since in .NET bytes and ints are internally 4 bytes *anyway* and the math with be less bogged down.

For matching two colors, we need the distance between them.  For this problem, using Euclidean distance is good enough, but we’ll use the square of the distance to avoid square roots:

    let inline delta a b = a - b


    let inline colorDistanceSquared (b1, g1, r1) (b2, g2, r2) =

        let db = delta b1 b2

        let dg = delta g1 g2

        let dr = delta r1 r2

        db * db + dg * dg + dr * dr

and in this, you can see one of the reasons I like F# – inline functions.  I can write my delta function and use it without the cost of a runtime function call and it makes the color distance function (itself inline) easier to read.

Now we have a function to look up the color.  This is a tail-recursive helper function that returns the closest match.  bestDist and bestIndex are accumulators of the best results so far, i is our current index, color is the color we’re searching for and colors is our palette.  Note that I could eliminate the limit parameter and use colors.Length, but I’d rather use a local than a member.  There’s probably a clever way to do with with fold or find, but I think this is good enough:

    let rec findBestColorLookup bestDist bestIndex i limit (color:int*int*int) (colors:(int*int*int)[]) =

        if i >= limit then bestIndex

        else

            let dist = colorDistanceSquared color colors.[i]

            if dist = 0 then i

            elif dist < bestDist then findBestColorLookup dist i (i + 1) limit color colors

            else findBestColorLookup bestDist bestIndex (i+1) limit color colors

Then our final findBestColor looks like this:

    let findBestColor (b, g, r) (colors:(int*int*int)[]) = findBestColorLookup worstDistance 0 0 colors.Length (b, g, r) colors

Now I can define a type to act as a color matcher for a given palette:

    type colorMatcher (sourcePalette:Palette) =

        let colors = paletteToTupleArray sourcePalette 

        member this.matchColor (b, g, r) =

            findBestColor (b, g, r) colors

which is nice, but will run like a dog, running the palette array.  This is a perfect time to use memoizing to make it faster.  Here’s the problem – in a 24 bit image, you will have a possible 2²⁴ colors to match.  Even a moderate subset of that will be heinously expensive in a memoized version of this function.  The expense comes from the cost of expanding the underlying hashtable every time you overload it.  So let’s extend the memoization pattern to include a clamp to keep this from going berserk:

    let clampedMemoize (f: 'a -> 'b) limit =

        let cache = new Dictionary<_, _>()

        fun x ->

            let ok, res = cache.TryGetValue(x)

            if ok then res

            else

                let res = f x

                if cache.Count < limit then cache.[x] <- res

                res

which now will ignore the cache when you start crossing the limit.  This lets us keep memory use from getting out of control.  Now I can rewrite my color matcher with memoization:

    type colorMatcher (sourcePalette:Palette) =

        let colors = paletteToTupleArray sourcePalette 

        let memoFind = clampedMemoize (fun (b, g, r) -> findBestColor (b, g, r) colors) paletteCacheLimit

        member this.matchColor (b, g, r) =

            memoFind (b, g, r)

Now if I do some refactoring to allow partial function application I can neaten up the code a bit:

    let findBestColor (colors:(int*int*int)[]) (b, g, r) = findBestColorLookup worstDistance 0 0 colors.Length (b, g, r) colors


    type colorMatcher (sourcePalette:Palette) =

        let colors = paletteToTupleArray sourcePalette 

        let memoFind = clampedMemoize (findBestColor colors) paletteCacheLimit

        member this.matchColor (b, g, r) =

            memoFind (b, g, r)

one thing is left to investigate – we’re hashing a tuple.  We don’t have to.  We could rebind those bits into a single int and use that as a key in our dictionary.  This is a way of saying, “hey, I know more about this problem domain than you do, so let me do the hashing.  Here’s a clamped memoizer with an outboard hash:

    let clampedMemoizeWithHasher (f: 'a -> 'b) (h: 'a -> int) limit =

        let cache = new Dictionary<int, _>()

        fun x ->

            let hash = h x

            let ok, res = cache.TryGetValue(hash)

            if ok then res

            else

                let res = f x

                if cache.Count < limit then cache.[hash] <- res

                res

At this point as well, this type of solution might benefit from having the hashed color put into a balanced binary tree instead of hashing.

So the lesson in this (and in many CS problems) is that you need to really understand the specific domain of your problem before applying a sweeping technique like memoization.

The Good Old Days Weren’t That Good

The Computer History Museum has published the source code to MacPaint and Quickdraw.  This is pretty cool – I spent a lot of time hacking the Mac around that time, so it was interesting to me to see how this code was put together.  I haven’t gone through all of it yet, but for grins, I pulled up the assembly source to MacPaint and started looking through the various routines.  Here’s one I found:

;---------------------------------------------------------------------
;
;  PROCEDURE MyGetItem(menu: menuHandle; item: INTEGER; VAR itemString: Str63)
;
;
;  *** just type-coerce VAR Str255 to Str63 ***
;
         JMP      GetItem

To understand this, you need to understand Pascal strings.  Pascal was the API language for the Macintosh, which presented a number of benefits and a number of problems.  Brian Kernighan wrote a pretty good paper about the deficits of Pascal in 1981 covering the language pretty well.  One of those problems centered around strings, which only halfway existed as a usable type in Pascal.  I say halfway usable because there wasn’t really a string type in Pascal, even though you could type them in.

Most implementations of Pascal had some way to get strings into a packed array of char or some other type.  On the Mac, they gave you a few types to work with: Str255, a 256 bytes array with the first byte being a length byte.  Str63, a 64 byte array and a couple others.

Variables of type Str255 are wasteful – especially for menus.  Most menu items (“Save”, “Quit”, “Cut”) are far shorter than 255 characters, but when you declare a Str255, you are saying that you have the full 256 bytes to work with.  Since GetItem is declared as taking a Str255, you can’t pass it anything else.  Bill Atkinson, decided to do a hard cast by writing assembly language glue to pass allow a Str63 to get passed in instead.  While this will work most of the time and probably all the time in the first revision of MacOS, if a menu item exists with more than 63 characters in it, this will fail.  And it will fail by silently overwriting either the stack or the heap.  Both cases are bad.

The cause of this problem is several fold:

1. Bill’s version of Pascal probably didn’t allow casting (which would’ve been unsafe anyway)
2. Pascal strings are awful – certainly worse than C, which are pretty bad
3. The Mac team didn’t insist on a reasonable string extension to Pascal to allow variable length strings (one version of Pascal I used allowed the declaration TYPE Str255 = VARYING[255] OF CHAR
4. Memory resources were tight on MacPaint to require shorter strings

As a side note, in 1988 I wrote a version of MacPaint in C called StevePaint for SunOS.  It handled 256 color images instead of black and white, better text handling, and image convolution (blur, etc).  That code took me a semester with a full course load.  It helped that the Suns I had access to were 68020 based machines running at a much better clip than the original Mac and that the UI was more or less designed for me.  Still, never needing to drop into assembly language was a big win.

Why Software Has Bugs

I’ve been thinking about the causes of bugs in software in the past week.  I reflect on this a lot and as I get older, I try to put habits into place that eliminate bugs before they happen.  As an example, in doing string manipulation in C, I had a nasty habit of writing the null terminator in the wrong place – always off by one on the generous side.  I put into place a habit that eliminated this by effectively proving my code correct through induction as I wrote it.

But these kinds of bugs are the microscopic bugs.  I’m thinking of the more granular and endemic.

The main three causes of larger bugs are:

1. Finite memory
2. Finite storage
3. Finite processing time

I say this because when the straightforward solution for a problem is not so good, it requires us to be clever instead.  And this quote from Brian Kernighan is a pretty good illustration of why that’s not always the best thing:

Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.

Take, for example, color quantization.  This is the task of selecting a good, finite palette of colors to be used in rendering a continuously colored image.  I can describe a straight forward algorithm very concisely:

foreach (pixel in image)
    add the color to a histogram
while size of histogram > desired number of colors
    merge least frequent colors into nearest greater frequencied colors

There we go.  Color quantization in 4 lines of code.  The problem is that in a 24 bit image, there could be up to 16,777,216 (2²⁴) possible colors, and the main chunk of a straightforward histogram will require 67,108,864 bytes, but since we have to merge, we can’t just store the frequency – we’ll need the color too, so that’s 134,217,728 bytes.  So scanning the histogram on the first pass alone will take something on the order of 33M operations (16M reads and 16M compares) – and you want to do this because you want to eliminate all the empty cells.  Then you need to sort the cells on frequency – there’s an n * log n operation, where n is in the millions.

It’s bad.  Really bad.  You could get away with another approach of limiting your histogram to the size of the image – that’s good – you can’t have any more unique colors than you have pixels, but now each time you record a color, you’re going to either have to hash on the color or insertion sort.  The cleverness required just went up.

There is a fairly good way to do quantization called Octree Quantization  (Michael Gervautz, Werner Purgathofer), which uses a sparse tree where each node has up to 8 children and the greatest depth of the tree is 8.  In this case, r, g, and b components are used to navigate a path through the tree by using most to least significant bits in r, g, and b to select a child from a given node.  When the load on the tree gets too high, it gets reduced.  This is all very, very clever and to make it perfomant requires even more cleverness.

I say this because in implementing the algorithm on my test image, which had 16M pixels in it, I found that one particular routine – a very simple one – was getting called 75M times.  This is bane of image processing.  Simple routines that get called an insane number of times.  With some refactoring, I eliminated 2/3 of the cost of that routine.  Ultimately, the running time of the quantization in managed code on a 2.4G machine was 3.3 seconds.  Compare this with the cost of simply scanning the image, which is .374 seconds. 

But each of these refactorings adds complexity and complexity adds bugs.  And the ultimate cause of those bugs is limited resources, because each change in algorithm and each refactoring was necessitated by the problem scope.   Roughly 10% of the cost of quantization is scanning the image and 90% is cleverness.  You shouldn’t be surprised now about why I think that cleverness causes bugs.

So what can we do to avoid the cost of cleverness?

1. Don’t assume you need to be clever a priori
2. Use a language appropriate to the problem domain
3. Use well-debugged, well-tested libraries to do common data structuring
4. Strive to keep your code as clean¹ and as readable as possible
5. Optimize based on measurements not instinct
6. Unit test before and after refactoring

¹by clean, I mean something similar to the adage of always wearing clean underwear because you might have to go to the hospital – if you just refactored and someone else had to pick up you code, would they want to jam spikes into their eyes (or for the clearer thinkers, would they want to jam spikes into your eyes)?

F# Range Specification Mistake

I’ve already mentioned how much I dislike F# for loops.  I ran into an issue in the spec that affects loops as well any language construct that uses the range syntax expr₁ .. expr₂.  The spec for ranges is this:

The default definition of these operators is in Microsoft.FSharp.Core.Operators. The (..) operator generates an IEnumerable<_> for the range of values between the given start (expr₁) and finish (expr₂) values, using an increment of 1 (as given by Microsoft.FSharp.LanguagePrimitives.GenericOne).

This is great – if you use the following code:

let x = [| 0..7 |];;

you get this:

val x : int [] = [|0; 1; 2; 3; 4; 5; 6; 7|]

which is what you’d expect.  If you do this, on the other hand:

let x = [| 7..0 |];;

you get this:

val x : int [] = [||]

Empty array?  Really?  Well, yes – by the spec they say that they will construct an IEnumerable<_> and use an increment of 1.  In reality, they should use an increment of sign(expr₂ – expr₁). This means that if I write the following function:

let f a b =

    for i in a .. b do someOtherFunction i

I will only get predictable results is a < b.  The workaround is to write it this way:

let f a b =

    for i in a .. sign (b – a) .. b do someOtherFunction i

in order to get predictable results.  Note that I do not want to do this:

let f a b =

    for i in (min a b) .. (max a b) do someOtherFunction i

as that will always run low to high and not in the order asked

Range syntax is a nice bit of sugar.  It’s a shame to see it so badly broken.  I imagine that this was brought in from OCAML but the section of the spec (such as it is) that I found doesn’t proscribe the ordering of a range.  I’d be interested in hearing if the F# implementation was accidental or not.  It would certainly lighten the syntax by removing the need for downto in for loops.

Applied F# Symposium Session 2

How to Define Consumable Classes

Fine Points

1. F# is Free, C# is Closed – members in F# are public by default, members in C# are private by default. When in doubt, spell it out.

2. F# wants you to use lots of little static functions. Our customers don’t – they want objects/controls. Follow the template

3. F# has multiple, sometimes conflicting syntaxes for defining things. Sorry.

4. Files in an F# project are not necessarily in alphabetical order; they are in parse/necessity/dependency order. Again, sorry.

Content

Best practice point – here’s how to build a class file

Gross Structure

<namespace declaration>

<open clauses>

<helper modules>

<open clauses>

<class definition(s)>

Example:

namespace Frobozz.lifeform

open System

open System.IO

module internal argutils =

let raiseOnNull s o =

if o = null then raise(ArgumentNullException(s)) else o

open argutils

type FilePath(s:string) =

let _pathStr = raiseOnNull "s" s

let _path = _pathStr.Split([| '/'; '\\' |])

member this.Path with get() = _path

Exercise

1. Define a class called Digit which constructs with a string, its name, and has a read-only property Name and overrides ToString to print its name

2. Define a class called Hand which constructs with an int, the number of digits, and has a property which is a list of Digit, initialized to the digits. Every hand with n digits has n-1 fingers and 1 thumb.

3. Show and tell for abstract life forms, then make your favorite non-mute animal

4. Show and tell for interfaces and mix-in classes

 
namespace Frobozz.lifeform   
open System
open System.IO
open System.Media
open System.Reflection   
module internal utils =
    let raiseOnNull s o =
        if o = null then raise(ArgumentNullException(s))
        else o
    let raiseOnNegative s n =
        if sign n < 0 then raise(ArgumentOutOfRangeException(s))
        else n   
open utils   
type Digit(name:string) =
    let _name = raiseOnNull "name" name
    member this.Name with get() = _name
    override this.ToString() = this.Name   
module internal lifeHelpers =
    let namedDigit (n:int) =
        new Digit(String.Format("finger {0}", n))
    let rec makeDigits n l =
        if n = 0 then l
        elif n = 1 then new Digit "thumb" :: l
        else (namedDigit (n - 1)) :: (makeDigits (n - 1) l)
    let makeDigits1 n =
        if n > 0 then new Digit("thumb") ::  [ for i in 1 .. (n-1) -> (namedDigit i) ]
        else []   
open lifeHelpers   
type Hand(digitCount:int) =
    let _digits = makeDigits digitCount []
    member this.Digits with get() = _digits   
[<AbstractClass>]
type Lifeform() =
    abstract member Vocalize : unit -> unit   
[<AbstractClass>]
type SoundLifeform() =
    inherit Lifeform()
    abstract member GetSoundStream : unit -> Stream
    override this.Vocalize() =
        let stm = this.GetSoundStream() |> raiseOnNull "GetSoundStream"
        let player = new SoundPlayer(stm)
        player.PlaySync()     
type FSharpDuck(assem : Assembly, resName:string) =
    inherit SoundLifeform()
    override this.GetSoundStream() =
        assem.GetManifestResourceStream(resName)     
type IVocal =
    abstract member Vocalize : unit -> unit   
type BetterLifeform() =
    abstract member Metabolize : unit -> unit
    default this.Metabolize() = Console.WriteLine("breathing.")
    member this.CanSpeak with get() = (this :> obj) :? IVocal   
type Slug() =
    inherit BetterLifeform()   
type BetterDuck() =
    inherit BetterLifeform()
    interface IVocal with
        override this.Vocalize() = Console.WriteLine("quack.")
 

F# Symposium Session 1

I’ve been running an F# symposium internally at Atalasoft.  Here is the first session’s notes and the “answers”.

1. Define simple polynomial:

type polynomial =

{ A : double; B : double; C : double; }

How do we evaluate some polynomial p at position x?

How do we get the roots of p?

2. Simple recursive functions – define Member a l

a is a member of a l if and only if

a) The l is not empty

b) a is the same as the front of the l or Member a (everything but the front of l) is true

Show trivial in-built Member f’n

Write Rember a l – Rember returns a new list that l’ such that l’ does not contain any instances of a.

3. Tail recursion – Square roots

Newton’s Method:

Make a guess.

For a certain number of iterations:

Refine the guess (is actually a Taylor series expansion IIRC) in this way:

Write with a for-loop/mutability.

Recast it recursively

4. Hermite polynomials – here is the definition of a Hermite polynomial:

Write Hermite recursively

Write Hermite iteratively

Write Hermite iteratively, tail-recursively

 

module File1   

open System   

type polynomial =
    { A : double; B : double; C : double; }   

let eval p x =
    (p.A * x * x) + (p.B * x) + p.C   

let root p =
    let discriminant = (p.B * p.B) - (4.0 * p.A * p.C)
    if p.A = 0.0 || discriminant < 0.0 then raise(ArgumentOutOfRangeException("p"))
    else
        let twoA = 2.0 * p.A
        let radical = sqrt(discriminant)
        let plusRoot = (-p.B + radical) / twoA
        let minusRoot = (-p.B - radical) / twoA
        (plusRoot, minusRoot)   

let derivative p =
    { A = 0.0; B = p.A * 2.0; C = p.B }   let derivativeAt p x = eval (derivative p) x   

let rec Member a l =
    match l with
    | [] -> false
    | head :: tail -> if a = head then true else Member a tail   let rec Member1 a l =
    List.exists a l   

let rec rember a l =
    match l with
    | [] -> []
    | head :: tail -> if a = head then rember a tail 
                      else head :: rember a tail   

let MutableNewtonSquareRoot S iterations =
    let mutable guess = S / 2.0
    for i = 0 to (iterations-1) do
        guess <- 0.5 * (guess + (S / guess))
    guess   let NewtonSquareRoot S iterations =
    let rec NewtonWorker guess iterations =
        if iterations <= 0 then guess
        else
            let newguess = 0.5 * (guess + (S / guess))
            NewtonWorker newguess (iterations - 1)
    let roughestimate = S / 2.0
    NewtonWorker roughestimate iterations   

let rec hermite1 x n = 
    match n with
    | 0 -> 1.0
    | 1 -> 2.0*x
    | _ -> (2.0*x*(hermite1 x (n-1))) - ((double (n-1))*(hermite1 x (n-2)))   

let hermite2 x n =
    let mutable prev = 0.0
    let mutable curr = if n = 1 then 2.0 * x else 0.0
    for i = 2 to n do
        let newcurr = (2.0 * x * curr) - ((double i) - 1.0) * prev
        prev <- curr
        curr <- newcurr
    curr  

See Ya, AT&T

About a year ago I wrote this blog about how AT&T and HTC teamed up to hate their customers with regards to the Cingular 8525 phone I had.  I had been looking around for a smart phone to replace that one and had decided that I would get a phone running Android, as that OS offered the most options in terms of carriers and interoperability.  There were rumblings and rumors of an AT&T Android phone and the one that had been pre-announced got killed in November.

In the meantime, I waited for my wife’s AT&T contract to expire so we could consider other carriers.  Then AT&T announced the Motorola Backflip, which is underpowered and crippled (Android 1.5, locked-in Yahoo search, locked AT&T apps).  They also announced a Dell made Aero (still no sign of it, three months later).

Neither of us were particularly interested in the iPhone.  I want to do development work for my phone and don’t have the resources to run xcode, so that platform is out of the question.

We decided to switch to Verizon and get HTC Incredibles.  In spite of my earlier experiences with HTC, I’m still giving it a shot – and by all appearances it’s a well-made phone.  The plan is more or less equivalent to my old plan in terms of cost.  The real capper--and I hope both AT&T and Verizon are paying attention--was this: while I was attending the Massachusetts Down Syndrome Congress annual convention in March, 2010, the MDSC gave Verizon a leadership award for its contribution to the organization and Verizon is also sponsoring the Massachusetts buddy walk again in 2010.

My experiences so far:

• It works well as a phone and I’m no longer losing half my calls.  This is a huge plus.  My quality of service with AT&T started out OK but had consistently gotten worse.
• The Google maps integration is done well – the 3D map view is smoother than a Garmin Nuvi, but the voice could be much better.
• The Marketplace for downloading apps is seamless – works great.
• Application management is lousy – slow and poorly thought out – it’s painful to figure out what’s currently running.
• Touchdown from NitroDesk for integration with Outlook is a must have.  It works better and has fewer issues than Microsoft’s own Pocket Outlook did on Windows Mobile.
• Some apps are a little flakey with no good explanation.
• The development tools work OK, but they really need to knock off the sharp edges.  I’m running the Eclipse integration under Ubuntu and it’s hardly seamless.  Debugging integration is off by default when you create a project (really?); bouncing back and forth between debug and DDMS aspects is a pain; writing UI layout with XML is awful.

As a side note, we chose to not get an SMS plan.  The cost was exorbitant.  It was just as bad on AT&T too.  Does it really cost 4x more  than getting an equivalent amount of data from the Hubble telescope? No thanks.  I celebrated not having text messages by having a video call with my wife using fring and showing her what I was having for lunch.  Cellphone carriers should wise up and give away SMS.  Connectivity will be the cash cow, not text messages.

So I've been on Cingluar/AT&T for 8 years, if I recall correctly.  You blew it AT&T - your service got worse, your choices narrowed, your products got worse.

Chasing Your Tail in F#

I don’t like the looping constructs in F#.  They don’t feel as thought out as the rest of the language and they feel more like Pascal looping constructs, which have their own issues.

In C-like languages, a loop looks like this:

for (start-exp; condition; repeated-exp) { /* ... */ }

which in most cases looks like this in practice:

int sum = 0;
for (int i=0; i < arr.Length; i++)
    sum += SomeOperation(arr[i]);

this is an idiomatic expression in C-like languages for “sum the result of a function on an each element of an array”.  In F#, you would probably use a fold instead – but ignoring the specifics of this case, let’s look at the F# equivalent loop:

let mutable sum = 0
for i = 0 to arr.Length do
   sum <- SomeOperation arr.[i]

Terrific.  Except for two things.  First, sum is mutable which is something you want to avoid and second, this loop is wrong.  It has an off-by-one error in the looping construct since F# for-loops starts and ends are inclusive.  This is a Pascal-ism and it works in Pascal, because of the ways that Pascal arrays are declared:

TYPE MyArr = ARRAY[1..10] OF INTEGER;
(* ... *)
VAR I, SUM:INTEGER;
BEGIN
    SUM := 0;
    FOR I := 1 TO 10 DO
        SUM := SUM + SomeOperation(arr[I]);
END;

This works because Pascal arrays are defined in terms of inclusive ranges, not in terms of an overall size.  Since F# uses .NET arrays, the arrays will be defined in terms of an overall size.  Therefore, the main for-loop construct is inappropriate for the language.  I would suggest that F# instead include the following construct:

for i = 0 upto arr.Length do
    sum <- SomeOperation arr.[i]

This mates with the native arrays better and is less likely to induce the off-by-one error.  The actual choice of keyword is unimportant.  The clash in meanings between upto and downto is not lost on me – using ‘until’ would be as good a choice.

Unfortunately, looping constructs in F# do not allow for short circuits.  There is neither break nor continue nor is there a way to return a value early from a loop.  This is because there is no real return value but rather an implicit equivalence of the value of an expression with the value of the function.

So to work around this issue, when I have loops like this, I write them using tail recursion.  I can take the for loop above and write it like this instead:

let rec tailFunc arr i i_end acc =
    if i >= i_end then acc
    else someFunc arr (i + 1) i_end (acc + SomeOperation(arr.[i]))
tailFunc arr 0 arr.Length 0

What I’ve done is broken the loop into its own tail-recursive function.  I put the end case first since it is essentially chaff and should be ignored.  This kind of loop runs very efficiently and consumes nearly no stack space.  This tells me that this is an effective idiom for the language, and I get the benefit of not having to remember to use arr.Length-1, so I don’t get an off-be-one error.

In addition, this construct does lend itself to short-circuiting.  Let’s consider the following C# function:

int ShortCircuitOperation(int[] arr)
{
    int sum = 0;
    for (int i=0; i < arr.Length; i++) {
        int opresult = SomeOperation(arr[i]);
        if (opresult < 0)
           break;
        sum += opresult;
    }
    return sum;
}

This is essentially, sum all results of the operations on an arr up until the the operation returns a negative result.  Writing this in F# tail-recursively becomes this:

let rec ShortCircuitOperation (arr:int[]) i i_end acc =
    if i >= i_end then acc
    let opresult = SomeOperation(arr.[i])
    if opresult < 0 then acc
    else ShortCircuitOperation arr (i + 1) i_end (acc + opresult)
// ...
let answer = ShortCircuitOperation a 0 a.Length 0
    

This function can’t be written with F# for-loops as is (although you could do it with a seq, I suppose).  Again, the important part is not the example itself but the concept: I’m running a loop that is supposed to run some number of times, but may in fact have to stop early and I can’t know that a priori.

Where the rubber hits the road is that I wrote a version of adaptive threshold in F# such that it is pixel-per-pixel identical to our existing adaptive threshold command.  The code contains no for-loops.  Except for image data and public class properties, the data within the code is immutable – there are no explicit side effects.  It does contain 15 tail-recursive functions that perform the various operations.  It runs about 1.5x slower than the equivalent C++ version, but instead of going through pointers to memory and doing pointer juggling, it is pure managed code and never touches a pointer and goes through an abstraction layer to get at pixels.  So even with the pixel memory abstraction, it’s still reasonably performant.

To give you an idea of how this stiches into dotImage, here is a function that computes the minimum and maximum pixel values in an 8-bit gray image:

let rec RowMinMax (row: byte[]) (x:int) (x_end:int) (minval:int) (maxval:int) =
    if x >= x_end then minval,maxval
    else
        let value = (int row.[x])
        RowMinMax row (x + 1) xlimit (min minval value) (max maxval value) 
let rec MinMaxXY (pa:PixelAccessor) (y:int) (y_end:int) (minval:int) (maxval:int) (row:byte[]) =
    if y >= y_end then minval,maxval
    else
        pa.GetReadOnlyScanline(y, row)
        let currmin,currmax = RowMinMax row 0 row.Length minval maxval
        MinMaxXY pa (y + 1) ylimit currmin currmax row
let MinMax (pm:PixelMemory) =
    use pa = pm.AcquirePixelAccessor()
    let row = Array.zeroCreate<byte> pm.RowStride
    MinMaxXY pa 0 pm.Height 255 0 row
// ...
let minval,maxval = MinMax atalaImage.PixelMemory

the resulting code is performant, fairly easy to read and safe.

Some Quick Thoughts on F#

F# is not my first functional language.  I’m looking into it as a possible tool for future work at Atalasoft.  Here are my thoughts so far after writing several hundred lines of F# over roughly two days:

1. I’m writing in it like I write in Scheme, but with a heavy tail-recursive bent
2. I don’t like the way currying creates partial function application by default.  My most common error in writing F# so far is leaving off an argument to a function.  I want an error, but F# gives me a curried function.
3. I don’t like the property syntax – it’s as bad as C++/CLI – why make common tasks so painful?  The obvious syntactic sugar should be “property this.PropertyName get = <body>”
4. I don’t like the modularity/package grouping, but I need to read up on it.

One thing I wrote which I do like quite a bit is a glue function to handle possibly null arguments:

let RaiseOnNull obj (description:string) =
    if obj = null then raise(ArgumentNullException(description)) else obj

which lets you write code using this pattern:

let Foo a b c =
    let _a = RaiseOnNull a "a"
    let _b = RaiseOnNull b "b"
    let _c = RaiseOnNull c "c"

I know that F# wants you to not use null as values, but if you need to interface with the rest of .NET, this is a reality and this lets you handle it gracefully.

Typography in Oberlin

I spent the previous weekend in Oberlin, Ohio for a 25th anniversary reunion of the Oberlin Computer Science department.  The major was created while I was a student there, and I leapt on board.

Over the weekend I had the opportunity, during some transient sunshine, to walk through the town and take some pictures.  While I took other pictures, I kept finding myself taking pictures of typography and found some examples both good and poor.  I don’t claim to be a typographer, but the exposure I had at Adobe left a lasting impression.

First, let’s start with the sign for the Oberlin Inn.

The font for the main sign is Copperplate Bold and the subtext is in Copperplate.  This is a slightly stodgy font that only has uppercase letters in it – this is known as small caps, which means nothing more than the small letters are capitals at a smaller size.  Note that the kerning – the space between letters – is very different in the words ‘Hotel’ and ‘Restaurant’.  Restaurant is closer to default kerning, but slightly tighter to fit.  Hotel is loosened up a lot so that it doesn’t feel completely out of balance.  Copperplate is not a bad choice here as the sign itself is sharp and angular.

 

Here is a sign that shows why typography isn’t something that you can just do with a downloaded font and Word.  So maybe you spotted this font and thought it looked nice and would use it for your logo.  What I’m seeing is something that looks like, but is probably a knockoff of Shelley Std Regular.  It has a similar feel to Shelley, but has a number of sharp edges that are truly horrid when scaled up for signage:

This is the connection between the u and r.  It is present at the joins for every lowercase glyph pair and is unforgiveable.  Script fonts should have a smoothness to them.  This level of discontinuity is anathema to the feel of the font.  Ouch.

This is The Feve, which is a coffee house/bar.  You can see another example of Copperplate, but this time it’s different – the letters are made out of stock steel welded into the letters.  It adds a degree of informality to the sign, which is consistent with the feel of the establishment.  Under the bay window, however, is the following sign:

This is a block of sandstone with carved letters.  I remember seeing a documentary called Final Marks: the Art of the Carved Letter, that centered on John Benson as he carved letters into the East Building of the National Gallery.  So when I saw this, I wondered why someone had gone to the trouble of carving stone and doing it so poorly.  I have to believe that it was intentional that the H and the V are uneven, but the general cutting looked sloppy, the first E being not particularly straight.  I looked for other examples of this logo on the building and found none.  To me, it’s sad that someone committed this to stone but didn’t maintain consistency in design so that this fit in a larger context.  Here is some focus on the layout:

The final thing I’ll point out was outside of Oberlin at the Cleveland Hopkins airport.  Between the C and D concourses I saw a set of giant “paper” airplanes:

The one in the lower left caught my attention in particular.   It was made to look as if it had been folded from newsprint.  I shot a close up and found this:

the artist who created the paper loaded it with lorem ipsum, which is faux Latin used by typographers as meaningless fill used to keep focus on the presentation, rather than the content.  I am no stranger to lorem ipsum, as you can see in a section of the DotImage documentation on OCR region types and PDF layout:

And of course, because I’m funny that way, I try to include pictures of my daughter in the documentation.  Wouldn’t you?

Seek and Ye Shall Find

I was building on some benchmarks on some heavy stream handling code that I wrote.  It’s part of a simple state machine lexer that tokenizes input.  One bottleneck I found was surprising – read on.

The lexer uses one of my favorite patterns: peek.  This uses the ability to look ahead precisely one byte in a stream to help determine the end of a token.  I had an obvious implementation of peek in my scanner:

private int LLPeekChar()
{
    int i = _stream.ReadByte();
    if (i >=0)
        _stream.Seek(-1, SeekOrigin.Current);
    return i;
}

This is straight forward, but I had quite a surprise when I ran a substantial chunk of text through my lexer:

Routine Name	Time	Time with Children	Shared Time	Hit Count
LLPeekChar	1.98	1.98	100.00	473683

Now, most people would think that 2 seconds for 473,683 iterations is not bad.  That’s .004 milliseconds per call.  I wasn’t happy, though – this is not a heavy operation and I knew when I wrote it that I would be unhappy – I already knew that Seek is an expensive operation.  So much so that this writing this line of code in any FileStream.Seek-heavy operation will make a huge difference:

if (postion != _stm.Position)
    _stm.Seek(position, SeekOrigin.Begin);

I’m not making this up – seeking to the same position costs more than catching that case.  I recommend that if you hate two argument seek as much as I do that when you write an extension method to do the most common case, that you write it this way:

public static long Seek(this Stream stm, long position)
{
    if (position == stm.Position)
        return position;
    return stm.Seek(position, SeekOrigin.Begin);
}

I decided to rework this by writing an adapter class on Stream.  This class would adapt a Stream but add the ability to un-get a single byte.  This is not unlike the C Standard IO call ungetc().

What I do is build a Stream subclass that is constructed with a Stream.  This will be a read-only Stream, to keep it simple.

Since most of the code is brief, I’ll put in the entire implementation.  The code uses a single byte buffer (this is easily extended, but I really don’t need or want the overhead of a full stack of byte – exercise left to the reader, and all that).  I also use a magic number to tell if the buffer byte is valid or not.  You could use a bool flag, but again – simple.  The only thing baroque in this implementation is that I keep track of how much to alter the stream Position property.  I could test the buffer and alter it that way, this to me makes the code less error prone, especially if it grows in the future.

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
namespace Atalasoft.StreamTesting
{
    internal class UngetStream : Stream
    {
        const int kInvalidByte = -2;
        Stream _stm;
        long _streamOffset = 0;
        int _b = kInvalidByte;
        public UngetStream(Stream stm)
        {
            _stm = stm;
        }
        public override bool CanRead
        {
            get { return true; }
        }
        public override bool CanWrite
        {
            get { return false; }
        }
        public override int ReadByte()
        {
            if (_b >= 0)
            {
                int val = _b;
                _b = kInvalidByte;
                _streamOffset = 0;
                return val;
            }
            return _stm.ReadByte();
        }
        public override int Read(byte[] buffer, int offset, int count)
        {
            int nRead = 0;
            if (_b >= 0)
            {
                buffer[offset++] = (byte)_b;
                count--;
                _b = kInvalidByte;
                _streamOffset = 0;
                nRead++;
            }
            if (count > 0)
            {
                return nRead + _stm.Read(buffer, offset, count);
            }
            return nRead;
        }
        public override long Seek(long offset, SeekOrigin origin)
        {
            _b = kInvalidByte;
            _streamOffset = 0;
            return _stm.Seek(offset, origin);
        }
        public override long Position
        {
            get
            {
                return _streamOffset + _stm.Position;
            }
            set
            {
                Seek(value, SeekOrigin.Begin);
            }
        }
        public override long Length
        {
            get { return _stm.Length; }
        }
        public void Unget(byte b)
        {
            if (_b >= 0)
                throw new IOException("attempt to unget twice");
            _b = b;
            _streamOffset = -1;
        }
        public override void Write(byte[] buffer, int offset, int count)
        {
            throw new NotImplementedException();
        }
        public override void SetLength(long value)
        {
            throw new NotImplementedException();
        }
        public override void Flush()
        {
            throw new NotImplementedException();
        }
        public override bool CanSeek
        {
            get { return true; }
        }
    }
}

This is just a two-state entity: ungotten byte pending or not pending.  So my implementation of LLPeekChar changes to this:

private int LLPeekChar()
{
    int i = _stream.ReadByte();
    if (i >= 0)
        _stream.Unget((byte)i);
    return i;
}

Now when I measure the performance, I get the following result:

Routine Name	Time	Time with Children	Shared Time	Hit Count
LLPeekChar	0.01	0.03	43.92	473683

The performance is now 66x faster if you include the performance of Unget.  More importantly, a 2 second hit in the total time running this app vanishes into the realm of imperceptible, as it should.  The total time per iteration is now 6.3 x 10-5 milliseconds or 63 nanoseconds.  I can live with that.  Can you?

As a final note, I did not preemptively optimize this code.  I did a full day of tests resulting in me doing some heavy refactoring – I had a routine that was taking 14 seconds of my total runtime which is now also taking 0.03 seconds.  When I was done with everything else significant within my control, LLPeekChar was the highest time thief and this type of optimization is clean and simple.