Category: programming

Categories
programming

Evolved Programmers Wanted. No Returns.

Here’s an interesting quote from Jeff Attwood (emphasis is mine):

“I use implicit variable typing whenever and wherever it makes my code more concise. Anything that removes redundancy from our code should be aggressively pursued — up to and including switching languages.”

It sounded like something I’d heard before. Here’s another quote from Paul Graham:

“The kind of dirtiness Arc seeks to avoid is verbose, repetitive source code. The way you avoid that is not by forbidding programmers to write it, but by making it easy to write code that’s compact.”

I’m not in anyway claiming that Jeff is lacking originality I’m suggesting that when two influential people with a large audience express the same thought … well something ought to happen right? Perhaps programming languages are going to become more expressive and concise. This certainly seems to be one of Paul’s aims at least.

Programming is changing, that’s for sure. It seems like only yesterday that Python was new and I was bending my head around it and liking being released from static types and embracing dynamic languages. Indeed if you watch this video (and I highly recommend you do) you can get a feel for how far Python itself has come in about 5 minutes.

The point though is our industry is still evolving. Natural selection finds the best parts of all those programming languages and software products and begats them into new ones. 10 years ago I believed that the future had arrived and that we would all use C++ where performance mattered and Java everywhere else. It seems that I was hopelessly naive to believe that evolution had ended. It had scarcely even begun.

I’m also eternally grateful to the innovators and early adopters that I don’t have to write much of either C++ or Java anymore. But that’s another story.

Categories
lisp programming

Know Your Idioms

A minor thought for today. Part of becoming an expert in any programming language is learning the idioms. Through experience, research and your peers you discover what makes your programming language hum. How to get the best performance and how to trade that against the best expressiveness. Since spoken language affects the way that what we think it’s reasonable to expect that programming languages affect the way we think about programming problems.

I have on a number of occassions wanted to write an expression in Lisp that will return true if all the elements are T and nil if any are not T. A sort of ‘and’ for a list. It seemed like a classic case of a ‘reduce’ or fold operation to me and so I went about doing that as a starting point.

CL-USER> (reduce #'(lambda (x y) (and x y)) '(t t t t t t t))
T

Hmm, because AND is a macro it can’t be an argument to reduce therefore I have to wrap it in a lambda. Which is ok but it removes the short-circuit feature from the AND.

So, I wasn’t terribly excited by this result but it served the purpose and life continued as normal. That was until today when I discovered the LOOP tutorial which inspired me with this trivial alternative …

CL-USER> (loop for x in '(t t t t t t) always (eq t x))
T

Yes it’s a little bit less functional but it it’s very clear what’s going on here and that was my original problem with the second reduce form. I was interested to see how the LOOP expanded too, so:

CL-USER> (macroexpand-1 '(loop for x in '(t t t t t t) always (eq t x)))
(BLOCK NIL
  (LET ((X NIL) (#:LOOP-LIST-1613 '(T T T T T T)))
    (DECLARE (TYPE LIST #:LOOP-LIST-1613))
    (SB-LOOP::LOOP-BODY NIL
                        (NIL
                         (SB-LOOP::LOOP-REALLY-DESETQ X (CAR #:LOOP-LIST-1613))
                         NIL
                         (SB-LOOP::LOOP-REALLY-DESETQ #:LOOP-LIST-1613
                                                      (CDR #:LOOP-LIST-1613)))
                        ((UNLESS (EQ T X) (RETURN-FROM NIL NIL)))
                        ((WHEN (ENDP #:LOOP-LIST-1613) (GO SB-LOOP::END-LOOP))
                         (SB-LOOP::LOOP-REALLY-DESETQ X (CAR #:LOOP-LIST-1613))
                         NIL
                         (SB-LOOP::LOOP-REALLY-DESETQ #:LOOP-LIST-1613
                                                      (CDR #:LOOP-LIST-1613)))
                        ((RETURN-FROM NIL T)))))
T
CL-USER> 

... Jeeeeezus.    No way that can be efficient surely?  So I ran both arguments with a temporary list of 1,000,000 elements all equal to true:


CL-USER> (time (reduce #'(lambda (x y) (and x y)) (loop for i below 1e6 collect t)))
Evaluation took:
  0.149 seconds of real time
  0.100006 seconds of user run time
  0.040002 seconds of system run time
  [Run times include 0.068 seconds GC run time.]
  0 calls to %EVAL
  0 page faults and
  7,999,488 bytes consed.
T
CL-USER> (time (loop for x in (loop for i below 1e6 collect t) always (eq t x)))
Evaluation took:
  0.059 seconds of real time
  0.052003 seconds of user run time
  0.0 seconds of system run time
  0 calls to %EVAL
  0 page faults and
  7,995,392 bytes consed.
T


Guess again brother.   The more I thought about it the more other solutions I could find to this problem.   For instance I could just count all the nulls and if I find one then the answer is false.


(eq 0 (count-if #'null 
           (loop for i below 1e6 collect t)))




This was marginally faster than the 'loop' on my implementation, but then I reasoned that on a list of a million items  'AND' should really retain that short-circuit ability to make it stop on the first false.   So perhaps the correct thing to do is return the first non-true argument:  


(not (find-if #'null 
          (loop for i below 1e6 collect t)))


This solution is less imperative in style and less complicated than all the other solutions.  Now that I've thought of it I can't imagine how I didn't think of it sooner.   A winner!


Lisp is such an old language that there seems literally dozens of ways to attack most problems and that really is the point.   Since I don't know what I don't know there's probably dozens more ways I could try to solve this trivial problem that only experience, research and interaction with my peers will get me.      


This is where books like the O'Reilly cookbook series should come in right?  They should have all that hard work done for me so I can stop making mistakes and start making systems.    Books, however, are not very easily searchable when they are on the shelf.   Therefore on-line resources are best for searching for optimal solutions.  So I was pleased to find that Common Lisp has an online cookbook.   However you still have to KNOW where to look in a resource like this because I might not have found the 'find-if' solution if I was stuck in a rut banging on the 'reduce' solution.    Not only that, every situation is different, 'reduce' definitely has its uses but perhaps not in this case.  


This further suggests to me that it's only your peers and your own research (i.e. trial and error) that can show you the way.  Just make sure you give yourself enough time for the research and pick your peers carefully 😉
Categories
article programming

Floating Point Flotsam

I have never been particularly clear about when to choose single or double floating point arithmetic. I think I have been operating on a sort of ‘trial-and-error’ approach for some time. It seems ludicrous that I should not, after all these years, know exactly when to chose single or double precision arithmetic. The truth is that I don’t, and it’s now time to fix that.

First, a little background. I was, for reasons that are too sad to explain, interested in how to calculate (accurately) the time of the Vernal Equinox. That is the exact time of the year (to the minute – if possible) that the sun is 90o above the earth at the equator. Anyway, I found some code which is an implementation of an astronomical algorithim designed expressly for the purpose of calculating the vernal equinox and is accurate to about 20 minutes. Which is good enough for now.

Now the next piece of background is that I was also doing this in Lisp and up until now I have let the reader interpret all the literals I enter. When I tried to do the calculation in the REPL I could get no closer than being in the same part of the day as I was expecting and with the result somewhat rounded to the nearest half day. After some head scratching it finally occurred to me that the the computation required more significant digits than I really had. It seems that the formula I was entering was being interpreted as single precision floating point numbers because if I had wanted double’s I would have suffixed my literal numbers with a ‘d’. It would seem that d could also stand for D’uh. Seems fair enough. Time to do some research then …

You see, according to the IEEE standard 754-1985 a single precision floating point number has 23 significant bits and a double has 53 significant bits. For me to answer the question of how many significant figures I can get in decimal would require me to know that the smallest decimal fraction that I can represent in binary is. This number would be 1/223 which is about .00000011920928955078125.

Now, floating point numbers are represented from a fractional part and an exponent part to give the decimal representation of the number. Therefore you can never get more accuracy than the smallest binary fraction multiplied by the exponent you have. This means that the significant figures should be something like:

log10(1/(2^23)) = -6.9

Therefore when a number has 7 significant figures you are already losing a little accuracy, the more significant figures you add the worse it will get. It was then clear that my astronomical antics were less than stellar since the first literal in the computation has 11 significant figures.

Indeed whilst I was thinking about this problem it occurred to me that if I wanted to continue using single precision I could split the fractional part from the integer part and continue this way. However, this is still inferior to a double because it would give me 7 significant figures for both parts and therefore a total of 14 significant figures. This is inferior because using my shiny new brain I can show that a double will give about 16 signficant figures. Of course I could have also concluded that double’s are better than two floats by noting that 23 bits+ 23 bits < 53 bits but that would never have been as much fun.

Type Word Size Mantissa Dec Sig. Figs.
Single 32 23 7
Double 64 53 16
Extended 96 63 19
Quad-Extended 128 113 34

You could argue that I could have saved myself 20 minutes of time by looking the answer up but then again I would never remember the answer unless I proved it to myself first. So, now my spring occurs at the same time as everyone else’s and I know why. Oh it happened already? Sheeeeiiiitttt.

Categories
programming

The Robustness Principle

It seems I’m becoming a man of principles. Last week I wrote about the principle of least surprise. This week I was reading this article about martians over at Joel it reminded me about my previous job in some non-obvious ways. And before you say it, no I didn’t work with martians or any sort of aliens for that matter. The main topic of Joel’s blog is very interesting but a side issue is the discussion of the robustness principle as defined by Jon Postel in RFC 793.

2.10. Robustness Principle

TCP implementations will follow a general principle of robustness:  
be conservative in what you do, be liberal in what you accept 
from others.

Whilst Joel is talking about HTML standards Jon is talking about TCP standards. Anyway, whilst this difference is minor the pedant in me is forced to point it out ;-).

However it’s fair to say that such a principle exists and that I’ve been living by it, without actually having a name for it, for some time. The reason I started doing it was because I inherited a large code-base for a distributed system once and I discovered that occasionally components would simply terminate, users would complain and I would have to go and invent some bullshit to explain why our system wasn’t working.

I felt like I had to invent some bullshit because I’d found that some components had statements in them like the following:

    if (such and such)
        abort();

The ‘such and such’ that caused the termination would be some condition that should not have occurred. You see, the original programmer felt the need to have all unknown conditions delivered to him by aborting the process. This is rather like demanding a criminal’s head on a plate because aborting a process under UNIX will usually cause a core dump. This memory dump file contains the contents of all the memory and registers at the time that abort() was called. With the appropriate tools this gives something to indicate what the cause of the problem might have been. This style of programming is sometimes referred to as kamikaze programming but I think seppuku programming is probably more apt.

My sin was to systematically remove these little time-bombs and attempt to handle the condition that had occurred. The problem with this, of course, is that if any of these conditions have undesirable side-effects then they can store problems up for the future which, I guarantee, will be a lot harder to find and fix.

It seems there is no right solution to this problem either. Extending Joel’s conclusion we could say that the idealist (the original code author) wanted to control the error state and deal with each case appropriately by hand. Perhaps, eventually, all these little abort() statements would get to be unused code and the system would run very smoothly. Perhaps. The pragmatist (me) would have a hard enough time of keeping the system running as it was without having components voluntarily dying all the time.

I stand by my decision to improve stability but I think I probably should have left a couple of the more esoteric abort()’s in place. I did improve the stability of the system to some extent. But my effort to restore faith in the system by making it completely stable would be somewhat thwarted for other reasons (more closely related to Joel’s post about martians). As we shall see next week …

Categories
.NET programming

The Principle of Least Surprise

I first came across the principle of least surprise a couple of years ago when someone pointed out to me that some script that I had written had violated it. Naturally defensive, and of course mildly arrogant, I asked my critic what he was talking about. He said that a command line script should return an explanation of its accepted arguments when given a –help or -h argument. He was right and I was ashamed and so I naturally did what any respectful programmer would do, I fumed quietly for a few hours and then fixed it when he wasn’t looking.

It seems then that almost any user-interface should not violate the principle of least surprise and this is common sense. When I click on a cancel button in a dialog it should not accept my input it should return to where I had come from leaving everything unchanged. This was my first violation this week and it’s a common one, a ‘Cancel’ button in a dialogue did the opposite of what I expected. This was in a popular source control tool (that I won’t name because my version is old and the bug is doubtless fixed now) and it did in fact ‘Submit’ the broken change that I was so keen to cancel. After a short bout of tourrette’s and 5 minutes of trying to figure out how to undo the change I was back on track but my confidence shaken a little.

It’s not just user-interfaces that should not violate the principle of least surprise, APIs shouldn’t violate it either. You know the sort of thing. For instance, a ‘getter()’ should be idempotent and not change any state. Languages like C++ have support for this through the ‘const’ method modifier but I can’t think of another language that I know of that enforces this in the same way.

So I was incensed when I thought I’d discovered an example of such a violation in the .NET framework. I was having trouble using the method Uri.MakeRelative(Uri uri) because I had misunderstood exactly what it did (because I didn’t RTFM) and I expected it to simply strip the routing information from the Uri and return the document path. What it actually does is a more general case and it will effectively ‘subtract’ one Uri from the other. Which is more useful when you have things like embedded Uri’s. Anyway, the depth of my sickness isn’t important, the important thing is that I realised that I could have used the principle of least surprise to save me.

As far as I can tell I haven’t ever found a .NET framework method that didn’t do as I expected, that’s partly because of the number of people who use early-release versions of .NET and iron out these problems for me. Thanks! Not only that over the years I have entered into a love-hate relationship with Microsoft. I won’t enumerate the things I hate because disk space is finite but what I really like is the way that M$ have a vast array of tools and products that seem to co-exist with very little problems. This is no small feat, it’s a triumph of quality control and standards and I applaud them.

The conclusion is then, that I should abide and uphold the principle of least surprise wherever possible. Additionally though, I can apply the principle in reverse when I trust the source of the interface to not violate the principle. Moreover if I can succeed in not violating the principle myself then people who use my and my team’s work will have more confidence in it … I can dream, can’t I?