Monday, April 6, 2009

Back from real life

After a long time of silence, I'm continuing to tell my story. There have been a lot of changes since. First and foremost, I've got a new job and I'm finally feeling to be at the right place. My work includes managing our corporate network, coding things (unfortunately in Visual Basic and Visual C#, although I have to admit that C# is quite a good imperative language) as well as helping my coworkers with computer-related issues. My company is widely known in the driving school branch.

Also I've got my hairs cut a few weeks ago, because long hairs were not compatible with my new work. I'm happy with my new hair style and with the overall situation and you can expect new blog entries more frequently again.

Thursday, February 19, 2009

Continuations for secure code

C is one of the most popular languages, especially for security-related applications including server programs, cryptography implementations and much more. Paradoxically it is also one of the most dangerous languages, because there are many spots where mistakes can be made, some of the most common being to forget to free allocated memory or to free it twice, to exceed a buffer (colloquially called a buffer overflow), to dereference a NULL pointer and more.

Some of you may have read my article about functional concepts in C, which I have written for fun. That article actually uses a non-standard extension to implement them. I have had a long thought about it and found that some of the concepts can be implemented without extensions easily and that they can be very useful in practice for real C code.

My focus was on continuations. They would immediately solve the problem of freeing memory and closing file handles properly in many situations. The idea is so simple and obvious that I just show you some example code of how it works:

int withFile(const char *fileName,
             const char *mode,
             int (*user)(FILE *))
{
  FILE *fh;
  int err;

  fh = fopen(fileName, mode);
  if (fh == NULL) return 1;

  err = user(fh);
  fclose(fh);
  return err;
}

The big advantage of this approach is that the responsibility for closing the file handle is moved from the programmer to the withFile function. In that sense withFile acts like a little run-time system (RTS) for the file handle. This also makes code much simpler. If you remember Linus Torvalds' note that goto is not necessarily evil and can make writing cleanup code much easier and more beautiful, you will find the above approach even nicer, because it gets along without goto, but does essentially the same.

Of course the above version of withFile is made for a single file handle. You can write versions of it for more than one or even arbitrarily many file handles. You can also make it allocate a working buffer for you and much more.

This style of implementing managed handles through a mini-RTS can also be applied to temporarily allocated strings and buffers, which particularly suffer from buffer overflow errors, double frees, dereferencing of NULL pointers, etc. The RTS guarantees that no code ever receives a NULL pointer or an invalid handle, it helps against double frees and forgetting to free memory, because this responsibility is moved out of mainstream code. Of course this works best, if you don't use global variables or use them sparingly.

Unfortunately C does not support closures. If it did, then you could easily pass handler functions to the user function, which obey certain rules for you like buffer boundaries. For certain kinds of managed handles you could even pass handler functions only, such that no handle is used at all. This is impossible in C, but can be very useful in languages with closures like Python or functional languages.

Monday, January 19, 2009

The problem with interpretations

I've had another one of those enlightenment experiences today, when I bought and read a very comprehensible book about quantum mechanics. What the author did right, and what most other authors do wrong: It disregarded all the partly quite bizarre interpretations of the theory. If you forget about all the motivations and interpretations of a theory, what remains? Equations. That's it.

For example, I've learned that a quantum state is simply a unit vector V. Things such as superpositions or in more colloquial terms being in multiple states simultaneously exist only in interpretations. The state vector is a fully determined value.

Then where do superpositions come from? It's simple. They are no fundamental feature of a quantum state, but a feature of the measuring process. Measurement is always done in a certain base described by a number of base vectors. The outcome of the measurement of V depends on the description of V as a linear combination of these base vectors. The square of the absolute value of the coefficient of a particular base vector X is the probability of the outcome being X. That's it. Quantum states are fully determined and not superposed. Superposition is a measurement effect, because the measurement destroys information.

Example: If you run a vertically polarized photon through a polarization filter, which lets through vertically and horizontally polarized photons, then the outcome is a vertically polarized photon. If you rotate your filter by 45°, the outcome is completely random. That's not because the photon had a superposed polarization, but because the new base of the measurement has changed in a way, which makes the outcome "vertical" impossible. In other words, in the former experiment, there was no superposition, in the latter there was, even though the initial configuration is exactly the same with the only difference being the justification of the filter. So superposition doesn't exist. It can be interpreted as a measurement effect.

I had that same experience with other things as well, for example group theory or monads. For some reason, people seem to prefer to depict abstract or unimaginable things and concepts as something complicated or mysterious. I think, this is related to our fascination for the incomprehensible and the satisfaction of amazing other people. Who isn't amazed by the imagination that there may be more than the three (or four) dimensions you can see, or that a single thing can be at multiple locations at the same time, let alone relativistic effects? However, if you described these things as what they really are, you wouldn't amaze anyone. Ask a physicist about quantum physics, you'll get a straight, but disappointingly boring answer.

Sunday, January 11, 2009

A reinterpretation of Python lists

I'm not a Python programmer and I only know the basics of the language, but what I never liked about it is its list handling. In general, just like C, Python is quite a boring language from a language-theoretic standpoint — a language to get the job done.

However, here is a supplemental piece of code implementing an alternative idea of lists for all the functional programmers of you, who are forced to use Python for whatever reason. Have fun, but beware: Your coworkers may not understand your code. ;)

Side note: A very annoying fact for me is that Python doesn't support currying, but I found a somewhat ugly way to emulate it. Refer to the fix and range functions to see how it works.

Update (Sun, 2009-02-08): I have refined the code and removed the fold function, since it's really useless. Lists are higher order functions themselves, and the fold function was just a wrapper around them. I have also solved the currying problem, thanks to verte from #python on Freenode.

Monday, January 5, 2009

The latest in low quality

With the advent of the internet and sophisticated digital audio and video codecs, classic hard mediums became less and less popular. People prefer to listen to their music on their PCs. However, it was just a few years ago, when people would insist on having high quality encodings of their favorite music or movies. I observed an interesting change in this trend.

Web services like streaming music or video are of rather low quality, compared to their non-networked counterparts. But somehow more and more people tend to happily accept that. Instead of getting a high quality copy of their favorite song, they just listen to it on YouTube, silently acquiescing the horrible quality.

I think, this comes partly from laziness or unawareness, but often even simply from ignorance. People abandon quality in favor of ease of use and less management overhead. I have even seen people download music clips from YouTube and extract the MP3 track of them. Honestly, I've done this myself a few times, when I was too impatient to get a song through other means.

The current state of things worries me, but at least I will do my part and go back to good old high quality files. Unfortunately many things aren't as easy to find in the music store as they are on YouTube, so I'm afraid, I might be stuck with it for now.

Friday, December 26, 2008

Understanding Haskell monads

I'm proud to announce that I have completed my first monads tutorial for Haskell programmers. Although I'm not completely happy with a few parts (I'm a virgo after all), I'm releasing it now. I hope it will be helpful to the community.

Tuesday, December 9, 2008

Prime de illuminati

Recently, when someone with the nickname Pr1me came into one of the German IRC channels I'm in, I pointed out that 1 is not a prime number. He should pick the nickname Pr11me instead.

Of course, I was just joking, but out of curiousity, I looked for larger prime numbers consisting only of decimal 1s, and I found the following numbers to be prime:

  • 11 (2 digits)
  • 1111111111111111111 (19 digits)
  • 11111111111111111111111 (23 digits)

I looked further, again just out of curiosity, to find the following interesting numbers, which are not prime:

  • 11111111111111111111111111111111111111 (38 digits)
  • 111111111111111111111111111111111111111 (39 digits)
  • 1111111111111111111111111111111111111111111111 (46 digits)

The first number is interesting, because it is 38 digits long and contains the 19 (= 38/2) digits number 1111111111111111111 as a prime factor. This is interesting in that it's a highly unlikely case (considering the random nature of prime numbers), that a prime factor consisting only of repetitions of a single digit is found in just another number of that form, and that the prime factor has exactly half the digits of the composite number.

The second number has the curious-looking prime factor 900900900900990990990991.

Finally the third number has 46 digits and is a product including the 23 digits prime factor 11111111111111111111111. The probability for that to happen for a 38 digits number is already very low. It is even orders of magnitude lower for a 46 digits number.

I'm not a fan of conspiracy theories, but this is surely curious. The 46 digits number is, by the way, the largest number of that form I have found. You can come up with many ways to relate that number to the (prime) number 23, some of which are very interesting.

Update: Robert Smith (quadricode at gmail com) took this further and observed the following curiosity: In any number base he tested, a number consisting entirely of repetitions of the digit 1 would only be prime, if the number of digits is itself prime. This may be a generalization of Mersenne primes. Let's see if we can prove this.