Older blog entries for shlomif (starting at number 48)

Web-sites Overhauling

I overhauled both the Freecell Solver and syscalltrack web-sites by converting them to WebMetaLanguage. At the moment, neither site is online but they can be found in the projects' respective CVS repositories.

The Freecell Solver web-site accepts a parameter that determines if it's the master web-site on vipe.technion.ac.il or the BerliOS mirror, so it would make it easier for me to maintain both sites.

Haifux Lectures

I posted a call for opinions on the mailing list on what my next lecture should be and so far received three opinions. %-) Maybe I should proceed in preparing what I'd like regardless of what other people want, because finding what they do, is quite hard.

This reminds me that I'd better finish the third Perl lecture, something I intended to do it for a long while.

Freecell Solver Book

I managed to find some time and write a large part of the abstract. Now I have to learn DocBook and start hacking on it seriously. Oh well, I have the entire summer.

I formed a private mailing list where I'll post or announce subsequent versions of the book. Send me an E-mail if you wish to join.

The Lex-&-Yacc Demo

It went pretty well, albeit my hope of extending the syntax of the language, did not materialize. Orr started explaining about how Yacc works (it converts a non-determinstic stack-based finite automata to a determinstic one, which may result in an exponential expansion of the automata)

Other than that, the meeting went very well, except for Guy not showing up to discuss gen_syscalls.pl. (it turned out he forgot and said that when he remembered it was already too late) Maybe we could try discussing it on the mailing list, but still a real-life discussion would have been so much more effective.

Orna's design is now the default at the Sys-Call-Track web-site and I already found some faults in it. But like I said: "Don't whine unless you are going to implement it yourself", which may mean I'll have to do some WebMetaLanguage hacking in my free time.

Lex and Yacc Demo

It all started when I suggested Muli and Guy that I give a presentation about Lex and Yacc in order to equip them with enough knowledge to re-implement the "System Call Tracker" user-land configuration utility with it. It turned out they already knew Lex and Yacc (just were too lazy-minded to use it), but it was decided by forces beyond my control that I give it in any case.

Go here for the results. My plan is to demonstrate them both using perl by starting from a very basic grammar, and then extending it with help and guidance from the audience. Should be pretty cool.

Orna, (ladypine) confessed told me she only has a vague understanding of formal languages, so I may have to delay a bit with the part on Yacc. But that's what the demo is for in the first place.

Meanwhile in the Haifux mailing list a friendly discussion erupted about how much the Scanner-less Generalizer LR Parser was innovative or not, just because it did not distinguish between parsing and tokenizing.

This demo would be part of the Sys-Call-Track developers' meeting, in which we will also discuss a better design for the notorious gen_syscalls.pl.

Biking

I saw a mole today when I rode through the park. It was sunbathing on one of the lawns and looked very cute. Aren't moles supposed to be nocturnal mammals?

Studies

My homework progress is in good shape. Liat and I sat on "Algo Design" yesterday and went on proving that a gaggle of problems were NP-Complete. I managed to prove two trivial questions and Liat found the answers to most of the interesting ones. Nevertheless, I was able to find a reduction from Subset Sum to Partition. I noticed that we sometimes ran into problems in our original concept just as we were writing it down, which we had (and were able to) resolve.

In "Computer Graphics", my partner and I sat on moving the Daemon using Bezier curves. This involved programming a path-editing dialog in Motif, a Polynomials module in ANSI C, and a function using it that constructs Bezier Polynomials. But it was mostly fun.

Eran and I handed out our last assignment (the VHDL one) for "EE-Lab 3" and hopefully we would have one less mandatory course in our agenda. I had higher expectations of VHDL than what I saw in this experiment, and I was quite disappointed. Eran claims that VHDL and Verilog sucks, and when I asked him if he can think of a better alternative, he told me that he sometimes does not need to know there is a better one to know that it sucks. He gave Word as an example.

I took the second exam in "Internet". It went comsi-comsa, but as I told Mom this morning, I am entirely discontent with the way the course was managed this semester. The questions in the tests were way beyond the other questions which we were given (albeit solvable); we were tested on material that was not given in the homework, and finally both tests contained a question valued 54% or 55%. Truly uncivil.

Freecell Solver

I had enough time to hack on it extensively. What started as a cleanup release turned out to add more features, and a lot of optimizations. But then again, this was the theme of most development branches of Freecell Solver so far. The --prelude switch and a Perl Script I wrote to construct a close-to-optimal one, made it possible to solve the MS 32,000 in less than 19 million iterations, and in 35 minutes. I don't know how it fares in comparison to patsolve, but it is still very impressive.

A quick calculation shows that it is an average of 594 iterations per board, which is a very good solving quota. Thus, I'm not sure if I can improve the performance much better by continuing to follow this direction.

LM-Solve

I released version 0.4.0 of it. It's not much different from the recent development version, but it deserves a stable version number. Now my plans for it are to make it possible to solve Plank Puzzles with it (which should prove to be non-trivial) and clean up the internals a bit and make it suitable as an API. If I'm in the mood, I might write a graphical front-end to it, but I also wish to do the same for Freecell Solver.

Freecell Solver Lecture

It went very well if you ask me. There were not too many participants. I think that all the people who were present were Guy, Adir, Muli (mulix), Emil, Tzafrir, Nadav Har'El, and another one whom I know but don't remember his name. There was a lot of active discussion throughout the lecture, and several times everybody burst in laughter; I felt I was doing okay and keeping most people interested, and later on, when I asked him, Muli noted that he found the lecture more interesting than he expected.

I think it went well for several reasons. First of all, I made sure I feel confident about giving it, and know that I'll do fine. Confidence go a long way to making the audience like you. Secondly, I decided not to just read the slides, but rather tell it in my own words, and extend some stuff from my own memory. I'm still not sure that I'm a good speaker, but those skills may probably evolve as well as revolve.

There were a few suggestions that were brought up during the lecture, which may be a good food for thought for the future. One of them was another discussion of how to avoid solutions that are not too long, without blocking deep states that may prove useful in the future. They were not too satisfied with the optimization scan (nor am I sure it is an absolutely robust solution).

Another thing that came up was Nadav's suggestion that I store the states like RCS does, by using deltas from the original one. This sounds like an interesting idea, which may reduce memory consumption drastically, but will make comparing states harder.

Note to self: implement a compact allocation for the move stacks. (very important)

BitKeeper

I finally have an on-line BK repository. It took me quite some time to get the ropes, but I think I now know how to use the basic system. It is more tedious to work with than CVS is, but I suppose such power has to come at some cost.

I'll probably check Arch and Subversion sometime later, just to get an objective review of what they give me.

I woke up today at 02:00 AM which is quite early for what I'm used to. I then turned on the computer and started working on it, and then tried to go back to sleep, but could not so I continued working on it until breakfast.

I managed to finally be able to understand how to work with BitKeeper. It requires quite a lot of commands just to commit the changes into the master repository, so I'd better write scripts to automate it (like Linus Torvalds did). I'll probably use it for LM-Solve, just to get a feel of how to work with it and what it can do.

Other than that, I did all kinds of bit and pieces like making the shoes of the BSD daemon a bit nicer. I went running at around 9 O'clock and close to home, I again encountered the same girl jogger I saw yesterday (wearing a differentyl coloured set of clothes). Maybe she has the habit of running everyday at around this time.

Freecell Solver Lecture

I finished it, gave it some final touches and uploaded it to vipe. You can find it here. Now I have to review the slides before the presentation on Monday.

Studies

The 3-D impression of a BSD Daemon we created now has moving parts, thanks to a lot of effort I invested in it. Writing Inventor Scenes in C++ sure is tedious. I still have to inform my partner about it.

An exercise that we were given in the "Internet" course, turned out to contain a bottom note saying that we should better use the book "Routing in the Internet". I left it at my apartment, so now I'm stuck without it. But who is John Galt? The way things are progressing it seems Roy and I will have to spend some time off the summer vacation working on the project. We just can't seem to find enough time during the semester proper.

I eventually finished the SICP 2 exercise. I implemented the Minimum Spanning Tree Algorithm with awful complexity because I was too lazy to implement a binary heap from scratch. Whatever: the lecturer said that complexity was not the issue here.

Biking

Yesterday, I could not drive through my usual trail in the Yarkon Park because there was a Food Festival there. Today I saw that people started dismantling all the equipment and stages that was left there. So it's probably back on track. There's some kind of activity going on in the middle part of the park, but I don't know what it is. There are just several large heaps of stones or dirt.

Today, a girl jogger sort of accompanied my trail for a large part of my ride through the University St. I then lost her as she jay-walked (or rather jay-ran) across the red-lights in Qeren Qayemet. It was no the first jay walk of her that I witnessed.

Freecell Solver

I placed the source on the CVS repository on BerliOS and since then I was able to hack on it. So far, I did some cleanups of the code, added an unlimited tests order, and implemented compact allocation for some resources. In the compact allocation scheme, I allocate contigous blocks from a buffer, rather than individuallly malloc everything.

The CVS is by far more convenient that keeping tar.gz archives. The problem is that it takes some time to commit it, because the connection is slow.

TuxRacer Demo

I downloaded the TuxRacer 1.1 Demo by SunSpire Studios. The graphics are better than the old Open-Source version. It took me some time to get used to it, but now I like it a lot. I'll probably talk my dad into buying the full game, because it looks very promising.

Learning STL

I've learned a bit of STL yesterday, and covered some of the basics of vectors, lists and iterators. Programming one of the exercises the tutorial gave me turned out to be quite tedious, and it took me a long time to get it right. The problematic part was the data structure logic more than the API.

I don't think I will invest much more extra time in it, because I'm not using it now, and until one needs to use something, he has little motivation to learn it.

Sys-Call-Track

mulix said that in his diary, but I might as well too. I hacked on the perl script that generated some code their, and cleaned it up a bit. Most of what I did had to do with making the code more perl5-ish instead of the perl4-like mess it used to be.

I talked with Guy Keren, the other prominent developer of Sys-Call-Track and he said that what he also would like to see is the entire philosophy of the script re-factored. But hopefully, I can do that by doing several incremental changes, rather than one complete re-write.

Freecell Solver Lecture

I started translating the points I wrote to HTML slides. I finished quite a lot of them, but it will take me some time until everything can be placed on-line.

Studies

I have a precept on Thursday for "Algo Design", due to the fact that my T.A. has been drafted into the Army with a Turtle-8, and the replacement T.A. does not have the same hours.

Furthermore, I have to sit with my Computer Graphics and "Algorithms" partners, before the weekend.

Learning C/C++

My sister, Noa, called me and requested that I buy for her a book on learning C and C++. Today, I bought the book "A Book on C", which I can still recall from "Intro to CS". Hopefully, it would be suitable for her.

Her original idea was that I should buy her a book in Hebrew, but I told her they are probably sub-standard. Going to Prof. Kimchi's site strengthened this, and I saw there that he recommends "A Book on C".

Studies

I had to stay in the Technion today, and may remain for the rest of the weekend. The ironic thing is that it's holiday during the weekend ("Shavuoth") and I won't be able to enjoy it. The anti-christ in this story is the course "Computer Graphics" whose homework require my partner and I to invest quite a lot of time in the front of the computer, hacking with OpenInventor and Motif.

Hopefully, I won't have to do too much Motif programming this time. Building proper GUI is a tedious task, and I have time finishing it in a reasonable time. Especially with a something like Motif that is very awkward and not programmer-friendly. I spent most of the time in the previous exercise trying to get the dialogs to work, and the OpenInventor part was relatively easy.

I really wish I could do Inventor programming in Perl. (or in anything in the same vain). But I'm not aware of any binding that allows it. Maybe, I'll get to it one day. I also wonder how much is Inventor dependant on Motif? I.e: how long will it take to make it available for Gtk+ or something else?

There are Motif bindings for Perl, so maybe I'll settle down for them.

Other than that the last SICP exercise took way too long, because the MIT Scheme debugger was awkward to work with and buggy. My apartment-mate recommended me to use Dr. Scheme, so I think I'll give it a try. And now I have to draw an environment diagram... %-). Plus, I don't know how to draw box-and-pointer diagrams for streams. (and the lecturer was abroad to give a presentation, so I could not ask him).

The other courses are going quite well. Eran and I finished preparing the preliminary reports for the VHDL experiment. But the instructors there did not let us simply hand what we prepared as is. We'll have to be there to see for ourselves. I was told the Sun workstations there don't have floppy disk drives and the Internet connection is not functional. I'll have to go there and find out.

Liat and I prepared the "Design and Analysis of Algo" third exercise and are meeting on Tuesday to prepare the third. I wrote a Perl script that implements the Edmonds-Karp flow analysis scan. We have now standard to learn about complexity, intractibility, Turing machines and friends.