Slash Boxes
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

robin (1821)

  (email not shown publicly)

Journal of robin (1821)

Tuesday March 19, 2002
04:54 PM


I moved into my girlfriend's flat at the weekend, from the shared house where I've been living for the last few years. In truth I've already been living here for a year or so, it's just that all my possessions were the other side of London. So it's a huge relief to finally have all my stuff. The first thing I did was to shelve my books, and I got a good deal of geeky pleasure from deciding how to organise them. I was so excited about it that I photographed the result.

There was one problem - there's no phone socket anywhere near my desk, and no extension cord long enough to reach the nearest one. But fortunately the phone line actually enters the flat right here, so I just wired the modem directly into the junction box. I expect that's hopelessly illegal, but it seems to be working fine.

From the repetitive-sounding module news department, I've released yet another new version of PadWalker (0.08) which fixes even more bugs and also adds a secret hook into the internals for Richard Clamp to use in his nefarious activities. Peter Scott has submitted his debugger patch which relies on this new version.

Thursday March 14, 2002
03:48 PM

Bits and bobs

New version of PadWalker, which actually co-operates with the debugger. Peter Scott is trying to use it to write a debugger enhancement so you can see your lexical variables when you're debugging. But you can also just debug that PadWalking program without everything going horribly wrong. I'm rather embarrassed at how grotty the PadWalker code was, but at least it's getting better...

This is a very funny short film (avoid if you're easily offended and/or lack a sense of humour). It seems to be some viral marketing crap, but it's still very funny.

I've only just noticed that the window-close blob on OS X (the red one) gets a little splotch in it when your document's been modified. Nice feature.

Thursday March 07, 2002
06:07 AM

Camels and categories

I've just returned from a few weeks in Rajasthan, India. I didn't do any Perl as such, though I did visit crab and cross the desert by camel.

I've been busy this week, and have just released new versions of Algorithm::FastPermute (more portable) and PadWalker (less buggy). Peter Scott has written a patch to the Perl debugger which uses PadWalker to allow you to inspect lexical variables from the debugger. I hope that it will actually work now, and get into 5.8 before it's too late.

Otherwise, I'm mainly learning category theory. I keep trying to read papers in computer science which don't make any sense at all because I don't grok the categorical language. Also, I want to learn categorical logic (toposes and so on); and there's no hope of that until I'm fluent with the basics. The most interesting thing I've learnt so far is that "A comathematician is a system for turning theorems into coffee".

Monday January 21, 2002
07:51 PM


I haven't written in this journal for quite a while, to put it mildly. Today seems a good day to bring it up to date, in a fragmentary way. Looking back at the last entry I made, it feels like a long time ago; but I haven't done a great deal of Perl since then. In November I gave a talk to dorkbotlondon about the elephants. A triumph ;-)

My main obsessions recently have been formal language theory, logic, and algebra. I'm excited today, because I just found out that I've been offered a funded place on the logic course I applied for, starting in September (the day before my 26th birthday). By coincidence, I'm going to Manchester tomorrow to visit the department; I'll feel a lot more relaxed about it, knowing that I've got a place! I've never been to Manchester before; apparently it rains a lot. (For a while I was planning to apply to MIT, and I even went to far as to take the GRE, but I gradually realised that not only would it be personally difficult to be so far from home for so long, but also that there's very little activity at MIT in the purely theoretical areas which interest me most.)

I also became a Perl monk since I last updated this. The site is organised like a game -- you gain points depending on how many people vote for your contributions. Not only is it a great resource for beginners, but there's a fair bit of advanced Perl going on there too (not to mention the occasional gems)

Connecting Perl and theory, I've become fascinated by regular expressions which allow back referencing (like /^(.*)\1$/). They've been largely neglected by theorists, and yet they're so rich and subtle. The known theoretical facts (as far as I can tell) are:

  • The problem of deciding whether a regex [1] matches a string is NP-complete.
  • If you have a regex $r, there isn't necessarily a regex which matches all and only the strings which $r doesn't match [2].
  • The deeper you allow capturing expressions to be nested, the more languages can be expressed.
  • Not all context-free languages are expressible using regexes, and not all regex-expressible languages are context-free.

(I suspect this last fact partly explains their neglect: they don't fit cleanly into the Chomsky hierarchy of languages.) So there's a host of interesting questions still to be answered. I've made a small amount of progress with one or two of them I think, but no definitive answers yet . Most recently I've been toying with the idea that if you restrict the capturing to be at the top level (i.e. not inside a (?:$foo)* or another capture ($bar)) then the resulting formalism is weakly equivalent to word equations (i.e. equations over a finitely-generated free monoid) with regular constraints. If that's true, it connects the theory to something that mathematicians are interested in! (The puzzle I recently posted to FWP is related to this conjecture.) On the down side, even if it's true it may well be rather hard to prove.

Another wild thought: what if you specify an order-sorted algebra with words (i.e. strings) as an explicit sub-sort of regular expressions? Word equations and regular expression matching could both be described in such an algebra, and in a unified way. Is that any use for anything? I don't know...


[1] I'm just talking about traditional regular expressions with the single addition of back referencing. Look-ahead operators, embedded code, independent subexpressions etc. aren't allowed, for my current purposes.

[2] Note that if you allow the negative look-ahead operator, this obviously stops being true. However much weirder things start to happen then, and I don't want to go there for the moment.

Saturday October 13, 2001
09:30 AM

Pretty pictures

Well now, seekers, do you remember the pretty combinatorial graphs I was playing with a few weeks ago? I only showed you one of them before, which I call the elephant because it looks like an elephant seen from the underneath.

The other one is here (the edges represent transposition of adjacent elements). I'm not quite sure what to call it - it reminds me a little of a trampoline for some reason.

Print out one of these graphs, and choose two vertices which are an odd number of edges apart. Now take a highlighter pen, and try and draw a continuous line which

  • starts at one of your chosen vertices
  • ends at the other one
  • always follows the printed lines
  • goes through every other vertex

It's good fun, the results are pretty, it can be suprisingly difficult, and there's even a serious point to it.

[[ The graphs have a lot of symmetry, so there are only five essentially different ways to choose an odd pair. So you only have to solve ten of these problems (five for each graph), and you can be sure that it's always possible. Furthermore, any way of breaking all four-element permutations into pairwise element swaps can be reduced to one of these two graphs. Then you can use a fairly simple inductive argument to extend the result to any such graph of the permutations of four or more elements, and that's the central result of Maurice Tchuente's paper. ]]

Saturday October 06, 2001
10:17 AM

Put your best foot forward!

It worries me. I don't know what notion of foot quality is being used, or how to measure it. Even once that has been agreed, it is surely possible that the quality of the left foot will turn out to be equal to that of the right; in which case the subject fails to denote, and we're in real trouble.

Keen as I am to improve the state of the world, I propose the following replacement. I think it captures the intent of the original, without being susceptible to that catastrophic mode of failure:

"At least one of your feet is such that the other is not better than it. Put forward such a foot!"

Be sure to agree in advance which quality metric you're using.

08:25 AM

Want for Win32

I should have mentioned this weeks ago. You can now get a binary distribution of the Want module for Win32. Download the two files from here into the same directory, and do ppm install Want-0.05.ppd. Many thanks to Daniel Berger for going to a lot of trouble to get this built. If you try it, let me know how it goes.

Now Windows users can participate in the context revolution too.

Daniel also pointed out that Want will fail if you try to use it from a subroutine which implements an overloaded operator. (People will try the strangest things.) It's going to be messy to fix, but I now once again have hope that it's possible. At the meeting on Thursday, I drunkenly explained the problem to Nicholas Clark, who proposed a startling but ingenious solution. "It's a crazy idea," I said, "but it might just work."

08:03 AM

Extended regular expressions

I've been thinking a lot about regular expressions recently, and so I was grateful to find Exploding Dog's reminder of the futility of turning to extended regular expressions for solace in a time of crisis.

07:47 AM

Speak truly by contradicting yourself

One consolation of the dull job I'm doing at the moment is that it's within easy walking distance of my favourite London bookshop. Last week I managed to escape there at lunchtime, and spent a happy half-hour browsing the shelves. Glancing through a (very good) book on paradoxes, I was startled by a section towards the end describing an account of truth on which contradictions can be true , called dialetheism. It's a shame that the supposedly definitive book on the subject is so prohibitively priced, especially when it's the only book which Amazon classify as both Logic and Occult.

I found a couple of interesting articles online, here and here. (Why do so many philosophers look mad?)

There's even a Logical Pluralism weblog! Anyway, dialetheism (in various forms) has a long history:

"In ancient Indian logic/metaphysics, there were standardly four possibilities to be considered on any statement at issue: that it is true (only), false (only), neither true nor false, or both. Early Buddhist logic added a fifth possibility: none of these."

Tuesday September 11, 2001
04:59 PM

Losing control

[ #787 ]

It's a time for taking stock. So I'm trying to tidy up the CPAN permutations scene. I've just scheduled Algorithm::PermuteInPlace for deletion: it's a nice module, but it's not worth confusing the CPAN users for.

I've also persuaded Edwin Pratomo to incorporate Algorithm::FastPermute into the latest version of his Algorithm::Permute module. So we'll be back to having just two CPAN permutation modules. (The other is Tom Phoenix's List::Permutor, which is IMHO obviously redundant now.)

I'm sad to have relinquished control of my baby like that, but I think the resulting simplification will be worthwhile. I had a funny email exchange with Edwin while we were talking about combining them. He sent me a mail explaining some benchmarks he'd used, and concluding:

Algorithm::FastPermute: 11 wallclock secs [...]
Algorithm::Permute: 7 wallclock secs [...]
So still, mine is the fastest :-)

I was confused by that, because I'd done a lot of performance tests, and I was sure that FastPermute lived up to its name. So I looked into the benchmark code, and I found a bug which meant that Permute was only running once, but FastPermute was being run five times on the same data. So I'd say that's a pretty good result :-)