torsdag 16 september 2010

Kan man sälja på vad som saknas?

Som pappaledig ägnar man en hel del tid åt filosofiska grubblerier. Då jag fjärmat mig från programmeringen i detalj har jag tänkt mer på sakers tillstånd i det större. En sak som alltid bedrövat mig inom programmering är jag då jag tycker mig funnit något genialiskt och berättar om detta för en kollega ofta bemöts av ett "Pffft" och en axelryckning. Jag har kommit fram till varför det händer mig så ofta, men tyvärr ingen riktig lösning på problemet. Dock har jag tänkt ut ett litet motexempel som kanske kan kasta lite ljus på problematiken. Så, om nu någon axelryckare skulle orka läsa detta kanske jag skulle kunna räddas från att ses som en naiv idiot.

Problemet

Då jag har min grund inom den teoretiska fysiken älskar jag att ta bort saker. Ämnet strävar efter att så koncist som möjligt formulerar en modell som avspeglar världen. Kan något exkluderas från modellen utan att den därför avspeglar världen sämre ska det bort. Är det dessutom ett element som man länge tagit för givet är viktig för modellen som visar sig överflödigt känns det på något vis än mer angenämt att kasta ut det ur modellen. Om elementet inte tillför något vill säga.
Denna strävan har lett mig till sådant jag finner expressivt, analytiskt och avskalat. Förmodligen är det helt rimligt att jag fallit för vad jag fallit för. I retrospekt förefaller det som om närapå alla de saker jag blivit begeistrad över uteslutande marknadsförs på vad de inte har. Funktionella språk har inga sidoeffekter, inga tillstånd och ingen tilldelning. Dynamiska språk har ingen typsäkerhet. CouchDB har ingen SQL och inga schematan. Git har ingen server.
Denna negativa marknadsföring har fungerat väl på mig. Jag engageras att försöka begripa fördelar med att ta bort något centralt. Jag försöker i min tur föra idéerna vidare med samma metod. Väldigt ofta bemöts jag ofta av ett ivrigt försvarande av just det jag vill ta bort. Jag får en liten föreläsning om hur mycket nytta de saker jag vill ta bort har tillfört världen och då jag faktiskt bara ansåg saken i fråga onödig, inte nödvändigtvis dålig, har jag svårt att få tillbaka ordet.
Ofta krävs det nog en hel del engagemang och funderande för att se nyttan av att ta bort något (skenbart?) användbart. Jag tar mig gärna den tiden. Jag gillar ju att ta bort. Om man inte gör det tar man sig förmodligen inte det besväret. Hur dåligt kan det vara om alla använder det? Det är lättare att avskriva idén som flamsig reduktionism och mig som dålig insatt på hur man faktiskt programmerar i verkligheten.
För fallet funktionell programmering tas problemet med att marknadsföra med vad som saknas upp i artikeln "Why functional programming matters" av John Hughes.
Som nämnt tar det lång tid att beskriva varför man vill ta bort det som tas bort i de exempel jag angav ovan. Anledningen till att det blir så fint att ta bort schemat i CouchDB beror ju på strukturen av CouchDB. Det fina är att man kan ta bort det inte att ta bort det. Därför är avsaknad av schema en dålig metod att sälja CouchDB. Det är en reklam som bara riktar sig till redan befintliga kunder.

Exemplet

För att belysa problemet har jag ett enklare exempel: Ett talat språk utan "ja" och "nej".
Vid första anblick låter detta som ett vansinnigt språk. "Ja" och "nej" används ju hela tiden och berikar ju språket tycker nog de flesta. Faktum är att språket thai inte har dessa ord. Och thai klarar sig inte bara ok utan dessa viktiga ord, det blir påtagligt mer stringent i de fall där de skulle ha använts.
Till att börja med kan jag försvara mig mot alla som semestrat i Thailand eller tittat på google translate och vet att "ja" heter "chai" (ใช่) och "nej" heter "mai" (ไม่). Jag hävdar att "chai" snarast betyder "joho" och "mai" betyder "inte" som i följande dialog:
- Är du arg?
- Jag är inte arg.
- Joho, det ser jag ju att du är.
Om man frågar på thai om en person är hungrig (หิวไหม) svarar personen inte "chai" eller "mai" utan "hungrig" (หิว) eller "inte hungrig" (ไม่หิว). D.v.s. svaret på en fråga är i regel predikatet eller det negerade predikatet. Då thai inte böjer några verb och har väldigt många enstaviga ord blir detta inte mycket jobbigare än att säga "ja" eller "nej".
Och vad är det som är så bra med det då?
Jo, svenskans "ja" och "nej" leder till en mängd komplikationer. Om man t.ex. tar frågan "Vet du om han kommer?" (รู้ไหมว่าเขามาหรือเปล่า) bringar svaret "nej" ingen klarhet i saken; vet du inte eller kommer han inte? På thai svarar man i dessa fall "vet inte" (ไม่รู้) eller "kommer inte" (ไม่มา). D.v.s. det thailändska svaret kan inte missförstås.
Ett annat exempel känner alla pendlare igen: En leende person frågar något du inte hör om den tomma platsen jämte dig. Då man inte säkert vet om hon frågat "Är platsen ledig?" eller "Är platsen upptagen?" kan man inte bara le och säga "ja" eller "nej" utan måste svara med hel mening (alternativt le inbjudande och säga något enstavigt ohörbart). Man kan faktiskt inte ens säga det lite artigare "Jodå, platsen är ledig". På thai behöver man inte höra frågan. Man kan säga "ledig" utan att ens avslöja att man inte hört frågan. Artigheten lägger man på slutet som ett "krap" (ครับ) eller "ka" (ค่ะ) om man är tjej.
Även negerade frågor klaras upp utan missförstånd på thai.
Min poäng är att något man anser vara fundamentalt kanske i själva verket ställer till en massa problem som man tror orsakas av annat. Innan jag lärde mig thai trodde jag att problemen ovan kom från dåligt formulerade frågor när det i själva verket var orden "ja" och "nej" som ställde till problemet.
Så bra kan det vara att ta bort saker.

Lösningen

Att sälja in thai som "Språket utan ja och nej" hade förmodligen fått få människor intresserade. På något vis måste man först förklara problemet med "ja" och "nej". Tyvärr tar det nästan ett helt blogginlägg att göra det för detta enklare exempel. För funktionell programmering, dynamisk programmering och de andra exemplen ovan skulle det ta åtskilliga.
Detta sätt att sälja är lite som att springa runt och dra punch lines utan att berätta skämtet. Bara de som hört skämtet tidigare skrattar. Alla andra blir irriterade. Kanske är det det som bidragit till att dessa intresseområden som säljs in på vad de saknar lätt upplevs som sekteristiska och världsfrånvända. Det är väldigt synd tycker jag. Det är ju jättebra saker man tagit bort.

En vyssningsmetod jag utvecklat

Jag kan varna redan nu att detta inlägg inte har något med programmering att göra; jag är pappaledig. Dock antar jag att många programmerare är könsmogna eller att de på annat vis kan tänkas komma i kontakt med barn som står i begrepp att somna utan att själva önska det. Om man ansvarar över just ett sådant barn kan min metod komma till användning.
Faktum är att vi programmerare, datakonsulter i synnerhet, förmodligen, mot mina tidigare fördomar, är väl rustade för att skaffa barn. Ett spädbarn, har jag märkt, har flera likheter med beställare av mjukvara. De är otydliga med de specifika kraven. De skriker och gråter vid felaktig eller utebliven leverans. De kan ofta blidkas med något helt orelaterad detalj och bortse från helheten. De vill gärna bete sig agilt genom att alltid övervaka processen. Till beställares försvar kan nog även vi leverantörer kan passas in i jämförelsen då en nybliven förälder är ganska handfallen i sin omvårdnad av barnet.
Skämt åsido har jag alltså kommit fram till en metod för att få min son Ture att somna. Upprinnelsen till idén var att jag läste i boken "Konsten att läsa tankar" av Henrik Fexeus. I den boken beskriver Fexeus hur viktigt det är att mentalt synkronisera sig med en personen vars tankar man vill påverka. En person i panik måste man tala starkt och häftigt med för att sedan kunna lugna ner densamme.
Jag har tagit Fexeus metod och lagt till en lite mer musikalisk prägel. Turligtvis är jag väldigt fascinerad av polyrytmer och lyssnar mycket på Steve Reich i vars musik man ofta hittar en massa rytmer som drar i varandra. Efter att lyssnat på Reichs musik slog det mig att Ture har en mängd olika rytmer då han ska somna men inte riktigt vill. T.ex. andning, gråt och sprattel. Då jag håller Ture i famnen söker jag avgöra vilken av dessa rytmer som är tydligast. Om han t.ex. gråter vyssar jag honom i den takten (eller halv- eller dubbeltakt om det är bekvämare). Sedan sänker jag gradvis min vyssningstakt och även intensiteten på mitt vyssande. Om man gör detta långsamt nog följer Tures gråt med och avtar även den i intensitet.
Av och till märker Ture att han lurats till lugn och börjar andas häftigare eller börjar gråta snabbare. Då anpassar jag min vyssning till Tures rytm för att sedan återigen sänka den gradvis.
Då vyssningen klingat av har Ture somnat. Inte nog med det; jag brukar efteråt känna mig lugn och harmonisk och nattningen, som ibland kan målas upp som en kamp, kan i detta fall beskrivas som en liten gemensam konsert. På sätt och vis är ju ritualen litet av ett musikaliskt utbyte. En öm tapto.

måndag 1 februari 2010

Clojure and monads

Edit: In order to make this post at least slightly comprehensible I reedited great parts of it since my first try.
Disclaimer: Since this post is based on Jim Duey's great collection of articles on monads in Clojure and is heavily inspired by this great lecture by Dr. Erik Meijer I write this post in English.

Introduction

I have for some time been fascinated by monads but haven't managed to get my head around them. After experimenting some on a recursive descent parser using monads my head is at least getting in some kind of reasonably stable orbit around monads. In this post I am working with one monad, or really a combination of two monads: The state monad and the maybe monad. There are lots of other monads, but I will only cover this combined monad.
This monad can be used to take care of much infrastructure of the parsing. Here a Parser is defined as a function that takes a string as single argument and returns either a pair containing the parsed result and the rest of the string or nil if it cannot parse the content. Say we want a number-parser it has to have the following results:
(number-parser "123abc456") => (123 "abc456")
(number-parser "abc123456") => nil
The infrastructure referred to above is that we can construct parsers being combinations of other parsers. That type of combination will be the task of the domonad. Say we have a number parser and a plus sign parser which tries to find a single "+". Then we can make a simple addition parser:
(def addition-parser
(domonad
[first-term number-parser
plus-sign plus-parser
rest-terms addition-parser]
(+ first-term rest-terms)))
The left hand side stuff in the first argument to domonad are the results from the parsers on the right hand side. The second argument is simply an expression with the results. Note that the first-term is the result of the number-parser, not the parser itself!
(addition-parser "1+2+3abc456") => (6 "abc456")
(number-parser "1+2+abc123456") => nil
So, the monads do quite a lot for us: They store the parsed values (that's the state-monad) and it gracefully exits and return nil if any of its components are nil (that's the maybe-monad). The nice thing now is that the domonad can combine both parsers we have written ourself and parsers created with the domonad function.
A second way to combine parsers is to have a fallback. Say we want to parse a number or a variable if it is not a number. Then we can create the parser
(def number-or-variable-parser (m-plus number-parser variable-parser))
The m-plus is provided by the monad framework.

What I did

To understand how to build a parser from Duey's recipies I decided to make a calculator parser. Firstly I followed Dr. Meijers methods as closely as I could (they are in Haskel) but I ran into problems when I added the minus operator and the division operator. Dr. Meijer calculates sum as usual in recursion, by adding the first element with the sum of the rest: a+b+c+d => a+(b+(c+d)) Adding also minus to this we run into problems: a-b+c+d => a-(b+(c+d))=a-b-c-d (and the same for multiplication and division) which is not what we want. I spent one night trying to figure out how to expand recursively to a+b+c+d => ((a+b)+c)+d in order for minus to work. Unfortunately this provided me neither with sleep nor result. If you know, please tell me how to do that elegantly!

I cheated a little and wrote it non-recursivelly so perhaps it is only a semi-recursive descent parser. What I did was that for a+b+c+d I took the first a and applied the functions (+b, +c, +d) to it.

It is probably easiest to show the code and explain it to them who bothers to scroll down past it:
(ns com.yourcompany.monad-test
(:use clojure.contrib.monads)
(:use clojure.contrib.str-utils))

(with-monad (state-t maybe-m)

(defn optional [parser]
(m-plus parser (m-result nil)))

(def one-or-more)

(defn none-or-more [parser]
(optional (one-or-more parser)))

(defn one-or-more [parser]
(domonad
[a parser
as (none-or-more parser)]
(cons a as)))

(defn is-match [pattern]
"Creates a parser that takes what matches the regex pattern"
(let [re (re-pattern (str "^\\s*(" pattern ")"))]
(fn [strn]
(let [[a b] (re-find re strn)]
(if a
(list b (. strn (substring (count a))))
nil)))))

(defn is-one-of [& strs]
"Creates a parser that takes one of the strings given"
(is-match (str-join "|" (map #(str "\\Q" %1 "\\E") strs))))

(defn signed [parser]
"Flips the sign of parsed value if it is prefixed with a minus sign"
(domonad
[sign (optional (is-one-of "-"))
number parser]
(if sign (- number) number)))

(def parse-number
(domonad
[n (is-match "\\d+(\\.\\d+)?")]
(Double/parseDouble n)))

(def parse-expr)

(defn end [b]
"Returns a closing bracket or nil."
((apply hash-map (map str (seq "(){}[]"))) b))

(def parse-atom
(m-plus
parse-number
(domonad
[lb (is-one-of "(" "{" "[")
r parse-expr
rb (is-one-of (end lb))]
r)))

(defn extract [opss bottom-parser]
(let [[ops & inner-ops] opss
inner-parser (if inner-ops
(extract inner-ops bottom-parser)
bottom-parser)]
(domonad
[f (signed inner-parser)
t (none-or-more
(domonad
[op (apply is-one-of (keys ops))
e inner-parser]
#((ops op) % e)))]
(if (empty? t) f ((apply comp (reverse t)) f)))))

(def parse-expr
(extract [{"+" + "-" -}
{"*" * "/" / "%" mod "\\" quot}
{"^" #(Math/pow %1 %2)}]
parse-atom))

(defn calculate [strn]
(let [r (parse-expr strn)]
(if r (first r) "Error"))))
Which works as desired:
(calculate "-(- 21.66)+[2^(2*3-{{{ { 4 } }}})]/3") => 22.993333333333332
The functions not commented or explained in Duey's tutorials are:
parse-atom: parses the smalest part of the expressions. I.e. a number or a new expression within brackets. And yes, atom is a bad name for it.
extract: a poorly named function that costructs a parser parsing smaller and smaller parts depending of the operators order: expression to terms (+, -), to factors (*, /), to parts in a power expression (^). When there are no sub-parts available, parse the atoms.
parse-expr: utilizes the extract function to render a parser for any expression.
calculate: parses the expression and returns result or error.

Note that the parser deals with a few special cases which makes the code a little less tractable:
  • leading negative terms: Ex: -2+3
  • any kind of matching brackets (), {}, []
  • easy to add functions and orders of execution
  • spaces