New blog. I will probably post as infrequently there as I did here.

EDIT:

Ha.  I change sites as often as I write:  http://dave.dkjones.org.  This one is just a static site served from github, where the files are generated by OrgMode.  Maybe that will meet my laziness criteria.  And my emacs criteria.

Finally got slime working for clojure

At strange loop, I finally got Slime kind of working on Clojure.  Here is the secret:  lein.

Instead of building all of Clojure from source, I just followed the directions here, and installed an up to date slime.  Also, it appears that slime does not start a REPL automatically anymore, so I had to adjust settings for that too.

Phew.

Strange Loop 2011 notes (day one)

Back from Strange Loop 2011, trying to collect my thoughts.

I went for two reasons - the speakers, and to meet like minded people.  Both goals were met.   Gerald Sussman, Erik Meijer, and Bryan O'Sullivan were enough to get me interested.  The rest was icing.

I was sold.

The organizer, Alex Miller, wants to make Strange Loop the best conference we ever attended.  The conference wins the award for me.  I only have the MSDN Developer conference to compare it to, and there was a wide gap in the quality.

Unfortunately, I signed up too late for the workshops I wanted.  Machine Learning with Hilary Mason, and Haskell (for data analysis) with Bryan.

A take away I have this year is to go to the talks with speakers I really want to see, even if I think someone else has a better topic.

Erik Meijer mentioned in his keynote that we keep reinventing things over and over again, and then later in the day Gerald Sussman reinfected me with the desire to tell everyone that every new idea was already done in Lisp.   He also inspired me (again!) about how fun programming can be.  Watching him, I realized that a lot of software engineering is to protect us from ourselves.  People like him, though, should be allowed to do whatever they want with a computer.

Also Professor Sussman pointed out a lot that can be done with code.  If we start worrying about performance less, and also stop worrying about proof as much, we can play and learn.  He showed some interval math code, like in the classic book, but also showed other ways of interpreting math code.  Notably, he showed how to use evidence as input, and how the program can determine better answers with better evidence, how it can fix imprecise evidence, and how it can help remove conflicting evidence.  Of course, this misses all of the deeper points.

Regardless, I am going to treat my code as data more often!

Neal Ford's functional thinking talk had a very important message.  Functional thinking can be used in any language.  He did not get into a lot of depth, but I think he had one of the better deliveries I saw, and I loved that his slides were there only to help his presentation.  That makes "sharing" the talk later difficult, but I wish more speakers had slides like his, and some sort of a draft of their talk for sharing afterwards.  (end of presentation rant)

Andrei Alexandrescu and Bartosz Milewski were kind enough to humour me after lunch on Monday, and we chatted C++, D, and F#.  I put my foot in my mouth at least once that I realized, and likely again without knowing it.  Andrei's D talk was a lot of fun.  Generic programming is something that you can do in several languages, but they all have some weaknesses.  D appears to have addressed most of the serious issues.  The last time I read up on D was about ten years ago... time to take another look!

I looked forward to Sarah Allen's "Teaching Code Literacy", and it was different and more important than I expected.  She talked about the importance of teaching programming to kids, and how to help them.  All kids learn about biology, even though few will be biologists.  They need to learn about the world they live in.  Programming is important because of all of the computer's around us.  And, they might love it, and become great programmers themselves.   Again, this is only scratching the surface.

This is still just day one!

After the conference, the languages I am most likely to play with:  Scheme (again) and D.

DFS for puzzle solving

I looked back at the one to nine puzzle, and realized that we can write a function to hold the main idea, and apply it to other puzzles.

The main idea is to solve the puzzle one step at a time. At each step, we try every possible move, but only the moves that are still valid. We return any solutions we find.

In the previous post, the searching was mixed with the puzzle specific code. Here is a function that handles the recursion for us, and lets us pass in problem-specific code for the details.

let solve next_f done_f initial =
    let rec search state =
        seq {
            if done_f state then
               yield state
            else
               for state' in next_f state do
                   yield! search state'
            }
    search initial

This function returns a sequence of answers. Some puzzles have one solution, others have many. With sequences, the function caller has more control over how many values are returned.

done_f has the type ('position -> bool) and is the stopping criteria. Our move generator next_f has the type ('position -> seq<'position>). solve is a higher order function because it takes other functions as inputs.

Now, we can solve the one to nine puzzle with this function.

let one_to_nine () =
    let next_move (number, digits, idx) =
        let idx' = idx + 1
        seq {
            for d in digits do
               let number' = number * 10 + d
               if number' % idx' = 0 then
                   yield number', Set.remove d digits, idx'
            }

    let finished (_, _, idx) = idx = 9

    solve next_move finished (0, Set.ofList [1..9], 0)
    |> Seq.head 
    |> fun (number, digits, idx) -> number

see the code at fssnip.net

A position is three things: the current number, the available digits, and the index of the digit we are considering. If we make it to nine digits, then we are done. Given a current state, we generate the next state by trying each digit that remains. We test each of these to make sure they follow the divisibility rule (two digit number must be divisible by two, three by three, etc.) Then we create a new state to hold the information.

We pass those two functions to solve along with the initial state, and it finds our solution.

solve is meant to be general, and that was too much work for one puzzle. Let's look next at the N-Queens problem. There are a ton of possible positions we could try for all N queens, but each piece reduces the number of options we have for the other pieces. We will place the queens one column at a time. At each column, we will compute which rows are valid based on the previous columns. A row is valid if no previous column has a queen on the same row or diagonal.

N-Queens has many solutions. With solve, we can find one, some, or all of the solutions, given enough time or memory.

Here is the code.

let n_queens n =
    let all_rows = Set.ofList [1..n]
    let next_f queens =
        let column = List.length queens + 1
        queens
        |> List.fold (fun possible (row, col) ->
            let distance = column - col
            // Remove the current row, and diagonals from the
            // possible set.  The diagonals are just previous
            // row +/- the column difference. This is safe here,
            // because even if row - distance is negative, we are
            // removing it from another set.  No array access is
            // involved.
            Set.difference possible
                      (Set.ofList [row; row + distance;
                                   row - distance])) all_rows
        |> Set.map (fun (row) ->
                (row, column)::queens)
    let done_f queens =
        List.length queens = n

    solve next_f done_f []

see the code at fssnip.net

And some results from running the code.

n_queens 8 |> Seq.length;;
val it : int = 92

> n_queens 9 |> Seq.length;;
val it : int = 352

> n_queens 10 |> Seq.length;;
val it : int = 724

> n_queens 11 |> Seq.length;;
val it : int = 2680

> // Solve for N = 20, but just return one solution. 
> n_queens 20 |> Seq.head;;
val it : (int * int) list =
  [(11, 20); (6, 19); (14, 18); (7, 17); (10, 16); (8, 15); (19, 14); (16, 13);
   (9, 12); (17, 11); (20, 10); (18, 9); (12, 8); (15, 7); (13, 6); (4, 5);
   (2, 4); (5, 3); (3, 2); (1, 1)]

This function also solves Sudoku, with the right inputs. By the time all of the helper code is written, solve is a small fraction of the code. But, it is still instructive to prune away the details of the puzzles to find the essence of the search problem, even if only for better understanding.

Sudoku code

Attitude in programming

From when I first learned to program on my family's C64, up through high school, college, and my first job, my only criteria of software quality was "Does it work?"  I prided myself on holding whole programs in my head, and making them do whatever I wanted, no matter how much time it took to get it working or debugged.

This attitude, it turns out, is hard to kill.  I see it in others, and I see it in myself, although I should know better by now.  

Some of my habits help fight this.  I generally write small functions.  My code is functional whenever possible.  Scope of variables is small. Globals are rarely used.  These habits help, but they still don't cover everything.

The main question is... "Is the code understandable?  To someone who hasn't been hacking at it for a week?"

Maybe like editing a paper, these questions need to be asked after a day or so or writing the code, so that the eyes are semi-fresh when looking at it.  Certainly a different set of eyes looking at it would be even better.

Most of the good practices (I mean the really good ones,  not just the popular ones) work towards making the code more understandable.    Even some of the other good goals, like managing complexity, seem secondary to understandability.  Managing complexity is necessary, but not sufficient to the goal of clear code.

When coding, it is very easy to just be done with something, without even a cursory check of how good it is.  So, how do I establish that habit?  I probably write more code at home, for fun, than I do at work.  That is probably where I need to build the habit, but it hurts a little to think of doing that extra effort for code that no one else will ever see, and that I might not ever look at again.

The habit may be worth it though.  Clearer code is more likely to be right, or at least easier to get right, instead of wading through the muck of something less clear.  Like clear writing, clear code should also encourage clear thinking.

That is a new goal of mine.  Let's see if it sticks.

Apologies

My apologies to the reader who was hoping for frequent updates.  Life got a little busy in February... I was contacted by a recruiter from a nice tech company, and then spent a month preparing to interview, and another month deliberating the choice, and finally another month recovering.

In the meantime, I have been working through The Essentials of Programming Languages.  The first edition sat in my night stand for about eight years.   Steve Yegge's post led me to this article (pdf), and inspired me to give it a serious try.

The book uses Scheme, so I started off in Common Lisp (since I want to learn it better).  I got the basic interpreters working, then tried porting it to Javascript.  After several days of slow going, I gave up, and went to Ocaml.   The pattern matching in the ML languages makes this kind of stuff much easier.  The EOPL book itself uses several macros to emulate the same behavior, but probably without the compile time checking.

None of this is new or exciting in general, but it is new and exciting for me.  I got a copy of the third addition of the book, and see that they build up to an interpreter with type inference.  That will be pretty cool to try, so I hope to stick it out.

Programming and proofs

This post talks about two completely different topics, then tries to merge them together.

How to Solve It

First I want to talk about How to Solve It by G. Polya. This book was recommended on the forums at Topcoder several years ago, and it was one of the most important things I got from participating at that site. (Besides relearning a bunch of algorithms I hadn't seen in a long time, and getting much more comfortable with the STL, and …)

This book talks about teaching math, and how to help students learn to solve the problems themselves. In part of the book, Polya mentions that for some hard problems, first the student must get a general idea of the "big steps" that are needed to solve the problem. Once she thinks the big steps look promising, then she can start working out the details.

I wish I had this book in college. Another important lesson in the book is that the most important step in solving a problem is review. Figure out what lessons you learned, what you could have done differently, and seek out new uses for what you learned.

Great Programmers

Next, I want to talk about great programmers.

When I read stuff by Donald Knuth, Philip Wadler, Peter Norvig, or any other number of super programmers, I feel ashamed of how I program. I don't sit down, think a lot, and then spew the well thought out code that these people seem too. Of course a lot of their published work is not first drafts, and they have had a lot of time to edit, and think things through again. Reading their papers though, surely makes it seem like they don't hack through things the way I do. Knuth certainly didn't when he was using punch cards.

Even in the normal world of mortal programmers, several coworkers of mine have mentioned how much better they used to be when they had to batch compile everything. They were far more careful to get things right before they attempted to compile. I blushed a little while they were saying it because I was running M-x compile just to see if I had the syntax right on an STL iterator.

I am not trying to argue against the merits of a REPL loop, or a very fast code-compile-test iteration. I love both of those. I just realize how human I am compared to some of my programming heros.

A Hasty Conclusion

Working on some ugly problems, I realized something. I cannot program exactly the way that Polya recommends I do a math proof. With a program, I often cannot be sure the big parts will work together until I try them together. Also, with a program, the small parts are code. So, in some cases, I have to have the small parts (code) working before I can see if the big parts work together.

That goes too far of course. In many cases, I could be much more careful in my thinking about the large parts of the program before I spend too much time on code. But I think I can relax some, and realize that I cannot always be sure that my design for a program is correct until I try it out.

As a corollary, just because my program isn't working as I had hoped doesn't mean that the big parts are wrong. In the AI contest, several times I had good ideas, but buggy code. With a lack of sleep, and too much excitement to push out new ideas, I lost my bearings a little and forgot that I should use a minimum of care when I was programming.

All three names I mentioned above, as well as many of the Haskell writers, all follow some steps I would be well off to imitate. If I could just stop for a moment, think about what I am trying to do, what I expect my solution to accomplish, and what properties I think both the problem and solution have, I should be a much better programmer than I am today.

A little more evidence

The winner of the Google AI contest, Gabor Melis, did a webinar. He talked about thinking things through, working out the ideas in his head, establishing some principles for his solution, and then coding it. He mentioned that you must test and debug the code before you give up on the design, because a bug may make you abandon a good idea.

This is more evidence that I am not careful enough when I code, and it is an extra push that it is ok to think things through before writing code.

I won't be emitting code that looks like proofs, but maybe I can spend some more time thinking instead of debugging. I have come full circle here… my intent was to say that hacking things out was needed, because the code is the proof. Instead, I think I could profit from being a bit more careful with what I do.

Something that has held me back is that I am good at the way I work now. There is always room to improve though.