Monthly Archives: January 2012

Binary search in Clojure

Binary search is an algorithm for finding a target item in a sorted list. As it’s quite a simple algorithm, it makes a nice example for introducing a few features in Clojure.

First, a review of the algorithm. If you haven’t encountered binary search before, it’s a good idea to try it out yourself on paper using a sorted list with around 10 elements in it.

The input to the algorithm is a sorted list which we’ll call numlist (for simplicity, we’ll assume the list contains integers, but the algorithm generalizes easily to any type of data provided methods of ordering the data and testing for equality exist), and a target to be searched for. Then:

  1. Set lower to 0 and upper to (length of list – 1). (Lists, like arrays, are assumed to be indexed from 0.)
  2. Test if lower > upper. If so, target is not found, so return nil.
  3. Calculate mid = (lower + upper)/2 (using integer division).
  4. Find the data stored at location mid and call it midvalue.
  5. If midvalue > target then if target is in the list, it’s in the portion of the list below mid so set upper to mid – 1 and repeat from step 2.
  6. If midvalue < target then if target is in the list, it’s in the portion above mid so set lower to mid + 1 and repeat from step 2.
  7. If midvalue == target, then target has been found, so return mid as the location of target in the list.

The algorithm is naturally recursive, in that each time target isn’t found, the list gets chopped in half (or as near to half as integer division will allow) and the search continues in the truncated portion of the list. It is this halving process that makes binary search an efficient algorithm, with logarithmic behaviour. For a list of length 2^n, it will take at most n comparisons to either find target or prove it’s not present.

The Clojure code looks like this:

(defn binsearch [numlist target]
  (def uppercount (dec (count numlist)))
  (loop [lower 0
        upper uppercount]
    (if (> lower upper) nil
      (let [mid (quot (+ lower upper) 2)
            midvalue (nth numlist mid)]
        (cond
          (> midvalue target) (recur lower (dec mid))
          (< midvalue target) (recur (inc mid) upper)
          (= midvalue target) mid)))))

We’ll step through the code to explain the various features. On line 1, the function binsearch is defined, and it takes two arguments: numlist and target. numlist is a list rather than a single number, while target is a bare number. After loading the function into the REPL, it can be called with a line like

(binsearch '(1 3 4 5 6 7 8) 5)

Note that when giving a list as an argument to a function, you must prefix it with a single quote. This tells the REPL that the list is to be treated as a list of data, and not as a function. If you omit the quote, you’ll get an error stating that ‘1’ (the first element in the list) can’t be defined as a function (the actual error message is #<CompilerException java.lang.ClassCastException: java.lang.Integer cannot be cast to clojure.lang.IFn but that’s what it’s saying).

The output from the above call is just 3, since the target of 5 is found at location 3 in numlist.

Anyway, back to the code. On line 2, we define a variable uppercount as (dec (count numlist)). ‘count’ counts the number of elements in a list, and ‘dec’ decrements its argument by 1, so this statement assigns (size of list – 1) to the variable uppercount.

On line 3, we begin a loop. We discussed loops in an earlier post. Here we initialize lower and upper as instructed by the algorithm. You might wonder, by the way, why we used a separate ‘def’ statement to define uppercount and then use this variable to initialize upper. Why couldn’t we just initialize upper to (dec (count numlist)) directly in the loop’s parameter list? The answer seems to be that there is a bug in the Clojure compiler that complains about a mismatch in data types if you try to put a function call in a loop’s parameter list. At least I’m assuming it’s a bug – there doesn’t seem to be any reason why you shouldn’t be able to do this.

Line 5 implements step 2 in the algorithm, and terminates the function if target is not found. Line 6 opens a let statement, and calculates mid and midvalue. Note the use of the quot function, which calculates the integer quotient, discarding any remainder. Recall that variables defined within a let have a scope that is restricted to the let.

Line 7 uses the nth function to find element number mid in numlist. The ‘nth’ function takes two arguments: the first is a list and the second is an integer giving the index of the required element.

Line 8 starts a ‘cond’ statement, which is a bit like a ‘switch’ statement in Java. A ‘cond’ consists of a series of pairs. Within each pair, the first element must be a predicate (returning true or false), and the second element is code that is to be run if the first element is true. This ‘cond’ tests the 3 conditions in the algorithm above.

If midvalue > target, then we make a recursive call with upper replaced by mid – 1 (remember ‘dec’ from above). Recall that within a loop, the ‘recur’ causes a recursive call to the loop statement, not to the enclosing function, so the loop is re-entered on line 3, with lower unchanged and upper set to (dec mid).

Line 10 handles the case where midvalue < target in a similar way. Line 11 ends the recursion if target has been found, and returns mid as its location in the list.

The ‘cond’ function allows the use of an ‘:else’ clause which is called if all the earlier predicates return false. Thus we could replace (= midvalue target) mid on line 11 by :else mid.

Advertisements

Closures in C#: Lambdas and Predicates

In the last post, we had a look at the Func family of delegates in C#. We saw how a function can be created dynamically within the program and passed as a parameter to another function.

A common requirement in any program that deals with searching a list is that we compare an element of the list with some reference value and return ‘true’ if there is a match or ‘false’ otherwise. A function that performs an operation and returns a boolean value is known in logic as a predicate. C# provides the Predicate delegate type which allows a predicate function to be defined and passed as a parameter to another function.

A Predicate is just a special case of a Func, in that it takes only a single parameter and always returns a bool. Thus Predicate<T> is equivalent to Func<T, bool>. Note, though, that there is only one Predicate delegate, which takes only a single generic type, unlike Func, of which there are 17 varieties for various numbers of input parameters.

As a simple example of the use of a Predicate, we’ll have a look at the built-in List generic type, which is part of the System.Collections.Generic namespace in .NET. Consider the following code.

  class TestClosure
  {
    Predicate<int> intPred;
    private void makePredWithDelegate()
    {
      int compare = 10;
      intPred = delegate(int number)
      {
        return number > compare;
      };
    }

    static void Main(string[] args)
    {
      List<int> intList = new List<int> { 5, -39, 123, 8, 89, 63, 102, -934 };

      TestClosure testClosure = new TestClosure();
      testClosure.makePredWithDelegate();
      List<int> largeNums = intList.FindAll(testClosure.intPred);
      Console.WriteLine("makePredWithDelegate: ");
      foreach (int number in largeNums)
        Console.Write(number + " ");
      Console.WriteLine();
    }
  }

On line 15, we create a List of ints and initialize it with a few numbers. Then we create a TestClosure object on line 17 and call its makePredWithDelegate method. On line 3, we declare a Predicate delegate which points to a function that takes an int as its one argument. The makePredWithDelegate method constructs the Predicate in the same way as we built the Func in the previous post. The Predicate thus tests if number is greater than compare. There are a couple of interesting things about the way we’ve done this.

First, note that we’ve made intPred an instance variable within the TestClosure class, rather than returning it from makePredWithDelegate as we did in discussing Func earlier. Second, we’ve introduced what looks like a pointless local int variable, compare, inside the method, and then used this variable in building the Predicate.

If you recall your scoping rules for local variables, this setup should set off a few alarm bells. We have created intPred inside a method, and we’ve used a local method variable in doing this. Surely when the method call ends, compare will fall out of scope and intPred will therefore contain an invalid reference.

In fact, this is not what happens. When a Predicate (or, more generally, a Func) is created in this way, it captures or encloses the environment that was current when it is created. This means that the compare variable is captured as part of intPred‘s definition and, even though we can’t refer to compare explicitly after the makePredWithDelegate method ends, compare lives on within the Predicate and it will not be garbage-collected until intPred itself falls out of scope. This is what is meant when we say that a closure captures or closes over its environment: all data at the time of the Predicate’s creation are frozen and preserved for the life of the Predicate.

Once we’ve created the Predicate, we can pass it to the FindAll() method on line 19. This method expects a Predicate argument whose data type is the same as the type contained within the List, in this case, an int. The Predicate is used as the test condition for finding objects in the List, and the FindAll() method returns a new list containing all elements in the original list that satisfy the condition. We then just print these out.

Admittedly this is an artificial example, since it’s unlikely we would ever write code like this, but it illustrates the important point that dynamic function creation in C# performs this capturing or closing activity.

While we’re at it, we might as well mention a language feature that was introduced with C# version 3: the lambda. The name ‘lambda’ is taken from ‘lambda calculus’ in logic theory, but basically it’s another name for a closure. In C#, a new operator is introduced to allow concise definitions of predicates, which we’ll illustrate with a brief example.

Insert the following lines of code in the Main() function above, after line 23:

      largeNums = intList.FindAll(num => num > 10);
      Console.WriteLine("Lambda: ");
      foreach (int number in largeNums)
        Console.Write(number + " ");
      Console.WriteLine();

This code actually does the same thing to the intList that the earlier code did, but it’s obviously a lot shorter.  In fact, we’ve replaced the explicit creation of a Predicate object by the single bit of code: num => num > 10. This introduces the lambda operator => which should be read as goes to. You’ll note that the variable num isn’t explicitly declared anywhere; it is in fact declared implicitly by being on the left of the => operator. Its data type is inferred from its location within the FindAll() method: since the method is being called on a List containing ints, this variable is assumed to be an int. In other situations where it isn’t obvious (either to the compiler or the human) what data type is intended, you can state it explicitly as in (int num) => num > 10.

This input parameter is then used in the expression num > 10, which evaluates to a bool value, and is taken as the return value of the function.

What is happening here is that an anonymous function has been created and a Predicate pointing to that function has been overlaid onto it, all in that one concise bit of code.

It is possible to write lambda statements as opposed to the lambda expression we have just written by enclosing the statement(s) within braces in the usual way. A more verbose way of writing the above lambda expression is

      largeNums = intList.FindAll((int num) => { bool result = num > 10; return result; });

It’s important to keep in mind that the => operator returns a delegate, not a function. The delegate points to the function whose code has been written to the right of the => operator. To make this clear, here is yet another way of writing the above code. We can replace the method makePredWithDelegate with another method called makePredWithLambda, which looks like this:

    private void makePredWithLambda()
    {
      int compare = 10;
      intPred = number => number > compare;
    }

This makes an explicit assignment of the result of the => operator to intPred, demonstrating that it has produced a Predicate.

Although in principle we could write an anonymous function of any length as the right operand of the lambda operator, to keep code readable, it’s a good idea to use it only for relatively short functions.

The lambda operator can also be used to create any delegate of the Func type, with any number of arguments up to 16. For example, if we declared a Func that takes two arguments and returns an int:

    Func intFunc;

then we could use a lambda expression to provide a delegate of this type, as in:

      intFunc = (int num, string str) => str.Length + num;

The data type of the result of the expression must match the data type of the Func, of course. We could also use a lambda statement here, provided it returned the correct data type (an int in this case).

Finally, it’s worth knowing that there is parallel set of 17 delegates called Action which mirror the Func delegates except that they point to void functions. These too can be initialized with a lambda expression or statement. For example we can declare a delegate for a void function that takes an int and a string as arguments:

    Action intAction;

We can use a lambda operation to initialize this delegate, provided that the result of the operation is void, as in

      intAction = (int num, string str) => Console.WriteLine("Sum = " + (str.Length + num));

Code for this post available here.

Closures in C#: Funcs

Since I’m trying to learn Clojure, and the name of the language is a variant on the term ‘closure’ (with the ‘j’ inserted since it’s based on Java, I assume), it seems appropriate that I should know what, exactly, a closure is. I’ve poked around the web a fair bit, but I couldn’t find a nice, clear (to me, anyway) explanation of what a closure is. I’ve patched together a bit of an understanding from a few places that posted some examples, so I’ll try to produce something that makes sense to me at this point. Hopefully any closure experts who chance on this page will correct me if my understanding is faulty.

Basically, a closure is a function that is created within a program (rather than being hard-coded before the program is compiled), and that contains the functionality and the data that were current when the function was created. In other words, a closure is a function that captures, or closes over, its environment at the time it was created, and preserves that environment throughout its lifetime.

As I haven’t delved deeply enough into Clojure itself yet, I’ll try to illustrate a closure by using some examples from a language with which I am more familiar: C#. Apologies if this isn’t a language that you know, but I had to start somewhere.

C# contains a feature called a delegate. Most C# programmers will be familiar with delegates as things that are used to handle events, but in fact they have many more applications. I’ll give a quick recap on delegates here (I’ll try to put up a more complete post on them soon). A delegate, as its name implies, delegates work to another function or functions. To declare a delegate, we must specify the signature of the type of function that it can deal with.

A typical delegate declaration is something like this:

public delegate int ArithOperation(int num1, int num2);

This declaration is for a delegate with the name ArithOperation and states that this delegate can refer to functions with two int arguments and an int return type. Note that ArithOperation is not the name of a function; it is the name of the delegate, and is a declared data type.

This delegate can be attached to an ordinary function of the required signature. For example, if we had a function:

  public int Plus(int num1, int num2)
  {
    return num1 + num2;
  }
 

we can then initialize the delegate by writing:

ArithOperation arithOp = new ArithOperation(Plus);

Having made this connection, we can then use the delegate by writing something like this:

int sum = arithOp(3, 4);

The arithOp delegate will pass its arguments along to the Plus() function, which will calculate the sum and return it via the delegate, so that sum becomes 7.

Now all of this might look very clumsy, since we could obviously have just called Plus() directly without using the delegate. However, the power of delegates begins to become apparent when we realize that a delegate can be passed as an argument to a function, whereas a raw function name like Plus cannot. Thus the C# delegate provides a way of passing functions around a program just like any other data types.

To illustrate this, we need a program that’s a bit more involved. A common operation is that of sorting data, and a popular sorting algorithm is quicksort. Don’t worry if you don’t know the quicksort algorithm; I won’t be looking in detail at how it works here. All you need to realize is that in any sorting algorithm, we must have a way of ordering the data, so we need a meaning for the ‘less than’ operation. Typically, data come in various forms (not always as bare numbers), and a program cannot anticipate all the types of data it may be required to sort. Thus the ability to define a ‘lessThan’ function on the fly to cope with some new data type that we wish to sort would be quite useful.

First, we’ll give the code for the quicksort algorithm (again, you don’t need to work through the whole thing to follow what I’m going to say):

  public class Quicksort<T>
  {
    public static List<T> Sort(List<T> data, int left, int right, Func<T, T, bool> lessThan)
    {
      int i = left;
      int j = right;
      int pivotValue = (left + right) / 2;
      T x = data[pivotValue];
      T w;
      while (i <= j)
      {
        while (lessThan(data[i], x))
        {
          i++;
        }
        while (lessThan(x, data[j]))
        {
          j--;
        }
        if (i <= j)
        {
          w = data[i];
          data[i++] = data[j];
          data[j--] = w;
        }
      }
      if (left < j)
      {
        Sort(data, left, j, lessThan);
      }
      if (i < right)
      {
        Sort(data, i, right, lessThan);
      }
      return data;
    }
  }

This code uses C#’s generic data types to allow it to sort any type of data. On line 1, the Quicksort class takes a generic data type T, which is the type of data we want to sort. There is only one method in this class, which performs the quicksort algorithm. Line 3 begins the Sort function, which takes a List (declared as a generic type, also containing elements of type T), two ints (left and right) which indicate which portion of the list to sort (these would be set to the beginning and end of the list on the first pass), and a curious object called Func<T, T, bool> lessThan. As you might guess from its name, this is the lessThan function that will be used to determine the order of two data elements in the list.

Func<T, T, bool> is a pre-defined delegate available with later versions of C#. The signature of the functions that it can connect to must have two arguments, both of type T in this case, and a return type of bool. (There are actually 17 varieties of Func allowing for functions with from zero to 16 arguments, so if your program needs a different number of arguments, just use the corresponding version of Func. If you have more than 16 arguments, you need to refactor your code(!))

Having a delegate as a parameter to the Sort() method means we can choose the lessThan function somewhere else and pass it in as a parameter to the program. (If you’re interested in the innards of the quicksort algorithm, you’ll note that the lessThan function is used on lines 12 and 16. Quicksort is recursive, so the same function must be passed along to subsequent calls to Sort() on lines 29 and 33.)

So how do we create a custom lessThan function? Let’s look at the other class in this program.

  class FuncTest
  {
    static Func<string, string, bool> selectFunc(int choice)
    {
      switch (choice)
      {
        case 1:
          return delegate(string s1, string s2)
          {
            if (s1.Length < s2.Length)
              return true;
            else if (s1.Length > s2.Length)
              return false;
            else
            {
              if (s1.CompareTo(s2) < 0)
                return true;
              return false;
            }
          };
        case 2:
          return delegate(string s1, string s2)
          {
            return s1.CompareTo(s2) < 0;
          };
        default:
          return null;
      }
    }

    static void Main(string[] args)
    {
      List<string> wordList = new List<string>();
      string[] test = "the quick brown fox jumped over the lazy dog".Split(new char[] { ' ' });
      for (int word = 0; word < test.Length; word++)
      {
        wordList.Add(test[word]);
      }

      Console.Write("Sort by size (1) or alphabetical order (2): ");
      int choice = int.Parse(Console.ReadLine());

      Func<string, string, bool> lessThan = selectFunc(choice);
      if (lessThan == null)
      {
        Console.WriteLine("Quitting");
        Environment.Exit(0);
      }
      List<string> sortedList = Quicksort<string>.Sort(wordList, 0, wordList.Count - 1, lessThan);
      for (int word = 0; word < sortedList.Count; word++)
      {
        Console.WriteLine(sortedList[word]);
      }
    }
  }

Let’s start with the Main() function on line 31. To test the program, we’ll use a List of strings, so we create this and populate it with some words on lines 33 to 38. Then we offer the user two options for sorting. First, the words can be sorted by size (so shorter words come before longer ones), or they can be sorted alphabetically. When the choice has been made, we call selectFunc() on line 43. This function will create the correct lessThan function and return it as a delegate to the function code.

Switch your attention now to selectFunc() on line 3. If the user wants the words sorted by size, we build the correct lessThan function on lines 8 through 20. We are constructing an anonymous function (it has no name). On line 8, we use the C# keyword delegate to create a delegate attached to the function code which follows. After writing delegate, we write out the function as usual, beginning with its argument list on line 8, then adding the rest of the code on lines 9 through 20 (not forgetting to put a semi-colon afterwards). The return type of the function is defined implicitly by the return statements in its definition.

If the user wanted alphabetical sorting, we build another delegate in the same way, on lines 22 to 25.

In case you’re wondering what all this has to do with closures, functions created in this way are closures. They are created within the running program, and capture the environment in which they were created. They can also (via their delegates) be passed as parameters to other functions. This is done back in Main() on line 49, where a call to the Sort() method is made, passing along the lessThan delegate we built earlier.

This example shows that closures allow the separation of the logic for accomplishing a given task from the rest of the code. If we wanted to sort other types of data (for example, database records consisting of several data fields, each of a different data type) we can write another function that determines the lessThan condition for such data, and pass that via its delegate into the Sort() function without having to rewrite the sorting routine.

One thing this example hasn’t shown, however, is how a closure captures data that is current when the closure (the function) is defined. But this post has already reached a fair size, so I’ll leave that till the next post.

Code for this post available here.

Loops in Clojure

We saw in the post on recursion in Clojure that the language doesn’t support any loops in the conventional sense. Rather, iteration must be done using recursion, with tail recursion the favoured mechanism. It may come as a surprise that Clojure contains a function called loop. It’s a bit cheeky, since the Clojure loop is really just a shorthand way of doing recursion. To see how this works, first recall the implementation of the power function (for raising a number x to an integer power y) we provided earlier:

(defn power
  ([x y] (power x y 1))
  ([x y current]
  (if (= y 0)
    current
    (if (> y 0)
      (recur x (- y 1) (* x current))
      (recur x (+ y 1) (/ current x))))))

The recursion consists of two steps: an initialization step in which the recursive part of the function is called, with current set to 1 as a starting point, and the recursive part of the function in which the answer is built up by successively multiplying or dividing (depending on whether y is positive or negative) current by x.

The loop function allows us to merge the initialization step into the recursive part of the function, so that only one argument list is required, rather than the two we used above. Let’s see how power is rewritten using loop.

(defn power
  [x y]
  (loop [exponent y
         current 1.0]
    (if (= exponent 0)
      current
      (if (> exponent 0)
        (recur (- exponent 1) (* x current))
        (recur (+ exponent 1) (/ current x))))))

We see that this version of power has a single argument list, taking as input x and y. The loop begins on line 2. A loop’s first argument is a vector (in square brackets) of symbol-value pairs. For each pair, the first element is bound to the second element. So in this example, exponent is bound to the value of y, and current is bound to 1.0.

The second argument of a loop is a statement that is run. Apart from the use of the symbol exponent in place of y, this code is identical to our earlier version. The key point is that when a recur function is encountered, the recursion starts again with the statement within the loop, not with the function that contains the loop. Thus here, the recursion reverts back to line 5, not line 1.

The loop has a superficial resemblance to a for loop in Java. The loop begins with the call to loop, and the pairs in the initialization vector are like the initialization condition in a for loop. The statement following the initialization is like the body of statements in a for loop. However, whereas a for loop has a specific termination condition stated in its first line, a loop can terminate only if the statement it runs recursively contains an anchor step that stops the recursion. In our example here, that condition is the test to see if exponent is zero on line 5. Just as it is possible to write an infinite loop in Java, so it is possible in Clojure if there is no anchor step, or the anchor step is never reached. As always, it’s up to the programmer to ensure this doesn’t happen.

We can expand this example a bit by applying the power function in another function. A method originally due to Newton for finding the nth root of a number goes like this. To find the nth root of number to within a tolerance tol:

  1. Make an initial guess of 1.0 for the root.
  2. Calculate guess to the nth power.
  3. Calculate the absolute value of the difference between number and guess to the nth power.
  4. If this difference is less than tol, return guess as the answer.
  5. If not, take the average of guess and number/(guess^(n-1)) as the next guess and repeat from step 2.
To implement this algorithm, we’ll need a few auxiliary functions; one for calculating the absolute value, one for calculating the average of two numbers and one for checking if a guess is within the tolerance. None of these is recursive, so we can just give their code:
(defn abs
  "Absolute value of argument"
  [n]
  (if (< n 0)
    (* n -1)
    n))

(defn avg
  "Average of two arguments"
  [a b]
  (/ (+ a b) 2))

(defn within-tol?
    "Is guess^n within tolerance of number?"
  [number n tol guess]
  (let [diff (- (power guess n) number)]
    (if (< (abs diff) tol)
      true
      false)))

Hopefully, these are fairly straightforward so we don’t need to comment on them. (OK, there are probably more succinct ways in which these could be implemented in Clojure, but I’m sticking to the elementary techniques we’ve looked at so far.)

One thing is worthy of note, however. Note that the name of the function for testing the tolerance ends with a question mark. Clojure allows more characters to be part of symbol names than most languages. The rules are

  • Symbol names may contain any alphanumeric character (although they cannot begin with a number).
  • Names may also contain the characters * + ! – _ and ?
  • A colon : is also allowed, but not at the beginning or end of the name, and it is not allowed to be repeated within the name. (Actually, colons are probably best avoided…)

For example, a function that returns a boolean result can end in a question mark, since it is determining whether some condition is true or false. The within-tol? function above does just that.

Anyway, with these functions in place, we can write the main function that uses a loop to calculate the nth root of a number:

(defn nth-root
  "Calculates the nth root of number to a tolerance tol"
  [number n tol]
  (loop [guess 1.0]
    (if (within-tol? number n tol guess)
      guess
      (recur (avg guess (/ number (power guess (- n 1))))))))

The function takes 3 arguments: the number, the value of n that specifies which root is to be calculated, and the tolerance to which we want the answer. The loop initializes guess to 1.0. The body of the loop first checks to see if the guess is within the tolerance (this is the anchor step that will stop the recursion), and, if so, returns the current guess as the answer.

If the answer isn’t yet good enough, a recursive call is made to the loop with the new guess as specified in the algorithm above.

As you might expect, the program takes longer to run as you either increase n or decrease the tolerance tol. This is due to the mathematics behind the algorithm: Newton’s method isn’t the most efficient method for finding roots if a high precision is needed. However, it’s a good exercise in recursion.

Dragging shapes with the mouse in WPF

In the last post we saw what happens when the mouse is used to click on a Button. The mouse is, of course, often used  to select a particular point on the interface. A common feature is that of dragging an object from one location to another (often as part of a drag and drop operation, but that’s a bit more advanced so we’ll leave that for a future post). Here we have a look at a simple application in which the mouse can be used to drag two shapes around.

Although most of the action happens in the event handlers, we can start the project as usual in Expression Blend (EB). After the project is created, the first thing we need to do is to change the layout type. To do this right-click on LayoutRoot (the default Grid layout that is provided for you when you create a project) and select “Change Layout Type”. Change the layout to a Canvas. A Canvas layout is one in which all elements must be placed manually, that is, (x,y) coordinates must be given for each component. Although this sort of layout might seem easier than having to cope with the vagaries of a Grid, it lacks any flexibility so that if the window is resized, for example, components will appear badly aligned or, if the window is made smaller, they could become cropped or disappear altogether. However, for images and drawings, the Canvas is usually the best layout to use.

To finish the setup, add an ellipse and a circle to the Canvas. It doesn’t matter where you put them since the aim of this program is to allow them to be moved around. However, it’s a good idea if they don’t overlap in the initial setup. In our example, we placed the square at location (10,10) (that is, 10 units to the left and down from the top-left corner), and the ellipse at (200,100). We also made the square red and the ellipse blue. The initial layout looks like this:

We would like to be able to click the left button of the mouse over one of the shapes and then drag that shape around the Canvas, with the shape remaining in the new position when the button is released. We therefore need to handle 3 events: MouseLeftButtonDown, MouseMove and MouseLeftButtonUp. We will write these event handlers in such a way that the same event handlers can be used for both shapes. In EB, use the Events panel for the ellipse to add handlers for these 3 events. Give them obvious names, like shape_MouseLeftButtonDown, etc. Then select the Rectangle and give the same 3 events the same handlers as those you gave the ellipse.

If you’ve set things up properly, Visual Studio (VS) will open to let you edit the handler code in the C# file that lies behind the XAML for the main window. Here’s the code for the first bit of the class, including MouseLeftButtonDown:

  public partial class MainWindow : Window
  {
    public MainWindow()
    {
      InitializeComponent();
    }

    bool captured = false;
    double x_shape, x_canvas, y_shape, y_canvas;
    UIElement source = null;

    private void shape_MouseLeftButtonDown(object sender, MouseButtonEventArgs e)
    {
      source = (UIElement)sender;
      Mouse.Capture(source);
      captured = true;
      x_shape = Canvas.GetLeft(source);
      x_canvas = e.GetPosition(LayoutRoot).X;
      y_shape = Canvas.GetTop(source);
      y_canvas = e.GetPosition(LayoutRoot).Y;
    }

On lines 8 to 10, we declare a few variables that we’ll use throughout the class, and we’ll explain them as we go along.

First, we want to make the handlers generic so they can be used with both shapes. The source object is declared as a UIElement, which is the base class of all user-interface elements, and is what the Canvas functions expect as arguments. When the left mouse button is pressed, calling the handler that starts on line 12, it will provide the object that triggered the event as the sender argument in the handler. On line 14, we cast this into a UIElement.

On line 15, we capture the mouse, binding it to the shape over which it was clicked. This means that all mouse events will relate to that shape, even if the mouse should be moved outside the Canvas. We’ll see later what difference this makes.

Next, we set a boolean flag captured to true, indicating that the mouse is captured, and that the left button has been pressed.

The remainder of the code, on lines 17 through 20, records the (x,y) coordinates of source (the shape) relative to LayoutRoot (the Canvas) in doubles (x_shape, y_shape). It also records the position of the mouse relative to LayoutRoot, storing this in (x_canvas, y_canvas). Note that the mouse position is obtained by calling GetPosition() from the MouseButtonEventArgs parameter passed to the hander.

We’ve now captured the mouse with the selected shape and recorded the position of the shape and the mouse when the left button was pressed. In the MouseMove handler, we do the moving of the shape.

    private void shape_MouseMove(object sender, MouseEventArgs e)
    {
      if (captured)
      {
        double x = e.GetPosition(LayoutRoot).X;
        double y = e.GetPosition(LayoutRoot).Y;
        x_shape += x - x_canvas;
        Canvas.SetLeft(source, x_shape);
        x_canvas = x;
        y_shape += y - y_canvas;
        Canvas.SetTop(source, y_shape);
        y_canvas = y;
      }
    }

We want the shape to move only if the left mouse button is down, so we check the captured flag on line 3. Next, we obtain the current position of the mouse on lines 5 and 6. Then we calculate what the new coordinates of the shape should be and use the static functions in Canvas to set the new position. We also update x_canvas and y_canvas so they can be used to calculate how much to move the shape the next time the MouseMove handler is called. The MouseMove handler is called only every so often as the mouse is moved, so you won’t get a call every time a coordinate value changes (unless you move the mouse very slowly), but unless you move the mouse very quickly, the motion will appear smooth.

Finally, we need the handler for releasing the mouse button. This is quite simple:

    private void shape_MouseLeftButtonUp(object sender, MouseButtonEventArgs e)
    {
      Mouse.Capture(null);
      captured = false;
    }

We have to ‘uncapture’ the mouse which we do by calling Capture() with a null argument, and we turn off the captured flag. That’s it for the code.

Finally, we promised we’d explain what difference capturing the mouse would make. This is easy enough to test; we merely comment out the call to Mouse.Capture(source) on line 15 in the MouseLeftButtonDown code above. The program appears to run properly, but note if you drag a shape and let the mouse go outside the Canvas, the shape will stop moving as soon as the mouse leaves the Canvas. If you put the call to Capture(source) back in, you’ll see the shape continue to move even after the mouse has left the Canvas. This latter behaviour is because the shape has sole use of the mouse when it captures it, so mouse move events are still routed back to the handler for that shape. If the shape did not capture the shape, then mouse events are routed to whatever is outside the Canvas when the mouse leaves the Canvas, and the shape stops moving.

Complete project files for this example are here.

The let statement in Clojure

Clojure’s method of assigning a symbol to the result of an expression will look a bit alien to those us used to imperative languages like Java. In Java, to assign a value to a variable, we say something like x = 42;, but in Clojure doing something like this is a bit more involved.

Clojure provides the let statement for assignment. The syntax of let is:

(let [vector of name-value pairs] (expression))

The vector of name-value pairs is the list of assignments that let is to make, and the expression can be any Clojure expression. A simple example will show how this works.

(defn let-test
  [number]
  (let [x number
        y (* x x)]
    (println "x = " x ". y = " y)))

Here we define a function called let-test which takes one argument, number. Then we have a let statement. Its vector contains two name-value pairs. The first pair assigns number to the symbol x, and the second pair assigns (* x x) (that is, x squared) to the symbol y. Finally, we use println to print out the values of x and y. If we test this from the REPL, we get

user=> (let-test 42)
x =  42 . y =  1764
nil

It is important to realize that the assignments that take place within a let have a scope that is restricted to the let statement. For example, if we had placed the println statement outside the let, we would get a compilation error, since x and y are undefined outside the let. In this respect, let is not equivalent to the simple assignment statements in Java, where an assignment’s scope lasts from the line in which it is made to the end of the function (assuming it is not superseded by another assignment statement).

The let statement can be used to make code more readable and understandable, even if it does make code a bit longer. As an example of a more extended use of let, consider the algorithm for calculating the date of Easter, given the year. Various algorithms exist, some of which give the date in the Gregorian calendar (the one commonly used in the West today) and others in the Julian calendar. We’ll have a look at one of the Gregorian algorithms (the ‘anonymous Gregorian algorithm’ given here). The algorithm uses only arithmetic, but is quite complicated, although it would be easy enough to code it in Java from the version given in the Wikipedia article. In Clojure, we’ll use let to make the assignments to each of the variables given in the algorithm, then print out the date of Easter at the end. The result is as follows.

(ns glenn.rowe.Easter
	(:require clojure.contrib.math)
)
(use 'clojure.contrib.math)
(defn easter
  [year]
  (let [a (rem year 19)
        b (floor (/ year 100))
        c (rem year 100)
        d (floor (/ b 4))
        e (rem b 4)
        f (floor (/ (+ b 8) 25))
        g (floor (/ (+ (- b f) 1) 3))
        h (rem (+ (- (- (+ (* 19 a) b) d) g) 15) 30)
        i (floor (/ c 4))
        k (rem c 4)
        L (rem (- (- (+ (+ 32 (* 2 e)) (* 2 i)) h) k) 7)
        m (floor (/ (+ (+ a (* 11 h)) (* 22 L)) 451))
        month (floor (/ (+ (- (+ h L) (* 7 m)) 114) 31))
        day (+ (rem (+ (- (+ h L) (* 7 m)) 114) 31) 1)]
    (println day "/" month "/" year)))

This code introduces the Clojure math library, so it’s useful to see how it is referenced. In the ns statement at the start, we’ve added a require clause, stating that the clojure.contrib.math library is needed for this program. The clojure.contrib library is a standard part of Clojure, so it will have been installed when you installed Clojure, and should be available.

On line 4, the use statement tells the program that functions in clojure.contrib.math are to be used in the code, so we can call these functions just by using their bare name. In fact, the only such function we need is the floor function, which returns the largest integer less than or equal to its single argument. (There is a built-in function called quot which will perform integer division and discard the remainder, so we could have said (quot year 100) instead of (floor (/ year 100)) without using the math library, but I wanted to see how to call functions in the math library.)

The rest of the code is a fairly straightforward translation of the algorithm into Clojure arithmetic functions. The rem function on line 7 is Clojure’s modulus function: (rem x y) returns the remainder when integer x is divided by integer y (it’s equivalent to the % operator in Java). The rem function is part of the Clojure core, so the math library isn’t needed for it.

You can see that let allows a whole series of symbols to be assigned in pairs, by stating the symbol and then the expression whose return value is to be assigned to that symbol. Again, remember that the println statement at the end must be inside the let statement. (American readers will probably want to reverse the ‘day’ and ‘month’ bits of the output.)

WPF event handling: anatomy of a button click

We’ve seen a simple example of how to add an event handler in WPF. However, a glance at the list of events available for any object shows that WPF provides a lot of flexibility in how you handle a user action such as pressing a Button with a mouse click. We’ll have a look at some of those features here.

First, we need to mention that it is possible, and in fact easy, to add pretty well any content to a Button. By default, a Button contains some text as its Content, but that can be replaced by as complex a layout as you wish. As an example, we’ll create a Button whose content is a Grid, and the Grid in turn contains two cells, one of which contains a coloured square, and the other of which contains a TextBlock.

In Expression Blend (EB) we create a project and insert a single Button in the top-level Grid (the one named LayoutRoot by default). Centre the Button in the window. Turn off the Focusable property if you don’t want the Button to flash after it’s clicked. Now, using the Assets button (with a double chevron symbol) in the EB toolbar on the left, find a Grid and add it to the Button as its Content. In the Layout panel (under Properties, on the right) add one row and two columns to the Grid.

In column 0, add a Rectangle, and give it a size of 50 by 50, with a background colour of pure green (RGB = 0, 255, 0). In column 1, add a TextBlock, centre it horizontally and vertically, give it a margin of 5 all round, and set its text to “Press the square”. The result should look like this:

You can run the program at this point, and you should find that the button is pressable, but of course nothing will happen since we haven’t added any event handlers.

We’ve seen that you can add the standard handler for the Click event, which is triggered when the mouse’s left button is pressed and then released over the button. However, WPF actually gives you much finer control over events. Any component on a display, not just controls such as Buttons, can give rise to events. Thus in our example, the Button itself, the Grid it contains, and the Rectangle and TextBlock within the Grid can all give rise to events.

To understand how these events arise and what you can do with them, we need to remember that compound objects like the Button containing graphics are structured as a tree. In the example, the Button is the root of the tree. The Grid is the single child of the Button, and the Rectangle and TextBlock are children of the Grid. If the mouse’s left button is clicked over the Rectangle, say, then events are generated for the Rectangle, the Grid that contains it, and the Button that contains the Grid.

For some events, such as a mouse click, there are two types of events: tunneling and bubbling. Tunneling events are generated by starting at the root of the tree that contains the object over which the mouse was clicked, and then travelling down the tree until the object itself is found. Thus clicking the mouse over the Rectangle generates an event first in the Button, then in the Grid and finally in the Rectangle itself. All tunneling events have names beginning with ‘Preview’. Thus pressing the left mouse button generates tunneling events called PreviewMouseLeftButtonDown.

Once the specific object over which the mouse was clicked is located in the tree, a series of bubbling events is generated. Bubbling events are generated in the opposite order to tunneling events, so they start at the node in the tree corresponding to the object over which the mouse was clicked, and then travel up the tree, ending at the root. Typically, each tunneling event has a matching bubbling event, whose name is the same as that of the tunneling event but without the ‘Preview’ at the start. Thus the bubbling event for pressing the left mouse button is MouseLeftButtonDown.

The easiest way to see these events is to add handlers to all of them, and get each handler to print out a message when it is called. In EB, select each of the Button, Grid, square and TextBlock in turn, and add handlers for PreviewMouseLeftButtonDown and MouseLeftButtonDown. 

One way to see textual output from a program is to make the application a Console application, as we mentioned earlier. A somewhat more professional way is to run the project in debug mode in Visual Studio (VS), and use the System.Diagnostics.Debug class to generate some text. To do this, add the line

using System.Diagnostics;

at the top of the C# code file. Then a typical event handler would look like this (for the tunneling event generated by pressing the left mouse button over the square:

    private void Square_PreviewMouseLeftButtonDown(object sender, MouseButtonEventArgs e)
    {
      Debug.WriteLine("Square_PreviewMouseLeftButtonDown");
    }

You can write similar handlers for all the other events. When the program is run in VS under Debug mode, look in the Output window at the bottom to see the output from these Debug statements.

Try clicking on various parts of the Button and look at the output. If you click over the green square, you’ll see that 3 tunneling events are generated, for the Button, then the Grid and finally the Rectangle. Following this, you will see 2 bubbling events, first for the Rectangle and then the Grid. The Button itself doesn’t get a bubbling event for mouse down, since WPF combines the mouse down with the mouse up events to generate a Click event, which is the one most commonly handled for a Button.

In practice, the tunneling events aren’t used that much, but they are useful to have in some situations. For example, you may want to change something at the root level in the tree before an event is handled by a lower-down component.

Sometimes, you may want to catch an event at a higher level and prevent any further processing of that event by lower level components. You can do this by setting the event’s Handled flag to ‘true’. In the sample of an event handler above, you’ll notice that the second argument to the handler is an object of class MouseButtonEventArgs. You can use this object to set the Handled flag by inserting this line in the handler:

  e.Handled = true;

Try inserting that line in the Preview handler for the Grid and then run the program again. If you click on the square you’ll see that the Preview handlers for the Button and Grid are generated, but no further event handlers are called.

You will also notice that the first argument to the event handler method is called sender. This is the object that contains the actual component that generated the event. In our example, sender will correspond to the level in the tree at which the event is generated. For example, if we are in the handler for the Button’sPreviewMouseLeftButtonDown event and we click on the square, then sender will be the Button, not the square.

If you want to know the actual component that generated the event no matter where in the tree we are, this is contained in the MouseButtonEventArgs object, in its Source field. We can see both of these objects, sender and source, by adding a bit to the Debug statements in each handler. For example, we can write the handler for the Button’s PreviewMouseLeftButtonDown as follows.

    private void Button_PreviewMouseLeftButtonDown(object sender, MouseButtonEventArgs e)
    {
      Debug.WriteLine("Button_PreviewMouseLeftButtonDown sender: " + sender.ToString()
        + "; Source: " + e.Source.ToString());
    }

Calling the ToString() method of the objects here will return the class name of the object, so you can see which type of object it is. In the code shown, this handler will print out:

Button_PreviewMouseLeftButtonDown sender: System.Windows.Controls.Button; Source: System.Windows.Shapes.Rectangle

As an example of how these features might be used, suppose we wanted to change the colour of the square, but only if the user clicks directly on the square and not any other part of the button. We could put the code for doing this in the bubbling event handler for the square:

    SolidColorBrush RosyBrownBrush = new SolidColorBrush(Colors.RosyBrown);
    SolidColorBrush LimeBrush = new SolidColorBrush(Colors.Lime);
    private void Square_MouseLeftButtonDown(object sender, MouseButtonEventArgs e)
    {
      Debug.WriteLine("Square_MouseLeftButtonDown sender: " + sender.ToString()
        + "; Source: " + e.Source.ToString());
      if (!Square.Fill.Equals(RosyBrownBrush))
      {
        Square.Fill = RosyBrownBrush;
      }
      else
      {
        Square.Fill = LimeBrush;
      }
      ButtonText.Text = "Press the square";
      e.Handled = true;
    }

We define a couple of colours from the Colors class (which contains a large number of pre-defined colours with given names). The if statement on line 7 will swap the square’s colour between RosyBrown and Lime. On line 15, we reset the text of the TextBlock (we change it in another handler to be seen shortly). Finally, we set the event to Handled to prevent any further processing.

We want to catch any other mouse click that is inside the Button but not over the square, and print a helpful message for the user reminding him to click on the square. To put this message in the right place, we need to remember the order in which events are generated. Tunneling events are generated from the top down, starting with the Button. Bubbling events are generated from the bottom up, starting with either the Rectangle or the TextBlock.

We might think, therefore, that we can place the message code in the bubbling handler for the Grid, since the Grid lies behind both the Rectangle and TextBlock. So our first attempt might be something like this:

    private void Grid_MouseLeftButtonDown(object sender, MouseButtonEventArgs e)
    {
      Debug.WriteLine("Grid_MouseLeftButtonDown sender: " + sender.ToString()
        + "; Source: " + e.Source.ToString());
      Square.Fill = new SolidColorBrush(Colors.Red);
      ButtonText.Text = "The SQUARE, idiot!";
    }

This sets the square to red as a warning, and changes the TextBlock’s text. We find that if we click directly over the current TextBlock text, this works, but if we click over the empty space within the Button above or below the text, nothing happens.

This is because the Grid cells size themselves to fit round the elements they contain, so the cell containing the TextBlock exists only behind the TextBlock itself and doesn’t extend to the top and bottom of the Button. We could try fiddling with the Grid’s settings to fix this, but in this case there’s an easier way.

Our next thought might be to put the code in the handler for the button’s MouseLeftButtonDown event, but remember that this event doesn’t get triggered for a Button, so again nothing will happen. We can solve the problem by putting the code in the Click event handler for the Button, since this doesn’t get called until the mouse button is released. Thus we get:

    private void Button_Click(object sender, RoutedEventArgs e)
    {
      Debug.WriteLine("Button_Click sender: " + sender.ToString()
        + "; Source: " + e.Source.ToString());
      Square.Fill = new SolidColorBrush(Colors.Red);
      ButtonText.Text = "The SQUARE, idiot!";
    }

This works no matter where outside the square the mouse is clicked. Remember that we stopped the event from further processing in the square’s event handler, so if we click over the square, the Button’s Click handler is never called.

Complete project files for this example are available here.

Recursion in Clojure

One of the hardest things for a non-functional programmer to get used to in a functional language like Clojure is the absence of loops. We OO and procedural programmers are so used to calling for loops to do any sort of repetitive task that when this is pulled out from under our feet, we’re left floundering.

Clojure replaces loops with recursion, which is the process of a function calling itself. Most OO and procedural programming languages such as Java also support recursion, but it is not often used except in specialized situations where the algorithms being implemented are explicitly recursive (binary trees are a good example of this). Recursion, we are told, is an inefficient way of implementing reptitive tasks and should be avoided unless it really does clarify the code.

The simplest examples of recursion typically involve elementary arithmetic, so we’ll have a look at one such problem: raising a number to an integer power. Suppose we wish to raise the number x to the power y. A typical bit of procedural code for doing this would be:

double result = 1.0;
for (int i = 0; i < y; i++)
{
  result = result * x;
}

After the loop, the answer is stored in result.

How would we do this recursively? There are two main parts of a recursive algorithm. First, we need a base or anchor condition, which provides a termination condition for the algorithm. Second, we need a recursive step, in which a function will call itself. The recursive step must be such that each step takes the calculation closer to the anchor condition.

In the case of raising x to the power y, the anchor step is when y has the value 0. In this case, the answer will always be 1 (unless x=0, in which case the answer isn’t defined, but we’ll assume x isn’t 0 here). For the recursive step, we note that (assuming y>0) x to the power y is x times x to the power (y-1). That is, if the function we’re evaluating is f(x,y), then f(x,y)=x*f(x,y-1). We can see that this takes y one step closer to the anchor condition of y=0.

Our first implementation of such a function in Clojure might look like this (the reason for calling the function bad_power will become apparent afterwards):

(defn bad_power
  ([x y]
    (if (= y 0)
      1
      (* x (bad_power x (- y 1))))))

This function introduces the if statement, which has the general form (if a b c). Here ‘a’ is the condition to test, ‘b’ is what to return if ‘a’ is true, and ‘c’ is an optional third argument which is returned if ‘a’ is false.

Thus bad_power takes two arguments, x and y. The if statement tests if the anchor condition is true (is y=0?). If it is, we return 1 immediately and that’s the end of the function. If it isn’t, then the last line is run. This multiplies x by a recursive call to bad_power with arguments of x and y-1.

Running this program produces the expected result, as in (bad_power 2 3) gives the answer 8.

Now, why have we called this function bad_power? It seems to work well enough. The answer is a bit technical, and deals with the way recursion is implemented.

In a running program, each function call pushes the current state of the program onto a stack, with execution jumping to a new instance of the function that is called. When the function call ends, the previous state of the program is popped off the stack and execution continues from that point. This all works well enough if function calls are sequential: program starts, function A is called, then returns, then function B is called and returns and so on. In this case, the stack never gets very deep since each function ends before the next one is called.

In the case of recursion, however, a function will call itself a potentially large number of times before any of these calls returns, and for each call, a separate instance of the program state must be saved on the stack. In the bad_power function, there will be y instances of the function called before any of them returns, so if we want to calculate a large power, the stack will get very deep.

Any computer will have a limit to the size of this stack, so if we give it too many recursive calls, we’ll get a stack overflow. The limit of a stack varies from one machine to another, but usually you’ll hit the limit with around 5000 calls. Try it with this function by giving it a large exponent. On my machine raising 2 to the power of 2000 runs OK, but 3000 causes a stack overflow.

We can see that this problem doesn’t arise with a loop in a language like Java, since no function calls are made, and the result is built up by saving the value in a single variable. Since loops are to be replaced by recursion in Clojure, and some loops can be many thousands of iterations in length, how can we get recursion to work properly without causing a stack overflow?

Tail recursion

The answer is that recursive algorithms have to be written in a special way called tail recursion. If we examine the algorithm above, we see that the result of each recursive call is needed, since this result is multiplied by x before being passed back up to the next function in the chain. If we could rewrite the algorithm in a way that didn’t require saving each recursive call until the end of the recursion, then we could throw away each function after it made its recursive call to the next function in the chain. The final answer is obtained when the bottom of the recursive chain is reached, so there is no need to climb all the way back up to the top of the chain again, as there was in the example above.

If we can arrange things in this way, the resulting algorithm is called tail recursive. How can we rewrite the bad_power function to be tail recursive? The answer is as follows, with additions to allow negative exponents to be handled as well:

(defn power
  ([x y] (power x y 1))
  ([x y current]
  (if (= y 0)
    current
    (if (> y 0)
      (power x (- y 1) (* x current))
      (power x (+ y 1) (/ current x))))))

The function uses multiple arity, so we’d better explain that first. Basically multiple arity allows a function to take a variable number of arguments (so it’s like function overloading in Java). In this case, power can take either two or three arguments. If it is given two arguments, the code on line 2 is run, which is a recursive call to power, but this time with 3 arguments. This will call the code starting on line 3, in which the symbol current is initialized to 1, and x and y are just passed along as they are.

On line 4, we test the anchor condition as before, but this time, if y=0, we return current. We can see this works if the initial value of y is 0, since it will just return 1.

If y isn’t 0, we then test to see if y>0. If so, we then recursively call power, passing x along unchanged, but reducing y by 1, as before. This time, however, we perform the incremental calculation by multiplying current by x and passing this along as the new value of current in the recursive call. Note that the return value of this recursive call is not used in any further calculations, so the value of this call need not be saved. All the required information is passed along to the next recursive call in the chain, so we can just forget about the current function. This means that it need not be stored on the stack.

The last line of this function adds some code that calculates x raised to a negative exponent, but it works in exactly the same way so it too is tail recursive.

Now, if you run this code, you might expect to be able to calculate much higher exponents than with bad_power, but you’d be disappointed. It still chokes on high exponent values. Why?

It turns out that the Clojure compiler does not automatically optimize tail recursive functions; it must be told to do so. This is easy enough to do: we replace the explicit name of the function in the recursive call by the keyword recur. The final version of the function thus looks like this:

(defn power
  ([x y] (power x y 1))
  ([x y current]
  (if (= y 0)
    current
    (if (> y 0)
      (recur x (- y 1) (* x current))
      (recur x (+ y 1) (/ current x))))))

The only changes we have made are the insertion of the recur keywords on lines 7 and 8. Now, finally, if you run this program, you can enter enormous exponents and the program doesn’t choke.

Incidentally, you might notice that Clojure can handle some truly huge numbers. Raising 2 to the power of 5000 gives an answer of 14124670321394260368352096670161473336688961751845411168136880858

5711816984270751255808912631671152637335603208431366082764203838

0699793383359711857266399234310517778518653990118779996451317070

69373498212631323752553111215372844035950900535954860733418453405

575566736801565587405464699640499050849699472357900905617571376

61822821643421318152099155667712649865178220417406183093923917686

1341383294018240225838692725596147005144243281075275629495339093

81319896673563360632969102384245412583588865687313398128724098000

8838073668221804264432910894030789020219440578198488267339768238

872279902157420307247570510423845868872596735891805818727796435

7530185180866413560128513025467268230092502183280182519073402454

49863183265637987862198511046362985461949587281119139907228004385

94288095395881655456762529608691688577482893444994136241658867532

69403325611036645569826222068344742198110818724049295034819913767

4037982599879141187980271758388549857511529947174346924111707023

0398103378615232793710290992656444842895511830355733152020804157

9200900418119518804567055154683494461827317423276859892776076207

09525878318766488368348965015474997864119765441433356928012344111

7657353363935578792149370043475682086659587177640592935928875142

92843557047089164876483116615691886203812997555690171892169733755

224469032475078797830901321579940127337210694377283439922280274

0607982347867404348934581201983411010338125067200466098911607002

8400210098045296403978870433530261933759786205219228037148113216

4147186514169090917191909376

I’ll take the program’s word for it that is correct (at least it’s an even number so that much is correct).

You’ll also note that, for negative exponents, if you enter x as an integer, the result is returned as a fraction rather than a decimal number. Clojure deals with rational numbers separately from decimal expansions of them, so if you want the decimal representation, enter x as a floating point number, as in (power 2.0 -2), which gives an answer of 0.25.

WPF’s Grid layout in XAML and C#

ZIndex

With the calculator example we’ve seen a simple example using WPF’s Grid layout. In that example, we saw how to position controls within a Grid and how to make a control span more than one column or row.

One feature of a Grid that we didn’t mention there was the ZIndex. Remember that every object placed in a Grid must have its row and column specified. You might think this is a bit tedious; why not just position objects from left to right, top to bottom, as they are added to the XAML?

The reason for this is that a Grid is flexible as to where objects can be placed, so that you need not fill up every cell in the grid with a control. We saw an example of this in the calculator example, with the 0 button placed in the centre of the bottom row, with no button on either side of it.

Another reason for requiring row and column to be given explicitly is that you can place more than one object in the same cell. The order in which these objects are stacked in the cell is given by each object’s ZIndex. The term ‘ZIndex’ arises from thinking of the plane in which the design is drawn as the x-y plane, with a z axis sticking out of the screen towards you. Objects with a higher ZIndex are further away from the x-y plane and thus appear stacked on top of objects with lower ZIndexes.

As a simple example (which isn’t exactly good interface design, but never mind), suppose we wanted to stack 3 buttons into the same cell in a Grid. The buttons decrease in size as we increase the ZIndex, so smaller buttons are stacked on top of larger ones.

The program is called NestedButtons and looks like this when run:

The interface was designed entirely in EB without writing any XAML code by hand, but the resulting code looks like this:

	<Grid x:Name="LayoutRoot" HorizontalAlignment="Center" VerticalAlignment="Center">
		<Grid.ColumnDefinitions>
			<ColumnDefinition Width="Auto"/>
		</Grid.ColumnDefinitions>
		<Grid.RowDefinitions>
			<RowDefinition Height="Auto"/>
		</Grid.RowDefinitions>
		<Button Content="Stop" HorizontalContentAlignment="Center" Width="150" Height="150" HorizontalAlignment="Center" Background="Red" VerticalContentAlignment="Top" Focusable="False" FontWeight="Bold"/>
		<Button Content="Pause" Background="#FFE6FF00" Width="100" Height="100" Panel.ZIndex="1" VerticalAlignment="Center" HorizontalAlignment="Center" VerticalContentAlignment="Top" Focusable="False" FontWeight="Bold"/>
		<Button Content="Go" Margin="0" VerticalAlignment="Center" Background="#FF00FF04" Panel.ZIndex="2" Width="50" Height="50" HorizontalAlignment="Center" Focusable="False" FontWeight="Bold"/>
	</Grid>

We’ve created a single row and column and placed all three buttons in that cell. The ‘Stop’ button in red is on the bottom and has a ZIndex of 0 (this is the default value). The yellow ‘Pause’ button has a ZIndex of 1 and the green ‘Go’ button a ZIndex of 2. When the program is run, pressing an exposed area of a button will trigger any events connected to that button but not to the button beneath it. (We haven’t included event handlers here but they are easily added as we showed in the earlier post.)

WPF in C#

For simple layouts, or layouts containing a lot of different controls placed at various positions around the Grid, it makes sense to use Expression Blend (EB) to do the layout. However, if we’re creating a layout that has a lot of elements positioned at easily calculable locations, it can get tedious positioning all of them using EB. In this case it makes a lot more sense to write C# code to do the job for us.

For example, suppose we wanted to design a chessboard layout like this:

We need 8 rows and 8 columns, and we need to fill in each square with the correct colour. Doing all this in EB is possible, but tedious. It is easier (once you know what code to write) to do this in the C# code. It’s also useful to know how to access the various components of a layout in C#, since sometimes you’ll want to change some of their properties in response to an event.

The complete project is available here.

By the way, I should add that if you find some of the following code obscure, in the sense of “I’d never have known how to do that.”, I was in much the same position when I started this example and discovered the bits and pieces by googling. Remember, google is your friend when you’re writing code that relies on a lot of library functions.

First, let’s look at the complete XAML code for this example. There’s not much of it, since most of the code is in C#.

<Window
	xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
	xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
	x:Class="Chessboard.MainWindow"
	x:Name="Window"
	Title="Chessboard" SizeToContent="WidthAndHeight" ResizeMode="NoResize">

	<Grid x:Name="LayoutRoot"/>
</Window>

The only things we’ve done in EB are the addition of the SizeToContent and ResizeMode properties in the main window. SizeToContent makes the main window size itself to the width and height of the control it contains (in this case the Grid). This means we can change the size of the chessboard without having to edit the code to change the size of the window. The NoResize option means (surprise!) that the main window can’t be resized.

Now we switch over to Visual Studio (VS) to do the editing of the C#. (You can edit C# code in EB, but it’s not a pleasant experience, so VS is strongly recommended.) Here’s the complete code (apart from the ‘using’ statements at the top, which are just those generated by VS) for the MainWindow class in the C# file:

  public partial class MainWindow : Window
  {
    const int squareSize = 50;
    public MainWindow()
    {
      this.InitializeComponent();

      // Insert code required on object creation below this point.
      InitializeChessboard();
    }

    private void InitializeChessboard()
    {
      GridLengthConverter myGridLengthConverter = new GridLengthConverter();
      GridLength side = (GridLength)myGridLengthConverter.ConvertFromString("Auto");
      for (int i = 0; i < 8; i++)
      {
        LayoutRoot.ColumnDefinitions.Add(new ColumnDefinition());
        LayoutRoot.ColumnDefinitions[i].Width = side;
        LayoutRoot.RowDefinitions.Add(new RowDefinition());
        LayoutRoot.RowDefinitions[i].Height = side;
      }

      Rectangle[,] square = new Rectangle[8,8];
      for (int row = 0; row < 8; row++)
        for (int col = 0; col < 8; col++)
        {
          square[row, col] = new Rectangle();
          square[row, col].Height = squareSize;
          square[row, col].Width = squareSize;
          Grid.SetColumn(square[row, col], col);
          Grid.SetRow(square[row, col], row);
          if ((row + col) % 2 == 0)
          {
            square[row, col].Fill = new SolidColorBrush(System.Windows.Media.Color.FromRgb(255, 255, 255));
          }
          else
          {
            square[row, col].Fill = new SolidColorBrush(System.Windows.Media.Color.FromRgb(0, 0, 0));
          }
          LayoutRoot.Children.Add(square[row, col]);
        }
    }
  }

A fair number of things are going on here, so let’s step through it.

Line 3 defines the size of each square on the board. This is the only place where an actual number is used for the size, so changing this value will change the board size and the size of the window that contains it.

Line 9 calls InitializeChessboard() which is where we’ve written all the new code.

Lines 14 and 15 create a GridLengthConverter which is used for setting the width and height of the Grid cells. The reason we need something fancy like this is because the width and height could be just numbers, but they can also be things like ‘Auto’, so they fit their contents. All these possibilities are encapsulated in a GridLength object, so we need to create one of them. In this case, we want the Grid cells to fit themselves to their contents, so we specify ‘Auto’ as the value.

The loop on lines 16 to 22 creates the columns and rows within the grid. This is what we’ve been doing up till now by using EB’s editor to add columns and rows. You can see that once you know what to call in the C#, it is a lot more concise if you have a lot of rows and columns to add.

On line 24, we declare a two-dimensional array of Rectangle objects. A Rectangle is a graphical element that just draws a rectangle. Within the double loop starting on line 25, we create each square on the board as a separate Rectangle and assign its height and width (these are absolute values).

On lines 31 and 32 we call static methods in the Grid class to assign the grid row and column to each Rectangle. Remember if we had done this in XAML, the row of a control is specified in the control’s properties as ‘Grid.Row=1’. At this point we are assigning properties to the Rectangle; we haven’t yet provided any connection between the Rectangle and the actual Grid (LayoutRoot) that it will be attached to.

The if statement on lines 33 to 40 determines the colour of each rectangle. We use the fact that if the sum of the row and column indexes is even, the square is white, otherwise it is black. The cryptic method for filling a Rectangle with a colour was found just by googling; nobody would expect you to be able to figure this out on your own (I’d guess).

Finally, on line 41, we add the Rectangle to the specific LayoutRoot Grid.

Functions in Clojure

In our Hello World program in Clojure, we saw one function, the println function, which prints its argument to the standard output. The heart of any Clojure program is, of course, the ability to write your own functions, so we’ll have a look at how that is done here. We’ll start with functions that do relatively simple things, such as arithmetic.

Java programmers are used to the idea of defining a function (or method as they are usually called in OO programming) by defining a name, argument list, and return type for their function. For example, a function that calculates the square of an integer might have the signature

int square(int number)
{
  return number * number;
}

In Clojure, the process is roughly the same, although the syntax is quite different. One key point is that a Clojure function actually has no name; however for it to be useful (that is, for you to be able to call it), it is almost always bound to a symbol that effectively gives it a name. The syntax for a Clojure function equivalent to the Java one above is

(defn square
         "Squares its argument"
         [number]
         (* number number))

Like everything in Clojure, a function definition is a list of forms enclosed in parentheses. The form defn is a special form (a keyword of the language) which begins a function definition. The next form is the symbol (square) to which the function is to be bound. Following this is an optional string which documents the function. As with all coding, it’s a good idea to document your code even if you plan never to let anyone else see it. It’s amazing how fast your own memory of what a function does will fade.

The next form is a list of arguments for the function. Note that this list is enclosed in square brackets: [number]. A list in square brackets is a vector, of which we will say more in another post. A function can have any number of arguments, including zero (in which case this form is just empty brackets: []). As with all lists, elements within the list are separated by blanks, so if the function had two arguments, this would be written as [arg1 arg2].

The last element in the list is the code which is run when the function is called. In this case we want to square number, so the code is (* number number). The * here is just another symbol, rather than a specialized operator as in Java, and it calls a built-in function which multiplies its arguments. (Actually, * can take any number of arguments so you could multiply together 4 numbers by writing (* n1 n2 n3 n4).)

A statement returns the value of the last element in the list, so in this case the result of the multiplication is returned.

To run this code, create a new Netbeans project called Square, with a namespace of glenn.rowe.square. Add the code above after the ns statement, so the full program looks like this:

(ns glenn.rowe.square
	;(:import )
	;(:require )
)
(defn square
         "Squares its argument"
         [number]
         (* number number))

Start up a REPL but don’t use Netbeans’s menu to load anything just yet. At the prompt, try calling your function. You’ll get the following error:

user=> (square 4)
#<CompilerException java.lang.Exception: Unable to resolve symbol: square in this context (NO_SOURCE_FILE:2)>

The problem is that since the file hasn’t been loaded, the square function is unknown to the REPL.

Now try loading the file by right clicking on the project name and selecting ‘REPL->Load all Clojure files in Source Packages’. Now try calling the square function again. You’ll still get an error:

user=>
#'glenn.rowe.square/square
user=> (square 4)
#<CompilerException java.lang.Exception: Unable to resolve symbol: square in this context (NO_SOURCE_FILE:4)>

What’s going on? The clue lies in the response you got when you loaded the source file. The REPL’s response was the mysterious string “#’glenn.rowe.square/square”. This gives the fully qualified name of the function it found in your source file; that is, the symbol name ‘square’ preceded by the namespace you defined when you created the project, and which appears in the ns statement at the start of the file.

The problem is that the namespace currently being used by the REPL is not the namespace defined in the file. In fact, it’s a default namespace which is called ‘user’, and that’s where the ‘user’ in the prompt comes from: it tells you which namespace the REPL is currently operating in.

Try calling the function by giving it its full name:

user=> (glenn.rowe.square/square 4)
16

Aha! This time we have success. However, it gets to be a bit of a pain having to type in the namespace every time we want to call a function. Fortunately, there are a few ways around this. One way is to change the namespace in which the REPL is operating by entering the following line at the ‘user’ prompt:

user=> (ns glenn.rowe.square)
nil
glenn.rowe.square=>

The ‘ns’ command tells the REPL to change its namespace to “glenn.rowe.square”, and you can see that after entering this command, the prompt in the REPL has changed to reflect the new namespace. Now try calling the square function using just its name:

glenn.rowe.square=> (square 4)
16

This time it works without having to type in the namespace.

If you don’t want to change the REPL’s operating namespace, there is another way to get access to the square function without having to type its namespace name every time. Return to the ‘user’ namespace by entering (ns user). Next, enter a use statement as follows:

user=> (use 'glenn.rowe.square)
nil
user=> (square 4)
16

The use statement, followed by the name of a namespace (the quote before the name is required) tells the REPL to include all the symbols defined in that namespace within the current ‘user’ namespace. Thus ‘square’ now becomes directly accessible so we can call it as shown above.

There’s an obvious danger with doing this, of course. If we use several namespaces within our operating namespace, no two of these namespaces can contain the same symbol; if this happens we get a collision of names, and the REPL will generate an error. However, for testing purposes, it’s usually a safe thing to do.

A couple of other commands are useful to know about before we leave this introduction to functions.

When you’re writing code, you frequently need to change things and then test them by running the result. However, the REPL won’t know about any changes unless you tell it reload the file. For example, suppose we added a new function called cube which returns the cube of its single argument. The file now looks like this:

(ns glenn.rowe.square
	;(:import )
	;(:require )
)
(defn square
         "Squares its argument"
         [number]
         (* number number))

(defn cube
         "Cubes its argument"
         [number]
         (* number number number))

Entering the code will not update the REPL, so the cube function will still be undefined. In Netbeans using Enclojure, the easiest way is to type Alt+L. This will save the file and load all the changes into the REPL.

If you’re running the REPL from a command console, you can reload a namespace by typing

user=> (use :reload-all 'glenn.rowe.square)
nil

Note that this won’t work in the Enclojure REPL, so just use the Alt+L shortcut (it’s a lot faster than typing in that line anyway).

Finally, it’s useful to know how to delete a symbol from the REPL’s map. If you try deleting the code for square from the source file and then reloading it, you’ll find that you can still call square from the REPL. The reason is that loading or reloading a file will just add new symbols or modifications to existing symbols, but it won’t delete symbols that are no longer in the source code. To do that, there is a special command called ns-unmap. Suppose we want to delete the square symbol. Try the command

user=> (ns-unmap 'glenn.rowe.square 'square)

The ns-unmap function’s first argument is the namespace from which to remove the symbol, and the second argument is the symbol to be removed (both prefixed by a quote).

Now if you try calling square you’ll get an error. However, if you had previously given a (use ‘glenn.rowe.square) command, there will still be a square symbol in the REPL’s map. You can see this by typing square on its own (without parentheses) into the REPL. You’ll get a response that looks something like this:

user=> square
#<square$square__304 glenn.rowe.square$square__304@1677737>

If square were completely undefined, you’d get an error, but this cryptic string shows that there is still a reference to square stored in the REPL’s map.

This is because the square in the namespace glenn.rowe.square was copied into the ‘user’ namespace. When you unmapped square from glenn.rowe.square, you didn’t remove the copy from ‘user’. However, you are unable to call square since the copy in ‘user’ pointed to the original function symbol in glenn.rowe.square, and since the original is now gone, the function can’t be called.

To completely remove the square symbol you need to use a second call to ns-unmap:

user=> (ns-unmap 'user 'square)

Now all trace of square is gone.