07.24.07
Failure Story on ICFP07…
My last weekend was spent on working out a solution in PLT-Scheme for the ICFP07 task. Amazingly fun, well-written, well-imagined task and poor code development on my part briefly resumes it. It was nonetheless, a lot of fun!!!
If you’re not confortable with the task description, you should look at it to understand what’s coming next. So I had to read a huge string from a file, Endo DNA, formed by 4 characters I, C, F and P. My approach was “Let’s get something done and then I’ll optimize if I need to.” And so it was…
Reading a file is pretty easy:
(define (get-line-from-file str)
(let ([filefp (open-input-file str)])
(begin0
(read-line filefp)
(close-input-port filefp))))
I now, started to think that it would be nice not only to have it in the string, but also to optimize prepends to this string and character skips and since th DNA string was global, I decided to make it global in my module also.
(define *dna* "")
(define *dna-index* 0)
(define (set-dna! str)
(set! *dna* str)
(set! *dna-index* 0))
(define (dna-prefix? str)
(string-prefix? str *dna* 0 (string-length str) *dna-index* (string-length *dna*)))
(define (dna-drop! n)
(set! *dna-index* (+ *dna-index* n)))
(define (dna-substring init end)
(cond [(or (>= init end) (>= (+ *dna-index* init) (string-length *dna*))) ""]
[else
(substring *dna* (+ *dna-index* init) (if (> (+ *dna-index* end) (string-length *dna*))
(string-length *dna*)
(+ *dna-index* end)))]))
(define (dna-preppend! str)
(if (> (string-length str) *dna-index*)
(set-dna! (string-append str (string-drop *dna* *dna-index*)))
(begin
(set! *dna-index* (- *dna-index* (string-length str)))
(string-copy! *dna* *dna-index* str))))
(define (dna-ref n)
(if (>= n (dna-length))
""
(string-ref *dna* (+ *dna-index* n))))
(define (dna-length)
(- (string-length *dna*) *dna-index*))
(define (find-smallest-dna-suffix s i)
(let loop ([k 0])
(let ([sstr (dna-substring (+ k i) (+ k i (string-length s)))])
(cond [(string=? sstr "") #f]
[(string=? s sstr) (+ i k (string-length s))]
[else (loop (+ k 1))]))))
(define (dna)
(dna-substring 0 (dna-length)))
This code basically defines a dna string globally and functions to handle this dna string. Also an index to the start of the real DNA string is maintained, because if I skip n chars I don’t want to be dropping chars and then when prepending ending up putting them again on it. So I used this little trick just to have one constant sized string capable of growing if needed. At this moment I considered using evectors but then again… I thought, later I optimize… Now, the code as you may see in the task manually is pretty written almost in a schemish style (if you look to the lets) and with Cish assignments and loops, so I decided to go ahead and do it in the most straighforward way possible. One problem was the finish function which could be called from any other function and it would finish the processing. After some messing around with Scheme and thinking about it I thought it would be a good time to put call/cc to good use.
(define exit-now (void))
(define (execute)
(call/cc (λ (exit)
(set! exit-now exit)
(let loop ([iteration 0] [time (current-inexact-milliseconds)])
(printf "Execution Iteration : ~a~n" iteration)
(let ([p (begin0 (pattern))]
[t (begin0 (template))])
(printf "pattern ~a~n" p)
(printf "template ~a~n" t)
(matchreplace p t)
(printf "len(rna) = ~a~n" (/ (rna-length) 7))
(printf "Time taken: ~a~n" (- (current-inexact-milliseconds) time))
(loop (+ iteration 1) (current-inexact-milliseconds)))))))
(define (finish)
(exit-now *rna*))
Once the function execute is called, it sets the exit-now variable to the continuation of execute and the function finish calls it with the rna global variable that we will look into later.
Defining pattern was just looking to the task manual and almost blindly copy it:
(define (pattern)
(let repeat ([p ()] [lvl 0])
(cond [(dna-prefix? "C")
(dna-drop! 1)
(repeat (cons 'I p) lvl)]
[(dna-prefix? "F")
(dna-drop! 1)
(repeat (cons 'C p) lvl)]
[(dna-prefix? "P")
(dna-drop! 1)
(repeat (cons 'F p) lvl)]
[(dna-prefix? "IC")
(dna-drop! 2)
(repeat (cons 'P p) lvl)]
[(dna-prefix? "IP")
(dna-drop! 2)
(repeat (cons `(! ,(nat)) p) lvl)]
[(dna-prefix? "IF")
(dna-drop! 3)
(repeat (cons `(? ,(consts)) p) lvl)]
[(dna-prefix? "IIP")
(dna-drop! 3)
(repeat (cons '( p) (+ lvl 1))]
[(or (dna-prefix? "IIC") (dna-prefix? "IIF"))
(dna-drop! 3)
(if (zero? lvl)
(reverse! p)
(repeat (cons ') p) (- lvl 1)))]
[(dna-prefix? "III")
(rna-append! (dna-substring 3 10))
(dna-drop! 10)
(repeat p lvl)]
[else
(printf "finish: called by pattern can't match beginning of DNA: ~a...~n" (dna-substring 0 10))
(finish)])))
And the same was try with the template function:
(define (template)
(let repeat ([t ()])
(cond [(dna-prefix? "C")
(dna-drop! 1)
(repeat (cons 'I t))]
[(dna-prefix? "F")
(dna-drop! 1)
(repeat (cons 'C t))]
[(dna-prefix? "P")
(dna-drop! 1)
(repeat (cons 'F t))]
[(dna-prefix? "IC")
(dna-drop! 2)
(repeat (cons 'P t))]
[(or (dna-prefix? "IF") (dna-prefix? "IP"))
(dna-drop! 2)
(repeat (cons `(_ ,(nat) ,(nat)) t))]
[(or (dna-prefix? "IIC") (dna-prefix? "IIF"))
(dna-drop! 3)
(reverse! t)]
[(dna-prefix? "IIP")
(dna-drop! 3)
(repeat (cons `(|| ,(nat)) t))]
[(dna-prefix? "III")
(rna-append! (dna-substring 3 10))
(dna-drop! 10)
(repeat t)]
[else
(printf "finish: called by template can't match beginning of DNA: ~a...~n" (dna-substring 0 10))
(finish)])))
The nat and consts functions seems that could do a little tweaking but again I postponed. Anyway it was Saturday, first competition day for me and I still had the whole day and still sunday so I just wrote:
(define (nat)
(cond [(dna-prefix? "P")
(dna-drop! 1)
0]
[(or (dna-prefix? "I") (dna-prefix? "F"))
(dna-drop! 1)
(* 2 (nat))]
[(dna-prefix? "C")
(dna-drop! 1)
(+ (* 2 (nat)) 1)]
[else
(printf "finish: called by nat. dna is empty.~n")
(finish)]))
(define (consts)
(cond [(dna-prefix? "C")
(dna-drop! 1)
(string-append "I" (consts))]
[(dna-prefix? "F")
(dna-drop! 1)
(string-append "C" (consts))]
[(dna-prefix? "P")
(dna-drop! 1)
(string-append "F" (consts))]
[(dna-prefix? "IC")
(dna-drop! 2)
(string-append "P" (consts))]
[else ""]))
The next one were the straightforward matchreplace and replace itself which were the most bug-ridden functions I had in the competition but not amazingly were quite simple to implement:
(define (matchreplace p t)
(call/cc (λ (return)
(let loop ([i 0] [e ()] [c ()] [cp p])
(for-each (λ (envel) (print-seq-info "e" envel)) e)
(if (null? cp)
(begin
(printf "successful match of length: ~a~n" i)
(for-each (λ (envel) (print-seq-info "e" envel)) e)
(dna-drop! i)
(replace t (reverse! e)))
(match (car cp)
((? symbol? (or 'I 'C 'F 'P))
(let ([dna-symb (string->symbol (string (dna-ref i)))])
(if (eqv? dna-symb (car cp))
(loop (+ i 1) e c (cdr cp)))))
(`(! ,n)
(if (not (> (+ i n) (dna-length)))
(loop (+ i n) e c (cdr cp))))
(`(? ,s)
(let ([smallest-suffix (find-smallest-dna-suffix s i)])
(if smallest-suffix (loop smallest-suffix e c (cdr cp)))))
((? symbol? '()
(loop i e (cons i c) (cdr cp)))
((? symbol? '))
(loop i (cons (dna-substring (car c) i) e) (cdr c) (cdr cp)))))))
(define (replace tpl e)
(let ([env (list->vector e)])
(letrec ([env-ref (λ (n) (if (>= n (vector-length env)) "" (vector-ref env n)))])
(let loop ([r ""] [t tpl])
(if (null? t)
(dna-preppend! r)
(cond [(symbol? (car t)) (loop (string-append r (symbol->string (car t))) (cdr t))]
[(list? (car t))
(if (eqv? (first (car t)) '_)
(loop (string-append r (protect (second (car t)) (env-ref (third (car t))))) (cdr t))
(loop (string-append r (asnat (string-length (env-ref (second (car t)))))) (cdr t)))]))))))
(match (car t)
((? symbol? (or 'I 'C 'F 'P))
(loop (string-append r (symbol->string (car t))) (cdr t)))
(`(_ ,l ,n)
(loop (string-append r (protect l (env-ref n))) (cdr t)))
(`(|| ,n)
(loop (string-append r (asnat (string-length (env-ref n)))) (cdr t)))))))))
Where the print functions are just debugging aids:
(define (print-seq-info name seq)
(printf "~a = ~a...(~a bases)~n" name (if (< (string-length seq) 10) (string-length seq) (substring seq 0 10)) (string-length seq)))
(define (print-dna-info)
(printf "dna = ~a... (~a bases)~n" (dna-substring 0 10) (dna-length)))
And follows the utility functions for matchreplace:
(define (protect l d)
(if (zero? l) d (protect (- l 1) (dna-quote d))))
(define (dna-quote d)
(printf "quote: d=NOTSHOWN~n")
(cond [(string-prefix? "I" d) (string-append "C" (dna-quote (string-drop d 1)))]
[(string-prefix? "C" d) (string-append "F" (dna-quote (string-drop d 1)))]
[(string-prefix? "F" d) (string-append "P" (dna-quote (string-drop d 1)))]
[(string-prefix? "P" d) (string-append "IC" (dna-quote (string-drop d 1)))]
[else ""]))
(define (asnat n)
(cond [(zero? n) "P"]
[(even? n) (string-append "I" (asnat (quotient n 2)))]
[(odd? n) (string-append "C" (asnat (quotient n 2)))]))
This finishes up the hard part DNA->RNA, which I had it finished by saturday afternoon… Now, I needed the bitmap part working. Incredibly, using PLT-Scheme functions to handle bitmaps was easy and produced great results, however, didn’t allow me to run this on my server, without X. This is because I needed mred.ss library which require X to be running, when in fact, no window is being displayed and apparently, no X is in fact being using directly by me. The RNA variable which I didn’t show was defined similarly to the DNA variable and is of no use to show it here. The RNA to image part is of not much interest (because I never got to really optimize it) and you can find the code online. However, with this much code and a little bit more for bitmap generation was enough to generate this from the prefix found in the last task page after about 140 iterations:
First the part where optimization worked beautifully… the replace function:
(define (replace tpl e)
(let ([env (list->vector e)])
(letrec ([env-ref (λ (n) (if (>= n (vector-length env)) "" (vector-ref env n)))])
(let loop ([r '()] [t tpl])
(if (null? t)
(dna-preppend! (apply string-append (reverse! r)))
(cond [(symbol? (car t)) (loop (cons (symbol->string (car t)) r) (cdr t))]
[(list? (car t))
(if (eqv? (first (car t)) '_)
(loop (cons (protect (second (car t)) (env-ref (third (car t)))) r) (cdr t))
(loop (cons (asnat (string-length (env-ref (second (car t))))) r) (cdr t)))]))))))
This version removed the string-appends from all over the body to apply a string-append to a list of strings which is built in reverse order during the loop. The difference of these two versions is quite big.
Now, using PLT-Scheme profiler I started to optimize everything that should up worse than light green (in DrScheme) and decided to remove the match at matchreplace by something similar which in fact didn’t improve much, if at all, this function. This is what is not in place of the match call:
(let ([obj (car cp)])
(if (symbol? obj)
(cond [(eqv? obj '()
(loop i e (cons i c) (cdr cp))]
[(eqv? obj '))
(let ([substr (dna-substring (car c) i)])
(loop i (cons substr e) (cdr c) (cdr cp)))]
[else
(let ([dna-symb (string->symbol (string (dna-ref i)))])
(if (eqv? dna-symb (car cp))
(loop (+ i 1) e c (cdr cp))
(return (printf "failed match~n"))))])
(if (eqv? (first obj) '!)
(if (not (> (+ i (second obj)) (dna-length))) (loop (+ i (second obj)) e c (cdr cp)) (return (printf "failed match~n")))
(let ([smallest-suffix (find-smallest-dna-suffix (second obj) i)]) (if smallest-suffix
(loop smallest-suffix e c (cdr cp))
(return (printf "failed match~n"))))))))))))
I also tried to optimize consts and nat by removing all those function calls without much success:
(define (nat)
;; Search for the first P
(let ([p-pos (let loop ([i 0])
(let ([cc (dna-ref i)])
(cond [(string? cc) (printf "finish: called by nat. After eating ~a bases can't find a P starting with ~a..." i (dna-substring 0 10))
(finish)]
[(char=? cc #P) i]
[else (loop (+ i 1))])))])
(begin0
(let loop ([pos (- p-pos 1)] [val 0])
(cond [(= pos -1) val]
[(char=? (dna-ref pos) #C) (loop (- pos 1) (+ (* 2 val) 1))]
[else (loop (- pos 1) (* 2 val))]))
(dna-drop! (+ p-pos 1)))))
(define (consts)
(let const-loop ([i 0] [transf ()])
(let ([cc (dna-ref i)])
(if (and (char=? cc #I)
(not (char=? (dna-ref (+ i 1)) #C)))
(begin
(dna-drop! i)
(apply string (reverse! transf)))
(cond [(char=? cc #C) (const-loop (+ i 1) (cons #I transf))]
[(char=? cc #F) (const-loop (+ i 1) (cons #C transf))]
[(char=? cc #P) (const-loop (+ i 1) (cons #F transf))]
[else (const-loop (+ i 2) (cons #P transf))])))))
And I even optimized template and pattern by replacing calls from
(dna-prefix? "C")
to
(char=? (dna-ref 0) #C)
without much, or any, success. These benchmark explain why I tried:
> (time (begin (let loop ([i 0])
(unless (>= i 3000000)
(cond [(dna-prefix? "IP") "C"]
[(dna-prefix? "IF") "P"]
[else "K"])
(loop (+ i 1))))))
cpu time: 32678 real time: 32821 gc time: 3660
> (time (begin (let loop ([i 0])
(unless (>= i 3000000)
(cond [(dna-prefix? "I") (if (char=? (dna-ref 1) #\P) "C" "P")]
[else "K"])
(loop (+ i 1))))))
cpu time: 34970 real time: 36296 gc time: 1664
> (time (begin (let loop ([i 0])
(unless (>= i 3000000)
(cond [(and (char=? (dna-ref 0) #\I) (char=? (dna-ref 1) #\P) "C" "P")]
[else "K"])
(loop (+ i 1))))))
cpu time: 38086 real time: 38345 gc time: 0
The optimizations took me almost all saturday night and sunday. Sunday evening I was getting desperate. Then I though that with these datastructures there wasn’t probably much more I could do but I was tired and had to work on the next day so I sent and email to the list to let my frustration go when I was advised to go by #oasis @ freenode.org where people where talking about datastructures and algorithms. I went by to the channel full of people and went to sleep to do nothing else. I’m doing basically ~1 iterations / sec when I should probably be doing 20000 iterations / sec.
Yesterday, I went to look into the PLT-Scheme manual and remembered myself that PLT Scheme string are unicode and probably perform even worse than normal C-strings (in PLT-Scheme, byte-strings) due to that. I shall try change to byte-string and see the results! :-) The more or less cleanified code of what I had is here. Overall, I already saw many possible optimizations, other that are possibly I certainly have not yet come to think about them but it was a whole lot of fun! :-)
07.23.07
The State of the Art of Paper Reviewing…
Fortunately, we have great conditions here in the new ECS building in Southampton University. One of the nice things is definitely the coffee room where we meet sometimes and in some of these times we have very interesting discussions. One of the last discussion was about a subject which I’ve been about to write, but this discussion removed all the inertia I might have had to write about it.
Some of the people present were Noura Abbas, Florian Letombe, Jordi Planes, John Colley and myself (in no specific order) and everything started because Florian was really mad about some software he is working with because it was ill-programmed, ill-documented, and with just a few modification he was able to improve not only its readability but its performance. From his growl of horror after having to look at this piece of code, I grabbed this issue and generalized it…
Truth is, that some research software is very very good. Check for example, the MiniSAT SAT solver of the SAT4J SAT solver (which Daniel le Berre developed in Java and is fast… against all odds ;)). However, most of the software is developed for the sake of getting some publishable results and once the paper is published, that’s it. If you have the luck to get the source code you’ll have to spend an obscene amount of hours to understand it, if you don’t have the source code you need to gently ask for it. Or sometimes, you’ll only have the chance to get your hands on a binary in order to compare or reproduce the authors results. It seems most of this software is developed for that specific deadline and the results are forced to appear the night before the deadline so the it can be inserted into the paper and submitted. This should be unacceptable. If high standards of technical writing, results, ideas, concepts or techniques, are required from a published paper why are there no standards on the way the code is developed and after all on the way the results are obtained? The good solution would be to have a Code Committee to review the code of, at least, some submitted papers to ascertain that its quality matches the ones in the paper and that the results are indeed reproducible. Unfortunately, I think this doesn’t happen due to the lack of manpower, to which I have no solution…
Another issue is the quality of papers themselves… How and why is it possible that some papers containing errors, which seem to come out of an horror movie, are published, some of them in well known conferences??? I guess the answer is that some reviewers are just sleeping while reviewing or don’t care about paper quality in the final proceedings. All of the people present in the meeting were able to know a paper like this. Noura mentioned the case of a paper that a colleague went through a set of equations to find in the end that they contained some errors. Other issues like this, some more flagrant were mentioned. Florian suggested a remarkable solution, which although simple would end these issues. In the final proceedings the reviewers of each paper should be included in the header of the footer of the paper pages, like (as Florian remarked) is done on some Mathematics Conferences. Now, I wonder, why is this not done in our Computer Science conferences? Why can’t we point the finger to those who do not care about published papers quality? Why can’t we applaud those who throughly review papers, accepting those that match conference quality and reject those that don’t? Even if the previous suggestion of having a Code Committee would be hard to implement, this one is trivial and should put in practice today! It seemed to be common agreement that if one day we get to manage some kind of conference, this should be done. :)
Incredibly, although some reviewers just don’t care, science keeps going forward. Every day in major conferences, new techniques, algorithms, data structures, proofs, ideas, encodings etc are presented and is very very difficult to keep up with the latest advances. What this means is that there are incredibly hard working reviewers which are not only doing their own work but also trying to diminish the blow other lazy reviewers provoke on the overall quality of conference proceedings. To these hard working people, I and — I’m sure my friends — wish all the best and give them good round of applause, I’m sure they know who they are.
Cartoons you can’t miss…
I usually don’t do this but this time they are really pretty good… via xkcd.com
Rule Number 1… “Watch out for the gotos…”
Rule Number 2… “First learn rule number 1…”
Kidding… Rule Number 2 is in this case, “Read the Fine Manual before anything else…”
07.22.07
Pownce… another Web2.0 thingy!
Lately, web services for everything you might want seem to come up everywhere. Pownce is one of those services which has a blog by its authors. Currently it is invite only but I have 4 to give away so if you want to give it a try, just leave a comment and you will receive it. First come, first serve!
07.15.07
Turing: A Novel About Computation (by: Christos H. Papadimitriou)
Turing: A Novel About Computation
Personal Comments:
(Note: This comment refers to the Portuguese translation published by Bizâncio. The portuguese translation is titled: “Turing: Um Romance sobre Computação”)
Last Valentine’s day I was in Portugal and my girlfriend offered me this book, which was definitely to my taste. I was eager to read it for three reasons:
- I knew Christos Papadimitriou from his Computational Complexity book which I enjoyed a lot;
- I liked the idea of using computer science inside a novel;
- The Scientific reviewer of this collection is Felix Costa, one of the best teachers I had back in Instituto Superior Técnico;
Overall, I didn’t like the book. The book is well-written but it is confusing and the computer science parts seems to be thrown into the novel without any kind of context. They just show up out of nowhere and for a computer scientist there is not much to learn.
On the other hand, I just might be plainly biased. Why? Because the book started and after the first three chapter I said to myself: “I won’t like this…” and so it was, I kept repeating this to myself until I finished the book in the vain hope of having a surprise and the book turning to be very good. This didn’t happen. As chapters started and ended I got more and more frustrated and nothing seemed to make sense. However, I might have lacked the insight to understand the brilliancy of the book, I’ll give you that. This because Doxiadis comments the book as being great, it was reviewed by many people one of them being Don Knuth, so… probably it was me who was not able to grasp its essence. For this reason I’ll read it again next year hoping that by then I’m able to provide a better ranking… for now… the book is taking an F!
07.14.07
Stow it…
Not in your distro package repository?!? Stow it!
All of us feel that sometimes the package we want is not on our distribution repository, be it Gentoo, Ubuntu or Debian. The general solution which I found only a couple of months ago and has been working perfectly is GNU Stow.
Stow allows you to install packages in /usr/local and keep track of what was installed or not. The general procedure is:
- Get the software tarball;
- Unpack it;
- Configure it using a prefixed directory (usually inside /usr/local/stow);
- ./configure –prefix=/usr/local/stow/<packagename>
- Stow it using the package name. Go to /usr/local/stow and write ’stow <packagename>’. Stow will create the correct symlinks from usr local directory to the package directory.
- cd /usr/local/stow
- stow <packagename>
Use the software!!! Whenever you want to remove it just go to the stow directory, e.g. /usr/local/stow and
stow -D <packagename>
With this I was able to build, install and later remove all of E17 packages cleanly. Nice, heh? (Many more options to tweak stow behavior can be found in its manual.
Shooter
Plot Outline:A marksman (Wahlberg) living in exile is coaxed back into action after learning of a plot to kill the president. Ultimately double-crossed and framed for the attempt, he goes on the run to track the real killer and find out who exactly set him up, and why.
Personal Comments:
I see the shooter as ‘one of a kind’. It seems an original idea, I liked Mark Wahlberg performance and the plot is good and full of action. I do recommend this movie. I saw it in the cinemas with a huge screen and great sound but I guess it is as good as at home. Just watch it! You will definitely have a great time.
The Sentinel
Plot Outline: A secret service agent is framed as the mole in an assassination attempt on the president. He must clear his name and foil another assassination attempt while on the run from a relentless FBI agent.
Personal Comments:
Here I am, trying to write about movies I’ve seen some time ago but lately time as been of great importance so these low priority reviews moved to the end of the queue but here they are.
This movie, as a 24 fan, is very awkward in the sense that Kiefer Sutherland is Jack Bauer and no one else. I definitely prefer him as Jack. However, the movie itself revealed Eva Longoria, the desperate housewife which becomes a very sexy police officer. The plot itself is nice but it lacks action. I would imagine Kiefer doing a better movie than this one. Unfortunately, it was this the result. Not that bad but it’s a nice renting for an evening.
07.13.07
So, I have a Second Life…
Only right about the other day it came to my attention that there’s already a second life client for Linux. Wow…I needed to try it since I have always heard about it but never tried it before. So I did, named myself Pauli Hapmouche and went in…
OH NO!!! I’M NAKED… fortunately for some unknown reason some clothes appeared on me… as I started pressing the keys to see what I could do… OH YES!!! A NAKED GIRL JUST FELL FROM THE SKY! :-) It was definitely fun and I had the opportunity to take a screenshot.
Definitely, I don’t understand second life hype. Why? What you do there? I’ll go there from time to time but unless I understand the reason to be there regularly my second life alter ego will show up rarely!
07.08.07
With 1.18£…
You can buy these… definitely you couldn’t find better ones anywhere that cheap… They are just delicious! 
On the other hand you can’t get this…
(No, it’s not mine… yet! :-) )
