The Revolution (The Preview)

This week I continued the work on diagram embeddings and, unfortunately, I have discovered that Diagram did not actually work properly. I have written a status report E-mail to Tom, in which I briefly outine the progess. This E-mail (with some omissions) will serve as this week’s blog post, because writing a proper blog post would take me at least three hours, and I would rather code right now, given the limited timeframe.

Unfortunately, I’ve got some, well, ambiguous news.

Remember I told you about hash-randomisation failures in computing
diagram embeddings? Well, it turned out that diagram embeddings was
quite OK, and the problem went as far back as the Diagram class.
Essentially, I have done a really bad job implementing it at the
beginning of the summer: I wanted it to directly store all possible
morphism compositions. However, in that implementation, I didn’t
really store all compositions, but just a part of them; which part I
stored depended on the order in which the morphisms were supplied
(severe facepalm :-( )

I tried thinking of some good fixes, but, as you can easily imagine,
the whole idea of storing all composites has suffered an epic
disintegration in the face of diagrams with cycles. I am really
_really_ astonished at how this has managed to slip by me for such a
long time! :-(

I have spent the first one third of Friday on trying to save the
existing design somehow, by carefully processing all possible edge
cases, but this has very quickly started to be abominable, and, of
course, it didn’t work. So, I have spent the greater part of Friday
on thinking out a new Diagram. I have spent all of yesterday, (all of
Saturday, that is), on implementing this new concept. Basically, the
new Diagram only stores the relevant generator morphisms, but it is
still able to correctly determine and enumerate the morphisms that
belong to it. It is also capable of determining whether it is finite
or not (i.e., whether there are cycles in the underlying directed
multigraph). When asked for all morphisms, the new Diagram yields a
generator which acts correctly both in the finite and infinite cases.
In the finite case it produces all the morphisms of the Diagram. This
is clearly impossible in the infinite case, but Diagram is
sufficiently clever in this case to produce the morphisms in a
BFS-like manner. Intuitively, it will first yield all length one
morphisms, then all morphisms of length two, etc.

I have made some changes to the interface of the Diagram to better
reflect the new internals. Nevertheless, the behaviour in the finite
case is the same as that of the old Diagram (modulo some property
names and minor changes, of course).

One bit of good news that deserves standing out in a separate
paragraph is that I only had to change _one_ line of code in
diagram_drawing.py to get it to work with the new Diagram. (Well, I
did drop three other lines, because they were redundant), so this
radical swerve with the Diagram has left the larger part of my GSoC
work unaffected.

Now, I have started cherry-picking the diagram embeddings code, and I
have arrived at a conclusion that Diagram has to be further extended.
(“Extending” means adding something new, not rewriting it again.)
Namely, it is insufficient to know whether the whole Diagram is finite
or not; I really need to know whether a certain hom-set is finite or
not. It’s not that hard to implement, and I’ve got a cool book on
graphs; however, it’s going to require some extra time.

Here comes the most important part of my message: I’m working at the
fullest possible cruising speed (not sprinting yet; that I’m saving
for the last 100m). I won’t obviously have everything done tomorrow,
on Monday; however, I strongly believe that I only need another couple
days to finish the bulk of inferencing. Provided that on Monday we
have what is referred to as _soft_ pencils-down date, I hope that I’m
still OK with the GSoC timeframe. Further, I think I have already
mentioned a couple times that I’m going to have another couple free
weeks after GSoC, during which I will be easily able to finalise
whatever will be unfinished. Do note, however, that I definitely
expect to have inferencing done _within_ the GSoC timeframe.

Conclusion: despite the rather radical direction things have taken in
the last two days, I’m _still_ more or less fine with the timing.

At the moment, you will not be able to see the code I’m working on on
GitHub. The reason is that I’m juggling branches rather ninja-ily
right now, so I don’t really have the most relevant one to push
online, and they are all relatively short-lived. I do expect to get
back to working sequentially today, and once I’ve got there, I’ll push
to ct3-commutativity to reflect the updates.

I’m documenting everything I do in as minute detail as possible. I
think the Diagram class and the embeddings functionality has more
comments than actual code. I expect this to make reviewing and later
maintenance considerably more agreeable. Further, my commits are
almost all rather short, with acceptably long commit messages. There
is one commit that breaks the rule, however: the commit which adds the
new Diagram. It is one relatively large chunk of code, which replaces
the old Diagram with the new one and shows that the old tests still
pass modulo minor changes. I have nevertheless reformatted the
history a bit to make this commit easier to review and, of course, the
code itself is just literally stuffed with comments. All other
commits are much more like my usual ones.

Whenever I’m done with the core parts of inferencing, I will write a proper blogpost.

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s