Recently a ‘FP User Group’ was started by some people at Ghent University, called GhentFPG, and the first meeting took place last thursday, with great interest from students, university employees as well as people working in the industry. You can find some more info in the GhentFPG Google Group or in the wiki (where you can also find the slides of the presentations given during the first meeting).

Some days ago someone new to FP posted a message on the mailing list, asking which language he should study, among other things.

Since I think my reply might be of general interest (also outside GhentFPG), I decided to post a copy on this blog as well (note I did add some extra markup). Comments welcome!

Based on my experience (which is biased, obviously):

• Functional Programming is not only a language-related thing. FP
  languages do enforce you to apply functional paradigms, but you can
  easily follow these paradigms in lots of other (more mainstream?)
  languages as well: it is easier to learn people a paradigm using a
  language they already know, rather than telling them FP is really cool
  and useful and interesting, but requires them to learn a new
  language/toolchain/… first.

  Not talking about Java or C++ or something similar here, rather Python
  and Ruby.

• If you’re into Java/C#/…, Scala is a really good introduction to FP:
  it allows you to write OOP code just like you do already, but also
  provides you lots of FP-related features, and pushes you gently into the
  FP approach. The book “Programming in Scala” by Odersky et al. (the main
  author of Scala) is IMO a really good intro to both Scala as well as the
  FP concepts it provides, not only showing them but also explaining
  gently why they’re useful, and why they’re ‘better’ than the approaches
  you’re taking already.

  The Scala type system is rather interesting as well.

  It’s the gentle path, so you want Learning Scala before reading
  ‘Real World Haskell‘ certainly helped me a lot to understand the latter.

• Haskell is an incredibly interesting language because of the concepts
  it adopted and types it provides, but it does require an immediate mind
  switch when coming from a non-OOP world (I once spent about 2 hours to
  explain a Java-guy how classes and instances in Haskell relate to
  classes and instances in Java, it wasn’t obvious). “Real World Haskell”
  is certainly worth a read (and if you read “Programming in Scala” as
  well, you’ll notice lots of similarities).

  I for one can read Haskell code pretty easily and learned lots of
  CS/math things thanks to learning it, but I’m (still) unable to write
  non-trivial code (I need some good project to get my hands dirty I
  guess).

• Erlang is really interesting from a (very specific) feature
  perspective: high-availability, distributed computing, the actor system
  and the OTP library on top of it,…

  It’s a rather ‘old’ language, but I kind of like it. Some people do
  complain about the syntax, but once you figured out ‘,’, ‘;’ and ‘.’ are
  used almost the same as they are in ‘human’ written language, everything
  becomes obvious

  Do note though Erlang is not a normal general-purpose language. You can
  code +- everything you want using it, but it’s really targeted to
  distributed/high-available/network applications. You most likely won’t
  use it to solve mathematical problems or write a game. It’s really good
  at what it’s built for though.

  One final note: please don’t ever make the mistake I made. If you know
  Erlang, and take a look at Scala (which also has an actor library in the
  standard distribution, as well as the more advanced Akka-library), don’t
  judge Scala as being a competitor for Erlang, they’re both completely
  different languages targeting different applications. ‘Scala’ is not
  about ‘scalability’ as Erlang is (it’s a “Scalable Language”).

• F# (and most likely OCaml as well, although I never used it though) is
  certainly worth a look as well. I only read 3/4th of a book on it, but
  it looks really promising and interesting.

• There’s obviously all sorts of Lisp dialects. I have no opinion on
  them, never looked into any Lisp closely enough. I only wrote some
  Clojure (a Lisp-dialect for the JVM) code one day, but need to learn
  more about the Lisp-way of programming. Clojure seems to be interesting
  because of the deep integration of Software Transactional Memory (STM)
  in the language (yet another approach to concurrency ).

As for the IDE question: Vim and a decent terminal are all you need,
luckily none of the above languages require you to learn how to use a
toolchain which enforces you (or some magic IDE) to write 500 lines of
XML-based build ‘programs’ or other insanities.

My advice: pick some language, learn it, but make sure you don’t only
learn the language, but especially the concepts (type system,
higher-order stuff, list manipulation,…). Then pick some other
language and learn it as well (which will be easier since you got the
concepts already) and so on.

And read tons of papers available on the internet in between Even if
you don’t understand a paper completely, you’ll pick up some things
already, and re-reading it 2 weeks later helps a lot

Just my .02,

Nicolas

The book targets people who know Python (it doesn’t contain a language introduction chapter or something alike, which would be rather pointless anyway), and want to start testing the code they write. Even though the author starts by explaining basic tools like doctests and the unittest framework contained in the Python standard library, it could be a useful read even if you used these tools before, e.g. when the Mock library is explained, or in the chapter on web application testing using Twill.

The text is easy to read, and contains both hands-on code examples, explanations as well as tasks for the reader and quiz questions. I did not audit all code for correctness (although in my opinion some more time should have been invested here before the book was publishing: some code samples contain errors, even invalid syntax (p45: “self.integrated_error +q= err * delta“), which is not what I expect in a book about code testing), nor all quizes. These could’ve used some more care as well, e.g. on p94 one can read

What is the unittest equivalent of this doctest?

>>> try:
...     int('123')
... except ValueError:
...     pass
... else:
...     print 'Expected exception was not raised'

I was puzzled by this, since as far as I could remember, int(’123′) works just fine, and I didn’t have a computer at hand to check. Checked now, and it works as I expected, so maybe I’m missing something here? The solution found in the back of the book is a literal unittest-port of the above doctest, and should fail, if I’m not mistaken:

>>> def test_exceptions(TestCase):
...     def test_ValueError(self):
...         self.assertRaises(ValueError, int, '123')

This example also shows one more negative point of the book, IMHO: the code samples don’t follow PEP-8 (or similar) capitalization, which makes code rather hard to read sometimes.

The solutions for the last quiz questions are missing as well, and accidently I did want to read those.

Don’t be mistaken though: these issues don’t reduce the overall value of the book, it’s certainly worth your time, as long as you keep in mind not to be too confused by the mistakes as shown above.

Topic overview

The book starts with a short overview of types of testing, including unit, integration and system testing, and why testing is worth the effort. This is a very short overview of 3 pages.

Starting from chapter 2, the doctest system is introduced. I think it’s an interesting approach to start with doctest instead of using unittest, which is modeled after the more ‘standard’ xUnit packages. Doctests are useful during specification writing as well, which is in most project the first stage, before any unittestable code is written. The chapter also introduces an overview of the doctest directives, which was useful to read.

In chapter 3 gives an example of the development of a small project, and all stages involved, including how doctests fit in every stage.

Maybe a sample of Sphinx and its doctest integration would have been a nice addition to one of the previous chapters, since the book introduced doctest as part of stand-alone text files, not as part of code docstrings (although it does talk about those as well). When writing documentation in plain text files, Sphinx is certainly the way to go, and its doctest plugin is a useful extra.

Starting in chapter 4, the Python ‘mocking‘ library is introduced. The chapter itself is a rather good introduction to mock-based testing, but I don’t think mocks should be used in doctests, which should be rather small, examplish snippets. Mock definitions don’t belong there, IMO. This chapter also shows some lack of pre-publishing reviews in a copy-paste error, in the block explaining how to install mocker on page 62, telling from now on Nose is ready to be used.

Chapter 5, which you can read here introduces the unittest framework, its assertion methods, fixtures and mocking integration.

In chapter 6 ‘nose‘ is introduced, a tool to find and run tests in a project. I use nose myself in almost every project, and it’s certainly a good choice. The chapter gives a pretty good overview of the useful features nose provides. It does contain a strange example of module-level setup and teardown methods, whilst IMHO subclassing TestCase would be more suited (and more portable).

Chapter 7 implements a complete project from specification to implementation and maintenance. Useful to read, but I think the chapter contains too much code, and it’s repeated too often.

Chapter 8 introduces web application testing using Twill, which I never used before (nor did I ever test a web application before). Useful to read, but Twill might be a strange choice, since there have been no releases since end 2007… Selenium might have been a better choice?

A large part of the chapter is dedicated to list all possible Twill commands as well, which I think is a waste of space, this can be easily found in the Twill language reference.

Chapter 9 introduces integration and system testing. Interesting to read, the diagram-drawing method used is certainly useful, but it also contains too much code listings.

Finally, chapter 10 gives a short overview of some other testing tools. First coverage.py is explained, which is certainly useful. Then integration of test execution with version control systems is explained. I think this is certainly useful, but not at this level of detail. Setting up a Subversion repository is not exactly what I expect here, especially not when non-anonymous, password-based authentication over svn:// is used (which is a method which should be avoided, AFAIK).
Finally, continuous integration using Buildbot is tackled. No comments here, although I tend to use Hudson myself

Final words

Is this book worth your time and money? If you’re into Python and you don’t have lots of experience with testing Python code, it certainly is. Even if you wrote tests using unittest or doctests before, you’ll most likely learn some new things, like using mocks.

I’m glad Packt gave me the opportunity to read and review the book. I’d advise them to put some more effort in pre-publishing reviews for future titles, but the overall quality of the non-code content was certainly OK, and I hope lots of readers will enjoy and learn from this book.

If you’re into Python software development, you might want to take a look at the book webpage, or download a free chapter (PDF) about the standard Python unittest package for now.

Since I’m not a big fan of extensive/exaggerated unit testing and rather believe in functional/component tests, I’m looking forward to read the book and learn some new things. Looking forward to the web application testing chapter, among others.

Disclaimer: I was invited by Packt Publishing to review this book, and they provide a free copy.

MacBook:~ nicolas $ telnet chat.facebook.com 5222
Trying 69.63.176.191...
Connected to chat.facebook.com.
Escape character is '^]'.
<stream />
<?xml version="1.0"?><stream:stream id="F6DE2CB5" from="chat.facebook.com" xmlns="jabber:client" xmlns:stream="http://etherx.jabber.org/streams" xml:lang="en"><stream:error><invalid-namespace xmlns="urn:ietf:params:xml:ns:xmpp-streams"/></stream:error></stream:stream>

Connection closed by foreign host.

Jay!

Last couple of days I wrote some very basic Scala snippets, containing constructs which would be non-trivial or ‘unusual’ to write in Java, compile it to a class file, and then use a Java decompiler to figure out how the Scala compiler maps those constructs to JVM bytecodes.

There’s one thing which took my attention: looks like (basic) tail-recursive functions are optimized into while-loops! This only happens if the last call of a function is a call to itself (the most basic form of tail recursion), but it’s an interesting feature anyway… No more need to put socket accept handling in an infinite while loop

A little demo. First, here’s a Scala object which implements a very basic ‘reduce’ function:

object Reducer {
  def reduce[T, V](fun: (V, T) => V, values: List[T], initial: V): V = {
    if(values isEmpty)
      return initial
    val next = fun(initial, values head)
    return reduce(fun, values tail, next)
  }

  def main(args: Array[String]): Unit = {
    val values = List(1, 2, 3, 4)
    val sum = reduce[Int, Int]((x, y) => x + y, values, 0)
    println("Result: " + sum)
  }
}

We can compile and run this, and it’ll output the expected result ’10′:

MacBook:reduce nicolas $ scalac Reducer.scala 
MacBook:reduce nicolas $ scala Reducer
Result: 10

Now we can open the generated class files in JD. There are a couple of them (it’s interesting to take a look at all of them and figure out what they represent exactly), but in this case we need ‘Reducer$.class’, which contains the implementations of our public functions, including ‘reduce’.

Here’s the Java version of the ‘reduce’ function:

public <T, V> V reduce(Function2<V, T, V> fun, List<T> values, V initial)
{
  while (true)
  {
    if (values.isEmpty())
      return initial;
    Object next = fun.apply(initial, values.head());
    initial = next;
    values = values.tail();
  }
}

‘Function2′ is a built-in Scala type which represents a function taking 2 parameters. As you can see, this code does exactly the same as our Scala version and is most likely the way we’d write the code manually as well (the only thing I don’t get is why ‘next’ is an Object and not a ‘V’, I might figure that out later), but without forcing us to write the imperative code, whilst still producing bytecodes which will most likely show the best performance on the JVM (which currently has no tail recursion optimization support (although that might change one day)).

I like it

[update]
For reference, here’s a slightly more Scala-ish implementation of reduce, showing the same time performance characteristics during some basic profiling. I was not able to get JD nor jad to generate any usable decompiled code though:

def reduce[T, V](fun: (V, T) => V, values: List[T], initial: V): V = {
    values match {
        case List() => initial;
        case head :: tail => reduce(fun, tail, fun(initial, head))
    }
}

It uses Scala’s “List” pattern matching functionality.

Git has a feature to work with SVN repositories, git-svn, but that’s intended to check out existing code from SVN and work on it, not publishing an existing Git tree into a Subversion repository.

A first rather naive approach didn’t work out (as somewhat expected), but then I figured out how to achieve this anyway.

As a test, let’s first create an empty SVN repository and a Git repository with some commits:

$ svnadmin create repo
$ svn co file:///Users/nicolas/Temp/git_to_svn/repo svn_repo
Checked out revision 0.
$ cd svn_repo
$ svn mkdir trunk tags branches
A         trunk
A         tags
A         branches
$ svn commit -m "Create repository structure"
Adding         branches
Adding         tags
Adding         trunk

Committed revision 1.
$ cd ..

$ mkdir project; cd project
$ git init
Initialized empty Git repository in /Users/nicolas/Temp/git_to_svn/project/.git/
$ echo "foo" > test.txt; git add test.txt; git commit -m "Initial version"
master (root-commit) 88464cf] Initial version
 1 files changed, 1 insertions(+), 0 deletions(-)
 create mode 100644 test.txt
$ echo "bar" > test.txt; git commit test.txt -m "Second version"
master cb62866] Second version
 1 files changed, 1 insertions(+), 1 deletions(-)

We now can set up git-svn:

$ git svn init -s file:///Users/nicolas/Temp/git_to_svn/repo/
$ git svn fetch
r1 = 741ab63aea786882eafd38dc74369e651f554c9c (trunk)

Depending on the layout of your SVN project, you might need to drop the -s parameter and add -t, -T or -b flags, see the git-svn manpage.

A little naive we could try to push everything to the SVN repository now:

$ git svn dcommit
Unable to determine upstream SVN information from HEAD history.
Perhaps the repository is empty. at /opt/local/libexec/git-core/git-svn line 439.

This fails since the git svn command can’t figure out which commits to push: there’s no link between our original Git repository and the Subversion heads.

To fix this, we can use a Git graft to link them. We’ll tell Git the commit which created the SVN folder in which we want to store the project is the parent commit of the first commit in our Git repository:

$ git show-ref trunk
741ab63aea786882eafd38dc74369e651f554c9c refs/remotes/trunk
$ git log --pretty=oneline master | tail -n1
88464cfdf549a82b30ee7c52e53e2b310f0d9ec4 Initial version
$ echo "88464cfdf549a82b30ee7c52e53e2b310f0d9ec4 741ab63aea786882eafd38dc74369e651f554c9c" >> .git/info/grafts

If now you execute git log, you’ll see the “Create repository structure” SVN commit is displayed after our “Initial version” commit.

Pushing to SVN now works fine:

$ git svn dcommit
Committing to file:///Users/nicolas/Temp/git_to_svn/repo/trunk ...
	A	test.txt
Committed r2
	A	test.txt
r2 = 8c72757dd3a7d550ed8ef393bb74c0350d22dbac (trunk)
No changes between current HEAD and refs/remotes/trunk
Resetting to the latest refs/remotes/trunk
test.txt: locally modified
	M	test.txt
Committed r3
	M	test.txt
r3 = ca0fc06d477bcd4dd5c6f6d2ae6d94356b510280 (trunk)
No changes between current HEAD and refs/remotes/trunk
Resetting to the latest refs/remotes/trunk

All set

Enlightened I/O is a specialized virtualization-aware implementation of high level communication protocols (such as SCSI) that utilize the VMBus directly, bypassing any device emulation layer. This makes the communication more efficient but requires an enlightened guest that is hypervisor and VMBus aware.

The drivers seem to be developed by Novell, so I guess the Boycott Novell guys will have some more coverage^Wrants soon (Update: can’t find the reference on this anymore, so this might be a false statement, sorry. Thanks for pointing out RubenV)

Interesting times on the virtualization front… Although I for one do not plan to replace Xen, xVM or VirtualBox anytime soon.

Sources:

• Microsoft Press Release
• Blog of the 451 Group
• LKML

On a side note: Red Hat entered the Standard & Poor’s 500 index, which might show Linux is gaining more interest from enterprises and investors.

Hey,

As discussed before, this is not a fair comparison, since the non-recursive version is much ‘smarter’ than the recursive one: it calculates values and will never recalculates them, whilst the recursive version calculates everything over and over again.

Adding some simple memoization helps a lot. First, my testing code:

Here are the benchmarks on my MacBook Pro Intel Core2Duo 2.33GHz with 3GB RAM (running quite a lot of applications). Do note the ‘dumb’ version calculates fib(35), whilst the slightly optimized versions, which still use recursion but much less recursive calls (as they should) or your second version calculate fib(150).

Using MacOS X 10.5.6 stock CPython 2.5.1:

MacBook:Projects nicolas $ python -V
Python 2.5.1

MacBook:Projects nicolas $ python fib.py 35 150
fib(35) = 9227465
Calculation took 12.8542108536 seconds

Calculating the amount of recursive calls to calculate fib(35)
Calculating fib(35) = 9227465 took 29860703 calls

fib2(150) = 9969216677189303386214405760200
Calculation took 0.00020694732666 seconds

memoize_dict(fib)(150) = 9969216677189303386214405760200
Calculation took 0.00141310691833 seconds

memoize_constant_list(151, fib)(150) = 9969216677189303386214405760200
Calculation took 0.000310182571411 seconds

Overall it looks like fib2 and memoize_constant_list perform fairly similar, I guess function call overhead and list.append have a similar influence on performance in this case.

Using Jython 2.5.0 from the binary distribution on the Java HotSpot 64bit Server VM as shipped for OS X 10.5.6:

MacBook:Projects nicolas $ ./Jython/jython2.5.0/jython -V 
Jython 2.5.0

MacBook:Projects nicolas $ ./Jython/jython2.5.0/jython fib.py 35 150
fib(35) = 9227465
Calculation took 12.5539999008 seconds

Calculating the amount of recursive calls to calculate fib(35)
Calculating fib(35) = 9227465 took 29860703 calls

fib2(150) = 9969216677189303386214405760200
Calculation took 0.0519998073578 seconds

memoize_dict(fib)(150) = 9969216677189303386214405760200
Calculation took 0.00399994850159 seconds

memoize_constant_list(151, fib)(150) = 9969216677189303386214405760200
Calculation took 0.00300002098083 seconds

The ‘dumb’ fib implementation performs similar in both CPython and Jython. Jython performs significantly less good on the other implementations though, but maybe todays news could help here, not sure how much locking on dict and list access Jython introduces.

Finally, using Unladen Swallow 2009Q2, self-compiled from SVN on the same system, using standard settings:

MacBook:Projects nicolas $ ./unladen-swallow/unladen-2009Q2-inst/bin/python -V
Python 2.6.1

MacBook:Projects nicolas $ ./unladen-swallow/unladen-2009Q2-inst/bin/python fib.py 35 150
fib(35) = 9227465
Calculation took 12.2675719261 seconds

Calculating the amount of recursive calls to calculate fib(35)
Calculating fib(35) = 9227465 took 29860703 calls

fib2(150) = 9969216677189303386214405760200
Calculation took 0.000118970870972 seconds

memoize_dict(fib)(150) = 9969216677189303386214405760200
Calculation took 0.000972986221313 seconds

memoize_constant_list(151, fib)(150) = 9969216677189303386214405760200
Calculation took 0.00036096572876 seconds

which is similar to, slighly better or slightly worse than the CPython run, and when enforcing JIT (which introduces a significant startup time, which is not measured here):

MacBook:Projects nicolas $ ./unladen-swallow/unladen-2009Q2-inst/bin/python -j always fib.py 35 150
fib(35) = 9227465
Calculation took 14.6129109859 seconds

Calculating the amount of recursive calls to calculate fib(35)
Calculating fib(35) = 9227465 took 29860703 calls

fib2(150) = 9969216677189303386214405760200
Calculation took 0.0432291030884 seconds

memoize_dict(fib)(150) = 9969216677189303386214405760200
Calculation took 0.0363459587097 seconds

memoize_constant_list(151, fib)(150) = 9969216677189303386214405760200
Calculation took 0.0335609912872 seconds

which, to my surprise, performs pretty worse than the default settings.

Overall: your first implementation performs tons and tons of function calls, whilst the second one, which resembles memoize_list_fib in my code (which is recursive), performs significantly less function calls and in the end memoize_list_fib performs almost as good as your second version (it performs +- the same number of function calls as the number of times you’re going through your loop).

So whilst I do agree function calls in Python are reasonably slow compared to plain C function calls (which is just a jmp, no frame handling etc. etc. required), your comparison between your recursive and non-recursive implementation is completely unfair, and even if calculating fib(35) takes several seconds, consider you’re doing a pretty impressive 29860703 function calls to perform the calculation.

Time to get some sleep.

Since I wanted to learn some language not resembling any other I already know (even a little), I decided some hours ago to start digging into Clojure, which is a LISP dialect running on the JVM using STM (Software Transactional Memory) and created with concurrency in mind. Check the website for more information.

After some hacking I got a first ‘application’ running. Since recently there’s been some little meme at work regarding echo servers, I decided to write a very basic line-oriented echo server in Clojure.

The result is a server using one thread per connection which just sends back lines to a connected client as-is. Nothing fancy, but might be a useful start for developing basic network applications using Clojure.

Enjoy!