robin's Journal robin's use Perl Journal en-us use Perl; is Copyright 1998-2006, Chris Nandor. Stories, comments, journals, and other submissions posted on use Perl; are Copyright their respective owners. 2012-01-25T02:09:46+00:00 pudge Technology hourly 1 1970-01-01T00:00+00:00 robin's Journal Does everything come back to Perl? This morning I got the <a href="">'Pataphysics CD</a> in the post, from the <a href="">Sonic Arts Network</a>. There's some good stuff on there, including some of Luc Etienne's phonetic palindromes, and Nigey Lennon's strange homage to Alfred Jarry, <i>The Man with the Axe</i>. <p> Idly <a href="">googling for <b>merdre</b> </a>, what should I see on the first page of results but <a href="">this</a>. Though, on reflection, maybe it's not so strange after all. Perl is surely one of the more 'pataphysical programming languages.</p> robin 2006-01-16T11:46:29+00:00 journal Hacking on Want It's been a while since I've done any serious hacking on anything Perl-related. Yesterday I woke up to a message from Damian Conway, reporting a subtle bug in my Want module. I haven't been very good at responding to bug reports of late (most of them are EBKAC or known bugs), but I think Damian has earnt the right to be taken seriously. <p> It took me most of the day to track down the bug and fix it, but it was an interesting journey. What he found is that, if you call want() from (a sub that's called from) within the guard of a loop, it crashes the second time through. </p><p> It turns out that this happened because of a subtle design flaw in Want. Perl doesn't really have any proper introspection capabilities, so modules like Want have to be cunning and take advantage of data that's around for other reasons. To decide what context a sub is called in, Want locates the part of the optree where the sub is called, and then trawls it to find the essence of the expression the sub call is in. (For example <tt>foo() + 2</tt> means <tt>foo</tt> is called in numeric context, whereas <tt>foo() &amp;&amp; 2</tt> means it's called in boolean context. </p><p> There's no easy way (that I know of) to find the right part of the optree, but there are various bits of information around that give enough of a clue. The activation record for a sub records the last statement that was executed before the sub call, and the address the sub should return to. So I walk the optree, starting at the last statement, until I find the return address; then I know where the sub must have been called from. </p><p> The second time through a loop, however, it can happen that the last statement executed is <b>after</b> the return point, so it keeps walking and walking but never finds what it's looking for. </p><p> It took me a while to see how to fix it, but in the end I found a way. It so happens that loops, as well as subroutines, leave an activation record on the context stack, so the new code does this: after it's found the activation record for the sub, it keeps looking up the stack to see if there's a loop around the sub call. If there is, the optree walk starts at the beginning of the loop instead. That seems to fix it. </p><p> I'm just waiting for Damian to give the all clear before I release the new version.</p> robin 2005-06-30T23:48:39+00:00 journal You know you're starting to think in O'Caml when... You write Perl code like this:<blockquote><div><p> <tt>sub gron {<br>&nbsp; my ($f, $total, $width) = @_;<br>&nbsp; my $veet;<br>&nbsp; $veet = sub {<br>&nbsp; &nbsp; my ($partial, $subtotal, $n) = @_;<br>&nbsp; &nbsp; my $rem = $total - $subtotal;<br>&nbsp; &nbsp; if ($n+1 == $width) {<br>&nbsp; &nbsp; &nbsp; $f-&gt;($rem, @$partial);<br>&nbsp; &nbsp; }<br>&nbsp; &nbsp; else {<br>&nbsp; &nbsp; &nbsp; $veet-&gt;([$_, @$partial], $subtotal+$_, $n+1) for 0..$rem;<br>&nbsp; &nbsp; }<br>&nbsp; };<br>&nbsp; $veet-&gt;([], 0, 0);<br>}<br> <br>gron(sub {print($_ ? $_ : " ") for @_; print "\n"}, 3, 27);</tt></p></div> </blockquote><p>I'm fairly sure that the idea of using a recursive closure in Perl has never crossed my mind before. Notice the disguised conses as well<nobr> <wbr></nobr>:-)</p> robin 2002-05-25T14:57:14+00:00 journal Source filtering, the O'Caml way Recently I've been playing with <a href="">O'Caml</a>, which is a charming language.<p> It has a source filtering mechanism called <a href="">camlp4</a>. At the heart of it is an extensible replacement parser, which makes it almost trivial to change or extend the language. One of the <a href="">examples in the manual</a> adds a new loop construct in six lines of code.</p><p> Of course, camlp4 itself is written not in ordinary O'Caml but in the <a href="">"revised"</a> (formerly "righteous") syntax invented by the author of camlp4.</p><p> It's interesting that several of the "big" changes planned for Perl 6 are already features of O'Caml: extensible syntax, currying, stable multithreading.</p><p> Oh, and it's (conceivably) <a href="">faster than C++</a>.</p> robin 2002-05-23T14:50:01+00:00 journal More recursion I've rewritten my <a href="">recursive regex</a> implementation, and I think it actually works properly at last.<p> I have started wondering about the feasibility of replacing perl's regex engine with PCRE. The regex engine is supposedly pluggable already, but it looks as though plugging in a completely different regex engine would still be non-trivial. Any thoughts?</p> robin 2002-04-20T12:52:56+00:00 journal OS X filename oddity Filenames in Darwin are UTF-8, so I wondered what would happen if you use a nonsensical sequence. It seems that you can make <i>weird disappearing files</i>, which show up in the Finder when you first open the folder they're in, and then quickly disappear. Sometimes they don't actually disappear until you try and click on them, which is tantalising. <p> If you have an OS X machine try this: <code>perl -e 'mkdir("foo\xED\xA0\x80bar") or die $!'</code></p> robin 2002-04-12T15:18:50+00:00 journal Ccard There is a <a href="">card game</a> based on category theory. robin 2002-04-12T12:18:38+00:00 journal Other Cam(e)l book? Apparently O'Reilly is bringing out a book on <a href="">OCaml</a>. I wonder what animal they'll use for the cover... robin 2002-04-09T18:32:36+00:00 journal More regex [<b>Note: </b>There is a full account of my recursive regex idea in <a href="">this article</a>.] <p>I've found the bug in my PCRE patch, which is partly to do with the way <tt>*</tt> repetitions are handled. But you don't actually need to use iterative repetitions any more, because you can replace iteration with recursion!<nobr> <wbr></nobr><tt>/a*/</tt> can be rewritten as<nobr> <wbr></nobr><tt>/((a(?1))?)/</tt>. And if you do that, you sometimes avoid triggering the bug. So you can test for matching XML-style tags like this:</p><blockquote><div><p> <tt>&amp;#163;^(&lt;\w+/&gt;|&lt;(\w+)&gt;([^&lt;&gt;]|(?1)|)(?3)&lt;/\2&gt;)$&amp;#163;</tt></p></div> </blockquote><p>I'll fix the bug soon... </p><p> I've also managed to prove that all context-free languages can indeed be expressed. The proof takes the form of an algorithm for turning a context-free grammar into a regex: </p><ul> <li> Eliminate left recursion from the grammar. (This is a standard procedure, but quite complicated.)</li> <li> Write the grammar as a system of equations. For example, the grammar <ul> <li> <b>S</b> --&gt; ''</li> <li> <b>S</b> --&gt; '(' <b>T</b> ')' <b>S</b></li> <li> <b>T</b> --&gt; <b>S</b></li> <li> <b>T</b> -&gt; 'x' <b>T</b></li> </ul><p> becomes </p><ul> <li> <b>S</b> = '' + '(' <b>T</b> ')' <b>S</b></li> <li> <b>T</b> = <b>S</b> + 'x' <b>T</b></li> </ul></li> <li>Now work out the least solution for <b>S</b> in terms of a least fixpoint operator &#181;. In our example that is <ul> <li> &#181;S. ('' + '(' &#181;T.(S+'x'T) ')' S )</li></ul></li> <li>And translate the &#181;-expression into a regex:<blockquote><div><p><nobr> <wbr></nobr><tt>/(|\(((?1)|x(?2))\)(?1))/</tt></p></div> </blockquote></li> <li>(That regex doesn't actually work yet, because of various bugs. But it ought to.)</li> </ul><p> Of course, the interesting part is proving that the algorithm really works. I plan to write it up in more detail soon.</p> robin 2002-04-09T13:59:38+00:00 journal Regex power! I've been hacking on <a href="">PCRE</a>. I love coding in C, it's so clean and crisp and <i>quick</i>. <p> I've added an <a href="">interesting extension</a> to the syntax. Would this be a good idea for Perl? </p><p><nobr> <wbr></nobr><tt>/^\W*(?:((.)\W*(?1)\W*\2|)|((.)\W*(?3)\W*\4|\W*.\W*))\W*$/i</tt></p> robin 2002-04-01T22:01:09+00:00 journal Moving 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 <i>possessions</i> were the other side of London. So it's a <b>huge</b> 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 <a href="">photographed</a> the <a href="">result</a>. <p> There was one problem - there's no phone socket <i>anywhere</i> near my desk, and no extension cord long enough to reach the nearest one. But fortunately the phone line actually enters the flat <i>right</i> here, so I just <a href="">wired</a> the modem directly into the junction box. I expect that's hopelessly illegal, but it seems to be working fine. </p><p> From the repetitive-sounding module news department, I've released yet another new version of PadWalker (<a href="">0.08</a>) 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 <a href="">debugger patch</a> which relies on this new version.</p> robin 2002-03-19T21:54:43+00:00 journal Bits and bobs New version of <a href="">PadWalker</a>, 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... <p> <a href="">This</a> 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 <i>still</i> very funny. </p><p> 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.</p> robin 2002-03-14T20:48:37+00:00 journal 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 <a href="">crab</a> and cross the desert <a href="">by camel</a>.<p> I've been busy this week, and have just released new versions of <a href="">Algorithm::FastPermute</a> (more portable) and <a href="">PadWalker</a> (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 <i>actually work</i> now, and get into 5.8 before it's too late.</p><p> Otherwise, I'm mainly learning <a href="">category theory</a>. 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 "<i>A comathematician is a system for turning theorems into coffee</i>".</p> robin 2002-03-07T11:07:03+00:00 journal Update 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 <a href="">dorkbotlondon</a> about the elephants. A <a href="">triumph</a><nobr> <wbr></nobr>;-)<p> 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 <a href="">logic course</a> 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 <a href="">rains a lot</a>. (For a while I was planning to apply to <a href="">MIT</a>, 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.) </p><p> I also became a <a href="">Perl monk</a> 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 <a href=";lastnode_id=9066">gems</a>)</p><p> Connecting Perl and theory, I've become fascinated by regular expressions which allow back referencing (like<nobr> <wbr></nobr><tt>/^(.*)\1$/</tt>). 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: </p><ul> <li> The problem of deciding whether a regex [1] matches a string is NP-complete.</li> <li> If you have a regex <tt>$r</tt>, there isn't necessarily a regex which matches all and only the strings which <tt>$r</tt> <em>doesn't</em> match [2].</li> <li> The deeper you allow capturing expressions to be nested, the more languages can be expressed.</li> <li> Not all context-free languages are expressible using regexes, and not all regex-expressible languages are context-free.</li> </ul><p> (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 <tt>(?:$foo)*</tt> or another capture <tt>($bar)</tt>) 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 <em>are</em> interested in! (The <a href="">puzzle</a> 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. </p><p> 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... </p><p> <em>footnotes:</em> </p><p> [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. </p><p> [2] Note that if you allow the negative look-ahead operator, this obviously stops being true. However <em>much</em> weirder things start to happen then, and I don't want to go there for the moment. </p> robin 2002-01-22T00:51:04+00:00 journal Pretty pictures <p>Well now, seekers, do you remember the pretty combinatorial graphs I was playing with a few weeks ago? I only showed you <a href="">one of them</a> before, which I call <i>the elephant</i> because it looks like an elephant seen from the underneath.</p><p>The other one is <a href="">here</a> (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.</p><p>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</p><ul> <li>starts at one of your chosen vertices</li> <li>ends at the other one</li> <li>always follows the printed lines</li> <li>goes through <b>every</b> other vertex</li> </ul><p>It's good fun, the results are pretty, it can be <i>suprisingly</i> difficult, and there's even a serious point to it.</p><p>[[ 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, <i>any</i> 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 <b>or more</b> elements, and that's the central result of <a href="">Maurice Tchuente's paper</a>. ]]</p> robin 2001-10-13T14:30:40+00:00 journal Put your best foot forward! <p>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 <i>equal</i> to that of the right; in which case the subject fails to denote, and we're in <i>real</i> trouble.</p><p>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:</p><blockquote><div><p>"At least one of your feet is such that the other is not better than it. Put forward such a foot!"</p></div></blockquote><p>Be sure to agree in advance which quality metric you're using.</p> robin 2001-10-06T15:17:31+00:00 journal Want for Win32 <p>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 <a href="">here</a> into the same directory, and do <tt>ppm install Want-0.05.ppd</tt>. Many thanks to Daniel Berger for going to a lot of trouble to get this built. If you try it, <a href="">let me know</a> how it goes.</p><p>Now Windows users can participate in the context revolution too.</p><p>Daniel also pointed out that Want will fail if you try to use it from a subroutine which implements an overloaded operator. (People <i>will</i> 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 <a href=""></a> 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 <i>just</i> work."</p> robin 2001-10-06T13:25:44+00:00 journal Extended regular expressions <p>I've been thinking a lot about regular expressions recently, and so I was grateful to find Exploding Dog's reminder of <a href="">the futility of turning to extended regular expressions for solace in a time of crisis</a>.</p> robin 2001-10-06T13:03:59+00:00 journal Speak truly by contradicting yourself <p>One consolation of the dull job I'm doing at the moment is that it's within easy walking distance of my <a href="">favourite London bookshop</a>. Last week I managed to escape there at lunchtime, and spent a happy half-hour browsing the shelves. Glancing through a (very good) <a href="">book on paradoxes</a>, I was startled by a section towards the end describing an account of truth on which <i>contradictions can be <b>true</b> </i>, called <a href="">dialetheism</a>. It's a shame that the supposedly definitive <a href="">book on the subject</a> is so prohibitively priced, especially when it's the only book which Amazon classify as both <b>Logic</b> and <b>Occult</b>.</p><p>I found a couple of interesting articles online, <a href="">here</a> and <a href="">here</a>. (Why do so many philosophers <a href="">look mad</a>?)</p><p>There's even a <a href="">Logical Pluralism weblog</a>! Anyway, dialetheism (in various forms) has a long history:</p><blockquote><div><p>"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 <i>both</i>. Early Buddhist logic added a fifth possibility: none of these."</p></div></blockquote> robin 2001-10-06T12:47:25+00:00 journal Losing control <p> <b>It's a time for taking stock.</b> So I'm trying to tidy up the CPAN permutations scene. I've just scheduled <tt>Algorithm::PermuteInPlace</tt> for deletion: it's a nice module, but it's not worth confusing the CPAN users for.</p><p>I've also persuaded Edwin Pratomo to incorporate <a href="">Algorithm::FastPermute</a> into the latest version of his <a href="">Algorithm::Permute</a> module. So we'll be back to having just two CPAN permutation modules. (The other is Tom Phoenix's <a href="">List::Permutor</a>, which is IMHO obviously redundant now.)</p><p>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:</p><p> <tt>Algorithm::FastPermute: 11 wallclock secs [...]<br> Algorithm::Permute: 7 wallclock secs [...]<br> [...]<br> So still, mine is the fastest<nobr> <wbr></nobr>:-)</tt> </p><p>I was confused by that, because I'd done a lot of performance tests, and I was <i>sure</i> that <tt>FastPermute</tt> 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<nobr> <wbr></nobr>:-)</p> robin 2001-09-11T21:59:40+00:00 journal ... <p>This is starting to sound repetitive, isn't it. Ah well - if I'd been keeping a Perl journal a few months ago, every entry would have been about <tt>B::Deparse</tt><nobr> <wbr></nobr>:-)</p><p>Graham Barr pointed out that there's a flag you can set which instructs <tt>eval</tt> to catch its <i>own</i> errors, so that you don't have to. So I've <a href="">changed A::FP</a> to use that, instead. And I've <a href="">uploaded it to the CPAN</a>. I'm a bit nervous that I still haven't managed to get in touch with Matt Day: if you know how to get hold of him, please <a href="">let me know</a>.</p> robin 2001-09-01T13:14:24+00:00 journal Want 0.05 <p>In Perl 5.6.1 and later, there are some quite strict compile-time checks on the return value from an lvalue subroutine. Because the checks are done at compile-time, it doesn't matter if you <i>know</i> at run-time that you're going to be in lvalue context.</p><p>So code like:</p><p> <tt>sub foo<nobr> <wbr></nobr>:lvalue {<br> &nbsp;&nbsp;if (want('RVALUE')) {<br> &nbsp;&nbsp;&nbsp;&nbsp;return 23;<br> &nbsp;&nbsp;} else {<br> &nbsp;&nbsp;&nbsp;&nbsp;$foo;<br> &nbsp;&nbsp;}<br> } </tt> </p><p>won't even compile. The <a href="">new version of Want</a> adds a function <tt>rreturn</tt> which you can use for an rvalue return from an lvalue sub. So the above can be written as:</p><p> <tt>sub foo<nobr> <wbr></nobr>:lvalue {<br> &nbsp;&nbsp;if (want('RVALUE')) {<br> &nbsp;&nbsp;&nbsp;&nbsp;rreturn 23;<br> &nbsp;&nbsp;} else {<br> &nbsp;&nbsp;&nbsp;&nbsp;$foo;<br> &nbsp;&nbsp;}<br> &nbsp;&nbsp;return;<br> }<br> </tt> </p><p>The compiler sadly doesn't realise that <tt>rreturn</tt> will actually return from the function, so you have to put the bare <tt>return;</tt> at the end to shut it up. But you can think of that like the <tt>1;</tt> that you have to put at the end of a module: meaningless furniture that has to be there.</p><p>Actually, the check is obviously too strict, because something like:</p><p> <tt>sub foo<nobr> <wbr></nobr>:lvalue {<br> &nbsp;&nbsp;if (something_bad()) {<br> &nbsp;&nbsp;&nbsp;&nbsp;die "Something bad happened";<br> &nbsp;&nbsp;} else {<br> &nbsp;&nbsp;&nbsp;&nbsp;$foo;<br> &nbsp;&nbsp;}<br> }<br> </tt> </p><p>ought to be okay. But in Perl 5.6.1 it won't compile. <tt>Can't modify die in lvalue subroutine return</tt>. <b>I'm not trying to modify it, you brain-damaged compiler!</b></p> robin 2001-08-29T12:33:54+00:00 journal bits &amp; pieces <p>I've produced new versions of both <a href="">Algorithm::PermuteInPlace</a> and <a href="">Algorithm::FastPermute</a>.</p><p>They both had nasty bugs that would cause them to crash, and PermuteInPlace wouldn't work at all on any Perl version less than 5.7. Ah, the joys of the bleeding edge... </p><p>FastPermute uses a callback technique which I essentially stole from the <tt>first</tt> and <tt>reduce</tt> routines in <a href="">List::Util</a>. While I was testing FastPermute I noticed that exception handling doesn't work inside the callback. So code like this: </p><p> <tt>&nbsp; permute { eval {die}; print "Got here!\n" } @array</tt> </p><p>will not continue past the <tt>die</tt>, even though the exception should have been caught. There followed a quick self-taught crash course in perl's exception handling mechanism. It's based around <i>setjmp</i>/<i>longjmp</i>, and like most of Perl's internals is simultaneously ingenious and baroque. When there's an exception, control immediately passes to the exception handler, whose responsibility it then is to continue if appropriate. Anyway after an intense few hours, FastPermute now deals politely and properly with exceptions. (Maybe I should fix up List::Util, now I've worked out how to do it.)</p><p>I'm still not quite sure whether the exception handling code, as it stands, makes FastPermute significantly slower. It now looks possible that it doesn't really; and that my comments in the README are misinformed.</p> robin 2001-08-28T10:16:55+00:00 journal The need for speed <p>I've done it. <a href="">Algorithm::FastPermute</a>.</p><p>It can comfortably print all the permutations of ten elements in less than a minute, on my iBook. So it's almost four times as fast as <a href="">Algorithm::Permute</a>.</p><p>Since it's based on <a href="">Matt Day's code</a>, I should get his permission before releasing it properly. I also wonder if it could be incorporated into <a href="">List::Util</a>. Time to write some email.</p><p> <b>Update:</b> Email to <tt></tt> and <tt></tt> is bouncing. Does anyone have his current email address?</p> robin 2001-08-25T12:23:07+00:00 journal Faster! Faster! <tt># The fastest Perl permutation algorithm I've yet found. It's only 20-30% slower<br># than Algorithm::PermuteInPlace.<br>#<br># Now if we implement _this_ in C, with a Perl callback for processing<br># the permutation, we can probably get even faster than Algorithm::PermuteInPlace.<br># (There are ways to invoke Perl callbacks without the normal subcall overhead.)<br><br># Translated from the C code by Matt Day,<br>#&nbsp; &nbsp; &nbsp;at<br><br>use strict;<br><br>sub permute {<br>&nbsp; &nbsp; my ($aref, $level) = (@_, 0);<br>&nbsp; &nbsp; my ($index, $copy, $printing) = ($level, [@$aref], $level+1 == @$aref);<br>&nbsp; &nbsp; do {<br>&nbsp; &nbsp; &nbsp; &nbsp; if ($printing) {<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; print "@$copy\n";<br>&nbsp; &nbsp; &nbsp; &nbsp; } else {<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; permute($copy, 1+$level);<br>&nbsp; &nbsp; &nbsp; &nbsp; }<br>&nbsp; &nbsp; &nbsp; &nbsp; @$copy[$index-1, $index] = @$copy[$index, $index-1]<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if $index != 0;<br><br>&nbsp; &nbsp; } while $index-- &gt; 0;<br>}<br><br>permute([1..shift]);<br></tt> robin 2001-08-24T18:27:46+00:00 journal Algorithm::PermuteInPlace <p> <a href="">Algorithm::PermuteInPlace 0.01</a> is making its way to the <a href=";query=Algorithm%3A%3APermuteInPlace">CPAN</a>.</p><p>As an experiment, I used <a href="">Inline</a> rather than XS. It's just a proof of concept, but it performs okay - about twice as fast as the Perl version, in my tests.</p><p>My iBook can now print all the permutations of ten elements within 90 seconds.</p> robin 2001-08-24T16:52:34+00:00 journal Permutation benchmarks <p>I took a clutch of permutation routines and used them to print out all 10! permutations of the numbers (1..10). I ran them on my iBook with <tt>time perl &gt;<nobr> <wbr></nobr>/dev/null</tt>. The results are stunning.</p><p> <b>Both</b> of the permutation routines here run faster than <b>any</b> of the alternatives.</p><p>The older pure-Perl algorithms are the slowest. The fastest of them is List::Permutor, at <tt>user 7m35.270s, sys 0m1.670s</tt>. The rest are a <i>lot</i> slower than that. The cookbook code seems to be even slower than the routine from perlfaq4, if the list is long (&gt; 8 elements). </p><p>Algorithm::Permute, with its C implementation, fares rather better. It clocks in at <tt>user 2m59.160s sys 0m0.660s</tt>.</p><p>However, it's pipped by the loopless algorithm immediately below, at <tt>user 2m42.170s sys 0m0.430s</tt>. And the winning place is awarded to the code I posted here last month, which cruises home at <tt>user 2m18.920s sys 0m0.760s</tt>.</p><p>It's surprising that a pure Perl routine can be significantly faster than handcrafted C - a convincing testament to the power of in-place updates. Just wait until I get the same algorithm implemented in C<nobr> <wbr></nobr>;-)</p> robin 2001-08-22T17:43:21+00:00 journal In constant time! <tt># A loop-free implementation of the Johnson-Trotter permutation algorithm.<br># Ehrlich is responsible for the idea[1]. This implementation is mine.<br># [1] Journal of the ACM: 20, 3 (July 1973), 500-513<br>#<br># next_perm runs in constant time, every time. A longer list won't make<br># it slower. Cute trick, but in practice the looping version below seems<br># to be faster.<br>#<br># 2001-08-21<br><br>use strict;<br>my (@array, @p, @a, @d, @u, @c);<br><br>sub init_perm {<br>&nbsp; &nbsp; @array = @_;<br>&nbsp; &nbsp; @p = (0..$#array);&nbsp; &nbsp; # Element key =&gt; position<br>&nbsp; &nbsp; @a = (0..$#array);&nbsp; &nbsp; # Position =&gt; element key<br>&nbsp; &nbsp; @d = (-1) x @array;&nbsp; &nbsp;# Start off going left<br>&nbsp; &nbsp; @c = (0..$#array);&nbsp; &nbsp; # counter for each element<br>&nbsp; &nbsp; @u = (0..$#array);&nbsp; &nbsp; # which element to move when the counter expires<br>&nbsp; &nbsp; print "@array\n";<br>}<br><br>sub next_perm {<br>&nbsp; &nbsp; my ($l, $i) = (0, $u[$#u]);<br>&nbsp; &nbsp; return if $i == 0;<br>&nbsp; &nbsp; $u[$#u] = $#u;<br><br>&nbsp; &nbsp; # Switch the element keyed by $i with the one to the left/right<br>&nbsp; &nbsp; # of it, and update the @p and @a arrays to keep them in sync with @array.<br>&nbsp; &nbsp; my ($x, $y) = ($p[$i], $p[$i]+$d[$i]);<br>&nbsp; &nbsp; $p[$i] += $d[$i]; $p[$a[$p[$i]]] -= $d[$i];<br>&nbsp; &nbsp; @array[$x,$y] = @array[$y,$x];&nbsp; @a[$x,$y] = @a[$y,$x];<br><br>&nbsp; &nbsp; # See if we're at one of the ends<br>&nbsp; &nbsp; if (--$c[$i] == 0) {<br>&nbsp; &nbsp; &nbsp; &nbsp; $c[$i] = $i;<br>&nbsp; &nbsp; &nbsp; &nbsp; $u[$i] = $u[$i-1];<br>&nbsp; &nbsp; &nbsp; &nbsp; $u[$i-1] = $i-1;<br>&nbsp; &nbsp; &nbsp; &nbsp; $d[$i] = -$d[$i];<br>&nbsp; &nbsp; }<br>&nbsp; &nbsp; 1;<br>}<br><br>init_perm(1..shift());<br>print "@array\n" while next_perm();</tt> robin 2001-08-22T17:05:09+00:00 journal Permute! Permute! Custom ops? <p>I've been working on various things recently, mostly not very Perl-related. I found an answer to the permutations problem mentioned below. It's in a twenty-year-old paper written by <a href="">a Cameroonian mathematician</a>, published in <a href="">a Canadian journal</a>, which I found in the <a href="">British Library</a>. On the second page of the paper is exactly the same <a href="">diagram</a> that I'd been using.</p><p>One thing I've realised is that good permutation algorithms are not at all well-known. The algorithm in <a href="">perlfaq4</a> is devastatingly slow, and the <a href=";snode=87">Cookbook entry</a> is only a slight improvement. <a href="">Algorithm::Permute</a> is somewhat better (and written in C), but there's plenty of room for improvement.</p><p>The only way to list permutations <i>really</i> fast is to permute the array in-place, rather than copying the elements each time. Good permutation algorithms are fast enough that the overhead of copying the elements completely swamps the time taken to calculate the permutation. In complexity terms, copying the elements means that your algorithm will <b>never</b> be faster than O(n) to get the next permutation. We can get that down to O(1). And we still only need O(n) space.</p><p>So I'm thinking of writing Algorithm::Permute::InPlace. We should be able to make it <i>scream</i>. But if we write it in C, the overhead of calling the XSUB will still be quite heavy. So I'm toying with the idea of building an interface that will allow C routines to be called directly from the optree by the red-hot op dispatcher. I think that's a lot easier than it sounds. It would be nice to integrate it with Inline too. I hope to have a working proof of concept soon.</p> robin 2001-08-22T12:33:07+00:00 journal clean <p>Back in London - I've had a bath. My tent is drying in the garden. It's sad to have left: the conference was a delight.</p><p>I'm happy to have met two of the great artists who work in the medium of Perl: <a href="">Philippe</a> and Abigail. They both offered future works for sale at the conference auction. So Philippe is going to produce a work for Dave Cross, and Abigail is going to write one for Philippe. That makes me happy. It's just a shame that <a href="">Erudil</a> wasn't there as well<nobr> <wbr></nobr>:-)</p><p>Schwern organised a CPANTS hacking session last night. I only stayed around for a short while before heading into town, but I plan to contribute something B-related to help with gathering code metrics.</p><p>Don't miss <a href=";uid=998">Andy's journal</a>. Love to everybody.</p> robin 2001-08-05T18:20:45+00:00 journal