Perl 6 for finding non trivial powers less than 2 ^ 20

I recently noticed Terry Jones's blog post, "The eighty six non-trivial powers ≤ 2^20." I was immediately struck by how well this lent itself to being implemented in Perl 6, so I grabbed a handy Rakudo interpreter and translated it rather literally and then played with some slightly more idiomatic approaches. I still think I'm missing something with respect to the main loop, but I like what I came up with. The code is on github in my scripts repo.

In comparing the two (Terry's Python and my Perl), I really felt like this summed up the reason I want to code in Perl 6 more often. I work in Python for work, these days, and while it's a fine language with some very nice tools (django is especially nice), I frequently find myself wishing Rakudo were just a bit more production-ready.

So, without further ado, some thoughts about the two versions...

Code length is ignorable. Sure, the Perl is shorter in some areas and longer in others, but if that's interesting to you in terms of a mathematical problem, then there may be a problem.

However, in terms of clarity, I find two distinguishing features. One is strongly in Perl's favor, and one is mildly in Python's favor:

Pro Perl:

The largest thing I notice is that last block. It's much clearer to me that were'e concatenating the key with the value, after both are transformed in some way.

This reads a bit like, "print the formatted number in the key, followed by an equal followed by the values, joined internally with "^" and externally with commas."

Meanwhile the Python is something like, "print a formatted number, and equal and a formatted string where the number is in n and the formatted string is a comma joining a formatted pair of numbers joined with a "^" where the numbers are a and b where a and b are the tuples in powers indexed by n."

It's not that the code is *longer* that's the problem, but that it's far more disjoint. Even the indentation has to be complicated to suit the way they're mixing infix, functional and postfix grammatical elements.

Pro Python:

The declaration and use of powers is far cleaner in Python due to the handy defaultdict concept. This bypasses the defaulting that we do in Perl:

    (%powers{+$n} //= []).push([$a,$b]);

Beyond being punctuation-heavy, this is exactly the same underlying behavior as the Python. We default the bucket at $n to an empty list and then append the new item. The difference is that in Python the defaulting behavior is taken care of behind the scenes.

I say that this is minor because I understand this to be functionality that Rakudo Perl 6 has simply not implemented yet. You will eventually write:

    my Array %powers;
    ...
    %powers{$n}.push([$a, $b]);

very much like its Python counterpart.

Update: I'm told by the good folks on #perl6 that the right way to push onto a hash entry with a default empty array is:

    %powers.push: $n => [$a, $b];

Which is certainly cleaner than all of the  above, so woot!

Python subprocess vs os.popen overhead

Let's say you're writing a Python program and you want to run an external command and read its output. The right thing to do used to be to:

 import os

 p = os.popen("command")

 output = p.read()

But there were a lot of ways to run programs depending on what kind of output you wanted to read (if any) what kind control you wanted (if any) and so on. Thus was born the subprocess module. In the current, 2.7 documentation for the os module, there's a note on popen:

Deprecated since version 2.6: This function is obsolete. Use the subprocess module. Check especially the Replacing Older Functions with the subprocess Module section.

Well, that's pretty definitive, right? Unfortunately, not so much.

Typically, process creation overhead doesn't matter a great deal. If a program needs to run another program, then the startup time involved in the creation of the process is probably an order of magnitude (often several) less than the time that the new program takes to do its work. So, you only typically care about process creation overhead when you're creating a very large number of parallel children.

Unfortunately, I work in the world of system monitoring, and in that world, creating a few hundred or thousand programs a second during peak times (subordinate monitoring tools) is not a rarity, and even when the load is much lighter, large amounts of process creation overhead isn't always ignorable. For example, if your system is doing a lot of IO, then large memory operations during process creation might reduce the amount of caching the system can do.

All of these factors lead me to test the subprocess module against os for a simple case: I want to run a process under a shell with standard output being captured. With the os module, my test looked like this:

 import os
 for i in range(10000):
    f = os.popen("exit 0")
    f.close()

With the subprocess module, my test looked like this:

 import subprocess
 for i in range(10000):
    f = subprocess.Popen("exit 0", shell=True)
    f.wait()

I timed the two scripts and came to a surprising conclusion: subprocess has about a 40% process creation overhead over os.popen! That's an awful lot of increase, so what could be going on? My next step was to use strace to determine what could be taking up that extra time. Here's a partial strace fo the subprocess example under Linux:

pipe([3, 4])                            = 0
fcntl(4, F_GETFD)                       = 0
fcntl(4, F_SETFD, FD_CLOEXEC)           = 0
clone(...) = 3306
close(4)                                = 0
mmap(NULL, 1052672, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f358acc6000
read(3, "", 1048576)                    = 0
mremap(0x7f358acc6000, 1052672, 4096, MREMAP_MAYMOVE) = 0x7f358acc6000
close(3)                                = 0
munmap(0x7f358acc6000, 4096)            = 0
wait4(3306, [{WIFEXITED(s) && WEXITSTATUS(s) == 0}], 0, NULL) = 3306

The os.popen example had one less fcntl and an extra fstat, both of which are fairly light weight. The real culprit here are the mmap, mremap and munmap calls that subprocess is doing. Why are those there, I wondered. In looking at the subprocess code, it seems that these operations may be the result of thread creation which subprocess uses to manage reads and writes on subprocess inputs and outputs, but I'm not sure. What is clear is that the subprocess module is about 1,300 lines long while popen was a builtin supplied by the interpreter.

Conclusion

subprocess is a valiant attempt to make a complex snarl of library calls into a uniform tool. The problem is that process creation is one of the most fundamental operations that a language performs, and when a simple task like running an child process and reading its output becomes too heavy, a language suffers for it. Perhaps subprocess should be simplified and its convenience routines re-written as low-level operations that are optimized per-platform. Or perhaps os.popen should be undeprecated. After all, I'm willing to bet that managing fork, pipe and exec operations from Python will never be as low-impact as calling the C library popen(3) function.

Perl 6, Python, hyperoperators and list comprehensions

I use Python every day at work, and I do like the language. There are things about it that annoy me, but I don't think that's ever not been true of any language I've used. One of Python's best features is its list comprehensions. These short snippets of code can embody so much work that it often feels like Python is writing your code for you.

At night, I go home and work on Perl 6, the upcoming update to the decades-old programming language which adds features from nearly every programming language you've ever heard of (and some you haven't). The direct equivalent of the list comprehension in Perl 6 is the same as it was in Perl 5: map. Here's how you use map in Perl 6:

 map {$_ + 10}, (1,2,3,4)

This yields the same list as the Python:

 [ x + 10 for x in 1,2,3,4 ]

Ah, but the astute among you are noticing that the Perl uses a variable name that's always the same, thus making nested map statements painful due to the need to create temporary variable names manually. In Perl 5, this was true, but we can name those temporaries quite easily now:

 map { $^x + 10 }, (1,2,3,4)

Perl sees these temporaries from left to right and considers them positional parameters in the order that they appear to the current block (which is also a closure).

But Perl 6 gives us something more than map. In fact, map will be used much less frequently in Perl 6 because of hyperoperators. A hyperoperator is an operator that takes another operator as a parameter and augments its behavior. In Perl 6, hyperoperators can do this:

 (1,2,3,4) <<+>> 10


or the Unicode equivalent:


 (1,2,3,4) «+» 10

This takes the + operator and makes it work on the list given on the right side, adding the value on the left to each item and returning the newly created list of results. So, we never need to create a closure in order to ask Perl to do some particular binary operation on all elements of a list. Instead, we just pass the list, the operator and the right hand side to a hyperoperator and it does all the heavy lifting. We don't even need to see the temporary variable that's being used.

List comprehensions like Python's [ ... for ... ] and Perl's map are extremely valuable things for doing complex operations, but when what you really want is just to perform a simple operation on the elements of a list, hyperoperators give you what you need without the trappings you don't care about.

Note: There are actually multiple forms of hyperoperator depending on how "DWIMy" (Do What I Mean) you want it to be and on which of its arguments. See Synopsis 3's section on Hyperoperators for more.

5 things you can do with Lists in Perl 6, Python and Ruby

I think practical examples of doing the same sorts of tasks in different programming languages can be wonderful tools. Recently, an IT student in Poland named Konrad posted a followup on his blog to the 2007 Ruby blog, "5 things you can do with a Ruby array in one line (PLUS A FREE BONUS!!)" by drewolson. He updated this for Python. Of course, having worked with Perl 6 quite a lot recently (see my Google Buzz posts titled "Your daily dose of Perl 6"), I was compelled to do the same for that language. See below for the results. Notice that Konrad chose temporary variable names that were much shorter than drewolson's, so the visual comparison between Ruby and Pyhthon in terms of code size is somewhat unfair, but I'll go with the original names where I need temporaries, just to be fair to Ruby.

Summing elements


Here, the original Ruby example printed the result, but I've trimmed that out for consistency with the rest of the examples.


Ruby:

  my_array.inject(0){|sum,item| sum + item}

Python:

  sum(my_list)

Perl 6:

  [+] @my_array

Double every item

Ruby:

  my_array.map{|item| item*2 }

Python:

  [2 * x for x in my_list]

Perl 6:

  @my_array <<*>> 2

Finding all items that meet your criteria (such as being divisible by 3)

Ruby:

  my_array.find_all{|item| item % 3 == 0 }

Python:

  [x for x in my_list if x % 3 == 0]

Perl 6:

  grep {$^item %% 3}, @my_array

  # or...

  grep * %% 3, @my_array

Combine techniques

Ruby:

  my_array.find_all{|item| item % 3 == 0 }.inject(0){|sum,item| sum + item }

Python:

  sum(x for x in my_list if x % 3 == 0)

Perl 6:

  [+] grep * %% 3, @my_array

Sorting

For more information on how Perl 6 sorting works and what the *-autoclosure syntax that I've used above does, see carl's excellent Perl 6 Advent Calendar post.


Ruby:

  my_array.sort
  my_array.sort_by{|item| item*-1}

Python:

  sorted(my_list)
  sorted(my_list, reverse=True)

Perl 6:

  @my_array.sort;
  @my_array.sort: -*;

And there you have it. Enjoy the many choices you have in programming languages!

Python class attribute annoyance

Python class attributes are fairly handy things, if somewhat visually misleading. Coming from other languages, you might expect this:

  class Foo(object):

    a = 10

To define a class whose instances will have one attribute called a. Not quite. a is actually what most languages call a "static attribute" or "static member" of the class itself, not the instances. Python calls these "class attributes." Once you know this, class attributes are a tool you'll reach for in a number of circumstances, but they have subtle behaviors that can feel like bugs.

For example, today I was trying to do something like this:

  class Foo(object):

    a = 10

    b = a + 5

which works just fine and does what you might expect (a is 10 and b is 15). But, this will yield an error:

  class Foo(object):

    a = 10

    b = [ a+i for i in range(1,11) ]

You might expect b to contain [ 11, 12, ..., 20 ] but instead, you get an error telling you that a isn't defined. [Note: tested in Python 2.6 and 3.1] This subtle flaw exists because that a+i is actually being executed in a nested lexical scope, but because it was created inside of a class body, it fails to inherit what appears to be the parent scope and thus has no access to its lexically scoped variables. There are many ways to accomplish what you might have intended, here, but none of them are very clean. For example:

  class Foo(object):

    a = 10

    b = [ z+i for z in (a,) for i in range(1,11) ]

Now you are passing a as a parameter to that nested scope, so it works perfectly. It's certainly a stilted way to do this, but it works just fine.
Coming, as I do, from Perl, this feels very odd. Perl's OO model is, at best, a framework upon which to build your own. Even still, this kind of scoping problem just never happens. Any lexical scope introduced anywhere in Perl will have a parent scope which is visually quite obvious. Running into such subtle shifts in Python's behavior seems counter to its stated goal of simplicity and elegance.

Perl and Python documentation or Pydoc considered harmful

If you've read my programming posts before you know that I've transitioned from being mostly a Perl programmer to mostly a Python programmer (and from C to Perl before that). For the most part, this has been a painless transition. Python tends to take itself too seriously (which leaves me thinking: odd choice of name), but other than that it's a good language. Perl has its strengths, to be sure, but so does Python. One area, however, that causes me no end of frustration is reading Python module and program documentation. Coming from Perl, as I do, I'm used to flowing, descriptive documentation, the crafting of which is as much a part of the authoring of a piece of public code as the source.

In the Python world, it's another story. There are projects with excellent documentation like django, but I've never seen one that used the built-in documentation system in Python that was worth the time it took to create. (more...)

Python: Adopting Perl's given and Smart Matching

Python doesn't have a switch statement. This makes it relatively unusual among modern languages, but it's not terribly shocking. It has never been entirely clear what the useful equivalent of C's very efficient and elegant switch should be in high-level languages. However, one useful signpost is Perl's late addition: given.

In Perl 5 (released around the dawn of Python) there was no switch equivalent. Many of the same hacks that are used in Python to work around this were suggested to Perl users. However, when crafting a spec for Perl 6, a switch statement was high on the list of user requests, so "given" was introduced. Later, as Perl 6 prototype implementation features were scrutinized for back-porting to Perl 5, given was selected as a useful bit of low-hanging fruit that didn't require massive changes to the language. In Perl 5.10, the given statement is now available with the use of a special pragma. Presumably, this pragma will be removed in future versions.

So, back to Python. Is given the right way to go? Perhaps. Given assumes a lower-level tool called smart-matching, and Python currently has no such mechanism. The introduction of smart-matching has the potential to be disruptive to the language if done poorly. Great care should therefore be taken, but a minimal approach should be acceptable.

(read on for the proposal...)

The Python Platform

Update: I believe that the example for this essay on Python as an incompatible platform is incorrect. The bug report that I submitted was updated 3 months later to indicate that I'd read the documentation wrong. I think the core point here is still valid. There's a lot of "not invented here" applied to the UNIX and Linux conventions in Python, but I chose a bad example, and for that I should apologize to the Python community. I like Python. I like programming in Python. I don't want to make it sound like I'm dismissing the language, here, just a particular trope in the community.

When Java came out, I remember the promise that it would be the write-once-run-anywhere language. It was supposed to free programmers from the need to tie their code to a platform, and instead they could simply write it. This never really happened. Instead, what we got was the Java (or more accurately the JVM) platform. It wasn't really a great platform as these things go, and for a short time that confused me. I wasn't sure why the smart people at Sun would be unable to create a decent platform on which to write generic code.

Then it came to me... It was Windows. You see, Sun had a pretty decent little operating system called Solaris (né SunOS), but Java was supposed to work everywhere, so at a minimum, it would have to accommodate the world's most popular desktop platform at the time (and still, though it has less market share now): Microsoft Windows. Windows has its own ideas about how a system should manage users, permissions, networking and a host of other things that programs want to interact with, so Java couldn't allow the same code to run everywhere while exposing the powerful semantics of the Solaris operating system. More broadly, it couldn't expose those core Solaris semantics that came from its Unix heritage, embodied in the POSIX standards. These standards are what make C, C++, Perl and many other language's standard libraries so powerful, and because of that power they are also widely portable. So useful are these standards that they have molded operating system after operating system, all based to some extent on Unix. Today this includes Linux, MacOS and a plethora of lesser-known systems, all of which have important niches in various industries such as HP/UX and AIX.

So, in the late 90s a new language started to gain popularity: Python. It didn't fall for Java's trap entirely. It was mostly in league with the POSIX way of thinking. Process management, file IO and many other aspects of the language were all very reminiscent of POSIX. However, Python suffered from a new problem: it was the anti-Perl. Perl, you see, is a programming language that became very popular in the early 90s, and Guido van Rossum, Python's original author made his feelings about Perl fairly clear early on. He wasn't fond of it, and Python was going to avoid its mistakes.

While correcting the perceived mistakes of another language might seem a noble goal, it has several pitfalls which must be avoided. One of the most obvious of these is avoiding something only because the original language embraces it. Python has had a rocky relationship with POSIX for just this reason. You see, Perl is a deeply POSIX-based, and even more specifically, Unix-based language. Python, as I said, is mostly a POSIX-friendly language as well, but there's a silent mistrust within the community of the platform that Python's nemesis language so readily embraces, and this has lead to a number of almost-entirely-POSIX-friendly choices which, when seen as a whole, yield the Python Platform.

This platform is not entirely POSIX-compatible, which means that users of Python and Python programs on both POSIX and Windows systems must adapt to it, in the same way (but to a lesser extent) that they must adapt to Java's platform.

OK, so that's the generalities, but what about specifics? One must look no further for a simple example than the Python standard library's command-line processing module, optparse. This module has a simple documentation bug, but that bug illuminates the Python Platform in stark detail. Here's an excerpt:

"... the traditional Unix syntax is a hyphen (“-“) followed by a single letter [...] Some other option syntaxes that the world has seen include: a hyphen followed by a few letters, e.g. "-pf" [...] These option syntaxes are not supported by optparse, and they never will be. This is deliberate: the first three are non-standard on any environment[...]"

This sounds reasonable, after all, why support oddball features? Well, it turns out they're not so oddball. The POSIX standard says that the compliant program "accepts any of the following as equivalent: 'cmd -ao arg path path', 'cmd -a -o arg path path' ..." notice that traditional Unix and POSIX programs such as the "ls" command will always accept these concatenated arguments. So why would Python tell us that this is non-standard on any environment? That goes back to the mistrust that Python has for POSIX. There's no compliance testing for the Python library's POSIX support because Python isn't a POSIX language. It's a Python language.

I decided to take the cautious approach here. I didn't want set anyone off, so when I submitted the following alternate wording to the Python folks:

"optparse has chosen to implement a subset of the GNU coding standard's command line interface guidelines, allowing for both long and short options, but not the POSIX-style concatenation of short options."

... I kept it simple and factual. I didn't attempt to suggest a rationale, and I made it clear that I wasn't asking for Python's behavior to change, just the documentation. This bug report sat for three months and then was silently lowered in priority, even though it required nothing more than a cut-and-paste documentation change.

This is but one example of where Python chooses to go its own way, eschewing the wisdom of a platform that has suited the likes of Sun, Apple, HP, IBM and countless FOSS developers for decades now. I like Python. I think it's a great language for certain types of tasks. I'm also a fan of its nemesis, Perl, along with a host of other languages I've used over the years, but time and time again, I see the Python community embrace a culture of exclusion and "not invented here." For Python to truly reach the potential that I'm sure it has, it will have to be able to embrace the tools that have worked well and only discard features which have been carefully considered and understood.

There's hope, though, that this will be the case. Guido's distaste for Perl and some other Unix tools like it may have fueled this fire, but it turns out he's a very reasonable person for the most part. In a recent blog post, he says, "It's no wonder that users are switching to the web as the platform for everything that used to live on the desktop -- with all its flaws (which I will discuss another time), web development still feels like a breeze compared to Windows development." I take this as a sign that he understands the power of a platform which works with consistency at all levels, and that he will continue to improve the Python Platform so that it builds synergy with the POSIX platform, and doesn't fight against it as if it were an opponent to be conquered.

The Power of Perl's Data::Dumper

Update: sorry about the code formatting. I don't appear to be able to get Blogger to play ball with me right now. Use your imagination, especially with respect to the python examples which simply won't work with the indentation shown.

I've been doing a fair amount of work in Python recently, and there are some things I really like about the language. However, being an old Perl programmer, I find myself desperately wanting a few features of Perl in Python, and one of them is Data::Dumper. This module lets you print out the contents of a variable as Perl code. Now, Python has some similar features such as pprint and pickle, but neither of them quite gives you what Data::Dumper does.

For example, here's a class definition:

  package Someclass;
  sub new {
   my($class, $param1, $param2) = @_;
   return bless { param1=>$param1, param2=>$param2 }, $class;
  }

When we dump out an instance of this class, we get:

  $VAR1 = bless( {
          'param2' => 2,
          'param1' => 1
        }, 'Someclass' );

This is exactly the code you need in order to re-create the object (which you get from pickle), but it's a human-readable copy of all of the state contained within the object at the same time.

In Python, you might write:

  class Someclass(object):
     def __init__(self,param1,param2):
       self.param1=param1
       self.param2=param2

But the pprint output just calls repr and you get:

  <__main__.someclass>

This is because Python relies on each object to provide its own serialization method, called __repr__. If you don't define it (and sadly, many don't define anything useful, here), there's no way to know just what it is that's going on under the hood other than by writing your own introspection code. You could, for example, treat the object as a dict and peruse its attributes:

 >>> pprint.pprint(x.__dict__)
  {'param1': 1, 'param2': 2}

but there are limitations to such an approach, especially when it comes to encapsulation.

Anyway, the point is, this is one area in which Lisp, Perl and other languages that can represent arbitrary data as code have an ease-of-use advantage over languages that cannot. Hopefully this is being addressed in future versions of the language (I'm not using 3.x yet).

Perl 6: Why So Long?

Over the years, many people have asked me when Perl 6 is going to happen. Now, I've only been peripherally involved, and I don't think I can speak for any of the current developers, but here's my take. First off, comparing development times of Perl 6 to, say, Python 3 (ne Python 3000) is entirely spurious. Python and Perl 5 relate to Perl 6 in roughly the way that classic Lisp 1.5 relates to Common Lisp. That is to say, Python and Python 3 are essentially the same language and exist at essentially the same order of complexity. In fact, they exist at about the same order of complexity as Perl 5, Ruby, PHP and many other high level languages.

Perl 6, meanwhile, is a massively ambitious effort that aims to meld the best features of nearly every style of language design into a single language. This means that the language must be able to represent programs as data (in order to implement true macros); it must provide a meta-object protocol (in order to support Ruby-style mixins and Smalltalk-style traits); it must implement function overloading (C++-style calling) and multi-method dispatch (CLOS-style methods) while also providing interface contracts (like Java) and generics (C++ at the low-level, Haskell at the high level); and it should provide native threading and parallel execution (ala Fortress). Now, take a language that has all of these features, and yet still manages to be familiar to a C-derived language programmer and also allow programs full access to the definition of the language at run-time in order to support multiple Common Lisp style domain-specific languages within a single program. To my knowledge no other language has ever taken on all of these goals and managed to get very far.

OK, so that's the excuse. What's the reality? Hmm... I'd say that Perl 6 is probably closing in on its .0 release within the next 2-3 years. Realistically, it probably would have taken a team of dedicated programmers who knew the finer points of self-hosted language design a couple of years to accomplish the Perl 6 design and implementation, given a clear idea of what they wanted from the onset. Perhaps a bit longer, but not much. As it was, many of the Perl developers have other things to do and Larry had some time that he wasn't able to do much for personal reasons in the middle of the whole thing. All of that combined with the fact that the Perl community was never entirely sure what the end-goal would be, and much of the design process has been a journey of discovery and... well, 10-12 years isn't a surprising number.

These days, there's an STD that describes the grammar and a fairly solid set of specs. That's a big improvement. There's also a virtual machine for running the language that's reached 1.0 status and deployed what can arguably be called the most advanced compiler-writing toolkit ever written. Again, a huge leg up.

That in turn has enabled the creation of a new prototype of the language that uses said virtual machine, taking a large portion of the burden of implementation off of the Perl 6 team, and the result has been a flood of development on the prototype, which has overtaken that of previous efforts in only a little over a year.

In the end, if you thought that Perl 6 was going to be Perl 5 with a few changes, you're in for a shock. If you thought that Perl 6 was basically a dead project because it has taken almost 10 years so far, then you're not aware of the history of such language design (the Common Lisp design and implementation process took nearly as long with DARPA and many commercial Lisp organizations backing it).

As we enter the final stretch and Perl 6 begins to become a platform upon which real work can be done, I just wanted to remind everyone that, while simpler languages (and I mean that in a non-pejorative way) rise and fall, there are some things that are worth waiting for.