Tuesday, 5 November 2013

Notes on Learning Meteor.js

I've been experimenting with meteor.js recently, and it's great! The depth and breadth of the experience behind it really shows through in all the details, even at this fairly early stage. There isn't a lot of documentation out there yet, so I thought I'd record my notes here, in case they're helpful to those that follow. Corrections very welcome. Meteor is still changing rapidly, so I'll try to record exactly which version I was using and when.

How to Update Meteor

(Updated 5 Nov 2013 for Meteor 0.6.6.1)

Once you've installed meteor the first time, it looks like you can just run

meteor update
in your project to get it running the latest version.

Private Meteor Packages to Wrap npm Packages

(Updated 5 Nov 2013 for Meteor 0.6.6.3)

Meteor has its own "smart package" system that's mostly separate from Node's npm. The main difference seems to be that the smart package has to tell meteor which packaged files belong on the client, and which packaged files belong on the server. Meteor wrappers for many npm packages are available on the atmosphere repository, but they're not always up to date, and you may want to customise.

Fortunately, you can add private wrapper packages to your project. A good example is this XML2JS package. The steps were as follows. Create a subdirectory under packages, which looks like:

my-project
  packages
    my-package
      my-package.js
      package.js
where, in the most basic case, my-package.js just requires the underlying npm package:
myPackage = Npm.require('my-package');
and package.js defines the meteor package:
Package.describe({
  summary: 'a description of your package'
});

Npm.depends({myPackage: 'x.y.z'});

Package.on_use(function(api) {
  api.export('myPackage'); // required as of Meteor 0.6.5!
  api.add_files('my-package.js', 'server');
});

Then manually add my-package on a line in your .project/packages file.

Then run meteorite with

mrt
to build the private package and install dependencies. This also adds a .gitignore files to your package directory, so you can then git add the packages directory, and it all seems to work.

Sunday, 4 October 2009

The Amazing Ruby: Precompiled Header Hack for Eclipse CDT

With a good IDE, such as Eclipse, and good libraries, such as boost, programming in C++ is almost bearable. Unfortunately, boost's magic templates take a long time to compile. Like most compilers, g++ provides precompiled headers to mitigate this problem, but support for these in Eclipse has so far been limited. This post describes a hack to get some level of precompiled header support in Eclipse with the g++ tool chain on Linux.

How it Works

The usual build process for a C++ project in Eclipse is:

  1. Eclipse writes Makefiles based on the source files in your project, and your project's configuration settings.
  2. Eclipse calls make, and make builds your project.

Here we'll replace step 2 with:

  1. Eclipse calls a ruby script.
  2. The ruby script edits Eclipse's generated Makefiles to include build rules for the precompiled header.
  3. The ruby script calls make, and make builds your project, using the precompiled header as needed.

Using this approach, you can add and remove files from your project or change configuration settings, and things will work mostly as expected.

Caveats

The current limitations of this method are:

  1. The script only supports one precompiled header file per project. It works like Visual Studio, in this regard: you have to supply a header file (stdafx.h) that includes all the headers you want to precompile.

  2. You can only add precompiled header support to one configuration for each project; for example, if you have precompiled headers in the Debug configuration, they won't be used in the Release configuration. This is because the script puts the precompiled header into the source folder, rather than in the build folder.

  3. This is a hack. Your mileage may vary. It may not work in future versions of eclipse.

So, with those caveats in mind, the next section describes how to get it set up.

Tutorial

  1. Make sure you have ruby installed and that you can run it from a terminal (command prompt). These instructions have been tested with Ruby 1.8.7 on Ubuntu 9.04 (Jaunty). You can install ruby via the Synaptic package manager.

  2. Start eclipse. These instructions have been tested with Eclipse 3.5 SR1 (Galileo). I've also used this script with Eclipse 3.4 and 3.5.

  3. You can easily add this script to an existing project using the steps that follow. For this demo, I'll create a new Hello World project, to make things more concrete.

  4. Run the project to make sure it works, before changing things.

  5. Download the cdtgch.rb script. The script is also included in this post, below. Put a copy in the root of your project folder (workspace/cdtgchdemo in this case).

  6. Add a header file that includes the headers you want precompiled. The script assumes that you call it stdafx.h, for consistency with Visual Studio. It also assumes that you have put it in a folder called src, for consistency with the default Eclipse C++ project structure. (See step 8 for a picture of the file structure used in this demo.) You can use any name and folder structure you want, but you will have to edit the first few lines of cdtgch.rb accordingly.

  7. Now it's time to tell eclipse to call cdtgch.rb instead of make. Right click on the project in the Project Explorer and choose Properties. On the left, choose C/C++ Build. Uncheck the Use default build command option, and enter

    ruby ../cdtgch.rb

    as the build command. The ../ is important, because the command runs in the build directory, and the script is in the project root. Click OK.

    Note: This hack only allows you to use precompiled headers with one configuration per project. Here, we'll put it into the Debug configuration, which makes sense, because that's the one that gets built most often (sigh).

  8. Build the project. (Choose Project > Build All.) If you refresh the Project Explorer, you should find a stdafx.h.gch file along side your stdafx.h file; this is the precompiled header. It will be rebuilt every time you change stdafx.h.

  9. Make sure you change your source files to include stdafx.h. It should be the first file that you include. For example, my main C++ file now reads:


    #include "stdafx.h" // was #include <iostream>
    // add other includes here...


    using namespace std;

    int main() {
    cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
    return 0;
    }

    and my stdafx.h now reads:


    #ifndef STDAFX_H_
    #define STDAFX_H_

    #include <iostream> // was in main file

    #endif /* STDAFX_H_ */
  10. Continue developing as normal (but somewhat faster!).

The Ruby Script (cdtgch.rb)


#
# Edits Eclipse's generated Makefiles to make them support a precompiled header.
#
# To use this script:
# 1. Create a file that includes the headers you want to precompile; this script
# assumes that you use my_project/src/stdafx.h, but you can change the PCH
# constant, below, if you want to do it differently.
# 2. Put this script in your project root.
# 3. Edit your project's properties; under C/C++ build, set the build command to
# ruby ../cdtgch.rb
# (the "../" is important because eclipse runs the script from the build
# directory, and the script is in the project root).
# 4. Make sure your source files include "stdafx.h"; it's a good idea to make
# this the first include.
# 5. Everything else should be as normal.
#
# Note that the script only allows you to have *one precompiled header file*.
# Note that you only get to use the gch in *one configuration*.
#
# See
# http://jdleesmiller.blogspot.com/2009/10/amazing-ruby-precompiled-header-hack.html
# for more info.
#

#
# Header file that you want to precompile.
# Path must be relative to the project root.
# The directory containing the stdafx.h must contain at least one .cpp file.
#
PCH = 'src/stdafx.h'

# Look at existing makefile to see if it needs hacking; we will only rewrite
# it if necessary.
rewrite_makefile = false
makefile_lines = IO.readlines('makefile')
makefile_lines.each {|l| l.chomp!}

# Need to import dependency file for the pch. This has to happen after we've
# imported subdir.mk.
dep_line = "CPP_DEPS += #{PCH}.gch.d"
objects_line = makefile_lines.index("-include objects.mk")
raise "cannot find subdir.mk include line" unless objects_line
unless makefile_lines[objects_line+1] == dep_line
makefile_lines.insert(objects_line+1, dep_line)
rewrite_makefile = true
end

# Make all objects depend on the precompiled header (even if not all of them
# really do).
gch_o_rule = "$(OBJS):%.o:../#{PCH}.gch"
unless makefile_lines.member?(gch_o_rule)
makefile_lines << ""
makefile_lines << gch_o_rule
makefile_lines << ""

rewrite_makefile = true
end

# Look for the rule to build the gch. We need to use the same g++ arguments as
# everywhere else; we can get these from a subdir.mk file. The dependencies on
# the project files ensure that the PCH gets rebuilt when the project settings
# change; otherwise, this happens for all the other files, but not the PCH, for
# reasons that I don't fully understand.
gch_rule = "../#{PCH}.gch: ../#{PCH} ../.cproject ../.project"
unless makefile_lines.find {|l| l =~ /^#{gch_rule}/}
# Need to look up the command in the subdir.mk file.
subdir_mk = File.new(File.join(File.dirname(PCH),'subdir.mk')).read
subdir_mk =~ /^(\tg\+\+.*)$/ or raise "cannot find g++ command in subdir.mk"
cmd = $1

# Make the command do dependencies for the gch file.
cmd.gsub! /-MF"[^"]*"/, "-MF\"#{PCH}.gch.d\""
cmd.gsub! /-MT"[^"]*"/, "-MT\"#{PCH}.gch.d\""

# Append a rule for building the precompiled header.
makefile_lines<<""
makefile_lines<<"#{gch_rule}"
makefile_lines<<cmd

rewrite_makefile = true
end

# Add a command to the clean rule so we get rid of the gch-related files.
clean_line = (0...makefile_lines.size).find{|i| makefile_lines[i] =~ /^clean:/}
raise "couldn't find clean: line in makefile" unless clean_line
unless makefile_lines[clean_line+1] =~ /#{PCH}\.gch/
makefile_lines.insert(clean_line+1,
"\trm -f #{PCH}.gch.d ../#{PCH}.gch")
rewrite_makefile = true
end

# Save changes, if any.
if rewrite_makefile
File.open('makefile', 'w') do |f|
f.write makefile_lines.join("\n")
end
end

# Now run make.
exec "make", ARGV.join(' ')

#
# Copyright (c) 2009 John Lees-Miller
#
# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation
# files (the "Software"), to deal in the Software without
# restriction, including without limitation the rights to use,
# copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the
# Software is furnished to do so, subject to the following
# conditions:
#
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
# OTHER DEALINGS IN THE SOFTWARE.
#

Thursday, 21 May 2009

The Amazing Ruby: Rake + EtherPad + LaTeX


Update (20120208): I recently launched writeLaTeX, a service that combines EtherPad with LaTeX preview. Try it out — it's free!


Update (20100518): EtherPad has finally shut down its servers after being acquired by Google, last year. The scripts below may still work (with some changes) with PiratePad, or with a pad that you host yourself, but I haven't tried it out myself.


Update (20090713): The epview AppJet application that I originally used seems to have disappeared. The code has been updated to use EtherPad's new export feature, so it should now be working again.

When I was in primary school, I spent most of my time on the 3 R's: reading, writing and arithmetic. Now I'm a PhD student studying maths; guess how I spend most of my time! The more things change, the more they stay the same, as they say.


One thing that has changed is that I rarely write things on my own, now. Most of my written work is collaborative, and almost all of it involves math. A lot of scientific writing fits this pattern, but I've found that tool support remains limited.


The `old fashioned' way is to pass LaTeX files around by e-mail, but this requires either one-at-a-time editing or manual merging. A better way is to put the document into a shared version control system, but this has high administration overhead, and it still requires lots of external coordination. (It's also almost totally unknown outside of the software engineering community, perhaps because it's not very user-friendly — did you forget to update before you committed?)


Google Docs is pretty good for general collaborative writing, because the document is stored on a central server. The authors can edit simultaneously via their browsers, from wherever in the world they happen to be. The key advantage is that there's one current version of your document; it's always up to date (plus or minus about 10s) and there is no manual merging. As an added bonus, you can easily view the state of your document at any time in the past, so you don't have to worry about losing text if you delete it. The main problem for me is that it has no support for typesetting math, so I just end up writing LaTeX markup in Google Docs. The editor is also a bit clumsy; for example (at least when I last used it), my undo stack reset itself every time someone else made a change.


Enter EtherPad. Again, the document is stored on a central server and edited via a browser, so there is one current version. Unlike Google Docs, it doesn't support images or formatting; it's just a plain text document, but that's fine when writing LaTeX markup. This simplicity allows the collaborative editor to be very responsive; updates are distributed so quickly that two authors can work on the same sentence without stepping on each others' toes. So, it's quite possible to write LaTeX collaboratively in EtherPad. But, there's a problem: you have to get your LaTeX source out of EtherPad so you can compile it; copying and pasting quickly gets tedious.


Enter Ruby. The following Ruby code grabs the current content of your pad. (Note that this code is linked below, so you don't have to copy and paste it.)

# Get the plain text content of an etherpad.
def get_etherpad pad
# Based on http://forums.etherpad.com/viewtopic.php?id=168
url = URI.parse("http://etherpad.com/ep/pad/export/#{pad}/latest?format=txt")
$stderr.print "Getting #{url}... "
s = Net::HTTP.get(url)
$stderr.puts "done."
s.strip
end

For extra streamlining, combine this with a custom Rake (Ruby make) task. (If you're not familiar with the rake or make tools, you might be interested in this article on dependency-based programming, by Martin Fowler.)


# See etherpad_file.

class EtherpadFileTask < Rake::FileTask

  attr_accessor :pad


  def remote_pad

    @remote_pad = get_etherpad(pad) unless @remote_pad

    @remote_pad

  end


  def needed?

    return true unless File.exists?(name)

    local_pad = File.open(name) {|f| f.read}

    return remote_pad != local_pad

  end

end


#

# Task to copy an etherpad to a local file.

# Each time it is invoked, it checks whether the etherpad has changed;

# if it has, the local file is updated; if it hasn't, the local file is

# left alone.

#

def etherpad_file(file_name, pad, &block)

  eft = EtherpadFileTask.define_task({file_name => []}) do |t|

    raise unless t.remote_pad

    File.open(t.name, 'w') {|f| f.write(t.remote_pad)}

    $stderr.puts "Wrote pad #{t.pad} to #{t.name}."

  end

  eft.pad = pad

  eft

end


Then add the following call to your Rakefile, where the Etherpad you want to use has the URL http://etherpad.com/your_pad_id.


etherpad_file 'your_local_file.tex', 'your_pad_id'


Now, when you run the command


rake your_local_file.tex


the script will grab the text from the pad and, if it differs from the local version (if any), it will overwrite the local version with the one from the pad. For even more convenience, add a LaTeX rule to your Rakefile, like:


rule '.pdf' => %w(.tex) do |t|

  tex = t.prerequisites.first

  dvi = tex.sub(/\.tex$/,'.dvi')

  ps = tex.sub(/\.tex$/,'.ps')

  sh <<SH

latex #{tex}

latex #{tex}

latex #{tex}

dvips -o #{ps} #{dvi}

ps2pdf #{ps} #{t}

SH

end


Now, you can run the command


rake your_local_file.pdf


and all the right stuff will happen. When the pad changes, and you run rake, the PDF will be rebuilt. Magic!


Of course, this is still far from the ideal collaborative LaTeX editing solution.

  • There is no syntax highlighting or reference auto-completion in the EtherPad editor.
  • There is no way to attach figures to the document; you have to exchange them some other way.
  • There's no safe way to import the pad into your favorite editor and then export it back again.
  • This method relies on the `epview' application, which may change or cease to exist at any time.
  • This method isn't very efficient; it goes out and gets the whole content of the document to compare with the local copy. All that's needed is the latest modification time, or maybe a hash of the document content.
  • EtherPad currently does not support private pads; anyone who knows the URL can read and edit your pad.

On the plus side, the method works for other text-based data you might stick on a pad. You could conceivably put any kind of code on several different pads and then use rake to compile them together. It would be rather slow, though.


For longer or more serious stuff (like the thesis I should be writing instead of this blog post), my preferred solution is the LyX `what you see is what you mean' (WYSIWYM) editor with version control (e.g. subversion). It may be that LyX will one day support collaborative editing, but so far there doesn't seem to be much progress on this.


For convenience, I've posted a demo Rakefile.rb file on my website, but all of the code you need is on this page.

Tuesday, 16 December 2008

Shuffles, Surprises and Scala

Let's say you want to shuffle an array. This C++ code looks about right:

void exchangeShuffle(int *xs, int n) { // *bad*
  for (int i = 0; i < n; ++i) {
    swap(xs[i], xs[rand() % n]);
  }
}

It compiles, it runs and it even seems to do the right thing. It's Miller Time. Now that you can shuffle cards, you're ready to buy stupiditytax.com from the domain parking trolls, start your online gambling site and profit... or not.

It's a well-documented, but perhaps not well-known, fact that exchangeShuffle yields biased shuffles. In an unbiased shuffle, each of the n!=n(n-1)...(2)(1) distinct orderings of n elements is equally probable. Our exchangeShuffle has nn equally probable possible paths of execution, because there are n possible swaps in each iteration, and there are n iterations. It would produce an unbiased shuffle only if each distinct ordering were the result of an equal number of possible paths of execution; but this can't be, because n! is never an integer divisor of nn for n > 2. 1

The Fisher-Yates shuffle is the preferred way to shuffle a list. In C++, this looks like:

void fisherYatesShuffle(int *xs, int n) {
  for (int i = n; i > 1; --i) {
    swap(xs[i-1], xs[rand() % i]);
  }
}

The Fisher-Yates algorithm satisfies our requirement for n! equally likely paths of execution, because it reduces the number of possible swaps by one in each iteration. It produces unbiased shuffles. (Assuming that your random number source is good enough.)

Think carefully; have you written any bad shuffles recently? I'm afraid I have. You might wonder how bad exchangeShuffle really is. There is at least one theoretical study of this, by Goldstein and Moews. They show that, for a reasonably long list, the most likely outcome is that the exchange shuffle does not change the order of the list at all! That's not good news for your gambling site. 

Before I found that paper, I decided to run some experiments. It seemed like a simple simulation + visualization experiment was in order; where did the elements usually end up? I decided to try this in Scala 2, mainly because Scala ties into Java's Swing GUI toolkit, with which visualization is sometimes less painful than usual. I hope the following will make sense, even if you aren't familiar with Scala.

First, we transcribe the shuffles into Scala and put them into our main application object, called Shuffle.

object Shuffle {
  val rand = new scala.util.Random();

  def swap[T](xs: Array[T], i: Int, j: Int) = {
    val t = xs(i)
    xs(i) = xs(j)
    xs(j) = t
  }

  def exchangeShuffle[T](xs: Array[T]) = {
    for (i <- xs.indices)
      swap(xs, i, rand.nextInt(xs.size))
  }
  
  def fisherYatesShuffle[T](xs: Array[T]) = {
    for (i <- xs.indices.reverse)
      swap(xs, i, rand.nextInt(i + 1))
  }

  // ... visualization code follows ...
}

If you're new to Scala, you might find the following tips helpful. First, Scala uses parentheses (xs(i)) rather than brackets (xs[i]) to index arrays 3. Second, rand.nextInt(k) returns a random integer in the range 0,...,k-1. Third, note that these are generic (template) functions; Array[T] denotes an array whose elements are of an arbitrary type T, like Array<T> in C++ or Java.

Next, we'll need a routine to run the shuffling simulations. A higher-order function is called for; the shuffle parameter takes a procedure as its argument.
  
/**
 * m(i)(j) = number of times the element
 *           at i was shuffled to position j
 */
def measure(n: Int, trials: Int,
            shuffle: Array[Int] => Unit):
             Array[Array[Int]] = {
  // Set up result matrix (all zeros).
  val m = new Array[Array[Int]](n, n);
  
  // Run experiments.
  for (trial <- 1 to trials) {
    val xs = (0 until n).toArray
    shuffle(xs)
    for (i <- xs.indices) {
      m(xs(i))(i) += 1;
    }
  }
   
  return m
}

Row i of the resulting matrix is a histogram recording how many times element i was permuted to each possible position j. Now we're ready to draw it; I'll just put the display code in the main method.

def main(args : Array[String]) : Unit = {
  import java.awt._
  import java.awt.event._
  import javax.swing._

  val trials = 1000000
  val n = 20 // number of elements in array
  var m = new Array[Array[Int]](n,n)
    
  val win = new JFrame("Shuffle")
  val px = 400
  val viz = new JComponent() {
    override def paintComponent(g: Graphics) = {
  val square_px = px / n
      val mAvg = trials / n;
      for (i <- 0 until n; j <- 0 until n) {
        val offset = (127.0 * (m(i)(j) - mAvg)) / mAvg
        val gray = 128 + offset.toInt;
       g.setColor(new Color(gray, gray, gray));
       g.fillRect(square_px * j, square_px * i,
          square_px, square_px)
      }
    }
  }
  viz.setPreferredSize(new Dimension(px, px))
  val controls = new JPanel() {
    val doIt = new JButton("Recompute");
    doIt.addActionListener(new ActionListener() {
      override def actionPerformed(e: ActionEvent) = {
        m = measure(n, trials, exchangeShuffle)
        viz.repaint();
      }
    })
    add(doIt, BorderLayout.WEST);
  }
  win.add(viz, BorderLayout.CENTER)
  win.add(controls, BorderLayout.SOUTH)
  win.pack()
  win.setVisible(true)
}

OK, that was still pretty painful. Scala did some type inference for us, which saved us a little bit of typing when we declared our local variables. Unfortunately, this didn't help us with Swing's action listeners. Man, I hate action listeners; if ever there were a killer application for closures, it's handling user interface events. Anyway, here is the result:



Lighter greys indicate more frequent outcomes. For an unbiased shuffle, the picture would be a uniform grey. In simple terms, it looks like an element is more likely to move a few places backward than a few places forward 4. The largest deviations are typically over +/- 25% from the uniform case. There's a good chance that's significant.

I'll finish with an intriguing aside; note that both of these routines are written in an imperative style. Take a moment to think about how you'd write a shuffle in a functional style. It probably wouldn't look much like exchangeShuffle. Here's mine, in Scala:

def shuffle(xs: List[T]): List[T] = xs match {
  case List() => List()
  case xs => { 
    val i = rand.nextInt(xs.size);
    xs(i) :: shuffle(xs.take(i) ++ xs.drop(i+1))
  }
}

That is, take a random element out of the list, shuffle the rest of the list and cons (::) them together. It's not exactly efficient, but it produces unbiased shuffles. Here, coding in a functional style pushes you toward the right answer. I won't claim that's always true, but I suspect it's not the only example.

Footnotes

1 The reason that n! is never an integer divisor of nn for n > 2 is that n-1 is a factor of n!, and n and n-1 share no prime factors (they are "coprime"), so the prime factorization of n! will always contain some prime factors not in nn. That n and n-1 are coprime follows from a property of integer divisibility: if k divides a and k divides b, then k divides a-b. Applying this property with a=n and b=n-1, we see that a-b=1, so k divides 1, so k=1. That is, 1 is the only common factor of n and n-1, which means they are coprime. Isn't it amazing how even the simplest algorithms have some serious math encoded in them? There's a special case that requires less math: when n is odd, we have that the product of odd numbers is always odd, so nn is odd, but n! is even because it contains the number 2; but, an odd number divided by an even number is never an integer. (These arguments are scattered across the various Wikipedia pages cited in this article; I've just pulled them together here.)

2 Thanks to Ondřej Lhoták for introducing me to Scala.

3 As with most things in Scala, there's a fairly deep reason for this. Scala allows you to treat arrays like functions; both are classes with a method called apply, and the expression xs(i) is defined to be equivalent to xs.apply(i). Functions are treated similarly; the measure method has a parameter shuffle that takes a procedure as its argument; this procedure is just an object with an apply method, and we can call it very cleanly as shuffle(xs). This makes a lot of sense: an array of strings is a function from the non-negative integers to the set of strings. A hash table works the same way; it's a function from the key set to the value set.

4 The theoretical analysis shows that the identity permutation is the most likely. This picture suggests that there are some non-identity permutations with significant probability mass, and that these tend to move each element a couple places backward.

Source Code

Shuffle.scala

package shuffle

object Shuffle {
val rand = new scala.util.Random();

def swap[T](xs: Array[T], i: Int, j: Int) = {
val t = xs(i)
xs(i) = xs(j)
xs(j) = t
}

def exchangeShuffle[T](xs: Array[T]) = {
for (i <- xs.indices)
swap(xs, i, rand.nextInt(xs.size))
}

def fisherYatesShuffle[T](xs: Array[T]) = {
for (i <- xs.indices.reverse)
swap(xs, i, rand.nextInt(i + 1))
}

def functionalShuffle[T](xs: Array[T]) = {
def shuf(xs: List[T]): List[T] = xs match {
case List() => List()
case xs => {
val i = rand.nextInt(xs.size);
xs(i) :: shuf(xs.take(i) ++ xs.drop(i+1))
}
}
shuf(xs.toList).copyToArray(xs, 0)
}

/**
* m(i)(j) = number of times the element at i was shuffled to position j
*/
def measure(n: Int, trials: Int,
shuffle: Array[Int] => Unit): Array[Array[Int]] = {
// Set up result matrix (all zeros).
val m = new Array[Array[Int]](n, n);

// Run experiments.
for (trial <- 1 to trials) {
val xs = (0 until n).toArray
shuffle(xs)
for (j <- xs.indices) {
m(xs(j))(j) += 1;
}
}

return m
}

def printMatrix[T](m: Array[Array[Int]], expected: Int) = {
import scala.Math._
var max_dev = -MAX_DOUBLE;
var min_dev = MAX_DOUBLE;
for (i <- m.indices) {
for (j <- m(i).indices) {
val dev = m(i)(j) / (0.0 + expected)
min_dev = min(dev, min_dev)
max_dev = max(dev, max_dev)
print(dev)
print(" ")
}
println
}
println("min deviation: "+((min_dev-1)*100)+"%")
println("max deviation: "+((max_dev-1)*100)+"%")
}

def main(args : Array[String]) : Unit = {
import java.awt._
import java.awt.event._
import javax.swing._

val trials = 1000000
val n = 20 // number of elements in array
var m = new Array[Array[Int]](n,n)

val win = new JFrame("Shuffle")
val px = 400
val viz = new JComponent() {
override def paintComponent(g: Graphics) = {
val square_px = px / n
val mAvg = trials / n;
for (i <- 0 until n; j <- 0 until n) {
val offset = (127.0 * (m(i)(j) - mAvg)) / mAvg
val gray = 128 + offset.toInt;
g.setColor(new Color(gray, gray, gray));
g.fillRect(square_px * j, square_px * i, square_px, square_px)
}
}
}
viz.setPreferredSize(new Dimension(px, px))
val controls = new JPanel() {
val doIt = new JButton("Recompute");
doIt.addActionListener(new ActionListener() {
override def actionPerformed(e: ActionEvent) = {
m = measure(n, trials, exchangeShuffle)
printMatrix(m, trials / n)
viz.repaint();
}
})
add(doIt, BorderLayout.WEST);
}
win.add(viz, BorderLayout.CENTER)
win.add(controls, BorderLayout.SOUTH)
win.pack()
win.setVisible(true)
}
}

shuffle.cpp

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <iterator>
#include <vector>

using namespace std;

void exchangeShuffle(int *xs, int n) {
for (int i = 0; i < n; ++i) {
swap(xs[i], xs[rand() % n]);
}
}

void fisherYatesShuffle(int *xs, int n) {
for (int i = n; i > 1; --i) {
swap(xs[i-1], xs[rand() % i]);
}
}

void measure(int n, int trials, vector<vector<int> > &m) {
// Set up results matrix, m (all zeros).
m.resize(n);
for (int i = 0; i < n; ++i)
m[i].resize(n, 0);

// Run experiments.
int *xs = new int[n];
for (int trial = 0; trial < trials; ++trial) {
for (int i = 0; i < n; ++i) {
xs[i] = i;
}
exchangeShuffle(xs, n);
for (int j = 0; j < n; ++j) {
m[xs[j]][j] += 1;
}
}
delete [] xs;
}

int main(int argc, char **argv) {
srand(time(NULL));
vector<vector<int> > m;
int n = 10;
int trials = 1000000;
measure(n, trials, m);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cout<<m[i][j] / (trials + 0.0) * n<<" ";
}
cout<<'\n';
}
return EXIT_SUCCESS;
}

Saturday, 3 February 2007

Flirting with Functional Programming

As Bjarne Stroustrup put it, "There are only two kinds of languages: the ones people complain about and the ones nobody uses." Having spent the last 10 years programming in languages that definitely fall into the first category, I'm increasingly curious about those in the latter. And, while it's true that I've developed a mild aversion to the mainstream in many other areas, as well (e.g. in movies and music), I don't think that's all there is to this new interest.

I was raised on a fairly traditional diet of imperative programming. I wrote my first programs in QBASIC with a couple of friends on an old PC at school, around 1995. Then the WWW came along, and I started working with early versions of JavaScript. Then, thanks to the .com boom, I landed a work experience placement as a Visual Basic programmer, around 2000. Then I did some work in C++, because, at the time, it seemed to be the pinnacle of both programming power and programmer prowess. But, computers had crossed a kind of magical threshold, by then: they were so fast and so cheap and had so much memory that even grossly inefficient code was fine for most of the things that users wanted to do. So, I picked up C#. By this time I was studying computer science at university, where we used Java, C and C++.

It wasn't until my third year of university that I had even a vague inkling that there were other ways to tell a computer what to do: I took a course in Lisp and Prolog. I must admit that I didn't really get it, at the time. I studied hard for the exam, and did fine in the course, but I figured it was just sophistry. After all, if it was any good, why were so few people using it?

But, that course on functional programming had some subtle side effects. Afterward, having gone back to working in Java or C++, I frequently found myself staring at an ugly mess of for loops and iterator objects, and thinking, "this would be much better if I could just use a little lambda function and call mapcar." The seed of discontent had been planted, and it was beginning to germinate: I finally started to complain about the programming paradigm that I'd grown up with.

I have not yet decided whether the grass is indeed greener in the functional programming pasture, but I am starting to learn more about it. And, from what I've read, it seems that there are lots of other people at this point, as well. So, here are some interim observations.

I think much of the revived interest in functional languages is due to the better-than-average mainstream penetration of Ruby (in particular, Ruby on Rails). I like Ruby. It provides a pleasing mixture of functional and imperative styles, and it has a familiar syntax and type system. The main reason I haven't used a lot of Ruby for my code at work is its lackluster run-time performance: simulators are programs of the "the faster, the better" variety (provided they are correct, of course). I also wasn't very happy with the available development tools: having smart identifier completion and in-line documentation (e.g. Eclipse) improves my design-time performance dramatically, but it's hard to do it well for dynamically typed languages. I ended up writing my Ruby in VIM, a general text editor that's older than I am. But, both of these stand to improve in the near future.

Having read several of Paul Graham's essays, and done some reading on Wikipedia, I decided that Lisp was definitely on the list of things to learn. I've been working through Peter Seibel's Pratical Common Lisp. I have been quite pleased with it, so far.

I'm also experimenting with Haskell, but I'm in the very early stages.

I'll close with what I think is a very insightful comment from a tutorial by Eric Etheridge, "Haskell for C Programmers:"
If you play around with Haskell, do not merely write toy programs. Simple problems will not take advantage of Haskell's power. Its power shines mostly clearly when you use it to attack difficult tasks. Once Haskell's syntax is familiar to you, write programs that you would ordinarily think of as too complicated. For instance, implement graph-spanning algorithms and balanced-tree data types. At first, you'll probably trudge ahead using 'imperative thought processes'. As you work, you'll hopefully see that Haskell's tools let you dramatically simplify your code.
I think this is a general truth for learning about any programming language that is new to you. Unless you try to do something hard, you'll always think, "So what, I could write that in Blub, just as easily." Most of the canonical functional programming examples found in tutorials and textbooks, like computing Fibonacci sequences and factorials, undersell their language for precisely this reason. (Incidentally, I don't really recommend the rest of the tutorial.)

So, what's my hard something? It's still a bit of a secret...