Du var kanskje ikke klar over det, men Common Lisp er et objektorientert språk. Det påstås faktisk at det har det kraftigste og mest fleksible objekt-systemet av alle språkene vi har, og gjennom å implementere Template Method pattern i Common Lisp håper jeg å gi deg en grei introduksjon til noen av språkets muligheter. Du vil også få se at multippel arv løser utfordringen jeg hadde med den klassiske implementasjonen i del 1.

Pass på at du har designet fra del 1 klart for deg når du ser på denne løsningen.. Og husk at parantesene ikke er farlige :D

(PS: Jeg ser bort fra diskusjonen om det faktisk er gyldig å kalle det jeg presenterer i denne serien for Template Method pattern – delta i debatten her.)

Først trenger jeg å lage selve templaten – noe som definerer skjelettet til algoritmen, men overlater detaljene til en konkret rapport-implementasjon. Templaten opprettes ikke i en klasse som i del 1 og del 2, men heller ikke som en høyereordens funksjon som jeg brukte i del 3. logReport er en prosedyre som tar et rapport-objekt som parameter, og typen av dette rapport-objektet vil avgjøre detaljene i loggfil-prosesseringen.

 2 (defun log-report (report)
 3   "A template for reporting from log files"
 4   (log-report-init report)
 5   (loop for line in (log-report-read report)
 6         do (log-report-process-line report line))
 7   (log-report-cleanup report))

Når jeg i den tredje linjen sier (log-report-init report) så er det det samme som å kalle metoden log-report-init på objektet report. Det neste jeg skal gjøre er å opprette disse metodene. Jeg bruker en makro som heter DEFGENERIC – du kan gjerne se på det som om jeg bruker dem til å opprette abstrakte metoder, slik jeg gjorde i LogProcessor i del 1. Metodene henger derimot ikke direkte på en klasse – klasser i Common Lisp har bare properties, mens metodene defineres for seg:

10 (defgeneric log-report-init (report))
11 (defgeneric log-report-read (report))
12 (defgeneric log-report-process-line (report line))
13 (defgeneric log-report-cleanup (report))

Så bruker jeg DEFMETHOD til å lage noen fornuftige default-implementasjoner av de abstrakte metodene. For initialisering og cleanup lager jeg bare noen tomme metoder, mens metoden som prosesserer en linje bare skriver den ut.

17 (defmethod log-report-init (report))
18 (defmethod log-report-process-line (report line)
19   (format t "~a~%" line))
20 (defmethod log-report-cleanup (report))

Jeg kan også lage en konkret variante av metoden som leser en fil, og jeg mocker fillesingen slik jeg har gjort i de andre delene i denne bloggserien:

28 ; Faking reading the file as usual..
29 (defmethod log-report-read (report)
30   (list "20120125180000000 DEBUG Tick!"
31   "20120125180100000 DEBUG Tick!"
32   "20120125180132112 ERROR Some error occurred"
33   "20120125180133056 ERROR Some other error..."
34   "20120125180200000 DEBUG Tick!"))

Nå kunne jeg ha kjørt koden ved å skrive for eksempel (log-report nil). Nil er nemlig også et objekt i Common Lisp – alt er objekter – og jeg har laget default implementasjoner av metodene som vil fungere for alle typer objekter! Alle linjene fra filen vil bli skrevet ut.

Opprette en klasse

Det er på tide å se hvordan man definerer en ny klasse. Jeg vil nå opprette en klasse for å rapportere errors fra loggfiler, sånn som jeg gjorde i del 1. Til det bruker jeg DEFCLASS:

36 (defclass error-report () ())

Klassen arver ikke fra noe spesielt, og den har ingen properties, så den ble ganske minimal. Men som du vil se er den viktig likevel.

Jeg kan nå opprette nye metoder for de stegene i algoritmen/templaten som er interessante for error-rapporten. Disse metodene vil bli brukt i tilfeller hvor report-objektet er en instans av error-report.

42 (defmethod log-report-init :before ((report error-report))
43   (format t "Errors:~%")) ; Printing a header..
44 
45 (defmethod log-report-process-line ((report error-report) line)
46   (let ((log-type (subseq line 18 23)))
47     (if (equal log-type "ERROR")
48       (format t "~a: ~a~%"
49         (subseq line 0 17)
50         (subseq line 24)))))

Metoden som prosesserer linjene vil erstatte default-implementasjonen, siden den ikke “kaller base/super” (i Common Lisp ville jeg gjort det ved å kalle en funksjon som heter CALL-NEXT-METHOD). Initialisering-metoden vil derimot bli lagt til i tillegg til eventuelt andre initialiseringsmetoder. I dette tilfellet skjer det fordi jeg har brukt :before-nøkkelordet. Before-metoder kaller i forkant av de virkelige metodene, og er bare en av mange måter man kan opprette metoder på.

Hvis jeg nå kjører koden (LOG-REPORT (MAKE-INSTANCE ‘ERROR-REPORT)) så vil den skrive ut headeren og error-linjene fra filen jeg har mocket.

En klasse for FTP-stegene

Nå oppretter jeg en ny klasse for FTP-stegene jeg trenger. Denne klassen arver heller ikke fra noen spesiell klasse, men inneholder én slot (property) for å holde på URLen til loggfilen.

58 (defclass ftp-report ()
59   ((url :initarg :url)))
60 
61 (defmethod log-report-init :before ((report ftp-report))
62   (format t "Fetching ~a~%" (slot-value report 'url)))
63 
64 (defmethod log-report-cleanup :after ((report ftp-report))
65   (format t "Deleting ~a~%" (slot-value report 'url))
66   (format t "Archiving local copy"))

Om jeg nå hadde evaluert (LOG-REPORT (MAKE-INSTANCE ‘FTP-REPORT :URL “some url..”)) ville metodene for å hente og slette FTP-loggen bli brukt, og default metoder for lesing og prosessering hadde også blitt brukt, slik at hele innholdet av filen hadde blitt vist. Men det er ikke det jeg er ute etter…

Multippel arv

Jeg skal nemlig nå lage en ny klasse som arver fra både error-report og ftp-report:

68 (defclass ftp-error-report (ftp-report error-report) ())

Når jeg oppretter en instans av denne klassen, og så kjører log-report, vil metodene for klassene som arves bli kombinert:

71 (log-report (make-instance 'ftp-error-report
72          :url "ftp://foobar.com/logs/my.log"))

Dette gir altså følgende output:

Fetching ftp://foobar.com/logs/my.log
Errors:
20120125180132112: Some error occurred
20120125180133056: Some other error...
Deleting ftp://foobar.com/logs/my.log
Deleting local copy as well

Et UML-diagram over denne modellen, om den hadde vært gjort i et mere klassisk OO-språk, ville sett ut som dette:

Konklusjon

Jeg har altså brukt multippel arv til å gjøre Template Method mindre rigid enn løsningen jeg kom opp med i C# i del 1; nå kan jeg kombinere de ulike klassene på ulike måter i stedet for å ha en fastlåst arverekkefølge. Dette gjør denne løsningen mer utvidbar.

Jeg har ikke jobbet mye med objektorientering i Common Lisp, men synes systemet med de generiske funksjonene som ikke er knyttet direkte til klassene er ganske elegant. Det er kanskje ikke lett å se hvor fleksibelt dette er uten å forsøke litt selv, spesielt ikke om man er vandt til typisk klasse-basert objektoerientering fra språk som C#, Java eller C++, men det finnes nok av folk som skryter hemningsløst av Common Lisp’s objektsystem. Dette er noe jeg må eksperimentere mer med.

Ønsker du en innføring i Common Lisp + objekter kan du ta en titt på Practical Common Lisp (online bok), kapittel 16 og 17.

I løpet av denne serien har du sett at et objektoerientert designpattern kan ha svært ulike implementasjoner. Et designpattern er ikke noe man kan pugge, og bare bruke igjen og igjen på samme måte. Man må tilpasse det omstendighetene, og hele tiden være klar over hvilke begrensninger det har. Jeg håper koden min har gitt deg noen ideer, og at du vil eksperimentere videre med hvordan du løser lignende problemer.

Her kommer nok en Lisp-er-bedre-enn-andre-språk-blogpost!

Jeg har nylig mottatt noen nye bøker fra Amazon, deriblant Let Over Lambda (subtitle: 50 years of Lisp). Dette skal være en av de mest hardcore programmeringsbøkene som finnes. Det føles som om jeg har oppdaget dødehavsrullene, som om jeg har funnet en glemt skatt med potensialet til å totalt forandre mitt syn på verden. Jeg er klar for å ta steget opp til et helt nytt nivå.

Let Over Lambda er en bok om å kode og utnytte makroer i Lisp – fortrinnsvis Common Lisp. Med makroer lager man programmer som lager programmer. Det finnes flere språk som støtter metaprogrammering, men Common Lisp er det ypperste.

La meg sitere et av de første avsnittene i boken:

“Macros are the single greatest advantage that Lisp has as a programming language and the single greatest advantage of any programming language. With them you can do things that you simply cannot do in other languages. Because macros can be used to transform lisp into other programming languages and back, programmers who gain experience with them discover that all other languages are just skins on top of lisp. This is the big deal. Lisp is special because programming with it is actually programming at a higher level. Where most languages invent and enforce syntactic and semantic rules, lisp is general and malleable. With lisp, you make the rules.“

Boken er en stor egotripp – bare de aller beste utviklerne leser Let Over Lambda sies det. De smarteste utviklerne ender alltid opp med Lisp. Lisp er ikke skrevet for å gjøre programmering enkelt, men for å gi deg som utvikler all makt og alle muligheter.

Om fremtiden ligger i makroer – som Let Over Lambda hevder – eller ikke, så er jeg uansett klar for å utvide mine egne ferdigheter og potensielle produktivitet, og gleder meg til å lære å lage optimale abstraksjoner.

Som jeg har sagt mange ganger før, Lisp (det vil si Common Lisp, Scheme, Clojure og alle andre varianter) er et fantastisk språk. Alan Key sa at det var det beste programmeringsspråket som noen sinne var konstruert. Så hvorfor er det så få som bruker det? Hvorfor er det ikke like populært som C++, PHP, Java og C#.

Det enkle svaret er at det er et vanskelig språk. Men hvis det er riktig, hva er det da som gjør det så vanskelig?

Det jeg skal se litt på i denne artikkelen er en utfordring knyttet til det faktum at Lisp er et svært fleksibelt språk. Denne fleksibiliteten gjør at man kan løse problemer på veldig mange forskjellige måter.

4Clojure.com er en webside som tilbyr en rekke små programmeringsoppgaver som man må løse for å få noen enhetstester til å bli grønne. Jeg har løst over 80 av oppgavene, og lært mye Clojure på den måten. Når du har løst en oppgave kan du også se hvordan andre har gjort det samme. For å illustrere poenget mitt om Lisp’s fleksibilitetsproblem vil jeg nå vise noen utvalgte løsninger på tre av oppgavene. Oppgavene er nokså tilfeldig valgt.

Om du merker at du får vondt i hodet av Clojure kan du hoppe ned til konklusjonen :)

Eksempel 1: Er verdien for en nøkkel nil?

Jeg begynner med en veldig enkel oppgave. Her skulle vi lage en funksjon som tar imot en nøkkel og en hash-map (dictionary om du vil), og returnere true hvis og bare hvis map’en inneholder nøkkelen med en tilordnet verdi som er nil. Du finner oppgaven på 4Clojure her.

Brukeren beickhoff laget en rett frem løsning som er enkel å forstå:

 4 (fn [key map]
 5   (and (contains? map key)
 6        (nil? (get map key))))

Min egen løsning er bare en minifisering av beickhoff’s løsning – den er litt vanskeligere å lese, fordi den ikke gir navn til variablene, men ellers er det akkurat det samme.

10 #(and (contains? %2 %)
11        (nil? (%2 %)))

Brukeren indy har også tenkt på samme måte, men har tydeligvis ikke kjent til funksjonene contains? og nil?:

21 (fn [k h]
22   (and (if (some #{k} (keys h)) true false)
23        (= (k h) nil)))

Condotti viser derimot bedre kunnskap om Clojure, og har implementert en kort og elegant løsning:

16 #(nil? (%2 % 0))

Brukeren immo har egentlig gjort det samme, men viser at det likevel kan skrives på forskjellige måter:

18 #(nil? (% %2 1))

Darren har derimot kommet opp med den korteste løsningen (ett tegn mindre):

14 #(not (%2 % 0))

Dette er som sagt et lite eksempel, men det er interresant å se hvor forskjellige løsningene kan bli selv for dette problemet.

Eksempel 2: Konvertere binærtall til desimaltall

I denne oppgaven skulle vi konvertere et binærtall (i form av en streng, f.eks. “1100101″) til et desimaltal. Jeg hadde akkurat oppdaget funksjonen reductions, og syntes den var fin å bruke:

 1 (fn [s]
 2   (reduce +
 3     (map *
 4          (reductions (partial * 2) (repeat 1))
 5          (map #(Integer/parseInt (str %)) (reverse s)))))

Jeg er forsåvidt fornøyd med løsningen, men så etterpå at min nyoppdagelse av reductions hadde gjort at jeg hadde glemt iterate, som hadde vært bedre. Her er maximental’s løsning, som bruker nettopp den, pluss et litt annet triks som gjør at han unngår å parse karakterene til integer:

10 (fn [s]
11   (apply + (map #({\1 %2} % 0)
12                 (reverse s)
13                 (iterate #(* 2 %) 1))))

Beickhoff tenkte litt anderledes:

16 (fn [string]
17   (let [c (fn [acc x]
18              (+ (Integer/parseInt (str x)) (* 2 acc)))]
19     (reduce c 0 string)))

Brukeren dlepage har en ganske fin løsning, synes jeg. I prinsippet er det det samme som jeg og maximental gjorde, men han har brukt pipelining til å forenkle koden:

22 (fn [s]
23   (->> s reverse
24        (map #(- (int %) 48))
25        (map * (iterate #(* 2 %) 1))
26        (reduce +)))

Aredington derimot har tatt helt av, og benyttet group-by, partition og interleave:

29 (fn [str]
30   (let [digits (reverse str)
31         two-raised (fn [n] (apply * (repeat n 2)))
32         digit-count (count digits)
33         powers-of-two (map two-raised (range digit-count))]
34     (apply +
35        (map second
36             ((group-by first
37                        (partition 2
38                                   (interleave digits
39                                               powers-of-two)))
40              \1)))))

Men condotti og immo viste oss alle at det lønner seg å kjenne API’et man har tilgjengelig godt. Så enkelt kan det gjøres:

43 #(Integer/parseInt % 2)

Hvor lenge tror du man må ha jobbet med Clojure for raskt å kunne se at disse seks variantene gjør akkurat det samme?

Eksempel 3: Reverse Interleave

Nå øker vi vanskelighetsgraden. Her skal vi reversere effekten av en funksjon i Clojure som heter interleave. Vi skal lage en funksjon som tar som input en sekvens og et positivt heltall. Og vi skal returnere en liste med sekvenser bygget opp av input. Oppgaven finner du her.

Funksjonen illustreres best med et par eksempler: Hvis input f.eks. er listen [1 2 3 4 5 6] og tallet 2, så skal output bli [[1 3 5][2 4 6]]. Input er altså splittet i to, og annethvert element er plassert i hver sin del.

Hvis input er [0 1 2 3 4 5 6 7 8 9] og 5, skal output bli [[0 5] [1 6] [2 7] [3 8] [4 9]].

Her følger min løsning:

31 (fn [col n]
32   (loop [col col, acc (repeat n [])]
33     (if (seq col)
34       (let [vals (take n col)]
35         (recur (drop n col)
36                (map #(conj %1 %2)
37                     acc
38                     vals)))
39       acc)))

Jeg hadde et “Moment of Zen” da jeg implementerte dette. Funksjonen er en typisk “list eater” med en (synes jeg) litt snedig bruk av map. Det jeg derimot ikke hadde fått med meg var at Clojure har en nyttig funksjon som heter partition. De følgende løsningene forsøker å utnytte den funksjonen på ulike måter for å løse oppgaven.

Her er beickhoff’s løsning:

42 (fn demultiplex [xs n]
43   (let [nth-only (fn nth-only [n xs]
44                      (map first
45                           (partition n n '() xs)))]
46     (map #(nth-only n (drop % xs))
47          (range 0 n))))

Indy’s løsning er ikke helt ulik, men endel enklere:

50 (fn [c n]
51   (map (fn [i]
52            (map #(nth % i)
53                 (partition n c)))
54        (range n)))

Aredington kom opp med noe litt mere avansert. Igjen har han brukt group-by, partition og interleave – jeg tror han er glad i de funksjonene der. Jeg tror jeg ser hvordan den virker, men orker ikke bygge opp et fullstendig mentalt bilde av algoritmen:

57 (fn [c n]
58   (map (partial map second)
59        (vals (group-by first
60                        (partition 2
61                                   (interleave (cycle (range n))
62                                               c))))))

Darren derimot viser oss hvordan oppgaven skal løses – så enkelt kan det gjøres! Det blir nesten pinlig å se tilbake på min egen løsning etter å ha sett denne:

65 #(apply map list (partition %2 %))

Konklusjon

Jeg har forsøkt å vise at forholdsvis enklere problemer ikke bare kan, men i praksis også løses svært forskjellig av ulike Clojure-utviklere.

Clojure og andre Lisp’er er svært fleksible, og lar deg kombinere de grunnleggende funksjonene på utallige måter. Man kan gjøre ting på forskjellige måter i f.eks. C# også, men ikke på langt nær i samme grad som i Lisp. Det er i alle fall det jeg hevder.

En utvikler beskrev Lisp til meg en gang som et “write only” språk. Man kan skrive kode, men det kan være svært vanskelig å lese den. Dette henger sammen med fleksibiliteten. Det er ikke én bestemt måte å gjøre noe på i Lisp, og derfor er det vanskelig å kjenne igjen sammensatte elementer i kode, særlig kode man ikke har skrevet selv.

Dette er både en styrke og en svakhet. En utvikler ved navn Glenn Ehrlich har sagt at programmering i Lisp er som å leke med urkreftene i Universet. Man kan gjøre hva som helst, ting man trodde var umulig før man oppdaget Lisp. Men hvordan studerer man kode som hele tiden redefinerer Universet?

Personlig forholder jeg meg egentlig bare til funksjonsnavn. Gode funksjonsnavn er ultraviktig. Men når jeg får behov får å finne ut hvordan en funksjon løser oppgaven sin så må jeg rett og slett rekonstruere hele funksjonen fra kildekoden, dvs. skape meg et mentalt bilde av hvordan utvikleren tenkte da han implementerte den. Og i Clojure/Lisp kan dette være veldig forskjellig fra hvordan jeg ville ha tenkt.

Gjett om det er viktig med korte funksjoner da, gitt!

Dette problemet er ikke så stort at jeg ikke vil bruke språket – styrken er større enn svakheten for å si det sånn. Men det kan være én forklaring på hvorfor språket ikke er mere brukt.

I tilfelle du ikke synes det er nok med én blogpost hver dag har jeg her en knøttliten bonus til deg. Jeg har jo nå vist deg Euler 1 løst på forskjellige måter i et utall språk. Blant annet har jeg vist hvordan oppgaven kan løses ved hjelp av pattern matching – dette gjorde jeg i F# og i Nemerle, og Kråkelefse delte også en lignende løsning i Haskell.

Når jeg da nylig kom over et matching-biblotek for Clojure måtte jeg nesten teste denne muligheten ut også i det språket. Måtte leke meg litt. Man kan trygt si at multiplene av 3 og 5 har gjort meg litt ensporet. Anyways, here goes…

10 (ns euler1CljMatch.core
11     (:use [clojure.core.match :only [match]]))
12 
13 (let [mod-zero? #(zero? (mod %2 %1))]
14   (def mod-zero-3? (partial mod-zero? 3))
15   (def mod-zero-5? (partial mod-zero? 5)))
16 
17 (defn mult3or5? [x]
18   (match [x]
19     [(_ :when mod-zero-3?)] true
20     [(_ :when mod-zero-5?)] true
21     :else                   false))
22 
23 (defn euler-1 []
24   (loop [n 0, sum 0]
25     (match [n]
26       [ 1000 ]              sum
27       [(_ :when mult3or5?)] (recur (inc n) (+ sum n))
28       [ _    ]              (recur (inc n)    sum))))
29 
30 (println (euler-1))

Det er langt fra optimalt å bruke match til dette her, og det illustrerer heller ikke hva pattern matching er godt for. Men jeg måtte bare få det ut! Viktig å test nye muligheter.

For ordens skyld: I slike situasjoner (som det jeg har rotet meg opp i ved å forsøke å bruke match) foretrekker Lisp’ere å bruke en makro som heter cond. I dette tilfellet gir det mye renere syntaks:

17 (defn mult3or5? [x]
18   (cond (mod-zero-3? x) true
19         (mod-zero-5? x) true
20         :else           false))
21 
22 (defn euler-1 []
23   (loop [n 0, sum 0]
24     (cond (= n 1000)    sum
25           (mult3or5? n) (recur (inc n) (+ sum n))
26           :else         (recur (inc n)    sum))))

Og så var det fire dager igjen til Jul :D

I forrige bloggpost presenterte jeg ulike løsninger på Euler-problem nummer 1. Men alle disse løsningene var i prinsippet like; iterer over alle tall mellom 0 og 1000, og filtrer ut og pluss sammen tallene som er multipler av 3 eller 5.

Jeg klarer ikke helt å slippe denne oppgaven. Alternativt kan vi nemlig se på det som et matematisk sett-problem, og da kan vi implementere løsninger som er litt mere deklerative. Hvis A er alle tall som er multipler av 3, og B er alle tall som er multipler av 5, så er løsningen å summere tallene i unionen av A og B.

La oss ta en titt på ulike måter å implementere dette på…

A + B – snittet av a og b

Gitt at A og B er settene som beskrevet over. Da er en løsning å legge sammen summen av tallene i A og summen av tallene i B. Problemet nå er at tall som både er multipler av A og multipler av B blir lagt til i summen to ganger. For å løse dette kan vi trekke fra summen av alle disse tallene – nemlig alle tall som er multipler av 3 ganger 5, altså 15.

Her er en løsning i Ruby:

10 def sum_multiples args
11   (args[:of]..args[:upto]).
12     step(args[:of]).
13     reduce(:+)
14 end
15 
16 sum  = sum_multiples :of => 3, :upto => 999
17 sum += sum_multiples :of => 5, :upto => 999
18 sum -= sum_multiples :of => 3*5, :upto => 999
19 puts sum

Jeg liker hvor leselig koden blir: “Sum er lik sum multiples av 3 opp til 999″ osv. Men ved å introdusere litt kodeduplisering kan det hele selvsagt gjøres endel enklere:

23 puts (3..999).step(3).reduce(:+) +
24      (5..999).step(5).reduce(:+) -
25      (3*5..999).step(3*5).reduce(:+)

Det vi trekker fra på slutten er altså snittet mellom A og B.

Unionen av a og b direkte

Mange programmeringsspråk/standard bibloteker har direkte støtte for å beregne unionen av to sett, og det kan vi også benytte. Her er en tilsvarende Ruby-implementasjon som oppretter A og B, tar unionen av disse, og summerer sammen:

30 def set args
31   (args[:of]..args[:upto]).
32     step(args[:of]).
33     to_a
34 end
35 
36 multiples_of_3 = set :of => 3, :upto => 999
37 multiples_of_5 = set :of => 5, :upto => 999
38 multiples_of_3_or_5 = multiples_of_3 | multiples_of_5
39 
40 puts multiples_of_3_or_5.reduce(:+)

Nå begynner det å komme seg :) Som en referanse slenger jeg med den samme løsningen implementert i Clojure, som har en egen set-datatype:

1 (defn multiples_of [x upto]
2   (set (range x upto x)))
3 
4 (defn multiples_of_3_or_5 []
5   (clojure.set/union (multiples_of 3 1000)
6                      (multiples_of 5 1000)))
7 
8 (->> (multiples_of_3_or_5) (reduce +) println)

Som du forstår er det mange ulike måter å løse en programmeringsoppgave på – selv en så enkel oppgave som dette. Ulike språk foretrekker ulike løsninger, og det er en av grunnene til at det er interessant å studere dem.

NÅ er det på tide å gi seg! Håper jeg ikke har kjedet vettet av deg med denne oppgaven – men nå er du i alle fall skikkelig primet og klar til å studere løsninger programmert i diverse språk du sansynligvis aldri har sett før. Neste blogpost kommer 1. desember!

I den oppkommende adventskalenderen, hvor jeg hver dag frem til Jul vil introdusere deg for et nytt programmeringsspråk, har jeg valgt én bestemt oppgave for å vise frem språkene – nemlig den første og enkleste oppgaven på Project Euler.

Oppgaven lyder:

Hvis vi lister opp alle naturlige tall under 10 som er multipler av 3 eller 5 så får vi 3, 5, 6 og 9. Summen av disse er 23. Finn summen av alle multipler av 3 eller 5 under 1000.

Jeg bruker denne oppgaven som min Hello, World når jeg lærer meg nye språk. Den sørger for at jeg raskt lærer meg flere grunnleggende byggestener i språket, som hvordan man itererer, og hvordan man tar avgjørelser basert på numeriske operasjoner.

Jeg har også brukt oppgaven her på bloggen tidligere, i posten Parallellisering av en algoritme i Erlang. I dag gir jeg deg mulighet til å gjøre deg kjent med oppgaven, og viser noen implementasjoner i de språkene du normalt ser på programmeringsbloggen.

Løsning i C#

C# er språket jeg bruker til daglig, så det er et greit sted å begynne. Her følger en komplett løsning som looper gjennom alle tallene opp til 1000, sjekker om de er multipler av 3 eller 5 (ved å bruke modulo), og summerer opp tallene i sum-variabelen. Det siste som skjer er at tallet skrives ut.

10 class Program
11 {
12     static void Main()
13     {
14         int sum = 0;
15         for (int i = 0; i < 1000; i++)
16             if (i % 3 == 0 || i % 5 == 0)
17                 sum += i;
18         System.Console.WriteLine(sum);
19     }
20 }

Som sagt er det en meget enkel oppgave – så sant du kjenner til modulo da.

En alternativ måte å løse oppgaven er å bruke en funksjonell, stream-basert teknikk. I .NET vil dette si Linq. Her er en løsning i C# som bruker Range, Where og Sum:

10 using System.Linq;
11 
12 class Program
13 {
14     static void Main()
15     {
16         System.Console.WriteLine(
17             Enumerable.Range(1, 999)
18             .Where(i => i % 3 == 0 || i % 5 == 0)
19             .Sum());
20     }
21 }
22 

I julekalenderen vil du komme til å se en god mix av disse to fremgangsmåtene, og noen som er helt anderledes.

Løsning i Ruby

Ruby er det språket det er lettest for meg å hoppe inn i om jeg skal lage et kjapt lite verktøy, skal teste ut en algoritme eller noe lignende. Her følger en imperativ løsning:

1 sum = 0;
2 (1...1000).each do |i|
3   sum += i if i.modulo(3) == 0 or i.modulo(5) == 0
4 end
5 puts sum

I Ruby bruker jeg omtrent aldri vanlige for-løkker – å opprette en range, og så kjøre en kodeblokk for hvert element er mere naturlig.

En stream-basert løsning er mere elegant. Da bruker jeg select for å filtrere tallene, og reduce for å summere, slik som dette:

7 puts (1...1000).
8   select{|x| x.modulo(3) == 0 or x.modulo(5) == 0}.
9   reduce(:+)

Løsning i Clojure

Clojure er fortsatt favorittspråket mitt, så jeg må ta med noen løsninger i det også. Selv om det er helt unaturlig å bruke en løkke i Clojure så har jeg kokt sammen en slik løsning for denne ene gangens skyld:

 1 (loop [sum 0, numbers (range 1000)]
 2   (if (seq numbers)
 3     (let [i (first numbers)]
 4       (if (or (zero? (mod i 3))
 5               (zero? (mod i 5)))
 6         (recur (+ sum i) (rest numbers))
 7         (recur sum (rest numbers))))
 8     (println sum)))

Det fungerer, men jeg gremmes! I Clojure er stream-basert programmering det naturlige, og jeg kan bruke range, filter og reduce til å løse oppgaven ganske enkelt:

 1 (println
 2   (reduce +
 3           (filter #(or (zero? (mod % 3))
 4                        (zero? (mod % 5)))
 5                   (range 1000))))

Det er derimot ikke sikkert du synes det er så enkelt å lese denne koden. Trikset med å lese Clojure/Lisp-syntaks er som følger: Skann raskt med øynene fra venstre mot høyre til du kommer til uttrykkets siste del, som i dette tilfellet er (range 1000). Arbeid deg så tilbake mot høyre.

For å gjøre koden litt mere leservennlig tilbyr Clojure deg å gjøre det samme på følgende måte:

10 (->> 1000 range
11      (filter #(or (zero? (mod % 3))
12                   (zero? (mod % 5))))
13      (reduce +)
14      println)

Denne koden kan leses fra venstre mot høyre. “Ta tallet 1000, og lag en range av det. Filtrer med en anonym funksjon som sjekker om tall er delelig på 3 eller 5. Reduser med pluss (altså pluss dem sammen), og skriv til slutt ut”.

Løsning i Common Lisp

Og helt på tampen tar jeg med en løsning i Common Lisp – fordi man der finner den kuleste og mest komplette varianten av en for-løkke som finnes i noe språk, nemlig loop makroen:

1 (print (loop for x below 1000
2              when (or (zerop (mod x 3))
3                       (zerop (mod x 5)))
4              sum x)

Du har nå sett oppgaven løst med fire ulike språk, og i desember vil du få se flere løsninger. Da vil jeg sansynligvis bryte oppgaven opp i flere steg eller funksjoner, slik at jeg får presentert enda flere aspekter ved språkene jeg forteller om.

Jeg håper du gleder deg like mye som meg :)

En nerd må ha noe å gjøre på. Så i sommer begynte jeg å implementere et nytt programmeringsspråk. Jeg har valgt å kalle det Mist!

Navnet ble valgt før jeg ble gjort oppmerksom på at det på tysk betyr gjødsel (for å si det pent).

Mist skal være et general purpose, dynamisk språk med fokus på den funksjonelle programmeringsparadigmen, og tilhører Lisp-familien. Det kjører på .NET-plattformen, og er implementert i C#.

Hvorfor?

Jeg begynte på dette for å lære, og for å ha det gøy. Alle utviklere med noen år på baken og respekt for seg selv burde vite hvordan man bygger et språk, og den eneste måten å kontrollere at man vet hvordan er å gjøre det.

Følelsen jeg hadde da jeg f.eks. implementerte rekursjon, eller da jeg fikk til closures, var helt hærlig. Følelsen litt senere av å forstå at jeg hadde løst scopes feil (etter å ha lest litt i Structure and Interpretation of Computer Programs), for så å rette det opp slik det burde være, var enda bedre. Jeg har allerede lært mye av dette, selv om jeg er LANGT FRA FERDIG.

Kan det brukes til noe?

Mist kommer ikke til å bli det neste, store språket som alle kommer til å ville bruke. Det kommer ikke til å kunne konkurrere med for eksempel Clojure. Men kanskje finnes det en liten nisje hvor Mist kan komme til nytte? Selv om jeg gjør dette for å lære og å ha det gøy, så har jeg i alle fall tenkt å holde på til jeg har et “ferdig” språk som kan tas i bruk av andre enn meg selv.

Mist kan brukes på flere måter; spåket er implementert i form av en høy-nivå tolker som består av én enkelt .NET dll. Denne kan refereres direkte i .NET-prosjekter for å gjøre dem “skriptbare”. Jeg har også laget en enkel Read-Eval-Print Loop hvor man interaktivt kan eksperimentere med Mist-kode, eller laste og kjøre Mist-filer.

Som en tredje opsjon har jeg tenkt å tilby en slags kompilator som tar en eller flere Mist-filer som input, og genererer en “standalone” exe-fil.

Noen betraktninger

Når man skal implementere dynamiske språk på .NET-plattformen kan det være naturlig å basere seg på Dynamic Language Runtime. Det valgte jeg derimot å ikke gjøre. Jeg ville lære mest mulig som jeg kan benytte uavhengig av plattform, og ikke bruke tid på å sette meg inn i et biblotek hvor deler av jobben allerede er gjort.

Det finnes forøvrig mange beskrivelser på nett og andre steder av hvordan man implementerer Lisp-lignende språk. Jeg valgte å ikke studere disse – mitt fokus var igjen å bruke og lære generelle teknikker for å utvikle parser, tolker og/eller kompilator (hovedinspirasjonen til prosjektet er boken Language Implementation Patterns – og så trekker jeg på det jeg allerede kan om Clojure, Scheme og Common Lisp).

Ved første øyekast ser Mist ut som en hvilken som helst Lisp-implementasjon, men det skiller seg nok litt fra de fleste andre likevel. Blant annet har jeg valgt å ikke basere liste-strukturene på såkalte cons-par. I stedet bruker jeg listene i .NET basebibloteket.

Det er også vanlig at store deler av språk i Lisp-familien implementeres i språket selv. Mist består derimot av ganske mye C# – dette er for å utnytte det som allerede finnes i .NET, blant annet i et håp om å gjøre koden raskere enn jeg ellers ville klart.

Veien videre

Men det er tidlig enda. Jeg ser for meg at jeg skal jobbe med Mist – på bussen, fergen, og på kveldstid – i et par måneder til før jeg har noe som kan kalles en beta. Og estimater er til for å sprekke!

Av ting som jeg gleder meg til å gå igang med nå kan jeg nevne reader-macros, syntax quoting og tail call optimalisering. Når det gjelder tail calls så har jeg en ide om at jeg kan løse det med contiuation passing, men jeg må nok gjøre litt mer research før jeg er sikker på hvordan det skal gjøres.

Jeg har også planer om en dyp integrasjon med .NET (bruke .NET-typer fra Mist) som vil skille seg endel i fra hvordan f.eks. Clojure er integrert med Java. Med det gjenstår å se om det lar seg realisere.

Er du interessert i å ta en titt på koden, eller laste det ned og ta Mist på en liten kjøretur, så finner du prosjektet på Github. Bedre dokumentasjon på bruk og API kommer etterhvert.

Er du klar for å hopp inn i tidsmaskinen og ta en titt på hvordan verden så ut for 15+ år siden? Slik føles det nemlig når du surfer rundt i Common Lisp (CL) -miljøet på nettet. Det er ganske fasinerende egentlig, og veldig, veldig merkelig.

La oss først ta et titt på en av de aller mest sentrale CL-sidene, nemlig CLiki – the common lisp wiki (screen shot under). Dette er faktisk et eksempel på en av de bedre sidene jeg har funnet; den er ganske ryddig og grei, men står litt tilbake for det jeg normalt forventer av en wiki.

Men la oss gå videre. Når man vurderer et programmeringsspråk er det viktig å se på selve communitiet, på brukergrupper og organisasjoner som fremmer brukernes interesser. Den sentrale organisasjonen i CL-miljøet ser ut til å være ALU – Association of Lisp Users (screen shot under). Hvilket inntrykk får du av denne websiden?

Hvis du ser helt nederst på skjermbildet der så ser du forresten at det jobbes med et nytt design for ALU og lisp.org. Jeg venter i spenning!

Det finnes mange ulike implementasjoner av CL. Den utgaven det ofte virker mest naturlig for nybegynnere å velge er GNU CLISP (screen shot under som vanlig), en gratis CL-implementasjon som kjører på mange platformer. Hvor komfortabel ville du være med å installere noe du fant på denne siden?

Det er lenge siden jeg har sett HTML-tabeller med border=”15″, men på clisp.org mener man tydeligvis at hvis det var godt nok i 95 så bør det være godt nok i 2011.

Det finnes også en rekke komersielle CL-implementasjoner, men websidene deres er ikke så veldig mye bedre. Som en helt tilfeldig representant kan vi se på Corman Common Lisp (du klarer sikker finne screen shot’et selv fra nå av).

Dette er altså hjemmesiden til et firma som lever av å selge en programmeringsplattform, og som selvfølgelig bør gi inntrykk av at de følger med i tiden. De har derfor innsett at de bør gjøre noe med siden, og har begynt på et nytt design…., som du ser nedenfor.

Ok, de har fått seg farger, og viser nå at de er glade i graderinger. Og det er sikkert ubetydelig få brukere som får epileptisk anfall mens de ser på den.

Den gjennomsnittelige internettsiden om Common Lisp har minimalt med grafiske elementer, og minimalt med formatering. Man kan si at “Content is King” i CL-verden. Mange sider har ikke noen meny engang, absolutt alt man ønsker å si er bare spydd nedover forsiden. Et eksempel på dette finner man på siden til en av de mest kjente CL-webserverne, nemlig Hunchentoot.

Legg merke til scrollbaren til høyre. Legg også merke til den fantastiske logoen. Det er ikke mange CL-prosjekter som har en egen logo, så Hunchentoot skiller seg faktisk positivt ut på det området. Selv om den ser ut til å ha vært designet i paint av en femåring er den ganske kul.

Slik flertallet av disse sidene er designet kan det nesten virke som om Common Lisp-utviklere ikke har oppdaget at grafiske brukergrensesnitt eksisterer, og at de stort sett surfer nettet via Lynx eller lignende tekstbasert browser. Men det må i alle fall være noen CL-utviklere som bruker GUI, for det finnes nemlig flere GUI-rammeverk for språket. McCLIM er et av dem.

Det er ikke rart folk tror Common Lisp er et dødt språk når de ser websider som dette. Sammenlign denne siden med sider som omhandler f.eks. Adobe AIR. Hvilken platform blir du mest fristet til å velge?

Den neste siden jeg har funnet er en godbit for alle .NET-ninjaer: RDNZL (uttales “Redunzl”) er et biblotek som lar deg kalle .NET-kode fra Common Lisp. Jeg har testet det ut, og det fungerer utmerket. Men websiden er ikke spesielt imponerende. Legg igjen merke til scrollbaren.

Selve rosinen i pølsen har jeg spart til sist. Common Lisp HyperSpec er hovedkilden til API-dokumentasj for CL-utviklere. Den har blant annet en “fantastisk” imagemap-basert meny, og designerne har tideligvis ikke vurdert søk som en viktig funksjon – søk finnes nemlig ikke. Anbefaler at du klikker på bildet og tar en nærmere titt på egenhånd…

Det har ikke vært meningen å henge ut folk i denne blogposten – det er mye bra innhold på disse sidene, og mange utviklere som har jobbet hardt og lenge med gode CL-løsninger. Men det må være lov å le litt av hvordan det hele presenteres.

Jeg sitter tilbake med en følelse av at noe bør gjøres for å løfte det generelle inntrykket folk får av Common Lisp på nettet. Jeg får lyst til å hjelpe til. Lyst til å lage en ny, moderne portal og inngangsport til språket. Forslag til konkrete ting vi kan gjøre mottas med takk!

Jeg har laget en ny video til dere; denne gangen har jeg tatt opp mitt forsøk på å gjennomføre Bowling Kata i Clojure (bakgrunn om Bowling Game Kata på codingdojo.org og butUncleBob.com).

Jeg sier forsøk fordi jeg knoter litt underveis. Jeg valgte derimot å beholde videoen slik den var i stedet for å ta den opp igjen – å se hvordan jeg feiler, og hvordan jeg får hjelp av testene til å hente meg inn igjen, har også en viss verdi.

Så hvis du trenger litt TDD og/eller Clojure-inspirasjon, her har du en ærlig og munter code cast:

Det er ikke fredag i dag, men likevel, jeg gir dere “Universet, første alpha-versjon”…

(ns genesis
    "Book of Genesis, 
    Version 0.0.1-SNAPSHOT")

; Some universal plumbing..
(def darkness 0)
(def light (inc darkness))
(def be identity)

; The main character..
(def God
     (fn [miracle something]
         (condp = miracle
             :create (symbol (name something))
             :see    (if (= something light) :good :evil)
             :say    (println "GOD:" something))))

; In the beginning
(defn in-the-beginning [darkness god]

   ; God created the heaven and the earth.
   (let [heaven (god :create :heaven)
         earth  (god :create :earth) ]
     (assert (and (= heaven 'heaven)
                  (= earth 'earth)))

     ; And God said,
     (god :say
          (pr-str
            ; Let there be light:
            (let [there (be light)]

              ; and there was light.
              (assert (= there light))

              ; And God saw the light,
              (assert (= (god :see light)
                         ; and it was good.
                         :good))

              ; And God divided the light from the darkness.
              (try (/ light darkness)
                   (catch java.lang.ArithmeticException ex
                          (god :say
                               (str "Ah, can't devide by zero, "
                                    "genesis postponed!")))))))))

(in-the-beginning darkness God)
;=> GOD: Ah, can't devide by zero, genesis postponed!
;=> GOD: nil
;=> nil