Harsh J

Memoirs of a QWERTY Keyboard

Archive for the ‘Programming’ tag

Justice enough

leave a comment

About the immutability of variables once bounded in Erlang:

Single assignment is like algebra.

When I went to school, my math teacher said, “If there’s an X in several different parts in the same equation, then all the Xs mean the same thing.” That’s how we can solve equations: if we know that X+Y=10 and X-Y=2, then X will be 6 and Y will be 4 in both equations.

But when I learned my first programming language, we were shown stuff like this:
X = X + 1

Everyone protested, saying “you can’t do that!”. But the teacher said we were wrong, and we had to unlearn what we learned in math class. X isn’t a math variable: it’s like a pigeon hole/little box…

In Erlang, variables are just like they are in math. When you associate a value with a variable, you’re making an assertion – a statement of fact. This variable has that value. And that’s that.

Joe Armstrong, in his book Programming Erlang.

Written by Harsh

August 7th, 2010 at 11:08 pm

Posted in Computing Issues,Fun

Tagged with ,

Sieve of Euler in Erlang

9 comments

Learning Erlang is a fun task. Solving PE problems with it even more. You can never really beat PE problems unless you have your own fast implementations of primality tests, prime generation sieves and so on.

A quick way to generate primes, as many would tell you, would be to implement and use the Sieve of Eratosthenes. Its a simple sieve that works by striking off all multiples of primes thus observed in sequence. Wikipedia has an illustration on its working technique.

There is another simple sieve derived from the same idea, known as the Sieve of Euler, which uses a filtering technique based on products of an encountered prime across the remaining elements. This sort of a sieve, again explained in a good manner at Wikipedia, is shorter and easier to implement in Erlang than the traditional Eratosthenes (and I mean proper Eratosthenes, mind you).

The following is the solution I came up with, a couple of days into learning Erlang for great good:

-module(primes).
-export([generatePrimes/1]).

% Sieve of Euler %

generatePrimes (N) when is_integer(N) and (N > 1) ->
    Numbers = lists:seq(2,N),
    BeginIndex = 1,
    generatePrimes(Numbers, [], BeginIndex).

generatePrimes (Numbers, Numbers, _Index) ->
    Numbers;

generatePrimes (Numbers, _PreviousNumbers, Index) ->
    FilteredNumbers = ordsets:subtract(Numbers, multiples(lists:nth(Index, Numbers), Numbers)),
    generatePrimes(FilteredNumbers, Numbers, Index + 1).

multiples (Prime, Numbers) ->
    lists:map(fun(Num) -> Prime * Num end, Numbers).

% Compile as c(primes). %


The function primes:generatePrimes(N) will generate all primes until N. On my 2.93 GHz machine it takes about 2.1s to generate all primes under a million (78498 primes).

As a bonus, you can go ahead and compute single-line inelegant solutions #3 and #10 of Project Euler as:

% Solution to problem 3 %
lists:nth(1, lists:dropwhile(fun(X) -> not(600851475143 rem X == 0) end, lists:reverse(primes:generatePrimes(trunc(math:sqrt(600851475143)))))).

% Solution to problem 10 %
lists:sum(primes:generatePrimes(2000000)).

Notes: There is some redundant multiple calculation involved but I noticed that if I perform a sublist operation to remove that it slows the generation down, so I let it be. The sieving operation also terminates when it notices that no number was filtered in one of its call, as this marks the proper end of it. For instance, to generate all primes under 100, it only sieves through the first five primes.

Update:

Kind commenter Angel (angel at uah dot es) posted a solution (and a multi-process one!) to a proper Eratosthenes’ Sieve (based on the O’Neill’s paper I referenced above), which goes below:

% "Genuine" Erathostenes sieve in erlang
% based on www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
% 2009 Angel Alvarez
%
% Process  1     2     3     4     5     6     7 ....
%
%         02    03    05    07    11    13    17
% P 02 -> 04
% P 03    04 -> 09
% C 04 == 04    09
% P 05    06    09 -> 25
% C 06 == 06    09    25
% P 07    08    09    25 -> 49
% C 08 == 08    09    25    49
% C 09    10 == 09    25    49
% C 10 == 10    12    25    49
% P 11    12    12    25    49 -> 121
% C 12 == 12    12    25    49    121
% P 13    14    15    25    49    121 -> 169
% C 14 == 14    15    25    49    121    169
% C 15    16 == 15    25    49    121    169
% C 16 == 16    18    25    49    121    169
% P 17    18    18    25    49    121    169 -> 289

-module(multi_erathostenes).
-author("angel at uah dot es").
-compile(export_all).

compare(X,Y) when X > Y -> greater;
compare(X,Y) when X < Y -> smaller;
compare(_,_) -> equal.


worker(Prime,UpperBound)->
	receive
		{test,Number,ParentPID} ->
			ParentPID ! ok,
			case compare(Number,UpperBound) of
				equal ->
%					io:format("[Worker of prime: ~w (~w)] Found composite: ~w~n",[Prime,UpperBound,Number]),
					worker(Prime,UpperBound + Prime);
				smaller ->
					io:format("[Worker of prime: ~w (~w)] Spawn new worker for Prime: ~w~n",[Prime,UpperBound,Number]),
					NextPID =spawn(?MODULE,worker,[Number,Number*Number]),
					worker(Prime,UpperBound,NextPID)
			end;
		stop ->
		    noop
	end.

worker(Prime,UpperBound,NextPID) ->
	receive
		{test,Number,ParentPID} ->
			ParentPID ! ok,
			case compare(Number,UpperBound) of
				equal ->
%					io:format("[Worker of prime: ~w (~w)] Found composite: ~w~n",[Prime,UpperBound,Number]),
					worker(Prime,UpperBound + Prime,NextPID);
				smaller ->
% 					io:format("[Worker of prime: ~w (~w)] passing along: ~w~n",[Prime,UpperBound,Number]),
					NextPID ! {test,Number,self()},
					receive
					    ok -> ok
					end,
					worker(Prime,UpperBound,NextPID);
				greater ->
% 					io:format("[Worker of prime: ~w (~w)] passing along: ~w~n",[Prime,UpperBound,Number]),
					NextPID ! {test,Number,self()},
					receive
					    ok -> ok
					end,
 					worker(Prime,UpperBound+Prime,NextPID)
			end;
		stop ->
		    NextPID ! stop,
		    noop
	end.

start(N) ->
    OnePID=spawn(?MODULE,worker,[2,4]),
    cicle(3,N,OnePID).

cicle(Last,Last,Worker) ->
    Worker ! stop;
cicle(Current,Last,Worker) ->
    Worker ! {test,Current,self()},
    receive
	ok -> ok
    end,
    cicle(Current+1,Last,Worker).

Written by Harsh

June 6th, 2010 at 11:15 pm

PyQt – Creating interfaces visually with Designer

4 comments

Note: If you’re new to using PyQt but are interested in great cross-platform GUI application development please read the PyQt Introduction article.

Designing a graphical interface for an application could be a tiresome task. There are guidelines to keep track of, layouts to maintain and more of such stuff. In the PyQt code samples you’ve seen so far we’ve written our interfaces in pure code. While this is fun and easy to do for little applications that consist of about 5 to 10 widgets, it’s not worth spending the time upon in creating fully blown up interfaces for complete applications.

The Qt Designer

Fortunately, Qt provides us a tool to design interfaces and to port it to usable code automatically. This tool is called the Qt Designer, and it comes with the Qt library bundle you installed. Additionally we would require a converter for processing the XML .ui files Designer produces into a python module .py file; also installed with the PyQt4 bundle.

Thus, to design in PyQt we need the two following tools:

  • Qt Designer from Nokia’s Qt Software
  • The pyuic4 script from Riverbank’s PyQt

Once you have Designer and PyQt4 tools installed, let’s fire it up and get started.

The initial interface might look familiar to those who have used Visual Studio, or Glade and such tools. For the rest, it’s intuitive enough to learn smoothly. Read the Qt Designer guide for more elaborate help if you still don’t find it usable.

The Qt Designer

The Qt Designer

In this article, we’ll be using Designer to design and create a simple Image Viewer application.

References: Qt Designer, The PyQt + Qt Designer Documentation

Image Viewer

Our Image Viewer application would be a very simple one, with options to Open an image file of major types (JPEG, PNG, GIF, etc.) and another to Quit. Upon opening of an image, we shall also set the status bar to show the dimensions of the image.

Designing the GUI

Open Qt Designer (‘designer’ command if on Linux) and choose File | New | “Main Window” under templates/forms expansion. This creates a new QMainWindow widget for us to work upon. The QMainWindow is basically a composition of a main-area widget, a menu-bar and a status-bar at the bottom, the very usual stuff an application consists of.

Design of the Image Viewer UI

Design of the Image Viewer UI

From the Widget Box, drag a Label onto the main window’s area. Right-Click at any of the free space available on the same area, choose the “Lay out” sub-menu and then hit the “Lay out Horizontally” option. Designer will automatically stretch your Label across the area available this way. We need this layout (any layout will do here, actually) since we want the image to show in the entire window area.

Now on to menus, Add a File menu and under it add an Open and a Quit option, as shown below. To add these just click where it says “Type here” and get typing; Hit Enter/Return key to get to the next element in the menu after you’ve typed.

Under the Property Editor, select and set the Label’s text property to blank, and its alignment property to AlignHCenter and AlignVCenter. This completes our UI design in Qt Designer. But don’t quit already, do explore the other properties of the widgets used and figure out their possible uses; get used to the interface and available tools like Form Previews, etc.

The imageLabel (QLabel) object Properties

The imageLabel (QLabel) object Properties

For instance, check out the properties like geometry (Height and Width), font, tooltip, etc. If you’re in a good reading mood, also checkout the amazing Style Sheet documentation in Qt Assistant, as it explains a lot about each Widget’s construct and how to go about customizing it till your heart’s content.

Finally, renaming the widget elements’ variables would be a good idea, since it will help us code our application in a much more readable manner. This is how I’ve named these widgets but feel free to follow whatever naming conventions you would like to use:

Image Viewer object names

Image Viewer object names

Just double-click on the Object Name items and edit them in-line after that. Note and remember your QMainWindow class’s object name. Once you’re done, save the file as ‘ImageViewerUI.ui‘.

References: QLabel, QAction, QMenuBar, Layouts Guide

Using PyQt’s pyuic4 script

Our next step requires the use of the aforementioned pyuic4 tool. It’s usage syntax is as follows:

pyuic4 input_file.ui -o output_file.py
# Optionally takes -x parameter to make the generated code executable.

Thus we should run, for our UI file:

pyuic4 ImageViewerUI.ui -o ImageViewerUI.py

This will create a file ImageViewerUI.py that we can now use. Looking into the file will show you that its just a long list of widget constructs and of applying property settings. There is no need to edit this file, and is advised not to since pyuic4 will over-write all changes in it if you run it once again after some changes you wanted to do.

Whenever you edit your .ui files, make sure to run the pyuic4 tool to convert it into its Python equivalent (or to update existing Python code such that it reflects the new changes).

Additional info: Try `pyuic4 –help` for more fine-tuning options.

Running the basic GUI

Create a new file ImageViewer.py to finally add the application logic. Before we get to the code part, let me explain how the Qt’s subclass approach works. A Qt Designer file is inherited by the QMainWindow-derived class, and then the interface is setup using the setupUi() call with an instance. This creates all the objects/widgets for the interface as attributes of the derived QMainWindow class so that it’s ready to show. Next, we need to add the application-level logic to this derived class as normal methods. Since we have access to all the widgets used in the interface via our class, we can do as we like with their available features. The following diagram explains the hierarchy we ought to follow each time we need to implement a UI class for use:

Image Viewer Inheritance Diagram

Image Viewer Inheritance Diagram

Thus, a basic class that can be run would look like:

#!/usr/bin/python

from PyQt4 import QtGui, QtCore
import sys

# Import the interface class
import ImageViewerUI

class ImageViewer(QtGui.QMainWindow, ImageViewerUI.Ui_mainWindow):
    """ The second parent must be 'Ui_<obj. name of main widget class>'.
        If confusing, simply open up ImageViewer.py and get the class
        name used. I'd named mine as mainWindow, hence Ui_mainWindow. """

    def __init__(self, parent=None):
        super(ImageViewer, self).__init__(parent)
        # This is because Python does not automatically
        # call the parent's constructor.
        self.setupUi(self)
        # Pass this "self" for building widgets and
        # keeping a reference.

    def main(self):
        self.show()

if __name__=='__main__':
    app = QtGui.QApplication(sys.argv)
    imageViewer = ImageViewer()
    imageViewer.main()
    app.exec_()
    # This shows the interface we just created. No logic has been added, yet.

Run this class and you can see the window you just created.

Basic GUI of Image Viewer during Runtime

Basic GUI of Image Viewer during Runtime

You MUST call self.setupUi(self) to make the UI file run the setup statements and build the GUI interface for use by our class.

References: QMainWindow

Adding Application Logic and other Code

Now to add the opening-an-image feature, let’s define a few methods in the class as:

#!/usr/bin/python
# -*- coding: utf-8 -*-

from PyQt4 import QtGui, QtCore
import sys

# Import the interface class
import ImageViewerUI

class ImageViewer(QtGui.QMainWindow, ImageViewerUI.Ui_mainWindow):
    """ The second parent must be Ui_<obj. name of main widget class>. \
      If confusing, simply open up ImageViewer.py and get the class \
      name used. I'd named mine as mainWindow and hence the use. """

    def __init__(self, parent=None):
        super(ImageViewer, self).__init__(parent)
        # This is because Python does not automatically
        # call the parent's constructor.
        self.setupUi(self)
        # Pass this "self" for building widgets and
        # keeping a reference.
        self.connectActions()

    def connectActions(self):
        self.actionQuit.triggered.connect(QtGui.qApp.quit)
        # Connect the Quit action's triggered signal
        # to a proper Quit method
        # given by qApp (which points to your QApplication
        # object).
        self.actionOpen.triggered.connect(self.openImage)
        # Connect the Open action's triggered signal
        # to load an image onto the image label.

    def openImage(self):
        # Lets get a user-provided file to open
        # using PyQt's QFileDialog class.
        fileName = QtGui.QFileDialog.getOpenFileName(
                        self,
                        "Open Image File",
                        QtCore.QDir.homePath(),
                        "Image Files (*.jpg *.jpeg *.gif *.png)"
                    )
        # Don't attempt to open if open dialog
        # was cancelled away.
        if fileName:
            self.imageLabel.setPixmap(QtGui.QPixmap(fileName))
            # Load the image file as a pixmap onto the
            # labelImage QLabel GUI object.

    def main(self):
        self.show()

if __name__=='__main__':
    app = QtGui.QApplication(sys.argv)
    imageViewer = ImageViewer()
    imageViewer.main()
    app.exec_()

Note the two new method additions connectActions() and openImage(). They complete the application logic that’s involved for our image viewing application example. Try to understand them better by seeing the PyQt classes used in them and referring them up in Qt Assistant for much more detailed information.

Now the application can open images via File | Open and can also be quit via File | Quit.

This is the final result of our work:

Image Viewer in Action

Image Viewer in Action

References: QPixmap, QFileDialog, qApp

Exercise

Try to build a simple text-based evaluator application that contains of two things:

  • A text input box that allows for mathematical expressions input.
  • An output label or text area (non-editable) for showing results of these expressions.

Classes you could use are QLabel, QLineEdit and QTextEdit. Another hint is to use Python’s ‘eval‘ function. As a bonus try to make the evaluation via Python safe.

Written by Harsh

April 18th, 2010 at 9:28 pm

Scratching my itch

4 comments

If you like open source software, you end up doing that someday sooner or later – you scratch your itch and make a contribution. That’s how it rolls. Well unless you’re sponsored to do so, of course.

I did the same for KDE, having had an on/off relationship with it since 3.x, and finally settling onto 4.3, I managed to get into writing code for it. Although not a fan of the entire desktop, it is what I use on a daily basis and I do feel the lack of a few things sometimes. There’s already too much to customize; and am sure I don’t know the half of it yet.

I read a lot of comic books in my free time, on the PC. While I do have my collections named and arranged neatly, it has always been hard finding a particular file since there were no previews of its covers on KDE 4. Since Okular, KDE’s magnificent all-in-one document reader, reads the files (.cbr, .cbz type) why not also preview it. That became my itch, my want. And I scratched it with copious amounts of help provided by its development community. However, I’d be glad if some artist came along and gave the format an Oxygen-style icon as well – since it still lacks one.

In KDE 4.4, you will have comic book previews which would show you the comic book covers in its file manager’s preview mode. This should make your life easier. However, for .cbr thumbnails to work, you’d need the non-free version of unrar cause the free ones don’t do version 3+ files well. It isn’t a hard dependency, and .cbz ZIP files would work just fine without unrar. I’d also written support for .cbt, but it’d have to wait until KDE 4.5 cause of their ‘feature freeze’.

Since I made it this far, I also fixed certain minor annoyances – some reported by other people as well. A small list:

I’ll be more than glad to hammer more bugs, once the feature freeze melts. Go here to read about what’s new in KDE 4.4.

Written by Harsh

December 8th, 2009 at 12:04 am

Randomize: Some Programming Quotes

4 comments

Scripts vs. Programs

Couldn’t be put more simpler than this.

A script is what you give the actors. A program is what you give the audience.
– Larry Wall, the creator of Perl

So, do you know what programs written in scripting languages really are? :P

Recurring Recursions

You’re on Step 2, which asks you to do Step 1?

In order to understand recursion, one must first understand recursion.
– Unknown, multiple sources

Stack overflow.

Smart Debugging

Damn!

Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.
– Brian W. Kernighan, the K in K&R C Book and AWK

Where would you draw the line?

Deficit Obviousness

There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies and the other way is to make it so complicated that there are no obvious deficiencies.
– C.A.R. Hoare, the inventor of Quicksort

Obviously no deficiencies in understanding which way to choose.

Add your favorites in the comments, if you wish to.

Written by Harsh

November 6th, 2009 at 10:55 pm

Posted in Fun

Tagged with , ,