Archive for the ‘LINQ’ Category

Does Declarative Programming generally help?

Sunday, April 17th, 2016

A recent post compared different ways of approaching the same problem in Scala and Go:

https://www.quora.com/Scala-vs-Go-Could-people-help-compare-contrast-these-on-relative-merits-demerits/answer/Nick-Snyder-1?srid=dsGW&share=191eaf13

The Go approach is longer than the one in Scala, but every line is dead simple to understand. We might dismiss it as repetitive, boiler plate code rather than abstract, business logic. However, setting break points for debugging or changing the behaviour of the code when the new requirements arrive, six months down the line, is trivial. This can be a mixed blessing, as there’s really nothing to stop code like that ballooning in size as new conditional statements get added to cope with the changing needs of the software. Every 5 kLoC ball of mud that any programmer ever wrestled with started out as something dead simple like that.

The following article investigates how non-programmers approach programming problems and whether programming languages make the task harder because they do not match how an untrained mind thinks.

http://alumni.cs.ucr.edu/~ratana/PaneRatanamahatanaMyers00.pdf

More children developed rules to describe the behaviour of Pacman than instructions for the sprites to follow. People apparently start out thinking in a more declarative style and then develop the habit of thinking in the imperative style.

Is this an argument for using more declarative languages? If declarative programming is more natural, surely it would be easier. However, many programmers start out with imperative code and perhaps only try declarative code later. Is this just a historical or social accident caused by the greater availability of imperative languages compared to declarative ones? It is possible that this is a greater issue for novice programmers than for experienced ones.

Often, we cannot move between languages at whim. Few programmers have the privilege of being able to write part of their system in Go in the morning, then head over to Scala land after lunch. However, .Net has Linq, which affords a C# developer, like your author, greater freedom to move freely back and forth between imperative and declarative styles of programming.

Imagine a book stall in a market. There is a table with books with different numbers of pages with covers that are red or blue.

The types in this world are an enum for the colours and a class for the book:

enum Colour
{
    Red,
    Blue
}
 
class Book
{
    internal Book(string name, int numberOfPages, Colour colour)
    {
        Name = name;
        NumberOfPages = numberOfPages;
        Colour = colour;
    }
 
    internal string Name { get; }
    internal int NumberOfPages { get; }
    internal Colour Colour { get; }
}

We can model our bookstall with a list:

var books = new List<Book>
{
    new Book ("War and Peace", 1123, Colour.Red),
    new Book ("Doctor Zhivago", 803, Colour.Blue),
    new Book ("Jeeves and the Feudal Spirit", 154, Colour.Red),
    new Book ("Shogun", 1213, Colour.Red)
};

You want to write down the names of the books that are more than 500 pages long and have red covers. Here are three ways to solve this problem.

The imperative approach:

foreach (var book in books)
{
    if (book.Colour == Colour.Red && book.NumberOfPages > 500)
    {
        WriteLine(book.Name);
    }
}

This way, we are putting ourselves in the role of the person actually sifting through the books one by one and writing the names of the books that meet our criteria as we go. However, the presentation code (the WriteLine) is mixed up with the filtering logic in the loop.

Linq makes use of the Where extension method to allow the so-called fluent syntax:

var longRedBooks = books.Where(b => b.Colour == Colour.Red && b.NumberOfPages > 500);
 
foreach (var longRedBook in longRedBooks)
{
    WriteLine(longRedBook.Name);
}

Here, we first ask for the books that match our criteria, defined in the lambda expression passed to the Where method. Then, we print the books that matched. The filtering logic and presentation logic are now separate.

Using Linq’s query syntax below, the code looks quite different from the fluent syntax used above, but the meaning is the same. This approach is perhaps more familiar to developers with a background in SQL.

var longRedBooks = from book in books
                   where book.Colour == Colour.Red && book.NumberOfPages > 500
                   select book;
 
foreach (var longRedBook in longRedBooks)
{
    WriteLine(longRedBook.Name);
}

The complete source can be found on GitHub:
https://github.com/robert-impey/CodingExperiments/blob/master/C-Sharp/BookFinding/Program.cs

Which is easiest to understand? If the requirements change, let’s say that we now only want one book, which should be the longest book, shorter than 500 pages, with a blue cover, which approach will be easiest to update and understand with the new logic? With the Linq approach, we can take advantage of the type system to see that the query now returns a Book (which may be null) rather than an IEnumerable<Book> and handle the object appropriately. Will the change in meaning be as obvious in the imperative code?

For what it’s worth, I’ve experienced plenty of resistance in code reviews to Linq queries, but almost none to writing the same thing in a for loop. Sometimes the reasoning is to do with performance, but I doubt there’s much in that. Anyway, a read-only code review is a terrible place to make assumptions about relative performance. However, it’s very easy to reason about the performance of the for loop, but more advanced knowledge of lazy evaluation, the iterator pattern and its implementation is needed to understand what gets executed where and how many times for the linq approaches.

I would be very interested to see an analysis of open source projects that compared the frequency on these approaches to see what is the approach that people tend to settle on. Do pull request with Linq get accepted more or less often? Is code generally refactored from one to the other? In which direction?

How should this influence job interviews and hiring? If we want to hire experienced programmers, we could check for signs that their thinking has been moulded to the structures of industrial programming languages. Perhaps we should pity such creatures. Should we look for signs of skills in imperative programming in hands-on programmers and for a declarative approach in tech leads and more senior roles, where coordinating the efforts of several developers is the required skill?

Project Euler 1 in F# using Sequences

Wednesday, August 21st, 2013

I have written previously about solving the first problem on the Project Euler website using F# and Haskell.

The problem is to find the sum of the natural numbers that are divisible by 3 or 5 that are less than 1000. To solve this in F#, my first solution looked like this:

[0..999]
|> List.filter (fun x -> x % 3 = 0 || x % 5 = 0)
|> List.sum

This works. However, it was pointed out to me that using lists to generate the numbers below 1000 in my F# solution was memory hungry as the list will be created and stored in memory then piped to the filter and so on. The list is evaluated eagerly. This isn’t a problem with a small list like this, but it could create issues with more elements.

I took a look at sequences in F#, which are evaluated lazily. To get an idea of what this means, consider the sequence of natural numbers:

let countingNumbers = 
    seq { 
        for i in 1 .. System.Int32.MaxValue do 
            printfn "Yielding: %d" i
            yield i 
    }

If you are unfamiliar with lazy evaluation, it might look like this will create all the natural numbers up to System.Int32.MaxValue (2147483647) and print each number as it goes. However, if you run this with F# Interactive (aka fsi), it creates a seq<int> without printing anything out. At this point, the sequence is yet to be enumerated.

The ingenious thing about sequences is that we can work with them without enumerating them. Consider these lines:

let max = 999
let firstUpToMax = Seq.take max countingNumbers

The Seq.take function allows us to take the first elements in a sequence. However, running these lines in fsi does not cause the for loop in the sequence above to be run. The print and yield statements are not run.

F#’s ability to delay enumeration is not limited to sequences. Queries also allow us to describe a sequence of numbers without enumerating them.

I define the following function that will be used to filter the sequence:

let isDivisibleBy3Or5 x = 
    x % 3 = 0 || x % 5 = 0

and then create this query:

let divisibleBy3Or5 = 
    query {
        for countingNumber in firstUpToMax do
        where (isDivisibleBy3Or5 countingNumber)
        select countingNumber
    }

Programmers who are familiar with SQL or LINQ should have no problem understanding this query. In plain English, we might say “we will go through the sequence and find the values that match the given criterion.” Note the use of the future tense. Running this code in fsi does not result in enumeration of our sequence and the printing of the “Yielding…” lines.

I could find the sum of the numbers matching our criteria using a built in function like this:

let seqSum = Seq.sum divisibleBy3Or5

This will cause the sequence to be enumerated and finds the same sum as the list method above.

However, by defining the following function:

let noisySum total next =
    printfn "Adding %d to %d" next total
    total + next

I will be able to see the order in which the sequence is enumerated and when the values are pumped down the pipeline to be folded into the sum.

let seqFoldSum = 
    divisibleBy3Or5
    |> Seq.fold noisySum 0

At this point we get the following out put at fsi:

Yielding: 1
Yielding: 2
Yielding: 3
Adding 3 to 0
Yielding: 4
Yielding: 5
Adding 5 to 3
Yielding: 6
...
Yielding: 996
Adding 996 to 231173
Yielding: 997
Yielding: 998
Yielding: 999
Adding 999 to 232169
 
val seqFoldSum : int = 233168

Which clearly demonstrates the order of execution and that only the numbers that are divisible by 3 or 5 are added to the sum.

Does this make much difference to the memory usage? For this problem, this is not the bottle neck. The integers storing the sum of the numbers overflow before the input lists become large enough to use a lot of memory. However, passing values down the pipeline as they are yielded is somehow more pleasing to this programmer. Also, lazy evaluation means that enumerating the numbers and performing the mathematics do not take place until the result is actually needed. By creating a sequence and query, the programmer can create the code and pass it around the program without doing any heavy computation or using up much memory.

The complete listing of this code can be found at GitHub:

https://github.com/robert-impey/CodingExperiments/blob/master/F%23/Loose/Euler1.fs

Finding the Nearest Tube Station with LINQ

Tuesday, August 20th, 2013

I recently wrote a little command line program in C# that can tell you the name of the nearest tube station. I’ve put the program on GitHub in my Coding Experiments repository:

https://github.com/robert-impey/CodingExperiments/tree/master/C%23/NearestTube

The interface is very simple- this more of an experiment than something that I intend for mass consumption! You enter a location via the command line as the latitude and longitude:

Nearest Tube CLI

The starting point of the program was to calculate the distances between points. To do this I adapted some JavaScript code that John D. Cook wrote:

http://www.johndcook.com/lat_long_distance.html

Mathematical code looks very similar in many languages, and the translation from JavaScript to C# was trivially simple as the languages are very similar in this case. This code is part of the Point class:

        /// <summary>
        /// Porting JavaScript code from
        /// http://www.johndcook.com/lat_long_distance.html
        /// </summary>
        /// <param name="that"></param>
        /// <returns></returns>
        public double Distance(Point that)
        {
            // Compute spherical coordinates
 
            double rho = 6373;
 
            // convert latitude and longitude to spherical coordinates in radians
            // phi = 90 - latitude
            double phi1 = (90.0 - this.Latitude) * Math.PI / 180.0;
            double phi2 = (90.0 - that.Latitude) * Math.PI / 180.0;
            // theta = longitude
            double theta1 = this.Longitude * Math.PI / 180.0;
            double theta2 = that.Longitude * Math.PI / 180.0;
 
            // compute spherical distance from spherical coordinates
            // arc length = \arccos(\sin\phi\sin\phi'\cos(\theta-\theta') + \cos\phi\cos\phi')
            // distance = rho times arc length
            return rho * Math.Acos(
                    Math.Sin(phi1) * Math.Sin(phi2) * Math.Cos(theta1 - theta2)
                    + Math.Cos(phi1) * Math.Cos(phi2)) * 1000;
        }

Once I was able to calculate the distances between points on the map, I needed to be able to sort the tube stations of London by distance from the given point. This is the sort of code that LINQ to objects handles very naturally. In the SequentialTubeStationFinder class, I have the following method:

        public TubeStation FindNearestTubeStation(Point point)
        {
            return (from tubeStation in tubeStations
                    orderby tubeStation.Point.Distance(point)
                    select tubeStation).First();
        }

tubeStations is a generic list of TubeStation objects. Each has a Point property that is used to sort the tube stations and find the nearest one to our location.

The declarative style of programming that LINQ uses is much easier to read (and therefore maintain) than the equivalent code written with a for loop.