Kalenderluke 10: Litt Lisp (oh no!)


onsdag 11. desember 2013 Julekalender

Luke 10 i årets julekalender inneholdt noen få linjer Common Lisp, en bug, og et spørsmål om hvilket output koden hadde skrevet ut om den hadde fungert. Til å dreie seg om et språk som svært få utviklere behersker, synes jeg mange klarte seg bra.

luke10_knut

I denne posten vil jeg gi noen tips til hvordan jeg tenker man burde gått frem for å løse oppgaven.

Buggen

Jeg hadde introdusert en bug i koden. Jeg hadde kun fjernet ett tegn, og dette tegnet hadde ingen stor betydning for forståelsen av koden, men skulle sørge for at man ikke bare kunne poppe koden inn i en "try Common Lisp online"-compilator og få frem svaret uten å måtte tenke selv.

Når buggen er fikset ser koden slik ut – tegnet som manglet er markert:

(defun xmas (&rest args)
  (format t "~{~a~#[~; and ~:;, ~]~}!" args))

(apply #'xmas (loop for i upto 3 collect "Ho"))

Målet mitt var aldri at utviklere uten Lisp-erfaring skulle finne buggen for å løse oppgaven. Den beste strategien her er etter min mening å forsøke å forstå koden.

En funksjon

Hvis man vet noe som helst om Lisp – eller bruker litt fantasi – så ser man at de to første linjene definerer en funksjon (defun), og at denne heter xmas. Det som følger i paranteser etter navnet må være argumentene. Det funksjonen gjør, som er det sentrale her, finner vi altså i linje 2.

Format

Koden kaller en funksjon som heter format. Dermed er det viktig å finne ut hvordan den virker. Man kan gjette seg til at den formaterer en streng på en eller annen måte – de fleste språk har en eller flere sånne funksjoner. Første steg bør da være å finne dokumentasjonen til format.

Man kunne også forsøkt å google formatstrengen som sendes inn som andre parameter i format-kallet. Det kan hende det kan gi deg noe, men jeg tror jeg brakk google da jeg forsøkte: Treffene jeg fikk omhandlet alt annet enn Common Lisp (Forskjellen mellom Vest- og Øst-Polen, forskjellen mellom Shari'a og vestens lov-tradisjon, og Raspberry Pi).

Formatstrengen inneholder faktisk noe så komplekst som et domenespesifikt språk for formatering – like vanskelig å forstå, men ikke så vanlig, som regulære uttrykk. Man kan selvfølgelig klare å gjette seg til hva den gjør – og noen gjorde kanskje det – men hvis ikke vil en titt på dokumentasjonen kunne forklare mye...

...som at formatstrengen kan iterere over lister. Og det er det som skjer her. Det bygges opp en streng av inneholdet i listen args, og alle elementene bortsett fra de to siste joines sammen med separatoren ", ". Mellom de to siste elementene derimot brukes separatoren " and ". (format t "~{~a~#[~; and ~:;, ~]~}" '("a" "b" "c"))) ville dermed gi strengen "a, b and c".

Lenker: Formater, ikke konkatener (min blogpost fra 2011) | Commen Lisp HyperSpec: Formatted Output

Ikke glem utropstegnet

Det siste tegnet i formatstrengen hadde derimot ikke noe med iterasjonen å gjøre.., det la jeg bare til som en liten felle. Og mange gikk i den :) (format t "~{~a~#[~; and ~:;, ~]~}!" '("a" "b" "c"))) gir strengen "a, b and c!".

Apply

Vi har kommet til siste linje. Den begynner med (apply #'xmas ... , og selv om man ikke google apply-funksjonen så kan man gjette seg til at dette kaller funksjonen xmas. Men det vi lurer på er hva argumentene til xmas er, for da har vi løsningen.

Loop

Common Lisp's loop-makro er nesten et helt lite språk i seg selv, og brukes her til å produsere en liste. for i upto 3 sier at vi skal loope' fra 0 (default start) og helt opp til og med 3. Mange hadde nesten løsningen, men fikk ikke med seg at "upto" inkluderer 3 (eventuelt trodde de at man startet på 1).

For hver iterasjon skal vi collecte strengen "Ho". Da står vi igjen med listen ("Ho" "Ho" "Ho" "Ho").

Løsningen på luke 10 er dermed "Ho, Ho, Ho and Ho!".

Lenker: Common Lisp HyperSpec: The LOOP Facility

Hvem var raskest?

Raskeste utvikler på luke 10 var Henrik Grotle (PSWinCom), som leverte riktig svar på 4 minutter og 29 sekunder. Han har aldri kodet en linje Lisp i sitt liv, men er flink til å google :)

Magnar Sveen kom på fjerdeplass, og tok dermed tilbake ledelsen sammenlagt.


comments powered by Disqus