Sunday, November 20, 2011

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.

Saturday, September 24, 2011

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.


Friday, September 23, 2011

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.




Wednesday, July 13, 2011

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

Thursday, May 19, 2011

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.

Wednesday, May 18, 2011

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.

Wednesday, February 2, 2011

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.

Sunday, January 30, 2011

My most important programming book

My first employer had a great library. Tons and tons of books, multiple copies of the most popular books, and you could keep a book until someone else needed it. They would display new books for people to look at, and then have a sign up sheet to borrow the book when it went into circulation. From that program, I first read The Pragmatic Programmer, by Andrew Hunt and Dave Thomas.

At the time, I was only a year or two out of college with a fresh math degree and a bunch of Computer Science coursework. I wasn't really a programmer. I was a math / computer science nerd who had a programming job. When I started the job, I was paired with a mentor who taught me better practices at programming than what I picked up at school. Sadly, I cannot recall exactly what she taught me, because it all became ingrained in the way I work. I feel that it was things that are obvious to software engineers, but maybe not to math majors (to be fair, I believe she was a math major too, but had been working for ten years as a developer).

Then one day, I found this book at the library. I read it all in about two days. The stuff I have really taken from it is not really about programming, but the craft of programming, and ways to get better at it. When I left the job, I had a list of books I needed to buy … this was near the top of the list.

Some of the things I got from this book were the importance of learning the tools that I use for programming. I learned the about knowing your editor very well, learning a text processing language, and how much time the command line can save you. This led to me learning Emacs, Python, and Bash (then Z-Shell) pretty well. I am not an expert in any of these. I cannot do real tricky stuff off of the top of my head, but I do know where to look to figure stuff out. These skills are now some of my greatest strengths, though they don't really translate to a resume point very well. Part of how I get things done fast is that I let my tools do a lot of my work, and I am willing to spend time writing code to do my work for me.

Learning Python also fell under their recommendation to learn a new language every year. That is a goal I haven't really met, either, but I have probably read tutorials and documentations on far more than the 11 languages I should have learned the last 11 years. I just don't have applications for many of them, so I don't really learn them.

Version control was another topic I learned about from this book. **Gasp**. I know. It was 1999… I was a math major. Ok, I should have known better. I first learned RCS. CVS was a huge step up. I got along with CVS pretty well until Subversion came out. Then I flirted with several distributed version control systems, and am now pretty happy with Mercurial, although it looks like I need to be conversant in Git to get along in the open source world today. I have used Darcs, Arch, and Bazaar enough to say that I walked through their tutorials, and I remember some of the quirks of their developers.

There are some basic software design ideas in this book, but I think I learned a lot more about actual software from the references in the appendices of the book. This alone would have been worth the cost of the book to me. Again, remember it was 1999 or 2000. The appendices had a list of internet resources for things like programming languages, shells, editors, mailing lists. I went through a lot of those links. All the Python, Emacs, and Bash skills I built started there. Now that I look at it, even Z shell was in there.

Even more important was their bibliography of books. So, I was able to find the books that interested me easily from the library at work. The Practice of Programming, Effective C++, Sedgewick's Algorithms. From this start I was led to Programming Pearls, Code Complete, Writing Solid Code. I was humbled by many, but none as much as The Art of Computer Programming. (I'm not pretending I have managed to read much of that, and I still haven't bought my own copy)

Much of their soft suggestions seem like they should have been obvious, but Hunt and Thomas's book set me on a path of growth as a programmer. As a computer scientist too, if I can call myself that. They helped push my interest in computer languages to where I can now understand, but maybe not write, code in Lisp, Haskell, and Ocaml. I have looked into many languages, and for the most part only read enough to understand why they are different (Forth and Lua, maybe).

This book taught me some important things, but mostly it taught me that I have a lot to learn. That is what makes it the most important programming book I have read. Other books may be better, but this is the one that opened my eyes.

Thursday, January 20, 2011

Stackoverflow -- finally answered a question

Got my first selected answer on stackoverflow!  I waited several days to post the full solution, in case the competition in question was still running.  My hope was that people would down vote his question if that was the case.

My solution isn't elegant, but I thought it was a nice example of a recursive function that goes beyond the factorial function you normally see.  Ok, it isn't really a good example of recursion.   It is an example of using tail recursion to eliminate mutable variables that you would use in a while loop.  Oh well.



Thursday, January 6, 2011

Othello in Javascript

A few times I have tried this strategy to learn something new. I try to convert some code from a book into a different language. Just copying and running examples out of a book isn't very exciting, and it doesn't force me to understand what is going on in the code.

But porting to another language forces me to understand (better) what the original code is doing, why it is nice in the language used, and how to do the same thing in a different language.

The last few days, I ported code from Peter Norvig's Lisp AI Book into javascript. Learning more about lisp has been a goal of mine for years. Learning javascript is a more recent goal. I have always been interested in AI programming.

Here is the work in progress. Here are some of the known deficiencies:

  • very little testing or cleanup has been done
  • the GUI is a hack
  • there isn't a timer to let the computer know it took too long. On a fast computer, 6 ply look ahead may not be too bad
  • yeah, my use of the google app engine is probably lame. But it serves my static file for me.

The javascript code has a variety of influences. Norvig's code, of course, provides an often literal example. Crockford's book and website were a big help, although I probably didn't succeed in getting the good parts right. My F# experience led to the m_array library object at the top of the javascript file, even though everything I do in that library is probably available in javascript somewhere else.

I probably won't try to add the more advanced AI code from the book, and instead move on to playing with it in lisp.

If you see any dangerous problems here, I would like to know about it.