Just sharing some of my inconsequential lunch conversations with you... RSS  

Saturday, November 24, 2007

Ackermann in F#

Ackermann is a recursive function with a tendency to generate large numbers like there's no tomorrow. I've decided to implement it on F# as a part of my learning process.

Here is my first attempt:


let rec ackermann m n =
if m = 0 then
n + 1
else
if n = 0 then
ackermann (m - 1) 1
else
ackermann (m - 1) (ackermann m (n - 1))


Ok, not as impressive as those great samples I've been browsing on the net, but still a challenge to write for an old curly brackets developer. Here's what I found hard:

  • tabs not allowed;
  • initially no brackets or BEGIN/END to create blocks (#light pragma) was a problem; surprising as it may seem, this was easily absorved - now I just love it (probably because I didn't have to code a syntactic analyser for F#);
  • parameters are still hard to code; not just to define, but also to push; no comma here - except for non F# CLR methods...
  • the error messages are not yet natural to me; ex: "found int -> int when expecting int * int"

I confess it took me a some try and error until I got it right - it kind of remember when I learned C back in 1988: try structure.member; doesn't compile? try structure->member; Thank god for the great IDE.

Then I've tried the pattern matching way of live.


let rec ackermann m n =
match m, n with
0, n -> n + 1
| m, 0 -> ackermann (m - 1) 1
| m, n -> ackermann (m - 1) (ackermann m (n - 1))

It seems more FSharpish, right? My next step could very well be a memoization approach, who knows. One thing's for sure: learning a new language is a lesson on humbleness - I feel like a total ignorant! :)

[update]

Here are my results (ok, the table comes from wikipedia):


m\n 0 1 2 3 4
0 1 2 3 4 5
1 2 3 4 5 6
2 3 5 7 9 11
3 5 13 29 61 125
4 13 Stack Fault
Stack Fault Stack Fault
Stack Fault
5 Stack Fault
Stack Fault Stack Fault Stack Fault Stack Fault


The results are not a complete surprise. What comes as a surprise to me is that both my cores were in use during the test. Is it possible?

1 comment:

Unknown said...

Hi,

Interesting post. The function stack overflows because it is not tail recursive. You can create a tail recursive version like so:

#light
let ackermann m n =
let rec ackermann m n acc =
match m, n, acc with
| 0, _, m :: tl -> ackermann m (n + 1) tl
| 0, n, _ -> n + 1
| m, 0, _ -> ackermann (m - 1) 1 acc
| m, n, _ -> ackermann m (n - 1) ((m - 1)::acc)
ackermann m n []

I used this function to succesfully calculate

ackermann 5 0 = 65533

But I got bored trying to calculate "ackermann 4 2" because it took so long. I think interger overflow will soon become problem, you can get round this by chaning the program to use F#'s big integers.

I too observed some usage of my second core. The only explation I can think of is this is the CLR doing an asynchronous garbage collection.

Cheers,
Rob

Development Catharsis :: Copyright 2006 Mário Romano