LISP/Clojure

Magnar Sveen er en meget hyggelig fyr jeg har presentert en gang tidligere på denne bloggen. I sommer klarte han med sin editor-magi å nesten få meg til å konvertere fra Vim til Emacs. Som Emacs-hacker programmerer Magnar endel Lisp, og i dagens blogpost deler han av sin erfaring omkring dette. Du behøver ikke kunne Lisp for å få utbytte av artikkelen, kun et åpent sinn – Magnar forklarer det meste underveis.

Hvem er du?
En glad utvikler som knaster taster på toget mellom Oslo og Fredrikstad hver dag.

Hva er jobben din?
Framsieutvikler og partner i Kodemaker.

Hva kan du?
Trives godt i hele stacken – oftest solgt inn som frontend.

Hva liker du best med yrket ditt?
Å bygge ting.

Eksempler i Lisp: Kode som genererer tester og dokumentasjon

Jeg fikk til noe kult her om dagen.

Som du vet så er ikke dokumentasjon det morsomste å skrive. Og det er skremmende lett å glemme å oppdatere dokumentasjonen når du gjør endringer.

Så når jeg skulle lage et liste- og et string-bibliotek til Emacs, så fant jeg en fet løsning på akkurat det problemet.

Se her:

(defexamples s-dashed-words
  "some words" => "some-words"
  "under_scored_words" => "under-scored-words"
  "camelCasedWords" => "camel-cased-words")

Her definerer jeg noen eksempler på hvordan en funksjon fungerer. Det kule er at jeg ut i fra disse genererer både tester og dokumentasjon.

La oss starte med det første:

Generere tester

Slik må testen se ut for at testrammeverket skal forstå den:

(ert-deftest s-dashed-words ()
  (should (equal (s-dashed-words "some words") "some-words"))
  (should (equal (s-dashed-words "under_scored_words") "under-scored-words"))
  (should (equal (s-dashed-words "camelCasedWords") "camel-cased-words")))

Så nå skal vi ta eksempelkoden øverst og bygge om til denne testkoden programatisk. Det gjør vi med makroer.

Noen introduksjoner

• Makroer bygger ny kode. Du gir dem argumenter som så brukes til å sette sammen den endelige koden før den kjøres.

• Homoikonisitet betyr at språket er definert ved hjelp av sine datastrukturer. Altså kan kode både kjøres, men også undersøkes, manipuleres og bygges på samme måte som annen data i applikasjonen.

Homoikonisitet er essensielt for å få bunnsolide makroer.

I lisp får vi dette fordi et funksjonskall er en liste:

(* 2 4)

Dette er en liste med tre elementer (*, 2 og 4), og når den evalueres så blir det første elementet i listen kalt som en funksjon, og resten som parametere til den funksjonen – og vi får 8.

Anatomien til en makro

I lisp så er altså jobben til en makro å lage en liste som skal evalueres. Du kan lage listen akkurat slik du selv vil, men det finnes noen triks for å gjøre det lettere. La oss starte med et enkelt eksempel:

(defmacro multiply (a b)
  (list '* a b))

Denne tar i mot to argumenter, og bygger en liste på tre elementer. Hvis du stusser over fnutten foran * så er det en quote. Det er slik man sørger for at symbolet ikke blir evaluert, men får stå som det er.

Altså vil (multiply 2 4) bygge koden (* 2 4) som deretter evalueres til 8.

Vi kan også quote hele lister, slik:

'(* 2 4)

Denne blir ikke evaluert til 8, men fortsetter å være listen på tre elementer. Det kan vi bruke når vi skal lage makroer:

(defmacro multiply (a b)
  '(* a b))

men det fungerer ikke helt. Dette vil returnere lista akkurat slik, altså (* a b) – så når denne skal evalueres så er a og b ikke lengre bundet. Men det peker mot trikset:

(defmacro multiply (a b)
  `(* ,a ,b))

Backtick lar oss quote lista, men hvor vi kan evaluere deler av uttrykket. Kommaet escaper ut av quotingen, slik at verdiene i a og b settes inn. Tenk ruby eller python sin string interpolation.

Kanskje skulle multiply kunne ta flere argumenter? Vi prøver:

(defmacro multiply (&rest numbers)
  `(* ,numbers))

Nøkkelordet &rest betyr at resten av argumentene havner i lista numbers. Men dette gir ikke ønsket resultat. Vi ender opp med (* (2 4 6)).

Istedet skriver vi:

(defmacro multiply (&rest numbers)
  `(* ,@numbers))

Escapingen ,@ tar lista i numbers og splicer inn. Da får vi (* 2 4 6) som ønsket.

Og med det er vi klare for å generere testene:

Generere tester, take two

Vi vil altså at dette:

(defexamples s-dashed-words
  "some words" => "some-words"
  "under_scored_words" => "under-scored-words"
  "camelCasedWords" => "camel-cased-words")

skal transformeres til dette:

(ert-deftest s-dashed-words ()
  (should (equal (s-dashed-words "some words") "some-words"))
  (should (equal (s-dashed-words "under_scored_words") "under-scored-words"))
  (should (equal (s-dashed-words "camelCasedWords") "camel-cased-words")))

Og det gjør vi ved å definere defexamples slik:

(defmacro defexamples (fn &rest examples)
  `(ert-deftest ,fn ()
     ,@(map (partial 'example-to-should fn) (partition 3 examples))))

Den tar i mot funksjonen vi tester som fn, og en liste med eksempler. Jeg stykker opp examples i tripletter, som da ser slik ut:

0: "some words"
1: =>
2: "some-words"

Disse mapper jeg over en example-to-should som ved hjelp av partial har fått satt første parameter til fnallerede.

Her er den:

(defun example-to-should (fn example)
  (let ((actual (nth 0 example))
        (expected (nth 2 example)))
    `(should (equal (,fn ,actual) ,expected))))

Som du ser så tar den første og siste element i lista, og bygger opp should-uttrykket. => blir bare ignorert.

Ved hjelp av kun disse to, en liten funksjon example-to-should og en liten makro defexamples, så gjør jeg eksemplene om til tester og kjører dem.

Men det som gjør dette fett, er jo at de samme eksemplene brukes til å generere dokumentasjonen.

Generere dokumentasjon

Ta en titt på den genererte dokumentasjonen her. Slik ser én entry ut:

s-dashed-words (s)

Convert s to dashed-words.

(s-dashed-words "some words") ;; => "some-words"
(s-dashed-words "under_scored_words") ;; => "under-scored-words"
(s-dashed-words "camelCasedWords") ;; => "camel-cased-words"

Som du ser så er eksemplene der, men også funksjonens parameterliste og en forklarende tekst. Hvor kommer de fra?

Homoikonisitetens vidundere

Se her:

(symbol-function 's-dashed-words)

Slik får jeg tak i funksjonen som symbolet s-dashed-words peker på.

Jeg kan kalle den:

(funcall (symbol-function 's-dashed-words) "camelCase")

;; => "camel-case"

Men det sprø her er at funksjonen er en liste som jeg kan grave meg inn i. Slik ser den ut:

(lambda (s)
  "Convert S to dashed-words."
  (s-join "-" (map 'downcase (s-split-words s))))

Det jeg funcall‘er der oppe er ikke en peker til noe kompilert i minnet. Det er denne listen.

Så når jeg kaller

(nth 0 (symbol-function 's-dashed-words))

får jeg ut lambda. Og når jeg kaller

(nth 1 (symbol-function 's-dashed-words))

får jeg ut (s). Og når jeg kaller

(nth 2 (symbol-function 's-dashed-words))

får jeg ut "Convert S to dashed-words.".

Og det er ved å kombinere eksemplene, og ved å grave meg inn i datastrukturen som definerer funksjonene at jeg setter sammen dokumentasjonen.

Koden for det er litt mer omfattende, men hvis du er nysgjerrig så finner du den her på github.

Til slutt

Det aller kuleste er at dokumentasjonen aldri går ut på dato. Hvis navn eller signaturer endrer seg, så gjenspeiles det øyeblikkelig i dokumentasjonen. Og eksemplene er alltid riktig.

Konge.

Helt siden i september 2009 (da Greg Young var på besøk i Bergen) har jeg tenkt på event sourcing. Og i årene etter har dette blitt en mer og mer populær arkitektur blant de softwareutviklerne som er mest cutting edge.

Men jeg har ikke bygget noe med det i tiden som har gått siden da. Å treffe Greg igjen på NDC i år har derimot stimulert meg på nytt, og her følger en blogpost som forklarer hva det går i, og som implementerer et lite eksempel.

Blogposten er også en liten leksjon i programmeringsspråket Clojure. Eksempelet er en nedskalert begynnelse på et verktøy jeg kommer til å lage for eget bruk, og dette språket er ideelt for oppgaven. Men kunnskap om Clojure er absolutt ikke nødvendig for å henge med i det jeg gjør, alt du behøver er et åpent sinn.

Hva er Event Sourcing?

Event sourcing består av to steg:

1. Man lagrer alle endringer i et system som en sekvens av hendelser.
2. Man bygger opp igjen systemets tilstand fra disse registrerte hendelsene.

Se for deg hvordan en bank overfører penger fra en konto A til en konto B. De gjør ikke som i de typiske kodeeksemplene hvor man har en databasetransaksjon, og oppdaterer saldoen på de to kontoene i én atomisk operasjon. Nei, saldoen i banken din består av en serie med hendelser:

1. Konto opprettet, saldo kr 0,-
2. Innskudd a kr 30 000,-
3. Overføring fra konto X a kr 560,-
4. Betalt regning a kr 1 499,-
5. 1,1% renter effektuert
6. Debetkort belastet kr 19.50
7. osv…

Selv om den ikke står der eksplisitt er det enkelt å beregne saldoen.

På grunn av at man kan bygge opp igjen systemets tilstand fra hendelsene kan man ofte klare seg uten noen annen form for lagring av tilstand. I praksis vil man nok ofte likevel lagre data i et annet format for eksempel for rapportering, og man vil også ta “snapshots” av tilstand for å slippe å kjøre gjennom hele loggen hver gang man trenger tilstand. Men rapportene og snapshotene kan når som helst forkastes og genereres på nytt fra loggen.

Fordelene med event sourcing

Fordelene med event sourcing er mange, men det kan være et komplekst tema å diskutere. Jeg har ikke mye erfaring, så jeg vil ikke gå i dybden, men her er de viktigste punktene slik jeg ser det:

• Event sourcing innebærer såkalt append only data storage – man behøver ALDRI oppdatere data. Dette løser flere problemer, spesielt knyttet til transaksjoner og samtidighet, og skrivehastigheten til systemet kan øke dramatisk. Skulle samtidighetskonflikter mellom endringer snike seg inn så er det også mye enklere å rydde opp i dem med en hendelseskø.
• Et system som baserer seg på event sourcing er godt tilrettelagt for testing. Man kan simulere all mulig adferd ved å sette opp en sekvens av hendelser. Og opplever man problemer i produksjon kan feilene alltid gjenskapes ved å kjøre hendelsesloggen derfra. Dette er gull!
• Hendelsesloggen inneholder ikke bare hvilke dataendringer som har skjedd, men eksplisitt hvorfor de skjedde. Meningen bak tilstandsendringene blir tatt vare på. Dette er noe som mangler i de fleste “vanlige” systemer i dag, og er verdifullt av mange grunner. En av dem er at man etter at systemet er i produksjon kan komme opp med nye måter å analysere bruken på, og så kjøre disse analysene på historiske hendelser.
• Og finner man en bug i systemet; da fikser man den, ruller systemet tilbake, og alle hendelsene blir registrert på nytt med den nye koden. Feil i data vil “fikse seg selv”.

Hvorfor (og hva er) s-expressions?

For noen år siden var XML det ultimate dataformatet. Nå føles det som om JSON er blitt vårt standard format, både for lagring og for kommunikasjon mellom tjenester. Men det har lenge funnes et annet format i denne kategorien, et format som i sin tid ble utviklet for å representere både kode og data (i form av lister og trær) i programmeringsspråket LISP. Dette er såkalte symbolske uttrykk, gjerne forkortet til sexprs eller sexps.

Sexps er enkle å parse, mye mindre bråkete enn XML, og mere fleksible enn JSON. Du ser ikke mye til dette formatet utenfor Lisp-sfæren, men det er ekstremt kraftig. Hvorfor? Fordi de kan representere data og programkode på en og samme tid.

I denne blogposten skal jeg implementere en del av et todo-program. I programmet skal man kunne opprette todo-items, flytte dem rundt mellom ulike “bøtter”, markere dem som utført, slette dem, og lignende handlinger.

Hva om jeg lar todo-programmet logge alt som skjer til en fil, og jeg logger på et format som dette:

(todo-created (id t1) "Experiment with event sourcing s-expressions")
(todo-created (id t2) "Draw some good event sourcing illustrations")
(todo-created (id t3) "Blog about event sourcing")
(todo-moved   (id t1) (todo-bucket today))
(todo-moved   (id t2) (todo-bucket tomorrow))
(todo-moved   (id t3) (todo-bucket tomorrow))
(todo-done    (id t1))
(todo-created (id t4) "Create an awesome todo system")
(todo-moved   (id t4) (todo-bucket in-two-days))
(todo-created (id t5) "Rule the World!")
(todo-moved   (id t5) (todo-bucket later))
(todo-deleted (id t5) (reason "Just kidding"))

Det du ser over er kun en tekstfil. Men loggelinjene er formatert som sexps. Altså er de gyldige Lisp-uttrykk. Hva om jeg så implementerte funksjoner som het todo-created, todo-moved osv., og så kjørte loggfilen gjennom en Lisp-tolker – f.eks. Clojure?

Loggen vil da ha blitt til et program skrevet i et domenespesifikt språk som gjenskaper tilstanden som hendelsene loggen er generert ut ifra en gang før skapte.

Det kan tenkes du bør lese den forrige setningen mer enn én gang!

En implementasjon i Clojure

Så la oss skrive litt kode som er i stand til å gjøre dette. Jeg begynner med å deklarere et navnerom, og oppretter så en variabel todos (globalt i navnerommet). Denne peker til en hash / dictionary / lookup table som vil holde programmets todo-items.

(ns worklog.core)

;; Todo items are stored here
(def todos (atom {}))

Deretter begynner jeg å skrive implementasjoner for nøkkelordene i loggfilen. Jeg tar de enkleste først – dette er små makroer som transformerer symbolene de omkranser til spesifike datatyper i Clojure (henholdsvis string for id og keyword for todo-bucket). Reason, som brukes i siste linje i loggfilen, tar en streng og ikke et symbol som parameter, og returnerer den derfor bare som den er. Dette er et eksempel på en funksjon som bare eksisterer for å gjøre loggfilen mere leselig.

(defmacro id [id]
  (str id))

(defmacro todo-bucket [bucket-id]
  (keyword bucket-id))

(def reason identity)

Og så har jeg kommet til den første seriøse funksjonen, nemlig todo-created. Parametrene er en todo-id og en todo-beskrivelse. Hvis et todo-item med gitt id allerede finnes i todos kaster den et exception. Hvis ikke legger den til et nytt objekt i en default bøtte (staging) og med default tilstand (open):

(defn todo-created [id description]
  (if (@todos id)
    (throw (Exception.
             (str "Todo with id " id
                  " already exist, can't create!")))
    (swap! todos assoc id { :id     id
                            :desc   description
                            :bucket :staging
                            :state  :open })))

Før jeg implementerer de resterende tre funksjonene trenger jeg en liten makro – dette er for å unngå at jeg repeterer meg selv i koden. De tre funksjonene skal nemlig oppdatere et todo-item, så da lager jeg en makro jeg kaller update-todo! som gjør det for en gitt todo-id, et feltnavn, og en verdi.

Makroen kontrollerer at et todo-item med den gitte identifikatoren eksisterer, og kaster et exception hvis det ikke gjør det:

(defmacro update-todo! [id key val]
  `(if-let [todo# (@todos ~id)]
     (swap! todos assoc-in [~id ~key] ~val)
     (throw (Exception.
              (str "Unable to find todo " ~id)))))

OBS: Nærmere gjennomlesning fikk meg til å innse at jeg her har laget en makro helt unødvendig – dette kunne ha vært en helt vanlig funksjon. Jaja..!

Når jeg har update-todo! er det trivielt å implementere funksjonene for å flytte, markere som utført, og å slette et todo-item:

(defn todo-moved [id bucket]
  (update-todo! id :bucket bucket))

(defn todo-done [id]
  (update-todo! id :state :done))

(defn todo-deleted [id _reason-ignored]
  (update-todo! id :state :deleted))

Den siste funksjonen illustrerer også et case hvor loggfilen inneholder informasjon som jeg ikke behøver for å gjenskape programmets tilstand – nemlig årsaken til hvorfor et todo-item ble slettet.

På tide å laste event-historikken

Alt jeg nå trenger å gjøre for å laste todo-listen min er å laste logfilen og eksekvere den. Følgende funksjon gjør det (den er egentlig bare en wrapper som gir meg en funksjon med et litt mere spesifikt navn):

(defn load-events-from-file [file]
  (load-file file)
  :ok)

Hvis jeg nå fyrer opp en REPL i terminalen min og laster DSL-koden så kan jeg kjøre funksjonen og gi den stien til loggfilen min (altså filen gjengitt i toppen av bloggposten):

worklog.core=> (require 'worklog2.core :reload)
nil
worklog.core=> (load-events-from-file "./todo.log")
:ok

Å skrive ut todo-listen

load-events-from-file svarer med nøkkelordet “ok”. todos-variabelen vil nå inneholde todo-itemene mine. Vi kan se på innholdet direkte, men i stedet tar jeg meg tid til å vise deg litt kode jeg har skrevet for å presentere listen litt bedre.

Funksjonene er små og har gode navn, så se om du klarer å skjønne hva de gjør (det kommer ingen forklaring):

;; Formating functions to print todo list

(defn todo-state-to-str [t]
  (condp = (:state t)
    :done    "DONE"
    :deleted "XXXX"
    :open    "    "))

(defn todo-2-str [t]
  (str "  [" (todo-state-to-str t)  "] "
       (:desc t)))

(defn todos-for-bucket [b todos]
  (filter #(= (:bucket %) b) todos))

(defn bucket-to-str [b-id]
  (let [s (name b-id)]
    (str (.toUpperCase (subs s 0 1))
         (.toUpperCase (subs s 1)))))

(defn print-bucket [id todos]
  (println (bucket-to-str id))
  (doseq [t (todos-for-bucket id todos)]
    (println (todo-2-str t))))

(defn print-todos
  ([] (print-todos (vals @todos)))
  ([t]
    (println "--- TODO-LIST ----------------------------")
    (doall (map #(print-bucket % t)
                [:today :tomorrow :in-two-days :later]))
    'EOF))

Om jeg nå går tilbake til REPL’en og evaluerer funksjonen print-todos så får jeg en formatert utskrift av todo-listen min slik den ble etter at jeg lastet inn alle eventene fra todo.log:

worklog.core=> (print-todos)
--- TODO-LIST ----------------------------
TODAY
  [DONE] Experiment with event sourcing s-expressions
TOMORROW
  [    ] Blog about event sourcing
  [    ] Draw some good event sourcing illustrations
IN-TWO-DAYS
  [    ] Create an awesome todo system
LATER
  [XXXX] Rule the World!
EOF

Som du kan se er alle items flyttet inn i riktige bøtter, dagens todo-item er utført, og verdensherredømme er kansellert.

Konklusjon

Du har sett meg fortelle om event sourcing, som er en teknikk hvor man lagrer alle hendelser i et softwaresystem, for så å kunne gjenskape nåtilstand (eller tilstanden for et hvilket som helst tidspunkt) ved å kjøre hendelsene på nytt. Dette eliminerer mer eller mindre behovet for klassisk lagring av tilstand, og gir en rekke nye muligheter.

Jo mer jeg tenker på disse mulighetene, jo mer verdifull blir denne teknikken for meg. Jeg kan f.eks. veldig enkelt lage ulike versjoner av DSL’en / parseren som utfører ulike ting basert på hendelsene i loggen. Mulighetene rundt testing, både hva angår enkelhet og styrke, er også veldig interessante.

Se ikke bort ifra at jeg kommer til å begynne å logge i sexps-format overalt fremover. Du er herved advart! :D

OPUS POLYGLOTIS II, Act 4
Tagline: "Groteskt vakkert!"
På scenen: Clojure

Jeg har presentert 3 ulike programmer som gjør det samme – i Python, Ruby og Rebol – og her kommer den aller siste implementasjonen for denne gang.

Clojure er et herlig språk, men det kan være vanskelig å lese koden – spesielt når man ikke har skrevet den selv. Jeg vil likevel anbefale deg som er interessert i programmeringsspråk å ta en titt, og kanskje forsøke å sammenligne fremgangsmåten med de andre løsningene. Men jeg kommer ikke til å forklare alle detaljene, så hvis du vil at jeg skal utdype noe av koden ytterligere får du legge igjen en kommentar.

Litt om løsningen

I denne løsningen har jeg valgt å bruke multimethods for dispatch, dvs. for å velge hvilken strategi jeg skal bruke (les introduksjonen om du ikke vet hva programmet skal gjøre). Multimethods brukte jeg også nylig i artikkelen Template Method del 4: Multippel arv, og lengre tilbake i tid viste jeg teknikken i posten 1-2-3 Dispatch.

Jeg definerer også et par datatyper med DEFRECORD, og det er en av disse datatypene multimetodene fungerer på. I prinsippet er denne formen for dispatch det samme som jeg implementerte i Ruby og Rebol, bare at det er innbakt i språket, og at jeg dermed slipper å gjøre så mye av jobben selv.

Clojure-koden viser også litt interop med noen Java-klasser; jeg bruker java.util.Scanner til å sjekke om en streng er et tall (muligens overkill, men jeg hadde lyst til å teste dette objektet som jeg aldri før hadde benyttet).

Og så har jeg laget en aldri så liten regex table lexer til å parse CSV-filen. Geeks synes det er gøy med lexing!

Koden: Parsing av CSV-fil

Først deklarerer jeg et namespace, og inkluderer bibloteker jeg trenger i programmet:

 22 (ns polyglotis
 23     (:use clojure.contrib.json)
 24     (:require clojure.string)
 25     (:require [clojure.xml :as xml])
 26     (:import [java.util Scanner Locale]))

Og så definerer jeg datatypene jeg skal jobbe med:

 28 (defrecord OpusData [headers records])
 29 
 30 (defrecord OpusFormatResult [format data output])

Så kommer lexeren. Og dette er ganske vakkert, synes jeg selv. TOKENIZE splitter opp en semikolonseparert tekststreng ved hjelp av tre regulære uttrykk:

 32 (defn get-first-token [s]
 33   (first (or (re-seq #"^([^;\"]+)" s)    ; unqouted
 34              (re-seq #"^\"([^\"]*)\"" s) ; quoted
 35              (re-seq #"^;" s))))         ; separator
 36 
 37 (defn tokenize
 38   ([input] (tokenize input []))
 39   ([input tokens]
 40     (if-let [token (get-first-token input)]
 41       (if (= token ";")
 42         (recur (subs input 1)
 43                tokens)
 44         (recur (subs input (-> token first count))
 45                (conj tokens (second token))))
 46       tokens)))

Jeg trenger også en liten funksjon som kan splitte linjer; igjen bruker jeg regex, og sørger for å håndtere både unix og windows-format:

 48 (defn split-lines [text]
 49       (clojure.string/split text #"\r?\n"))

Nå bruker jeg alt det jeg har laget til å definere en funksjon som tar inn et filnavn, leser filen, splitter den opp i linjer, splitter linjene opp i tokens, og returnerer en OpusData-instans:

 51 (defn get-csv-data [filename]
 52   (let [data (->> filename          ; filename
 53                   slurp             ; Read the file content
 54                   split-lines       ; Split on rows/newline
 55                   (map tokenize))]  ; Split on fields
 56 
 57     ; Create record of headers and rows
 58     (OpusData. (first data) (rest data))))

Hvis jeg nå evaluerer (get-csv-data “data.csv”) i REPL’en, vil det gi følgende output (data.csv er den testfilen jeg har brukt gjennom hele denne bloggserien):

 60 ; (get-csv-data "data.csv")
 61  #:polyglotis.OpusData{ :headers ["Field 1" "Field 2" "Field 3"],
 62                         :records (["Value 1" "Value 2" "123"]
 63                                   ["Value A" "Value B" "456"]
 64                                   ["Value x" "Value y;;" "789.45"])}

Koden: Dispatch

Nå har vi kommet til multimetodene. Først definerer jeg APPLY-FORMAT. Når denne blir kalt så vil den velge en funksjon basert på :format-verdien til argumentet sitt (argumentet kommer til å være av typen OpusFormatRecord, definert tidligere):

 69 (defmulti apply-format :format)

Implementasjonen av det første konkrete formatet ser slik ut:

 71 (defmethod apply-format :yaml [csv]
 72   (assoc csv :output "YAML not yet supported!"))

YAML-metoden setter :output-feltet i csv-objektet til “YAML not yet supported”.

Da er vi klare for litt mere funky greier – her er definisjonen av XML-formatet. Begynn med å lese kommentarlinjene mot slutten av methode, og se om du kan nøste deg bakover og forstå hvordan det fungerer:

 75 (defmethod apply-format :xml [csv]
 76   (let [headers (->> csv :data :headers
 77                      (map #(.replace % \space \_)))
 78 
 79         xml-str #(with-out-str (xml/emit-element %))
 80 
 81         <tag> (fn [k v]
 82                 {:tag (if (keyword? k) k (keyword k))
 83                  :content (if (seq? v) (vec v) [v])})
 84 
 85         row-<tag> #(->> % (map <tag> headers)
 86                           (<tag> :record))]
 87 
 88     (->> csv :data :records      ; Pluck rows from CSV
 89          (map row-<tag>)         ; Create tags from them
 90          (<tag> :records)        ; Wrap in a <records> tag
 91          xml-str                 ; Convert to a string
 92          (assoc csv :output))))  ; Update output field

Clojure har ganske grei støtte for å konvertere hash-maps (disctionaries, om du foretrekker det navnet) til XML, og dette benytter jeg her.

Og da har vi bare ett format igjen, nemlig JSON:

100 (defmethod apply-format :json [csv]
101   (let [headers (-> csv :data :headers reverse)
102 
103         ; Fn: Coerse to Int or Float if possible
104         coerse-num #(let [s (Scanner. %)]
105                       (.useLocale s (Locale. "en" "US"))
106                       (cond
107                         (.hasNextInt s) (.nextInt s)
108                         (.hasNextFloat s) (.nextFloat s)
109                         :else %))
110 
111         ; Fn: For all rows, for all fields, coerse num
112         coerse-num-all (partial map
113                          (partial map coerse-num))
114 
115         ; Fn: Convert seq into map with headers as keys
116         mapify-row (comp (partial zipmap headers) reverse)
117 
118         ; Fn: Convert all seqs to maps
119         mapify-row-all (partial map mapify-row)]
120 
121     (->> csv :data :records     ; take the rows
122          coerse-num-all         ; coerse the numbers
123          mapify-row-all         ; make maps
124          json-str               ; convert maps to json
125          (assoc csv :output)))) ; update output field

Clojure har enda bedre støtte for JSON enn for XML. Igjen konverterer jeg dataene mine til hash-maps, og funksjone JSON-STR konverterer hash-maps til JSON. Dette er en generell teknikk innen funksjonell programmering: Omstrukturer dataene dine til noe som passer for det du skal løse, og så blir selve løsningen ganske enkel.

Koden: Main

Den siste funksjonen jeg definerer knytter sammen alt jeg har laget til nå. Den oppretter et OpusFormatRecord-objekt hvor dataene fra en CSV-fil mates inn vha. GET-CSV-DATA funksjonen. Jeg kaller APPLY-FORMAT, som vil kalle den riktige format-metoden, plukker resultatet og skriver det ut.

129 (defn main [out-format csv-file]
130   (->>
131       ; Create a record with CSV data and format info
132       (OpusFormatResult. (keyword out-format)
133                           (get-csv-data csv-file)
134                           nil)
135 
136        apply-format   ; Dispatch to correct format def.
137        :output        ; Pluck the output string
138        println))      ; Print it

Til slutt kaller jeg MAIN og sender inn kommandolinje-argumentene.

141 ; Kick it all off !!!
142 (main (first *command-line-args*)
143       (second *command-line-args*))

Og det var det :P

Oppsummering

Multimetoder er ideelt for denne typen dispatch mellom ulike strategier, men bortsett fra det kan jeg ikke peke på noen andre fordeler med Clojure. Annet enn at det er veldig gøy å kode Clojure da!

Da jeg implementerte dette her gikk forresten koden gjennom ganske mange refaktureringer. Selv den enkleste Clojure-funksjonen kan skrives på hundrevis av ulike måter, og det er vanskelig å bestemme seg for hva man liker best, hva som kommuniserer godt, hva som er enklest å vedlikeholde og så videre. Jeg skrev litt mer om dette problemet i Er Lisp’s fleksibilitet et problem? tidligere i år.

Nå tror jeg vi lar dette polyglotiske opuset ligge. Det har sansynligvis vært mer interessant for meg selv enn for mine lesere, men jeg håper(?) noen har satt pris på å få se noen tilnærmet fullverdige men likevel små program skrevet i diverse språk.

Hei då!

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.