What task is best done in a functional programming style?
I've just recently discovered the functional programming style [...] Well, recently I was given a chance to give a talk on how to reduce software development efforts, and I wanted to introduce the concept of functional programming.
If you've only just discovered functional programming, I do not recommend trying to speak authoritatively on the subject. I know for the first 6 months while I was learnig F#, all of my code was just C# with a little more awkward syntax. However, after that period of time, I was able to write consistently good code in an idiomatic, functional style.
I recommend that you do the same: wait for 6 months or so until functional programming style comes more naturally, then give your presentation.
I'm trying to illustrate the benefits of functional programming, and I had the idea of showing people 2 set of code that does the same thing, one coded in a very imperative way, and the other in a very functional way, to show that functional programming can made code way shorter, easier to understand and thus maintain. Is there such example, beside the famous sum of squares example by Luca Bolognese?
I gave an F# presentation to the .NET users group in my area, and many people in my group were impressed by F#'s pattern matching. Specifically, I showed how to traverse an abstract syntax tree in C# and F#:
using System;
namespace ConsoleApplication1
{
public interface IExprVisitor<t>
{
t Visit(TrueExpr expr);
t Visit(And expr);
t Visit(Nand expr);
t Visit(Or expr);
t Visit(Xor expr);
t Visit(Not expr);
}
public abstract class Expr
{
public abstract t Accept<t>(IExprVisitor<t> visitor);
}
public abstract class UnaryOp : Expr
{
public Expr First { get; private set; }
public UnaryOp(Expr first)
{
this.First = first;
}
}
public abstract class BinExpr : Expr
{
public Expr First { get; private set; }
public Expr Second { get; private set; }
public BinExpr(Expr first, Expr second)
{
this.First = first;
this.Second = second;
}
}
public class TrueExpr : Expr
{
public override t Accept<t>(IExprVisitor<t> visitor)
{
return visitor.Visit(this);
}
}
public class And : BinExpr
{
public And(Expr first, Expr second) : base(first, second) { }
public override t Accept<t>(IExprVisitor<t> visitor)
{
return visitor.Visit(this);
}
}
public class Nand : BinExpr
{
public Nand(Expr first, Expr second) : base(first, second) { }
public override t Accept<t>(IExprVisitor<t> visitor)
{
return visitor.Visit(this);
}
}
public class Or : BinExpr
{
public Or(Expr first, Expr second) : base(first, second) { }
public override t Accept<t>(IExprVisitor<t> visitor)
{
return visitor.Visit(this);
}
}
public class Xor : BinExpr
{
public Xor(Expr first, Expr second) : base(first, second) { }
public override t Accept<t>(IExprVisitor<t> visitor)
{
return visitor.Visit(this);
}
}
public class Not : UnaryOp
{
public Not(Expr first) : base(first) { }
public override t Accept<t>(IExprVisitor<t> visitor)
{
return visitor.Visit(this);
}
}
public class EvalVisitor : IExprVisitor<bool>
{
public bool Visit(TrueExpr expr)
{
return true;
}
public bool Visit(And expr)
{
return Eval(expr.First) && Eval(expr.Second);
}
public bool Visit(Nand expr)
{
return !(Eval(expr.First) && Eval(expr.Second));
}
public bool Visit(Or expr)
{
return Eval(expr.First) || Eval(expr.Second);
}
public bool Visit(Xor expr)
{
return Eval(expr.First) ^ Eval(expr.Second);
}
public bool Visit(Not expr)
{
return !Eval(expr.First);
}
public bool Eval(Expr expr)
{
return expr.Accept(this);
}
}
public class PrettyPrintVisitor : IExprVisitor<string>
{
public string Visit(TrueExpr expr)
{
return "True";
}
public string Visit(And expr)
{
return string.Format("({0}) AND ({1})", expr.First.Accept(this), expr.Second.Accept(this));
}
public string Visit(Nand expr)
{
return string.Format("({0}) NAND ({1})", expr.First.Accept(this), expr.Second.Accept(this));
}
public string Visit(Or expr)
{
return string.Format("({0}) OR ({1})", expr.First.Accept(this), expr.Second.Accept(this));
}
public string Visit(Xor expr)
{
return string.Format("({0}) XOR ({1})", expr.First.Accept(this), expr.Second.Accept(this));
}
public string Visit(Not expr)
{
return string.Format("Not ({0})", expr.First.Accept(this));
}
public string Pretty(Expr expr)
{
return expr.Accept(this).Replace("(True)", "True");
}
}
class Program
{
static void TestLogicalEquivalence(Expr first, Expr second)
{
var prettyPrinter = new PrettyPrintVisitor();
var eval = new EvalVisitor();
var evalFirst = eval.Eval(first);
var evalSecond = eval.Eval(second);
Console.WriteLine("Testing expressions:");
Console.WriteLine(" First = {0}", prettyPrinter.Pretty(first));
Console.WriteLine(" Eval(First): {0}", evalFirst);
Console.WriteLine(" Second = {0}", prettyPrinter.Pretty(second));
Console.WriteLine(" Eval(Second): {0}", evalSecond);;
Console.WriteLine(" Equivalent? {0}", evalFirst == evalSecond);
Console.WriteLine();
}
static void Main(string[] args)
{
var P = new TrueExpr();
var Q = new Not(new TrueExpr());
TestLogicalEquivalence(P, Q);
TestLogicalEquivalence(
new Not(P),
new Nand(P, P));
TestLogicalEquivalence(
new And(P, Q),
new Nand(new Nand(P, Q), new Nand(P, Q)));
TestLogicalEquivalence(
new Or(P, Q),
new Nand(new Nand(P, P), new Nand(Q, Q)));
TestLogicalEquivalence(
new Xor(P, Q),
new Nand(
new Nand(P, new Nand(P, Q)),
new Nand(Q, new Nand(P, Q)))
);
Console.ReadKey(true);
}
}
}
The code above is written in an idiomatic C# style. It uses the visitor pattern rather than type-testing to guarantee type safety. This is about 218 LOC.
Here's the F# version:
#light
open System
type expr =
| True
| And of expr * expr
| Nand of expr * expr
| Or of expr * expr
| Xor of expr * expr
| Not of expr
let (^^) p q = not(p && q) && (p || q) // makeshift xor operator
let rec eval = function
| True -> true
| And(e1, e2) -> eval(e1) && eval(e2)
| Nand(e1, e2) -> not(eval(e1) && eval(e2))
| Or(e1, e2) -> eval(e1) || eval(e2)
| Xor(e1, e2) -> eval(e1) ^^ eval(e2)
| Not(e1) -> not(eval(e1))
let rec prettyPrint e =
let rec loop = function
| True -> "True"
| And(e1, e2) -> sprintf "(%s) AND (%s)" (loop e1) (loop e2)
| Nand(e1, e2) -> sprintf "(%s) NAND (%s)" (loop e1) (loop e2)
| Or(e1, e2) -> sprintf "(%s) OR (%s)" (loop e1) (loop e2)
| Xor(e1, e2) -> sprintf "(%s) XOR (%s)" (loop e1) (loop e2)
| Not(e1) -> sprintf "NOT (%s)" (loop e1)
(loop e).Replace("(True)", "True")
let testLogicalEquivalence e1 e2 =
let eval1, eval2 = eval e1, eval e2
printfn "Testing expressions:"
printfn " First = %s" (prettyPrint e1)
printfn " eval(e1): %b" eval1
printfn " Second = %s" (prettyPrint e2)
printfn " eval(e2): %b" eval2
printfn " Equilalent? %b" (eval1 = eval2)
printfn ""
let p, q = True, Not True
let tests =
[
p, q;
Not(p), Nand(p, p);
And(p, q),
Nand(Nand(p, q), Nand(p, q));
Or(p, q),
Nand(Nand(p, p), Nand(q, q));
Xor(p, q),
Nand(
Nand(p, Nand(p, q)),
Nand(q, Nand(p, q))
)
]
tests |> Seq.iter (fun (e1, e2) -> testLogicalEquivalence e1 e2)
Console.WriteLine("(press any key)")
Console.ReadKey(true) |> ignore
This is 65 LOC. Since it uses pattern matching rather than the visitor pattern, we don't lose any type-safety, and the code is very easy to read.
Any kind of symbolic processing is orders of magnitude easier to write in F# than C#.
[Edit to add:] Oh, and pattern matching isn't just a replacement for the visitor pattern, it also allows you to match against the shape of data. For example, here's a function which converts Nand's to their equivalents:
let rec simplify = function
| Nand(p, q) when p = q -> Not(simplify p)
| Nand(Nand(p1, q1), Nand(p2, q2))
when equivalent [p1; p2] && equivalent [q1; q2]
-> And(simplify p1, simplify q1)
| Nand(Nand(p1, p2), Nand(q1, q2))
when equivalent [p1; p2] && equivalent [q1; q2]
-> Or(simplify p1, simplify q1)
| Nand(Nand(p1, Nand(p2, q1)), Nand(q2, Nand(p3, q3)))
when equivalent [p1; p2; p3] && equivalent [q1; q2; q3]
-> Xor(simplify p1, simplify q1)
| Nand(p, q) -> Nand(simplify p, simplify q)
| True -> True
| And(p, q) -> And(simplify p, simplify q)
| Or(p, q) -> Or(simplify p, simplify q)
| Xor(p, q) -> Xor(simplify p, simplify q)
| Not(Not p) -> simplify p
| Not(p) -> Not(simplify p)
Its not possible to write this code concisely at all in C#.
There are plenty examples out there but none will be as impact full as using a sample relevant to one of your projects at work. Examples like "Sum Of Squares" by Luca are awesome but if someone used that as proof as to how our code base could be written better I would not be convinced. All the example proves is some things are better wrote functionally. What you need to prove is your code base is better written functionally
My advice would be to pick some popular trouble spots and some core spots in the code base, and rewrite them in a functional style. If you can demonstrate a substantially better solution, it will go a long way to winning over co-workers.
Tasks for functional style? Any time you have a common coding pattern and want to reduce it. A while ago I wrote a bit on using C# for functional style, while making sure it's practical: Practical Functional C# (I'm hesitate to link to my own stuff here, but I think it's relevant in this case). If you have a common "enterprise" application, showing, say, how expressions are lovely in pattern matching won't be too convincing.
But in real-world apps, there are TONS of patterns that pop up at a low, coding level. Using higher order functions, you can make them go away. As I show in that set of blog posts, my favourite example is WCF's "try-close/finally-abort" pattern. The "try/finally-dispose" pattern is so common it got turned into a language keyword: using. Same thing for "lock". Those are both trivially represented as higher order functions, and only because C# didn't support them originally do we need hard-coded language keywords to support them. (Quick: switch your "lock" blocks out to use a ReaderWriter lock. Oops, we'll have to write a higher order function first.)
But perhaps convincing just requires looking at Microsoft. Generics aka parametric polymorphism? That's hardly OO, but a nice functional concept that, now, everyone loves. The cute Ninject framework wouldn't work without it. Lambdas? As expression trees, they're how LINQ, Fluent NHibernate, etc. get all their power. Again, that doesn't come from OO or imperative programming. The new Threading library? Pretty ugly without closures.
So, functional programming has been blessing things like .NET over the last decade. The major advances (such as generics, "LINQ") are directly from functional languages. Why not realise there's something to it and get more involved in it? That's how I'd phrase it to skeptics.
The bigger problem is actually getting people to make the jump in understanding to higher order functions. While it's quite easy, if you've never seen it before in your life, it might be shocking an incomprehensible. (Heck, seems like a lot of people think generics are just for type-safe collections, and LINQ is just embedded SQL.)
So, what you should do is go through your codebase, and find places that are an overly-complicated imperative nightmare. Search for the underlying patterns, and use functions to string it together nicely. If you can't find any, you might settle for just demo'ing off lists. For example "find all the Foos in this list and remove them". That's a 1 line thing in functional style "myList.Remove(x=>x.Bla > 0)" versus 7 lines in C# style (create a temp list, loop through and add to-remove items, loop though and remove the items).
The hope is that, even though the syntax is odd, people will recognize "wow, that's a lot simpler". If they can put down the "verbose == more readable" and "that looks confusing" for a bit, you'll have a chance.
Good luck.
The best advocacy paper ever written for the functional style is a paper by John Hughes called Why Functional Programming Matters. I suggest you do some examples for yourself until you reach the stage where you can convincingly make the arguments laid out in that paper.
Many of the examples in the paper are numerical and do not resonate with today's audiences. One more contemporary exercise I gave my students was to use the ideas in that paper to pack large media files onto 4.7GB DVDs for backup. They used Michael Mitzenmacher's "bubble search" algorithm to generate alternative packings, and using this algorithm and Hughes's techniques it was easy to get each DVD (except the last) 99.9% full. Very sweet.