NYCJUG/2015-06-09

Beginner's Regatta

Here we look at how we might insert lines, for debugging purposes, customized to show the line number of the file in which they appear.

Updating Lines in a File

I work with some Pascal code, using the time-honored debugging approach of “print”, like this:l

…
    if DbgPrt then println('Reached line 371: ranking.');
…
// Check if rankings have changed since previous rebalancing
   if DbgPrt then println('Reached line 385: rankings changed?');

This is a fairly effective way to narrow down the source of any number of bugs. However, either we have to be content with letting the line numbers shown in these statements become incorrect as lines are added and removed, or we have to spend considerable time doing tedious updates. Obviously, this cries out for an automated solution. Why can’t we recognize these lines and replace the line numbers with their correct values using a simple J verb?

Here’s how we developed such a simple utility.

Read File Lines and Find Where to Update

First, we’ll read in a file partitioned by line-feed characters to give us a vector of lines.

   flnm=. '\amisc\Clarifi\THB\Subset Long Short with Sector Limits.pas'
   $fl=. <;._2 ] LF (] , [ #~ [ ~: [: {: ]) CR-.~fread flnm
652
   #whln=. (<'DbgPrt') +./ . E.&>fl
652
   +/whln
11

Our initial guess of a search string to locate the lines of interest gives us 11 possibilities. Looking at some of them, we notice a few spurious hits, so we refine the search to isolate only the lines in which we are interested.

   >whln#fl
    DebugPrint, DbgPrt, DbgSectorWt, SpendCash, InvCashDbg, CoolOffDbg : boolean;
   DbgPrt := false;  // Detailed debugging -> line nums.
    if DbgPrt then println('Reached line 344: ranking.');
   if DbgPrt then println('Reached line 358: rankings changed?');
...
   #whln=. ((<'DbgPrt') +./ . E.&>fl)*.(<'Reached line') +./ . E.&>fl
652
   +/whln
9

This gives us 9 valid lines. We assign one of these to a name to develop the code to extract the sections of the line before and after the line number we’ll be re-assigning.

   str=. '    if DbgPrt then println(''Reached line 344: ranking.'');'
   I. 'Reached line' E. str
28
   28}.str
Reached line 344: ranking.');
   (28+#'Reached line')}.str
 344: ranking.');
   (28+#'Reached line ')}.str
344: ranking.');

Abstracting from these phrases, we name our first utility verb “takeUpTo” which takes the part of the line up to the line number.

   13 : 'y}.~(#x)+I. x E. y'
] }.~ ([: # [) + [: I. E.
   takeUpTo=: 13 : 'y}.~(#x)+I. x E. y'

The first thing we do is test our new verb and look at the remainder of the line we have to process.

   'Reached line ' takeUpTo str
344: ranking.');

Now we develop the phrase to return the part of the remaining line after the line number.

   ': '(13 : 'y}.~I. x E. y') '344: ranking.'');'
: ranking.');
   13 : 'y}.~I. x E. y'
] }.~ [: I. E.
   dropBefore=: 13 : 'y}.~I. x E. y'

Basic Insertion Verb

Now that we have the two verbs to break the text into the part before the line number and the part after it, we combine them with the code to insert a new line number.

insertBtw=: 4 : 0
   'start end string'=. x
   s0=. start takeUpTo string
   s1=. end dropBefore string}.~#s0
   s0,y,s1
)

We structure this to work on a single line of the selected Pascal code, generalizing it to take an arbitrary start and end target string surrounding the line number to be replaced. Testing this, we notice that the second utility verb “dropBefore” can be thwarted by lines with more than one occurrence of the target string, so we modify it to take only the first instance:

   dropBefore=: ] }.~ [: {. [: I. E.

Finally, we develop the code to apply the high-level “insertBtw” verb to each relevant line of the file, supplying the number of each line to be inserted.

   fl=. ((<"1 (<'Reached line ';': ')(,<)&>whln#fl) insertBtw &.> nn) (I. whln)}fl

Test and Continue

The first thing we do is test our new verb and look at the remainder of the line we have to process.

   'Reached line ' takeUpTo str
344: ranking.');

Now we develop the phrase to return the part of the remaining line after the line number.

   ': '(13 : 'y}.~I. x E. y') '344: ranking.'');'
: ranking.');
   13 : 'y}.~I. x E. y'
] }.~ [: I. E.
   dropBefore=: ] }.~ [: I. E.

Now that we have the two verbs to break the text into the part before the line number and the part after it, we combine them with the code to insert a new line number.

insertBtw=: 4 : 0
   'start end string'=. x
   s0=. start takeUpTo string
   s1=. end dropBefore string}.~#s0
   s0,y,s1
)

We structure this to work on a single line of the selected Pascal code, generalizing it to take an arbitrary start and end target string surrounding the line number to be replaced. Testing this, we notice that the second utility verb “dropBefore” can be thwarted by lines with more than one occurrence of the target string, so we modify it to take only the first instance:

   dropBefore=: ] }.~ [: {. [: I. E.

Finally, we develop the code to apply the high-level “insertBtw” verb to each relevant line of the file, supplying the number of each line to be inserted.

   fl=. ((<"1 (<'Reached line ';': ')(,<)&>whln#fl) insertBtw &.> nn) (I. whln)}fl

Bringing it All Together

Once we’ve tested the code and verified that it seems to work correctly, we put it all together with some documentation in a J script file:

NB.* insertDbgLns.ijs: insert line numbers into debug print lines in Pascal code.
require 'dsv'

insertBtw_egUse_=: 0 : 0
   flnm=. '\amisc\Clarifi\THB\Subset Long Short with Sector Limits.pas'
   's0 s1'=. 'DbgPrt';'Reached line '
   fl=. <;._2 ] LF (] , [ #~ [ ~: [: {: ]) CR-.~fread flnm
   whln=. ((<s0) +./ . E.&>fl)*.(<s1) +./ . E.&>fl
   nn=. ":&.>>:I. whln
   fl=. ((<"1 (<s1;': ')(,<)&>whln#fl) insertBtw &.> nn) (I. whln)}fl
   (;fl,&.>LF) fwrite flnm
)

NB.* insertDbgLns: insert debug lines w/correct line numbers.
insertDbgLns=: 3 : 0
   's0 s1'=. 'DbgPrt';'Reached line '
   fl=. <;._2 ] LF (] , [ #~ [ ~: [: {: ]) CR-.~fread y
   whln=. ((<s0) +./ . E.&>fl)*.(<s1) +./ . E.&>fl
   nn=. ":&.>>:I. whln
   fl=. ((<"1 (<s1;': ')(,<)&>whln#fl) insertBtw &.> nn) (I. whln)}fl
   (;fl,&.>LF) fwrite y
NB.EG insertDbgLns '\amisc\Clarifi\THB\Subset Long Short with Sector Limits.pas'
)

Show and Tell

Here we look at an implementation of a dynamic linear model as described here File:IntroToConstantModelDLM-West&HarrisonCh2.pdf (pdf).

Implementing a Constant Model DLM

Some excerpts from working out the “KURIT” example from West and Harrison, chapter 2.

   100%100+5
0.952381
   405%505
0.80198
   130+(405%505)*20
146.04
   Rt=. 400+5 NB. Ct-1+Wt
   ft=. 130
   Qt=. Rt+100 NB. Rt+Vt
   Qt
505
   et=. 150-ft  NB. Yt-ft
   At=. Rt%Qt
   At
0.80198
   mt=. 130+At*et  NB. mt = mt-1 + Atet
   Ct=. At*100     NB. Ct = AtVt
   Ct
80.198
   mt
146.04
   load '\amisc\J\DLM2.ijs'
   Ktab
+--+---+-----+----+---+-----+-----+---+
|0 |   |     |    |   |     |130.0|400|
+--+---+-----+----+---+-----+-----+---+
|1 |505|130.0|0.80|150|20.0 |146.0|80 |
+--+---+-----+----+---+-----+-----+---+
…
+--+---+-----+----+---+-----+-----+---+
|10|125|143.0|0.20|   |     |     |   |
+--+---+-----+----+---+-----+-----+---+
   Ct_1=. 400

   constantModel 1;1;100;5;150 136 143 154 135 148 128 149 146;130;400
    505     130  0.80198 150       20  146.04  80.198
185.198  146.04 0.460037 136 _10.0396 141.421 46.0037
151.004 141.421 0.337765 143  1.57899 141.954 33.7765
138.776 141.954 0.279417 154  12.0457  145.32 27.9417
132.942  145.32  0.24779 135 _10.3201 142.763  24.779
129.779 142.763  0.22946 148  5.23712 143.965  22.946
127.946 143.965  0.21842 128 _15.9646 140.478  21.842
126.842 140.478 0.211618 149   8.5224 142.281 21.1618
126.162 142.281 0.207367 146  3.71891 143.052 20.7367

   'tbl qfar'=. constantModel 1;1;100;5;150 136 143 154 135 148 128 149 146;130;400
   tbl
  505   130 0.8 150    20   146 80.2
185.2   146 0.5 136   _10 141.4   46
  151 141.4 0.3 143   1.6 141.9 33.8
138.8 141.9 0.3 154  12.1 145.3   28
  133 145.3 0.2 135 _10.3 142.7 24.8
129.8 142.7 0.2 148   5.3 143.9   23
  128 143.9 0.2 128 _15.9 140.4 21.9
126.9 140.4 0.2 149   8.6 142.2 21.2
126.2 142.2 0.2 146   3.8   143 20.8
   qfar
125.8 143 0.205087 25.8

From my DLM script so far:

NB. KURIT example, p. 41
'Ktits Ktab'=: 2 split <;._1&>TAB,&.><;._2 ] LF (] , [ #~ [ ~: [: {: ]) CR-.~0 : 0
Month	Forecast Distribution	Adaptive Coeff.	Datum	Error	Posterior Information
t	Qt	ft	At	Yt	et	mt	Ct
0						130.0	400
1	505	130.0	0.80	150	20.0	146.0	80
2	185	146.0	0.46	136	_10.0	141.4	46
3	151	141.4	0.34	143	1.6	141.9	34
4	139	141.9	0.28	154	12.1	145.3	28
5	133	145.3	0.25	135	_10.3	142.6	25
6	130	142.6	0.23	148	5.3	143.9	23
7	128	143.9	0.22	128	_15.9	140.4	22
8	127	140.4	0.21	149	8.6	142.2	21
9	126	142.2	0.21	146	3.8	143.0	20
10	125	143.0	0.20				
)
NB. r=0.05 : low signal-to-noise ratio.
NB. DLM{Ft,λ,V,W}: DLM{1,1,100,5} in this case.
NB. Qt = Ct ++/Wt+j + Vt+k
NB. 505 = 400 ++/100+5
NB. a) Posterior mt-1: (µ0|D0) ~ N[130,400]
NB. b) Prior for µt: (µt|Dt-1) ~ N[mt-1,Rt] where Rt = Ct-1 + Wt : 400+5
NB. c) 1-step forecast: (Yt|Dt-1) ~ N[ft,Qt] where ft = mt-1 & Qt = Rt + Vt : 130 & 505
NB. d) Posterior for µt: (µt|Dt) ~ N[mt,Ct] with mt = mt-1 + Atet and Ct = AtVt,
NB. where At = Rt/Qt (405%505), and et = Yt - ft (150-130)

NB.* constantModel: x is 1 for rounded intermediate results.
constantModel=: 3 : 0
   0 constantModel y
:
   'Ft lambda Vt Wt Ys mt_1 Ct_1'=. 7{.y
   keepTbl=. 0 7$0
   for_Yt. Ys do.
       Rt=. Ct_1+Wt
       ft=. mt_1
       Qt=. Rt+Vt
       et=. Yt-ft
       At=. Rt%Qt
       mt=. mt_1+At*et
       Ct=. At*Vt
       if. x do. 'Qt ft At Yt et mt Ct'=. 0.1 roundNums Qt,ft,At,Yt,et,mt,Ct end.
       keepTbl=. keepTbl,Qt,ft,At,Yt,et,mt,Ct
       'mt_1 Ct_1'=. mt;Ct
   end.
   A=. R%Q [ Q=. R+Vt [ f=. mt_1 [ R=. Ct_1+Wt
   keepTbl;<Q,f,A,R
NB.EG 'tbl qfar'=. constantModel 1;1;100;5;150 136 143 154 135 148 128 149 146;130;400
)

Advanced Topics

Inverting A.

How would we go about inverting the anagram generator “A.”? Alas, the obvious way does not work:

   100 A. i.5
4 0 3 1 2
   (100 A. i.5) A.^:_1] i.5
|domain error
|   (100 A.i.5)    A.^:_1]i.5

However, we notice that A. generates its results in ascending order:

   t5=. (i.!5)A."0 1 ] i.5
   t5 i. 100 A. i.5
100
   t5 -: /:~ t5
1

We'll need this:

   standardizeStr=: =: [: tolower ' ' -.~ ]  NB. lowercase no spaces

So, we could do a binary search on this without generating the entire table first. We had these anagrams to work with:

   isAnagramOf=: ([: /:~ [: standardizeStr ]) -: [: /:~ [: standardizeStr [
   'city sojourners up wry keg' isAnagramOf 'New York City J Users Group'
1
   'Jockeying surrey sup wort'  isAnagramOf 'New York City J Users Group'
1
   'Guy work syrup rejections'  isAnagramOf 'New York City J Users Group'
1
   'Wry gurus projection keys' isAnagramOf 'New York City J Users Group'
1
   'Sky guy unwire projectors' isAnagramOf 'New York City J Users Group'
1
   'Wry sojourners put icy keg' isAnagramOf 'New York City J Users Group'
1
   'city sojourner sup wry keg' isAnagramOf 'New York City J Users Group'
1
   'Us wry per torus jockeying' isAnagramOf 'New York City J Users Group'
1

Taking the first as our example,

   ]str1=. standardizeStr 'city sojourners up wry keg'
citysojournersupwrykeg
   ]str0=. standardizeStr 'New York City J Users Group'
newyorkcityjusersgroup

We want a proper permutation of str0 into str1. At first we are stymied by index’s behavior of giving us the index of the first occurrence:

   ]xx=. str0 i. str1
7 8 9 3 13 4 11 4 12 5 0 1 5 13 12 21 2 5 3 6 1 17

The repetitions prevent us from having a true permutation vector, so how do we convert this? Some experimentation gives us this:

   what=. I.&.>(<str0)=&.>str0{~xx{~I. -. whUnq xx
   where=. I.&.>(<str1)=&.>str0{~xx{~I. -. whUnq xx

update=: 3 : 0
   'what where targ'=. y
   targ=. (what) where}targ
)
progressiveUpdate=: 3 : 0
   'ww targ'=. y
   while. 0<#ww do. targ=. update ({.ww);targ end.
)

   ]xx=. progressiveUpdate (}.what,.where);xx
7 8 9 3 13 4 11 19 12 5 0 1 15 16 20 21 2 18 10 6 14 17
   #xx
22
   #~.xx
22

So, taking an initial guess at the midway point of the range of permutations:

   guess=. -:!x:22
   guess
562000363888803840000

We develop a way to compare permutation vectors to tell which is greater:

   2#.(guess A. i.22) < xx
2024400
   2#.(guess A. i.22) > xx
2104367
      (guess A. i.22) ,: xx
11 0 1 2  3 4  5  6  7 8 9 10 12 13 14 15 16 17 18 19 20 21
 7 8 9 3 13 4 11 19 12 5 0  1 15 16 20 21  2 18 10  6 14 17
   (2#.(guess A. i.22) > xx) > 2#.(guess A. i.22) < xx
1

Eventually, we develop the following routine to find the proper guess:

   ]guess=. (}:guess),~<.1r2+-:+/guess
421500272916602880000 281000181944401920000
   (2#.(({.guess) A. i.22) > xx) > 2#.(({.guess) A. i.22) < xx
1
…
   ]guess=. guess,~<.1r2+-:+/2{.guess
351250227430502400000 421500272916602880000 281000181944401920000 562000363888803840000
   (2#.(({.guess) A. i.22) > xx) > 2#.(({.guess) A. i.22) < xx
0
   guess=. guess,~<.1r2+-:+/2{.guess
   (2#.(({.guess) A. i.22) > xx) > 2#.(({.guess) A. i.22) < xx
1
   guess=. guess,~<.1r2+-:+/2{.guess
   (2#.(({.guess) A. i.22) > xx) > 2#.(({.guess) A. i.22) < xx
0
   guess=. guess,~<.1r2+-:+/2{.guess
   (2#.(({.guess) A. i.22) > xx) > 2#.(({.guess) A. i.22) < xx
1
   guess=. guess,~<.1r2+-:+/2{.guess
   (2#.(({.guess) A. i.22) > xx) > 2#.(({.guess) A. i.22) < xx
0
   guess=. guess,~<.1r2+-:+/2{.guess
   (2#.(({.guess) A. i.22) > xx) > 2#.(({.guess) A. i.22) < xx
0

Now that the simple alternation of “too high, too low” is broken, we have to think about it a little more.

   guess=. guess,~<.1r2+-:+/0 2{guess
   (2#.(({.guess) A. i.22) > xx) > 2#.(({.guess) A. i.22) < xx
1
   guess=. guess,~<.1r2+-:+/2{.guess
   (2#.(({.guess) A. i.22) > xx) > 2#.(({.guess) A. i.22) < xx
1
   guess=. guess,~<.1r2+-:+/0 2{guess

Continuing on, we develop a pattern: average “0 1{guess” if the last two guesses were in opposite directions, otherwise, average “(0,n){guess” where “n” increases as long as the direction stays the same:

   guess=. guess,~<.1r2+-:+/0 1{guess
   (2#.(({.guess) A. i.22) > xx) > 2#.(({.guess) A. i.22) < xx
0
   guess=. guess,~<.1r2+-:+/0 2{guess
   (2#.(({.guess) A. i.22) > xx) > 2#.(({.guess) A. i.22) < xx
0
   guess=. guess,~<.1r2+-:+/0 3{guess
   (2#.(({.guess) A. i.22) > xx) > 2#.(({.guess) A. i.22) < xx
0
   guess=. guess,~<.1r2+-:+/0 4{guess
   (2#.(({.guess) A. i.22) > xx) > 2#.(({.guess) A. i.22) < xx
0
   guess=. guess,~<.1r2+-:+/0 5{guess
   (2#.(({.guess) A. i.22) > xx) > 2#.(({.guess) A. i.22) < xx
1
   guess=. guess,~<.1r2+-:+/0 1{guess
   (2#.(({.guess) A. i.22) > xx) > 2#.(({.guess) A. i.22) < xx
1
   guess=. guess,~<.1r2+-:+/0 2{guess
   (2#.(({.guess) A. i.22) > xx) > 2#.(({.guess) A. i.22) < xx
1
   guess=. guess,~<.1r2+-:+/0 3{guess
   (2#.(({.guess) A. i.22) > xx) > 2#.(({.guess) A. i.22) < xx
1
   guess=. guess,~<.1r2+-:+/0 4{guess
   (2#.(({.guess) A. i.22) > xx) > 2#.(({.guess) A. i.22) < xx
0

Eventually, we have an answer:

   str0{~({.guess) A. i.22
citysojournersupwrykeg
   {.guess
375540904969390575462
   str0
newyorkcityjusersgroup
   375540904969390575462x A. 'newyorkcityjusersgroup'
citysojournersupwrykeg

Learning and Teaching J

We look at an essay by Dijkstra on teaching computer science; an abbreviated version follows and the entire essay may be found here.

On the Cruelty of Really Teaching Computer Science

The second part of this talk pursues some of the scientific and educational consequences of the assumption that computers represent a radical novelty. In order to give this assumption clear contents, we have to be much more precise as to what we mean in this context by the adjective "radical"….

The usual way in which we plan today for tomorrow is in yesterday's vocabulary. We do so, because we try to get away with the concepts we are familiar with and that have acquired their meanings in our past experience. Of course, the words and the concepts don't quite fit because our future differs from our past, but then we stretch them a little bit. Linguists are quite familiar with the phenomenon that the meanings of words evolve over time, but also know that this is a slow and gradual process.

It is the most common way of trying to cope with novelty: by means of metaphors and analogies we try to link the new to the old, the novel to the familiar. Under sufficiently slow and gradual change, it works reasonably well; in the case of a sharp discontinuity, however, the method breaks down: though we may glorify it with the name "common sense", our past experience is no longer relevant, the analogies become too shallow, and the metaphors become more misleading than illuminating. This is the situation that is characteristic for the "radical" novelty.

…Coming to grips with a radical novelty amounts to creating and learning a new foreign language that can not be translated into one's mother tongue. (Any one who has learned quantum mechanics knows what I am talking about.) Needless to say, adjusting to radical novelties is not a very popular activity, for it requires hard work. For the same reason, the radical novelties themselves are unwelcome. …

Radical Novelty

The other thing I cannot stress enough is that the fraction of the population for which gradual change seems to be all but the only paradigm of history is very large, probably much larger than you would expect. Certainly when I started to observe it, their number turned out to be much larger than I had expected.

For instance, the vast majority of the mathematical community has never challenged its tacit assumption that doing mathematics will remain very much the same type of mental activity it has always been: new topics will come, flourish, and go as they have done in the past, but, the human brain being what it is, our ways of teaching, learning, and understanding mathematics, of problem solving, and of mathematical discovery will remain pretty much the same. Herbert Robbins clearly states why he rules out a quantum leap in mathematical ability:

Nobody is going to run 100 meters in five seconds, no matter how much is invested in training and machines. The same can be said about using the brain. The human mind is no different now from what it was five thousand years ago. And when it comes to mathematics, you must realize that this is the human mind at an extreme limit of its capacity.

My comment in the margin was "so reduce the use of the brain and calculate!"…. Robbins flatly refuses to honour any alternative to time-honoured brain usage with the name of "doing mathematics", thus exorcizing the danger of radical novelty by the simple device of adjusting his definitions to his needs: simply by definition, mathematics will continue to be what it used to be. So much for the mathematicians.

Let me give you just one more example of the widespread disbelief in the existence of radical novelties and, hence, in the need of learning how to cope with them. It is the prevailing educational practice, for which gradual, almost imperceptible, change seems to be the exclusive paradigm.…The same silly tradition is reflected at university level in different introductory calculus courses for the future physicist, architect, or business major, each adorned with examples from the respective fields. The educational dogma seems to be that everything is fine as long as the student does not notice that he is learning something really new; more often than not, the student's impression is indeed correct.

…I raised all this because of my contention that automatic computers represent a radical novelty and that only by identifying them as such can we identify all the nonsense, the misconceptions and the mythology that surround them. Closer inspection will reveal that it is even worse, viz. that automatic computers embody not only one radical novelty but two of them.

First Radical Novelty: Increase in Computing Power

The first radical novelty is a direct consequence of the raw power of today's computing equipment. We all know how we cope with something big and complex; divide and rule, i.e. we view the whole as a compositum of parts and deal with the parts separately. And if a part is too big, we repeat the procedure….From a bit to a few hundred megabytes, from a microsecond to a half an hour of computing confronts us with completely baffling ratio of 109! The programmer is in the unique position that his is the only discipline and profession in which such a gigantic ratio, which totally baffles our imagination, has to be bridged by a single technology. He has to be able to think in terms of conceptual hierarchies that are much deeper than a single mind ever needed to face before. …

Second Radical Novelty: Computer is First Digital Device

Again, I have to stress this radical novelty because the true believer in gradual change and incremental improvements is unable to see it. For him, an automatic computer is something like the familiar cash register, only somewhat bigger, faster, and more flexible. But the analogy is ridiculously shallow: it is orders of magnitude worse than comparing, as a means of transportation, the supersonic jet plane with a crawling baby, for that speed ratio is only a thousand.

The second radical novelty is that the automatic computer is our first large-scale digital device. We had a few with a noticeable discrete component: I just mentioned the cash register and can add the typewriter with its individual keys: with a single stroke you can type either a Q or a W but, though their keys are next to each other, not a mixture of those two letters. But such mechanisms are the exception, and the vast majority of our mechanisms are viewed as analogue devices whose behaviour is over a large range a continuous function of all parameters involved: if we press the point of the pencil a little bit harder, we get a slightly thicker line, if the violinist slightly misplaces his finger, he plays slightly out of tune….

It is possible, and even tempting, to view a program as an abstract mechanism, as a device of some sort. To do so, however, is highly dangerous: the analogy is too shallow because a program is, as a mechanism, totally different from all the familiar analogue devices we grew up with. Like all digitally encoded information, it has unavoidably the uncomfortable property that the smallest possible perturbations —i.e. changes of a single bit— can have the most drastic consequences.

Having described —admittedly in the broadest possible terms— the nature of computing's novelties, I shall now provide the evidence that these novelties are, indeed, radical. I shall do so by explaining a number of otherwise strange phenomena as frantic —but, as we now know, doomed— efforts at hiding or denying the frighteningly unfamiliar.

Software Engineering: A Doomed Discipline

A number of these phenomena have been bundled under the name "Software Engineering". As economics is known as "The Miserable Science", software engineering should be known as "The Doomed Discipline", doomed because it cannot even approach its goal since its goal is self-contradictory. Software engineering, of course, presents itself as another worthy cause, but that is eyewash: if you carefully read its literature and analyse what its devotees actually do, you will discover that software engineering has accepted as its charter "How to program if you cannot.".

…Nor are we above the equally primitive superstition that we can gain some control over some unknown, malicious demon by calling it by a safe, familiar, and innocent name, such as "engineering"…. The practice is pervaded by the reassuring illusion that programs are just devices like any others, the only difference admitted being that their manufacture might require a new type of craftsmen, viz. programmers. From there it is only a small step to measuring "programmer productivity" in terms of "number of lines of code produced per month". This is a very costly measuring unit because it encourages the writing of insipid code, but today I am less interested in how foolish a unit it is from even a pure business point of view. My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger.

Besides the notion of productivity, also that of quality control continues to be distorted by the reassuring illusion that what works with other devices works with programs as well. It is now two decades since it was pointed out that program testing may convincingly demonstrate the presence of bugs, but can never demonstrate their absence. After quoting this well-publicized remark devoutly, the software engineer returns to the order of the day and continues to refine his testing strategies, just like the alchemist of yore, who continued to refine his chrysocosmic purifications.

Unfathomed misunderstanding is further revealed by the term "software maintenance", as a result of which many people continue to believe that programs —and even programming languages themselves— are subject to wear and tear…. In the same vein I must draw attention to the astonishing readiness with which the suggestion has been accepted that the pains of software production are largely due to a lack of appropriate "programming tools". (The telling "programmer's workbench" was soon to follow.) Again, the shallowness of the underlying analogy is worthy of the Middle Ages. Confrontations with insipid "tools" of the "algorithm-animation" variety has not mellowed my judgement; on the contrary, it has confirmed my initial suspicion that we are primarily dealing with yet another dimension of the snake oil business….

So much for the evidence that the computer's novelties are, indeed, radical.

And now comes the second —and hardest— part of my talk: the scientific and educational consequences of the above. The educational consequences are, of course, the hairier ones, so let's postpone their discussion and stay for a while with computing science itself. What is computing? And what is a science of computing about?

Well, when all is said and done, the only thing computers can do for us is to manipulate symbols and produce results of such manipulations….

What is Computing?

But before a computer is ready to perform a class of meaningful manipulations —or calculations, if you prefer— we must write a program. What is a program? … We can view the program as what turns the general-purpose computer into a special-purpose symbol manipulator, and does so without the need to change a single wire…. I prefer to describe it the other way round: the program is an abstract symbol manipulator, which can be turned into a concrete one by supplying a computer to it. After all, it is no longer the purpose of programs to instruct our machines; these days, it is the purpose of machines to execute our programs.

So, we have to design abstract symbol manipulators. We all know what they look like: they look like programs or —to use somewhat more general terminology— usually rather elaborate formulae from some formal system. It really helps to view a program as a formula. Firstly, it puts the programmer's task in the proper perspective: he has to derive that formula. Secondly, it explains why the world of mathematics all but ignored the programming challenge: programs were so much longer formulae than it was used to that it did not even recognize them as such….

Hence, computing science is —and will always be— concerned with the interplay between mechanized and human symbol manipulation, usually referred to as "computing" and "programming" respectively. An immediate benefit of this insight is that it reveals "automatic programming" as a contradiction in terms. A further benefit is that it gives us a clear indication where to locate computing science on the world map of intellectual disciplines: in the direction of formal mathematics and applied logic, but ultimately far beyond where those are now….

In the long run I expect computing science to transcend its parent disciplines, mathematics and logic, by effectively realizing a significant part of Leibniz's Dream of providing symbolic calculation as an alternative to human reasoning. (Please note the difference between "mimicking" and "providing an alternative to": alternatives are allowed to be better.)

Needless to say, this vision of what computing science is about is not universally applauded. On the contrary, it has met widespread —and sometimes even violent— opposition from all sorts of directions. I mention as examples

• (0) the mathematical guild, which would rather continue to believe that the Dream of Leibniz is an unrealistic illusion
• (1) the business community, which, having been sold to the idea that computers would make life easier, is mentally unprepared to accept that they only solve the easier problems at the price of creating much harder ones
• (2) the subculture of the compulsive programmer, whose ethics prescribe that one silly idea and a month of frantic coding should suffice to make him a life-long millionaire
• (3) computer engineering, which would rather continue to act as if it is all only a matter of higher bit rates and more flops per second
• (4) the military, who are now totally absorbed in the business of using computers to mutate billion-dollar budgets into the illusion of automatic safety
• (5) all soft sciences for which computing now acts as some sort of interdisciplinary haven
• (6) the educational business that feels that, if it has to teach formal mathematics to CS students, it may as well close its schools.

  Educational Consequences

  The problem with educational policy is that it is hardly influenced by scientific considerations derived from the topics taught, and almost entirely determined by extra-scientific circumstances such as the combined expectations of the students, their parents and their future employers, and the prevailing view of the role of the university: is the stress on training its graduates for today's entry-level jobs or to providing its alumni with the intellectual baggage and attitudes that will last them another 50 years? …

  Traditional academic rhetoric is perfectly willing to give to these questions the reassuring answers, but I don't believe them. By way of illustration of my doubts, in a recent article on "Who Rules Canada?", David H. Flaherty bluntly states "Moreover, the business elite dismisses traditional academics and intellectuals as largely irrelevant and powerless.".

  So, if I look into my foggy crystal ball at the future of computing science education, I overwhelmingly see the depressing picture of "Business as usual". The universities will continue to lack the courage to teach hard science, they will continue to misguide the students, and each next stage of infantilization of the curriculum will be hailed as educational progress. …

  We could, for instance, begin with cleaning up our language by no longer calling a bug a bug but by calling it an error. It is much more honest because it squarely puts the blame where it belongs, viz. with the programmer who made the error. The animistic metaphor of the bug that maliciously sneaked in while the programmer was not looking is intellectually dishonest as it disguises that the error is the programmer's own creation. …My next linguistical suggestion is more rigorous. It is to fight the "if-this-guy-wants-to-talk-to-that-guy" syndrome: never refer to parts of programs or pieces of equipment in an anthropomorphic terminology, nor allow your students to do so. This linguistical improvement is much harder to implement than you might think….

  … The analogy that underlies this personification is so shallow that it is not only misleading but also paralyzing. … It is misleading in the sense that it suggests that we can adequately cope with the unfamiliar discrete in terms of the familiar continuous … It is paralyzing in the sense that, because persons exist and act in time, its adoption effectively prevents a departure from operational semantics and thus forces people to think about programs in terms of computational behaviours, based on an underlying computational model. This is bad, because operational reasoning is a tremendous waste of mental effort.

  Let me explain to you the nature of that tremendous waste, and allow me to try to convince you that the term "tremendous waste of mental effort" is not an exaggeration….

  The point to get across is that if we have to demonstrate something about all the elements of a large set, it is hopelessly inefficient to deal with all the elements of the set individually: the efficient argument does not refer to individual elements at all and is carried out in terms of the set's definition.

  Consider the plane figure Q, defined as the 8 by 8 square from which, at two opposite corners, two 1 by 1 squares have been removed. The area of Q is 62, which equals the combined area of 31 dominos of 1 by 2. The theorem is that the figure Q cannot be covered by 31 of such dominos.

  Another way of stating the theorem is that if you start with squared paper and begin covering this by placing each next domino on two new adjacent squares, no placement of 31 dominos will yield the figure Q.

  So, a possible way of proving the theorem is by generating all possible placements of dominos and verifying for each placement that it does not yield the figure Q: a tremendously laborious job.

  The simple argument, however is as follows. Colour the squares of the squared paper as on a chess board. Each domino, covering two adjacent squares, covers 1 white and 1 black square, and, hence, each placement covers as many white squares as it covers black squares. In the figureQ, however, the number of white squares and the number of black squares differ by 2 —opposite corners lying on the same diagonal— and hence no placement of dominos yields figure Q.

  Not only is the above simple argument many orders of magnitude shorter than the exhaustive investigation of the possible placements of 31 dominos, it is also essentially more powerful, for it covers the generalization of Q by replacing the original 8 by 8 square by any rectangle with sides of even length. The number of such rectangles being infinite, the former method of exhaustive exploration is essentially inadequate for proving our generalized theorem.