Refactoring By Any Other Name

I like philosophy.  Specifically, I like semantics and ontology.  I like thinking about naming things, and naming them distinctively.

"There are only two hard things in computer science: cache invalidation, and naming things." - Phil Karlton[1]

Normally, "naming things" in this quote refers to naming your variables and namespaces, but we can imagine it applying equally to programming concepts themselves.

Refactoring, as defined by Martin Fowler et. al.[2], is the process of improving a code base through incremental changes to the source code.

I don't like terms whose definitions require subjectivity, but I'll be a nice guy and let Fowler have the word 'refactoring'.

Today I'm going to talk about the more objective definition of refactoring: changing code without changing its behavior.  I'm even going to give it a new name, so that we have some common (and hopefully sane) vocabulary to discuss changes to code and the affects of those changes on the behavior of the code.

So what are we talking about anyway?  We're talking about changing code.  We're talking about a transformation of the source code of a file from one state to a different state.

Definition time:

    Def.

      Transformation:

        Some change or alteration to the source code.

As you can see, this is not limited to changes which result in working/compilable code.  Adding a comment is a transformation.  Fixing a bug (usually) requires one or more transformations.

Okay, so we know what 'change' means.  But there's another word in the objective definition of refactoring.  "Behavior".  Sure, yea, we all *know* what 'behavior' is.  It's what the code does!

Here is a more formal definition:

    Def.

      Behavior:

        The mapping of the state of the program at one point of computation to another point of computation.

A "point of computation" can usually be thought of as a particular line of code, if you're programming in a structured fashion. In fact, most times we will be assuming the beginning and ending lines of a function/method definition.  As a matter of convenience, I argue that this should be the default.  So in a colloquial sense, the behavior is the mapping of your program's state from before a function/method is run to after that function/method is run.

But do note that "behavior" must be discussed with respect to two points of computation.  So the definition "what the program does" is not enough information to convey 'behavior'.

So now that we have a common ground for transformations and behaviors, we can start to classify transformation by their affects on behavior.

The first will be the Behavior-Maintaining Transformation, or BMT.

    Def.

      Behavior-Maintaining Transformation (BMT):

        A change in the source code such that the behavior (mapping of program state between two points) is maintained for all execution paths between those two points.

An example of a BMT is adding a comment (unless there's something gravely wrong with your compiler/interpreter).

When people talk about refactoring, they're usually referring to BMTs.  However, this definition also applies to minification and linting.  I doubt many proponents of refactoring would consider minification an example of it.

The other classification of transformations are those that do change the behavior of the code between two points.  I'll call these Behavior-Changing Transformations, or BCTs.

    Def.

      Behavior-Changing Transformation (BCT):

        A change in the source code such that the behavior (mapping of program state between two points) is altered for any execution paths between those two points.

Note here I said any execution paths.  Even if your change changes one special case, it is a BCT.  Fixing a bug is a BCT.  A bug fix alters the current behavior, so it must be behavior-changing (otherwise you wouldn't fix the bug).

Since we live in the real world where real work is done, the situation is more hairy.  For example, you may introduce a BCT whose changes don't affect you because you never use the code in a manner in which the change is evident.  For example, take the case of a function which you change and becomes incorrect for integer values that cannot be expressed with the total matter of the universe.  This can safely be considered a BMT.  But of course, there are closer cases, such as ones where you aren't currently affected by the change, but you could write a test which exposes the new bug, but it may never be the case that you use the code that way.  Is this a BMT or a BCT? I'll leave the answer up to the reader to ponder.  But I maintain (no pun intended) that it is an important question and should be considered.

---

So who cares?  What can we do with these new-found definitions?  I'd say it's useful in the following sense.  If you know all of the transformations in your programming language which will not change code behavior, then you can freely alter your source code to a form which is more palatable.  We already know a few of these transformations.  Extract method, extract class, replace literal with variable, etc.  almost every refactoring is a BMT (one which is not a BMT is extract class, since you have a new class you can talk about elsewhere in your code).

Also, we can start to construct an Algebra of Programming (Transformations).  In trigonometry, we learned about identities, and how to show that one trigonometric expression was identical to another through a series of algebraic transformations, each of which were provably correct transformations (like multiplying by sin(x)/sin(x) or breaking tan(x) into sin(x)/cos(x)).

The only difference was that we were never allowed to make changes in math that resulted in incorrectness, but in programming we do it all the time, since things can work well enough without being "correct".

Here is an implementation of square root in Ruby through a series of easily digestible steps/transformations.  I've labelled each step as a BCT or a BMT.  It's surprising how much work you can get done with only BMTs.  Of course, BCTs have to be written eventually, otherwise your code won't actually do anything!
https://gist.github.com/nicklink483/aefec4a7fec814300ba4

[1] https://twitter.com/timbray/status/506146595650699264
[2] http://martinfowler.com/books/refactoring.html

What is a Master Programmer?

After seeing Bob Martin's talk on professionalism in computer programming, it got me thinking about programming as a craft.

We're all aware of the notion of a craft, and varying levels of proficiency within a craft.  The most intriguing level is that of the master.  The master craftsman has a level of knowledge worth revering, but what it means to be a master is different from craft to craft.

So, what does it mean to be a master programmer?  Here is an inexhaustive, slightly opinionated list of traits of a master in programming.  Feel free to add to this list, and share it around.  And if you aspire to be an expert in the field of programming, then set this list aside and reason about it and choose some of them to abide by.

Note that some of these bullet points are true of master in general, not about programming in particular.

A master programmer...

• knows several languages and language paradigms and leverages each to inform the others and his/her overall product
  • i.e. imperative vs declarative, and functional, OO, procedural, etc., and various type structures
• puts some effort into typing quickly
• knows how long it will take to complete a project, or at least has some reasonable amount of insight
• knows which of his/her beliefs are "opinions", and is versed in the tradeoffs of both sides
• (optional) takes on an apprentice
• is constantly learning and improving
• knows the limits of his/her knowledge
• can convert one problem into another
• knows that tomorrow he/she may be proved wrong on any of his/her beliefs of the craft
• knows where to get more information on almost any subject

In short, a master knows their tools, knows how to use them, and is aware of the right tool for the right job.  There are some things I'm hesitant to add to the list, but seem important, though I don't know how to word them or modify them to fit in:

• is comfortable in a full stack
• knows the O-times for various algorithms and their implementations

Do note that nowhere in either list is the master considered "professional".  This is not a mistake.  Professionalism is not a trait of the master craftsman.  Just ask this fella:

(Note that TDD isn't on the list either)  Finally, this list will not help you become good at programming.  For that list, check out this page.

Ruby is better than Assembly

Take two systems A and B.  A and B are identical excepting that B has a CPU that is twice as fast.

The benefits that a Ruby program running on B get vs running on A outweigh the benefits that an Assembly program running on B get vs running on A.  That is to say that Ruby receives a greater marginal utility in the change to a faster system than Assembly.

Since A and B are identical excepting their clock speed, writing a Ruby program for one takes the same amount off time and effort as it does for the other.  The same is true for Assembly.

Assembly takes more time and effort to code in than Ruby.

Computers get faster over time.  Therefore, Ruby will get better than Assembly will over time.

In addition, Assembly can't get much faster, but Ruby can and will.

Further, one can only do so much work, as there is only so much work to do.  Consider the following.  One spends a month writing a program that runs for 1 week.  Or they spend one week writing a program that runs for 6 months.  But the programmer's services aren't needed again for 1 year.  Surely they should opt to spend 1 week coding.

On the other hand, a certain amount of work needs to get done.  And Ruby is doing enough work in various domains.

A Better Typing Tutor

A better typing tutor

I've spent quite a bit of time doing typing tests to get better at touch typing.  2 years ago I could only type around 25-30 wpm without looking.  Today I can type around 70-80 wpm (on a good day, at least).  While a large portion of this increase is due to hard work and elbow grease, I also attribute a particular website the cause of my getting better.  This site is 10fastfingers.com.  It's a great interface for typing that is reasonably responsive, and the creator responds to feedback.  He even implemented my suggestion of being able to hide the timer (for us more anxious folk).

The main typing test gives you a random assortment of the 200 most common words in whatever language you choose.  It then gives you a minute to type out as many of that list as possible.  It's mostly lowercase and other than an occasional apostrophe, there is no punctuation.

The "advanced" test has a pool of 1000 words to randomly choose from, which contain many more occurrences of capital letters, and even some punctuation from abbreviations.

The other features of the tests are that you can only backspace in the current word, the typing area is separate from the word list, and every time you type a word, it disappears and the word in the list turn from black to either red or green depending on whether you typed it correctly.

Each of these features and their particular mixture can be different (for example, writing over the list instead of separately), but I'm not going to talk about those.

The features I am going to discuss are those of word choice/vocabulary, readability of word lists, and the computer's awareness of your skill level.

Arguably, these "features" are present in the 10fastfingers test.  For example, the word list has a readability of zero, the computer has zero awareness of your skill (in terms of using that knowledge to alter word choice), and the vocabulary is offered in 2 levels.  The vocab choice comes from there being an advanced test with 1000 word pool.

Other sites offer more readable word lists, but they suffer a different problem as a result.  Their method of offering readability comes in the form of the word list being a direct quite that a human has written somewhere.  The cost of this is maldistribution of letter frequency.  For example, in a Moby Dick quote, the letter 'w' might come up more often than on average, due to the word "whale" showing up so much.  Now, this isn't too big of a problem, but that solution forgoes another possible feature, skill awareness and word choice as a result.  If the computer knows you suck at typing "ae", it is more difficult to generate word lists if all you have to choose from are quotes.

And that brings us to the second feature I want to talk about.  The computer's awareness of your skill level.  That is, your skill at typing particular letters or letter groups.  For example, a lot of people are much more skilled in typing the letter group "the" than any other three-letter letter group because they type it so often.  Try it now!  I define "skilled" as being the amount of time in milliseconds it takes to type the letters in a letter group starting with the stroke of the first letter to the stroke of the keystroke following the last letter.  So if, say, you're typing the word "there", then the letter group "the" would be measured starting the timer at typing the "t" and stopping the timer at typing the "r".  Javascript is good at differentiating to the millisecond, and if someone were typing at 1 millisecond per character, their wpm would be around 12000, so milliseconds are good enough to measure by.

Finally there is the matter of vocabulary choice.  This is straightforward.  A vocabulary pool would grow to include words which occur less and less frequently in culture.  This is calculable several ways, from doing word occurrence analysis on books to magazines to blogs, etc.

Sentence readability is a harder problem, I grant you, but not anywhere near impossible, especially with naive solutions.  For example, one could arbitrarily generate a handful of syntaxes in a language, and, given a dictionary with sufficiently granular parts of speech, be able to generate sentences on the fly which maintain syntactic validity.  Only thing left is to remember to conjugate, though even that could be subsumed into the arbitrary syntax list.

Now, it's one thing for the computer to be aware of your skill level, but it's another thing to do anything about it.  Let's say it takes you 38 milliseconds to type the letter group "le" but it take everyone else 25 milliseconds (if we're comparing like wpm's).  In that case, the computer should opt to give you sentences in which "le" shows up more often, at least until you get better at it, or perhaps just for some temporary amount of time.  This will offer to strengthen your weakest muscle motions and even out your overall typing skill.

Mandlebrot rendering optimization method

Mandlebrot rendering optimization method

I thought of a new optimization for rendering the Mandlebrot set on a computer screen.  It involves prioritizing pixels based on whether or not their color has changed since the last iteration, and it is useful for real-time rendering.

Consider an unrendered 1,000x1,000 px canvas.  On it are 1,000,000 pixels to calculate.  The traditional naive method is to iterate over every pixel and stop only when the dwell is reached or the orbit escapes.  Such a method is computationally costly when the dwell is considerably large and there are large portions of pixels in the set (i.e. traditionally black pixels) within the current canvas.  One purpose of real-time rendering is to see just outside the set, not where the set is per se.  This new rendering method will algorithmically priorotize colored pixels to calculate in a computationally efficient manner to tend to render the bands first before spending time verifying that pixels in the set will cap out at the current dwell.

For the purposes of illustration, let us also assume that our 1000x1000 canvas is centered at the origin with horizontal and vertical ranges of [-2,2].

My optimization algorithm will start with the assumption that all pixels are in the same band, so we will only calculate one iteration of the top-left-most pixel.

This is easy to display, as the point (-2,2) escapes before the first iteration:

Next, we break down this "one" pixel into 4 sub-pixels and check to see what their color is.  As a result, you get a 2x2 Mandelbrot set render:

Next, of the pixels we just rendered, we only break them down into their subpixels if they are a different color from their parent.  So we will calculate the children of the top-right, bottom-left, and bottom-right, but ignore the top-left since it's the same color as last time.  Note that this is a naive implementation of the algorithm for illustrative purposes.  The next run gives a 4x4 render of the Mandelbrot set:

As you can see, we are already starting to see the shape of the set, and we've only calculated 13 pixels.  The next version will only select those smaller pixels whose color is different from its parent and break them down to get a 16x16 render:

As a result of selectively ignoring stagnant pixels, we can rush to render those regions which are interesting.  Now for 4 iterations this particular algorithm isn't any more impressive than if you simply rendered pixels in subchunks with no prioritizing, but this method starts to shine in areas where there are large regions of black, like a zoom-in to a mini-mandelbrot.

The details of the prioritizing process is left as an exercise to developers, but a few notes may aid the process.

1. It may be useful to only deprioritize regions for a few iterations, as seen in the example above, a naive deprioritization will lead to interesting areas being left unrendered until the end.
2. Be sure to calculate each pixel all the way to its dwell, as coupling the dwell with the current iteration in the render will result in mandelbrot set members to be focused on.

Got it working!

You can see that it very quickly finds a lot of the noisy parts of the image, and defers computation for areas which have neighboring colors that are the same.

Update:  Already got it quite a bit faster!

The big blue area is where the dwell is maxed out.

Why the 25% Bitcoin Attack is not a Problem

Recently, there was a paper which outlined a vulnerability in the Bitcoin protocol.  This paper claimed that with a share of the computing power of the network adding up to only 25%, "Selfish" Miners could take advantage of the rest of the network and take more bitcoins from the block reward than their fair share.

The paper is wrong.  They fail to take into consideration the extra amount of time it takes to generate blocks.

Let's assume for a moment that a pool has 25% of the mining power.  If this is true, then they expect to finish 25% of the blocks everyday, which yields an expected daily income of 900 BTC from block rewards.  While it is true that more or fewer blocks can be finished in one day, the assumption of the 25% computing power share renders that irrelevant.

The paper states "We assume that miners are rational; that is, they try to maximize their revenue, and may deviate from the protocol to do so."

If this is true, then a strategy which yields an expected daily income of less than 900 BTC would not be followed by a rational miner, selfish or not.

This is a simplification of Selfish Mining.  Circles are blocks and vertices are the periods of time between completed blocks.  The paper assumes that each round takes 10 minutes.  This is false.  By this false assumption, the expected daily income of a Selfish Miner is 1,008 BTC, which we can see is bigger than 900 BTC.

As said before, the paper does not take into account the extra time for blocks to finish if you're not following the protocol in this manner.

Here's what the strategy actually yields:

The 3 minutes and 20 seconds extra on the 4th block is when the 25% selfish pool is waiting for the rest of the network to catch up in order to cause a fork event.  The 6 extra minutes on the 5th block is because on average, they will force half of the network to work on their "false" fork.

While they expect to receive 25 BTC on the 4th block, they can only expect to receive 40% of the revenue from the 5th block.  Not only this, but 37.5% of the time they won't get anything because the public block finished first, causing everyone to continue to work on it.

As a result, their expected earnings per event are 21.875 BTC, and due to the extra time, we can expect ~24.27 of these events to occur per day, which leaves an expected daily income of ~530.90 BTC, which is ~369.10 BTC less than if they were honest.

Conclusion:  Miners can be expected to not follow this strategy since it yields less income.

Comment? Concerns?  Leave a comment below.

tl;dr Miners lose by following the "Selfish Mining" technique by about a 41% decrease in expected income if they control 25% of the network.

Why Ruby’s Binary Search is Meh

As of Ruby 2.0.0, the Array#bsearch and Range#bsearch instance methods have been added to do binary searching within an array or a range.

While this awesome algorithm is much welcomed, Ruby has it implemented in a slightly broken manner, (in my probably silly opinion).

First, let’s look at how it works, and by works I mean works in the way expected and produces a meaningful and reasonable result.

some_array = [ 0, 1, 4, 7, 10, 15, 99, 100 ]

Let’s try to find the first element in the array that is bigger than or equal to 72.

some_array.bsearch { |i| i >= 72 }

#=> 99

Cool!  And if the algo is running the way it should, that took 3 iterations, instead of the 7 iterations a linear search might take.

Now, this only works if the array is sorted, which is a requirement of the binary search algorithm in general.  Let’s see why:

The binary search algorithm works as fast as it does because it makes assumptions.  It assumes that the values are in order, because it uses this assumption to “throw away” portions of the collection at a time.  In our example, it did something like this:

[ 0, 1, 4, 7, 10, 15, 99, 100 ]
hmm, some_array is 8 elements large. I’m gonna check the middle first.

okay, the middle has the number 10.  well, 10 is NOT greater than or equal to 72, and since everything is in order, everything below it is useless too, so my new array is… 
[ 15, 99, 100 ]

okay, this is 3 values large, so I’ll check the middle again

99 IS larger than or equal to 72, so everything bigger than it can suck it!
New array is:

[ 15 ] 
well, the only element in this one is LESS than 72, so that 99 was the right answer!

Okay, this works nicely.  But what if I set the condition to be the last guy less than 7?

That should be 4, the third element of the array.

Unfortunately, you can’t tell it to give you “the last element which…”, but only “the first element which…”

And even if you try to use this logic, you’ll get unexpected results.

Let’s try to find the first guy less than 7.  Should be 0, right?

[ 0, 1, 4, 7, 10, 15, 99, 100 ] 
hmm, some_array is 8 elements large. I’m gonna check the middle first.

okay, the middle has the number 10.  well, 10 is NOT less than 7, and since everything is in order, everything below it is useless too, so my new array is… 
[ 15, 99, 100 ]

Wait, wha…?  It still threw away the bottom half!  That’s where the 0 was...

[ 15, 99, 100 ]

okay, this is 3 values large, so I’ll check the middle again

99 is NOT less than 7, so everything bigger than it can suck it!
New array is:

[ 15 ] 
well, the only element in this one is BIGGER 7, so there is no right answer!

I’d better tell the user the answer is nil.

Okay, that’s not quite what I wanted.  Is there a better way to do this?  Should the search ‘save’ the other half and look through it if the right hand fails?  Should there be other bsearch-type methods that work a little differently (like bsearch_max or something)?

Feel free to comment below to tell me why I'm wrong or what should be done.

Cheers!