Recent Entries [entries|reading|network|archive]

[ userinfo | dreamwidth userinfo ]
[ archive | journal archive ]

Wed 2014-04-23 10:49
Unsolved problem writeup

Thanks to everyone who commented on my previous entry with proofs, software and other useful comments. I think I've now taken the investigation of this problem as far as I have the energy to, at least for the moment. A collection of all the useful things I know about it, including a big pile of data, is now up on a web page:

[xpost |]

Link19 comments | Reply
Wed 2014-02-19 10:52
Unsolved problem

Here's a mathematical sort of question that occurred to me last year. I've been pondering it off and on ever since, but not reached any useful conclusions; and I just came across my file of notes on it, and thought perhaps I should post it somewhere for other people to ponder as well.

cutting up sticks and reassembling them )
[xpost |]

Link43 comments | Reply
Mon 2014-01-27 18:42

A few months ago I was talking to a friend who was intending to learn C, having previously only worked with higher-level languages. We had a conversation about the assorted (and mostly painful) culture shocks that C is liable to deliver to someone whose previous experience of programming is rather less user-hostile, and afterwards I thought, hmm, that turned out to be quite a lot of potentially useful and more or less organised information, perhaps I should write it up.

It's taken me a few months to get round to it and to fill in the last few pieces, but it's now done. In case anyone reading this finds it useful, or knows anyone else who would, I present

This is a bit of a departure from the usual kind of article I write and put on the web. It's about the only thing I've written that's purely educational in nature, in the sense that it rehashes material well known to many for the benefit of those who don't already know it, rather than presenting stuff I've invented myself and don't expect anyone to already know. For some reason that makes me feel noticeably more nervous about its reception (perhaps because there's scope to be vigorously criticised by both its intended audience and people who already know the material and think I've got it wrong). But I hope someone finds it useful, anyway!

[xpost |]

Link11 comments | Reply
Sat 2013-09-21 20:57
Covered in Bs

I'm currently in the middle of two weeks off work. During this time I'm trying to get a few long-standing chores done, and a few things mail-ordered while I'm conveniently in to receive the deliveries. And it occurred to me today that more or less everything on that list of chore-type activities has unexpectedly turned out to begin with B.

I've mail-ordered: some bread flour, some books, and some biscuits.

Additionally, I've bought a belt, and booked a boiler service.

Given all that, I think I ought to take care to avoid referring to this two-week period as a ‘holiday’. This one is unquestionably a break!

[xpost |]

Link6 comments | Reply
Fri 2013-07-12 09:41

It's increasingly occurred to me, as I get older and crustier, that I find myself saying things to people that I've said a number of times before.

Some of them are well known adages or observations, of course, but others are things that I wasn't previously aware of, or put together from several other pieces, and they've gradually become a sort of collection of my personal adages and laws and maxims.

A few months ago I idly wondered how many of those I actually had, so I started collecting them in a text file. I've come up with more than I expected, so I thought I'd post them in one go for your entertainment.

ten short pontifications )
[xpost |]

Link19 comments | Reply
Wed 2013-06-19 14:02
Line comments versus line splicing

Here's a thing I was pondering the other day about lexing.

Suppose you have a language containing two moderately common lexical features: a comment mechanism in which comments are newline-terminated (C++/C99 style //, shell #), and a line-splicing mechanism in which a backslash at the end of a line causes the next line to be glued on to it as if they were one long line. How should these interact?

some ponderings and a suggestion )

[xpost |]

Link16 comments | Reply
Thu 2013-03-14 15:16
Do I it means means not that think think what you

Inspired by completely mistaking the meaning of a class name this week ...

Poll #13035 Hey, I ordered a cheeseburger
Open to: Registered Users, detailed results viewable to: All, participants: 26

I would take the phrase "ordered pair" to mean

View Answers

A pair (a,b) in which a <= b always
3 (11.5%)

A pair (a,b) in which (a,b) and (b,a) count as different unless a=b
19 (73.1%)

I would always ask which one you meant
3 (11.5%)

1 (3.8%)

I would take the phrase "ordered list" to mean

View Answers

A list which is in order according to some sorting criterion, e.g. alphabetical
19 (73.1%)

A list in which order is significant, i.e. [1,2] and [2,1] are interestingly distinct
5 (19.2%)

I would always ask which one you meant
2 (7.7%)

0 (0.0%)

I would take the phrase "ordered collection", in the context of data structures, to mean

View Answers

A data structure which keeps elements in an order determined by some sorting criterion
9 (36.0%)

A data structure which considers the order of elements to be an important part of what it's remembering
11 (44.0%)

I would always ask which one you meant
5 (20.0%)

0 (0.0%)

[xpost |]

Link13 comments | Reply
Fri 2013-03-01 00:03
Because it still seemed funny after I got home from the pub

[xpost |]

Link1 comment | Reply
Fri 2012-12-21 09:19
Time comes to an end

Hmmm. This morning I looked at my watch and discovered that it was reading a completely random time of day. It's also lost its ability to sync with the MSF radio signal from Rugby, and for good measure it's forgotten its settings too (particularly the vital ‘don't go beep all the time’).

Now those could all be consequences of a low battery, possibly with a side order of MSF being harder to hear in Dorset (where I'm currently visiting Dad) than it is in Cambridge.

But on this day of all days, perhaps there's an alternative explanation. Time really has come to an end, and that's why my watch isn't telling it any more!

[xpost |]

Link5 comments | Reply
Wed 2012-11-21 10:13
Found pun

This morning I noticed a sort of ‘natural pun’ between maths and software. I suspect about three people will get it, but I'll say it anyway because it's too good to lose.

The Schröder-Bernstein theorem states that given injections from a set A to a set B and from B to A, you can find a bijection between A and B. There's a well known construction proving the theorem, which goes like this: draw a graph whose vertices are the elements of A and B, connect a (in A) and b (in B) with a red edge if f(a)=b, and with a blue edge if g(b)=a. This gives every vertex a red-degree and blue-degree at most 1, so each vertex has at most degree 2 and so the graph decomposes into connected components which are chains or loops; furthermore, no chain can be finite (because in one direction you can keep applying f and g forever). Now in most kinds of component you can pair up the elements by simply saying ‘use the blue edges’ (so that on those points, the bijection h we're constructing matches f); the only case where that doesn't work is a one-way infinite chain starting with a red edge, in which case you can just use the red edges instead (so that h matches the inverse of g).

If you actually apply this construction to find a bijection between two sets which are mostly similar but one contains a few elements not in the other, then the resulting bijections tend to be of the form: map everything to itself, unless it's one of the things we want to avoid, in which case do a sort of ‘quoting’ transformation to turn it into something safe – but then we also have to apply the quoting transformation to any input which could have been derived from a bad thing by repeated quoting. For example, if you want to find a bijection between the non-negative real numbers and the positive real numbers (that is, the former including zero and the latter not), you can map x to itself in most cases, and map x to x+1 if x is either zero or anything reachable from zero by repeated adding of 1 (i.e. if x is an integer).

It occurred to me this morning that this is identical to a procedure frequently used in software for reversible quoting. For example, the mbox mail folder format separates emails with lines starting with the word ‘From’ followed by a space. Therefore, if such a line shows up in an email, it needs quoting, and what generally happens is that you put a ‘>’ character before it. But to make that quoting properly reversible, so you can distinguish lines that start ‘From’ from those that already started with ‘>From’, you must also quote any line which begins ‘>From’ or ‘>>From’ and so on – that is, any line which could have been derived from the thing you want to avoid by repeated application of the quoting transform. It's exactly a Schröder-Bernstein construction.

And what makes this amusing is that this reversible scheme for quoting in mbox files is not always used, because not everybody is that rigorous – but it is used by qmail, by Dan Bernstein. Hooray!

[xpost |]

Link6 comments | Reply
Sat 2012-08-11 08:26
My Hasse diagram done better

Almost four years ago I had a silly idea, and used Graphviz to generate a Hasse diagram of the 2008 Olympic medal table, under the partial order with which any sensible ranking of medal counts (irrespective of the country producing them) must agree no matter what relative importance it assigns to gold, silver and bronze.

I had an email from the New York Times a few weeks ago, saying that they were planning to pick up my idea and do the same thing this year. All they wanted to know was how to credit me accurately, but I mentioned to several friends a sneaking suspicion – based on previous interactions with journalists interested in my maths-and-computers frivolities – that round about now I might find then coming back and asking for a little help with the coding.

Apparently I greatly underestimated them. I've just checked my web logs and found this page: Not only did they have no trouble at all repeating my analysis, but they've managed to automate it on a web page so conveniently that they're able to drop in new data sets effortlessly – and so they're able to put it up before the Olympics are over (and presumably, therefore, it keeps running track as more medals are won), and have it also show the Beijing results and have a button to adjust for population. And their version is prettier and has mouseovers. Nice work, NYT!

[xpost |]

Link18 comments | Reply
Mon 2012-05-28 15:46
Numbers and words

This morning I tried to return a phone call. I managed to dial the wrong number three times at widely separated intervals, and (I later worked out) on all three occasions I transposed the same pair of adjacent digits. And despite carefully cross-checking between the number shown on the display of my phone, the number on the email (my employer's voicemail system works by sending you an email containing the caller ID and a sound file) and the number read out by the caller, I managed not to spot the error for most of the morning.

I'm actually quite worried by that. I've always prided myself on my ability to remember long strings of digits, and found it repeatedly useful. I've known for a while that I was prone to occasionally transpose adjacent digits in a number I'd only just seen, but I usually notice on the second attempt. This is the first time I've spent hours completely blind to the difference between the right and wrong versions and I don't like the feeling. :-(

My best guess for how it might have happened is that the transposition turned a trailing 245 into a trailing 425, and my brain might have found the latter more plausible because it's common to see round-ish numbers ending in 25, so perhaps it unilaterally 'corrected a typo'. But even that's not a very good explanation.

In other news, I visited my niece at the weekend, and she's just learned to say my name. (She's one and a half.) I'm not usually all that susceptible to the cuteness of toddlers, but when they repeatedly look at me and say ‘Si-mo’ I have been forced to make an exception.

[xpost |]

Link12 comments | Reply
Mon 2012-05-07 13:49
Not bad for a first effort

Today I got out needle and thread and made a new strap for my watch.

My diary archives tell me that it was on 4th July 1998 when I last did this. I had been advised by a doctor that wearing a watch constricting my wrist might have been contributing to the wrist pains I had at the time, and after trying various other solutions (e.g. things that weren't actually watches, or just getting good at reading other people's watches upside down very quickly when their wrists turned towards me) I hit on the plan of making a custom strap which velcroed round my belt and had a little loop to fit to the watch. This turned out to be a great idea; I haven't had those wrist pains in years, so I could in principle go back to wearing a watch on my wrist, but I really wouldn't want to any more. It's very convenient not to have to take it off to wash up, and having my watch attached to my trousers makes it incredibly difficult to accidentally leave it at home or anywhere else.

That custom watch strap was the very first thing I ever sewed. I had to more or less teach myself to sew in the course of making it, and my diary archive also records that I sewed my thumb to it in the process. Given that, I think, it's a reasonably decent result that it's lasted until today, when I finally decided it was so close to falling apart that I didn't trust it not to fail suddenly and drop the watch down a drain, so I sat down and sewed a new one.

I'm not actually sure my sewing has improved all that much in the intervening thirteen years and ten months. I didn't sew myself to anything this time, but the actual stitching is in much the same robust but unaesthetic, purely functional style as it was on the first strap. The only real difference is that this time I made the strap out of leather rather than rucksack strapping, in the hope that it would be both thinner and less prone to unravelling.

So, I wonder how long the new one will last! To do as well as the original, it'll have to survive until March 2026.

[xpost |]

Link8 comments | Reply
Mon 2012-03-12 18:52
Yet more C abuse

In two recent posts here, I've suggested moderately evil things to do with the C preprocessor, both on the same theme of defining a macro that can be used like a loop keyword by following its invocation with a statement or block of your choice.

Last week some further thoughts on the subject occurred to me, which were rather more comprehensive and also considerably more evil still. I think I've now taken that general idea to somewhere near the limit of its possibilities, by developing a general system of construction-kit macros that make it more or less feasible for people to develop custom loop types.

The result is far too long to fit in this post, so I've put it up on my website. For those with a strong stomach and an interest in metaprogramming or C abuse or both, I present ‘Metaprogramming Custom Control Structures in C’:

[xpost |]

Link6 comments | Reply
Tue 2012-02-28 09:17
I shouldn't be allowed in a kitchen

I mentioned two weeks ago that I'd cut my fingers chopping onions again.

A few days after that I managed to cut my foot in the kitchen: I dropped a plate, which shattered on the floor, and since I happened to be barefoot at the time my toe was gashed open by a sharp piece of flying crockery.

And last night I splashed boiling water over my hand while taking a pan of potatoes off the hob, and not content with that threw half the potatoes over the kitchen in the process.

I've bought an onion-chopping gadget, but it's possible that what I should have bought instead was a chef, so that I could never set foot in a kitchen again.

[xpost |]

Link7 comments | Reply
Tue 2012-02-21 11:53
C abuse of the week

I continue to be amazed at the number of bizarre things you can arrange to do using the C preprocessor, the switch statement, and a strong stomach. I've previously used the combination to implement coroutines, of course, and also a modified version of for which performs its test after the loop body rather than before it.

Chris mentioned to me this morning the fact that you could write this sort of thing:

    switch (get_value()) case 1: case 2: case 3: do_stuff();

which has the handy effect of calling get_value() only once and then testing its return value against several possibilities (though they're constrained to be compile-time constant integers). But of course it's hopelessly ugly, so he challenged me to wrap it up in a macro or two. (Not that that stops it being ugly, exactly. But differently ugly. :-)

The obvious solution seemed to me to be this:

#define IF_IN_LIST(expr,list) switch (expr) case list:
#define OR : case

which then lets you write compound statements that only look slightly un-C-ish:

    IF_IN_LIST(get_value(), 1 OR 2 OR 3)

But then I realised that if you dangle a few more oddities off the switch statement, you can do better. If you do it like this:

#define IF_IN_LIST(expr,list) switch (expr) default: if (0) case list:
#define OR : case

then your uses of the macro can now include an optional else clause!

    IF_IN_LIST(get_value(), 1 OR 2 OR 3)

(And naturally both versions work with either bare statements or braced blocks.)

[xpost |]

Link4 comments | Reply
Wed 2012-02-15 09:51

Nasty cuts on two fingers of my left hand today, after an onion-chopping accident – two layers of the onion unexpectedly detached and slid along each other, one carrying the knife with it.

This is the second time in recent years that this has happened; when the current cuts heal, the scar on my middle finger will sit next to a suspiciously similarly-shaped one on my index finger from 2009. Onions were the culprit on that occasion too.

So perhaps, for my own safety, I should invest in a gimmicky kitchen gadget for chopping onions. A quick google this morning suggests that there are several quite different-looking designs, though, and I'm not at all sure which is likely to be most effective…

[xpost |]

Link18 comments | Reply
Tue 2012-01-03 09:38
Forgot my password!

I got into the office today after a relaxing holiday of three weeks (plus yesterday) and found, embarrassingly, that I couldn't remember my work password any more. I could remember a password, but I was pretty sure it was the one from before my most recent change, and it certainly didn't work when I tried it.

I can't believe that. First password I've forgotten in over a decade, surely. I had to go and queue outside the IT helpdesk room like a gormless student.

I had a brief moment of hope when I got back to my desk and found the new password didn't work either. ‘Aha!’ I thought, ‘perhaps the password I'd remembered was right after all, and it's just my desktop computer that's confused.’ But no; after some more faffing, it turned out that password changes are just propagating slowly this morning and I had forgotten my original password after all.

It's at moments like this I feel that companies ought to have a mechanism whereby you can turn round and go home and back to bed, on the basis that you're likely to do more harm than good if you continue trying to do work.

[xpost |]

Link15 comments | Reply
Wed 2011-12-07 15:45

I had a disgusting thought just now. I needed to have some Python code check whether a dictionary contains a particular key/value pair. The obvious approach,

if dictionary[key] == value:

isn't sufficient, because I need to not throw an exception if the dictionary doesn't contain any mapping for that key at all.

An obvious way is to use a second clause to handle the latter case, so you end up writing

if key in dictionary and dictionary[key] == value:

But that's unpleasantly verbose, and also undesirable if dictionary or key is a complicated expression or one with side effects. So I wondered if we could do better.

Another possibility is to use the get() method of Python dictionaries, which lets you specify a default return value if the dictionary hasn't got the key in question. So you might say, for instance,

if dictionary.get(key, None) == value:

But in order to be able to do that, you have to be able to think of a default that will guarantee to compare unequal to value; for instance here, what if the value is None? If you know something about value (e.g. its type) then this is probably feasible one way or another, but one can imagine more general situations in which that wouldn't be the case.

I think the right answer, in fact, is to write

if (key, value) in dictionary.viewitems():

where viewitems() is a standard method which presents the dictionary as if it were a set of ordered pairs. (You could also use dictionary.items(), which would be semantically equivalent, but much slower due to constructing an explicit list and then iterating along it.)

But before I found the viewitems() method, I thought a bit harder about the get() approach. Perhaps, I thought, I could define a class with a comparison method that always returned false, so that an instance of that class would compare unequal to anything, including itself.

And then, as I thought the phrase ‘compare unequal to anything, including itself’, a stray neuron fired in my head. I think this would work pretty reliably:

if dictionary.get(key, float('nan')) == value:

and its only downside is that it is the most disgusting thing ever! :-)

[xpost |]

Link42 comments | Reply
Thu 2011-10-06 19:13
Sometimes I have an idea and then just wish I hadn't

Many Unix programmers will be familiar with the utility variously called strace, truss, ktrace, dtrace and probably other names too, which logs all communication between a process and the kernel across the system call interface.

A couple of years ago I wrote an analogous program called xtruss, which produces similar logging but operates at the interface between an X11 client program and the X server. (Of course, that wasn't a new idea; I just liked my version's design better than prior ones, mostly because it behaves more like strace.)

A related piece of software to strace is Subterfugue, which intercepts system calls using the same underlying technology that strace does, but instead of passively monitoring them, is able to modify the results as it sees fit. The result is a user-scriptable system that allows you to subject a process to all sorts of subtle and not-so-subtle illusions or behaviour modifications; it can be quite tricky to do anything that's both useful and robust with it, but it's potentially pretty powerful. (It's also not been maintained for ages, but that's not relevant to my current train of thought.)

Today I had the idea: why not fill in the blank in that table, and write the thing that is to xtruss what Subterfugue is to strace? Reuse xtruss's framework for conveniently setting up one-off X11 proxies between a specific application and the X server, and then implement a marshalling and demarshalling layer which translates between wire-encoded X11 messages and an unpacked format that can be accessed by a popular scripting language. Then you could arrange both large and small special effects on X programs, and in particular you could cause them to happen on a per-client basis rather than uniformly across the whole server.

But that wasn't the idea I started off with. I was actually wondering about a much more specific problem: remapping – and occasional complete destruction – of X keystroke events on a per-application basis, for applications with inadequate built-in keymap configurability. (For instance, I keep accidentally hitting a key combination in my work email client which causes half-composed messages to be sent without confirmation, but I'm unwilling to just define that key combination to be a window-manager hot key for ‘do nothing’ in case I turn out to need it in some totally different application.)

And since I already have the X proxy framework from xtruss, the thought occurred that I could enhance it just a little to let it rewrite or squash X events, and then I'd have a proxy that would do the thing I wanted; and although this would certainly be a disproportionate effort for the result if I were writing that X proxy from scratch, doing it by slightly modifying code I've already got seemed almost practical by comparison.

But of course once I'd thought of doing this job by proxying an X connection and rewriting pieces of it, I realised that that certainly wouldn't be the only use for such technology, which led immediately to the idea of a Subterfugue-like general framework.

And on the one hand that does sound like quite a fun piece of software … and yet, we're now back to it being a huge amount of work to go to for the sake of the one specific application I actually wanted it for, and I'm pretty sure I can't be bothered. But on the other hand, now I've imagined the generic version, I also wouldn't feel right about writing just the one-off utility that only does key mapping (or, worse still, only the specific key mapping I wanted). Bah.

(There seems a good chance that at least one reader will point out some totally different way in which I could impose keystroke-mangling of my choice on an uncooperative X client. I will be grateful for that, but it won't affect the main point, which is that sometimes having an apparently cool and generalising and elegant idea makes me less happy, and furthermore, bah.)

[xpost |]

Link6 comments | Reply
[ viewing | 20 entries back ]
[ go | earlier/later ]