Archive for May, 2008

« Older Entries

Compile-time symbolic computations

Saturday, May 31st, 2008

A compiler ought to be able to perform compuations at compile time. Unlike the generated code, these computations don't have to be blazingly fast (since they only happen at compile time), and don't have to conform to any particular machine's architecture (since the language should be the same for different architectures anyway) so some nice things can be done.

Arbirary-precision integer arithmetic is a nice easy one and one that is done by many scripting languages already. This allows you to write expressions such as:

const int a = 1000000000000/1000;

and have a initialized to one billion even on 32-bit machines.

Rational arithmetic is also easy and useful. This allows one to write:

const int a = (1000/3)*3;

and have a initialized to exactly 1000 even on machines lacking any sort of floating point facility.

Then there are closed forms such as:

const int a = sqrt(1000)^2;  // a==1000, not 961

One could even make a compiler understand pi as a symbolic constant of type "Real" and evaluate it to the appropriate number of significant figures for the expression and type that is being initialized. So:

const int a = truncate_cast<int>(pi*10000);

would initialize a to 31416.

Once these things are in place, a compiler can perform quite sophisticated mathematical transformations to allow programmers to write what they really mean and still obtain optimal code. Even to the level of Maple/Mathematica if the compiler writers are sophisticated enough.

Posted in language | No Comments »

Compile time metalanguages

Friday, May 30th, 2008

The C programming language actually contains two different languages - C itself (the code for which runs at run-time) and the preprocessor language which runs at compile time and has completely different syntax. It's also not very powerful - often programmers resort to writing programs which generate C code as output instead.

It would be really nice to be able to make both these approaches unnecesary, and have a compile time language that uses the same syntax as the run-time language. A compiler ought to be able to detect parts of the program which run on constant data, run them during compilation and emit the output directly into the generated binary.

Replacing #ifdefs is easy - just use the normal "if" and ensure that your compiler will optimize away false clauses for constant expressions. GCC does this and indeed the GNU coding standards recommend this.

Replacing code that performs complex transformations on data is more complicated, but not intractably so as long as the compiler can reliably determine that all the functions used in these transformations are pure.

Posted in language | No Comments »

Lexical scoping and closures

Thursday, May 29th, 2008

A closure is a just a piece of code with some context - data on which it works. Such things are common in the functional programming community but were left out of the C language because they're actually quite difficult to implement properly.

The C++ language has sufficiently powerful constructs that one can create closures, but the syntax is very unwieldy. One must write:

class Totalizer
{
    int _total;
public:
    Totalizer() : _total(0) { }
    void operator(int x) { _total += x; }
    int total() const { return _total; }
};
 
int total(Vector<int> x)
{
    Totalizer t;
    for_each(x.begin(), x.end(), t);
    return t.total();
}

where one would really like to write something like:

int total(Vector<int> x)
{
    int t;
    for_each (x, lambda(int y) {t += y;} );
    return t;
}

Here the code is the "{t += y;}" bit and the context is the "t" variable, which is local to the "total" function.

C# 3.0 provides functionality like this.

What's really going on here is that an object is being created which encapulates some subset of the local variables (the "t" variable in this case) and which is passed to the for_each function (just like in the C++ version). Closures and objects are really just different syntaxes for the same thing.

If we want to return a closure from a function we can do so, but we must then allocate the object in such a way that the "t" variable will still be valid when the function exits. This is where things get really fiddly. This is one of those things that is easier in a language with garbage collection (you can just allocate the closure on the heap and the GC will take care of cleaning it up when it's finished with) but with care I think it should be possible to do it in a non-GC language as well.

Posted in language | No Comments »

Stringy identifiers

Wednesday, May 28th, 2008

In most computer languages, identifiers can only contain alphanumeric characters (plus, often, the underscore '_') and can't start with a number. There are very good reasons for this, but there are occasions when it would be desirable to be able to use arbitrary strings as identifiers. For example, suppose that we have a language that has a parser generator built in. Suppose also that we give it a parsing rule like this:

WhileStatement := ("while" | "until") "(" Expression ")" Statement

This is really just another way of writing a parsing class:

class WhileStatement { ... }

We would like the members of this class to be automatically generated by the parser generator in a predictable way. With string-identifiers, the generated class might look something like this:

  class WhileStatement
  {
    Enum { `"while"`, `"until"` } `"while" | "until"`;
    Expression expression;
    Statement statement;
  }

i.e. the name of the member variable which holds the piece of data about whether this is a "while" loop or an "until" loop is called `"while" | "until"`. The type of this member is

Enum { `"while"`, `"until"` }

which means that it can take only the values `"while"` and `"until"`.

This class can be used as follows:

  WhileStatement whileStatement = WhileStatement::Parse(file);
  if (whileStatement.`"while" | "until"` == `"while"`)
    ...

This reads very naturally, and avoids the need for anyone (human or compiler) to make up any variable names. It's good to avoid making the programmer make up names for things when not absolutely necessary.

Posted in language | 1 Comment »

Random numbers

Tuesday, May 27th, 2008

A commenter asked how random programs like random song shuffle work. How can a computer (which follows the same instructions each time) have unpredictable behavior?

Well, to understand this, first think about how random numbers are generated in the "real world" outside of computers. One way to do this is to throw dice - as long as you don't do something tricky, most people would agree that that's a perfectly reasonable source of randomness.

Except that if you really think about it, it isn't really random at all. In principle, one could make a machine that throws dice exactly the same way each time and always get a double six. You'd have to isolate it from stray air currents, minor gravitational influences from passing traffic and so on (as needs to be done for many sensitive scientific experiments). If you think about it, the randomness you get from throwing dice is really just due to these kinds of factors (and the fact that we human beings can't control our muscles finely enough to exert precisely the same forces each time). So really, what you're doing when you're throwing dice is "amplifying" these unpredictable factors (air currents, position, throwing force etc.) so that any tiny changes in them result in an entirely different number coming up.

Computers generate random numbers the same way. Well, sort of - they don't simulate the physics of three-dimensional dice being buffeted by air currents and bouncing off things - they do something that doesn't require such a complicated program but the same principle is at work. One reasonably common one (not the best, but fine for uses such as games) is to multiply by 22695477, add one and then take the remainder after divison by 4294967296. If I give you the sequence 953210035, 3724055312, 1961185873 you'd be hard pushed to tell me that those numbers were generated by that formula starting from the number 42 (maybe not quite so hard pushed as telling me the precise forces acting on dice given the numbers that came up but you get the idea). Other random number generators use the same idea but with more complex formulae to make the patterns even more obscure.

The problem with this method is that (as with any computer program) given the same input you're going to get the same output every time. And indeed this was a problem with some home computers and calculators in the 80s - if you tried to use the random number generator right after turning the machine on you'd get the same "random" numbers each time. The solution is to "seed" the random number generator somehow. The usual method is to use the current time. While it's predictable in some sense, you will get a different random sequence every time in practice so for most purposes you will never notice a pattern.

For some other purposes (like generating cryptographic keys or passwords, which have to be unpredictable even to people who are trying very hard to predict them) just using the time isn't enough and you have to mix in other sources of unpredictability (or "entropy" to use the technical term). This is why some SSH clients ask you to bash on the keyboard or wiggle the mouse the first time they are run - someone who wants to intercept your communications would have to know exactly which keys you pressed and how you wiggled the mouse (with extremely high precision). This is very easy to get wrong (and difficult to know when you've got it wrong) and can lead to security holes. Hence the old saw that "generation of random numbers is too important to be left to chance"! Some computers even have hardware built in which generates random numbers from unpredictable physical processes like thermal noise or quantum wavefunction collapse.

Once you've got a sequence of (pseudo-)random numbers evenly distributed over some range (for example 0 to 4294967295 in the above example) there are a variety of techniques to massage these into various different forms for different purposes. If you want an integer in the range 1 to 10 you can find the remainder after division by 10 and then add 1. If you want a random real number in the interval 0 to 1 you can divide by 4294967295. If you want numbers from a Gaussian distribution you can use a Box-Muller transform. And if you want to shuffle songs in your playlist you can start with an empty playlist and add a random song to it (removing it from the original playlist each time) until the original playlist is empty.

This last algorithm has a flaw in some sense (though it's more of a flaw in our brains). While all possible orders are equally likely, it will tend to play two songs in a row by the same artist more often than you would expect (just look at the bug database for any open source media player application to see the evidence for this). The problem isn't that the numbers aren't random enough, it's just that that if you have n artists in your playlist you'll see this phenomenon once every n songs on average. The problem is that we tend to notice this when it happens, and because the times when it happens stand out more than the times when it doesn't the problem seems to be worse than it really is. Another factor is that we are used to radio stations, which deliberately avoid doing this by hand-picking the order of songs rather than using a random shuffle. Some media player applications have appeased the complainers by actually making their shuffle features *less* random - adjusting the algorithm so it avoids picking orders which have two songs by the same artist in a row. This seems hacky to me, but if users like it I suppose I can't disagree with that.

Posted in computer, random | No Comments »

Object relational mismatch

Monday, May 26th, 2008

I don't have a lot of experience with SQL databases. Most of the programming I have done is object oriented. It's a little odd to hear about the "object relation impedence mismatch" because as far as I can tell the two paradigms complement each other quite nicely.

Object oriented programming creates complex things by sticking simple things together. So you might have a Customer object which can have any number of Order records. The Order records associated with a particular customer are easily accessible to code running in the context of a particular Customer.

Relational programming slices things up the other way. There is a table of Customers and (completely separately) a table of Orders each of which points back to a particular Customer. All the Orders are stored together no matter which Customer did the ordering. This has the advantage that you can easily look through the Orders for (e.g. every Order of a particular widget, without looking through all the Customerrs first.

The downside is that relational programmers spend lots of time writing things like "SELECT o FROM Orders where o.customer==customer" to retrieve the data that would just "be there" in context, if you were using objects.

It seems natural to try to combine these two styles - to persist objects to long-term storage by slicing them up into normal form components which are then stored in tables representing different classe, and to automatically generate queries for interesting chunks of related data and construct objects based on them. Then you could generate different object structures for different problems (for example, your Order objects might be organized by widget instead of by customer for stock-keeping purposes.

I know some things like this have been done but it seems such a clearly useful thing to do that I'm surprised it isn't completely ubiquitous by now. Why don't OSes come with a transactional databases as basic system services? Is it just that the object people and the relational people don't talk as much as they should? It would be really cool if a compiler stored its syntax tree in such a way that I could make a list of (for example) the set of "if" statments in a program being compiled.

Posted in computer | No Comments »

Mixins in C++

Sunday, May 25th, 2008

A desirable property of C++ class libraries is to be able to leave the inheritance hierarchy up to the user of the library. For example, suppose you are writing a UI framework. You have a "Window" class - every window in the system is represented by an object of some subclass of Window. Windows can be animated, scrollable or dockable. Each of these attributes has some data and methods associated with it, so naturally forms a class. But any combination of these attributes also forms a class. So to be fully general your library would have to provide 2n possible classes - clearly not very practical.

A solution is to provide each attribute as a Mixin (the name was inspired by an ice cream parlour near MIT which allowed you to mix in extra items like crumbled cookies and jelly babies into your base ice cream flavour). A Mixin is a template class parameterized on its superclass, like so:

template<class Base> class Animated : public Base { ... }

Then you can specify a class hierarchy like:

Animated -> Scrollable -> Dockable -> Window

as the template class:

Animated<Scrollable<Dockable<Window> > >

The trouble with this is: how do we construct an object of such a type? An object's constructor needs to know how to construct its base class, which means that you'd still need to write 2n constructors. I found a paper which provides a rather convoluted solution using all sorts of macros and template programming wizardry, but I thought of a much simpler way.

All you need to do is have some sort of standard for constructing an object. For example:

template<class Base> class Animated : public Base
{
public:
    class Params
    {
        friend class Animated;
    public:
        Params(typename Base::Params bp, ...) : _bp(bp) { ... }
    private:
        typename Base::Params& _bp;
    }
    Animated(Params p) : Base(p._bp) { }
    ...
}

And similar subclasses (with the same name) for all the other mixins and the base flavor class.

Then you can instantiate your composite class as follows:

Animated<Scrollable<Dockable<Window> > >
    window(Animated<Scrollable<Dockable<Window> > >::Params(
        Scrollable<Dockable<Windows> >::Params(
            Dockable<Window>::Params(
                Window::Params("blat"), "baz"), "bar"), "foo"));

or, if you don't like typing n2 identifiers:

Window::Params wp("blat");
typedef Dockable<Window> D;
D::Params dp(wp, "baz");
typedef Scrollable<D> S;
S::Params sp(dp, "bar");
typedef Animated<S> A;
A:Params ap(sp, "foo");
A window(ap);

You also get the advantage that your calling code says exactly which parameters belong to which mixin, improving type checking (similar to the named parameters construct described in D&E).

Posted in computer | 2 Comments »

Scripted merge

Saturday, May 24th, 2008

I've been thinking a bit about version control systems. It occurs to me that almost every element of a version control system is actually fairly easy technically except for two - diff and merge.

Diff is the process of finding the difference between two files - I've written about some ways to deal with this in the past.

Merge is process of taking two changes X and Y and finding the change Z consisting of both X and Y. This sounds easy but it's really solving the "A is to B as C is to what" problem (the original being A, X being B, Y being C and Z being the answer). Suppose X is adding a method to a class and Y is renaming the same class. Most merge systems would add the new method with the original name (since Y didn't include renaming of the new method).

I think the answer is to treat every change as a little program in its own right. X isn't just "inserting the lines corresponding to the new method", it's "insert the lines corresponding to the new method, substituting the current name of the class where appropriate" and Y isn't just "change this list of instances of Foo to Bar" it's "change Foo to Bar everywhere it appears in the context of a class name in namespace Baz". In other words, have the changes themselves actually have some intelligence about what they are supposed to be doing. Then these programs could just be "run" (in any other) and produce the correct result.

Such changes would be more than just lists of "insert this text in this position in this file" and "delete this text from this position in file", and could therefore not easily be generated from diffing two files.

However, such changes could be generated by a text editor which has some understanding of the format of the files it is used to edit. For example, if such an editor had a "rename class" command, it could generate a change saying exactly that.

Posted in algorithms | No Comments »

Gun control

Friday, May 23rd, 2008

Lots of people in the media (especially in the US) say lots of things about guns. Here are my thoughts on the matter.

  1. Killing people is bad. One should try to avoid killing people as much as possible.
  2. Guns are, fundamentally, designed for killing people (some may be sold for other purposes but killing people is what guns were invented for).
  3. Because of (1) and (2) there is something inherently quite distateful about guns.
  4. So it is understandable that many people dislike guns and don't want to own one or be around people who have them.
  5. There are some types of weapons (such as nuclear weapons) which no individual should be allowed to own.
  6. There are some types of weapons (such as kitchen knives) which any non-incarcerated adult should be allowed to own.
  7. Not all weapons fall into categories (5) or (6).
  8. There are some people (those with criminal pasts, unsound minds or who are just not sufficiently responsible) who should not be allowed to own guns. Loopholes which allow them to obtain them legally should be closed.
  9. It would be impossible to ban all private gun ownership in the USA.
  10. When a national government bans all its citizens from doing something which was previously allowed and widely practiced, this is usually a bad thing.
  11. Because of (9) and (10), some people should be allowed to own certain types of gun.
  12. Even those who have had lots of training in the safe and proper use of guns sometimes make mistakes and shoot someone who is not a threat.
  13. Some criminals are not afraid of death, and will commit mass murder even knowing that doing so will get them killed.
  14. In practice, most of the people who want to own a gun and should be allowed to own one probably own one already.
  15. Because of (3), (8), (11), (12), (13) and (14), arming everybody is not a solution to gun crime not even practical (no matter how much some gun enthusiasts would like it to be.
  16. As it is in the interests to gun sellers to sell as many guns as possible, it should not be up to the gun sellers to determine who should be allowed to own a gun.
  17. It would be difficult but possible to prevent most of the people who should not be allowed to have guns from having them, to reduce the number of guns in the hands of people who should not have them, and to reduce the number of gun deaths (accidental and deliberate) in the USA.

Another thought I had about this recently: In some senses, gun ownership is already de facto illegal (and has incredibly harsh penalties), even if it is technically legal. If a police officer thinks you have a gun and feels threatened by you, he can shoot you dead (effectively acting as judge, jury and executioner for the "crime" of gun ownership) and suffer no legal consequences. This is a risk for all gun owners (and, to a lesser extent, gun non-owners) whether or not the gun is "by the book" legal.

Posted in random | No Comments »

Rotating fractals

Thursday, May 22nd, 2008

Fractals like z=z^2+c and z=z^3+c are easy to draw because they just involve complex addition and multiplication. What happens if we try to generalize these sorts of fractals to non-integer powers?

We can do this using the identities
\displaystyle z^w = (e^{\frac{\log z}{\log e}})^w = e^{w\frac{\log z}{\log e}}
\displaystyle e^{x+iy} = e^x(\cos y + i \sin y)
\displaystyle \frac{\log z}{\log e} = \frac{\log |z|}{\log e + i(\arg z + 2n\pi)}

The trouble is, we have to pick a value for n. Given a parameter \theta we can pick n such that \theta - \pi \leq \arg(x+iy) + 2n\pi < \theta + \pi (i.e. choose a branch cut of constant argument and a sheet of the Riemann surface): \displaystyle n = \lfloor\frac{1}{2}(\frac{\theta - \arg(x+iy)}{\pi} + 1)\rfloor. Then as we gradually vary \theta the fractal we get will change. For w = u+iv, v \ne 0, increasing \theta will cause z^w to "spiral in" from infinity towards the origin (v<0) or out (v>0). When v = 0, increasing \theta will have a periodic effect, which will cause the fractal to appear to "rotate" in fractally sort of ways with a period of \displaystyle \frac{2\pi}{u}.

It would be interesting to plot these as 3D images (like these with \theta on the z axis. These would look sort of helical (or conical, for v \ne 0.)

Using u < 0 poses some additional problems - the attractor isn't bound by any circle of finite radius about the origin so it's more difficult to tell when a point escapes and when it is convergent but just currently very far out. Clearly some further thought is necessary to plot such fractals accurately - perhaps there are other escape conditions which would work for these.

Posted in fractals | 2 Comments »

« Older Entries