Posts Tagged ‘Perl’

Number of possible different one line programs

February 22nd, 2012 No comments

Writing one line programs is a popular activity in some programming languages (e.g., awk and Perl). How many different one line programs is it possible to write?

First we need to get some idea of the maximum number of characters that written on one line. Microsoft Windows XP or later has a maximum command line length of 8191 characters, while Windows 2000 and Windows NT 4.0 have a 2047 limit. POSIX requires that _POSIX2_LINE_MAX have a value of at least 2048.

In 2048 characters it is possible to assign values to and use at least once 100 different variables (e.g., a1=2;a2=2.3;....; print a1+a2*a3...). To get a lower bound lets consider the number of different expressions it is possible to write. How many functionally different expressions containing 100 binary operators are there?

If a language has, say, eight binary operators (e.g., +, -, *, /, %, &, |, ^), then it is possible to write 8^100 right 2.03703598*10^90 visually different expressions containing 100 binary operators. Some of these expressions will be mathematically equivalent (adopting the convention of leaving out the operands), e.g., + * can also be written as * + (the appropriate operands will also have the be switched around).

If we just consider expressions created using the commutative operators (i.e., +, *, &, |, ^), then with these five operators it is possible to write 1170671511684728695563295535920396 mathematically different expressions containing 100 operators (assuming the common case that the five operators have different precedence levels, which means the different expressions have a one to one mapping to a rooted tree of height five); this 1.17067*10^33 is a lot smaller than 5^100 right 7.88860905*10^69.

Had the approximately 10^9 computers/smart phones in the world generated expressions at the rate of 10^6 per second since the start of the Universe, 4.336*10^17 seconds ago, then the 4.336*10^32 created so far would be almost half of the total possible.

Once we start including the non-commutative operators such a minus and divide the number of possible combinations really starts to climb and the calculation of the totals is real complicated. Since the Universe is not yet half way through the commutative operators I will leave working this total out for another day.

Update (later in the day)

To get some idea of the huge jump in number of functionally different expressions that occurs when operator ordering is significant, with just the three operators -, / and % is is possible to create 3^100 right 5.15377521*10^47 mathematically different expressions. This is a factor of 10^14 greater than generated by the five operators considered above.

If we consider expressions containing just one instance of the five commutative operators then the number of expressions jumps by another two orders of magnitude to 5*100*3^99. This count will continue to increase for a while as more commutative operators are added and then start to decline; I have not yet worked things through to find the maxima.

Update (April 2012).
Sequence A140606 in the On-Line Encyclopedia of Integer Sequences lists the number of inequivalent expressions involving n operands; whose first few values are: 1, 6, 68, 1170, 27142, 793002, 27914126, 1150212810, 54326011414, 2894532443154, 171800282010062, 11243812043430330, 804596872359480358, 62506696942427106498, 5239819196582605428254, 471480120474696200252970, 45328694990444455796547766, 4637556923393331549190920306

The Met Office ‘climategate’ Perl code

December 25th, 2009 3 comments

In response to the Climategate goings on the UK Meteorological Office has released a subset of its land surface climate station records and some code to process it. The code consists of 397 lines of Perl (station_gridder.perl and make_global_average_ts_ascii.perl).

At various times I have been asked to suggest which part of an application’s or product’s source code should be made available to a third party. The third party may have been interested in evaluating the quality, getting a feel for the complexity or felt that they ought at least be able to say they had seen some code. In these situations there is always a trade-off between impressing the customer (e.g., well structured code containing lots of comments) and not revealing too much (e.g., impenetrable code with no comments).

Have the Met Office released the code they have used over a period of time or have they release newly written code?

The source does not have the characteristics often seen in well worn, ‘old’, code. There is no revision history (that may be due to poor programming practices or may have been stripped off prior to release; I discuss pretty printing below), the visual layout is generally consistent (this may be because the same small group of people have worked on it over time), there are no obvious hacks used to get around previous design decisions that have changed and unscientifically it just feels to me like newly written code.

Was the original code written in another language (e.g., Fortran), perhaps as part of a larger program and been rewritten in Perl?

The code does not have a Fortran ‘accent’ to it. The code was written by people who are fluent in Perl; perhaps they do not know Fortran very well and were given time to craft something presentable, hence no Fortran accent.

Why have I been referring to the code authors, plural, when writing 397 lines is well within the capabilities of a competent developer working for a day (I bet the authors spent longer in meetings about this code than actually writing it)? Developers tend to have very fixed habits when it comes to bracketing statements with curly braces, there are those who always put the open brace at the end of the line and those who always put it on a newline. The Met Office code contains both usages, sometimes within the same subroutine. Also the use of whitespace around punctuators and operators does not follow a consistent pattern, which for me rules out the use of an automated pretty printer and kind of implies more than one person doing the editing. And why are some variables names capitalized and other not (the names in subroutine read_station are all lower case while the names in the surrounding subroutines are mostly upper case)? More than one author is the simplest answer.

One Perl usage caught my eye, the construct unless is rarely used and often recommended against. Without a lot more code being available for analysis there are no obviously conclusions to draw from this usage (apart from it being an indicator of somebody who knows Perl well, most mainstream languages do not support this construct and developers have to use a ‘positive’ construct containing a negated condition rather than a ‘negative’ construct containing a positive condition).