• ## 41. pingcat

Most data on the Internet is transferred over TCP or UDP. The former works best when the transport needs to be reliable, and the latter is for when lower latency is more important than data loss or packet reordering. However, for a laugh, you can also transfer it over ICMP, aka ping.

• ## 40. Variable Length Arrays

When I learned C back in high-school, I was taught that all arrays declared on the stack had to have their size statically known at compile time. If we wanted variable sized arrays, we had to allocate them on the heap. It turns out that, as of C99, that’s no longer true.

• ## 39. mkstemp

Every time I’ve needed a temporary file, I’ve used mkstemp(3) or some variant of it. However, it wasn’t until recently that I wondered how it works, and more importantly, under what conditions it fails.

• ## 38. Faster Fibonacci

Most programmers are familiar with the naïve $$O(2^n)$$ and the memoized $$O(n)$$ algorithms for computing the nth Fibonacci number. However, with a bit of math, you can get the time down to $$O(\log_2n)$$.

• ## 37. An Optimisation Story

Premature optimisation may be the root of all evil, but it’s also dammed fun. I recently needed an OCaml library for affine transformations: essentially, I needed to multiply 3x3 matrices together.

• ## 36. Empirical Pi

You’ve finally snuck into the evil mastermind’s billiards room. You’re only one door away from his office and the Big Red Button that stops the moon laser from vaporizing the Great Barrier Reef.

• ## 35. OCaml's Compare

Programming languages often have features which are not necessary but which are a boon to working with them. For example, Haskell compilers can automagically derive pretty-printers for user-defined datatypes which is a great help when debugging. Unfortunately, things don’t always go the way the language authors intended, and such features end up being more confusing than helpful. Take, for instance, the following implementation of a doubly-linked list in OCaml.

• ## 34. Amortized Analysis

The asymptotic complexity of a loop which does at most $$N$$ constant-time operations is $$O(N)$$. $$M$$ such loops will then have $$O(M * N)$$ time complexity. But not always. If you’re careful, you can sometimes do $$M$$ loops of $$O(N)$$ in only $$O(M)$$ time.

• ## 33. Cycling Arrays

Here’s a challenge: cycle an array in-place. That is, given an array $$[x_0, x_1, \dots, x_{n-1}]$$ and a number $$m$$, you must make $$[x_m, x_{m+1}, \dots, x_{n-1}, x_0, x_1, \dots, x_{m-1}]$$ using only a constant amount of additional memory.

• ## 32. Faking Exceptions in C

I love the breaking the structure of structured programs. We have previously implemented coroutines in C using setjmp(3) and longjmp(3). We are now going to fake exceptions in C using the same functions.

• ## 31. IsString Abuse

The IsString type-class and the OverloadedStrings extension were meant to save Haskell programmers from having to type {ByteString,Text}.pack over and over again, but they can be used in more creative ways as well.

• ## 30. Fun with MI in C++

The only features originally allowed into C++ were those which had efficient implementations. This sounds great, but the results were sometimes dubious. Consider the following program which uses multiple inheritance.

• ## 29. Escape Analysis in Go

Returning a pointer to a local variable is legal in Go. As a C programmer, the following looks like an error to me, but it’s perfectly alright in Go.

• ## 28. A Stopping Problem

Let’s play the following game: you roll a four-sided die; if 1 or 2 come up, you get 1$; if 3 comes up, you lose 1$; if 4 comes up, the game ends, and you lose all of your gains; finally, you can stop the game at any point and keep your gains. How do you play so that you maximize your gains?

• ## 27. i^i is real

A funny thing happens when you take the imaginary unit $$i$$, and raise it to the power of $$i$$; it becomes real. Again, $$i^i \in \mathbb{R}$$.

• ## 26. Quines

A quine is something that, when evaluated, yields itself. More precisely, a quine is x, such that when we evaluate, interpret, or otherwise run x, we get x as the result. Quines are interesting because their existence in a language points to the language’s self-referentiality.

• ## 25. Where's my Pi?

When I powered on my new Raspberry Pi the other day, I realized I had a problem: even though we were both connected to the same WiFi network, I had no idea what its address was.

• ## 24. Time Dilation

A while ago, SMBC had a comic about whether our reality is simulated. They suggest that a way to tell would be to check if our reality were “optimised for computation”, such as if there were a minimum temperature, or a maximum speed. That got me thinking, are there other signs like that?

• ## 23. Zingr

Since Google has decided to shut down Google Reader, we should do what any self-respecting software developer would do: complain about it on Hacker News, and write a replacement that works for us. Today, we’ll be writing Zingr (“Zingr is not Google Reader”), a single-user web-based news aggregator in Python, SQLite3, Flask, Mootools, and Knockout.

• ## 22. Human Evolution

Consider a colony of bacteria living in a fresh water lake. Suppose the lake becomes more and more salty; the salt is damaging and ultimately lethal to the bacteria. What can they do? Ignoring more esoteric adaptations like bacterial conjugation, individually, they cannot do anything. As a species though, through selection of the fittest (most salt resistant, in this case), the bacteria evolve and adapt.

• ## 21. Complexity Ordering

We all know that $$O(N) < O(N^2)$$, but what’s the relation between $$O(\sqrt{N})$$ and $$O(\log_2(N))$$? Let’s determine an ordering for some common asymptotic complexities, and find the points where the smaller ones meet the larger ones.

• ## 20. Fixed Frequency Loops

Suppose we want to stress-test a server by hitting it with a fixed number of requests per second. Or maybe we want to write a game loop that runs at a fixed number of frames per second. In both cases, we want to run some code at a fixed frequency $$\nu$$. More precisely, we want a loop that calls some function, sleeps for a bit, then restarts, and overall, the function is called $$\nu$$ times per second.

• ## 19. Bank Cards in the US

As a European, I’ve had lots of problems using bank cards in the US. This wasn’t because of the bedlam that is the international banking system, but because of differences in user interfaces.

• ## 18. Sized QuickChecks

I recently ran into an issue with QuickCheck where one of my tests seemed to hang. My mistake was that I was ignoring how QuickCheck generates sized arbitrary values, and ended up creating very large structures.

• ## 17. strace

Although debugging with GDB is useful, it has the big disadvantage of focusing on the program’s internal state at a single moment in time. Often, we instead need to see how a program is interacting with its environment. In this post, we look at strace, a utility which traces system calls.

• ## 16. Debugging Field Guide

I’ve been programming for over a decade now, and, although I don’t usually use debugging tools, there are a few instances where I’ve found them to be indispensable. In this post, we go over a few debugging scenarios where print statements just don’t cut it.

• ## 15. Phantom Types

There are two ways of looking at the type-system of a language: as a set of rules which must be followed for the program to compile, and as a tool to make code more expressive. In this post, we talk about phantoms types, which is one way of doing the latter.

• ## 14. Looper

“A fixed point of a function is a point that is mapped to itself by the function”. In other words, it is $$x$$, such that $$f(x) = x$$. Fixed points are everywhere; in particular, the movie Looper is all about finding them.

• ## 13. Solving Crises

Last week, we saw how a financial crisis unfolds. In this post, we see what can be done to bring things back to normal again.

• ## 12. Crises Stories

Let’s talk about financial crises, what causes them, how they happen, and how to stop them. In this post, I tell a few made-up stories to illustrate how a crisis unfolds, and how it’s stopped; these stories are mostly modeled after the Panic of 1907; these stories are a gross simplification of what really happens and are only meant to give an intuition.

• ## 11. On Small Samples

The Law of Large Numbers says that “the average of the results of a large number of trials should be close to the expected value”. This is common knowledge, but most people are not familiar with the corollary that “the average of the results of a small number of trials may be quite far from the expected value”.

• ## 10. Permissions Puzzle

Here’s a Linux permissions puzzle for you: assume you have a file, on which the owner has no permissions, the group has read/write permissions, and everybody else has no permissions; you are the owner of the file, and a member of the file’s group; do you have permission to read or write to the file?

• ## 9. On Transfer Speeds

Let’s say we’re trying to copy a $$1$$ GiB file from one machine to another over a gigabit ethernet LAN. How long will it take? (Spoiler: it’s quite a bit more than the simple calculation says.)

• ## 8. Math Jokes

I present here the longest and shortest math jokes I know. Furthermore, I will render the long one unfunny by explaining it.

• ## 7. Java Variance Pitfalls

Last week, I found out about a non-obvious pitfall of the Java language caused by the interaction of sub-classing and arrays. In short, Java arrays are covariant, so what I thought was illegal code compiles, and causes an exception at runtime. In this post, I give a quick intro to type variance, and describe the particular issue I encountered recently.

• ## 6. Malloc Never Fails

Here’s a fun bit of trivia: malloc on Linux never fails [due to the obvious cause]. In this post, we’ll show that this indeed is the case, and explore why this happens.

• ## 4. permamake.sh

I tend to build very often when working; in this post, I describe how I went from a build every few minutes to automatic builds on every file change.

• ## 3. Loop Unrolling in sh

Here’s a puzzle for you: what does the following shell script do? (works in zsh, bash, dash, BusyBox’s sh, but not tcsh; the script must have a trailing newline)

• ## 2. Coroutines in C

There’s a pair of C functions that I feel are underused, namely setjmp(3), and longjmp(3). With them, you can fake exceptions in C, implement coroutines, and much more.

• ## 1. Random Integers

Suppose you have a fair coin, that, when thrown, lands heads half the time and tails the other half. Design a procedure that makes a uniformly distributed random integer in the inclusive range [1, n].