Friday, November 8, 2013

Sad Hill Cemetery revisited

I recently re-watched the classic spaghetti western "The Good, The Bad, and The Ugly."

The film ends in a classic scene, where our protagonist Blondie ("The Good") is part of a Mexican stand-off at Sad Hill Cemetery versus the antagonists Tuco ("The Ugly") and Angel-Eyes ("The Bad").



In the film, Blondie has an ace up his sleeve, so he does not have to consider the rules of this problem, which is a bit unfortunate as they are pretty interesting. The trivial case where each shooter has 100% accuracy, it is clearly never a good idea to shoot first -- whomever you do not shoot will shoot you. Shooting first simply never is a good idea in this scenario. Good thing Blondie cheated, in other words.

However, when accuracy is less than perfect, things get more complex. Instead of crunching the numbers manually, I decided to let machines do my work for me, and wrote a python script to simulate the stand-off.

Assuming Blondie fires first, these are the results, which offered a few surprises
Simulation of the Sad Hill Cemetary scenario, 1000 samples/accuracy level

As expected, the high-accuracy scenario means shooting first is a guaranteed way of losing, but if the involved parties are poor marksmen, the rules change. It turns out, if the accuracy of all involved shooters is less than 50%, shooting first is in fact the optimal strategy.

But there's a third domain. If all involved are imperial stormtroopers, with accuracy approaching 0%, it won't matter who fires first; all gunslingers have approximately the same likelihood of surviving, which seems sensible, as the battle will get more drawn out who performed the opening move will play an increasingly smaller role.

The sources used for the simulation are attached below:

Returning null is the devil, never do it

This, first of all, goes mainly for object oriented languages. In C, you have no option but to return null.

I'm on a bit of a personal crusade against functions that "return null;" Allow me to soapbox a bit.

So many perfectly avoidable bugs arise from this practice. Sure, the exception will probably be called somewhere higher up in the code, and things probably won't be that bad. Unless someone has written a function like say

If your function can fail, and you expect the caller to deal with it, you should throw a checked exception. That way, the caller will deal with it. And if he doesn't, he's explicitly ignored an exception, and he's a moron. If you fail and don't think your caller will be able to deal with it, throw an unchecked exception on the spot. Returning null and having the caller explode at some unspecified time later isn't cool, not one bit. You should fail fast, and make as loud a bang a possible.

If your function can fail, and you communicate this by returning null, the caller may not null check. It's an easy mistake to make. Oftentimes, you need to thoroughly investigate the function being called before even finding how it returns null -- it may happen in something it calls.

Of course, sometimes null isn't an error, but an absence of data. In that case, always return a safe object. Like an empty list, an empty string, and so on. If someone doesn't have a name set, his name isn't null, it is "". If you ask me how many green skinned people live in my neighborhood, I don't say null, I give you an empty list.

Which is why I propose the following strategy to seeing "return null;". Get mad. This function lied to you. It betrayed you. You trusted it, and it rewarded you by stabbing you in the back. It told you it would bring you an object, but it gave you nothing. That bastard! You should be livid at this.

Null-checking is a symptom of bad code, and is a bad solution to the problem at that. The problem at heat is that null checking is very easy to overlook. You oftentimes have to have the code crash before you realize a return value could be null. If you are relying on trial-and-error to make your code stable, you are doing something terribly wrong. Furthermore, a function littered with null checks is significantly more hard to read and maintain, not to mention, if it has 17 null checks already, you almost certainly won't know if it needs another one by looking at it. The very fact that null checks are easily overlooked is reason enough to avoid returning null -- who knows when and how that will backfire. You don't want to be the next Knight Capital. KC's problems weren't down to a NPE, but to a slew of other bad practices, but in a wider sense it's all the same.

The fix to this problem isn't to add null checks, but to re-write the poorly designed function(s). If that isn't possible because it's 3rd party or legacy code, call it indirectly through a facade that guarantees proper error handling.

Tuesday, November 5, 2013

Leveraging task-tags in Eclipse

This is one of my favorite tricks you can use to improve Eclipse. It provides a very nice way of managing your task tags in a large multi-author codebase, where TODOs typically count in the hundreds, if not thousands, and in doing so making the Task View-feature into a very powerful tool for tracking your own development.

First, set up templates for your tags, including a ${user} and ${date} reference.

First, set up templates for your task tags, on the format
// TODO (${user} ${date}) - ${cursor} 
// FIXME (${user} ${date}) - ${cursor}

You can easily insert these by typing todo and hitting <ctrl><space>. This is useful in that it is possible to keep track of who is responsible for the task tag, but the real magic comes in the next step.

Open the Tasks view, click the little downward-pointing triangle-button in its upper right corner, and select "Configure Contents". You want a new filter based on your user name appearing in the contents of the task tag.

Configuration example

When this is all set-up, Eclipse will track all of your task-tags. 

Instant task-tracking

Making a habit of using these improved tags provides an immensely powerful way of getting around the code, not only does it allow you to keep track of your margin-scribbles in the code, the tags also serve as task-oriented bookmarks. If you just plop one down when a potential issue springs to mind, you will remember it later.

I'm leaning toward preferring the use of task tags to the actual bookmark feature in eclipse, which I find much clunkier. The feature has also largely superseded the practice of attaching post-its to my screen.

As a final note, you can make Eclipse recognize additional tags in the settings: Java>Compiler>Task Tags. For example, I also use "TEST" to mark code that needs additional unit tests, and "STUB" to mark unwritten functions (this is purely as a bookmark).

File Transfer Over Soundcard: Director's Cut

I've changed templates on this blog, a process which horribly mangled some of my older posts. This was necessary partially because the mobile device support of my old theme was awful.

I can't actually update my old posts, because they're in some form of you-have-an-ancient-blogger-account compatibility mode, which inserts random line-breaks everywhere. So I'm having to re-compose them entirely. This takes time, so I'm only going to do it for my most popular posts.

This one combines my two posts on how to build a simple software modem from back in 2009. The full sources are available on a github repo.

I'll soon be emptying the original articles, and replacing them with a link to this post. I'll still keep them up, because there is to this date occasionally comments going on in them.

File transfer over soundcard: Part 1
File transfer over soundcard: Part II

Part 1

Before I even start, a word of warning: Never try these programs with your headphones on. THEY MAKE LOUD NOISES! It is possible to configure these programs to make noises way louder than you ever imagined your headphones could make. You can damage your hearing when playing with audio programming. Tinnitus isn't fun.

This will be you if you don't take my warning seriously:



Background and problem

I have an old laptop laying about. A while back, I was in a bit of trouble getting it to work. It's so old that several parts of it has shut down. The USB system is fried, and it can't read modern burned DVD:s. I needed to move software to it to get the network up and running again. The only peripheral that was working (besides the keyboard and the screen) was the sound card. It was running an old version of Slackware.

Ah, I thought, and wrote a program that encoded data in sound. When I did it back then I used a bad algorithm. It was very noise sensitive and tried to do too much at the same time. As of then, I've improved (and simplified) the concept to using a sort of pulse width modulation (an idea I got when I read about the ZX Spectrum Tape Loader.)

The basic protocol is trivial:

  • For every character:
    • For every bit:
      • Send a short pulse if the bit is 1
      • Send a long pulse if the bit is 0
      • Send a silence
    • Send a very long pulse (four times as long as the shortest pulse)
  • Send a silence


This is nice and not very error prone. The end-of-byte signal means that errors don't taint their neighbors. 


The crux isn't the signal generation (which is laughably trivial), it is the analysis on the receiving end; or rather dealing with the noise in the signal. The naive implementation would be to sum the square of the signal amplitude over time periods--the presence of a sine wave would converge towards some value and a silent signal would converge towards 0. In a noisy signal, it almost always converges towards something non-zero, so no such luck.

So, the second approach would be to use a Fourier transform, to select the part of the spectrum where our signal resides (400 Hz is what I chose).

A simple implementation of such a function looks like this:


Where x_in is a series of numbers between -1 and 1, and n is the modified frequency (which is to say: length * frequency / rate). This function would give you a number corresponding to how much of a given frequency is in a sample. But you can do one better: Harmonics. Almost every loudspeaker will produce some level of harmonics even though the signal broadcasted is a plain sine wave with no harmonics.

So, to check if our signal is in a given segment, the following code can be used:

To check if the signal is present in a given signal, you must compare this against some form of threshold. What's a good threshold varies with noise. A bad threshold value may either cause the program to interpret random noise as meaningful data, or reject good data as random noise.


The protocol described above can be realized with the following code:


This does work. It's not just some crazy pipe dream. Following is all the code you need for transferring files from two computers using their soundcards.

Garbled transfers like this may soon arrive through a soundcard near you. 




Utility programs

Before I get deeper into to the main program, I'm going to contribute some utility programs. record and playback. They are both wrappers for OSS, and reads and digests data from the soundcard; or writes digested data to the soundcard at given sample rates. They deal in signed char arrays only, and may convert them for the soundcard. Exactly what they do and how they work is a bit off topic, so I'll just post the code listings.

playback.c
record.c

The broadcasting end
As previously discussed, the broadcasting part of the program is pretty simple. The only real gotcha is the sample rate factor in the frequency. Since we're generating a signal with N bytes per second, we must decrease our frequencies by a factor 1/N. Beyond that, it's really quite trivial.

generate.c

The math parts
Almost there now. We just need some fourier transforms and things of such nature. The analysis end of the program can also make a XPM file of the frequency spectrum of the input, which is why you see a bunch of XPM code.

fourier.c
fourier.h

Finally... the receiving end

Most of what this one does has already been discussed. The threshold is hard-coded. You may want to change it or whatever.

analyze.c

... one file to compile them all, and into objects link them

Makefile

To compile, you just run
> make

Using the programs

Before I get to actually using the programs, I repeat my warning: Never try these programs with your headphones on. THEY MAKE LOUD NOISES! It is possible to configure these programs to make noises way louder than you ever imagined your headphones could make. You can damage your hearing when playing with audio programming. Tinnitus isn't fun.

Not there yet. It's quite an elaborate matter to use all these programs. First you'll want to generate your raw sound data. Let's transfer /etc/fstab (don't do this as root! Something might go horribly wrong!)

First, attach the microphone on the receiving end to the speakers on the transmitting end. Use duct tape or whatever. I had an old hands free headset that I wrapped so that the microphone was held in place by the earpiece.


Experimental set-up


On the transmitting computer, run the following command:
> ./generate -b 25 -r 48000 -o out.data /etc/fstab

Enter, but do not start the following on the transmitting computer:
> ./playback -r 48000 < out.data # don't press enter yet!

Now, on the receiving computer, run the following command:
> ./record -r 48000 -o out.recdata
Note that out.recdata will grow very fast. In this case, 48000 bytes/second.

Run the command pre-typed in the transmitting computer's terminal. Be very quitet, and listen to the noise coming from of the speaker. This may take quite some time. Practice your Zen. Find enlightenment. When the noise stops, press Ctrl+C on the receiving computer.

Run the following command on the receiving computer:
> ./analyze -b 25 out.recdata

Watch a semi-garbled /etc/fstab be printed across your screen. The -b switch is to be taken with a grain of salt. It is proportional to how fast the transfer is. It must (obviously) be the same on the receiving and the transmitting end. I've gotten it to work at -b 50 -r 48000. Sample rate (-r) increases the processing time, but it also allows faster transfers. There are a few fixed possible sample rates, 8000 always works, others that are supported by most soundcards are 11025,16000,22050,24000,32000,44100 and 48000.

So, in summary: -b determines how fast the transfer is, and the maximum possible transfer speed is limited by the sampling rate.

If it doesn't work, try playing what you recorded with playback. If you can hear and distinguish the beeps, then so should the computer be able to. If record or playback fails, chances are you don't have permissions to access /dev/dsp. If all you get is character salad, fiddle with threshold in analyze.c.

Part 2

I've played around further with the file transfer over sound card idea, and developed a more advanced method that uses a technique called Phase Shift Keying. Similar techniques are used in wireless network connections.

Instead of coding data in the amplitude or frequency of the carrier signal, phase shift keying (as the name indicates) encodes it in the phase. It is significantly faster, partially because it doesn't waste as much time with silences, but also because it's more reliant.

Flawless transmission

I must admit it's a good thing I wasn't drinking coffee when tinkering with this technique, because it's very likely I would have blown coffee through my nose and onto the keyboard when I first saw transfer rates over around 200 baud, with no random garbling. I'm sure it's possible to go higher with better equipment than my cheaper-than-dirt headsets that came with my webcams.

How it works

The mathematics of the method is as following, if the signal is expressed as

\[S(t) = A_0 \sin(\omega t + \phi)\]

Then the Fourier transform of S would give you

\[F_\omega(S) = A_0 e^{i\phi}\]

Normally, one would simply discard the phase factor by taking the norm of the frequency coefficient, but for this we're going to make use of it. You can't just yank the phase out of the expression as it is though (phase is always relative to something). But! You can compare this phase with the phase of the last sample you got (this is called differential phase-shift keying, by the way).

So, I propose the following scheme:
\(\Delta\phi\) 
Function
0 Still the same sample as last time
\(\frac{\pi}{2}\)  Next bit is 1
\(\pi\) Next bit is 0
\(\frac{3\pi}{2}\) New byte

This has several nice features. You can jump into the signal almost anywhere and at most one byte will be garbled. Furthermore, everything has an uniform length, so bit rate doesn't depend on how many ones and zeros is in the byte.

Modifying the fourier code from the last blog post on sonic file transfers, the following function will allow you to make use of the phase:



So how do we figure out the phase difference? Let φ be the phase of the current sample, and ψ be the phase of the previous sample.

\[e^{i\phi}e^{-i\psi} = e^{i(\phi - \psi)} = \cos(\phi - \psi) + i sin(\phi - \psi)\]

The real term will dominate if φ - ψ ~ nπ , and the imaginary term will dominate if φ - ψ ~ (n+1)π/2 and their sign will further tell you if n is odd or even.

The demodulation algorithm is fairly short:



For several reasons, it's a good idea to use a pretty high carrier frequency for this method. At some point, your speaker or microphone will not be able to process the information, so you'll want to stay under that, but a high frequency will result in less perturbation of the signal since fairly few objects have eigenfrequencies in the 5 kHz range or higher, and even oscillation at harmonic frequencies drops off pretty significantly at such frequencies.

Sources

The complete source code for the program:

generate_psk.c
analyze_psk.c

You may have grabbed these the last time, but they are slightly altered now, so get them again:

fourier.h
fourier.c

You also need the playback and record programs I posted in the previous post. They haven't changed though.

playback.c
record.c


Using

Same old warning: Never try these programs with your headphones on. THEY MAKE LOUD NOISES! It is possible to configure these programs to make noises way louder than you ever imagined your headphones could make. You can damage your hearing when playing with audio programming. Tinnitus isn't fun.

To transfer a file (let's transfer /etc/fstab again), put the microphone next to the speaker, pre-type the following on the transmitting computer (without running it):

>./generate_psk -r 48000 -c 8000 -b 100 /etc/fstab | ./playback -r 48000

Type the following on the receiving computer:

>./record -r 48000 > mydata

Press enter on the transmitting computer. Be quiet (this should be fairly quick. Maybe 30 seconds?) When the high pitched noise stops, press Ctrl+C on the receiving computer's terminal.

Running
./analyze_psk -r 48000 -c 8000 -b 100 mydata
on the receiving computer should retreive the message.

The parameters are
-r : Sample rate -- carrier frequency and signal quality
-c : Carrier frequency -- limits baud rate and signal quality
-b : Baud rate -- determines how fast the transfer is

What works and doesn't with the sampling rates and frequencies is a bit tricky. It all boils down to Nyquist-Shannon. That theorem is all innocent looking, until you make it mad. Then it turns green and grows three times it's size and goes on a furious rampage through your hopes and dreams.

Anyways, have fun experimenting with this technique.

Sunday, November 3, 2013

Let's design better exceptions

I've always been sort of mixed towards exceptions in object oriented languages. When done right, they are pretty neat, but in other cases, they are a source of endless frustration.  I've been thinking about why this is, and how we can change them for the better.

The sort of exception-handling code I have nightmares about looks something along the lines of


This sort of code is very unpleasant to work with. As a caller, I am forced to deal with more exceptions than I want to.  The second and third exceptions should have arguably been run-time from the get-go. Now I either have to handle them poorly (re-throw, ignore), or infest my code with even more checked exceptions that just push dealing with them higher up the call hierarchy. That may be okay within the same module, but once your aggregate starts publicly hemorrhaging unchecked exceptions from its components, something has gone wrong. It rhymes especially bad with modern code that is going to be glued together with dependency injection -- it just doesn't work to leak implementation details like that anymore.

There is a deeper issue afoot here, what really should be gnawing at your design senses is that this pattern simply isn't kosher object-oriented design. I shouldn't be inspecting the run-time type info of an object, and then determining behavior based on this! This is all sorts of wrong!  We are encoding what reasonably speaking should be data into the object type, so that the only way to extract the data is a bunch of glorified instanceof clauses.

If I were to speculate why exceptions look the way they do, I'd say it's because they were designed by the same people who wrote the standard library, rather than those who spend their days writing business logic. Which is a phenomenon you see every once in a while.  C++ does the same thing with operator overloading -- a rather large language feature that really only shines in designing custom numerical types and collections. The same way, Java exception handling makes perfect sense if you're writing an I/O or threading library, but they are wholly unsuitable for application development.

A few observations to act as a base for a new exception paradigm

  1. The caller shouldn't be forced to handle errors against their will -- programmers are lazy creatures, and this will lead to bad code.
  2. The caller shouldn't have to use instanceof to glean information about the error.
    1. The caller may want to know the type of error.
    2. The caller may want to know the source of the error.
    3. The caller may want to know if the error is recoverable.
  3. Our exception-system must be as extendable as regular exceptions. Lists of magic integers or strings are unacceptable as type-information.
  4. If the callee throws an exception, it does not know how the caller wants to handle it (i.e. you can't have a fixProblem() method in the exception).
Applying these observations, I've come up with an ansatz that looks like this:


It's rather difficult to see how this behaves looking at the code itself, so let's apply it to the original scenario.

The difference may appear subtle from the original examples, but look what really happened here: First of all, the callee does no longer need to let us know every way it can fail. By declaring it throws a BetterExceptionIf, it tells us it can fail and we need to know about it, presumably because it thinks we can recover. I'm a bit undecided whether I consider an unchecked exception may be more appropriate here.

When it does fail (either directly, or some in some unhandled sub-component exception), we are not forced to to concern ourselves with exactly which manner it failed in order to handle it responsibly. The caller can glean as much (or as little) information as he requires in order to deal with the problem.

Saturday, November 2, 2013

The software developer's fallacy

Wow. Very long time to go without updates.

I'd like to rant a bit about how a lot of software developers are being sort of stupid in how they go about their profession.  This may upset some people, that is fine.  Please leave an enraged comment below.

Let's assume that deadlines are tight, because that's just the industry and deadlines are always tight.  You need to get a lot of work done in a short time.  Do you opt to:
  1. Working overtime, stressing and drinking bucket-loads of coffee
  2. Cuting corners and skimping on best practices
  3. Cutting unit tests / foregoing code maintenance
  4. Some/all of the above
  5. Proceeding at a normal pace
A vast number of software developers will choose option d.  I will argue that this option is only correct if your job is letter-entry.  That is, what is bottle-necking your productivity is how many keys you can press in a given time-span, and the time you spend debugging and analyzing problems is insignificant compared to the time you spend mindlessly typing code.

Fig A. A hypothetical work-distribution where entering code is the most time-consuming activity.

Let me tell you, this is very foreign to how I work.  Maybe COBOL programmers had this type of work-distribution?  While I may hammer away at the keyboard quite a lot, it isn't my main activity.  My main activity is problem solving. Pulling numbers out of my ass, I'll argue that the distribution in figure B is a lot more accurate.

Fig B. A majority of time is spent problem-solving. Entering code is big, but not the major activity.

Let's look back at the approach programmers take to meet deadlines. Options b and c--skimping on good practices--emphasizes a reduction in key-presses, at a cost of code quality.  It increases the time spent debugging the code, if not this sprint, then certainly the next one.  Having poor test coverage means debugging takes even longer time, and re-factoring is nigh on impossible, so even the mindless code-entry part will eventually start to take longer than it necessarily has to!

If code-entry is indeed a major bottleneck, there are better ways of changing that. Setting up some eclipse templates for boilerplate goes a very long way.

Cutting corners seems like a poor strategy, so what's left? Overtime. If it is an occasional occurrence, I'm all for it.  But chronic overtime is counter-productive. Innumerable studies have demonstrated this[1]. To make matters worse, most of the developer's time is spent thinking, it should be fairly self-explanatory that this is not the type of work that benefits from an exhausted practitioner.  Among the most time-consuming activity in software development is fixing bugs, and developer exhaustion is a significant cause of these bugs.  Therefore, increasing exhaustion increases the time it takes to implement a given feature. You can actually end up producing less than you would, were you working normal hours!

My thesis is this: It is flat out counter-productive to rush software development.  You are spending more time producing less, at lower quality, than if you simply play by the book and let the development take its time.

Other craftsmen have had this figured out for ages. It's time we did too.

Measure twice, cut once.


Correcting mistakes is among the most time-consuming aspects of software development, which is why preemptively avoiding them is arguably the best way of meeting the deadline, even if it feels like you are "wasting time". 

The bottom line is that you have ample time to type almost any code into the editor this sprint (along with ample unit tests).  What will make or break the deadline is how much time you spend debugging what you entered.


[1] http://cmdept.unl.edu/drb/Reading/overtime2.htm