Previous Up Next
Dutch / Nederlands

Diary, May 2012

Sun Mon Tue Wed Thu Fri Sat
          1   2   3   4   5
  6   7   8   9  10  11  12
 13  14  15  16  17  18  19
 20  21  22  23  24  25  26
 27  28  29  30  31

Tuesday, May 1, 2012

Peter Struycken

At 17:11, I bought the book P. Struycken (ISBN:9789056626051) from bookshop De Slegte for € 16.99, which is about the works of Peter Struycken, a Dutch artist who often used computer programs during the creation of his art works.

Wednesday, May 2, 2012

Peter Struycken: Structure 7

Last Sunday, I looked at Structuur 4,5,6,7 made by Peter Struycken and the algorithm used to make it. I did not notice the rather obvious structure, which I read about yesterday evening in the book P. Struycken on page 108, that it build-up with squares of four elementary squares. This evening, I spend some time turning the bottom pattern of the work of art (downloaded from Kunst.Nu) into a binary representation using a script for the MySample editor. In the process, I made some fixes to this editor as well. The image that is produced by this script is:

Tuesday, May 8, 2012

P. Struycken: Five books

Today, the five books about/by P. Struycken that I ordered from Luïscius Antiquarian Booksellers arrived. The books with the prices are:

Friday, May 11, 2012

IParse: Parallel parser

In the past weeks, I worked on a parallel parse version of IParse. The first parser that I implemented as part of IParse was a recursive back-tracking version, which jumps for- and backwards through the text in an attempt to parse the text according to the given grammar. For a very long time, I have been thinking about a version that would try all alternatives in parallel and would be strickly speaking only move forward through the text. This evening, I managed to parse the first text ("12") with a very simple grammar ("root : int eof .") succesfully. I does not look much, but I still consider it as an important milestone, because the parallel parser is a rather complex thing. It maintains two tree like structures in parallel. One tree like structure represents all the alternatives. The second tree is an memory efficient implementation of a collection of stacks, where each stack belongs to one of the active alternatives. Each stack represent the nesting of the rules that have been applied to parse the text up until the given point. The structure of the actual parsing routines looks very much like the one used for the heap implementation of the back-tracking implementation (which was released on October 2, 2011) and in the past week, I realized that they could be combined, where only the execution part would be different. Maybe that will be my next project, when this will be finished.

Sunday, May 13, 2012

IParse: Parallel parser

This weekend, I worked on the parallel parser in IParse. I removed a number of bugs but I am still encounting problems, which become harder and harder to debug. Also added code to assist debugging. However, I do have good faith that I will be able to weed out these bugs. Today, I discovered that performance is very bad compared to the other parsers. Implementing an alternative memory allocation strategy (keeping a list of deallocated objects to avoid calls to system allocation routines) did not show a significant improvement. I am afraid it is becoming a rather academic exercise, one that I will finish anyway.

Thursday, May 17, 2012

Smallest counter example

In the past days, I have been looking at problem in the new parallel parsing algorithm in IParse which I found when trying to parse a preprocessed C file with a C grammar. Today, I have tried to constructing the smallest counter example, for which the parallel parsing algorithm fails while the back-tracking algorithm gives the correct answer. I don't know whether it is the truely smallest counter example, but it is small enough, I think, to further investigate the cause of the problem. It is at least a lot smaller than the C grammar from which I started. The counter example grammar is:
root : expr eof .

expr : declaration ";" [decl]
     | ident "+" ident ";" [add]

declaration : ident declarator OPT [type] .

declarator : "*"  | .
With the input "a + a", the parallel algorithm says that it expects an "*" or end-of-file at place of the "+", while the back-tracking algorthm parses the input correctly as an 'add' expression.

Sunday, May 20, 2012

Ambigious C grammar

I have finally finished a problems with the new parallel parsing algorith in IParse related to alternatives not being reduced. The problem was related to a fundamental error in the algorithm managing the tree of alternatives. I had used a Boolean for the success state, but it should have been a counter. This is something I had thought about before in detail. I usually do not write down my algorithm designs when I think about them. Yesterday evening, I remembered this use of a counter, but it was only this morning that I fixed an important detail.

But the algorithm still gives a different result when parsing the example scan.pc file with the C grammar. The difference is related to the very ambigious C grammar. Normally a statement like "a = 1;" is read as assignment stament, but according to the C grammar it can also be parsed as a declaration with an initialization. Also the statement "print(x); is usually seen as a call to a function with a single argument, but it can also be parsed as a prototype declaration with the type "x" for the first argument. It is the following grammar rule that is causing the problem:

        : declaration SEQ OPT statement SEQ OPT
I now realize that the back-tracking algorithm give preference to the clause following a sequence, while the parallel algorithm gives preference to the element in the sequence instead of what follows. It would not surprise me, if made this like this ambiguity in the used C grammar. Actually, it goes against the definition of a "greedy" algorithm. I could fix the parallel algorithm to match the behaviour of the back-tracking algorithm. I thought about adding an option to switch the behaviour, but when I give it a little more thought, I realized that there are two ways to interpret the "OPT" keyword. The grammar rule "x : y OPT z." can be interpreted in a greedy style: "x : y z | z." or a non greedy style "x : z | y z. (assuming that the clause before the bar-symbol get preference of the one following it). I similar problem plays with the sequence grammar constructs ("SEQ", "LIST", and "CHAIN"). I think I should add a new keyword (for example "AVOID") to indicate the preference.

Monday, May 21, 2012

P. Struycken

Today, the book Struycken: Structuur, verscheidenheid en verandering by Marie Hélène Cornips editor (ISBN:9789063221089) arrived, which I had ordered from ALEPH BOOKS for € 15. It is signed by P. Struycken on October 20, 1984. The book consists of a collection of seventeen articles by various authors about various subjects related to the works of Struycken.

Wednesday, May 23, 2012

Kabuki Syndrome and KDM6A

The paper Deletion of KDM6A, a Histone Demethylase Interacting with MLL2, in Three Patients with Kabuki Syndrome by Damien Lederer et al describes that defects in the Lysine-specific Demethylase 6A (KDM6A) gene (also known as UTX gene), which interacts with MLL2, have been found in individuals with Kabuki Syndrome that do not have any defect in the MLL2 gene. If I understand it correctly, this does not account for all case of Kabuki Syndrome that do not have a defect in the MLL2 gene, meaning that the puzzle has not been solved yet.

De Slegte: special evening opening

This evening, bookshop De Slegte was open for the kick-off of the spring sale. I arrived a little after half past five. I was told that they would close at a quarter to six and reopen again at six. But there were only a few customers in the shop at a quarter to six that they only closed for less than a minute. We were all given tickets, for the prize draw that would be held at seven o'clock. I got the ticket with number 601. We were also given a bag with the text "Bijzondere boekentas" (in English: "Special book bag") containing the books Er was eens een God by Jan Blokker, Jan Blokker Jr. and Bas Blokker (ISBN:9789025426163) and Zadelpijn: De Reisgids by Liza van Sambeek (ISBN:9789044606294). There were a lot of books on sale for just € 2.50 and a few for € 5, but I did not find anything worthwhile. I also looked around the rest of the store, because they gave a discount of 10% on all items (except the books for which the price was fixed by law). In the end, I bought Tramwijzer 1: In de sporen van Brussel van zuid naar zoniën for € 2,25 (including 10% discount) mainly because of the nice map of the public transportation routes of Brussels. It was a little before half past seven when I left the shop.

This months interesting links

Home | April 2012 | June 2012 | Random memories