nomeata’s mind shares
Entries from May 2012

Today, it must have been exactly 10 years that I started using Debian. The story of how I came to Debian shows some of its strengths, so I’ll use this occasion to share it.

I spent the first half of 2002 as an high-school exchange student in Wenatchee, USA. I was already a user of Linux at that time: I made my first contact roughly in 1996 and did my first installation at home two years later, but all that time I was dual-booting and my main system was a well-arranged Windows 98. The machine was a regular tower PC, but nevertheless I put the computer into my trunk when I flew to the US. It took away most of the space, and I had to put some of my cloths inside the case.

So I was there, happily using my Windows and my manually set up “Linux From Scratch” until one day the inevitable happened; inevitable at least until you start doing backups: On April 30th, my hard drive crashed, and took the two systems together with 4 years of personal data with it.

Two weeks later I had a new hard drive and was pondering my options. I did plan to install Windows again; at that time Windows XP was just released. But I wanted a German version of Windows, which would be hard to get there. Also, I did not want to use Linux from Scratch any more, and wanted to make a well-founded choice of a distribution. On the other hand, I really wanted to get my machine up and running quickly, to be able to read my mail more comfortably. I had heard that Debian had good support for network installations (downloading a full 700MB CD was something to avoid at that time), so I grabbed some netinst images, burned a CD, and quickly installed Debian.

I was planning to use the system for about two weeks. I did not pay any particular attention to the setup. Heck, I even picked from my Simpsons sidekick machine naming scheme one that I would not miss being used up (“barney”). Nevertheless, I was using this installation for many years (and many upgrades), until I eventually switched to using laptops. In fact, that very installation is still on the machine somewhere and works. I did install Windows XP a few weeks later as well, but hardly used it. So May 12th of 2002 was when I turned into a full-time Linux and Debian user.

I soon became interested in Debian the project and started to contribute. But that is another story for another ten year anniversary blog post, most likely on October 21, 2013...

I must say that I do like free groups. At least whenever I play around with some theorem provers, I find myself formalizing free groups in them. For Isabelle, my development of free groups is already part of the Archive of Formal Proofs. Now I became interested in the theorem prover/programming language Agda,so I did it there as well. I was curious how well Agda is suited for doing math, and how comfortable with intuitionalistic logic I’d be.

At first I wanted to follow the same path again and tried to define the free group on the set of fully reduced words. This is the natural way in Isabelle, where the existing setup for groups expects you to define the carrier as a subset of an existing type (the type here being lists of generators and their inverses). But I did not get far, and also I had to start using stuff like DecidableEquivalence, an indication that this might not go well with the intuitionalistic logic. So I changed my approach and defined the free group on all words as elements of the group, with a suitable equivalence relation. This allowed me define the free group construction and show its group properties without any smell of classical logic.

The agda files can be found in my darcs repository, and the HTML export can be browsed: Generators.agda defines the sets-of-generators-and-inverses and FreeGroups.agda (parametrized by the Setoid it is defined over) the reduction relation and the group axioms. Here are some observations I (disclaimer: Agda-beginer) made:

• Fun fact: Free groups exist not only in classical logic.
  
• Without any automation as in Isabelle, even simple things get quite complicated. A simple substitution of an equality with subst requires me to specify not only the equality and the term I want it to apply, but also to repeat the common part of the terms. Or when using the associativity of list concatenation, I have to pass all three sublists to the lemma. Maybe I am a bit spoiled by Isabelle, but I’d be worried that this would prevent large proofs.
• The levels are also annoying. Although my theory stays within one level, I have to annotate it everywhere. I’d expect the type inference to figure this out for me.
• Equality reasoning with begin ... ∎ is quite nice and surprisingly well readable.
• Besides the additional work, it is nice to be able to do the proof in almost all detail. There is a limitation, though, as some steps are done automatically (if they happen to occur when evaluating/normalizing a term) and the others, even if similar-looking, are not.
  
• It’d be great if one would be free in the choice of editor, but vim users generally have a hard time in the field of theorem provers.
  

If I were to extend this theory, there are two important facts to be shown: That there is a unique reduced word in every equivalence class (norm_form_uniq), and the universal property of the free group. For the former (started in NormalForm.agda) I’m missing some general lemmas about relations (e.g. that local confluence implies global confluence, and even the reflexive, symmetric, transitive hull is missing in the standard library). For the latter, some general notions such as a group homomorphism need to be developed first.

I planned to compare the two developments, Isabelle and Agda. But as they turned out to show quite things in different orders, this is not really possible any more. One motivation to look at Agda was to see if a dependently typed language frees me from doing lots of set-element-checking (see the “mems” lemma in the Isabelle proof of the Ping-Pong-Lemma). So far I had no such problems, but I did not get far enough yet to actually tell.

Thanks to Helmut Grohne for an educating evening of Agda hacking!