tirsdag 3. januar 2012 Lisp Clojure
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 :)
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.
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?
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 %))
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.