Older blog entries for shlomif (starting at number 30)

4 Apr 2002 (updated 4 Apr 2002 at 05:46 UTC) »

Studies

It's Passover vacation now, and I prepared all my homework before the vacation, so I was free to follow my own whims the last few days. (and I still have until Sunday to return to studying).

However, Eran and I met on Tuesday and Wednesday to prepare the Computer Networks Experiment of EE-Lab 3. We managed to finish it, but when we wanted to start working on the "Analog VLSI" experiment, we realized we should have bought its booklet in advance. Since the counter is closed during the vacation, we could not buy it then, so we agreed that I'll simply return to Tel-Aviv.

As you see below, with the Logic Mazes Solver, I found out that I made a good use of my time during the vacation.

Freecell Solver

I released Freecell Solver 2.4.0, which a new stable release, that enables several scans to operate on the same states' collection. It required quite a large overhaul to the program's internals which was made easier by using Vim's powerful features. The last time I tried doing it, I believe I used MS DevStudio, and it was a much harder process that bit me in unexpected places. The code was also made more prepared for the overhaul that the last time.

Shortly afterwards, I released Freecell Solver 2.4.1, which fixed a bug there. I wonder if there'll ever be a time when I release Freecell Solver x.y.0 (where y is even) and never have to release Freecell Solver x.y.1, x.y.2, etc. So far, it has been the case only for 0.10.x and 1.2.x, and I'm not sure they are truly bug-free.

Logic Mazes Solver

I did say in the Rules of Open Source Programming that the numbers of items on a project's to-do list always grows or remains constant. Similarily, it seems that the number of projects a developer becomes involved in, always grown or remain constant.

My latest venture started when I remembered the Theseus and the Minotaur Puzzle (check No. 14) which somebody referenced me to. After several good tens of minutes, I was finally able to solve it. But then, I wondered whether a computer program can solve it equally as well, so I decided to write one.

I decided to write it in Perl, and convert it to C only if I see that it is too slow. Eventually, it turned out that it was actually feasible to solve those kind of puzzles using standard Game AI techniques, and that it was very fast even as a Perl program. I accidently searched for Theseus and the Minotaur and google and stumbled upon the Logic Mazes site and found there many puzzles of a similar vein. So I decided to write a generic API that can solve as many of them as possible.

What I did eventually, was adapt the Minotaur script to solve a different kind of Logic Maze called Alice mazes, then I made the alice script more modular and clean, and eventually created a Minotaur sub-class. Now everything is generic enough for solving many kinds of puzzles.

I eventually implemented support for Number Mazes, and also wrote a Breadth-First Search scan. It turns out that even BrFS can solve such puzzles in a good time, and I get the minimal solutions.

The ad-hoc site for the Logic Mazes Solver is here:

http://vipe.technion.ac.il/~shlomif/logic-mazes/

Getting a Central Source Control Repository

Source Control is highly addictive and for a good reason, because it is a life saver. While I don't use CVS for Freecell Solver or for FCFS RWLock (the latter being a little inactive lately), I do use it for my homework, and for the Technion projects, and I'd like to use it for Logic Mazes Solver. At the moment, I use two local CVS repositories, one at home and one at my Technion workstation. However, I would natuarlly prefer to have a central Internet-wide repository.

To make things a bit more complicated, I encountered several of CVS limitations so far, so I'm looking for something more versatile that will at least allow me file renames and copies, as well as better branch management. BitKeeper seems nice, but I noticed something about having to supply it with an SSH public key, which makes me wonder if I can login there from several accounts where I have diffferent public keys. I'll have to find out about it, beforehand.

Subversion also seems nice, but I'm not sure if it has a repository that is available for the public to use. (and registering a project on BitKeeper seems quite straightforward). For the while, I tried to register a project on GNU Savannah, but as usual with this site, they have given me some trouble. Registering a project on BerliOS (and I'm almost sure that on SourceForge too) was much more straightforward than what I encountered with Rindolf or LMS. The Savannah guys' Free Software purism seems to make it much harder for the poor developers who just want to use their service. But who is John Galt?

28 Mar 2002 (updated 28 Mar 2002 at 11:13 UTC) »

Studies

I stayed in Haifa last weekend, so Eran and I can work on preparing the Lab 3 assignments in advance. It took us a very long time to solve anything, but we managed to finish the "Image Processing" and part of the "Computer Networks" experiments. Right now, Passover started, so I have till the Sunday after the next.

Studies were quite interesting the past two weeks. In "Computer Graphics" the lecturer gave us an overview of the book "The Psychology of Everyday Things" so we can design better UIs. My partner for "Design and Analysis of Algorithms" and I sat on the first assignment and managed to finish it. (I consulted the T.A. regarding one exercise there).

Solving the "SICP 2" exercises on streams proved to be quite enlightening. There are many tricks that can be done efficiently using such delayed lists.

The New Project

Roy and I's new project has to do with writing a web-based front-end for viewing and managing Technion Seminars. Roy and I spent some time writing a SPEC and site workflows of it. Our supervisor (who also happens to be the lab engineer and a T.A. in some courses), many times did not have too much time to meet with us. (sometimes despite the fact that we scheduled with him in advance) Hopefully, we won't rely on him too much as we start working on the project.

Rindolf

Omer Zak convinced to write a detailed SPEC of Rindolf, so people will understand what's my general direction is. You can find it here. So far, it diverted a bit from my original intention as I decided to not make it break compatibility. What I am going to do, though, is deprecate a lot of stuff by let issuing warning s all over the place.

I also issued an informal ad-hoc Road Plan to the project. It does not include implementing anything yet, but then again a good design is a pre-requisite for starting to through code all over the place. And naturally the behaviour of the program has to be designed before the actual design of the internals.

6 Mar 2002 (updated 6 Mar 2002 at 05:22 UTC) »

Run-Level 5 - Ahoo!

I eventually switched my Com-Net computer to Run-Level 5. It was more convenient than the screen trick and the sound was not disabled after a while. It will be problematic if something changes in the system that does not give way to run-level 5 so I have to remember to change it back to run-level 3.

The way I see it run-level 5 was introduced for a reason and obviously the renegade terminal is a good one for using it.

Game Theory Exam

It could have gone worse but could have gone better. Right before the test I discovered that the Math faculty gives the students to prove theorems in the test. (from some reason, they have an obsession with their students studying anything by heart for the exam).

When I got the form I discovered that I could not solve one question because I could not remember the proof of Nash' Theorem. Despite the fact that it was 4 questions out of 5, I managed to solve only 2 1/2 since I was a bit drowsy and could not concentrate or think very clearly. But it was fun.

Hopefully, I will get more than 55 as a final score, so Game Theory will enter my record. If not, I may have to take the second date exam without reviewing the material right before the exam too much. (since it falls out after the beginning of the semester).

Of course, for those interested I have an O(1) algorithm for finding the proof to Nash' Theorem:

1. Find the Open University Book (the lecturer should have it available).
2. Open it.
3. Find the chapter about Nash Theorem.
4. Copy the proof from it onto the tests' answer sheet.

It is O(1) since the book has a finite number of pages and the lecturer should have the book. I thought about writing this algorithm in the test sheet, but then I thought better of it. I did include one other joke in the test, but it was only complementary to the serious answer. (it was that p*A+(1-p)*B violates Apple's Patent on Alpha... ;-))

The Project's Demo

The project's demo went very well. We gave it only to Lavy and Yoram Yihyie, who is the Com-Net Lab's engineer. Yoram Or-Chen, the director of the communications center was not present. Yoram Yihyie was very impressed and said the Lab can actually make use of the IP-Noise Simulator.

Naturally, there are still the things that has to be cleaned up in the code to make it run on newer kernels. Plus, I'm not sure what the implication of the pre-emptible kernel would be next. The Linux Kernel changes so rapidly, that third-party vendors must sometimes modify their code constantly. I wish the situation was a bit different, but that's progress for you.

1 Mar 2002 (updated 1 Mar 2002 at 06:37 UTC) »

I believe this entry should be concatenated to the previous one , but since I posted the latter yesterday's evening, I'd like to keep them separated.

Game Theory

I took a course by that name this semester. I missed many lessons because I had EE-Lab 2 experiments and my notebook is in quite disorder due to my hand-writing. Luckily, I bought the Open University's booklets on the subject, and after the SICP test, I went over them while solving most of the exercises there.

It is possible that the lecturer deviated a bit from what was presented in these booklets, because they were not the only recommended material for the course. (and are not considered the most definite resource on the subject).

Game Theory is actually quite an interesting subject, but during a lecture I kept having the feeling of "been there, seen that.". What I mean is that the material kept sounding pretty much the same. Going over the booklets was quite enlightening, though.

In any case, the important thing is that I enjoyed the course. It is not a critical course for me to take, so even if I fail the test (and the second date one), nothing terrible will happen.

A gvim Problem

I seem to have another gvim problem, after I upgraded to gvim 6.0. I already solved the crummy fonts one (refer to the Linux-IL archives) by eliminating the guifontset variable that got in my way. Now, however, it seems that I have to copy or cut a variable twice to put it in the clipboard for the first time I'd like to copy something there. Copying or cutting once does not seem to do the trick. Refer to this post.

Nobody could answer so it is possible it is something that is only encountered at my machine from some unknown reason. Maybe I should consult the Vim mailing list about it.

When the editor does not work properly, a developer's life is not really complete. Perhaps I can add a line to copy a buffer to the clipboard once on startup as a kludge. But then I'd like to restore the information stored there, so it won't be destroyed. I need help...

Vim Hanoi Towers Implementation

Refer to here for the code. This is more like a doctorate work in Vi macros programming as I:

  1. Did not use the Vim's scripting language (only map and friends).
  2. Implemented the recursive algorithm

The problem I'm facing now is that the number of disks is hard-coded into the program and will take some time to abstract. But I have better things to do with my time, for the moment.

28 Feb 2002 (updated 28 Feb 2002 at 20:40 UTC) »

SICP

After the test I had a while ago, I received the news that my final grade is 88%. IMVHO, I deserve more, but perhaps I should have stayed a while in the testing room and gone over the test, instead of handing it right away, like I did.

Not staying to go over the test, seems to be a theme of mine lately in the Technion. I just don't have the nerve to spend more time in the testing room and ahttp://groups.yahoo.com/group/fc-solve-discuss/message/283m anxious to get out ASAP. I'd like to break this habit for the Game Theory test though.

Next semester I am taking the course "SICP 2", which from what I understood is being taken by very few students. Dudu, Eran's friend, is taking it too, so I'll have a partner in case the course gives way to them. The course covers the other part of the book, with the interpreters and the compiler as well as some external material.

When I read the book I found it strange that it is a register machine where every register can hold an entire S-expression. I.e: '(hello (6 (9 0) jkl (uo) op) kl). Now put this in the EAX register of a Pentium...

But thinking about it, Abelson and Sussman got along with very few registers, so I don't think consing several values into one register, could give any advantage. And Parrot has registers which are strings of unlimited length or those "Parrot Magic Cookies", so it's probably a relatively common idiom in designing high-level virtual machines.

Nevertheless, I don't think the book gives the readers enough knowledge to implement a Compiler from Scheme to a Real-Life Assembler. But that's what the Dragon Book is for probably. I did not read the Dragon Book as of yet, but I'd like to, sometime.

Freecell Solver

Being home after the SICP test gave me some time to work on Freecell Solver vis-a-vis with studying for Game Theory. After fine-tuning the FCS 2.2.x autotools parameters, I started working on implementing the so called "Soft Threads".

By "Soft Threads" I mean a way for several parallel scans to operate on the same state collection. I remember that last time I tried it (in what should have been FCS 1.8.x), it took me a very long time to get everything working and even then it was not flawless. This time, howver, working on gvim with a lot of substitutions and an internal framework that was adapted to it a-priori, I managed to get it done very quickly. God bless Linux.

The code is very stable now, and the soft threads work beautifully. Refer to the following URL for more details.

There is still a minor glitch I encountered, which I'll have to deal with. And then there is a mis-feature in the range solver, which I'll have to adapt to the new architecture.

Incidentally, Tom Holroyd released PatSolve 3.0 recently. He claims that he managed to code a very speed-wise optimized mode using a genetic algorithm. I was not able to compile it (probably due to a python version mismatch) and Tom is out of town until next Wednesday, so I'll just have to wait.

"Rindolf" - a New Language is Born

I decided to start my own dialect of Perl, which I call Rindolf. It will be based mostly on Perl 5, with some ideas from other languages I'm familiar with and with some ideas for cleanups I have in mind.

The idea came to me after I heard mulix say that he reads the Apocalypses and Exegesis, but doesn't understand them. It made me realize that I also felt that most of the suggestions were either incomprehensible, or useless for me.

I plan to simply formulate a complete SPEC of the way in which Rindolf deviates from Perl 5. That way, my recommendation can be integrated into Perl 5, Perl 6 or stand on their own.

For more information Refer to:

My original post to Hackers-IL with the idea (I call it Perl 5 TNG there).
The Rindolf Mailing List I set up
A Rindolf Feature in "Use Perl" (It was not comprehensive enough, I believe)

Fixing the IP-Noise Final Report

The Final Report of the IP-Noise Project which Roy and I wrote was based on an old version of the Mid-Term Report before Lavy fixed a lot of things. Thus, Lavy was not very happy with it, and asked us to correct things before he'll take another look. He said the user's guide which we wrote was very good, OTOH.

Today, my father and I went over the final report and corrected a lot of things. Office XP was installed so it can read the report in the first place, but it still causes some minor glitches. But so far, the document is better than it was before.

The worst case scenario is that we will lose some points due to the brevity of the report.

Vim Macro

Due to the fact that I could not find any decent editor outside KDE that behaves just like I wanted, I decided to try and make gvim into an xmms front-end. Which naturally meant adding two macros (one for playing a file and the other for enqueuing it) into my .vimrc file.

I knew Vim macros were basically a recording of all the commands needed to execute them. So, after consulting the vim help pages a bit I came up with a generic macro that did just that. This macro had a problem in which it was not resistant to shell's special characters.

I worked on two other revisions of the macro. In the third revision everything was fixed except for filenames that contain newlines (which are pretty rare as it is).

What I did was copy the line containing the filename into a register, duplicate it below, substitute all the single quotes with the sequence '\'', copy it into the register again. Then, I entered the command line :!xmms '$reg' on the shell, and afterwards deleted the extra line.

Guy Keren once said to me that one did not do real programming until he programs with Vi macros. So, perhaps this was a baby step in the direction of becoming a "real" programmer.

This macro looks like line noise, doesn't it? ;-)

So many things happened since my last diary entry and I have so many things to write. Well - better start somewhere - here goes:

"The Great Kernel CVS Mutiny"

That was the name of a post I made to the Linux-IL mailing-list, which started quite a flamewar. Basically, I made two suggestions for improvements to the way the Linux kernel was managed:

  1. That a source control mechanism be used by Linus and the other kernel developers (hence the name)
  2. That Linus will not necessarily OK all the patches that will go into the main kernel tree, but rather rely on the good judgement of the subsystem maintainers, the module maintainers, etc.

Suggestion #1 seems to have been resolved (with or without my influence - IANA prominent kernel developer) by Linus' switch to BitKeeper. Suggestion #2 seems to have been raised in the "Patch Penguin" post. I did not thoroughly read either the original post or Torvalds' reply to it, so I cannot say right now whether or not it has been resolved the way I think it should.

An interesting theme to my posts was an analogy I made to the story of Moses and Jethero in the Exodus. Read the posts and be amused.

21 older entries...

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!