1 Dijkstra

1.1 Edsger W Dijkstra

  • b. Netherlands, 1930 - 2002
  • Pioneer in many aspects of computer science
  • Dijkstra's algorithm, ALGOL compiler, concurrency, structured programming, etc…

1.2 Essay

  • On the role of scientific thought (1974)
  • Written while Research Fellow at Burroughs Corporation
  • Thoughts on problems observed in "computing science"
  • A widespread lack of … "scientific thought"

2 Problem

  • "… when scientists no longer know, what science is supposed to be about, we are in bad shape. Hence this essay."
  • … so what is science supposed to be about?

3 Detour

3.1 What is a computer program?

  • Consider whether each of what follows is "useful" or "helpful"
  • Dijkstra's terms – to be revisited

3.2 Def 0

  • It makes the computer do something

3.3 Def 1

  • Something that translates software to hardware

3.4 Def 2

  • Bits stored on a machine that get read by the machine
  • Causing the machine to do something (or "nothing")

3.5 Def 3

  • Symbols drawn from a finite set
  • That are supposed to follow syntax rules
  • That may or may not have some "meaningful" semantics
  • To be interpreted directly by humans
  • Or to be interpreted by machines
  • Possibly producing side effects for human interaction

3.6 Def 4

  • An intersection of the following categories
  • Human Intent
  • Language Syntax and Semantics
  • Language Lexing and Parsing
  • Language Compilation
  • Operating System Design
  • Machine Design
  • Hardware Engineering

4 Review

  • Which ones were "useful" or "helpful"?
  • Probably context-dependent
  • Dijkstra: for computer science, some definitions are better
  • What does this mean?
  • Some motivating examples…

4.1 Chasing General Acceptance

… [a] laboratory [with] new computing equipment of such a radically different architecture, [they] had concluded that a new programming language was needed … But they got their language design never started because they felt that their product should be so much like FORTRAN that the casual user would hardly notice the difference "for otherwise our users won't accept it"

4.2 Reponse to Provable Program Examples

… standard objections raised from the floor… : "What you have shown is very nice for the little mathematical examples with which you illustrated the techniques, but we are afraid that they are not applicable in the world of business data processing, where the problems are much harder, because there one always has to work with imperfect and ambiguous specifications."

4.3 Specification vs Implementation

… the LISP 1.5 Manual: halfway their description of the programming language LISP, its authors give up and from then onwards try to complement their incomplete language definition by an equally incomplete sketch of a specific implementation. Needless to say, I have not been able to learn LISP from that booklet!

4.4 Specification vs Implementation (2)

At an international summer school in 1973… [a professor said] "ALGOL 60 was a very inefficient language", while what he really meant was that with the equipment available to him, he and his people had not been able to implement ALGOL 60 efficiently.

4.5 Specification vs Implementation (3)

Another fairly well-known professor …repeatedly argued in public that there is no point in proving the correctness of one's programs written in a higher-level language "because, how do you know that its compiler is correct?".

4.6 Unimplemented Languages

… the often expressed opinion that "one cannot use a programming language that has not been implemented". But this is nonsense, of course one can! One can use any well-defined programming language, whether implemented or not, for writing programs in; it is only when you want to use those programs to evoke computations, that you need an implementation as well.

5 Scientific Thought

5.1 Modularity

  • "the way in which the knowledge in the world has been arranged"
  • break subjects down into orthogonal, distinct areas
  • "separation of concerns" that can be independently studied

5.2 Cohesion

  • But the indiviudal parts cannot be a random assortment
  • There must be "internal" cohesion and "external" viability
  • Internal: knowledge and its applications support each other
  • External: degree of bootstrapped, self-sustaining knowledge domain
  • It must hang together; there should be good abstractions
  • Separate concerns, but regarded in context

5.3 "Intelligent Thinking"

"Scientific thought comprises "intelligent thinking" as described above. A scientific discipline emerges with the —usually rather slow!— discovery of which aspects can be meaningfully "studied in isolation for the sake of their own consistency", in other words: with the discovery of useful and helpful concepts. Scientific thought comprises in addition the conscious search for the helpful concepts."

5.4 Hmm…

  • What is useful?
  • What is helpful?
  • Both seem to be predominantly a posteriori concepts
  • Both seem to be defined by the application of theory
  • aka the context of implementation
  • (though theory can be applied to more theory…)

5.5 Where shall wisdom be found?

  • The goal of scientic thinking is reasonably clear
  • Abstraction and modularity remain foundational paradigms
  • BUt it's an ongoing process to determine the right order of things
  • Dijkstra himself acknowledges the tension in "useful"
  • A call to for continuous introspection

6 Postscript

6.1 Evaluation Order of Arguments

#include <stdlib.h>
#include <stdio.h>

int main() {
  int i = 1;
  printf("%d %d %d\n", i++, i++, i);
  return 0;

6.2 What does it print?

√ dijkstra74 % clang order.c -o order_clang.c
clang order.c -o order_clang.c
order.c:6:25: warning: multiple unsequenced modifications to 'i' [-Wunsequenced]
  printf("%d %d %d\n", i++, i++, i);
                        ^    ~~
1 warning generated.
√ dijkstra74 % ./order_clang.c
1 2 3

6.3 Implementation-Dependent


6.4 (Opinionated) Better Specification

The Java programming language guarantees that the operands of 
operators appear to be evaluated in a specific evaluation order, 
namely, from left to right.

It is recommended that code not rely crucially on this specification. 
Code is usually clearer when each expression contains at most one side 
effect, as its outermost operation, and when code does not depend on 
exactly which exception arises as a consequence of the left-to-right 
evaluation of expressions.