Readable, or reason-aboutable?

My coworker Tom finds Ruby unreadable.

What?? I’m thinking. Ruby can be quite expressive, even beautiful.

But Tom can’t be sure what Ruby is going to do. Some imported code could be modifying methods on built-in classes. You can never be sure exactly what will happen when this Ruby code executes.

He’s right about that. “Readable” isn’t the word I’d use though: Ruby isn’t “reason-aboutable.” You can’t be completely sure what it’s going to do without running it. (No wonder Rubyists are such good testers.)

Tom agreed that Ruby could be good at expressing the intent of the programmer. This is a different goal from knowing exactly how it will execute.

Stricter languages are easier to reason about. In Java I can read the specification and make inferences about what will happen when I use the built-in libraries. In Java, I hate the idea of bytecode modification because it interferes with that reasoning.

With imperative code in Java or Python, where what you see it what you get, you can try to reason about these by playing compiler. Step through what the computer is supposed to do at each instruction. This is easier when data is immutable, because then you can trace back to the one place it could possibly be set.

Beyond immutability, the best languages and libraries offer more shortcuts to reasoning. Shortcuts let you be sure about some things without playing compiler through every possible scenario. Strong typing helps with this: I can be sure about the structure of what the function returns, because the compiler enforces it for me.

Shortcuts are like, I can tell 810 is divisible by 3 because its digits add to a number divisible by 3. I don’t have to do the division. This is not cheating, because this is not coincidence; someone has proven this property mathematically.

Haskell is the most reason-aboutable language, because you can be sure that the environment won’t affect execution of the code, and vice-versa, outside of the IO monad. Mathematical types like monoids and monads help too, because they come with properties that have been proven mathematically. Better than promises in the documentation. More scalable than playing compiler all day.[1]

“Readability” means a lot of things to different people. For Tom, it’s predictability: can he be sure what this code will do? For many, it’s familiarity: can they tell at a blink what this code will do? For me, it’s mostly intent: can I tell what we want this code to do?

Haskellytes find Haskell the most expressive language, because it speaks to them. Most people find it cryptic, with its terse symbols. Ruby is well-regarded for expressiveness, especially in rich DSLs like RSpec.

Is expressiveness (of the intent of the programmer) in conflict with reasoning (about program execution)?


[1] “How do you really feel, Jess?”

We want to keep our programs simple, and avoid unnecessary complexity. The definition of a complex system is: the fastest way to find out what will happen is to run it. This means Ruby is inviting complexity, compared to Haskell. Functional programmers aim for reason-aboutable code, using all the shortcuts (proven properties) to scale up our thinking, to fit more in our head. Ruby programmers trust inferences made from example tests. This is easier on the brain, both to write and read, for most people. It is not objectively simpler.

Left to right, top to bottom

TL;DR – Clojure’s threading macro keeps code in a legible order, and it’s more extensible than methods.

When we create methods in classes, we like that we’re grouping operations with related data. It’s a useful organizational scheme. There’s another reason to like methods: they put the code in an order that’s easy to read. In the old days it might read top-to-bottom, with subject and then verb and then the objects of the verb:

With a fluent interface that supports immutability, methods still give us a pleasing left-to-right ordering:
Methods look great, but it’s hard to add new ones. Maybe I sometimes want to add functionality for returns, or print a gift receipt. With functions, there is no limit to this. The secret is: methods are the same thing as functions, except with an extra secret parameter called this
For example, consider JavaScript. (full gist) A method there can be any old function, and it can use properties of this.


var
completeSale = function(num) {
console.log("Sale " + num + ": selling " 


+ this.items + " to " + this.customer);
}

Give that value to an object property, and poof, the property is a method:

var sale = {

customer: "Fred",

items: ["carrot","eggs"],

complete: completeSale

};
sale.complete(99);
// Sale 99: selling carrot,eggs to Fred

Or, call the function directly, and the first argument plays the role of “this”:

completeSale.call(sale, 100)
// Sale 100: selling carrot,eggs to Fred
In Scala we can create methods or functions for any operation, and still organize them right along with the data. I can choose between a method in the class:
class Sale(…) {
   def complete(num: Int) {…}
}
or a function in the companion object:
object Sale {
   def complete(sale: Sale, num: Int) {…}
}
Here, the function in the companion object can even access private members of the class[1]. The latter style is more functional. I like writing functions instead of methods because (1) all input is explicit and (2) I can add more functions as needed, and only as needed, and without jumbling up the two styles. When I write functions about data, instead of attaching functions to data, I can import the functions I need and no more. Methods are always on a class, whether I like it or not.
There’s a serious disadvantage to the function-with-explicit-parameter choice, though. Instead of a nice left-to-right reading style, we get:

It’s all inside-out-looking! What happens first is in the middle, and the objects are separated from the verbs they serve. Blech! It sucks that function application reads inside-out, right-to-left. The code is hard to follow.

We want the output of addCustomer to go to addItems, and the output of addItems to go to complete. Can I do this in a readable order? I don’t want to stuff all my functions into the class as methods.
In Scala, I wind up with this:

Here it reads top-down, and the arguments aren’t spread out all over the place. But I still have to draw lines, mentally, between what goes where. And sometimes I screw it up.

Clojure has the ideal solution. It’s called the threading macro. It has a terrible name, because there’s no relation to threads, nothing asynchronous. Instead, it’s about cramming the output of one function into the first argument of the next. If addCustomer, addItems, and complete are all functions which take a sale as the first parameter, the threading macro says, “Start with this. Cram it into first argument of the function call, and take that result and cram it into the first argument of the next function call, and so on.” The result of the last operation comes out. (full gist


\\ Sale 99 : selling [carrot eggs] to Fred


This has a clear top-down ordering to it. It’s subject, verb, object. It’s a great substitute for methods. It’s kinda like stitching the data in where it belongs, weaving the operations together. Maybe that’s why it’s called the threading macro. (I would have called it cramming instead.)

Clojure’s prefix notation has a reputation for being harder to read, but this changes that. The threading macro pulls the subject out of the first function argument and puts it at the top, at the beginning of the sentence. I wish Scala had this!
—————–
Encore:
In case you’re still interested, here’s a second example: list processing.

Methods in Scala look nice:

but they’re not extensible. If these were functions I’d have:

which is hideous. So I wind up with:
That is easy to mess up; I have to get the intermediate variables right.
In Haskell it’s function composition:
That reads backwards, right-to-left, but it does keep the objects with the verbs.

Notice that in Haskell the map, filter, reduce functions take the data as their last parameter.[2] This is also the case in Clojure, so we can use the last-parameter threading macro. It has the cramming effect of shoving the previous result into the last parameter:

Once again, Clojure gives us a top-down, subject-verb-object form. See? the Lisp is perfectly readable, once you know which paths to twist your brain down.

Update: As @ppog_penguin reminded me, F# has the best syntax of all. Its pipe operator acts a lot like the Unix pipe, and sends data into the last parameter.
F# is my favorite!
————
[1] technical detail: the companion object can’t see members that are private[this]
[2] technical detail: all functions in Haskell take one parameter; applying map to a predicate returns a function of one parameter that expects the list.

Property-based testing of higher-order functions

Property-based testing and functional programming are friends, because they’re both motivated by Reasoning About Code. Functional programming is about keeping your functions data-in, data-out so that you can reason about them. Property-based testing is about expressing the conclusions of that reasoning as properties, then showing that they’re (probably) true by testing them with hundreds of different input values.

example:
Person: “By my powers of reasoning, I can tell that this code will always produce an output collection longer than the input collection.”

Test: “For any generated collection listypoo, this function will return a collection of size > listypoo.size.”

Testing Framework: “I will generate 100 different collections, throw them at that test, and try to make it fail.”

Property-based testing gets tricky when I try to combine it with another aspect of functional programming: higher-order functions. If the function under test accepts a function as a parameter, how do I generate that? If it returns a function, how do I validate it’s the right one?

In the trivial case, we pass in the identity function or a constant function, and base our expectations on that. But that violates the spirit of generative testing.

Test operate on values. Values go in, values go out and we can check those. Functions are tested by operating on values. So to test functions that operate on functions, we need to generate functions that operate on values, and generate values to test the functions that came out of the function under test. Then we’ll need to state properties in terms of values going in and out of functions going in and out… ack! It’s Higher-Order-Property-Based Testing.

My sources on twitter tell me that QuickCheck for Erlang and Haskell have generators for functions. Looking at this sample of the Haskell one, I think this is what it does:

Each generated function from A => B includes a random factor that’s constant to the function, and a generator for B that can create Bs based on a seed. When an A is passed in, it’s combined with the function’s random factor to prod the generator into creating a deterministically-random B.

So, we can create random functions A=>B if we have a generator of B, a random-factor-generator, and some mapping from (A, random-factor) to the seed for the generator of B. That doesn’t sound so bad.

There are two other functionalities in good generators. When a test fails, we need enough information to figure out why and fix the bug. One tool for this is shrinking: make the generated input simpler and simpler until the test doesn’t fail anymore, and then report the simplest failing case. I haven’t even started thinking about that in function-generation. (Does Haskell or Erlang do it?)
The second tool for fixing failed tests is simpler: print out the input that revealed the bug. That’s also hard with generated functions. Since the generated functions described above are random mappings from input to output, printing the actual input-output mapping used in the failing property evaluation should be sufficient. This is implemented in Haskell, with no state, so it must be possible in Scala and Erlang. And it’s in F#.

Like everything in property-based testing, generic input generation is the easy part (even when it isn’t easy). Describing properties expected of output functions based on input functions – now that sounds hard. When I write a test that does it, that’ll be worth another post.

Thanks to @reiddraper, @ericnormand, @silentbicycle, @natpryce, @deech, @kot_2010 and everyone who chimed in. Please continue.

Mental revolution

The book Structure of Scientific Revolutions (1962, Thomas Kuhn) brought the word paradigm into common use. Ideas from fifty years ago about research science apply today to computer science and the software industry. This is one parallel Kuhn makes, extended to illuminate how we think about programming.

The human mind does not perceive objects incrementally, feature by feature. We grasp images as coherent wholes. Sometimes when we step back, we can see the object in a new way. When we step back even farther, we might perceive it as something more basic and universal.

For instance, consider:

What do you see first, the duck or the rabbit? Now that I mention them, do you see them both? You can switch back and forth between them at will. If you stare at the picture long enough, you might see it instead as a collection of lines. You can perceive these lines as forming a duck or a rabbit, but in both cases you see the more universal nature of the lines.

This is like the wave-particle duality of light. A millenium ago, light was pictured as a particle. About five hundred years ago, Descartes observed that it behaved like a wave. Newton saw light as particles. Maxwell showed that light is waves. Einstein saw the particle nature of light again, and finally combined the two. Stepping back, it turns out that all particles have wave-like properties. Just as all duck drawings and all rabbit drawings are composed of lines, all matter has a quantized wave nature.

This same process of discovery can apply to software design. Take, for instance, the Strategy Pattern. Say we need to tell our SearchEngine at construction which RankingAlgorithm it should use. In an object-oriented design, such as for Java, it looks like this:

From a functional programming paradigm, it’s simpler. For a first implementation, we might give the search a lambda or a reference to a ranking function that translates a document to something orderable.

search :: (Document -> Ord) -> Doc[] -> String

These are two ways to view the same solution – either we’re implementing the Strategy pattern, or we’re passing in a function. When both of these views make sense, take a step back and observe that in both cases we’re doing the same thing: we’re passing a behavior. Look at it as a Strategy or as function-passing, whatever is better suited to our environment. Understanding both views and the common principle behind them gives a broader perspective on design.

This is a simple example, but the principle applies to many concepts in programming. Playing with Hadoop and then doing list processing in a functional language can show the common nature of map-reduce. Seeing the commonalities between two views of the same concept shows what is core to map-reduce and what is an implementation detail specific to Hadoop.

Get too focused on the duck, and you might never see the lines. In software, as in life, it helps to adopt a new paradigm. After we see a problem in a new light, we can step back and look for the broader concepts. This leads to a new level of understanding we can never see if we keep insisting that light is a wave and that picture has a beak.

Finding Primes in Haskell

I’m currently distracted from life, immersed in Concepts of Modern Mathematics.

Did you know that you can find out whether a number is prime by multiplying all the integers before it, adding one, and then dividing by the number of interest? Me neither! it’s like this:


a number p is prime if and only if: (1*2*3*...*(p-1) + 1) mod p = 0

So, if the product of all positive integers less than p is one short of dividing evenly by p, then p is prime. Otherwise, not prime.

As the book points out, this is not a practical way to determine primeness, because if p is 17, that product is fourteen digits long. However, there’s a sneaky way to make this more practical.

This formula came out of the concept of arithmetic modulus p, which is a strange sort of arithmetic that considers only the numbers 0 through p-1. Any higher or lower numbers circle around. Any number above p-1 reduces to its remainder when divided by p. It’s a bit like when a two-year old is counting: “One, two, three, four, one, two, three…”

Since this equation came out of arithmetic modulus p, we can use this property to shrink the product as we do the multiplication. While we multiply 1 times 2 times 3 times 4, etc, we can stop after each multiplication and mod p. That way the product never gets crazy high — at most (p-1)*(p-1) — because at each step it drops to something less than p.

To simplify this equation, we take out the “mod p” because in arithmetic modulus p, “mod p” is free. Also, 0 and p are the same number. (yes, that’s weird.)
We can knock a few steps off this procedure:


1*2*...*(p-1) + 1 = 0 = p

1*2*...*(p-1) = p - 1

1*2*...*(p-2) = (p-1)/(p-1) = 1

1*2*3*...*(p-2) = 1

In Haskell, we can write this as: for a list of numbers from 1 to p-2, accumulate a product, modding the product by 17 at each step; see whether the end result is 1.


let isPrime p = foldl (\acc x -> acc * x `mod` p) 1 [2..(p-2)] == 1

This says start with 1, accumulate the product-then-mod, and see whether we come out with 1.

Let’s check all the numbers up to 100 and see which ones are prime.


>filter isPrime [2..100]

[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

That’s pretty much instantaneous. Finding every prime between 2 and 10000 — there are 1229 — takes about thirty seconds on Swirlybob in GHCi. It was twenty seconds on Carolyn, my work laptop.

A future goal: use monads to time the operation precisely. I wonder whether implementing it as a recursive function and explicitly checking for 0 in the accumulator will be faster. (This happens early in the process for all non-primes except perfect squares.)