Harsh J

Memoirs of a QWERTY Keyboard

Archive for the ‘Computing Issues’ Category

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

Pomodoro and KDE

2 comments

Am no follower of the Pomodoro technique nor do I know its specifics but before you go ahead and try out those multiple Adobe AIR applications or use the GNOME-oriented Workrave, please try out this software called RSIBreak which was built for KDE specifically.

RSIBreak - Repetitive Strain Injury prevention software for KDE

RSIBreak - Repetitive Strain Injury prevention software for KDE


It isn’t a full fledged timer feature but I think it will get your needs covered with its offerings easily enough. One of the amazing utilities I’ve used, built with KDE Libraries. It should be available in your Linux distribution’s software repository too.

Written by Harsh

May 5th, 2010 at 3:22 pm

PyQt – Creating interfaces visually with Designer

2 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

KDE and the .gtkrc

leave a comment

In my quest to have a perfectly usable dark theme I found I would require two things:


Having acquired those, I went on to install and select them via System Settings’s Appearance applet and all my Qt4+KDE4 applications looked neat in their dark avatars. Next I had to make Chromium reflect and respect the native theme settings and found an option for it to “Use GTK Theme” under Settings – Options – Personal Stuff.

However upon switching that on I realized that GTK themes were indeed showing the coloring of darkPearl right but not the widget styling that the darkPearl + QtCurve provide together, despite placing a proper QtCurve .gtkrc and its other known aliases at all key positions. Sometimes it’d work after doing the last action, but only for the current KDE session and it would all go back to simple-coloring hell post a re-logon.

The solution to this was apparently under System Settings’s Appearance – Colors applet itself. I’d missed an option under the Options tab of Colors that said “Apply color to non-KDE4 Applications“. Un-check this and the custom .gtkrc you place sticks like its supposed to. Chromium looks great now! So does GIMP, the second of the two GTK-using applications I use.

Written by Harsh

April 17th, 2010 at 4:41 pm