Wednesday, August 5, 2009

Quantum Superpositions and other Scary Stuff

Quantum::Superpositions, Quantum::Entanglement and Quantum::Usrn, as one may note, are related to quantum mechanics. Those are not packages to solve equations characteristic to quantum mechanics, but to bring quantum ideas and logic into Perl and programming in general. All three packages are interesting and deserve attention but only Quantum::Superpositions achieved wider recognition and become part of Perl 6. For that reason (limited space also plays a role) I would concentrate only on Quantum::Superpositions.

Welcome to Hilbert space and no, you do not have to have quantum computer at home to play with madness. With a little help from your friends (whom you manage to find on Internet) your good old computer will do just fine.

If you are running Ubuntu or Debian, use sudo; if not, just run terminal as root:

sudo perl -MCPAN -e shell

As mentioned, to invoke CPAN shell you must use root. If you never used it then do the update.

cpan[1]> install Bundle::CPAN

That may take some time.

cpan[2]> reload cpan

And finally, why we started all this - installation of Quantum::Superpositions:

cpan[3]> install Quantum::Superpositions

CPAN shell will ask for permission to download dependencies, and when all is done type in q or quit and hit enter to release the lock.

There is a philosophycal background to this package and the author, Damian Conway, gently mentioned it in documentation. Naturally, very few readers have the knowledge of quantum mechanics (that thing is worse than maths) and for the majority we will nicely disect the package through trusty old trial and error aproach. Quantum::Superpositions introduces two operators - any and all. Those operators are mapping a set of scalars to a single scalar variable, the author calls those scalar variables eigenstates. You see how that quantum mechanic may be dangerous and contageous, short exposure to it and you are already appending German words to English ones creating a new language which nobody understands. Without further ado we start with the code:

use Quantum::Superpositions;

use Data::Dumper;

$temp = all(1 .. 5);

print "$temp";

print "\n";

print Dumper($temp);

From the output we may conclude that to string method is overloaded and that $temp is a reference to anonymous array blessed to Quantum::Superpositions::Conj. If we do the same for any we see that $temp is a reference to anonymous array now blessed to Quantum::Superpositions::Disj. If you can't remember that reference to anonymous array, here it is:

$temp = [1, 2, 3]

Beside string conversion, the package overloads all other commonly used operators. Locating Superpositions.pm and inspecting the code may be highly beneficial here. Trivial:

$test++;

will increase all eigenvalues, irrespective of whether we are using any or all. Multiplication and addition becomes real fun:

$temp = any(1 .. 3)*any(4, 5);

print "$temp";

will produce:

any(8,4,10,12,15,5)

We will also note that any ignores duplicate values (or eigenvalues?) and all doesn't. Commutativity is satisfied for any*any or all*all but not for all*any. For example:

any(1 .. 3)*all(4, 5) = any()

but

all(4, 5)*any(1 .. 3) = all(any(8,4,12),any(10,15,5))

The type of the first operand determines the type of the result of multiplication. If we try addition then:

$temp = all(4, 5)+any(1 .. 3);

print "$temp";

print "\n";

print Dumper($temp);

produces a very interesting result:

6 7
$VAR1 = bless( [
                 bless( [
                          5,
                          6,
                          7
                        ], 'Quantum::Superpositions::Disj' ),
                 bless( [
                          6,
                          7,
                          8
                        ], 'Quantum::Superpositions::Disj' )
               ], 'Quantum::Superpositions::Conj' ); 

The result is an array containing common subset. From this (pretending that we did not read help file) we can easily draw the formula for finding common subset:

$temp = all(any(1 .. 5), any(4, 5, 6), any(3, 4, 5));

Small warning here: if one tries @$temp it will not produce expected 4 and 5 but:

any(4,1,3,2,5) any(6,4,5) any(4,3,5)

To pull subset into array properly we must use eigenstates method.

@subset = eigenstates(all(any(1 .. 5), any(4, 5, 6), any(3, 4, 5)));

Now the question do elements of array @b contain all the elements of array @a becomes:

@a = (1, 2, 3);

@b = (1 .. 5);

if(@a == eigenstates(all(any(@a), any(@b)))){

print "Yes @a is subset of @b\n";

}

Which is really a neat way of coding compared to usual nested loops.

If you download the source as well, it contains demo directory where we can see GCD and factoring and generally get some idea on how the package may be used. While the package brings ideas from quantum computing, it doesn't turn your old computer into a quantum one, so some algorithms may still execute in exponential time. If you find this interesting here is a small advertisment for Quantum::Entanglement, its demo directory contains implementation of Shor's algorithm for factoring numbers.



Monday, July 20, 2009

Pascal's triangle, Perl, and homework

Frequently, an evil professor gives to his students homework and sometimes it may be a request to write code which prints Pascal's triangle. Naturally, the student cranks up Firefox (that is synonym for web browser) and goes googling around for examples. A nice elegant solution comes up in the form of:

sub pascal { 
my @row;
foreach (1 .. shift) {
push @row => 1;
$row [$_] += $row [$_ - 1] for reverse 1 .. @row - 2;
print "@row\n";
}
}


I picked up that one on http://www.perlmonks.org/?node=175586, naturally very few students will understand, right away, what is happening in this code. In order to make the code shorter the author did some Perl tricks, which made it difficult to read and understand the code. In the first transformation I will introduce one unnecessary variable and also make function call more C or Java like.

sub pascal {
my $size = shift();
my @row;
foreach (1 .. $size) {
push (@row, 1);
$row [$_] += $row [$_ - 1] for reverse 1 .. @row - 2;
print "@row\n";
}
}


Already looks better. Inner loop still looks odd and we are not quite sure what it does and which $_ is used, one from foreach or one from for reverse. In order to see, let us add one debug loop:

sub pascal {
my $size = shift();
my @row;
foreach (1 .. $size) {
push (@row, 1);
for (reverse 1 .. @row - 2){
print $row [$_]," + ",$row [$_ - 1]," store in \$row[$_]\n";
}
$row [$_] += $row [$_ - 1] for reverse 1 .. @row - 2;
print "@row\n";
}
}


Output will look like this:

1 
1 1
1 + 1 store in $row[1]
1 2 1
1 + 2 store in $row[2]
2 + 1 store in $row[1]
1 3 3 1
1 + 3 store in $row[3]
3 + 3 store in $row[2]
3 + 1 store in $row[1]
1 4 6 4 1


Now it is obvious that outer loop just pushes ones and inner loop does all difficult work.
One small thing is left, printout doesn't look nice, it is somehow skew. To remedy that we add some pretty printing:
sub pascal {
my $size = shift;
my $count;
my $margin;
my @row;
foreach (1 .. $size) {
push (@row, 1);
$row [$_] += $row [$_ - 1] for reverse 1 .. @row - 2;
$margin = " " x ($size - $count - 1);
print "$margin";
$count++;
foreach (@row){
printf "%6d",$_;
}
print "\n";
}


If we call it and pass 16 as parameter it will print this:

                                                 1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1


Not quite equilateral, one would say.

Tuesday, July 7, 2009

Install JDK on Ubuntu 9.04

Occasionally there is need to switch between JDK's. For example DrJava works nicely only with JDK downloaded from the Sun website. Also Eclipse and NetBeans may show some funny behaviours if they are using JDK from Ubuntu repositories. But before I go about creating config files and setting up this or that JDK to be default, let me explain how to install any JDK on Ubuntu.

Vanilla Ubuntu JDK

There are two main methods which can be used to install Java Development Kit on Ubuntu. The first one is you use Ubuntu repositories. GUI way is go to System -> Administration -> Synaptic Package Manager. It will ask you for a password. When it is up type in Java into Quick search box. Further, locate the JDK that you want, tick check box next to it (from context menu select Mark for installation) and hit Apply button. Under the bonnet packages will be downloaded, unpacked, installed and symbolic links created. If you want you can use command line and apt-get instead. Go to Applications -> Acessories -> Terminal, when terminal shows up type in:



apt-cache search java | more



That does search for packages which are somehow related to Java. Part of the command '| more' prints single screen at the time; to see the next batch of results hit the space bar. When you locate what you need then you install it:



sudo apt-get install openjdk-6-jdk



sudo gives you temporary root authority and will ask you for password. You may want to install sun-java6-jdk instead, or maybe both of them.

If you decided to install more than one JDK then you may wish to alternate between them from time to time. To achieve that run:



update-java-alternatives -l



That should produce a list of JDK's. What is it and what does it actually do? It is bash script located in /usr/sbin/ and it is part of java-common. To see what else is in java-common use:



dpkg -L java-common



It goes to /usr/lib/jvm/ and looks for *.jinfo files. Those files are hidden files, their name starts with dot, for example .java-6-sun.jinfo. In order to see hidden files in Nautilus press Ctl+H. Their content looks something like this:



name=java-6-openjdk

alias=java-6-openjdk

priority=1061

section=main



hl java /usr/lib/jvm/java-6-openjdk/jre/bin/java

hl keytool /usr/lib/jvm/java-6-openjdk/jre/bin/keytool

...

hl jexec /usr/lib/jvm/java-6-openjdk/jre/lib/jexec

jre javaws /usr/lib/jvm/java-6-openjdk/jre/bin/javaws

jre pluginappletviewer /usr/lib/jvm/java-6-openjdk/jre/bin/pluginappletviewer

jre policytool /usr/lib/jvm/java-6-openjdk/jre/bin/policytool

jdk appletviewer /usr/lib/jvm/java-6-openjdk/bin/appletviewer

...

jdk jar /usr/lib/jvm/java-6-openjdk/bin/jar

jdk jarsigner /usr/lib/jvm/java-6-openjdk/bin/jarsigner

jdk javac /usr/lib/jvm/java-6-openjdk/bin/javac

...

jdk wsgen /usr/lib/jvm/java-6-openjdk/bin/wsgen

jdk wsimport /usr/lib/jvm/java-6-openjdk/bin/wsimport

jdk xjc /usr/lib/jvm/java-6-openjdk/bin/xjc

plugin xulrunner-1.9-javaplugin.so /usr/lib/jvm/java-6-openjdk/jre/lib/amd64/gcjwebplugin.so



If your Firefox or Chrome gives you hard time with Java applets, you know where to look.

Back to list of available JDK's, pick one and set it as default:



sudo update-java-alternatives -s java-6-sun



Now when you try java -version it should print out your current JDK version.

Using JDK which is not from Ubuntu Repository

Usually that is JDK downloaded directly from Sun website. It usually comes as shell script and it is named jdk-6u13-linux-i586.bin; update version may be different. When you run it (double click and select Run from dialogue) it will show EULA and extract JDK right there where you downloaded it. If you expected that it will be installed and become the main supplier of Java Virtual Machine - sorry that is not the case. There are two options, the first one is quick and dirty. In order to make your ~/install/jdk1.6.0_13/bin/java main supplier of Java do the following:



sudo update-alternatives --install /usr/bin/java java /home/JDKPATH/install/jdk1.6.0_13/bin/java 300

sudo update-alternatives --auto java

sudo update-alternatives --install /usr/bin/javac javac /home/JDKPATH/jdk1.6.0_13/bin/javac 300

sudo update-alternatives --auto javac



That should be enough to get you going. If the need arises, you may wish to append more of those symbolic links to the collection.

The more appropriate solution would be how Debian developers are doing it, cd to where JDK is and execute the following:



sudo apt-get install fakeroot java-package

fakeroot make-jpkg jdk-6u13-linux-i586.bin



After the process of packaging JDK is over there should be sun-j2sdk1.6_1.6.0+update13_i386.deb which you can double click to start GDebi and install it. Finally execute:



sudo update-alternatives --config java



It will list what is available on your box and you type in number for /usr/lib/j2sdk1.6-sun/bin/java to set it as default.



Monday, July 6, 2009

Concatenate empty String with Integer or not

Recently I was lucky enough to take part in some damage control mission. At the site I discovered many interesting things. Tomcat was deployed in development mode in production environment and log file was well over 6GB. For some unknown reason they preferred to use Tomcat and solve connection polling manualy (using Proxool). Naturally, the client wanted everything upgraded to Java 6, which may not be such a good idea with Proxool. I hope that one can imagine the amount of work invested in Proxool and appreciate equally the complicated dependencies like Cglib or Asm. Anyway, why would one use Glassfish, TopLink, JSF and EJB 3.0 when with Tomcat we can do nicely our own thread-connection-pulling management, do user interface using Velocity and so on.

Luckily, there was no documentation and the reason for all those architectural decisions can't be clearly established. The unofficial version is that on the same project (but old version) there was a small group of developers using Delphi and Sybase. After years of work they knew business logic so well. Then the client decided to start using Oracle and Java. Since the guys were so familiar with business logic, the fact that they did not know much about Java was not that important. They didn't quite understand the need for build process, source versioning and other boring stuff. So they will check in and out source, do bug fixes, compile at will, drop classes into Tomcat's WEB-INF folder. Mostly people were using Eclipse incremental compiler, but some used ant and javac. Tagging was non-existing and eventually nobody knew what was deployed where - which version of the source. So it was required to discover through decompiling what was deployed in production environment. Through the process I discovered the most original way of converting number to string. Here is the small example of original and common way of obtaining string representation of integer:



public class Main {

public static void main(String[] args) {

System.out.print(useInteger(11));

System.out.print(hereIsYourString(12));

}

static String hereIsYourString(int i){

return ""+i;

}

static String useInteger(int i){

return Integer.toString(i);

}

}


Now some people would maybe like less typing idea more. OK, the question is how does one explain to an inexperienced Java programmer to stay out of those shortcuts?

I think the best way is to disassemble class using the Java Class File Disassembler and take a look at bytecode. The best way to start with javap is this:


~$ javap -help

Usage: javap <options> <classes>...


where options include:

-c Disassemble the code

-classpath <pathlist> Specify where to find user class files

-extdirs <dirs> Override location of installed extensions

-help Print this usage message

-J<flag> Pass <flag> directly to the runtime system

-l Print line number and local variable tables

-public Show only public classes and members

-protected Show protected/public classes and members

-package Show package/protected/public classes

and members (default)

-private Show all classes and members

-s Print internal type signatures

-bootclasspath <pathlist> Override location of class files loaded

by the bootstrap class loader

-verbose Print stack size, number of locals and args for methods

If verifying, print reasons for failure


Using info I will cd to /MyProjects/JavaApplication22/build/classes/javaapplication22 and that is where the product of compilation is. Then I will do dissasembling:


~/MyProjects/JavaApplication22/build/classes/javaapplication22$ javap -c -classpath . Main

Compiled from "Main.java"

public class javaapplication22.Main extends java.lang.Object{

public javaapplication22.Main();

Code:

0: aload_0

1: invokespecial #1; //Method java/lang/Object."<init>":()V

4: return


public static void main(java.lang.String[]);

Code:

0: getstatic #2; //Field java/lang/System.out:Ljava/io/PrintStream;

3: bipush 11

5: invokestatic #3; //Method useInteger:(I)Ljava/lang/String;

8: invokevirtual #4; //Method java/io/PrintStream.print:(Ljava/lang/String;)V

11: getstatic #2; //Field java/lang/System.out:Ljava/io/PrintStream;

14: iconst_1

15: invokestatic #5; //Method hereIsYourString:(I)Ljava/lang/String;

18: invokevirtual #4; //Method java/io/PrintStream.print:(Ljava/lang/String;)V

21: return


static java.lang.String hereIsYourString(int);

Code:

0: new #6; //class java/lang/StringBuilder

3: dup

4: invokespecial #7; //Method java/lang/StringBuilder."<init>":()V

7: ldc #8; //String

9: invokevirtual #9; //Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;

12: iload_0

13: invokevirtual #10; //Method java/lang/StringBuilder.append:(I)Ljava/lang/StringBuilder;

16: invokevirtual #11; //Method java/lang/StringBuilder.toString:()Ljava/lang/String;

19: areturn


static java.lang.String useInteger(int);

Code:

0: iload_0

1: invokestatic #12; //Method java/lang/Integer.toString:(I)Ljava/lang/String;

4: areturn


}


At the first sight output may look confusing, but if we take a better look everything is there and comparing to Java source helps identify our methods. Here you have it: concatenating empty string with integer generates few more instructions than calling static Integer.toString.

If one would like to explore what happens further eg. inside Integer.toString or StringBuilder.append I would warmly recommend downloading OpenJDK, alternatively make a break until such an idea goes away.



Sunday, July 5, 2009

Home SMS Gateway using Perl, Ubuntu and Nokia

Thinking what would be good for the start. SMS gateway sounds quite interesting.

On a large scale one is inclined to look at Kannel as a starting point. There are a few traps with Kannel. While being open source (bearerbox and smsbox), the most interesting parts like smppbox are not open source, so be prepared to spit out about 4000 Euros for it when the volume becomes critical. Also, Kannel doesn't like SuSE Linux Enterprise Server very much, and for some reason that one is used here by the government and big companies. Apparently, Novell sells support cheaper than Red Hat and it is friendlier with MS. So, if you like Kannel-based solution - use Red Hat or Debian. That is stated in Kannel's documentation and they know what they are talking about.

What else may one use to roll out SMS gateway?

Java and its enormous wealth of open source libraries, application servers and development tools. Assembling SMS gateway with SMPP API should be quite easy.

How about deploying SMS gateway on Windows?

You cannot be serious.

Now we may leave alone make-millions-from-spamming enterprise projects and check something more appropriate for common people. How do you create your own SMS gateway? Not so long ago I wrote a small article about sending SMS using Nokia S60 phone as a modem from Ubuntu and Device::Gsm Pearl module. Now lot of people will ask why Perl? If you want to do something simple and effective on Ubuntu (or any other kind of Linux), Pearl is the way to go. If you want to do some massive development with tens of thousands of line of code, do not use Perl.

I tried this using Nokia N81 as a modem. There is no need to go that high, any phone which can act as a modem will do. USB wireless modems, like Huawei E220 should do as well. Operating system is Ubuntu 8.04, but you can try that using any OS where Perl can be installed.

For the start we need to install Device::Gms.


$ sudo perl -MCPAN -e shell


Super user is required to do that, now from CPAN shell we update our CPAN


cpan[1]> install Bundle::CPAN


That may take some time.


cpan[2]> reload cpan


And finally why we started all this:


cpan[3]> install Device::Gsm


It may be needed to install dependencies, like Device::Modem, CPAN will suggest that it downloads and installs dependencies. Home page of Device::Gsm is here http://search.cpan.org/~cosimo/Device-Gsm/Gsm.pm, I suggest visiting it and reading it - carefully.


Now we can grab the USB cable and connect Nokia (or whatever you are using) and PC, from phone menu we select PC Suite. On Ubuntu we activate terminal and execute dmesg, only the last few lines are interesting.


[11869.492522] usb 2-5: new full speed USB device using ohci_hcd and address 2

[11869.727885] usb 2-5: configuration #1 chosen from 1 choice

[11870.010452] cdc_acm 2-5:1.8: ttyACM0: USB ACM device

[11870.015377] usbcore: registered new interface driver cdc_acm

[11870.015387] /build/buildd/linux-2.6.24/drivers/usb/class/cdc-acm.c: v0.25:USB Abstract Control Model driver for USB modems and ISDN adapters

[11870.053566] usbcore: registered new interface driver cdc_ether

[11870.056287] usb 2-5: bad CDC descriptors

[11870.056308] usbcore: registered new interface driver rndis_host


We now locate the following line of code on Device::Gsm home page


my $gsm = new Device::Gsm( port => '/dev/ttyS1', pin => 'xxxx' );


From dmesg otput we find out where the phone is and also we enter appropriate PIN


my $gsm = new Device::Gsm( port => '/dev/ttyACM0', pin => 'here comes your PIN' );


We are now ready to go:


#!/usr/bin/perl -w


use Device::Gsm;

my $gsm = new Device::Gsm( port => '/dev/ttyACM0', pin => 'XXXX' );

if( $gsm->connect() ) {

print "connected!\n";

} else {

print "sorry, no connection with gsm phone on serial port!\n";

}

my $imei = $gsm->imei();

print "$imei\n";

my $model = $gsm->model();

print "$model\n";


Copy and paste this into new file, name it test.pl and execute from terminal perl test.pl. That will print IMEI and phone model.

By further modification of initial example from Device::Gsm home page we have


#!/usr/bin/perl -w

use Device::Gsm;

my $gsm = new Device::Gsm( port => '/dev/ttyACM0', pin => 'XXXX' , log => 'file,network.log', loglevel => 'debug');

if( $gsm->connect() ) {

print "connected!\n";

} else {

print "sorry, no connection with gsm phone on serial port!\n";

}

$gsm->register();

$gsm->send_sms(

recipient => '+2774XXXXXXX',

content => 'Here is your Ubuntu talking',

class => 'normal'

);


Naturally, replace XXXX with what is your pin number. Start of recipient is +27 for South Africa and 74 for network, it may need adjustment as well. Reusing test.pl is a good idea. To send an SMS takes a while. In network.log we will find the story, if everything went well do not even look at it - 160 Kb of log per SMS. Now typically one would like to combine this with some kind of HTTP or maybe TCP access, but that is quite easy and well explained all over the web so I will not bother you with it.

If you happen to be in Italy, Cosimo Streppone may be happy to know that you are using his library, look for send_to_cosimo.pl in examples folder.