Algorithm.co.il

Programming

Website development and not supporting Internet Explorer 6

Posted on by 1 Comment

My partner and I started to work on a website a few months ago. We have a working prototype, and we are always improving it. My work is mostly concentrated on a smart Python backend, and on a Javascript front-end, while a thin controller acts as a messenger between the two.
Lately, I’ve worked on improving the UI. As expected, I rely heavily on CSS. I generate a lot of html elements using Mochikit and format them with CSS classes. While obviously better than the old alternatives, I still don’t like CSS. Maybe it’s because I don’t understand it deeply enough, but for me, there is still a lot of voodoo involved. An example I found, which luckily I didn’t run into yet, is collapsing margins.

Still, even with all its voodoo, CSS is bearable. At least until you get to IE. My latest run in with it was a scrolling bug, and I ran into many other issues. However, as much as I complain, I’m probably getting it easy, as when we started work, we decided not to support IE 6, at least until required.
Our reasoning was:

  • Developing for IE6 both independently and consistently with other browsers has a high cost attached to it.
  • IE6’s use rates are declining, and will decline even more by the time we launch (See these statistics for example).
  • Our first versions were mostly required as a prototype to prove our technology to potential investors.
  • As a two-men team, and a one man programming team, we are very low on development resources.

Given my latest bout of UI programming, this choice made me just a little bit happier.

Fractals in 10 minutes No. 5: Sierpinski Chaos Game

Posted on by Leave a Comment

A few years back, I was in some course where they also taught me some Matlab. One of the exercises was to draw the Sierpinski triangle using a method of progressing a point randomly. I was quite surprised at the time, because I thought the Sierpinski triangle was more of an analytical thing: you drew it using inverted triangles.

I wanted to check up on it, and it turns out the method has a name: Chaos Game.
To generate a Sierpinski triangle using this method, one starts with a some point inside the triangle. Then, at each step, the next point is half the distance from the current point to one of the corners selected at random. I think this method of generating the Sierpinski triangle is even easier than the analytical one.

A sierpinski triangle generated using a chaos game

I used pylab (matplotlib) to create this image.
As I usually do, I also wanted to draw it using ascii-art. However, I must confess, I am not satisfied with the result:

              %6
             6*%8
            %8  66
           %6%*6%%6
          6%'    '66
         6866'  '6%86
        %6* 86 '%8 *66
       %**%%'***%6***%%
      8'6            6*8
     6%%*8          %*'*6
    6%6'666        86# 86%
   %%*''**%6      %**''*'%6
  *%8'   '6%6    668'   '#%%
 %% '6' '#*'6%  *% %8' '6''6*
%68%#6#*#68*86*%6#%8%8'6%6*6%*

The code isn’t really good, as I didn’t put much thought into it and just hacked it up. Still, I’m putting it up, and I might improve it someday.

Fractals in 10 minutes No. 4: Mandelbrot and Julia in Ascii Art

Posted on by Leave a Comment

I felt like it’s about time I tackled the Mandelbrot and Julia sets, in Ascii-Art. Heck, the Mandelbrot fractal is on the logo of this Blog! However, being the most well-known fractal, this issue was tackled already, with satisfactory results.

Still, I took the ten minutes required to draw them in Python, using numpy:

def get_mandelbrot(x, num_iter = 10):
    c = x
    for i in range(num_iter):
        x = x**2 + c
    return abs(x)>2
 
def get_julia(x, c, num_iter = 10):
    for i in range(num_iter):
        x = x**2 + c
    return abs(x)>2

“Hey!” you might say, “There’s no loop in here!”. Indeed, with numpy loops can sometimes be avoided, when using arrays. When the expression x**2 + c is applied to an array x, it is applied element-wise, allowing for implicit loops. The actual magic happens in the following function:

def get_board(bottom_left, top_right, num_x, num_y):
    x0, y0 = bottom_left
    x1, y1 = top_right
    x_values = numpy.arange(x0, x1, (x1-x0)/float(num_x))
    y_values = numpy.arange(y0, y1, (y1-y0)/float(num_y))
    return numpy.array([[x+1j*y for x in x_values] for y in y_values])

The result of get_board will be used as the “x input” later on. It should be noted though that while that’s a cute trick this time, it might grow unhandy for more complicated computations. For example, making each element to reflect the iteration number on which it “escaped”.
So, here are the results:

############################   ##############
###########################   ###############
##########################     ##############
#####################                ########
####################                #########
############ #######                 ########
############                         ########
#########                           #########
#########                           #########
############                         ########
############ #######                 ########
####################                #########
#####################                ########
##########################     ##############
###########################   ###############

############################################################
############################################################
############################################################
############################ ###############################
######################### ##   #############################
############## #######           ###########################
######## ##      ###              ##########  ##############
#########  ###        ###         ######       #############
##############       ######         ###        ###  ########
###############  ##########              ###      ## #######
############################           ####### #############
##############################   ## ########################
################################ ###########################
############################################################
############################################################

Here’s the code. (With the usual bsd-license slapped on top of it :)

Small Python Interactive Interface Trick

Posted on by 9 Comments

Not too long ago, I helped someone with some research work, and one of the research tools was also used from the Python interactive prompt.
The interface used was handy enough for development: intuitive, readable, short, and useful. Still, for interactive research it wasn’t handy enough.
To improve the script, I decided to use a trick I heard about a long time ago – using __repr__:

class NoParens(object):
    def __init__(self, obj):
        self.obj = obj
    def __call__(self, *args, **kwargs):
        return self.obj(*args, **kwargs)
    def __repr__(self):
        result = self.obj()
        return str(result)

And using it looks like this:

In [2]: import noparens
 
In [3]: def test():
   ...:     return 4**4
   ...:
 
In [4]: t = noparens.NoParens(test)
 
In [5]: t
Out[5]: 256
 
In [6]: t,t,t
Out[6]: (256, 256, 256)

For research consoles that interact with other programs or devices, such as debuggers and sniffers I found this useful, and made work a bit less annoying.

Open Question No. 1: Persistent Predicates?

Posted on by 6 Comments

Lately I’ve been developing a website. One issue that I’ll probably need to address in the near future is “persistent predicates”. By “persistent predicates” I mean the problem of treating predicates as data.

Consider the following situation: you are developing some big rss reader/aggregator and you want to allow users to specify handling rules. How would you keep these rules in memory, and how would you keep them on disk?
Obviously, this problem was solved before. Just consider email filters, or even packet filters in ethereal.

One way of approaching the problem is implementing simple predicate templates:
“%field contains %s” where field is subject, or body, etc.
Once that is accomplished, you can specify that a “filter” is some combination (for example logical and, or logical or) of multiple predicates. To store this, we’ll have an actual predicate table (or pickle) with their data, and a one-to-many mapping of filters to predicates.

Another option is allowing just some very simple predicates, and a filter will just “point” to (have an id/name of) the required predicate, and the required data. In this option, all data is stored with the filter.

A more complicated solution is to implement some logical serialize-able lanugage (such as the expression trees I used for diStorm or PyKoan). Using this language, the predicates can be very dynamic, and be combined and manipulated programmatically. This solution might be overkill for many projects though.

An interesting issue regarding handling of predicates, is their application to constraint solving. However, this is an issue for a future post. Suffice it to say, that when writing PyKoan I’m using a constraint solver. Since I’m representing predicates with expression trees, the ability to analyze and manipulate predicates is very handy.

Besides looking at existing solutions, I’m very curious to hear other peoples’ opinions. Feel free to write about your preferred solution in the comments.

Starting from Scratch – Part 1

Posted on by 5 Comments

About a month ago, someone I met asked me if I could give him C programming lessons. To protect his privacy I won’t talk about him much, besides saying that he is a serious guy and he doesn’t know programming at all.

The first thing I did was give him a general explanation of what C does, the compilation process and so on. I then showed him a simple program, and showed him how to compile it, and how to run it.
I think the first thing beginners see when they start to program with C is all the “unnecessary voodoo”. For someone just starting to program, “#include <stdio.h>” doesn’t make much sense, and he shouldn’t be bothered with it. The same applies to “int main(void)”. So I just told him to ignore that for now, it would be made clear later on.

The next thing I did was give him a C book, and telling him what to read, and more importantly, what not to read. Teaching books suffer from a kind of “split personality” problem – they try to be both a tutorial and a reference. They also cover things fully the first time around. For example, consider variable types.
A first timer doesn’t need to know about anything besides int. He really doesn’t need to know about size limitations. He shouldn’t be bothered by these issues in the first few lessons.

As I see it, the order of things to learn is:

  • General information such as how to compile, etc…
  • Meaning of variables, and variable assignments.
  • if-else, and then do-while.

So we covered these subjects in the first two lessons, and he was able to write some simple programs, such as compute the average of two numbers, and so on.

We wrote a simple ‘guess the number’ game together, and I used this opportunity to explain if-else by writing conditions for cases such as “warm” or “cold”, “too low” and “too high”. Simple while loops were explained as well: “keep playing as long as the number was not guessed”. We wrote some more programs after that.

As homework, I gave him the following problem:

Write a program to compute an average of numbers.
It will read numbers from the user, until the user gives the number -1.
After it finished reading the numbers, it will print their sum, and their average.
If the average is in the range, print: 0-55: failed, 56-72: could be better, 73-85: ok, 85-95: good, 95-100: excellent.

I knew this will be problematic, and indeed it was. He wrote a program that asked for three grades, and averaged them. It went on asking again until the grades 100, 100, 100 were entered – he thought that was nicer than -1.
Well, a few days ago we sat together, and I understood the problem:

He knew how to write C code, but he didn’t know how to program!

I simplified the problem. I asked him to write (during the lesson) a program that reads numbers from the user until a zero is entered. It will then output how many ones were encountered. He couldn’t write that as well, and that’s no surprise – he had a big concept to understand.

So I told him, let’s play this together. I will tell you numbers, and when I finish, you will tell me how many ones were there. I gave him ten numbers and I noticed he was counting on his fingers!

Grasping this opportunity, I told him to explain exactly what he does. Then I asked him to give me instructions on how to count numbers. The instructions were “read a number onto your left hand”, and “if the number on your left hand is one, set the number on your right hand to be the number on your right hand plus one”. It took some effort for him to understand this, but he did. I then asked him to do the same, but now summing the all of the numbers with the right hand.

I then showed him how I translate these instructions into C. I asked him for the definition of an average, and then, looking at the code on the screen, realization dawned on him. He was amazed – he managed to calculate the average of an unknown number of numbers!

It was amazing for me as well – it’s not often that you get to see someone understand a big concept such as programming.

After the averaging program I asked him to write a counter program – given a number, print all the numbers from zero up to this number. When he got stuck, I asked to turn off the screen, and again give me instructions on how to do the task. That he was able to do. Translating these instructions to C wasn’t that hard, and some 30 minutes later, he had a working program. Success!

Fractal Memory Usage and a Big Number

Posted on by 1 Comment

In a previous post I said I’d talk about 4**(4**(4**4)).
First, about the number. I first saw it mentioned in a math lesson back in high-school, when the teacher wanted to demonstrate estimation abilities.
He wrote it on the board, like so:

4444

and then asked students to estimate how big that number is. Turns out this number is much bigger than most students thought. (For comparison, the number of atoms in the observable universe is 1080.)

Given that this number is so big, it should come as no surprise that computing it will consume all available memory.
What is interesting is the way the memory is consumed:

(It died with a MemoryError just before the next “jump”.)

When I first saw this I was fascinated. To those interested it is generated by the long pow function in Python, implemented in longobject.c. According to the comment there, the algorithm is a left to right 5-ary exponentiation, taken from “Handbook of Applied Cryptography”.
In short, the simpler algorithm “left-to-right binary exponentiation” (used for smaller exponents) repeatedly squares the accumulator, and according to the binary digits of the exponents, multiplies it by the base. 5-ary exponentiation basically does the same thing, but in each iteration it ‘eats’ five digits of the exponent instead of just one.

It might be very interesting to study algorithms and code according to their memory usage. Once at work I used a similar memory usage graph to optimize the memory usage of some algorithm that was eating too much memory. I don’t remember the details as it happened a few years ago, but I do remember that I recognized the “type of the memory eating”, which helped me to narrow the problem down to a specific area of code, where indeed the problem was located. (I consider this a case of programming-fu :)

Notes:
1) The reason I’m talking about Python is because it has arbitrarily sized longs built-in.
2) This graph was generated using Windows’ task manager. On my Ubuntu machine it looks quite different, almost a straight line. Any guesses why?

My Bad Memory, High Load, and Python

Posted on by 1 Comment

About a month ago the new Ubuntu 8.04 was released and I wanted a clean install. I downloaded an image and burned it to a CD. Just before installing, I tried “check CD for defects” and found a few. Turns out (*) this was because of bad memory – and memtest confirmed it.
So I went to the shop, replaced the bad memory, and also bought two new sticks. I went home to install the new Ubuntu, and after the installation, Firefox crashed. After rebooting back to memtest, I saw this:

memory errors in memtest

Back at the computer shop, they asked me to reproduce the errors. Just firing up the computer and booting directly into memtest didn’t seem to do the trick, so I suspected that I had to overwork my computer a bit to reproduce this.

Since I was at the lab, I didn’t want to muck around too much.
So I thought, “what’s the quickest way to give your CPU a run around the block?”
That’s right – a tight loop:

while True:
    pass

However, this snippet doesn’t really play with the memory.

The next simplest thing to do, that also jiggles some ram is the following (and one of my favorites):

In [1]: x = 4**(4**4)
In [2]: y = 4**x

I will talk about this peculiar piece of code at a later post.

In any case, this snippet also didn’t reproduce the error. It is also quite unwieldy, as it raises a MemoryError after some time. Later at home I tried two more scripts.
The first is a variation on the one above:

x = 4**(4**4)
while True:
    try:
        y = 4**x
    except MemoryError:
        pass

I ran a few of those in parallel. However, my Ubuntu machine actually killed the processes running this one by one.

The second is smarter. It allocates some memory and then just copies it around:

import sys
import copy
megabytes = int(sys.argv[1])
 
x1 = [["a"*1000 + str(i) for i in range(1000)] for j in range(megabytes)]
while True:
    x2 = copy.deepcopy(x1)

After both of these scripts didn’t reproduce the problem and it still persisted arbitrarily, I returned the computer to the lab. Turns out that the two replacement sticks and the two new sticks weren’t exactly identical, and that was the cause of the problem. So now my memory is well again.

As for the scripts above, I once wrote a similar script at work. I was asked to help with testing some software in some stress testing. The goal was to simulate a heavily used computer. A few lines of Python later and the testing environment was ready.

Footnotes:
(*) – Finding out that it was a memory issue wasn’t as easy as it sounds. I didn’t think of running memtest. I checked the image on my HD with md5, and the hash didn’t match. I downloaded a second image, and again the hash didn’t match. I checked twice.
At this point I was really surprised: not only the second check didn’t match the published md5, it also didn’t match the first check. Some hours and plenty of voodoo later, a friend suggested running memtest, and the culprit was found.

PyKoan – The Logic Game

Posted on by Leave a Comment

As you can probably tell, I’m back from my undeclared hiatus. I’ve got lots of stuff to talk about, and I’ll be starting with PyKoan, one small project I’ve been working on lately in my spare time.

A few weeks ago I stumbled upon an article in wikipedia, regarding a logic game. This game fascinated me, especially because of the “Godel Escher Bach” connection. Quoting from Wikipedia:

Zendo is a game of inductive logic designed by Kory Heath in which one player (the “Master”) creates a rule for structures (“koans”) to follow, and the other players (the “Students”) try to discover it by building and studying various koans which follow or break the rule. The first student to correctly state the rule wins.

As it happens I’m also taking a mathematical logic course this semester. Having read about the game, I wanted to write a similar computer game. Hence – PyKoan.

PyKoan is a game where the goal is to discover some logical rule, for example, “For each x holds x%2 == 0”. This rule is applied to a koan – a list of integers. An example koan that “has Buddha nature” (follows the rule) is [0,2,8]. One which doesn’t is [1].

To implement this idea, I wrote an implementation of an expression tree very similar to the one used in vial, but with a different implemented language. I also did some experimentation with the design. Since I’ve been talking a lot about expression trees without giving a full explanation, in a future post I’ll write about the implementation used in PyKoan.

So far I didn’t code a lot of the game, just the expression tree framework, and a simple rule builder. When using Python’s interactive prompt, one can get a taste of how the game might feel:

In [19]: r = rulegen.create_rule(rulegen.easy_grammer, rulegen.easy_grammer_start)
 
In [20]: r.eval([])
Out[20]: False
 
In [21]: r.eval([0])
Out[21]: False
 
In [22]: r.eval([1])
Out[22]: False
 
In [23]: r.eval([2])
Out[23]: True
 
In [24]: r.eval([2,2])
Out[24]: True
 
In [25]: r.eval([2,2,3])
Out[25]: True
 
In [26]: r.eval([3])
Out[26]: False
 
In [27]: r.eval([4])
Out[27]: False
 
In [28]: print r
x exists such that x == 2

Here is how I would generate such an expression manually:

In [3]: from exptree import exps
 
In [4]: exps.Exists('x',exps.Eq('x',2))
Out[4]: exps.Exists(exps.Var(x), exps.Eq(exps.Var(x), exps.Imm(2)))
 
In [5]: print _
x exists such that x == 2

The game has many interesting possibilities for research, for example, computer players. Other possibilities include “just” guessing koans (not the rule itself), creating interesting and playable rules, and so on. There’s a lot to do.

This time, instead of just publishing the (unfinished) code, I decided to do something different. I’ve opened a space in assembla, with public read access. I’m opening this project for participation: if you want to join then leave a comment, or send me an email.

(Since Assembla seems to be going through some connectivity issues right now, here’s a link to a copy).