On Beyond Lambda

Project Euler and Refactoring

2012-02-15T07:34:00.002-08:00

I started doing the problems on Project Euler the other day. For anyone that doesn't know, Project Euler is a website that has a collection of math problems for you to solve. You can solve the problem any way you want. The site keeps track of which problems you have submitted correct answers to.

Just finding the right answer is a good programming challenge, but refactoring makes for much deeper learning.

Another benefit from doing the problems is that you are building samples of your work that you can show to prospective employers. If you are going to show the world your code, you want it to be clean.

Here is an example of my process solving one of the problems in Clojure. I can't show what I have learned without displaying my ignorance, but I am less ignorant now because of this process.

Every line of code you see here represents at least 5 lines of experimentation preceding it.

Problem 3 asks, "What is the largest prime factor of the number 600851475143 ?"

Solution 1

Find all of the divisors of n, filter the ones that are prime and then take the largest. To find all of the divisors, iterate through all of the numbers from 1 to n, and test remainder of n divided by i.

Works just fine with 42. Doesn't show any signs of returning with 600851475143 . Restart the REPL.

Learned a bit more about 'for' like the difference between :while and :when.

Solution 2

Create a function that finds a single factor, called afactor. In Clojure you don't use loops with breaks, you use sequences and take the items you want. Lazy sequences don't calculate numbers until you ask for them, so you can create an expression which calculates all of the divisors, but only actually calculate one or two.


(defn afactor [base]
  (nth (for [x (range 1 (+ 1 base))
             :when (= 0 (rem base x))] x ) 1))

Learned how to use 'for' in a lazy way.

Now to create a function that returns a pair of factors.


(defn factor [base]
  (let [first (afactor base) ]
    (list first (/ base first))))

Got more confidence with 'let' binding.

The next step is a test whether a number is prime. A prime number has 2 divisors, but counting the number of divisors of our number is going to leave us restarting the REPL again, which of course is just a menu item in Clooj, but it is painful to admit that I was dumb enough to think that would work, so we will skip that step. Since a prime number is only divisible by 1 and itself, its 2nd largest factor will be itself.


(defn prime? [base]
  (= base (afactor base) ))

I assumed (= base (afactor base)) would allow me to return a boolean, glad to see that it actually does.

The first call to factor with our number yields a result large enough that I don't care to retype it. Let's set up a manual recursion of 1 level.


(defn prob3 [base]
  (map factor 
       (filter #(complement prime?
                (factor base)))))

Playing around with this function and others like it really got me confident with the #(%) syntax of anonymous functions. Not long ago they were a mystery, but with repetition they are comfortable.
Playing with the ugly (map factor (filter ... construction was good practice with maps and lists even if the resulting code is terrible.

It is not hard to see a way to the right answer from this. Either you take the output of prob3 and call prob3 again, typing in the first result, or you could nest the map factor filter inside of another map factor filter. This isn't anything you are going to show off to your friends.

Solution 3

Solving a problem earlier on 4clojure I found out that Clojure has a function called tree-seq. We always drew trees when we were factoring numbers in school, so that will probably yield a more satisfying result. Tree-seq takes 3 parameters, branch? children and root. branch? is a function that tests whether a node has children, children is a function that returns the children for a node and root is the initial value.


(defn factor-tree [base]
  (tree-seq (complement prime?) factor base))

I got to learn how to use tree-seq. Also, prime? was returning true when a node didn't have children, exactly opposite the desired result. After (not prime?) failed, I understand when to use not and when to use complement.

factor-tree is returning a list of all of the factors. That is easy enough to handle. Getting all of the prime factors we may want to do on another problem, so lets give it its own function.


(defn prime-factors [base] 
    (filter #(prime? %)  (factor-tree base)  ))

For this problem, we just want the largest prime factor.


(defn problem3 []
  (apply max (prime-factors 600851475143)))

I was surprised that I had to type (apply max(...)) instead of just (max (..)). In the imperative world so often you are calling methods on parameters, so it is not hard to think of LISP syntax differently. Every language I have ever used though has had a function called max that operates on a list of data, which is why it is hard for my brain to see that max(list) isn't correct.

Solution 4

Using the tree-seq makes for a much nicer solution, and I was tempted to stop there. One thing still bothered me though. In one video I saw, Stuart Halloway said that with lazy evaluation, there seldom was a reason to return just one of anything. It is much more flexible to return a sequence and let the caller decide which elements they need.


(defn afactor [base]
  (nth (for [x (range 1 (+ 1 base))
             :when (= 0 (rem base x))] x ) 1))

Needs to be rewritten.


(defn lazy-factor [base]
  (for [x (range 1 (+ base 1))
     :when (= 0 (rem base x))]
     x ))

The idea of returning a lazy sequence instead of a single value is a different philosophy that I have used in the past.

As you can see, the change was very minor. In fact, it is easier to do it the right way than the wrong way. If I hadn't rewritten it, I never would have found that out!

Because I am now returning a lazy sequence instead of a single element, I do have to modify the callers to choose the element they want.


(defn prime? [base]
  (= base (nth (lazy-factor base) 1)))

(defn factor [base]
  (let [first (nth (lazy-factor base) 1) ]
    (list first (/ base first))))

Solution 5

I thought I was done, but moving when I moved on to other problems, I kept finding myself typing things like (range 1 (+ 1 base)), as I did in the lazy-factor function. Range is built to give you a c style loop, so (range 5) gives you (0 1 2 3 4). Usually this is fine, but for the Project Euler problems, I constantly find myself wanting a basic style loop, (1 2 3 4 5) instead. This was enough motivation for me to attempt my first macro.


(defmacro rangeb [last]
  (list 'range 1 (list '+ 1 last)))

With this change, lazy-factor becomes:


(defn lazy-factor [base]
  (for [x (rangeb base)
     :when (= 0 (rem base x))] 
     x ))

Conclusion

I expect that in the not too distant future I will be able to look back at this post and cringe. I am sure that I will find other situations where I find a simpler way to do things and will be tempted to refactor again.

I find myself using 'for' quite a bit, though only in the factor function (afactor and then its replacement lazy-factor) here. for feels imperative, and I wonder if I am overusing it.

My rangeb macro is overly specific. Right now you can only pass an ending number; it always starts at one and increments by one. When the spirit moves me, or when a situation demands it, I will update it. In the meantime I will pretend that YAGNI applies here.

One other thing I think my subconscious is learning is how easy it is to write and test things in Clojure. Next time I use C# I am sure I am going to miss the REPL. Even now, I can ponder having to write methods to call and output my code, compiling every change. /shudder

What is functional programming?

2012-02-11T11:18:00.000-08:00

One assertion made a lot is that functional programming is an important concept for handling concurrency. So what is functional programming, and how is it applicable to concurrent programming?

While there are a lot of topics can be included in a discussion of functional programming, there are two key ideas: Higher order functions and pure functions.

Higher Order Functions

Higher order functions are functions that are meant to be applied to other functions. They can also be thought of as functions as data. The idea is that functions can be passed as parameters to a function or a function can return a function.

A common example of passing a function as a parameter is passing a function to filter data. Using Linq in C# you may write something like:


    var GeorgiaCustomers = Customers.Where (c => c.StateCode == "GA");

The section in parenthesis is called a lambda expression. Read aloud it is "C goes to c dot statecode equals GA". The lambda expression is a function that we are passing as a parameter to the Where method of the Customers collection. The function StateCode == "GA" is applied to each item in the Customers collection; if the function returns true, that gets added to the new GeorgiaCustomers collection.

The Where method takes a single parameter, which is a function that takes a customer and returns a boolean (whether the StateCode matches).

Pure Functions

Pure functions are functions that return a value without having any side effects. Side effects are changes in things outside of a function, such as printing text to the screen, or setting a property or updating a database.

Here is an example in C#.

imperative:


     public static void doubler(int input) 
     { 
          Console.WriteLine(" {0} doubled = {1}.", input, input * 2) 
     } 

     public static void main(string[] args)
     {
          doubler(2);
     }

functional:


     public static int doubler(int input) 
     { 
           return input * 2 ; 
     }

     public static void main(string[] args)
     {
           int result = doubler(2);
           Console.WriteLine(" {0} doubled = {1}.", 2, doubler(2))   
     }

While this is a silly example, the difference is clear. In the imperative example we are calling a double and print method, and in the functional example we are calling a double method and printing the result. Which is more reusable? Which is easier to test?

Why is this important

If you want to start executing programs on multiple processors you need to break the work into pieces that can be run independently. Consider a function that will return the sum of the squares of a range of numbers. In C#, you might write something like:


int SumSquares(int maxInput)
{
     int accumulator = 0;
     for (int x = 1; x <= maxInput; x++)
     {
          accumulator += x * x;
     }

     return accumulator;
}

This code is written to be executed sequentially. You have single thread of execution which accumulates a value and increments a counter each time through a loop.

In F# it would be more natural to write the program like this:


let SumSquares maxInput =
    {1 .. maxInput}
    |> Seq.map(fun x -> x * x)
    |> Seq.sum

The Seq.map function is working exactly like the Where method did in our first example. It is being passed a lambda function and applying it to a list of items. It is returning a list of the results.

The |> operator takes the output of a function and sends it as an input of the next function.

First we create a list of numbers and then we pass that as an input to a function which returns a list contains the squares of an original list of numbers.

This list is then being applied to the Seq.Sum method, which is a function that returns the sum of all of the elements in a list.

The same function in Clojure could be written:


(defn SumSquares  [maxInput]
  (reduce +
       (map (fn [x] (* x x))
              (range 1 (+ maxInput 1)))))

The syntax is different, but this works the same as the F# version. Working from the inside out (and bottom to top) we create a range from 1 to the maxInput, which we input to the map function which applies the square function to each element.

The important feature of both the F# and Clojure implementations is that by passing an anonymous function and a list to a map function and then only doing the accumulation after the fact, each number in the list can be processed independently.

Neither of these implementations is actually running in parallel right now, they are just written in a way that will easily support parallelism.

Continuing on with the Clojure version, to make it parallel all we have to do is change the map function to pmap. I am also going to modify my anonymous function so that it produces a side effect to show that it does work in parallel and why side effects in parallel programs cause problems.

The new version is:


(defn SumSquares  [maxInput]
  (reduce +
  (pmap (fn [x] 
         (do
           (println x) 
           (* x x)))
    (range 1 (+ maxInput 1)))))

In this version, the anonymous function now prints out its input and then returns the square of the input. Running it twice, I got the following 2 results:

We are no longer guaranteed that our map will execute in a particular order. Adding the side effect of writing to the console just looks strange. I especially like the second execution where the program switched from the 1 thread to the 4 thread before the 1 thread wrote its own newline character, which is how we ended up with 14 on the first line and then a blank line a couple lines later.

Summary

Writing in a functional style supports breaking work up into pieces that can be run in parallel. Being able to pass functions as parameters to higher order functions allows for the creation of things like pmap which handle the dispatching of work to different threads. Writing pure functions, without side effects, leads to solutions that can be broken into the smaller independent pieces that can be passed to a map or pmap function.

Why C++ and where to look

2012-01-31T07:44:00.000-08:00

The theme of this blog is finding out how programming will have to change to deal with computers containing dozens or hundreds of processors. So far most of the posts have been related to Clojure. In addition to Clojure, F# and C# also have good answers to parallelism.

The approach in all three of these languages is to write applications that can be run in parallel safely, so that you can benefit from having multiple processors without breaking anything. In all three cases, the actual hardware is abstracted away.

In addition to the number of processors in a machine though, we are also seeing a diversity of processors being used within a single machine. Graphical Processing Units are very powerful, but their vector processing gives a bigger boost to some operations than others. GPUs and other chips have reduced instruction sets, which means that some code that is perfectly legal on a CPU won't work on a GPU.

Reducing the number of clock-cycles and choosing lower power processors are important whether you are trying to increase the battery life of a mobile device or having to power (and cool) a server farm. Cloud computing, which provide CPUs as a metered service, also encourages using cycles sparingly.

If you want to be optimizing cycles and choosing chips you need to be running "on the metal" and that means C or C++.

There have been a lot of changes to C++ in the C++ 11 specification. There are also new libraries that deal specifically with the problems of developing on different types of chips. When even Microsoft, with their traditional focus on drag and drop development and managed code, starts talking about a C++ renaissance you know it is a big deal.

Microsoft is hosting a 2 day "Going Native" event on February 2nd and 3rd. The event is being streamed live (for free) at http://channel9.msdn.com/Events/GoingNative/GoingNative-2012. I am sure they will also have videos of the keynotes and sessions available later on the channel 9 site.

I will not watch it live (I am still trying to learn Clojure), but it is timely information, so I thought I would pass it along.

Setting up clojure emacs on windows

2012-01-25T11:42:00.000-08:00

Setting up a Clojure development environment proved to be quite a challenge, especially given my handicap of using Windows.

The most widely used editor for Clojure is Emacs. I don't have any idea how to use it, but I have seen video of people who know what they are doing, and I really want that!

There are lots of options for setting up Clojure. If you are just starting out, there are too many. There are at least half a dozen editors that have Clojure plug-ins. Emacs itself has two. The instructions available also tend to present different ways of accomplishing the same thing.

I am not going to give you lots of options. I am going to give you the steps to go from a clean Windows 7 install to having the most popular plug-in for the most popular editor using the most popular build tool for Clojure. I am sure there is a lot of value to all of the flexibility that other people support, but it is lost on me and if you are reading this, it is probably lost on you too.

Also, I intend to cover each step in excruciating detail. I know from experience that any instructions on this subject, no matter how detailed, would include at least one or two steps that assumed I actually knew how to use Emacs. If you follow these instructions and there is a step that is not completely clear to you, please put it in the comments so that I can fix it. If the detail is too much for you, just read the bold print!

Our goal is to have a working installation of the Leiningen build tool, and the SLIME plug-in for the Emacs editor.

Before I start, let me say this works best if you do not already have clojure installed on your computer, or more specifically that you do not have the clojure.jar file in your class path. The Leiningen install will fail if you do.

Install the Java Development Kit (JDK )

Version 1.6 or better is required, I am running 1.7 Standard Edition. Download this from Oracle. There is also a link to installation instructions on that page.

After jdk is installed you need to make sure that the environment variables are set up correctly. (Control Panel >> System and Security >> System >> Advanced system settings >> Environment Variables...)

Under user variables I have JAVA_HOME with a path to the folder where the jdk is installed. On my system this is C:\Program Files\Java\jdk1.7.0_01

Under System Variables, the java bin directory needs to be in your path. click edit on the path, so you can scroll through and look to see if these settings are already there, and if not add them (path items are separated with ; on windows) %Java_Home%\bin\ and the physical path to the bin directory that holds the jdk executable. In my case this is C:\Program Files\Java\jdk1.7.0_01\bin\

Test the java installation by going to a command prompt (click the windows button in your taskbar and type cmd in the search box) at the command prompt type:
javac -version
if the computer responds with a version number the jdk is set up properly, if it says that javac is not found, you have a problem you need to fix before you move on.

Install Leiningen

(build tool)
Create a folder that will hold the leiningen batch file and also a helper utility it needs. Mine is in c:\lein. to create it I went to the command prompt, typed
cd \
md lein
After that type exit to close that command prompt window. Add the path to your new folder to your path setting.

Download curl from
http://www.paehl.com/open_source/?download=curl_723_1_ssl.zip
and place curl.exe and into your new folder.

download libssl from
http://www.paehl.com/open_source/?download=libssl.zip
and place libeay32.dll and ssleay32.dll into your new folder.

Download the lein.bat file from
https://raw.github.com/technomancy/leiningen/stable/bin/lein.bat
and put it in to your new folder. (My browser displayed the text, so to save it I did file >> save page as and then navigated to my c:\lein folder.

Open a new command prompt and type
lein self-install

After the installation completes you can test your leiningen install by typing
lein repl
at the command prompt. It should launch the clojure repl which you can test by typing
(+ 1 2)
at the user prompt.

click the x in the upper right to close the command prompt.

Install Emacs

(Editor)
Download emacs from
http://ftp.gnu.org/pub/gnu/emacs/windows/emacs-23.1-bin-i386.zip
extract the emacs-23.1 folder, and put it somewhere. I just put mine in c:\

Create a folder to hold plugins for emacs named .emacs.d I put mine in my emacs-23.1 folder.

Create a new user environment variable called HOME in the value put the path to the .emacs.d folder. in my case this is C:\emacs-23.1

Add the path to the emacs.exe folder to your path. mine was C:\emacs-23.1\bin

Install Clojure mode

Create a file called init.el in your .emacs.d folder and enter this text
(add-to-list 'load-path "~/.emacs.d/")
(require 'clojure-mode)
Add the file clojure-mode.el from
https://github.com/technomancy/clojure-mode/blob/master/clojure-mode.el
to your .emacs.d directory. I found the easiest way to do this was to copy the text in the code window at that url and paste it into a new text file that I called clojure-mode.el. If you just download the webpage, you will get lots of html commands that will cause errors in emacs.

Install Swank plugin

open a new command prompt and type
lein plugin install swank-clojure 1.3.4
-- note initially this install got hung for me, when I disabled avg link scanner it worked right away.

Create a new Clojure projectfrom the command prompt, navigate to a folder where you would like to create clojure files.from c:\Users\Rick I typed
md projects
then
cd projectscreate the new project by typing
lein new testproj
then type
cd testproj
emacs

after emacs loads type
alt-x clojure-jack-in
emacs will spend a couple of moments processing the plugin.After this, you should have a running REPL that you can test the same way that you tested the repl from leiningen. type
(+ 1 2).
If you get 3, it works.

Clojure is one answer

2012-01-23T09:37:00.000-08:00

My last post was a link to a video talking about the challenges of many-core computing. Today I am linking to another video from Channel 9. This one is a discussion with Rich Hickey about Clojure. The topics build on one another: introducing Clojure, why Clojure is a lisp, functional programming, lists and vectors, persistent data structures, identities and concurrent programming. I recommend the whole video, but if you just want to jump to the section on concurrency that starts at 37:15.

edit: For people who didn't like the embedded player, here is the link to the video on msdn.

Laying out the problem

2012-01-12T12:35:00.000-08:00

I recently saw a video on Channel 9 that provides a great background on parallel programming.

The amount of information available to developers from Channel 9 is incredible. Naturally there is good coverage of Microsoft technologies, but there is also a lot of material that has nothing to do with Microsoft.

The video is an interview with Burton Smith. I recommend it to anyone.

If you don't want to watch the interview, or the whole interview, here is how I would break down the talk:

(0:30)Hardware for mainstream computing is changing in a way that makes ideas that were once only relevant to supercomputers important to the mainstream.

(1:52)Multi-core refers to 8 or fewer processors, multi-core refers to either more than 8 processors, or utilizing different types of processors such as CPUs and Graphics Processing Units.

(3:08) In the early days super computers were powerful machines used for general purpose, transactional processing tasks.

(4:05) The introduction of vector processing caused supercomputing to become much more specialized. Programs that had a lot of branching could not benefit from vector processing. Tasks that involved performing the same operation across a set of data could be written to use Instruction Level Parallelism were able to get big gains from vector processing.

(5:37) After vector processing, the next big change was distributing computations among many smaller computers. This is the state of super computing today. Distributed parallel computing works by different machines sending messages to each other, though within each machine itself there may not be any parallel processing going on. In practice this makes supercomputing even more specialized than vector processing did.

(7:17) Now that mainstream computers are being built with multiple cores, the goal is to make parallel processing very general.

(8:56) In the 80s people realized that the physical limits of a single core would be reached. Their research didn't lead to success in the marketplace, but we can learn today from the knowledge they gained.

(10:00) It is not only computer architecture that you worry about. One of the major problems is programming languages.

(10:45) A decision made at the foundation of computing that is inhibiting attempts at parallelization is the idea of a variable.

(11:32) In a computer that executes one instruction at a time, you know the order in which the instructions will be done.

(14:28) Smith gives an analogy of parallel computing by describing a development team and talking about the implication of an office full of programmers working together to write a piece of software. He describes the risks of mutability and the strengths of messaging and immutability.

(16:25) Tweaking C++ a little bit isn't sufficient for solving parallel problems. The transformation needed is much more radical and will change programming styles for ever.

(20:33) The dominant programming languages today require the reading and writing of shared data. The programs are challenging and difficult to maintain as a result.

(21:00) Software Transactional Memory is one of the alternatives being pursued today.

(21:46) SQL is a functional programming language that a lot of people are able to use and understand. When people wish to modify data they use transactions.

(22:46) Excel is a functional programming environment. Every cell contains either a value or an expression that is a function of other values.

(26:28) Even in a parallel functional program, when state is modified it is still done sequentially. The difference is the imperative state changes become isolated pieces of a program.

(30:54) Databases are an example of a persistent store that has to be accessible in parallel, with changes done in isolation.

(32:43) Databases combine transactions with functional programming. That is the most successful parallel programming in the world.

(33:03) "There are only 3 ways to do parallel computing: 1. Get an expert. 2. Use functional Language. 3. Use transactions."

(33:40) Changes have to be done in isolation, but there are many ways to get the isolation in either space or time.

(33:20) Based on our experience with databases, transactional memory should be able to scale very well, but just adding to C++ probably won't be enough.

-- After that is a long discussion about different levels of programming and making parallelism more accessible. It is a fascinating discussion, but tougher to tease out parts for this blog.

Something to look forward to

2012-01-10T12:30:00.000-08:00

One of the problems that developers have to learn to address is concurrency. I expect this to be a recurring theme on this blog. From what I have seen Clojure is the language best suited to dealing with concurrency.

Rather than talking about the different problems of multi-threaded programming and how they are addressed with Clojure, as if it is some necessary evil, here is a great presentation about Clojure's strengths before even considering the issue of concurrency.

This is from Stuart Halloway, author of Programming Clojure. This was filmed at Øredev 2009.

It appears Vimeo doesn't want me to embed it, so here is the link:

Clojure - Stuart Halloway

Why?

2012-01-07T07:31:00.000-08:00

Every blog must have a first post. The usual model is to lay out some grand ambitions and ideals to inspire embarrassment or regret in the author later. In lieu of that, I will admit that this is my third attempt at blogging.

The first blog was about .NET programming that I started when I was playing with WinFX and Indigo, which became Windows Communication Foundation in .NET 3.0. I think I wrote 4 posts. I don't even remember the name of that blog now.

The second was an attempt at non-fiction prose. I wrote a bit more there, but no where near as much as I had hoped. That was a grand vision that didn't pan out.

So why a new blog? Because I am more excited about programming than I have been since at least the WinFX beta, possibly even more than when I first switched to .NET in 2002, and maybe since ever.

Computer platforms are mobile, multi-core and distributed. But sometimes developers are so focused on the problems they face day to day that they don't have a chance to see how the world has changed around them.

Think of this blog as the diary of Rip Van Programmer. I have recently woken up and now I have to learn to live in this strange modern world.

This blog is about the process of my learning. I hope that it will contain useful things for others, but I expect to make mistakes along the way. If a year from now I can't look back and find mistakes in this blog it will have been a failure.

If you see mistakes or better ways to do things, please tell me!