Think first, code later
Leggo ora una nota di Dijkstra segnalata da un post di Carlo Pescio: My recollections of operating systems design. Ci sono un paio di cose che mi sembrano molto interessanti.
Parlando del famoso algoritmo di Dekker, la prima soluzione corretta al problema della mutua esclusione, Dijkstra dice che da parecchio tempo stava sfidando i suoi colleghi perché producessero una soluzione. Quando la difficoltà di trovare gli errori nelle soluzioni proposte divenne eccessiva, D. cambiò le regole del gioco, richiedendo che insieme all’algoritmo venisse proposta anche una prova di correttezza.
And then something profound and lovely happened. By analyzing by what structure of argument the proof obligations could be met, the numerical mathematician Th.J. Dekker designed within a few hours the above solution together with its correctness argument, and this settled the contest.
L’idea della derivazione di programmi è di fare guidare la soluzione dalla dimostrazione di correttezza. E’ una cosa analoga (non equivalente! ma certamente analoga) a quello che si fa in TDD, dove si fa guidare la soluzione dai test che dimostrano empiricamente che la soluzione funziona.
Ci sono profonde differenze, è ovvio, fra “program derivation” e “TDD”. Ma ci sono anche ovvie analogie: entrambe le tecniche producono programmi molto concisi e corretti. Ed entrambe le tecniche sono molto più efficaci del code & fix, che è la maniera più comune di sviluppare.
A questo proposito D. cita un’episodio divertente:
When the design of the THE Multiprogramming System neared its completion, the University’s EL X8 was getting installed, but it had not been paid yet, and we hardly had access to it because the manufacturer had to put it to the disposal of an American software house that was supposed to write a COBOL implementation for the EL X8. They were program testing all the time, and we let it be known that if occasionally we could have the virgin machine for a few minutes, we would appreciate it. They were nice guys, and a few times per week we would get an opportunity for our next test run. We would enter the machine room with a small roll of punched paper tape, and a few minutes later we would leave the machine room with the output we wanted. I remember it vividly because when they realized what we were achieving, our minimal usage of the machine became more and more frustrating for them. I don’t think their COBOL implementation was ever completed.
Come riesco a immaginarmeli questi sfortunati programmatori… Accanirsi nel code & fix non serve se non si ha un’idea chiara di quello che si sta facendo. Va detto che nei primi anni ’60 scrivere un compilatore era un’impresa un bel po’ più difficile di oggi. Non potevano andarsi a comprare il Dragon Book, perché non era ancora stato scritto!
May 4th, 2007 at 20:59
Grazie del riferimento Matteo, mi piacciono tantissimo queste storie di archeoinformatica :-)
P.S. due curiosità sul “Libro del Drago”
– Da poco è uscita la tanto attesa seconda edizione http://www.amazon.com/o/ASIN/0321486811
– E’ stato citato nel film “Hackers”: veniva presentato ad un tizio che doveva riconoscerlo (come libro del drago) come prova di iniziazione per entrare in una banda di hacker appunto. Tra l’altro è stato uno dei primi film interpretati da Angelina Jolie http://imdb.com/title/tt0113243/
May 6th, 2007 at 15:58
Un’altro libro mitico è “Unix Network Programming”, dello scomparso Rich Stevens; questo libro appare in “Wayne’s World II”:
[Steven’s] books are so good that they have come to symbolize intelligence. In “Wayne’s World II,” Garth’s girlfriend carries a copy of “Unix Network Programming.” Stevens discovered this when he took his 13-year-old son to see the film. His son grabbed his arm and said, “Dad, that’s your book!” (http://archive.salon.com/tech/feature/2000/09/01/rich_stevens/index1.html)
May 20th, 2007 at 11:37
Matteo,
Dijkstra era estremamente cauto (se non scettico) rispetto al testing, da cui la sua famosa frase “Program testing can be used to show the presence of bugs, but never to show their absence”.
Nel caso particolare dell’algoritmo di Dekker, la storia e’ proprio di qualcosa che non si riusciva facilmente a testare, ma doveva essere modellata con un formalismo matematico, pensata a fondo ed infine realizzata in modo intrinsecamente corretto. Nel piccolo, mi pare piu’ vicino ad un “big” upfront design che ad un approccio alla XP.
Mi fai vedere come si deriva l’algoritmo usando il TDD? Ancora meglio, nelle condizioni dell’epoca, dove la concorrenza era principalmente dovuta agli interrupt e le macchine erano “chiuse”, ma sarei gia’ contento di vederlo con una concorrenza alla java (senza usare, ovviamente la sincronizzazione di java).
Con questo non dico che il TDD non sia utile, solo che non dobbiamo pensare che sia un approccio universale alla risoluzione dei problemi.
Vic.
May 21st, 2007 at 11:59
Ciao Vittorio,
è un discorso ampio e interessante. Non sono capace di derivare l’algoritmo di Dekker con TDD, e non credo che in generale con TDD si riescano a derivare algoritmi non banali. Non è lì il punto del TDD; il punto è che nella pratica, colui che fa il lavoro del programmatore, non ha mai o quasi mai il problema di derivare un algoritmo “difficile”.
In pratica, salvo rari casi, tutti gli algoritmi difficili che servono sono incapsulati in librerie. La cosa sorprendente è che nonostante questo, il lavoro del programmatore non si è ancora trasformato in un banale compito di compilazione, che possa essere fatto in maniera semiautomatica. Anzi, il compito di fornire al cliente software che funziona e risolve i suoi problemi è sempre difficile.
Come mai? Qual’è la tua risposta?
Secondo me, è perché il programmatore deve comunque scrivere un grandissimo numero di algoritmi banali, organizzarli in un tutto coerente, tenere conto di centinaia di requisiti che male si adattano a un analisi matematica, e fare tutto ciò in una maniera che permetta di modificare il risultato per tenere conto di nuovi requisiti.
E’ un problema molto diverso questo da quello che Dekker ha risolto; e sono convinto che Dekker stesso avrebbe fatto fatica.
Per me il TDD è una maniera di affrontare senza paura problemi di questo tipo, e di riuscire a vincerli anche se il mio potere cerebrale è minuscolo in confronto a quello di un Dijkstra o un Dekker.