Recently in Programming Category

I’ve just read yet another article showing how to calculate elements of the Fibonacci sequence in some functional language. I’ll give examples in Scala, though I’m not doing anything very clever linguistically, so they shouldn’t be hard for anyone. Of course, it showed the hopelessly inefficient dual recursion

def terrible_fib(n: BigInt): BigInt =
  if (n < 0) sys.error("not defined for -ve n")
  else if (n == 0) 0
  else if (n == 1) 1
  else terrible_fib(n - 1) + terrible_fib(n - 2)

and a tail-recursive version

def tail_fib0(n: BigInt, a: BigInt, b: BigInt): BigInt =
  if (n == 0) a
  else tail_fib0(n - 1, a + b, a)
def tail_fib(n: BigInt): BigInt =
  if (n < 0) sys.error("not defined for -ve n")
  else tail_fib0(n, 0, 1)

There was also an explicitly iterative version, which isn’t interestingly different from the tail-recursive version, so I shan’t bother showing it. Unfortunately, the tail-recursive version is still rather slow. On my (very old) laptop, it takes nearly a minute to calculate tail_fib(1000000). We can do much better.

The other day, a colleague asked me how to multiplex lines from a number of asynchronous sources from a Unix shell script. Here’s what I came up with.

#! /bin/sh

set -e
for i; do
  while read line; do echo "$i: $line"; done <"$i"&
done | cat
wait

Ward’s wiki explains that a ‘three-star programmer’ is ‘someone whose programs contain three consecutive dereference stars’. The implication, I believe, is that such code is too clever for its own good. I’m not sure whether three stars in a declarator count, but I’m hoping so.

This is a subject which has been on my mind for a while. It turns out to be much simpler than one might expect.

Firstly, let’s be clear about what the problem actually is. We want to be able to find out whether two objects are structurally equivalent. To have a clear idea of what this means, we’ll divide objects into atomic values and containers. An atomic value is just a thing with no interesting (for our purposes) internal structure. We can suppose that we’re given a predicate for determining whether two atomic objects are equal, and we’ll say that atomic objects are structurally equivalent if and only if they’re equal. A container, on the other hand, contains pointers to other objects. We’ll need to understand the structure of containers. In abstract, we can think of a container as being a partial function from atomic values to objects. Two containers are then structurally equivalent if and only if their domains are equal (so they have the same ‘shape’) and they map equal keys to structurally equivalent objects.

This is a recursive definition. If you translate it directly into code then you end up with a function which doesn’t always work. In particular, it won’t work on circular structures (e.g., $A$ points to itself).

Over the weekend I wrote a surprisingly simple function which solves this problem. I’ll present it in bits. It’s in Common Lisp, but hopefully that won’t be too scary.

Continuing my attempts to recycle articles written elsewhere… This stuff was originally from comp.lang.python. Its objective is to define the terms ‘pass-by-value’ and ‘pass-by-reference’ in ways which are:

• reasonably clear,
• language-independent, and
• consistent with widely-held expectations.

With a bit of luck and a following wind, the framework here can be extended to cover other weirder argument passing mechanisms, e.g., Algol’s pass-by-name.

If anything here is particularly controversial then I’ve failed.

Executive summary

Here’s the soundbite version.

• Pass by value: The callee’s parameters are new variables, initialized as if by assignment from the values of the caller’s argument expressions.

  So, we ought to be able to replace

  function mumble(a, b, c) { stuff in terms of a, b, and c }
  ...
  mumble(1 + 2, xyz, whatever)
  

  with

  ...
  fresh_a = 1 + 2
  fresh_b = xyz
  fresh_c = whatever
  stuff in terms of fresh_a, fresh_b and fresh_c
  

  with no observable difference.

• Pass by reference: The callee’s parameters are merely new names for the caller’s argument variables — to the extent that this makes sense.

  There’s a caveat there for argument expressions which don’t correspond directly to variables. Anyway, the idea is that you should be able to replace

  function mumble(a, b) { stuff in terms of a and b)
  ...
  mumble(xyz, whatever)
  

  by

  ...
  stuff in terms of xyz and whatever
  

  without observable difference.

Almost every Unix programmer’s done it:

int kid;

if ((kid = fork()) < 0) fail();
if (!kid) {
  if (dup2(x, 0) < 0 ||
      dup2(y, 1) < 0 ||
      dup2(z, 2) < 0)
    fail();
  close(p); close(q); close(r);
  execlp("/bin/foo", "foo", /* args */, (char *)0);
  fail();
}
/* and so on... */

And it’s wrong. What if y is zero? You’ve clobbered it too early!

This is fairly easy to deal with if you know where you got these file descriptors from. If you just got them by calling pipe(2), then you’ll know that they’re in ascending order, so you can dup2(2) them in the right order and all will be well. If you’re writing a library function which is meant to do fancy I/O redirection then you’ve got a bigger problem.

I present a glorious new solution to the problem. The mdup(3) function does multiple dup operations in one go. You give it a table explaining which file descriptors you want where, and it makes the mappings happen. It will work correctly even if you ask it to map 0 to 1, 1 to 2, 2 to 3 and 3 to 0. If it fails for some reason (probably you hit the per-process fd limit) it leaves enough information lying around that you can work out what state the world is in and clean up properly.

I won’t claim that mdup always does its job in the most efficient way possible — whatever that might mean anyway (probably the smallest number of calls to dup2(2), or runtime). But it is at least correct. And even so, it’s not a completely simple algorithm.

What? You want real code? OK: from my Git repository.

I’m going to try a new approach. Since I’m writing articles at the rate of three and a half every blue moon, I thought I’d recycle material from other places. Here’s one distilled from IRC.

Apparently I’ve acquired a reputation as someone who doesn’t really like the whole object oriented thing. While I never really liked the Kool-Aid, it certainly has its place and it’s often a good way of thinking about a problem. It doesn’t solve everything: nothing does.

Furthermore, it seems that some people have developed the idea that I’m against multiple inheritance, just because I’m down on C++. I usually get thumped by otherwise respectable object-oriented types when I explain that I think multiplie inheritance is actually a pretty neat idea. Oddly enough, they usually think I’m crazy because they’re thinking of C++’s version of multiple inheritance.

C++ is probably the biggest player which actually provides multiple inheritance: later related languages, like Java and C#, have (largely — more on this later) ditched multiple inheritance. And I think the reason is because C++ does such a bad job of it, providing almost none of the features which make it work properly.

The standard technique for writing files safely on Unix are presumably well known: you write to a temporary file alongside your target and then, when you’re finished, rename the temporary file into place. Writing code to do this is pretty straightforward, but it’s also rather dull and exactly the sort of thing which ought to be automated.

Time is annoyingly complicated. The mess of different civil definitions makes dealing with time in computers unreasonably difficult. And creating useful, portable interfaces is much harder than one would hope.