Atalasoft Community

F# Discoveries This Week 09/03/2010

RickM — Fri, 03 Sep 2010 22:12:19 GMT

One of the greatest things about running this blog, other than having a structured way to read all of the F# community content, is that I’ve been able to watch the community grow in a very concrete way. Looking back to a year ago there was only six posts on F# over the course of a week, now we have well over twenty. It’s truly amazing to see.

Now, on to the links.

Audio and Video

Dr. Ralf Lämmel's C9 Lectures: Advanced Functional Programming - Type Classes

“In this second lecture in the series, Ralf digs into Type Classes, which are type system constructs that were originally introduced to provide a form of ad hoc polymorphism (i.e., an advanced form of overloading).”

Rick Minerich's Functional Language Paradigms with F#

“I've got great news. F# is here and is poised to increase your productivity and reduce your suffering.”

Peter Sestoft's Teaching programming language concepts with F#

“Peter introduces the curriculum, lecture plan and lecture notes for the course "Programs as data" that uses the functional programming concepts in F# to teach students language concepts and implementation details.”

Tools

Essential F# | Refcardz

“This DZone Refcard will lead you through the basic essentials so that you can quickly move on to using this Functional Programming Language for creating some mind-bending code.”

fsxplat - Released: FSharp packages 1.2

“F# packages and samples for use across platforms”

Phillip Trelford's TickSpec: An F# BDD Framework

“Right now TickSpec is intended as a lightweight framework to get you started with BDD using F#. It is standards based, supporting a subset of the Gherkin language, so should be easy to change to another Gherkin based framework like Cucumber, SpecFlow or StorEvil.”

General

Vladimir Matveev's F#: Building compiler from sources.

“Of course, compiling them sources and observing all internal compiler activities, so to say “in action’.”

Ashley Feniello's Fixing Decades-old Bugs in the HP-35

“To make an assembler, I just parse with a series of regular expressions. F#’s active patterns came in super handy for this! In fact, the assembler turned out to be fewer lines of code than the disassembler.”

Ashley Feniello's Microcode-level HP-35 Emulator (in JavaScript!)

“I had the (silly) idea of building a JavaScript-based emulator. Looking at Peter Monta’s Python-based disassembler and his object code listing, it looked simple enough to automatically generate script from David Cochran’s original bits. I wrote my own little straight forward 100-line disassembler in F#, producting an array of JavaScript functions”

Brian McNamara's F# for puzzles (Morse code decoder)

“The idea is simple; the computer works out all the possibilities for the next 3 letters, and then the human selects which prefixes “look promising” to investigate further.”

Neil Carrier's TechNeilogy: Fuzzy Logic F# Reference Module: Fuzzy0

“Below is the fuzzy logic reference code for module Fuzzy0. Tomorrow I’ll post an example of its use that explores some extensions of earlier techniques.”

Yin Zhu's F# and Data Mining: WekaSharp: Tutorial for using Weka in F#/.Net

“The minimal wrapper in F# for Weka.”

Daniel Markham's Structuring Larger F# Functional Projects

“So here's a suggested structure outline for those larger functional projects”

Ade Miller's F# Samples for Parallel Programming with Microsoft .NET

“We’ve been working with the F# Team to get the samples for Parallel Programming with Microsoft .NET ported to F#.”

Neil Carrier's TechNeilogy: F#, Fuzzy Logic, WPF, and Tomatoes!

“This is my 100th blog post, and to celebrate, I’m pulling out all the stops. This example will combine F#, fuzzy logic, WPF, and tomatoes!”

Neil Carrier's TechNeilogy: Conjunctive Fuzzy Logic Rules in F#

“It shows how to make multipart conjunctive rules by storing the input sets in a list and using the “min” operator to combine the results into a truncation height. To do this, it adds vector versions of the fire and fire all functions.”

Justin Angel's Windows Phone 7 supports VB.Net and F#

“In this article we’ll review Windows Phone 7 support for the Visual Basic .Net and F# programming languages. Our goal is to demonstrate that Windows Phone 7 can indeed support F# and VisualBasic.Net code libraries and user controls.”

F# Artificial Intelligence Library Tutorial

“This step-by-step tutorial describes how to use the library in fsx script and C# project.”

Chris Marinos's 5 Reasons to use F# Interactive in Visual Studio 2010

“I find that I use F# Interactive more for performance analysis, learning F#, and verifying Base Class Library behavior than for spiking or scripting.”

Community

Stack Overflow - Calling F# (.Net dll) code from php

“Yes you can, by using PHP COM class but it works only on Windows version of PHP5+ and needs no separate installation.”

Stack Overflow - Scrap Your Boilerplate in f#

“I've used the Scrap Your Boilerplate and Uniplate libraries in the Haskell programming language, and I would find that form of generic programming over discriminated unions to be really useful. Is there an equivalent library in the f# programming language?”

Stack Overflow - Path to Become a Better F# Programmer

“What should be my steps from now on to become a better/professional F# programmer?”

Teaching and Basics

Bill Morrissey's Learning F# for C# developers: Scope, Workflow and Lists

“This post is part two of a series of posts looking at syntactical examples of F# and C#. This post will supply you with easy to understand F# coding examples.”

Anders Hesselbom's Type inference in F#

“I have recently been to a short F# presentation at HiQ in Arboga. One of the things that got mentioned was type inference.”

Rey Dacoco's WebBrowser control (Visual F# Windows Forms Application)

“WebBrowser control is a control used to display a web page or web document. To create a WebBrowser control in F#, use the following syntax:”

F# Discoveries This Week 08/27/2010

RickM — Sat, 28 Aug 2010 00:04:06 GMT

I’m back again with another edition of F# Discoveries this Week. The most exciting announcement this week is the new F# August 2010 CTP which brings with it the ability to build your own VS2010 F# Express Edition with Visual Studio Shell and the prospect of building F# applications on Windows Phone 7. Be sure to check out Daniel Mohl’s Windows Phone 7 template before getting started.

News and Upcoming Talks

F# (August 2010 CTP)

Announcing the F# 2.0 Standalone Tools Update

A standing invitation to F# users to "get in touch"

Don Syme lecturing at the F#unctional Londoners Meetup (9/9)

Tools and Libraries

WekaSharp: An F# wrapper for Weka (Yin Zhu)

F# and C# Win Phone List Template (Silverlight) (Daniel Mohl)

fsai Release FSharp AI library 1.10.0 (Lukáš Kouřil)

RockScroll: my new favourite Visual Studio Add-In (Kean Walmsley)

Video, Audio and Slides

Slides and samples from F# talk in Manchester (Oliver Sturm)

F# Intro Talk at NextGenUG in So’ton (Phillip Trelford)

Slides from Combinators, DSLs, HTML, and F# (Robert Pickering)

Busy .NET Developer’s Guide to F#: Basics (Ted Neward)

Technical Articles

iTunes via F# Interactive (Cameron Taggart)

F# for puzzles (Morse code decoder) (Brian McNamara)

Extracting elements from Win32 resource files (Luis Diego Fallas)

A variation on Matt Moloney's "Memento" pattern (Don Syme)

Bound Variables in F#: What Reflection Reveals (Neil Carrier)

Getting F# Running on a Continuous Integration Server (Ade Miller)

How F#'s async really works? (George Cullen)

Segment Tree in F# (Neil Carrier)

Bound Variables in F#: What Reflection Reveals (Neil Carrier)

Fuzzy Logic Experiments in F# (Neil Carrier)

Fuzzy Logic in F#, Example 1 (Neil Carrier)

Fuzzy Logic in F#, Now More Functional! (Neil Carrier)

F# “fun” with Windows Phone 7 (Fahad)

Getting started with Windows Phone in F# (Senthil Kumar)

Euler Problem 10 (Mark Pearl)

Euler Problem 16 (Mark Pearl)

Project Euler Problem 9 in F# (Stefano Ricciardi)

Project Euler Problem 8 in F# (Stefano Ricciardi)

Project Euler Problem 6 and 7 in F# (Stefano Ricciardi)

Enumerable.Skip vs Seq.skip (Mauricio Scheffer)

Getting Started and Evangelism Articles

Putting the fun in functional programming (Daniel Markham)

Back to school : Getting to know F# (Mehfuz Hossain)

Learning F# by writing C# (Alan Hemmings)

F# - sharper than C# (Josh Reuben)

Learning F# for C# developers (Bill Morrissey)

F# Community

Ars Technica - What do you think of F# ?

SO - How to merge sorted sequences in F#.

SO - Which to use, C# or F#? In this "real world" case

hubFS: F# Databse Application Samples & Articles

hubFS: MailboxProcessor.TryScan paradigm

C# Porting Strategies

Steve Hawley — Wed, 25 Aug 2010 15:24:33 GMT

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.

F# Discoveries This Week 08/15/2010

RickM — Mon, 16 Aug 2010 18:38:05 GMT

Tons of great links along with a brand new less cluttered format today. Let me know what you think on twitter.

News / Talks

Talbott Crowell at San Fancisco Bay Area F# Users Group (8/16)

Don Syme at the Community for F# Online (8/17)

Luke Hoban will be giving a F# keynote at CUFP (10/2)

Joel Pobar "Smart Software with F#" at JAOO (10/6)

Podcasts / Screencasts / Videos

Perspectives on Clojure and F# (with Rich Hickey and Joe Pamer) (Joey deVilla)

Advanced Functional Programming - The Expression Problem (Dr. Ralf Lämmel)

The Language Matters on the Software Engineering Productivity Podcast (Rick Minerich)

Articles

Undo / Redo using the Memento Pattern and Command Pattern in F# (Matt Moloney)

A variation on Matt Moloney's Undo/Redo "Memento" pattern (Don Syme)

Hindley Milner Type Inference Sample Implementation (Edmondo Pentangelo)

INotifyPropertyChanged strikes back (Vladimir Matveev)

WebSharper, part 2: WebExcel (Vladimir Matveev)

OOP Virtualization vs. F# Discriminated Unions (Neil Carrier)

Segment Tree in F# (Neil Carrier)

A F# Silverlight Template (Daniel Mohl)

Reading F# Projects, Part I: The Common Knowledge (Yin Zhu)

Reading F# Projects, Part II: F# Set (Yin Zhu)

Reading F# Projects, Part III: The F# math providers. (Yin Zhu)

Query Zune Music Collection with F# (Cameron Taggart)

How to merge sorted sequences in F# - Stack Overflow (Neil Carrier)

Combining memoization and tail-recursion – Stack Overflow (Ronald Wildenberg)

"I think F# is very cool" - Rich Hickey (Flying Frog Consultancy Ltd.)

F# – Euler Problem 10 (Mark Pearl)

Seq.unfold (Bohdan Szymanik)

Back to school : Getting to know F# - Mehfuz's WebLog (mehfuzh)

Slides from Combinators, DSLs, HTML, and F# (Robert Pickering)

Steve's Tech Talk : Using a Proxy Class to Fix F# Protected Access ... (Steve Hawley)

Tools

FastSharp 2.0 (Matt Manela)

NDjango 0.9.8 (Michael Feingold)

F# Project Extender 0.9.3 (Michael Feingold)

Quantifa: F# open-source project for quantitative finance and risk management (Don Syme)

VsVim (Jared Parsons)

Solving the Expression Problem with OOP

Steve Hawley — Thu, 12 Aug 2010 14:03:48 GMT

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:

Code-level modularization
Separate compilation
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

Steve Hawley — Tue, 10 Aug 2010 15:11:41 GMT

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#.

F# Discoveries This Week 08/08/2010

RickM — Sun, 08 Aug 2010 18:57:45 GMT

So many links, all well worth your time. I know one thing I won’t be missing is Don Syme’s online talk at C4FSharp on 8/17. It’s great to be part of a language community in which the founder interacts in such a direct way.

News

Draft F# Component Design Guidelines now Available (pdf)

Don Syme will be speaking online for the Community for F# on 8/17

I’ll be speaking at the NYC ALT.NET User Group on 8/25

Kevin Hazzard’s Slides from DevConnections are up

Howard Mansell will present Eden: (An F#/WPF framework for building GUI tools) at CUFP

F# is now at 93% on langref, only 1% behind scala. (Great Going!)

PexForFun.com now has puzzles for F#

FSharp Cross Platform Packages and Samples 1.1 Released

Audio/Video

Jon Harrop at the London F-Sharp User Group: QR Decomposition

This lecture takes the audience from a tiny numerically-robust implementation of a common linear algebra algorithm through several stages of optimization, culminating in a high-performance solution that easily outperforms Intel’s Math Kernel Library. The algorithm studied is QR decomposition, which is commonly used for linear least squares best fit.

F# Articles

Adam Granicz’s Expert F# 2.0 – what’s new?

There comes a time when you just have to stop working for a minute and take a few moments to enjoy the fruits of your hard labor. For me, one of these moments lately came when I received the author copies of our book, Expert F# 2.0

Daniel Mohl’s F# Templates Now On Visual Studio Gallery

As Don Syme mentioned in a recent blog post, I've been working to get the five F# templates that have been announced on this blog up on Visual Studio Gallery. I'm happy to say that all are now available.

Vagif Abilov’s Mock framework challenges in F#

So far I only tried very basic mocking described in the first post of Richard’s series: faking return value. As I expected, even such a simple operation became a challenge when executed from F# code. I managed to make tests work only for two and half frameworks.

Mauricio Scheffer’s Figment: a web DSL for F#

As I said, this is very much work in progress, and there's still a lot to do. I intend to make it fully open source when I finish writing my thesis.

Neil Carrier’s Segment Tree in F#

Suffice to say that a segment tree stores a group of intervals on an ordered set, in such a way that all the intervals containing a given value can be efficiently located. Such a query is sometimes called a “stabbing query,” because it’s like sticking a spear through the data and seeing which entries get stabbed.

Neil Carrier’s F# Sequence Lazy Evaluation Gotchas

Today’s post will be old news to experienced F# programmers. Actually, it’s old news to me, relative newcomer that I am. However, it’s one of those things I tend to forget until it jumps up to bite me, as it did today.

Edgar Sanchez’s F#, the ACM, and the SEC

And it is this last recommendation on DSLs that carries interesting news for F# because at the end of page 6 it states “Experience seems to show that higher-order programming languages such as F# provide a particularly good basis for domain-specific languages.

Jon Harrop’s Pure F# now only 2× slower than OCaml

This is a surprising and encouraging result not only because it makes F# competitive for an even wider variety of tasks but because it also implies that Microsoft are taking F# so seriously that they are optimizing the .NET garbage collector for it!

Steve Hawley’s Protect Yourself

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.

F# and .NET needed at Credit Suisse? Is there a future for this and Microsoft in the quant world?

As I said, when you compare to these other languages in the world of quant, F# appears to be taking an early lead.

Stefano Ricciardi’s Project Euler Problem 4 in F#

The actual algorithm uses brute force to test for palindromicity (neologism?) all the numbers that can be composed multiplying together 3 digits numbers (those from 100 to 999), picking the highest one.

Miscellaneous

Lambda the Ultimate’s OSCON 2010 Emerging Languages Camp Roundup

Inception Movie Review from a Data Security Perspective

loufranco — Fri, 06 Aug 2010 12:48:08 GMT

This is part of my ongoing series of extremely limited perspective movie reviews:

Previous Reviews:

Like the previous ones – SPOILER ALERT. Inception is the kind of movie where you might not want to know anything going in. So, please don’t read further if you don’t want any part of the plot spoiled.

In Inception there’s an elite team that can infiltrate your subconscious while you’re dreaming and extract secret information while your defenses are down. The plot of the movie is set up when someone asks them if they can do an “inception” where they plant an idea into a victim’s subconscious. Since the idea is detrimental to the victim, they must somehow convince him that it is his, and that it will be good for him to follow through with it.

Obviously, extraction directly relates to data security, and the attacks and defenses that are discussed in the movie have analogous ones in the security world. An obvious one is a honeypot and how it relates to the labyrinths that the dream architects construct.

[Honeypots] computers run special software, designed to appear to an intruder as being important and worth looking into. In reality, these programs are dummies, and their patterns are constructed specifically to foster interest in attackers.

Creating a honeypot is like “taking two minutes to create a maze that takes a minute to solve”.

Things like a “militarized subconscious”, “totems”, “forgers”, “chemists”, and “projections” have counterparts in the network security world.

But, what about “inception”? After thinking about it for a few minutes, I remembered this story from WWII. In 1943, the Allies wanted to convince the Germans that they would attack through Sardinia, not Sicily, so:

“The idea, very simply, was to get a dead body, equip the dead body with false papers, and then drop it somewhere the Germans would find it,”

[…] And it was an elaborate creation: the fictitious Major Martin was equipped with ticket stubs, keys, a religious medal, letters from an imaginary father and fiancee, and unpaid bills. Cholmondeley and Montagu thought that the more convincing his personal story was, the more likely the Germans would be to believe the ruse. And along with the personal items, he carried carefully faked letters hinting that the Allies were planning to invade Greece and Sardinia, not Sicily.

But, this is not a computer attack. While the idea of data tampering is nothing new—I haven’t heard of a tampering attack with the intent to mislead someone into making a bad decision. Data tampering is often used to gain access for another purpose or to cover up tracks (e.g. log tampering).

But, I suspect that this is a real threat as well. One so good, that it often goes undetected.

Protect Yourself

Steve Hawley — Tue, 03 Aug 2010 19:08:52 GMT

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.

F# Discoveries This Week 07/30/2010

RickM — Fri, 30 Jul 2010 19:03:57 GMT

It’s Friday and once again I’ve gathered up more F# content for your viewing pleasure. If you happen find yourself in the Boston area this next Monday come meet me for our New England F# User Group meeting. We are always happy to have new people interested in checking out functional programming.

News

VS2010 Keyboard Shortcuts Now Available in Letter and A4 Size

F# samples are 74% complete on langref.org (nudge nudge)

Two Contract Positions: F# Interactive in Silverlight

Scott Theleman will be speaking at New England FSUG on 8/2

Audio / Video

eXpress Persistant Objects and the F# Language

Articles

Don Syme’s Some F# Project Templates Available Online and Daniel Mohl’s An F# Silverlight MVVM Mutli-Project Template

If you have your own templates or projects-that-could-be-turned-into-templates, here are the steps to make and publish a template to the Visual Studio Gallery, making it really easy to access by the whole community.

Ben Hutchison’s Study Functional Programming or Be Ignorant

Right now, if you want to understand the state of the art in computer programming, those are your choices as I see them.

Bohdan Szymanik’s Heat/Image Mapping with .NET/F#

Most of the effort was spent aggregating and binning the data, the actual image prep was trivial. The following assumes you have an array of data to display.

Neil Carrier’s Cartesian Product of Lists in F#

So without further ado (other than to note that all the code here is presented "as-is" and without warranty or implied fitness of any kind; use at your own risk) here is my Cartesian product of lists code.

Jared Parsons’ Converting System.Func<T1..TN> to FSharpFunc<T,TResult>

Interop of delegate style types between F# and other .Net languages is a pain point that results from a fundamental difference in how delegates are represented in the F# language.

Steve Hawley’s Limit Your Memoization, Please

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.

Cameron Taggart’s Exploring the GAC with F# and Mono.Cecil

Mono.Cecil can be used to look inside assemblies. May be you want to search GAC to find types that implement a certain interface. In this post, I’ll show how to find all the types that implement IDisposable as an example.

Cameron Taggart’s Find Authenticode Signed Assemblies

Mono.Security can be used to check for the presence of an Authenticode signature on a assembly.

Gary Short’s XPO – F# Lists and Seqs Oh My!

Let’s assume we have a small database of people and we wish to calculate the combined age. The functional method of doing that would be to “fold” the elements of a collection of People over a function that accumulates the age of each person, in an accumulator value, which is threaded through the fold.

Mark Pearl’s F# Euler Problem 9

After some more thinking, I decided to use tuples instead and generate the permutations using the Seq.unfold method.

Maurizio Colucci’s How F# adapts to the way we think – part1

This is the first episode of a series meant to show how easily F# adapts to the way we think. I assume no knowledge of functional languages, but I do assume knowledge of an imperative language such as C#.

Wiston Gubantes’ F# Asynchronous Programming

Async programming in functional languages such as F# is such a breeze....

Community

Stack Overflow: Immutable data structures performance

Stack Overflow: Functional Reactive F# - Storing States in Games

Limit Your Memoization, Please

Steve Hawley — Mon, 26 Jul 2010 20:18:00 GMT

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.

F# Discoveries This Week 07/23/2010

RickM — Fri, 23 Jul 2010 19:54:12 GMT

One of my favorite things about the F# community is that its members tend to build things that are a bit more interesting, and think about concepts that are a bit deeper. This week is no exception. Come on in and see what’s been happening in the F# world.

A quick note to those giving F# talks or running events: If you would like listed here please don’t hesitate to contact me via the email link at the top of the page. I’d love to help you help others to learn F#.

Events

Nashville Geek Lunch 11:30 AM Next Tuesday (7/27/2010)

Articles

Tomas Petricek’s The Duality of Object and Event references

In this article, I'll talk about an interesting example of duality that (to my best knowledge) wasn't described by anyone before. The two dual structures are references between objects in a normal program and references between events in a reactive application.

Marius Bancila’s Resources for the F# Presentation at Ronua Roadshow

The program that I shown exhibits traits of both functional (for computing the fractal) and object oriented (for displaying the fractal) paradigms.

Neil Carrier’s A Two-Instruction Virtual RISC

One of my favorite hobbies is building really tiny virtual computers. The experience has even paid off a time or two when I needed to create a compact domain-specific language (DSL).

Neil Carrier’s F#'s Little-Known (?) and (?<-) Operators

These two operators work similar to the C/C++ “stringizing” pre-processor operator. That is, they convert non-string code (limited to simple identifiers in the case of F#) into strings according to the following translation patterns:

Julien Ortin’s Arbitraging bookmakers with F#

The principle is rather simple. Take the best quotes for each outcome, and process. If the sum of 1/quote_i is less than one, an arbitrage opportunity exists. The amount to bet on each outcome is 100/quote.

Vladimir Matveev’s Tricky late binding operators

F# Dynamic and DynamicAssignment operators are not as simple as they appear ex facte. Most popular sample of their usage is something like this:

Vladimir Matveev’s Playing with WebSharper

As a sample we’ll make simple StickyNotes application. Web design is not my primary and favorite skill, so I'll omit cross-browser compatibility and bind all styles to Firefox.

Naveen Srinivasan’s Using F# to Automate Reading–The Morning Brew

I like to try and automate most of the stuff . So I thought why not write a script that reads the Morning Brew feed, filter the excluded content that I am not interested in and open the urls before I come in.

Steve Gilham’s Building PartCover 4 on Vista

Following on from earlier in the week, I pulled the current trunk from SourceForge, and set about building it then putting it to work on some F# code which had caused an earlier version (the most recent available at the end of last year) to balk.

Gert-Jan van der Kamp’s Using a DataReader like a list in F#

This article demonstrates a technique how you can write recursive algorithms in F# using a Reader instead of a list, so you don't have to load all your data into memory first.

Steve Jenson’s Building F# on Mac OS X

Joe says his team at Microsoft runs into these issues often with users and was kind enough to walk me through the steps to get F# running on the mac.

The Good Old Days Weren’t That Good

Steve Hawley — Tue, 20 Jul 2010 14:54:22 GMT

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:

Bill’s version of Pascal probably didn’t allow casting (which would’ve been unsafe anyway)
Pascal strings are awful – certainly worse than C, which are pretty bad
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
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.

F# Discoveries This Week 07/16/2010

RickM — Fri, 16 Jul 2010 15:49:19 GMT

As promised, a fresh batch of links to sooth your aching desire for more F#. I’m particularly excited to announce I’ll give giving a F# tutorial this year at the Commercial Users of Functional Programming conference. CUFP is going to have a lot of great content this year and will be well worth attending for anyone interested in functional programming.

News

FAKE – F# Make 1.40.5.0 Released

F# Jobs at Credit Suisse, London

I’ll be giving a F# tutorial at CUFP

Video

Steffen Forkmann speaks on F# Open Source Tools at the New England F# User Group

Presented at the New England F# User Group on June 7, 2010, Steffen discusses FAKE and NaturalSpec. Steffen is the author of the two open source F# projects "FAKE - F# Make" and "NaturalSpec".

Articles

Alex Pedenko’s Introducing Furious – A proof-of-concept RRM for F#

Meet furious. Furious is a RRM - a Record Relation Mapping system. It is a database-independent object query dsl for records, that currently has a (barebones) mysql implementation. Here's how it works. Suppose you have a record graph like so…

Vagif Abilov’s Exploring Amazon S3 with F#

The purpose of this article is to show how fast you can dig into low level details of an unknown technology using F#, and how little code you need to write. Therefore I keep the text of the article short, focusing just on the required steps.

Yin Zhu’s F# Async workflow application: a Flickr crawler

My strategy is to use the search query to search images with some specific tags and from the result page(as shown below), the url of each image is extracted, from which the image and its tags are then crawled.

Daniel Markham’s F# Versus Microsoft's Regex. A Lesson in Types

I was doing some text processing. As part of that, I set up a few RegExes. As I continued coding, I realized that I was following a pattern: apply the regex, check the match count, and if there were a bunch of matches, either get the first or last item.

Jon Harrop’s F# vs Mathematica: an even faster pricer for American options

This new optimized and parallelized F# solution is now a whopping 960× faster than the original Mathematica code from Sal Mangano's Mathematica Cookbook.

Neil Carrier’s Pure OOP – A Personal Retrospective

Almost instantly, my thoughts about the problem undergo a phase change, and I re-write my earlier code to be more succinct, maintainable, and composable, and usually more computationally efficient.

Neil Carrier’s Integer Square Roots

This is an old algorithm, once popular in assembly language programs on small processors. The fact that it uses only integers, addition, subtraction, and less-than branching, mean that its hardware and software requirements are at rock bottom.

Julien Ortin’s F# Event module extension

Functions to extend the F# Event module.

Julien Ortin’s Socket helpers in F#

This post describes a module to perform common socket operations using asynchronous operations and reactive programming.

Julien Ortin’s European Central Bank – extracting reference rates with F#

Every day, the European Central Bank publishes “official” reference FX (foreign exchange) rates where currencies are quoted against the Euro (expressed as EUR/XXX), or 1 EUR = xxx XXX. The exchange rates of the last thirty sessions are available in xml format which we shall try to parse. In order to do so, we use F# and active patterns, based on Don Syme’s draft paper.

Petr Lepilov’s F# interactive, AppFabric cache and PowerShell Part 1 and Part 2

Applications can store any serializable CLR object without worrying about where the object gets stored. Scalability can be achieved by simply adding more computers on demand. The cache also allows for copies of data to be stored across the cluster, thus protecting data against failures. It runs as a service accessed over the network.

Steve Gilham’s dotcover 1.0 beta – first impressions

Not having R# at home -- because I rarely use C# even if I'm writing for .net -- it's this which interested me more. So, I gave it a try on my current F# project

Kurt Schelfthout’s F# and Code Contracts: not quite there yet

In this post I’ll show how you can get Code Contracts sort of working for F#. From my very initial explorations, I would conclude that they seem basically usable for F# programming – but you’ll need some glue and tape, and not everything works as you’d expect.

Edmon Begoli’s Scala vs. F#, Application Programming Features Round 1 and Round 2

F# and Scala, two relatively recent programming languages, provide most .NET and Java software developers with new functional programming features that are worth understanding and evaluating.

Ivan Towlson’s F# pattern matching for beginners, Part 1, Part 2 and Part 3

Pattern matching provides a concise but clear and highly expressive way of writing conditional logic, because it combines the conditional flow with the ability to extract values of interest

Google’s Social Circles give it Acquisition Options

loufranco — Thu, 15 Jul 2010 12:58:31 GMT

A couple of days ago, I wrote about the social circles concept that a UX Researcher at Google is evangelizing. Here is the social circles presentation. The important part starts on Slide 47:

People don’t have one group of friends.

Making people create one big friends group has many of the same problems as planning seating arrangements at your wedding. […] Anyone who is married and went through this will remember how stressful it is.

Yet that’s what is happening online! Everyone being shoved into this big bucket. People don’t have one group of friends. Offline, people have multiple groups of friends that form around life stages and shared experiences.

This is sort of a problem with Facebook for me. Right now, it’s mostly managed by maintaining a separate profile on LinkedIn for my professional network, which brings up another advantage Circles would give Google – the ability to acquire LinkedIn.

Right now, if Facebook announced that it acquired LinkedIn, I’d probably delete one of my profiles. There’s just no way I could imagine them doing it the way I’d want it done (total separation). On the other hand, not withstanding Google’s Buzz debacle, if they do a good job with Circles, then I could see them incorporating LinkedIn or other networks.

The other obvious option is Ning. In Ning, circles are the default, as it’s a way of creating niche social networks. If I belong to different networks on Ning, my friends in one don’t even know I’m in another, let alone what’s going on in the network. Each Ning network is a natural fit for Circles.

This gives Google some options for growing their networks fast, and in a way that doesn’t break privacy. Even better, it’s a strategy that Facebook won’t want to copy as a single network seems to be part of their DNA, so it gives Google a vector of innovation to differentiate itself from Facebook.

VerCache Madness with .NET ActiveX Controls

RickM — Tue, 13 Jul 2010 15:37:39 GMT

About a year ago I was working on building our DotTwain ActiveX control and wrote two articles on some useful tips that I discovered. Since that time, I’ve seen a problem on a few customer computers where, after upgrading once, the control would never run. Instead, it would just try to reinstall after every page load.

After much frustration, it turned out that the problem is related to a little-known Internet Explorer registry entry called VerCache.

[HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Ext\Settings\{GUID}] "VerCache"

I figured this out after noticing that every machine exhibiting this problem had the same value for VerCache. Once the VerCache was set to this value, uninstalling did nothing. The repeated-reinstallation behavior happened with any new version installed which shared the control GUID.

What’s a VerCache?

Strangely enough, searching for “VerCache” ActiveX gives you little more than an IE Team blog post and one MSDN forums entry.

At first, I was very excited when I found this IE team blog post. It appeared that I had found my solution.

Here in the above mentioned screenshots they both are having same file date time stamps and that Causes the VerCache registry key to not get updated.

To resolve this , ensure that at least one of these parameters - “Created” date time stamp, “Modified” date time stamp or the file size, on the updated control is different from the old version of the control and you should be GTG!

Unfortunately, this information seems to be incorrect, or at least overly vague. I observed the same bad VerCache value on different machines with different version of the control. Each of these had different “created” and “modified” time stamps. In fact, the CAB, the installer in the CAB, and the control assembly itself each had different “created” and “modified” time stamps for every single version. I even tried updating the INF and setup launcher timestamps to no avail.

The only thing which did not vary consistently was file size as we rebuild and repackage our control for each DotImage version we release.

Some of the things I tried or considered.

Early on, I discovered simply deleting the registry key after uninstalling fixed the issue temporarily and was under the impression that it was a single bad version of the control causing this. So, I wrote a small cleaner utility to fix the issue. However, as time wore on it was apparent that this issue occurred in a somewhat random fashion with all versions of the control.

Another simple fix I thought about was updating the control GUID with each version. However, this would require updating both our documentation and demos with every build. Additionally, our customers would need to update their javascript with every upgrade. This was unacceptable.

The next thing I tried was to have the installer launch a custom console program on install which cleaned the registry value. This worked great in XP. However, in Windows 7 the console program, even as admin, did not have access to the registry values I wanted to delete.

Finally, a solution.

In the end the only solution I found worked consistently and met our needs was to put custom installer actions into the control itself. When both installing and uninstalling the installer calls the control’s custom actions which removes any existing VerCache value for the control.

First, I snagged a class I had made previously for cleaning guid-based registry entries:

Code Snippet
 public delegate bool RegActionBreakOnTrue(RegistryKey basekey, string key);
 
public class EventArgs<T> : EventArgs { private T eventData; public EventArgs(T eventData) { this.eventData = eventData; } public T EventData { get { return eventData; } } } 
 
public class RegGuidCleaner
{
    string _guid;
    public RegGuidCleaner(string guid)
    {
        _guid = guid;
        Locations = new string[] {};
    }
 
    public string[] Locations { get; set; }
 
    public RegistryKey GetPathBase(string path)
    {
        RegistryKey baseKey;
        if (path.StartsWith(@"HKEY_CURRENT_USER\"))
            baseKey = Registry.CurrentUser;
        else if (path.StartsWith(@"HKEY_LOCAL_MACHINE\"))
            baseKey = Registry.LocalMachine;
        else
            throw new ApplicationException("Unexpected location type: " + path);
        return baseKey;
    }
 
    private string GetBaselessPath(string location)
    {
        string truncatedLoc = location.Substring(location.IndexOf('\\') + 1);
        return truncatedLoc;
    }
 
    public void PerformRegActionForEach(RegActionBreakOnTrue action)
    {
        foreach (var location in Locations)
        {
            string fullPath = location + _guid;
            RegistryKey baseKey = GetPathBase(fullPath);
            string baselessPath = GetBaselessPath(fullPath);
 
            if (action(baseKey, baselessPath))
                break;
        }
    }
 
    public bool EnteriesExist
    {
        get
        {
            bool doesKeyExist = false;
            PerformRegActionForEach((baseKey, subkey) =>
            {
                var key = baseKey.OpenSubKey(subkey);
                if (key != null)
                {
                    doesKeyExist = true;
                    return true;
                }
                else
                    return false;
            });
            return doesKeyExist;
        }
    }
 
    public void DeleteEntries()
    {
        PerformRegActionForEach((baseKey, subkey) =>
        {
            try
            {
                Messages(this, new EventArgs<String>("Deleting Registry Key: " + baseKey.ToString() + @"\" + subkey));
                baseKey.DeleteSubKeyTree(subkey);
            }
            catch (Exception ex) 
            {
                Messages(this, new EventArgs<String>(ex.ToString()));
            }
 
            return false;
        });
    }
 
    public event EventHandler<EventArgs<String>> Messages = delegate { };
}
 

Please forgive the catch (Exception ex). So far it has been unnecessary to handle failure cases for anything other than logging.

Next, I added a custom installer class to remove the entries:

Code Snippet
 [RunInstaller(true)]
public partial class RegistryCleanerInstallerClass : Installer
{
    public RegistryCleanerInstallerClass()
    {
        InitializeComponent();
    }
 
    private void CleanVerCache()
    {
        try
        {
            RegGuidCleaner cleaner = new RegGuidCleaner("{" + typeof(AcquisitionControl).GUID + "}");
            cleaner.Locations = new string[] { 
                @"HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Ext\Settings\", 
             };
 
            cleaner.DeleteEntries();
        }
        catch { }
    }
 
    [System.Security.Permissions.SecurityPermission(System.Security.Permissions.SecurityAction.Demand)]
    public override void Install(IDictionary stateSaver)
    {
        base.Install(stateSaver);
        CleanVerCache();
    }
 
    [System.Security.Permissions.SecurityPermission(System.Security.Permissions.SecurityAction.Demand)]
    public override void Commit(IDictionary savedState)
    {
        base.Commit(savedState);
    }
 
    [System.Security.Permissions.SecurityPermission(System.Security.Permissions.SecurityAction.Demand)]
    public override void Rollback(IDictionary savedState)
    {
        base.Rollback(savedState);
        CleanVerCache();
    }
 
    [System.Security.Permissions.SecurityPermission(System.Security.Permissions.SecurityAction.Demand)]
    public override void Uninstall(IDictionary savedState)
    {
        base.Uninstall(savedState);
        CleanVerCache();
    }
}
 

I also decided to move the com registration into a custom action as well. The installer-based registration had been intermittently not working which caused us to hand test every release version of the control before sending it out.

Code Snippet
 [RunInstaller(true)]
public partial class ComRegisterInstallerClass : Installer
{
    public ComRegisterInstallerClass()
    {
        InitializeComponent();
    }
 
    [System.Security.Permissions.SecurityPermission(System.Security.Permissions.SecurityAction.Demand)]
    public override void Install(IDictionary stateSaver)
    {
        base.Install(stateSaver);
 
        try
        {
            RegistrationServices regSrv = new System.Runtime.InteropServices.RegistrationServices();
 
            if (!regSrv.RegisterAssembly(
                this.GetType().Assembly, AssemblyRegistrationFlags.SetCodeBase))
            {
                throw new InstallException("Failed to register componenet for COM interop");
            }
        }
        catch
        {
        }
    }
 
    [System.Security.Permissions.SecurityPermission(System.Security.Permissions.SecurityAction.Demand)]
    public override void Commit(IDictionary savedState)
    {
        base.Commit(savedState);
    }
 
    [System.Security.Permissions.SecurityPermission(System.Security.Permissions.SecurityAction.Demand)]
    public override void Rollback(IDictionary savedState)
    {
        base.Rollback(savedState);
 
        try
        {
            RegistrationServices regSrv = new System.Runtime.InteropServices.RegistrationServices();
 
            if (!regSrv.UnregisterAssembly(this.GetType().Assembly))
            {
                throw new InstallException("Failed to unregister componenet for COM interop");
            }
        }
        catch
        {
        }
    }
 
    [System.Security.Permissions.SecurityPermission(System.Security.Permissions.SecurityAction.Demand)]
    public override void Uninstall(IDictionary savedState)
    {
        base.Uninstall(savedState);
 
        try
        {
            RegistrationServices regSrv = new System.Runtime.InteropServices.RegistrationServices();
 
            if (!regSrv.UnregisterAssembly(this.GetType().Assembly))
            {
                throw new InstallException("Failed to unregister componenet for COM interop");
            }
        }
        catch
        {
        }
    }
}
 

Finally, I added the the custom action calls to the installer.

This still won’t allow an existing broken control to upgrade. However, after manually uninstalling the old control, the new one will install and work fine. At least that’s what I’ve found in IE 8.0.7600.16385 Update 0 on Windows 7 Enterprise 64-bit. ActiveX tends to be a bit of a moving target these days.

Now, let’s hope I never need speak of this again.

Technical CEO’s must be CEO’s in addition to being Technical

loufranco — Tue, 13 Jul 2010 12:02:38 GMT

Paul Adams, a Google UX Researcher, is writing a book called Social Circles, which you can get a good preview of in this presentation.

Don’t be put off by the 216 slides – it’s a quick read. The key insight is that the Facebook model of a single group of friends doesn’t match real-life social circles that have mutually exclusive friends and that you might want to communicate to each differently.

The document itself is a call to action to Google to recognize that the web is undergoing fundamental change, and in some ways is reminiscent of Bill Gates’s memo about the Internet in 1995.

Paul Adams:

The social web is not a fad, and it’s not going away. It’s not an add-on to the web as we know it today. It’s a fundamental change, a re-architecture, and in hindsight its evolution is obvious.

[…] Make no mistake about this. Everyone in this room will need to learn how to design social features on websites.

[…] When we use search engines today, it’s a pretty solitary experience. We get millions of web pages in our results, yet we don’t see any other people.

Bill Gates:

Browsing the Web, you find almost no Microsoft file formats. After 10 hours of browsing, I had not seen a single Word .DOC, AVI file, Windows .EXE (other than content viewers), or other Microsoft file format.

[…] One scary possibility being discussed by Internet fans is whether they should get together and create something far less expensive than a PC which is powerful enough for Web browsing.

[…] The Internet is a tidal wave. It changes the rules. It is an incredible opportunity as well as incredible challenge.

The Gates memo is reminder of how a technical CEO is critical in leading a software company. It’s full of detailed instructions that only a former programmer would be able to understand.

Eric Schmidt, Sergey Brin and Larry Page are all very technical themselves, and yet this call to arms comes from someone else in the organization. I’m sure Paul Adams is very skilled, but not knowing the internal politics of Google, it’s not clear if his call to action will cause change. It’s not enough to be technical, you also must lead. In the “Next Steps” section of the Gates memo, he says:

I want every product plan to try and go overboard on Internet features. One element that will be crucial is coordinating our various activities. The challenge/opportunity of the Internet is a key reason behind the recent organization.

Google needs a similar message about social features coming from Schmidt.

F# Discoveries this Week 07/09/2010

RickM — Fri, 09 Jul 2010 17:42:10 GMT

This week we once again reap another huge crop of fantastic F# content. In fact, it’s been getting so overwhelming that I’ll be moving to an every week format from here on out. Please come in, read, and enjoy!

News

A New F# Case Study on Microsoft.com

With its new tools, the bank can speed development by 50 percent or more, improve quality, and reduce costs.

Next F# London Meetup Announced: July 28th

The next meetup of the F#unctional London Meetup Group will be held on July 28, with Zach Bray talking on Agile Acceptance Testing with F#

Tim Anderson (of The Register) Interviews Don Syme

I met Syme at the QCon conference in London, in March 2010, and interviewed him shortly afterwards. Some quotes from that interviewed have already been published in an article for The Register, but I am now posting nearly all of it here.

DotNetKicks Now has a F# Section

Thanks to everyone on twitter who voted!

Quantifa 0.0.2 Released

Quantifa is an F# open-source library for quantitative finance and risk management.

F#-mode for Emacs updated to 0.3

The F# mode for Emacs is two years old, and has been downloaded more than 1,000 times.

Tables: Organize Your Files. Written in F#

Tabbles is a new way of organizing files: it combines virtual folders and tags, and auto-organizes and tags your files in very intelligent ways.

Audio / Video

Svea Ekonomi on F# for automated billing system for the Telecom industry

In earlier versions of the billing system, much of the business logic resided in SQL Server and various Perl and Java programs. That made the solution hard to maintain and tailor to the needs of the customers. By using F# instead of an object oriented language the developers at Svea Ekonomi can be a lot more productive.

Articles

Ian Voyce’s Minilight renderer in F#

I’m a sucker for eye-candy, and the other day I came across the beautifully lit renders produced by Minilight. It’s a nice, minimal implementation of a global illumination renderer that’s been ported to a wide variety of different languages from C to ActionScript. So of course, I couldn’t resist trying to implement it in F#.

Jon Harrop’s F# vs Mathematica: fast pricer for American options

Another example from Sal Mangano's Mathematica Cookbook, this time taken from Andreas Lauschke's example, is a "fast" pricer for American options. The relevant section of the book stresses the importance of performance in this context and the Mathematica code presented was heavily optimized by experts.

Jon Harrop’s F# vs Mathematica: parametric plots

Another example from Sal Mangano's Mathematica Cookbook (p.520) is an elegant little Mathematica program that uses a crude numerical integrator to plot the trajectory of a differential equation representing the populations of predators (foxes) and prey (rabbits):

Jon Harrop’s F# vs Mathematica: red-black trees

The simpler F# solution is also 20× faster at inserting 100k elements and 100× faster at computing the range of depths in the resulting tree.

Jon Harrop’s Lorenz Attractor

The Lorenz attractor is a fractal derived from the trajectory of a 3-dimensional dynamical system that exhibits chaotic flow. This blog post describes a 35-line program that computes trajectories of this attractor and visualizes them as a beautiful whisp using Windows Presentation Foundation.

Neil Carrier’s Composable Order Relations

Even before I started experimenting, I realized that checking a list for sorting was just a specific example of checking whether the pairs in a list satisfied a certain binary order relation. So I decided to work directly on a more general solution.

Neil Carrier’s Continuation-Passing Mnemonics

Learning to construct continuations can be tough. It’s easy to state how they work: they facilitate tail recursion by recursively passing the remainder of a computation. But it can be a lot harder to actually get one working from scratch.

Neil Carrier’s Dijkstra’s Shunting-Yard Algorithm

Without further ado, here is my first F# implementation of Dijkstra’s shunting-yard algorithm, including a basic test (based on the example at Wikipedia). This is probably not a minimal or most-efficient implementation, but it is a starting place.

Neil Carrier’s Arity and Unit Arguments in F# 2.0

While working on an internal domain-specific language, I encountered a case where passing a unit into a function made the syntax somewhat more readable. The completely artificial example below illustrates the concept as the function xfer1. I also tried a two-unit version, which is illustrated as xfer2.

Daniel Mohl’s Presentation: 5 Best Practices for F# Development slides and examples

Thanks to all who come out to the New England F# User Group meeting tonight!

Tomas Petricek’s Dynamic in F#: Reading data from SQL database

If you ever tried to call a SQL stored procedure directly using the SqlCommand, then you can surely appreciate the elegance of this code snippet. Let's now take a look at a larger example and some of the neat tricks that make this possible...

Erik Schulz’s Cartesian Tree Sort – Revisited, Cartesian Tree Sort – Skew Heap and Beating Quick Sort - Cartesian Tree Merge

After looking at skew heap, merge sort and Cartesian tree, I figured there has to be a way to combine all three.

Julien Ortin’s SEO Analysis in F#, and SEO Analysis in F#, a friendly application

Last time, we created a library of Search Engine Optimization (SEO) helpers. This time we’ll see how to use them to actually fetch information about your webiste rankings (and your competitors’).

Julien Ortin’s European Central Bank – extracting reference rates with F#

Every day, the European Central Bank publishes “official” reference FX (foreign exchange) rates where currencies are quoted against the Euro (expressed as EUR/XXX), or 1 EUR = xxx XXX. The exchange rates of the last thirty sessions are available in xml format which we shall try to parse. In order to do so, we use F# and active patterns, based on Don Syme’s draft paper.

Anton Tayanovskyy’s Optimizing JavaScript with F#

The need for optimizing JavaScript is very peculiar. This is not about delivering top wall-clock performance, but rather delivering the most compact (in Release mode) and most readable (in Debug mode) source. In the case of WebSharper™, it is also about relieving the compiler and the macro writer from the burden of emitting optimal code.

Chris Ballard’s My First F# Post

That said, this post will take you through my solution for Euler 54, which (somewhat unusually) isn't a particularly mathematical problem, but turns out to be a great way to demonstrate some of the features of the F# language. The basic principle of this problem is to compare two hands of cards in the game of poker, and to determine which is the winning hand.

Chris Ballard’s Prime Numbers - Building the EulerMaths library in F#

Those of you who are doing Project Euler know what I am talking about by the EulerMaths library. There are certain fundamentals which crop up again and again in the questions and it is important to work these into a reusable and performant library.

Daniel Mohl’s WPF MVVM Multi-Project Template: A Polyglot Approach

As an advocate for using the right tool for the job, I have created a new WPF MVVM multi-project template composed of an C# View project, an F# ViewModel project, and an F# Model project.

Rodolfo Ortega’s Eliza like chat bot in F# language for fun

This is a very simple Eliza like chat bot. I call it Meliza Sharp. I wrote it for having fun learning the F# language shipped with Visual Studio 2010.

Mauricio Scheffer’s Abusing PrintfFormat in F#

Pretty cool, huh? This trick can be used for other things, since PrintfFormatProc is fully reusable. For example, I'm currently using PrintfFormat manipulation to define type-safe routing in a web application

Mark Pearl’s Depressingly simple text file access

Today I was doing some work work and kept having to parse a log file. After a few hours of doing the same routine stuff I thought I might try and automate it using F#.

Mathias’s On the road from C# to F#: reading stock quotes and more stocks

Mads Kristensen has a nice post where he shows how to read stock quotes from Yahoo finance using C#, which was very helpful to get started. I figured it would be interesting to try out a conversion to F# and see what the result looked like.

Why Software Has Bugs

Steve Hawley — Thu, 08 Jul 2010 14:20:34 GMT

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:

Finite memory
Finite storage
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?

Don’t assume you need to be clever a priori
Use a language appropriate to the problem domain
Use well-debugged, well-tested libraries to do common data structuring
Strive to keep your code as clean¹ and as readable as possible
Optimize based on measurements not instinct
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)?

Twilight: Eclipse from a Social Media Perspective

loufranco — Thu, 08 Jul 2010 13:30:01 GMT

Last year, I wrote a review of Star Trek from an ECM Perspective, and I’ve been looking out for other movies that have an interesting collaboration angle, but couldn’t think of one until last week when I went to a midnight showing of the new Twilight movie.

Spoiler Alert: I have to give away some details of the movie (and the next one) in this review.

There are at least three kind of telepathic collaboration in Twilight. Edward can read thoughts (except for Bella’s), the wolf pack is connected to each other telepathically, and Alice can “follow” decisions and see the future after a decision is made.

I think a lot could be said about how the wolf pack telepathy is like Facebook (Jacob talks about the drama of a love triangle being broadcast around the wolf pack). And perhaps Alice has some kind of super-twitter that people can’t help using to blurt out their plans to her.

But I think the most interesting Social Media aspect to Twilight is Bella. Bella’s thoughts cannot be read, and in the Twilight world, privacy is a super-power.

And, it’s not just incidental, Bella’s ability to keep her thoughts to herself is an integral part of the plot. For example:

It’s part of Edward’s attraction to her (the other part being his insatiable desire to have her for dinner)
It probably saved her life with the Volturi in New Moon
She uses it to mask feelings she might have for Jacob.
(Breaking Dawn SPOILER) Her privacy abilities expand in Breaking Dawn to include being able to shield others.

In any case, with the world moving towards more sharing and openness, it’s interesting to remember the power of privacy as well.

F# Range Specification Mistake

Steve Hawley — Wed, 30 Jun 2010 20:10:27 GMT

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.

How Google Can Bust Facebook Network Effects

loufranco — Tue, 29 Jun 2010 16:24:28 GMT

There was a leak today that Google is building a Facebook competitor called Google Me (to go along with Orkut, Wave, and Buzz). GigaOM reports:

Could Google put together a credible competitor to Facebook? Anything is possible, but so far there’s little reason to believe that the search giant could come up with a service that represented a real threat. Orkut may be popular in South America and India, but has shown no signs of growing outside of those countries. Could Google use it as the basis for something that takes parts of Google Buzz, parts of Google Profiles, parts of Google Wave and parts of Blogger to construct a comprehensive social network? Theoretically, but that sounds more like a Frankenstein-style strategy than anything else — stitching together pieces of half-dead services and hoping they come alive.

The problem with the Google social networks aren’t their feature sets, it’s that no one uses them (because no one uses them). Going right up against Facebook with just comparable features is doomed to failure, because no one really has a feature problem with Facebook.

The problem they need to solve is how do they get a person sitting at their computer to open an account to use a service that is useless until others join. Their options:

Sign them up automatically – this has already spectacularly failed with Buzz. Perhaps there’s a better way.
Pay them.
Make it so that signing up makes some other Google service better.

And, they need to incent people to invite others in. Options are

Sign up all of your email contacts and connect you to them (oh yeah, that didn’t work)
Pay them.
Make is so that getting others to join makes some other Google service better.

Automatic sign-up has already failed, and I can’t see Google resorting to paying people. So, the only path is to somehow augment all Google services with the data from their social network (in a way that preserves privacy). The huge advantage that Google has over Facebook is that they can incorporate the data into search results without making the data indexable. Facebook has to either recreate all Google services or open up their data.

Here are some ideas for how Google services can be augmented with social data:

My registered likes and interests should make my search results better.
Likes and interests should be used by Google reader to suggest articles and feeds.
Likes and interests should augment maps with places I like
Let advertisers target search keywords and demographics
My network’s likes should augment my search results. When I search for a product, let me know that someone likes an alternative.
Let me designate a search as wanting a network result page. Like Quora, but only for my network (I do this ad-hoc on Facebook already).
Highlight mail that is from someone in my network.

After doing that, they can try to use my use of other services to augment the network. I would love if more things added to my timeline instead of sending e-mail. Let me designate filters that divert there instead. There are definitely some feeds that I would divert there as well.

Essentially, Google needs to fight the network effect of Facebook with one of their own (between their own services).

Applied F# Symposium Session 2

Steve Hawley — Fri, 25 Jun 2010 18:58:00 GMT

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

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

Steve Hawley — Fri, 25 Jun 2010 18:54:00 GMT

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

F# Discoveries This Week 06/25/2010

RickM — Fri, 25 Jun 2010 14:40:51 GMT

As always, a huge number of software releases and high quality articles this week. My favorite thing about the F# community is that someone is always writing about something that tickles my brain. While right out of a computer science textbook, I enjoyed Erik Schulz’s sorting animations quite a lot. His animations are excellent.

News

VS2010 Pro Power Tools Released (fixes scrolling reference dialog)

A set of extensions to Visual Studio Professional (and above) which improves developer productivity. Includes a New ‘Add Reference’ dialog: Pops up fast and is more pleasant (less frustrating) to use.

HuwmanCode 0.1 Released – Simplified Windows Services in F#

HuwmanCode is a collection of libraries intended to enhance the base class libraries for developers writing F#. Using HuwmanCode you can write a Windows Service in F# entirely.

F# Project Extender 0.9.3 Released

Installing F# Project Extender provides tools to better organize files in F# projects by allowing project subdirectories and separating file management in Solution Explorer from controlling compilation order.

VCC 2.1.30625 Released (Written in F#)

VCC is a mechanical verifier for concurrent C programs. VCC takes a C program, annotated with function specifications, data invariants, loop invariants, and ghost code, and tries to prove these annotations correct. If it succeeds, VCC promises that your program actually meets its specifications.

Fing 0.1 Released

Fing is F# API Search. It's inspired by Hoogle, although it is not a port.

Audio/Video

Tomas Petricek at the London F# User Group – Reactive Programming in F#

During this talk, Tomas will cover two techniques. We'll start by looking at F# events and declarative approach for specifying event processing. Next, we'll look at embedding F# event handling into asynchronous workflows and programming using "state machines". We'll also briefly mention how this relates to more general functional programming "design patterns".

A Listing of F# TechEd Talks, at the New England F# User Group

A complete listing of all TechEd talks pertaining to F#. Thanks Talbott!

Articles

Antonio Cangiano’s How Microsoft is changing the programming world.

The end result of Microsoft’s new approach is that now Joes everywhere are getting exposed to functional programming (masses of people who would otherwise be virtually shielded from the rest of the programming world).

Erik Schulz’s Cartesian Tree Sort, Insertion Sort, Priority Queue & Heap Sort, Heap Sort, Selection Sort, Quick Sort, Gnome Sort, Comb Sort, Odd-even Sort, Cocktail Sort, and Bubble Sort.

Inspired be Wikipedia's algorithm pages I decided to recreate their animations using JavaSrcipt and HTML5 canvas elements. IE 8 does not support canvas however new versions of all other modern browsers do. Mozilla Firefox, Google Chrome, Safari, and Opera.

Laurent Le Brun’s F# + OpenGL: a cross-platform sample

The nice thing is that the application was cross-platform. I tried it on Windows, Linux and Mac, it worked everywhere, without changing a single line. It seems like F# is ready to make great cross-platform 3D applications!

Daniel Mohl’s An F# WPF MVVM Project Template

I've been planning for a while to create an F# WPF MVVM Template to add to the other templates that have been announced on this blog. A resent post by Mark Pearl provided a great simple example which helped kick me into gear and bring this plan to fruition.

Jomo Fisher’s Use FsLex and FsYacc to make a parser in F#

The starter project implements a simple calculator language that you can grow into a more sophisticated Domain Specific Language or text processing application.

Julien Ortin’s SEO helpers in F#

In this post, we describe how to implement functions that help fetch information that can be used to study how well (or bad) the keywords are used on a given website in comparison with other (successful) competitors.

Neil Carrier’s Flip Operator for F#

I ask again: is there a good native way to do this in F#? If not, it might well worth standardizing this. (And potentially other FORTH-like operators like “over” and “rot,” perhaps with an extensible syntax.)

Joel Björnson’s Fun with dependent formlets (in WebSharper)

To give some hints of what you can do with the WebSharper formlet library, the objective of the following exercise is to create a simple spread-sheet like widget based on formlets.

Joel Björnson’s More of Ext JS and WebSharper

In general, seamlessly being able to create data abstractions and transfer data back and forth between the server and client is a very strong incentive for using the WebSharper extension.

Joel Björnson’s Reactive programming with WebSharper

In following post I'd like to highlight F# (and WebSharper) support for asynchronous and reactive programming.

Mark Pearl’s F# Seq.Unfold

The more I play the more I am really loving F# and how succinct the language is. Today I thought I would put up a brief post on the Seq.unfold function.

Daniel Merino’s Testing F# (with Traveling Salesmen)

The next example is a little snippet that returns a dictionary distances between cities for a small distributed traveling salesman problem I did last year to test F# on a software engineering class.

Richard Minerich’s Love the Lambda

So the idea for Love the Lambda was born: I would demonstrate both the usefulness and sheer novelty of first class functions and do so simultaneously in C# and F#. More than that, I would use the opportunity as a kind of F# omnibus.

Pete Hunt’s F# rocks (so far)

I have to say, I really like F# so far. For those of you not in the know, F# is Microsoft’s new first-class language that has been in development since 2002 but debuted in Visual Studio 2010. It is basically a dialect of O’Caml that runs on .NET and has full Visual Studio support.