Tue, 30 Nov 2010

Functional Programing, Tail Call Recursion and Javascript.

About 6 weeks ago, I got an email from Craig Sharkie, who runs the Sydney Javascript group, SydJS. He was contacting me because I run the Sydney functional programing group and he was asking if I knew anyone who might be able to give a presentation about tail call recursion at SydJS. In the spirit of FP-Syd outreach I volunteered to do it, even though I haven't really done all that much Javascript.

On the night, I showed up, had a beer and then presented my slides. I started off explaining what functional programming is and why its is interesting (hint; common language features like garbage collection, dynamic typing, lambda expression and type inference all started in functional languages).

I used the factorial function as an example of function that can be implemented recursively and I demoed the Javascript versions in a web browser. I gave the standard recursive form whose stack usage grows linearly with n: 


  function factorial (n)
  {
      /* Termination condition. */
      if (n <= 1)
          return 1 ;

    /* Recursion. */
      return n * factorial (n - 1) ;
  }

followed by the tail recursive form: 


  function factorial (n)
  {
      function fac_helper (n, fac)
      {
          if (n <= 1)
              return fac ;
          return fac_helper (n - 1, n * fac) ;
      }

      return fac_helper (n, 1) ;
  }

Unfortunately even though this is written in tail recursive form, it still doesn't run in constant stack space. That's because neither the ECMAScript 3 and 5 standards mandate tail call optimisation and few of the Javascript engines implement it.

For languages whose compilers do implement the TCO, the above function will run in constant stack space and I demonstrated this using the same function written in Ocaml: 


  (* Compile using: ocamlopt nums.cmxa mlfactorial.ml -o mlfactorial *)

  open Big_int

  (*
      val mult_int_big_int : int -> big_int -> big_int
          Multiplication of a big integer by a small integer
  *)
  let ($*) = mult_int_big_int

  let factorial n =
      let rec fac_helper x fac =
          if x <= 1 then
              fac
          else
              fac_helper (x - 1) (x $* fac)
      in
      fac_helper n unit_big_int

  let () =
      let n = int_of_string Sys.argv.(1) in
      let facn = factorial n in
      Printf.printf "factorial %d = %s\n" n (string_of_big_int facn)

When this program is run through the Ocaml compiler, the compiler detects that the factorial function is written in tail recursive form and that it can therefore use the Tail Call Optimisation and create a executable that runs in constant stack space. I demostrated the constant stack space usage by running it under valgrind using valgrind's DRD tool: 


  > valgrind --quiet --tool=drd --show-stack-usage=yes ./factorial 5
  factorial 5 = 120
  ==3320== thread 1 finished and used 11728 bytes out of 8388608 on its stack. Margin: 8376880 bytes.
  > valgrind --quiet --tool=drd --show-stack-usage=yes ./factorial 10
  factorial 10 = 3628800
  ==3323== thread 1 finished and used 11728 bytes out of 8388608 on its stack. Margin: 8376880 bytes.
  > valgrind --quiet --tool=drd --show-stack-usage=yes ./factorial 20
  factorial 20 = 2432902008176640000
  ==3326== thread 1 finished and used 11728 bytes out of 8388608 on its stack. Margin: 8376880 bytes.

Regardless of the value of n the stack space used is constant (although, for much larger values of n, the Big_int calculations start easting a little more stack, but thats much less of a problem).

Finally, I showed a way of doing TCO by hand using a technique I found in Spencer Tipping's "Javascipt in Ten Minutes". The solution adds a couple of new properties to the prototype of the Function object to provide delimited continuations (another idea from functional programming). See the the code for the details. Suffice to say that this solution is really elegant and should be safe to run in just about any browser whose Javascript implementation is not completely broken.

As far as I am concerned, my presentation was received very well and the Twitter responses (all two of them) ranged from "brain melting" to "awesome".

I then hung around for the rest of the meeting, had another beer and chatted to people. One interesting part of the meeting was called "Di-script-ions", where a member of the audience would put up small 4-10 line snippets of Javascript code and asked the audience what they did and why. What was surprising to me that for some cases the semantics of a small piece of Javascript code is completely non-obvious. Javascript seems to have some very weird interactions between scoping rules, whether functions are defined directly or as a variable and the sequence of initialisation. Strange indeed.

Anyway, thanks to Craig Sharkie for inviting me. I had a great time.

Posted at: 21:47 | Category: CodeHacking | Permalink