503 Service Unavailable

2007-04-27

Love and hate with Kommander

Filed under: Programming — rg3 @ 21:19

Note: this article was written on 2007-04-27, and the circumstances may probably change in the future.

I was about to write a very positive story about Kommander, a development tool from KDE. However, I think I’m only going to do so during the first lines and in the end I’m going to write a pretty long rant about it. Not because I think it deserves being bashed in public. Kommander is, IMHO, a great idea which needs a lot of technical improvements. The core idea is very good, but Kommander has many problems and bugs that need to be solved if it wants to be much more useful. I am currently using Kommander for a couple of things and fully acknowledge its power. There’s also a Kommander scripts section at http://www.kde-apps.org.

Core idea

Kommander is composed of two main programs. kmdr-executor is the program that runs Kommander scripts. kmdr-editor is the one that lets you create those scripts. A Kommander script is an XML file that describes something to be run. When you launch kmdr-editor, you find a tool similar to the Qt designer, if you know it, but simplified. The idea behind Kommander is that you must take into account 3 different aspects of your application. First, the editor lets you create dialogs (that is, windows) with widgets (buttons, labels, checkboxes, line edits, text edits, etc). Then, you must specify associations between events and actions. The events come from the different widgets, like a specific button being clicked. The actions are also associated to other widgets, because widgets can perform actions. In Qt, this is called signals and slots, and those are the terms Kommander uses. Finally, the core of those actions is a very simple programming language that lets you manipulate the application widgets by their name (which you set, like MyLovelyCheckBox), setting their text and/or state, perform basic operations with text strings, doing basic flow control (if, for), and run programs and scripts in any language, taking their output and manipulating it. That’s what makes Kommander powerful. You can take the texts and selections in the widgets, use them as parameters to run scripts in arbitrary languages (shell, awk, perl, python, php…) and process the output of those scripts to use them in other widgets. Kommander acts as a powerful glue that binds all those actions together in a GUI.

Problems

Kommander Handbook (F1)

The main problem with Kommander is its documentation and specially its handbook. The introduction is very hard to understand for programmers and non-programmers, and you don’t get to see an example of what Kommander is about because the tutorials, which should appear later in the documentation, are missing. It contains a lot of philosophy that should probably be put in a different section.

There are also contradictions present in the project goals and features, in my humble opinion. Quoting from the introduction:

The primary objective is to create as much functionality as possible without using any scripting language.

Yet the power of Kommander, as mentioned before, is being able to run scripts in many differente languages and bind them all together. This is acknowledged later in the introduction:

By being language neutral and allowing a Kommander dialog to be extended by using any scripting language Kommander positions itself in a unique position for wide spread adoption. Multiple script languages can be used in a single dialog and applications can be taken over by people using a different language than the original developer and gradually converting and extending it. New widgets and features can be instantly leveraged by all available languages.

In fact, the Kommander programming language (the one you use to code “actions”) is very simple and limited. If they wanted to be able to create as much functionality as possible without using any scripting language they should make the internal language powerful, don’t you think? Furthermore, Kommander tries to appeal to novices and non-programmers:

We hope that Kommander begins to get the developer support and recognition required to achieve the potential it offers. Our end goal is to make Kommander useful for novice users to extend and merge their applications.

However, no novice user is going to use Kommander if it has that lack of documentation and tutorials, and if the power resides in binding together scripts in arbitrary languages, the user will need to know one or more scripting languages to do something useful, and that’s not very novice-friendly.

Despite all that, I think Kommander is going the right way. I don’t mind contradictions between the project goals and the project state as long as I like the project state, obviously.

I think Kommander developpers need to urgently rewrite the introduction and create an easy to follow tutorial so people will see how to create dialogs, use layouts in them, connect signals and slots and use different scripting languages, as well as the Kommander language, to do something useful. This way, us Kommander newbies could easily see what a Kommander program is supposed to look like, according to them.

Vocabulary

The names the Kommander developpers have chosen for some components are unexplained and unfamiliar to programmers. In Kommander, words with special meanings are preceded by the @ character. For example, you have @if, @endif, @exec, @String.replace() and also widget names like @MyLovelyCheckBox. These are called specials and can refer, as you see, to reserved words, widget names, function names, etc. However, the name special isn’t used in any mainstream language that I know of. Please, mail me if I’m missing some important language with specials. Also, the introduction description of them is very poor.

Widgets have two types of text associated to them. One is the widget text, which is the content of the widget. For example, a button label like “Click me” or a text you have introduced in a line edit. On the other hand, widgets can “perform actions” to react upon events, and these actions are described in a special scripting language, like I mentioned before. These scripts are called Kommander text and that name is confusing because everytime you want to talk about a widget and modifying its text using Kommander text you end up talking about text and nobody knows what you’re refering to. This happens in the handbook introduction. I would have chosen another name like Kommander scripts, Kommander actions, or anything that doesn’t have the word “text” in it.

Obsolete documentation

The documentation is also plain wrong at some points because Kommander has changed and some things can be no longer done the way they’re described in the documentation. So it’s not only imcomplete, but sometimes wrong.

Key components go undocumented

Many key aspects and components of Kommander are completely undocumented, despite the fact that they should be the first ones to get documentation. Most widgets can have two Kommander texts. One is called the default Kommander text and the other one is called the population Kommander text. The one you will need to use more, I suppose (due to the lack of documentation I can’t be sure of what I’m saying), is the population Kommander text. However, when you edit the Kommander text of a widget, you have to manually choose to edit the population Kommander text, because the initial option is to edit the default Kommander text. It’s funny, because I still don’t know what the default Kommander text in a line edit is supposed to do or when it is supposed to be run. The importance of the population Kommander text is mentioned in the handbook introduction:

Signals and Slots is a little less intuitive to a new user. It is under review for how we process things in the first major release. These offer a limited event model for when a button is pushed or a widget is changed. Combined with “Population Text” it is rather powerful.

Furthermore, the usage of the population Kommander text is very confusing, and it took me a good amount of minutes to figure out what I was supposed to do with it, and let me explain the confusion in detail. Let’s suppose you want to create a simple dialog with a read-only line edit (the user can’t modify its contents) that displays your kernel version. The kernel version can be obtained from running uname -r. You create a dialog and place a line edit in the middle. You mark the dialog as read-only in the properties panel to the left. You then associate the widgetOpened dialog event to the line edit populate action, so that the line edit is populated with the kernel version when the application starts. How do you get and set the line edit text? The @exec special is the name of a function that runs a program and gets its output, so you need to run @exec(uname -r). Suppose you called your line edit KernelVersionEdit. Widgets have a set of properties that can be used to read or set its contents. For example, line edits, among other widgets, have a property or method called setText, which receives a text string. By invoking the following, you can achieve the intended effect: @KernelVersionEdit.setText(@exec(uname -r)). Or that was what I thought, because it turns out the population Kommander text has to contain a string or something that returns a string, which will be used to fill the widget contents, like @exec(uname -r). The other full expression won’t work, because its execution won’t return a string. When I tried to create my first application I thought something wasn’t working, and I didn’t know if it was my mistake or a program bug. I didn’t know if I was right assuming that when the populate action is associated with an event, the population Kommander text was executed. I finally got it running by specifying only @exec(uname -r) as the population Kommander text, and I don’t know if I had read it somewhere or if I was simply trying alternatives. I swear I don’t remember, but discovering it was painful. If the handbook had a tutorial, this wouldn’t have happened.

Another key component is the script widget. It’s a special invisible widget that has an execute action, and you can bind it to events. You can write things to do in the default Kommander text for the script widget, then bind an event to the execute action and it will do those things. The previous example could have used a script widget in addition to the line edit. I could have written @KernelVersionEdit.setText(@exec(uname -r)) in its default Kommander text and bind the widgetOpened event to its execute action, achieving the same effect. The script widget is a key component when the action involves more than just setting some widget text. For example, in one of my tests I created a GUI for the locate command. It lets you specify a regular expression to search, then launches locate with that regular expression and sends the result to a listbox, and if you doubleclick on any entry, it will launch kfmclient exec with the selected file or directory. It’s very neat, but locate can take some seconds to run, and the program appeared to have frozen, so I decided to add a status bar that contains “Searching…” while locate is being run, and after it has finished it contains “Found [x] files.”, where [x] is the number of rows in the listbox (there’s a listbox property to get the number, very easy). However, that group of actions need a script widget, or otherwise it can’t be done. The script widget isn’t mentioned in the documentation at all. Now, I ask, wouldn’t it be better if the populate action for the widgets would simply run their contents, including some setText calls if the user wants to? You wouldn’t have to use the script widget, and I wouldn’t have hit the problem in mentioned in the previous paragraph. Maybe people don’t usually hit that problem and it was just me. An issue with this suggestion is that, while the event is attached to the action of a widget, you could modify any other widget from that action. This is slightly unelegant.

Other problems

The only way to evaluate arithmetic expressions is to use the @expr special, but the documentation does not mention if it’s floating point or integer, or which operations are supported. I suppose the basics (+, -, *, /) are supported, but what about others? Experimentation is the only way to find out these things.

The @if special lets you execute some things if a condition is met, but it doesn’t have an @else counterpart. The boolean checks you can perform aren’t mentioned either. You’ll have to find out trying. Not having @else may be due to the lack of a grouping character (like the curly braces in many languages). This could be solved by introducing those grouping characters or by specifying in the @else and @endif the condition of the @if block they belong to (users of CMake will recognize this approach). Some other constructions use the @endif special as terminator, eventhough they’re not if blocks. Wouldn’t @endfor make more sense? Or something like bourne shell, where both the beginning and the end are marked with do and done.

The usage of double quotes to indicate strings is undocumented, as well as the escape sequences. Kommander interprets everything as strings, like for example mIRC does, so instead of @Somespecial(“The string parameter”) you use @SomeSpecial(The string parameter). This creates unneeded problems, in my humble opinion, and leads to confusing situations. How do you indicate a single space or end of line as argument, without receiving a syntax error? The answer is using ” “ and “\n”, quotes included, as far as I have seen.

Despite its orientation to manipulating strings and the output of programs, there’s no easy way of joining two strings without spaces between them. If you have two line edits, and one of them contains Hello and the other one World, you can join them with something like @LineEdit1.text @LineEdit2.text and get Hello World, but what if you want to get HelloWorld? I use the hack of putting each one of them in one line and calling @String.remove() on that, with “\n” as the second argument.

In a couple of places in the documentation the format a string must have is mentioned using a description like key\tvalue\n. I doubt a novice user will know what \t or \n mean, and if, on top of that, you put that description in italics, the backlash may end up looking like a vertical bar, making the description even more confusing.

I haven’t found a simple way of processing lines as they are received. Suppose you want to create a GUI for a program that outputs a completion percentage as it’s working, and you want to use it to create a progress bar. @exec returns all the output when the program finishes, but you can’t process the program output while it’s working. Using @forAll doesn’t solve the problem either. Is there a way to do this? If not, how can you use the progress bar widget in a useful way?

There are some bugs processing comments (lines that start with the # character), because sometimes I have commented lines of code to try a couple of alternatives and the programs have gone wild, doing weird things. These problems were solved as soon as I removed the comment line. I’m sure it was not my fault because I tried this several times, putting the comment line back again, even writting it again manually, and it was obvious the comment line was the source of the problems.

Conclusions

Despite all these problems, Kommander looks promising and I recommend you to experiment with it. Try not to get very frustrated when things don’t work and avoid doing complex things. You’ll find you are able to create very useful GUIs in a handful of minutes. You can easily use Kommander to display information coming from several programs or scripts, and create launchers for command line programs. I created a couple of GUIs for the cifras and letras programs and they work very well.

2007-04-21

Semantics of Python variable names from a C++ perspective

Filed under: Programming — rg3 @ 21:54

If you are going to start programming in Python and come from languages like C or C++, there are a couple of things you should know about variable names. In Python, variable names do not have the same behaviour as in C++. Part of this is clarified in the Python documentation, but I’ll try to give specific examples of things that work and don’t work as you may expect, and why.

All variables are references

Yes, that’s right. In Python, all variables are references. In C++, a reference is a type of data that behaves like a pointer but that has “normal” variable syntax. Other languages coined the name alias for this type of data. In other words, given the following C++ code:

int foo = 3;
int &bar = foo;

When creating the reference to int named bar, both foo and bar are names for the same variable or object. If you assign a value to bar, foo will see the change. They’re names for the same integer. References in C++, however, can’t be modified. You can’t make a reference start referencing a different object. Some people would argue that it’s because there’s no syntax to perform that operation. In Python, however, a reference can be modified. In fact, that’s what assignments do, because all variables are references.

For a Python beginner, it’s difficult to notice that all variables are references. That’s because they can be modified and because Python has two classes of objects: mutable objects and immutable objects. Boolean values, integers, floats and strings, among others, are immutable. A C or C++ programmer may write the following Python code:

a = 1
b = 2
c = 0
c = a + b

And they may not perceive that it’s all references. They have C++ in mind, and think those variables are all integers, and that when c = a + b is executed, the value of c (zero) is being overwritten with the value of a + b, and that’s not the case. The value of c can’t change because an integer is immutable, and c is a reference. This is what’s happening:

  1. A new integer is created with value 1. Variable a is a reference to that object.
  2. The same for integer value 2 and b.
  3. The same for integer value 0 and c.
  4. Due to the plus operator, a new integer is created with value a + b, and c is changed to refer to or point to that new object. The previous integer it was referencing (with value zero) can be discarded.

However, other data types such as lists or dictionaries are mutable, and they store references to other objects. Let’s see some examples of this variables-as-references interpretation.

Examples

Creating aliases for the same object:

>>> a = [1, 2, 3]
>>> b = a
>>> a.append(4)
>>> b
[1, 2, 3, 4]

Proof that lists store references too, and not the objects directly (this appears in the Python tutorial):

>>> a = [1, 2, 3]
>>> b = ['foo', a]
>>> b
['foo', [1, 2, 3]]
>>> a.append(4)
>>> b
['foo', [1, 2, 3, 4]]

Dictionaries store references too:

>>> a = [1, 2, 3]
>>> b = dict()
>>> b['foo'] = a
>>> a.append(4)
>>> b['foo']
[1, 2, 3, 4]

Objects aren’t copied when returning from functions either:

>>> def return_it(whatever):
...     return whatever
...
>>> a = [1, 2, 3]
>>> b = return_it(a)
>>> a.append(4)
>>> b
[1, 2, 3, 4]

Not even from lambda expressions:

>>> a = [1, 2, 3]
>>> b = (lambda x: x)(a)
>>> a.append(4)
>>> b
[1, 2, 3, 4]

And, of course, objects can be modified inside functions:

>>> def append_four(lst):
...     lst.append(4)
...
>>> a = [1, 2, 3]
>>> append_four(a)
>>> a
[1, 2, 3, 4]

However, you can’t modify them when they’re immutable. In this example, a function receives a copy of the reference. Inside the function, this local copy is changed to refer to another object, but the original reference doesn’t change.

>>> def add_one(some_int):
...     some_int += 1
...
>>> a = 1
>>> add_one(a)
>>> a
1

The case above may mislead a C or C++ programmer. If some_int is a reference and you perform a += operation, you may have expected to see the integer changed after calling the function, because you may be used to the C interpretation that the += operator modifies the integer in place. However, this is similar to the c = a + b example we used previously. Inside the function, a new integer is created as the sum of some_int and 1. some_int is then changed to refer to this new integer object. However, some_int is the function’s local copy of reference a, and changing its reference value won’t change the reference value of a. The integer object IS NOT being modified in place. Integers are immutable.

One last case that gave me problems in the past is the following: you can create a list by replicating a reference. For example:

>>> a = [0] * 3
>>> a
[0, 0, 0]

What’s happening here? First, a new integer object is created to hold the value 0. This reference is stored inside a list of one element. Then, this reference is replicated 3 times (or 2, to be precise) and a new list is created, consisting of 3 references pointing to the same integer object. If we change a list element, it will work as you expect:

>>> a[0] += 1
>>> a
[1, 0, 0]

This works because integers are immutable. As soon as you try to repeat this with mutable objects, problems appear. For example, I expected this to work when trying to create a 2×2 matrix:

>>> a = [[0] * 2] * 2
>>> a
[[0, 0], [0, 0]]

That’s apparently correct. The only problem is that it’s not, or at least not for what I expected:

>>> a[0][0] = 1
>>> a
[[1, 0], [1, 0]]

If you’ve understood up to here, you’ll know why. The “matrix” (outside list) contains 2 references to the same list object. When we change something in that list, it’s reflected in every row. How do you create a 2×2 matrix of zeros in Python? You may try to use the slice operator, which creates a new list. In particular, [:] creates a new list object that holds the same sequence of references as the original list:

>>> a = [[0] * 2][:] * 2
>>> a
[[0, 0], [0, 0]]
>>> a[0][0] = 1
>>> a
[[1, 0], [1, 0]]

So no, you are not creating a copy each time. I use the following method:

>>> a = [[0] * 2 for x in xrange(2)]
>>> a
[[0, 0], [0, 0]]
>>> a[0][0] = 1
>>> a
[[1, 0], [0, 0]]

This creates new lists in a loop. Suggestions for easier or different methods are welcome. Use the contact link if you wish.

2007-04-17

Generating combinations and permutations in C++

Filed under: Programming — rg3 @ 20:12

With all these articles about the Cifras y Letras show, from time to time people seem to be hitting this website searching for C++ code that generates permutations and combinations, so this post is dedicated to every casual reader that is desperate to find out how to accomplish that task in C++. It’s very easy, but it seems some people are unable to create such an algorithm, or are so limited in time that prefer to use Google instead of writting 50 lines of code.

I apologize in advance if someone doesn’t like the following code, or thinks I should’ve used templates or object oriented design or whatever design criteria you feel a program must meet to be considered good, and I hope it’s clear enough for the people I mentioned in the first paragraph. First, the code. Then, the analysis.

Combinations

Let’s suppose you have a set of N elements in a vector and want to find all the combinations of size M (M > 0 and M <= N). What do you need to do? Easy. Start by taking one element as the first one. Then, find a second element to the right of the first one, then a third element to the right of the second one, etc. Follow this method until you’ve chosen M elements. Example with elements (a, b, c), finding the combinations of two elements. The first one can be a, b or c. If it’s a, the second one can be b or c (for combinations ab and ac). If it’s b, the second one can only be c (forming bc) and if the first one is c there are no elements to its right to choose a second element. Hence, the combinations are ab, ac and bc. This isn’t rocket science.

Any algorithm that performs this task will be valid. Mine’s recursive, because I consider it easier this way. You have to search elements to the right of the previous one, and have to perform this task with M depth, so I think it calls for a recursive algorithm. Every recursive algorithm can be algorithmically transformed into an iterative algorithm, so feel free to do the conversion if you’re an iteration fan.

My test program has a recursive function, a wrapper function to simplify doing the initial call, and a main program that tests the algorithm by extracting the combinations of 3 elements out of 5. I will analyze only the recursive function.

void combinations_recursive(
  const vector<char> &elems,
  unsigned long req_len,
  vector<unsigned long> &pos,
  unsigned long depth,
  unsigned long margin
)
{
  // Have we selected the requested number of elements?
  if (depth >= req_len) {
    for (unsigned long ii = 0; ii < pos.size(); ++ii)
      cout << elems[pos[ii]];
    cout << endl;
    return;
  }

  // Are there enough remaining elements to be selected?
  // This test isn't required for the function to be
  // correct, but it saves futile calls.
  if ((elems.size() - margin) < (req_len - depth))
    return;

  // Try to select new elements to the right of the last
  // selected one.
  for (unsigned long ii = margin; ii < elems.size(); ++ii) {
    pos[depth] = ii;
    combinations_recursive(elems, req_len, pos, depth + 1, ii + 1);
  }
  return;
}

Sorry for the indentation as I’m trying to keep it narrow. The first function argument, elems, is a vector containing N elements. As you see, I chose characters as elements, just like in the examples above. The second argument, req_len, is the requested combination size or length (that is, M). pos is a vector of size req_len that will hold the positions or indexes of the chosen elements. The depth argument indicates how many elements we’ve chosen so far, that is, the recursion depth. Finally, the margin argument indicates the first position to start looking for a new element (the left “margin”). Remember we have to choose elements to the right of the last chosen one.

Simple as that, the first block checks if we’ve chosen enough elements and prints the elements in the chosen positions. If we wanted to store the combination instead of printing it, we could use one output argument, for example.

The second block checks if there are enough remaining elements to the right. In the example we put, when we chose c as the first element, there were no elements to its right to be chosen as the second one. This is a generalization of that test to stop as soon as possible. As the comments say, the function works if you remove it. However, it can be slower. This check can also be integrated into the loop condition in the third block, if you want.

The third and final block chooses one more element starting from the margin, iterating until the end of the vector, and recursively calls itself, indicating one more depth level, and setting the margin to one position to the right of the current chosen position.

The initial call must use depth 0 and margin 0.

Combinations with repetitions

I won’t spend much time with this. If elements can be repeated, you have to remove the check from the second block because there are always enough remaining elements. Finally, instead of choosing the next element strictly to the right of the last chosen one, you can start the search in the same position. This is the result:

void combinations_r_recursive(
  const vector<char> &elems,
  unsigned long req_len,
  vector<unsigned long> &pos,
  unsigned long depth,
  unsigned long margin
)
{
  // Have we selected the number of required elements?
  if (depth >= req_len) {
    for (unsigned long ii = 0; ii < pos.size(); ++ii)
      cout << elems[pos[ii]];
    cout << endl;
    return;
  }

  // Try to select new elements in the same position or
  // to the right of the last selected one.
  for (unsigned long ii = margin; ii < elems.size(); ++ii) {
    pos[depth] = ii;
    combinations_r_recursive(elems, req_len, pos, depth + 1, ii);
  }
  return;
}

Note how I removed the second block and used ii instead of ii + 1 as the margin argument.

Permutations

Permutations are a bit trickier, but not much. After we’ve chosen one element, we must choose the new one from the whole vector. Supposing we’ve chosen b as the first element, a could be selected as the second one. Because we may have already generated ab, but we still have to generate ba. The search will start at position 0, and we can remove the margin argument. However, we must skip elements that have already been chosen. There are several ways to do this. For example, we could check the current candidate position ii is not present in the first depth elements from the pos vector. However, for the sake of being somewhat fast and making the check easier, we will use a bool vector that will indicate if a position has been already used or not, and we’re going to skip already used positions. This is the code:

void permutations_recursive(
  const vector<char> &elems,
  unsigned long req_len,
  vector<unsigned long> &pos,
  vector<bool> &used,
  unsigned long depth)
{
  // Have we selected the number of required elements?
  if (depth >= req_len) {
    for (unsigned long ii = 0; ii < pos.size(); ++ii)
      cout << elems[pos[ii]];
    cout << endl;
    return;
  }

  // Try to select previously unused elements.
  for (unsigned long ii = 0; ii < elems.size(); ++ii) {
    if (used[ii])
      continue;
    used[ii] = true;
    pos[depth] = ii;
    permutations_recursive(elems, req_len, pos, used, depth + 1);
    used[ii] = false;
  }
  return;
}

Note how we start the search at the initial position, we skip used elements, mark the current position as used and store it in the pos vector as we did previously. We only need to remember to clear the used flag after the recursive call, before selecting another element. Obviously, the used vector must have at least the same size as the elems vector and in the initial call all of them must be set to false.

Conclusions

That was easy, wasn’t it?

2007-04-16

Cifras y Letras (3)

Filed under: Programming — rg3 @ 10:20

Some days ago I was searching for an old CD and instead of finding what I was looking for, I found another old CD with a digital Spanish dictionary. I didn’t even remember I had it, but it quickly prompted me to finish the letters program for the TV show. The dictionary was one of those typical Windows applications distributed in a CD that installs a minimum amount of data from it to your hard drive and runs from the CD itself.

I immediately had a look on the CD contents and spotted a .MDB file quite big in size. Kexi was unable to import the data, and OpenOffice.org didn’t appear to give me good results opening the database either. I waited some more days until I had access to a computer with MS Office installed, and opened the file with MS Access. To my surprise, the result was similar. The database appeared to contain a single table, where each row contained a word id, a definition id and the text of the definition, but the words themselves were nowhere to be found. Furthermore, the definition text appeared to be garbage. I didn’t bother to investigate, but maybe their bits were inverted, or the characters rotated like in ROT13. In any case, I lost hope and discarded finishing the program.

However, some days later, while watching TV I had the idea to run a recursive grep on the CD files just in case the words were stored in cleartext in a separate file. I didn’t have much hope, but the words did turn up. They were stored in a different file, using the ISO-8859-1 charset. The file was quite big and mostly filled with space characters. Each word seemed to use a fixed chunk of 65 bytes. I ran an on-the-fly Python program directly from the Python interpreter to split the file into chunks, strip whitespace and encode its contents in UTF-8. Five minutes later I had stored the word list into a text file called palabras-utf8.txt with one word per line. That file is distributed inside letras.zip. I needed to hand-edit that file using VIM to obtain a final list of words. The work mostly involved removing accents, words that start with a bracket that seemed to indicate “unofficial” words, split alternate spellings of words into different lines and some more minor changes. The final result is stored in palabras-utf8-final.txt, also included in the archive.

As you can see, many of the lines in the final file have alternate endings for different genders, and optional suffixes that modify the word gender. A file like that one can be processed with the script build-db.py included in the archive, that will create a database of words by processing that file. This database is created using the shelve Python module (yes, I know it was a nice situation to use sqlite3 but I wanted some backwards compatibility with Python 2.4). It uses the method I mentioned in the previous Cifras y Letras post. It takes each word, sorts its letters and associates the word, maybe along with other words, with its corresponding sorted letters combination. For example, the combination aacs corresponds to the words casa (house) and saca (bag). Given 9 letters, you form the combinations of 9 letters (there’s only 1), the combinations of 8 letters (there are 9), etc. You sort the letters of each combination and use them as keys to access the database, so it returns the list of words. As I explained in the previous post, this is much faster than forming every permutation and checking if it’s in the dictionary. In this case, preprocessing the database and organizing it once allows us to be much more efficient when we use it. The script build-db.py creates the database this way and handles the alternative endings and word suffixes, introducing both variants in the database. If you want to use a different text file and a different database name, those can be changed in the first lines of the script.

Finally, when you’ve run build-db.py and you have your palabras.db file, use letras.py to search for words. It needs two parameters: a sequence of letters and a minimum length for the words in the result. Internally, you can and may need to tune the terminal charset, that should probably be ‘iso-8859-1’ if you’re under Windows or probably ‘utf-8’ if you’re using one of the most popular Linux distributions. This charset and the database name can be changed in the first lines of the script. Example of use:

$ ./letras.py ananedros 7
orensana (8)
senadora (8)
rondana (7)
saneado (7)
arenosa (7)
sanador (7)
endosar (7)
senador (7)
sondear (7)
asadero (7)
darsena (7)

It’s worth mentioning that the database lacks gerunds and any past participles that aren’t used as adjectives. These are allowed in the TV show, so don’t be surprised if someone finds a longer word this way in some particular situations. Due to the lack of verb markers (in Spanish, there are may words ending in -ar, -er and -ir that aren’t verbs) and the existance of irregular verbs, I can’t generate gerunds and past participles automatically.

Both build-db.py and letras.py are less than 100 lines long, and some of them are comments. This gives you an idea of the game simplicity. The code and the word lists are released to the public domain.

2007-04-03

Software suspend under Linux

Filed under: Hardware,Software — rg3 @ 22:45

Suspending a computer means to turn it off in a special way, so that when you power it on again it resumes what it was doing, like nothing had happened. There are two common ways of suspending a computer: suspending to RAM and suspending to disk.

Suspend to disk

Suspending to disk is the “simplest” way of suspending a computer, also called “hibernation”. The operating system kernel stops what it is doing and writes the contents of the system RAM to a specific place in the hard drive. When a computer is running, the system memory contains all the information needed for it to run. It contains the kernel image, the kernel data structures that allow programs to run, the state of the programs currently running on the computer, etc. To sum up, a lot of data that represents the state of the computer at a given moment. By writing those contents to the hard drive, the operating system is writing a snapshot of the system in that moment to a safe place. After writing that snapshot, if proceeds to power off the machine in the same way it normally powers off.

There’s no need for special or unusual hardware support as far as I know (please, mail me if I’m wrong). If you can power on and off normally, you should be able to suspend to disk, provided you have enough space in your hard drive to store the RAM image and your OS kernel has suspend to disk support. When the computer powers on again, it checks if there’s a saved image. If there is, it restores the contens of that image to the system RAM, and continues execution at the point it left. Like if you had never turned it off. It’s not that simple because there are some things that won’t work after resuming. For example, if you suspend for a long time, which is usually the case, the network connections probably won’t work after resuming and will need to be reestablished. In other words, the computer can deceive itself and assume it’s not been powered off, but other computers will probably notice. There are some more issues. For example, when the computer boots again, it’s a normal boot up to the point when the operating system kernel starts restoring the image. First comes the BIOS, then the bootloader loads the kernel and the kernel starts booting, which is when it checks if there’s a saved image. But… what if you had upgraded the kernel and when it boots again, the new kernel is loaded? Or what happens if you change some hardware while the computer is suspended? Or what if you boot another operating system, maybe from a live-CD, and touch the filesystems or repartition your hard drive? A disaster. In many of these cases, as the Linux software suspend documentation says, you can “kiss your data goodbye”. So be careful and always power off or reboot normally when you want to do these things. This is specially critical about kernel upgrades, which is the most common operation from those mentioned. After installing a new kernel, reboot immediatelly to load it.

That said, many Linux distributions have suspend to disk preconfigured and handle that common kernel upgrade case. When you install a new kernel, maybe a “flag file” is created somewhere and when you try to run one of the suspend-to-disk scripts, they detect the flag file and refuse to suspend. In any case, it’s always a good idea to reboot after installing a new kernel. Furthermore, if you have installed it, you want to use it, don’t you?

To suspend to disk under Linux you don’t really need any special software package as long as your kernel has been passed the appropriate parameters on boot (resume=…) and you do the right thing. Essentially, you need to specify a swap partition to save to and restore the disk image from, and then run a couple of things:

echo shutdown >/sys/power/disk
echo disk >/sys/power/state

But there are more ways to do it (s2disk), and you probably need to run a couple of things before and after suspending. This is because, like I mentioned, not everything is restored properly. Most people would want to bring down the network interfaces before suspending and bring them up after resuming, etc. Also, some kernel modules and programs don’t like suspending (proprietary NVIDIA kernel module maybe?), and you may also need to reload and relaunch those kernel modules and programs. For example, my Acer laptop has a winmodem that uses the snd_intel8x0m kernel module and the slmodemd daemon. They need to be reloaded, so I have to kill the daemon, unload the module, reload the module and restart the daemon when I suspend. For this reason, and because I use Slackware and need to handle all of this myself, I created a short (24 lines) suspend-to-disk shell script that automates everything, and it’s the one I call if I want to suspend to disk.

If, instead of the vanilla kernel software suspend to disk you’re using Suspend2, you should probably configure your hibernate script and use it, because it may be easier. Remember to read your distribution manual and see what they have done for you and how everything is set up. This way you’ll know what you need to run if you want to suspend to disk.

In terms of time and power, suspend-to-disk isn’t specially fast, but it’s worth using it unless you can suspend to RAM. When the computer powers off, it really powers off. You may even unplug it if you want, and it won’t drain the batteries in case it’s a laptop computer. The time it takes to save and restore the image on disk depends on several factors, which are usually your disk speed, your CPU speed and if you’re compressing or encrypting the image or not. Eventhough it sounds weird or unintuitive, it’s usually faster to compress the image. This is because in modern computers, the CPU can compress the image faster than the hard drive can write it, so compressing it will use more CPU power but will take less time, because the amount of data to write will be greatly reduced. The same applies when resuming, because the CPU will be able to decompress the image faster than the hard drive will read it.

It will probably take around 10-20 seconds to power off and between 20 and 50 seconds to power on (around 35 in my case) since you press the power on button on the computer. A fast BIOS helps to boot faster, so does having a fast hard drive and a fast CPU. In general, unless your system is very well tuned and boots up very quickly, suspending to disk will benefit you and cut your boot time to one half or less. You will have to experiment and see it for yourself. Also, let’s not forget that when it has finished booting, you will have everything running like it was before. The disk cache will also be in place. In other words, the restored system will be as “responsive” as it was before suspending. This is another good reason for considering suspending to disk instead of simply powering off.

In terms of power, which is important if you use a laptop, I mentioned before that the system powers off really and will not drain the battery power. But let’s not forget that those 10-20 seconds in which the computer is writing the image to disk and the 20-50 seconds it takes to restore it are peaks in power usage, because the disk and probably the CPU will be working intensely. Those total 60 seconds of high power usage may use the same as 5 minutes of power being idle, or something similar, but not much more.

Suspend to RAM

Suspend to RAM means to power off almost everything in the computer except for the system RAM. That way, the state of the current running system is preserved while you save power by disconnecting the CPU, the hard drive, etc. There’s no need to lose time saving and restoring great amounts of data, but simply to disconnect and reconnect components. Hence, this is the fastest method. My Acer laptop can suspend to RAM in less than 10 seconds, and be restored in that same amount of time (7.5 seconds average using a stopwatch). You can think of suspend to RAM like going into standby mode.

However, suspending to RAM needs special cooperation from the computer hardware. When you resume, it’s not a normal boot (if you can still call it “boot”), and there are many things that may go wrong. The most typical problems involve the graphics card not restoring properly, and you may end up with a blank or corrupted screen after resuming, eventhough the computer keyboard and mouse may still work (or may not). From the software point of view you face the same problems as when suspending to disk, that is, you’ll probably want to bring down network interfaces, unload problematic modules, etc.

For these reasons, suspending to RAM does not always work. I think you can suspend to RAM using Suspend2 but I’ve only tried the vanilla kernel software suspend using the s2ram program from the suspend package. The name of the actual package depends on the distribution, so you better check which package contains the s2ram program and install it. The program maintainers are very optimistic and they always tell you to keep trying, because s2ram has several options to try different approaches and you may find one that works. Sometimes the program may tell you your computer is not in the whitelist and refuse to run, but you can force it to try and test several different methods, and one of them may actually work, so don’t lose hope. In case you make it work with a non-whitelisted system, they ask you to report the success and the method you forced, so they can whitelist your system in future versions.

Like before, in my Slackware system I wrote a specific script for myself (23 lines), which is identical to the one that suspends to disk but replaces the 2 critical commands with one call to s2ram. It’s the one I invoke when I “close” the laptop, that is, the one associated with the LID button event.

Suspending to RAM does use some power. Remember that your memory stays connected while the computer is suspended. For reference, my laptop can survive suspended for more than 12 hours when there’s only half an hour of battery left. If you’ve got a battery that lasts for 4 or 6 hours and it’s full, the computer may well survive for several days, but not many. Of course, if it’s a desktop computer and/or you leave it plugged in, it can stay so for as long as you want or your electric company lets you. I haven’t noticed the power on and off process having any peaks in power usage. It simply powers off to “standby” and on to normal.

As with suspending to disk, the system will be as responsive as just before suspending. Due to the low power requirements and the minimum time it takes to restore the system, suspending to RAM is usually a good alternative to leaving the system idle turned on, unless you want it to keep downloading something or completing some calculations.

Suspend to both

Suspend to both is useful if you can get suspend to RAM to work. Before suspending, it saves a RAM image to disk (like in suspend to disk) and then tries to suspend to RAM. If there’s some problem and the power is interrupted while suspended (because you run out of battery power, for example), it will restore the disk image when booting. Otherwise, it resumes like in suspend to RAM and discards the disk image. I haven’t found this useful, but I’m sure many people will do in their specific situations and environments.

Blog at WordPress.com.