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

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.

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

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!

The most common approach is something like (pseudocode):

temp = from
from = to
to = temp

In Python there’s an easier approach though which seems to be unknown to several developers. It uses the multi-assignment/expansion syntax:

from, to = to, from

Basically, the tuple on the right (to, from) is constructed, then expanded to locals ‘from’ and ‘to’.

Just a hint It’s a pretty elegant line of code IMHO.

A more elegant solution is creating a node using Python, similar to JInterface and equivalents. Luckily there’s an existing project working on a library to create Erlang nodes using Python and Twisted: TwOTP.

One downside: it’s rather underdocumented… So here’s a very quick demo how to call functions on an Erlang node from within a Twisted application.

First of all we’ll create 2 Erlang functions: one which returns a simple “Hello” message, one which uses an extra process to return ‘pong’ messages on calls to ‘ping’, and counts those.

The code:

-module(demo).
-export([hello/1, ping/0, start/0]).

hello(Name) ->
    Message = "Hello, " ++ Name,
    io:format(Message ++ "~n", []),
    Message.

ping_loop(N) ->
    receive
        {get_id, From} ->
            From ! {pong, N},
            ping_loop(N + 1)
    end.

ping() ->
    pingsrv ! {get_id, self()},
    receive
        {pong, N} -> ok
    end,
    {pong, N}.

start() ->
    Pid = spawn_link(fun() -> ping_loop(1) end),
    register(pingsrv, Pid).

This should be straight-forward if you’re familiar with Erlang (which I assume).

The Python code is not that hard to get either: it follows the basic Twisted pattern. First one should create a connection to EPMD, the Erlang Port Mapper Daemon (used to find other nodes), then a connection to the server node should be created, and finally functions can be called (calls happen the same way as Erlang’s RPC module).

Here’s the code. I’d advise to read it bottom-to-top:

import sys

from twisted.internet import reactor
import twotp

def error(e):
    '''A generic error handler'''
    print 'Error:'
    print e
    reactor.stop()

def do_pingpong(proto):
    def handle_pong(result):
        # Parse the result
        # 'ping' returns a tuple of an atom ('pong') and an integer (the pong
        # id)
        # In TwOTP, an Atom object has a 'text' attribute, which is the string
        # form of the atom
        text, id_ = result[0].text, result[1]
        print 'Got ping result: %s %d' % (text, id_)
        # Recurse
        reactor.callLater(1, do_pingpong, proto)

    # Call the 'ping' function of the 'demo' module
    d = proto.factory.callRemote(proto, 'demo', 'ping')
    # Add an RPC call handler
    d.addCallback(handle_pong)
    # And our generic error handler
    d.addErrback(error)

def call_hello(proto, name):
    def handle_hello(result):
        print 'Got hello result:', result
        # Erlang strings are lists of numbers
        # The default encoding is Latin1, this might need to be changed if your
        # Erlang node uses another encoding
        text = ''.join(chr(c) for c in result).decode('latin1')
        print 'String form:', text
        # Start pingpong loop
        do_pingpong(proto)

    # Call the 'hello' function of the 'demo' module, and pass in argument
    # 'name'
    d = proto.factory.callRemote(proto, 'demo', 'hello', name)
    # Add a callback for this function call
    d.addCallback(handle_hello)
    # And our generic error handler
    d.addErrback(error)

def launch(epmd, remote, name):
    '''Entry point of our demo application'''
    # Connect to a node. This returns a deferred
    d = epmd.connectToNode(remote)
    # Add a callback, called when the connection to the node is established
    d.addCallback(call_hello, name)
    # And add our generic error handler
    d.addErrback(error)

def main():
    remote = sys.argv[1]
    name = sys.argv[2]
    # Read out the Erlang cookie value
    cookie = twotp.readCookie()
    # Create a name for this node
    this_node = twotp.buildNodeName('demo_client')
    # Connect to EPMD
    epmd = twotp.OneShotPortMapperFactory(this_node, cookie)
    # Call our entry point function when the Twisted reactor is started
    reactor.callWhenRunning(launch, epmd, remote, name)
    # Start the reactor
    reactor.run()

if __name__ == '__main__':
    main()

Finally, to run it, you should first start a server node, and run the ‘pingsrv’ process:

MacBook:pyping nicolas$ erl -sname test@localhost
Erlang (BEAM) emulator version 5.6.5 [source] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.6.5  (abort with ^G)
(test@localhost)1> c(demo).
{ok,demo}
(test@localhost)2> demo:start().
true

Notice we started erl providing test@localhost as short node name.

Now we can launch our client:

(pythonenv)MacBook:pyping nicolas$ python hello.py 'test' Nicolas
Got hello result: [72, 101, 108, 108, 111, 44, 32, 78, 105, 99, 111, 108, 97, 115]
String form: Hello, Nicolas
Got ping result: pong 1
Got ping result: pong 2
Got ping result: pong 3

‘test’ is the shortname of the server node.

You can stop the ping loop using CTRL-C. If you restart the client afterwards, you can see the ping IDs were retained:

(pythonenv)MacBook:pyping nicolas$ python hello.py 'test' Nicolas
Got hello result: [72, 101, 108, 108, 111, 44, 32, 78, 105, 99, 111, 108, 97, 115]
String form: Hello, Nicolas
Got ping result: pong 4
Got ping result: pong 5

That’s about it. Using TwOTP you can also develop a node which exposes functions, which can be called from an Erlang node using rpc:call/4. Check the documentation provided with TwOTP for a basic example of this feature.

Combining Erlang applications as distributed, fault tolerant core infrastructure and Python/Twisted applications for ‘everyday coding’ can be an interesting match in several setups, an TwOTP provides all required functionalities to integrate the 2 platforms easily.

15:28  <eikke> is it possible in linux to access partitions in an losetup’ed raw image?
15:29  <carldani>  eikke: yes, I wrote a kernel patch for that
15:29  <eikke> ah, patch :p i did it using –offset now, but thats kinda hackish
15:29  <carldani>  eikke: the easiest way is to use kpartx
15:29  <carldani>  eikke: that was impossible back then
15:30  <eikke> i see
15:30  <carldani>  eikke: kpartx -a /dev/loop0
15:30  <carldani>  eikke: that will give you /dev/mapper/loop0p1 /dev/mapper/loop0p5 etc
15:30  <eikke> cool
15:30  <carldani>  eikke: are you the eikke responsible for ivman?
15:31  <eikke> a long time ago, yes
15:31  <eikke> dont start the flames please :p
15:31  <carldani>  eikke: thanks! I’m still using it on my laptop

A helps out B, B helps out A, A writes something useful for B, B wrote something used by A, etc. Got to love the open source movement.

import os

def some_func(fd):
    f = os.fdopen(fd, 'w')
    f.write('abc')

fd = get_some_fd()
some_func(fd)
some_other_func(fd)

Here’s what goes wrong: when some_func comes to an end, f (which is a file-like objects) goes out of scope, is destructed, which causes fd to be closed. I think this is pretty weird behavior (an object closing an fd it didn’t open itself), but well.

Here’s a better version, for reference:

def some_func(fd):
    f = os.fdopen(os.dup(fd), 'w')
    #Use f here

Try this on fd 0/1/2 in an (I)Python shell