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
|
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.
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:
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:
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.
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.
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.
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:
decl_or_stat
: 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.
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.
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.
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
