Easy to Use

I've noticed that when choosing a tool for software development one of the criteria that's often proposed is the tool should be "easy to use". While I agree that ease of use should be a criteria for choosing a tool I've come to realize that I have a different opinion on what "easy to use" means than others. When I say a tool is "easy to use" I mean it literally. A tool that is easy to use should make it really easy for me to do what I want. Here are some of the development tools that I use that I consider easy to use:

1. vim
2. git
3. The command line (bash)

All three of these tools let me do my job as quickly and painlessly as possible.  If you asked others for a list of similar tools that are easy to use you may get the following:

1. notepad
2. svn
3. GUI's

By my definition the above tools are not easier to use than my list (they don't allow me to do my job as quickly or painlessly) but they are easier to learn.  I'm not sure if easy to learn and easy to use must be mutually exclusive but I can't think of any tools that I use frequently that have both qualities.  There is nothing wrong with choosing a tool that's easier to learn over one that's easier to use as long as you use the tool infrequently.  Investing years to fully learn vim is a waste of time if you only edit text files for a few minutes every month.  If your going to use a tool frequently over a long period of time then you should spend the time to learn the tool that's easy to use even if it isn't easy to learn.

Recursion and Inductive Proofs

I've discovered that programmers frequently stumble when writing recursive algorithms. There are some simple rules that programmers can steal from mathematics to make writing recursive algorithms easy. I should point out that I'm only talking about writing recursive algorithms for interacting with recursive data-structures (lists, trees, etc.). Let's get started by reviewing some basic steps for proving a statement holds for all natural numbers n using an inductive proof.

1. Base case:  Show the statement holds for a value of n (usually n=1 or n=0).
2. Inductive step:  Assuming the statement holds for any value of n then show it also holds for a value of n+1

Rule 2.5 would be to make sure that the inductive step reduces the problem space.  Using a base case of n=0 and then and inductive step of n-1 wouldn't be a valid proof because the inductive step does not really reduce the problem space (remember we're talking about natural numbers for this example).  So let's use an inductive proof to show that 0+1+2...n=(n(n+1))/2.

Base case: Show the statement holds for n=0

0=0(0+1)/2

This equation clearly holds.

Inductive step:  Assuming the statement holds for any value of n then show it will also hold for n+1.

0+1+2...n+(n+1) = ((n+1)((n+1)+1)/2

If we assume that the statement holds for n then we can reduce the expression.

(n(n+1))/2 + (n+1) = ((n+1)((n+1)+1)/2

Using some basic algebra we can reduce both sides and discover that the inductive step holds.

Now we can apply same (perhaps slightly tweaked) rules to writing a recursive algorithm for finding the length of a linked-list (a recursive data-structure).

Let's start out with the function signature.

int length(Node *node)
{
  // Do stuff here
}

Base case: Write the algorithm for n=0 (the linked-list with 0 nodes).

int length(Node *node)
{
  if (NULL == node)
  {
    return 0;
  }
  // Do more stuff here
}

Congratulations! If you've make it this far you're above average. You've solved the base case without dumping core.

Now onto the inductive step: Assume that your length function will work for lists of length n now write code to make it work for lists of length n + 1.

int length(Node *node)
{
  if (NULL == node)
  {
    return 0;
  }
  else
  {
    return 1 + length(node->next);
  }
}

Notice that if we assume that "length(...)" works for lists of length n then for lists of length n + 1 all we need to do is add 1 to the length. You should also notice that we passed node->next to the "length(...)" function not just node because rule 2.5 states that the inductive step must reduce the problem space and just passing node would not reduce the problem space. Congratulations! If you've make it this far you're now well above average. Now not only will your algorithm not core dump, but it won't hang either.

So let's review what we've done. We've used the rules for inductive proofs to guide us in writing a recursive algorithm. Does this mean we've proved that this algorithm is correct? The answer is, not really or at least, not formally. Even though we haven't proved this algorithm is correct we can be much more confident that it will work.

If we were to write unit-tests for this algorithm (which you should *always* do before writing the algorithm) we could use the rules of induction to guide our unit tests. We could write a test for testing the base case and another test for testing the inductive case.

Since math has been around longer than computers, it makes sense that we could borrow a few ideas from it to make our jobs easier.

Google's Go trying to be too clever.

I've discovered a couple of cases where Google's Go is trying to be too clever. There are two expressions who's behavior changes based upon what is done with evaluated results. Lets look at a bit of code.

package main

import . "fmt"

// Define a simple struct
type foo struct {
        a int;
}

// Define an interface
type plus1 interface {
        add1() int;
}

func any(a interface{}) {
        v := a.(plus1).add1();
        Printf("%v\n", v);
}

func main() {
        f := foo{1};
        any(f);
}

So this code defines a simple struct "foo" with a single member a. It defines a "plus1" interface that says that any struct that implements the interface must implement an add1 method that returns an int. The main function instantiates a "foo" and passes it onto the any function. Because "foo" doesn't implement the "plus1" interface the first expression in the function "any" will fail with a runtime exception. the "a.(plus1)" is called a type assertion and it fails if the "a" doesn't implement the "plus1" interface. Now we can switch this code so the type assertion won't assert by assigning the results of the type expression to some variables. Consider the following:

package main

import . "fmt"

// Define a simple struct
type foo struct {
        a int;
}

// Define an interface
type plus1 interface {
        add1() int;
}

func any(a interface{}) {
        a1, ok := a.(plus1);
        if ok {
                v := a1.add1();
                Printf("%v\n", v);
        }
 }

func main() {
        f := foo{1};
        any(f);
}

The only difference in this code is that the type assertion will not assert but instead return two values (yes Go can return multiple values!). The second value is of type bool which indicates whether the first value is "a" cast to "plus1". If "a" isn't of type "plus1" then instead of asserting the type assertion will just return false for the second parameter. While this is clever, it feels like assigning the return value to a variable magically alters the behavior of the expression. I think this will just make the language too difficult to learn. The second operation has to do with go-routines and I'll talk about it next time.

Letting the compiler find the bugs

Lets start by looking at a bit of contrived C/C++ code. See if you can spot the (hopefully obvious) bug.

#include <stdio.h>

int main()
{
    float fieldLength = 120; // yards
    float fieldWidth  = 48.77; // meters
    float yardsInAMile = 1760; // yards per mile

    printf("You must run around the perimeter of an American football field %f times to run a marathon\n", 
            26.2 * (yardsInAMile / ((fieldLength * 2) + (fieldWidth * 2))));

    return 0;
}

It probably shouldn't take you too long to realize that in the above code I'm mixing units. I'm adding yards to meters. While bugs like this are obvious in trivial code they can be difficult to track down in more complex software. What can we do to prevent bugs like this from creeping into code? One solution is to use coding standards to reduce ambiguity. For example you could decide to use metric units for all data in your project. You could also use 'typedefs' and variable naming conventions to make errors even more obvious. Consider the following:

#include <stdio.h>
typedef float yards;
typedef float meters;

int main()
{
    yards fieldLengthYards = 120; // yards
    meters fieldWidthMeters  = 48.77; // meters
    float yardsInAMile = 1760; // yards per mile

    printf("You must run around the perimeter of an American football field %f times to run a marathon\n", 
            26.2 * (yardsInAMile / ((fieldLengthYards * 2) + (fieldWidthMeters * 2))));

    return 0;
}

By including the units in the variable names and types it makes the programmers intentions clear. It's also easier to spot bugs in code audits. For even more safety you could define Meters and Yards classes that encapsulate the floats and prevent mixing of types. The advantage of defining new types/classes is the compiler can now ensure that you don't mix types. The disadvantage is that you'll end up writing a class for each type, with lots of overloaded operators. Writing a class for every unit feels to burdensome for all but the most critical code (nukes, airplane firmware, surgery robots, etc.). The problem with the above 'typedef' solution is that C/C++'s 'typedef' really only defines an alias for the type. Both the type-checker and the compiler will treat 'meters' the exact same way it treats 'yards', we want the type-checker to treat 'meters' and 'yards' as distinct types and the compiler to treat them both as floats. Google's new system language Go lets you do just that. Lets reproduce the original bug in Google Go.

package main

import "fmt"

func main() {
    var fieldLength float = 120; // yards
    var fieldWidth  float = 48.77; // meters
    var yardsInAMile float = 1760; // yards per mile

    fmt.Printf("You must run around the perimeter of an American football field %f times to run a marathon\n", 
            26.2 * (yardsInAMile / ((fieldLength * 2) + (fieldWidth * 2))));
}

This has the same bug as the C/C++ code above. The code should be readable to a C/C++ developer, the only really "weird" thing is that the type follows the variable name. Now let's use Go's strong typing to let the compiler catch the bug for us.

package main

import "fmt"

type yards float
type meters float

func main() {
        var fieldLength yards = 120;
        var fieldWidth meters = 48.77;
        var yardsInAMile float = 1760; // yards per mile

        fmt.Printf("You must run around the perimeter of an American football field %f times to run a marathon\n",
                26.2*(yardsInAMile/((fieldLength*2)+(fieldWidth*2))));
}

Notice that all we did is define two new types 'yards' and 'meters' all which should act like 'floats', but should be treated differently by the type-checker. When we compile we get the following error:

invalid operation: fieldLength * 2 + fieldWidth * 2 (type yards + meters)

The most important part of the error is at the end where it tells us we're trying to add 'yards' with 'meters'. The type checker found the bug for us! So how do we fix it? We need some conversion routines. So lets add some methods to the types and fix the bugs.

package main

import "fmt"

type yards float
type meters float
type miles float

func (m meters) toYards() yards { return yards(m * 1.0936133) }
func (y yards) toMiles() miles  { return miles(1760.0 / y) }

func main() {
        var fieldLength yards = 120;
        var fieldWidth meters = 48.77;

        fmt.Printf("You must run around the perimeter of an American football field %f times to run a marathon\n",
                26.2*((fieldLength*2)+(fieldWidth.toYards()*2)).toMiles());
}

With the corrected program we see that you only have to run around the field 133 times instead of 136.6 times!

Go isn't the first nor the only programming language that allows you to encode units as types, but it's close enough to C/C++ for a good comparison. So what's the runtime overhead of the change? Well there are a couple of method calls (toYards(), toMiles()) where the original version did the conversions inline. The error checking happens at compile time because Go is statically typed so there's no runtime performance hit. Personally I'd much rather wait for my program to call a couple of functions than to run around an American football field 3.6 more times.

By carefully using Go's (or any other language with a good type system) type system you can spend more time writing code and less time tracking down bugs.

More fun with C/C++

In order to write a program it's useful (but not necessary) to have an accurate mental model of how the language works, so you can mentally interpret your code before handing it off the compiler. So if you're a C/C++ programmer take a look at the following code and see if you can correctly identify the output:

#include <stdio.h>

int foo(int a, int b, int c, int d)
{
    if (a>b)
    {
        return c;
    }
    else
    {
        return d;
    }
}

int main(int argc, char * argv[])
{
    int x = 2;
    int y = 1;

    printf("Result: %d\n", foo(x+=y, y+=x, x+=y, y+=x));

    return 0;
}

In this case the output is non-deterministic. While C/C++ specify what order arguments will be pushed onto the stack it doesn't specify what order they'll be evaluated in. So there are several possibilities for the output. This flexibility allows compiler writers to order the evaluation of operations in the most efficient way. If you want to avoid confusing/broken code don't mutate variables in argument positions. The person that ends up maintaining your code will thank you for it.

Coding Challenge

Here is a little coding challenge. Learning how to solve this probably won't make you a better programmer (it may make you worse) but it's fun anyway. You are given a file named "helloworld.cxx" that contains the following code.

#include <stdio.h>
#include "muck.h"

int 
main(int argc, char **argv)
{
    printf("%s\n", "Hello World!");
}

You can't edit this file! Your job is to write the "muck.h" header file. When you're done compile "helloworld.cxx" and run it and the output should be "Goodbye!" followed by a newline. Nothing more nothing less. Remember you can only modify "muck.h" and you must compile "helloworld.cxx" unmodified. My solution and it's Makefile.

The Essence of Scheme (part two)

This post is a continuation of part one. You probably want to read that post first. So in my previous post I walked you through a nifty little though experiment on why Scheme is so expressive, and why those pesky ('s and )'s are actually useful. In this post I hope to provide some concrete examples of using Scheme's macros to do interesting things. So lets start with a simple example. The Scheme programming language (R5RS) doesn't have a built in "while" loop. It does have a "do" loop which is kind of like a "for" loop but I don't think it gets used much. Most Schemers use recursion instead. Lets say you're just learning Scheme and recursion hurts your brain and you really really just want to use a "while" loop just this one time and you promise that you'll pay better attention when you CS professor talks about recursion. It turns out it's quite easy to implement a "while" loop as a Scheme macro¹.

;; A while loop
(define-syntax while
  (syntax-rules ()
    [(_ (cnd ...) body ...)
     (letrec ([tmp (lambda () (if (cnd ...) (begin body ... (tmp)) (void)))])
       (tmp))]))

If you want to try it out here is a bit of code that uses the while loop to count from 10 down to 1.

(define count 10)
(while (> count 0)
       (printf "~a\n" count)
       (set! count (- count 1)))

So in 10 lines of code you can define a "while" loop that works just like the "while" loops built into C/C++/Java/Python/Insert_Your_Favorite_Language_Here.

So that doesn't seem to hard. If C didn't have a built in "while" loop you could always create you're own with a C style macro as follows.

#define WHILE(cond) for(;cond;)

Lets try something more difficult. Scheme also doesn't have a C/C++ "#include" directive. So lets write our own.

;; Define include
(define-syntax include
  (lambda (stx)
    (define (read-all port)
      (let ([exp (read port)])
        (if (eof-object? exp)
            '()
            (cons exp
                  (read-all port)))))
    (define read-file
      (lambda (fn ctx)
        (let ([port (open-input-file fn)])
          (begin0
            (datum->syntax ctx (read-all port))
            (close-input-port port)))))
    (syntax-case stx ()
      ((ctx filename)
       (with-syntax ([(exp ...) (read-file (syntax->datum #'filename) #'ctx)])
         #'(begin exp ...))))))

Once you've defined this you can use it as follows.

(include "extern.ss")

Once you've defined the "include" macro any include expression will get evaluated at compile time which opens up the included file reads in the text and injects it into the the source file at the location of the "include" call. Spend a little time thinking about that. A Scheme programmer can write code that gets evaluated at compile time and that code can open, close, and read from files. So if Scheme's macro language allows you to read from files what else can it do? It turns out anything that a Scheme program can do. The above macro can read from files because any old PLT-Scheme program can read from files. A Scheme macro is just a chunk of regular old Scheme code that gets executed at compile time. If your Scheme allows you to open up a TCP/IP socket then you can write a macro to do this at compile time². If your Scheme allows you to rotate images then you can do it at compile time. If your Scheme allows you to play music then you can play music at compile time³. OK so lets look at some more examples.

(define current-catch 
  (make-parameter 
   (lambda (exn) 
     (printf exn) 
     (exit 1))))

(define (throw exn)
  ((current-catch) exn))

(define-syntax try
  (syntax-rules (catch throw)
    [(_ body ... (catch exn cbody ...))
     (let/cc k
       (parameterize ([current-catch (lambda (exn) cbody ... (k (void)))])
         (begin body ...)))]))

This chunk of code allows users to throw and catch exceptions using "try", "catch" and "throw"⁴. Scheme doesn't have a built in exception mechanism, but in 13 lines of code you can write your own. The following code will use the above macro and functions.

(try 
 (printf "Yes\n") 
 (throw "Error\n")
 (printf "No\n")
 (catch exn 
   (printf exn)))

It will print "Yes" followed by "Error" the "No" will not be displayed because of the "Error" exception will be thrown. OK lets look at one more.

(define-syntax define-generator
  (lambda (stx)
    (syntax-case stx ()
      ((_ (name args ...) body ...)
       (with-syntax ([yield (datum->syntax #'name 'yield)])
         #'(define (name args ...)
             (define yield-k #f)
             (define return-k void)
             (define (yield retval)
               (let/cc k
                 (set! yield-k k)
                 (return-k retval)))
             (lambda ()
               (let/cc ret
                 (set! return-k ret)
                 (if yield-k
                     (yield-k '())
                     (begin
                       body ...
                       (set! yield-k (lambda (x) (void)))))))))))))

This allow you to define Python style generators. Here is a simple example that defines a "range" generator that will reuturn 0 he first time it's called and 1 the next.

(define-generator (range init limit)
  (let loop ([i init])
    (yield i)
    (when (< i limit)
      (loop (+ i 1)))))

(define foo (range 0 1))
(foo)
(foo)

I hope these examples give some insight at how expressive and malleable the Scheme programming language is. There is one more issue I'd like to address. If you're a Python programmer you may be thinking to yourself. "Hey Python has loops, exceptions, generators and import which is kind of like #include. If python has these built in then why should I use Scheme?" That is a valid but slightly myopic question. The point of Scheme's macro system is not to create another Python with funnier syntax. The real point is that you the developer can extend and grow the language to meet your needs. You may extend the language by adding features that are found in other programming languages, but you may also add features that don't exist in any language, and that don't have a name, and that may not be generally useful but really make the current program you're working on really really easy to write. In Python, Perl and Java users have the power to create and extend libraries, in Scheme users have the power to create and extend languages⁵. Power to the people!

[1] All examples tested in in PLT-Scheme 4.1.3.
[2] Implementing "http-include" is left as an exercise for the reader.
[3] Playing music at compile time is possible but not recommended by the author.
[4] Anyone want to try implementing exceptions in C?
[5] There is one major downside to learning Scheme. Eventually you'll find yourself writing a program in C/C++/Python/Java and you'll realize that you could solve some problem really elegantly if you could just extend the language just a little bit. Then you'll realize that you can't and you'll spend the next hour wishing you we're never enlightened.