On Credibility

I just had a conversation on Skype with my mother and I made an interesting reflection while seemingly lecturing on our attitudes toward great authors. I was talking about the way Edsger Dijkstra was prejudiced and said that I found it too bad because he was otherwise very smart. And then I thought back on the period where I had not realized the prejudices that he had and wondered what I could do against that. I noticed, not for the first time, that, as I read, as the author gains my respect and esteem I tend to give him (or her) the benefit of the doubt. However, people that are always objective throughout their writing probably don't write much so, for the rest, we should remain prudent not to consider everything that is said by any trusted author to be true. The next question that I would expect to ask myself while reading what I wrote is: so, what difference does it make whether an author is trusted (alternatively more trusted) or not (alt. less trusted? Well, for one thing, an author that I trust is one of which I have read many text and it is a little bit less likely that I would be surprised by something he says or write. More importantly, when I hear people talking and I know the particular author is also giving his opinion, I'll give more attention to that author because I trust him. As a corollary, when I have interrogations on topics of which I suspect my author to be interested, I'll first try to find out what his opinion is on the topic. However, it shouldn't mean that I'll be satisfied once I did. As a good computing scientist, I just saw a case where the good behavior to take is ambiguous. If I stress my imagination a lot, I can imagine cases where I trust many authors. What to do? The naive extrapolation is to choose one randomly whenever I need to. It is not very satisfying so I go ahead and look at the next credible solution: to define a more subtle notion of trust for which I can trust author X on topic Z more than I trust author Y on topic Z. If I take one topic at a time for my investigations, this should be fine-grained enough. As a final note, I am not stating that this is what I usually do. It is more like the exposition of a judgment error I do more often than I would like to and a possible solution that I would like to adopt. Simon Hudon Zürich August 19th 2009

Algorithms in Object Oriented Programming

Approximately two years ago, I was writing a set of classes for dealing with graphs. At one point, I had to provide facilities for depth-first and breadth-first traversal. At first, I thought of doing it as a higher order function: it would be a regular encoding of a graph traversal that would use an agent --in Eiffel talk, in C# talk, it would be called a delegate-- to process every node encountered. This seemed a lot of work to set up and use and I decided to create particular kinds of cursors that would enumerate the nodes in preorder, postorder or in breath-first order. It was a very interesting exercise because I transposed the state of the computation of the algorithm to make it the state of a class. At the time, it seemed like a very nice reinterpretation of an algorithm to have it fit a more object oriented context. I did not push that investigation further. At the moment, I am working on the development of a parsing algorithm and its correctness proof. One of the decision I took was to have a token reading primitive instead of passing a complete sequence of tokens. With respect to the formulation of the algorithm, there is very little differences but with respect to its interface, the difference is big enough to allow me to do an interesting observation. The reading can be interpreted as a routine called by the program implementing the parsing algorithm, but it could also be interpreted as a method of a class whose state is described by the local variables of the algorithm. This would allow, for example, to interpret keystrokes as tokens and feed them to the parser as they come. What if we just considered it as an input without regard to whether it is ordered by a client or by the module. With that view, we could have a scanner which outputs one token at a time and inputs one character at a time. We could plug the input of the parser on the output of the scanner for which the input could either be plugged on a streamed string or on the keyboard input without significant changes. Furthermore, if we wanted to decouple further the lexical analysis and the syntactic analysis, we could put a buffer between the two (still without changing the algorithms) and we could even put each machine on its own process. Some theoretical framework which is very useful to conceive that is that of action systems. With just a few exception, an action system could be understood as a canonical view of (not necessarily terminating) programs where we have one loop over a set of one line guarded commands. For example, for the following statement: a := 32 if b > c then b, c := c, b [] b <= c then skip fi We could get the following loop which we will consider as an action system: line := 0 ;do line = 0 then a, line := 32, 1 [] line = 1 /\ b > c then b, c, line := c, b, 2 [] line = 1 /\ b <= c then line := 2 od The advantage of using an action system instead of the corresponding program (when there is a nice one) is that the action system can compose for various purposes. If you want to simulate the concurrent execution of two programs, taking the union of the actions (the lines in the loop) of their action system will give you a model of how the two programs will execute. The assertion that you put in both programs must become invariants in the loop attached to line numbers. It is similar to the methods described in the Gries-Owiki theory and in A Method of Multiprogramming by Netty van Gasteren and Wim Feijen. The other use of the action system is that it can model objects. Each action can be understood as a method or as a method call and it allow one to model "concurrent" access to objects much better than what we have with structured programming geared with type bound procedures (what we see all the time in OO languages). Simon Hudon Finished on August 26th Zürich

First post

After a long hesitation, I finally took the decision to start this blog. Admittedly, a lot of what I'm going to write is pretty technical but I'm going to take the liberty of switching from technical and non-technical topics as often as I feel like it. I am a big fan of Edsger W. Dijkstra and I think his EWD series is a great idea. However, I'm not sure that I'm completely in shape to make such amazing pamphlets as he did. From time to time, I plan to try it and I hope that any reader that finds it excessive will be able to tell me so to help stay as rigorous with my social (or other) commentaries as possible. I also appreciate the way in which he presented his work and his exercises but I am not sure yet that this is the right place to publish and receive comments on those. Since I see this account mostly as a trial for blogging for now, I'm going to try different things and see how it turns out. Another consequence of this is that I'm going to discover the features of the server as I go. Simon August 15th 2009 Zürich P.S. I already have some notes on my Facebook profile but I'm not sure I want to move them all over here. I'm going to think about it. P.P.S. Since I wrote and stored essays on different platform, I'm going to try and put them all or almost all in the say public place. Don't be surprised of some posts appear with a date anterior to that of this post.

On the Pervasiveness of Social Networks

I was about to write something on LaTeX or on technical writing but while surfing (read: procrastinating) I observed how much the features on many social networks in a wide sense of the word overlap on many points. It feels like some of the strongest incentives -at least for me- of joining one or another of the social networks is to get in contact with people which are not present on platform I'm on and to benefit from features that others don't have. For instance, I have an account on Facebook -no, really!-, on Twitter (which I don't really use), on google mail, google reader, google talk and linkedin. I'm sure I omitted some but it does give an idea on the many account I survey on regular basis. Just to see some of the zones of overlapping, we see that all keep a list of contacts, although the Google platform seem to use a common one. They also offer the possibility, with various levels of necessity of exposing one's profile, i.e. name, interests, education, jobs, etc. There is some measures of unification but it seems limited to the consumption of links, for example for sharing with friends on facebook or adding rss feeds. What could possible make the situation simpler for users of multiple platforms? I am very reluctant to suggest imposing or pushing a standard since it seems like a nice path to technological stagnation. For now, I'm happy to leave the question open and see if my reader(s) (if any) have anything to say on that matter. Simon August 14, 2009 Zürich

To Blog or Not to Blog

Having seen the recent birth of Simon Mathieu's blog and especially the motivations he evoked to do it, I started to wonder again whether it would be a good idea for me to do it as well. Since I seem to have some readership here, I think it would be a good idea for me to stick with Facebook's note for expressing various thoughts and distributing essays. I'm also considering to put technical documents here since I would like to give the opportunity to those I have intrigued with my talks of formal methods to see how I conduct it. For example, I am now conducting an experiment to implement something similar to the shunting yard algorithm to parse mathematical expressions with custom operators and precedence rules. I would like to include infix binary operators, prefix and bracketed operators (including parenthesis), quantification and substitution. The peculiarity of the experiment lies in the fact that I use the proof obligation to guide my programming efforts and it results in a program and its correctness argument growing together. Also, it allows me to stall the moment I don't know what I'm talking about so both the proof and the program are kept as simple as possible. I would like to know if anybody would like to be tagged when I upload the document. Simon August 14th, 2009 Zürich

Pondering about Reasoning Errors

This note is mostly about teaching and, in general, communicating with other human beings. I have thought about writing it for a while but I was afraid not to have enough material. I'm writing it now because of new observations and I don't care too much about the length, today. In logic, we have the two important notions of soundness and of completeness. In short, a logical system is sound if you can only use it to prove statements that are true (but maybe not all of them) and complete if you can prove all statements that are true (but maybe also some false statements). I mention them because they appear more and more relevant to the way I choose to explain or with which I choose to help people. In such cases, it is necessary to make assumptions in order to explain or skip notions. Two kinds of errors are of interest for me here: either I assume that the other person does not know something and choose to explain it while he or she already know about it or I assume that he or she does and skip it while he or she does not know about it. In the first case, the reaction can be to be insulted because the attitude seems patronizing because the notion seems obvious. In the second case, the other person can miss a notion and be too afraid to appear stupid to ask about it. While I was an intern at A2M (a game developer in Montreal), my supervisor, which I regard with high respect, taught me that it is desirable to make communications as simple and concise as possible and to trust that the other person (in this situation an engineer or a scientist) will not be shy to ask about the missing parts. During the last hour, I've been thinking about this post while doing my groceries and I realized that there are a handful of people that I trust enough to be very straightforward in my communications because I've been talking to them for a long enough period to see that they are active while listening. For the others, it does not mean they are any less. It just means that I don't know if they will ask questions and, from time to time, I don't want to risk them misunderstanding me. In no case is this a sign that I mistrust someone's intelligence because I noticed recently that I was too explicit even with some people which I have in high esteem. This is pretty short but it's all I could summon before my stomach started threatening me. Simon August 14th 2009 Zürich