Functional Programming

Recently, a colleague here at Lab49 asked whether there were any good books available to help getting developers unfamiliar with F# and functional programming started in the world of functional .NET. I had some ideas and thought I’d post them here.

(In his post below, Sergey mentioned that Luke Hoban, the F# product manager, gave a talk at the Lab on F#. We recorded that presentation and I’ll be posting it soon, so stay tuned.)

The question was if there was a good book for “a typical Java developer to learn F#”. The short answer is that there isn’t. F# is a pretty flying leap for a typical Java developer to make; you can approach F# from the .NET world (e.g. C#) or from other functional languages (e.g. its parent, OCaml), but it’s hard to see how one could do it from neither. That said, I know of three F#-focused books in print now that can serve as a guide:

-”Expert F#“, by F#’s creator Don Syme. This is the book I recommend. It’s not perfect but it’s a good introduction to F#, mostly suited for people coming from a .NET background. It’s very dense. It’s not for novice programmers, and assumes a good deal of expert general programming knowledge on the part of the reader. But it’s definitely the best out there. (It’s also a bit out of date since the release of the September 1.9.6.2 CTP, but still mostly relevant. I expect it will eventually get updated.)

-”Foundations of F#” by Robert Pickering. This one is simpler and more basic than the above, and might be useful for just getting started. It isn’t as illuminating as the above and won’t serve as a full guide on its own. If you’re ready to deep dive, go straight to Don Syme and pass this one by.

-”F# for Scientists.” This one is for scientists.

“Expert F#” is the best bet for really tackling this language.

Keep in mind that if you really want to get serious with F# as a platform you’ll eventually need to understand the .NET Framework and the CLR (for which the best book remains “CLR via C#” by Jeffrey Richter).

There are a couple of other books coming out that I’m looking forward to seeing. One, by Chris Smith, promises to be great and is slated for release next year (and has a truly bizarre image occupying its placeholder cover). Also check out Chris’s series on his blog solving Project Euler problems with F#, which show off some of F#’s core functionality and can be a nice intro to approaching problems in a functional way. Another, “Real-world Functional Programming in .NET” by Tomas Petricek, who used to work on the F# team, will deal with FP approaches in both .NET and C# (using LINQ).

Some other F# resources are:
Hubfs.com, where the minds behind F# monitor the boards and answer tough questions, and
Flying Frog Consultancy, who have done a lot of cool work with F#.

My advice: download the CTP, buy the Don Syme book, and have some functional fun.

A while ago Luke Hoban from Microsoft gave a presentation on F#. I started reading the F# book by Don Syme and the word that was often used to describe the language in both the book and the presentation was “succinct”.

I decided to test the succinctness of it and here is my implementation of Quick Sort in F#

 let rec quickSort sequence =
  match sequence with
  | [] -> sequence
  | x :: t -> List.partition (fun a -> a < x) t |> (fun (a,b) -> quickSort a @ x :: quickSort b)

Pretty Succinct!

Partitions a list based on a predicate. The first list contain the elements that match and the second the ones that don’t.

Function List-Partition {
 param($fun, $list)

 $list1=@(); $list2=@()

 $list |
   ForEach {
     if(& $fun $_) {
       $list1+=@($_) } else {$list2+=@($_)
     }
 }

 $list1, $list2
}

Works with a simple list

$numList = 1,2,3,5,7,11,13,16,17,19,23
$fun = {param($x) $x % 2 -eq 0}

$list1,$list2 = List-Partition $fun $numList
"[$list1] [$list2]"

Results

[2 16] [1 3 5 7 11 13 17 19 23]

Works with a list of Objects

$list = @()
$list += New-Person John Doe
$list += New-Person Jane Doe
$list += New-Person Tom Doe
$list += New-Person Harry Doe
$list += New-Person George Carlin
$list += New-Person Lenny Bruce

$list1,$list2 = List-Partition {param($x) $x.Last -eq ‘Doe’} $list
"List1"
$list1

"`nList2"
$list2

Results

List1

First  Last

—–  —-

John   Doe

Jane   Doe

Tom    Doe

Harry  Doe

List2

George Carlin

Lenny  Bruce

I am looking at extending LINQ for a current project. I Googled for custom linq and found resources like Charlie Calvert’s Links to LINQ then Introducing Linq to Amazon and then LINQ in Action. Other resources, Bart De Smet’s many detailed posts on LINQ that included LINQ through PowerShell.

Reading LINQ in Action, the authors start with Extension Methods. Which got me thinking about extension methods in PowerShell. Experimenting a while back I created a static class, added a method, used the this syntactical sugar but loading it up PowerShell and trying it did not work.

Continuing research on customization of LINQ led me to Bart’s post Extension Methods in Windows PowerShell. He used PowerShell’s feature called the Extended Type System. With this approach you to create Xml and use the cmdlet Update-TypeData.

You can view the extend types shipped with PowerShell like this

notepad %windir%\system32\WindowsPowerShell\v1.0\types.ps1xml

Here is Bart’s illustration of what you can find in this file and its use.

<Type>
    <Name>System.Array</Name>
    <Members>
        <AliasProperty>
            <Name>Count</Name>
            <ReferencedMemberName>Length</ReferencedMemberName>
        </AliasProperty>
    </Members>
</Type>

PS > $a = "Jimmy", "John"
PS > $a.Count
2

Take a look at Jeffery Snover’s post Hate Add-Member? (PowerShell’s Adaptive Type System to the Rescue). He calls this feature the Adaptive Type System and shows how to extend every object so it can dynamically add Methods and Properties to itself.

Back to LINQ

Bart has a new post outlining one of the most important properties of LINQ: its flexibility.

The potential of LINQ is infinity², the reason for it being the infinite fan-in (LINQ though C#, VB, F#, PowerShell, various transport mechanisms, etc) multiplied by the infinite fan-out (LINQ to SQL, Entities, XML, Objects, DataSets, SharePoint, Active Directory, Amazon, etc).

Bart’s full post Who ever said LINQ predicates need to be Boolean-valued?

Highscalability.com discusses about Disco, a map-reduce framework here .

Tomas Petricek, who interned under the supervision of Don Syme, is publishing.

“Thinking differently about problems" is available for free.

Parallelization of functional programs

Imagine that we’re writing a computer game and we have a list of characters controlled by the computer. In a single step of the game, we want to remove all characters that died since the last step and we want to calculate new state of the game character (such as new location). Also a character can perform some operation with the world (for example picking an item from the world).

Imperative Solution

List<GameCharacter> dead = new List<GameCharacter>();

foreach(GameCharacter ch in Characters) {
  if (!CharacterIsAlive(ch))
    dead.Add(ch);
  else
    ch.PerformStep(this.World);
}

Characters.RemoveAll(dead);

Functional Version

  1 Characters = Characters.Filter(CharacterIsAlive);
  2 Characters = Characters.Select(PerformStep);
  3 this.World = Characters.Aggregate(this.World, ModifyWorld);

1. Filter out dead characters
2. Calculate new state for each character
3. Calculate new state of the world

A fundamental part of Don Syme’s day.

Our aim here is to put nothing between you and your ability to explore a problem space with F#.

The new F# CTP is available at the Microsoft F# Developer Center.

I recently purchased F# For Scientists by Dr. Jon Harrop after the author mentioned it on the Mathematica Mailing List. According to Dr. Harrop,

Mathematica's .NET-Link technology allows Mathematica and .NET programs to interoperate seamlessly. Moreover, Microsoft's new functional programming language F# provides many familiar benefits to Mathematica programmers:
The marriage of Mathematica with F# can greatly improve productivity for a wide variety of tasks.

I am a big fan of Mathematica and functional programming and have been wanting to check out F# for some time so I decided to give the book a shot. It just arrived today so I can't post a full review but I did jump directly to the small section (5 pages) on using F# with Mathematica.

What did I learn? Well this section rightly claims that Mathematica has awesome symbolic math capabilities (it does). But then it goes on to claim that F# can beat the pants off of Mathematica on raw calculation. Thus it suggested F# programmers should call out to Mathematica for symbolic integration but then evaluate the result in F# for speed (to the tune of 3.4 times Mathematica's speed). I was naturally dubious. The explanation of this speed up is give as

The single most important reason for this speed boost is the specialization of the F# code compared to Mathematica's own general purpose term rewriter. ... Moreover, the F# programming language also excels at compiler writing and the JIT-compilation capabilities of the .NET platform make it ideally suited to the construction of custom evaluators that are compiled down to native code before being executed. This approach is typically orders of magnitude faster than evaluation in a standalone generic term rewriting system like Mathematica.

Okay, hold the phone! First off, I did not know the F# language could write compilers. I'll forgive this as poetic use of language. I guess I sort of know what he meant to say. More interesting is that we have gone from 3.7 times to "orders of magnitude". Now, I don't take anything away from the brilliant folks at Microsoft, but the equally brilliant folks at Wolfram have been focusing exclusively on mathematics software for 20 years and you might think they learned a thing or two about computational speed!

Here is the example from the book...

First, he uses Mathematica to integrate a function.


Integrate[Sqrt[Tan[x]],x]

(-2*ArcTan[1 - Sqrt[2]*Sqrt[Tan[x]]] +
2*ArcTan[1 + Sqrt[2]*Sqrt[Tan[x]]] +
Log[-1 + Sqrt[2]*Sqrt[Tan[x]] - Tan[x]] -
Log[1 + Sqrt[2]*Sqrt[Tan[x]] + Tan[x]])/(2*Sqrt[2])

He then goes to show that Mathematica takes 26 secondsto evaluate this function in loop for 360,000 iterations.

He then shows a translator that converts the Mathematica to F# and the F# code does the same work in 7.595 seconds.

So far Dr. Harrop is correct but like some many others who are in a rush to show their new favorite language superior to another's, he forgets to read the manual! Particularly, the section on optimization! If he had he would have found a handy little Mathematica function called Compile. Hmm, sounds promising. And in fact....


cf = Compile[{{x, _Complex}}, Evaluate[Integrate[Sqrt[Tan[x]],x]]]
Timing[Do[cf[x + y I],{x,-3.0,3.0,0.01},{y,-3.0,3.0,0.01}]]

{5.281,Null}

That's 5.281 seconds on my relatively underpowered laptop (Thinkpad X60) !

Some might feel I'm being a bit harsh on Dr. Harrop but after all he made me layout bucks for a book that promised me "many familiar benefits" only to deliver 5 measly pages of half truth. F# programmers may benefit from Mathematica but the jury is still out as to whether the reverse is true.

At this point we’ve developed a complete, though very simple, interpreter and runtime environment.  To some degree, this interpreter is all we need.  It can express any function, it can easily be extended, it has a simple parser, and it has a working garbage collector.  What more could we ask for?  Life is good.

Life is good, that is, until we ask somebody else to use it.  Their first response is probably an annoyance at the syntax — it’s a little surprising to have to write (+ 1 1) after grade school has burned 1 + 1 into our minds — and, truth be told, the S-Expression syntax isn’t the most natural or compact for every problem.

Luckily we can, with a little work, entirely eliminate this complaint by creating a parser generator — a function that takes as input a grammar (a formal description of a language), and produces as output a parser for that language.

Read the rest of this entry »

In the previous articles of this series we’ve seen how to create a simple Scheme interpreter, then how to write an S-Expression parser to feed the interpreter, and in the last article we saw how to most conveniently bind C++ functions to our interpreter with the strategic application of template classes and a “meta-circular” code-generator that built up a vital part of our interpreter (using our interpreter to do it).

Though we’ve come a long way, there’s still one glaring hole in our interpreter design: we’ve left the allocate<T> function unspecified.  This function is meant to allocate a garbage collected value of type T, which implies that we’ve got to write a garbage collector.  In this article, that’s exactly what we’ll do.

Read the rest of this entry »

Many computer science students have heard of red-black trees. If you use any container class library that has a map (ordered associative container) like STL you probably know that red-black trees are a popular implementation of a map. It may be non-obvious why the constraints associated with red-black trees cause them to remain roughly balanced but what is even more daunting is the implementation of such trees in an imperative language like C!

While working on an implementation for a recipe in my forth coming "Mathematica Cookbook" I found a functional implementation in Haskell (postscript) by Chris Okasaki. I know this has been said a million times before but it never ceases to amaze me how succinct and beautiful the functional approach can be. Using the Haskell solution as a guide, I was able to develop a complete red-black implementation in Mathematica in under 2 hours. This may not sound that impressive but consider that the referenced paper does not show how to implemented a remove operation. Even without the need for a remove, how many programmers could take a red-black tree written in say C and translate it into a completely working implementation in Java in under 2 hrs? I suppose a few can but this is really not a post about bragging rights. The functional approach to software development is just god-damn beautiful at so many levels and it is this and not my hacker abilities which made this exercise possible.

Now, there are caveats. There always are. Any C implementation of a red-black tree is bound to have numerous optimizations and a purely functional solution will not fare well for every application of a map (but surprisingly it is competitive for many. I'll post some C++ comparisons when I have a chance.)

If you'd like to learn more about red-black trees but don't know Haskell I would highly recommend learning the minimum of Haskell you need to understand Okasaki's paper instead of trying to learn about them by digging into a C implementation first.

Don Syme posts the highlights. Chris Smith posts F# in 20 Minutes - Part I.

Mailing lists are great places to find fruitless arguments. One of the most chronic arguments take the form of "My programming language is the most X". Here X may be "object-oriented", "functional", or even something much vaguer like "elegant".

When using terms like "object-oriented" and "functional" it is good to have somewhat agreed upon definitions. A characteristic that applies to everything applies to nothing. This is why I get a little bit frustrated when I read arguments like C is object-oriented because you can create tables of function pointers to simulate polymorphism or C is functional because you can pass a pointer to a function. We'll then so is assembler, I guess.

However, almost as annoying are arguments within the group of languages that are widely agreed to have the specified trait. Consider functional languages. I think present day functional enthusiasts would agree that Haskell is an outstanding example of a functional language. It has first class functions, lambda abstraction, and higher order primitives like map, foldr, foldl, etc. However, things begin to go awry when Haskellers start conflating features of the language that, although virtuous as they may be, evolved after the functional paradigm became widely recognised. For example, take single assignment. Clearly single assignment has many benefits. But it is hard for me to accept that the mother of all functional languages, Lisp, is not functional because it has setq. The same is true for other traits like currying, closures, type induction, lazy evaluation, etc.

What gets lost in the quest to define a language as the most X is the much harder question of why the traits that one deems must exist in a X language are important in the first place. In which circumstances will such a trait lead to better software and in which circumstances will it simply provide rope to hang oneself.

The distinction between strict and non-strict functional languages is a good case in point. In a strict language the arguments passed to a function must be fully evaluated before the invocation (ML, Scheme) while non-strict languages can support lazy evaluation (Miranda, Haskell). Is a non-strict language better than a strict one? Should languages support both? Are such questions even answerable?

I think these questions are important and are answerable but the answers involve very deep considerations of problem domain, proofs of correctness, type theory, compiler design and even the limitations of human ability to reason about software. Human knowledge in these areas are not extended by arguments about what's more X.

As you know from a recent post, I am not into language bashing but I recently came across a witty one liner that sort of resonated with me: "C is fast, Ruby is beautiful and Erlang is WTF?" I might substitute a functional language (like Lisp or Haskel for Ruby) but the basic message is a valid one. Erlang as some cool ideas but they are packaged into a slow and rather ugly (syntactically) implementation.

This is a minor continuation of my thoughts from The Law of the Excluded Middle does not apply to Programming Languages.

One sure sign that you have mastered a language is when you can create a fairly comprehensive list about what sucks about the language (while simultaneously appreciating why some of this suckiness is a necessary evil).

When you first meet a new language that floats your boat, there is a tendency is to fall in love. This happened to me not too long ago with Erlang. You think, "This language is great. Such and such is so hard to do in Language X and look how easy it is in Language Y.

Well, much like in the real world of human relationships you don't really know what love means until you get married! When you get married to a language (commit to developing a multi-year non-trivial system in it) then your love is surely tested. You learn about the languages warts and its tendency to leave its socks outside the hamper, squeeze the tooth paste from the top and leave the toilet seat in an inconvenient position!

If you still love the language with its warts and all, then you have some of the necessary (but not necessarily sufficient) hallmarks of a master. Either that, or you ave a really good therapist.

p.s. Erlang and I broke up but we are still friends! On a happier note, my long term mistress (Mathematica) and I are really making sparks fly! Hope C++ doesn't catch us.

Paul Graham released a new dialect of Lisp at http://arclanguage.org/ Arc is designed above all for exploratory programming: the kind where you decide what to write by writing it. A good medium for exploratory programming is one that makes programs brief and malleable, so that’s what we’ve aimed for. This is a medium for sketching software. […]

I’ve been looking for opportunities to express myself in F# and I found a good idea on Hubfs:

http://cs.hubfs.net/blogs/solong/archive/2008/01/14/4561.aspx

The idea is to solve problems at ProjectEuler in F#
http://projecteuler.net/index.php?section=problems

While implementing the solution for problem #2 in F#, I learned about an experimental feature. fun fun. Read the rest of this entry »

via Don Syme Greg Neverov’s post. The library exposes memory transactions as a monad using F#’s new computation expression feature. Download HERE.

Amazon has released to beta a new web service. Charles Ying, after being under NDA, blogs some details. Amazon is running Erlang. Greg Wilson, author of Practical Parallel Programming, picks up on the post and says this about pure functional languages: I don’t believe that PFLs make non-trivial parallel programs easier to write. I don’t believe they […]

Robert Pickering post. A happy side effect of this is that other .NET languages would find this class really easy to use too.