Lambda the Ultimate

EWD611, Edsger Dijkstra, 1976

My subject should be very simple, for it is only the difference between the orientations of computing science at two sides of the Atlantic Ocean.

I chased this up while looking for Alan Kay's rebuttal "On the fact that most software is written on one side of the Atlantic Ocean" which I couldn't find. I was struck by these passages:

My first visit to the USA, in 1963, was the result of an amazing invitation from the ACM. Without the obligation to present a paper I was asked to attend —as "invited participant", so to speak— a three-day conference in Princeton: for the opportunity of having me sitting in the audience and participating in the discussions, my hosts were willing to pay my expenses, travel included! As you can imagine, I felt quite elated, but shortly after the conference had started, I was totally miserable: the first speaker gave a most impressive talk with wall-to-wall formulae and displayed a mastery of elaborate syntax theory, of which I had not even suspected the existence! I could only understand the first five minutes of his talk, and realized that I was only a poor amateur, sitting in the audience on false pretences.

I skipped lunch, walking around all by myself, trying to make out what the first speaker had told us. I got vaguely funny feelings, but it was only during the cocktail party that evening, when I had recovered enough to dare to consider that it had all been humbug. Tentatively I transmitted my doubts to one of the other participants. He was amused by my innocence. Didn't I know that the first performer was a complete bogus speaker? Of course it was all humbug, everybody in the audience knew that! Puzzled I asked him why the man had been invited and why, at the end, some of the participants had even faked a discussion. "Oh, on occasions like that, we just go through the motions. IBM is one of the sponsors of this conference, so we had to accept an IBM speaker. He was given the first slot, because the sooner that is over, the better." I was flabbergasted.

This vividly reminds me of the first time I attended an ACM conference on programming languages! Though it's amazing to think that back in the golden age there would be just one bogus talk :-)

An Analytical Approach to Programs as Data Objects (PDF), Olivier Danvy, 2006.

This work presents an analytical approach to programs as data objects, i.e., to programs
whose representation is operated upon by other programs. The approach is analytical in
that a variety of program manipulations is considered and their impact on program understanding,
design, and efficiency is measured.
Most of the programs considered here are language processors, i.e., programs interpreting,
translating, or transforming other programs. As for the program manipulations, they
concern block structure and lexical scope, the representation of functions at run time, and
the representation of control.

A dissertation by Olivier Danvy. I haven't read it yet, but it sounds like a compilation of all the work he has been doing for the past several years. So there is probably not too much that is new, but it should be presented more cleanly and coherently drawing on the connections that join them.

Alrighty, another question for which I'm not sure how to start looking for answers. Don't worry, this will probably be the last one for awhile.

The idea for this one is that you have version 1 of a program, and you make a change to it. Now how does version 2 differ from version 1? Or put another way, what inputs/test cases end up returning different results from before?

The purpose of this is to develop a tool that will help to ensure one is not introducing any bugs. I'm aware that there are some computability issues. I'm not asking for anything that solves the halting problem. I think that such a tool could still be useful.

I've been studying static analysis and formal verification. With more study I think I could answer this question for myself, but that's going to take forever :)

And, on a more general note, are there any heuristics for figuring out what to look for when one wants to answer a question like this? Or is it you just keep studying and following leads until you get somewhere? I don't mind the latter, it's just a lot of work that I'd rather avoid if I could :)