A Portrait of a Genius
Krzysztof R. Apt ha scritto un bel necrologio per Edsger W. Dijkstra. E’ molto completo nella descrizione sia degli enormi contributi scientifici
In a one-page paper from 1965 he introduced the ‘mutual exclusion problem’ for n processes and discussed a solution to it. It was probably the first published concurrent algorithm.
che della sua personalitÃ
In writing his elegance was unmatched. He could write about formal issues in the form of an essay, with hardly any formulas. His paper Cooperating sequential processes is perhaps the best example. Similarly, he was able to discuss (one shold rather say, derive) intricate algorithms in distributed computing in a seemingly informal way, in plain prose, with just a few simple formulas. He wrote his articles in a unique style characterised by conciseness, economy of argument and clarity of exposition. Each sentence was carefully chiselled. Each paragraph was striking.
Come risuona questa eco nel ricordo delle poche occasioni in cui l’ho visto. Come apprezzo e ammiro questa concisione e precisione, per usare le parole di Roland Backhouse.
La concisione è potere, dice Richard Gabriel riferendosi alla programmazione. Non posso che essere d’accordo. Il momento più bello è quando l’astrazione giusta fa “click” nella tua mente, e puoi cancellare pagine e pagine di codice: David Heinemeier Hansson. Due citazioni di due hacker. Dijkstra disprezzava sommamente gli hacker. Eppure alla fine l’estetica spartana e cristallina di Ruby on Rails ha qualcosa degli articoli brevi ed icastici di Dijkstra.
Fra le molte citazioni gettonate di Dijkstra c’è Program testing can be used to show the presence of bugs, but never to show their absence! Dijkstra non usava mai i computer. Disprezzava l’idea di “testare” i programmi. Eppure … sono convinto che la disciplina del Test-driven development ha qualche cosa della discipline of programming di Dijkstra. I programmi che si ottengono hanno la stessa qualità di essere super-concisi ed essenziali. Quella stessa qualità che ammiravo nei programmi ottenuti per derivazione dalle specifiche.
Aneddoto: in un qualche momento degli anni novanta c’era un lungo dibattito su comp.lang.c.moderated su come risolvere il seguente problema: dato un array di interi, trovare la sottosequenza la cui somma è massima. La soluzione “forza bruta” è ovvia e richiede tempo quadratico; si voleva una soluzione più efficiente. Pagine e pagine di codice e ragionamenti confusi volavano nel newsgroup, fino a quando non intervenni io. Il problema in questione è uno degli esercizi standard che si usano nella program derivation. La soluzione lineare si calcola facilmente, e consiste in tre righe di codice. Il mio post è stato l’ultimo del thread :)
]]>
March 13th, 2007 at 00:19
[…] Ora, ad una prima occhiata questo problema si risolve con un algoritmo che ha complessità O(n2), ma io ricordavo da discussioni precedenti (sul blog di matteo vaccari e su #verbamanent, era stato usato durante un colloquio di lavoro) che esiste un algoritmo con complessità lineare. […]