Informatisk julekalender: Luke 3

fredag 3. desember 2010 Julekalender

lovelace

I går fikk du høre om verdens første, programmerbare datamaskin – den analytiske maskinen. Babbage fikk aldri fullført maskinen, men det hindret ikke Ada Lovelace i å lage verdens første program ment for å kjøres på den. Ada kalles derfor den første programmereren!

Programmet Ada designet for Babbages analytiske maskin var en algoritme for å kalkulere noe som heter Bernoulli-tall. Adas tekst om den analytiske maskinen finner du her (om du er veldig interessert og har god tid) – et diagram som viser selve algoritmen ser du her. Nedefor har jeg implementert min versjon av programmet i Ruby:

1 def bernoulli n
2 a=[]; a[0]=[]
3
4 (0..n).each { |j| a[0][j] = 1.0 / (j+1) }
5 (1..n).each do |i|
6     a[i] = []
7     (0..(n - i)).each do |j|
8       a[i][j] = (j+1) * (a[i-1][j] - a[i-1][j+1])
9     end
10 end
11 a[n][0]
12 end
13
14 puts bernoulli(0)   #=> 1
15 puts bernoulli(1)   #=> 0.5
16 puts bernoulli(2)   #=> 0.166666666666667
17 puts bernoulli(4)   #=> -0.033333333333334
18 puts bernoulli(6)   #=> 0.0238095238095676
19 puts bernoulli(16) #=> -7.0685020745223
20 puts bernoulli(18) #=> 69.99698015617

Dette er forresten en ypperlig anledning til å demonstrere hvor mye mer elegant en rekursiv implementasjon i Clojure er enn den typiske imperative løsningen. Ruby-koden ser ut som et øst-europeisk kullkrafverk, mens Clojure-algoritmen fremstår som selveste Taj Mahal. Estetikk har alltid hatt en viktig rolle i design av algoritmer. Så kanskje det ikke er så tilfeldig at den første programmereren var en kvinne? :)

1 (defn bernoulli
2       ([ n ] (bernoulli n 0))
3       ([i j] (if (zero? i)
4                (/ 1 (inc j))
5                (* (inc j)
6                   (- (bernoulli (dec i) j)
7                      (bernoulli (dec i) (inc j)))))))
8
9 (println (bernoulli 0))   ;=>      1
10 (println (bernoulli 1))   ;=>     1/2
11 (println (bernoulli 2))   ;=>     1/6
12 (println (bernoulli 4))   ;=>    -1/30
13 (println (bernoulli 6))   ;=>     1/42
14 (println (bernoulli 16)) ;=> -3617/510
15 (println (bernoulli 18)) ;=> 43867/798

Clojure-implementasjonen er omtrent bare definisjonen av hva et Bernoulli-nummer er for noe, mens en imperativ løsning er full av array-manipuleringer og andre implementasjonsdetaljer. Dessuten bestemmer Clojure helt av seg selv at det her er lurt å returnere svarene som brøk.

I likhet med Pascal (luke 1) har forresten også grevinnen av Lovelace fått oppkalt et programmeringsspråk etter seg. Ada er et objektorientert, statisk typet språk utviklet for det amerikanske forsvarsdepartementet. Utenfor forsvaret har språket også blitt brukt til å implementere systemer innenfor luftfart.

La meg så avslutte "dagens tekst" med et par Ada Lovelace-sitater. Først et som viser at hun tenkte som en god programmerer, og var opptatt av ting som vi også er i dag:

"In almost every computation a great variety of arrangements for the succession of the processes is possible, and various considerations must influence the selections amongst them for the purposes of a calculating engine. One essential object is to choose that arrangement which shall tend to reduce to a minimum the time necessary for completing the calculation."

Og her er et vakkert sitat som sammenligner den første datamaskinen med veven Babbage hentet ideen om programmering via hullkort fra:

"The Analytical Engine weaves algebraic patterns, just as the Jacquard loom weaves flowers and leaves."