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.

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

En första clojure-betraktelse

Jag har börjat kika på Clojure och blir alldeles tagen. Jag har tittat på LISP och lambdakalkyl tidigare och blivit begeistrad över skönheten men bedrövad över att jag inte skulle kunna få något gjort med det. Det verkar vara annorlunda med Clojure. Trots att det tillåter vacker struktur och ren logik är det användbart.

För er som inte vet det är Clojure en LISP-dialekt som lever i en JVM. Det är utvecklat för att vara funktionellt och ha stöd för samtidighet och parallellisering. Dessutom är det designat för att friktionsfritt kunna kommunicera med Java. Det finns mängder av blogartiklar som förklarar grunderna och flera bra inspelade föredrag av skaparen Rich Hickey. Om du inte känner till Clojure, kolla upp det!

Jag har tänkt att prova Clojure och vill kunna göra fler uppdateringar på en datastruktur. Var ändring skulle beskrivas med en path och en ändringsfunktion eller ett nytt värde. Kanske finns exakt vad jag behöver i clojure.contrib men jag ville prova själv.

Sagt och gjort. Så här blev funktionen:

(defn multi-update
  ([coll path update]
    (if (empty? path)
      (if (fn? update) (update coll) update)
      (assoc coll (first path)
        (multi-update (coll (first path)) (rest path) update))))
  ([coll path update & more]
    (apply multi-update (cons (multi-update coll path update) more))))

Funktionen anropas som följer:

(multi-update {:a 12 :b {:c [1 2 3]}}
  [:a] inc
  [:b :c 0] "Hupp"
  [:b :c 1] inc)

Precis som önskat ger den: {:a 13 :b {:c ["Hupp" 3 3]}}. Det inc som skickas in är en funktion som ökar argumentet med ett.

I funktionalistisk anda löses problemet med rekursion. Om man anropar funtionen med bara data, path och update gör den följande:

Om path är tom har hittat elementet som ska uppdateras. Den ersätter värdet (coll) med (update coll) om update är en funktion och med update i annat fall.

Om path har element kvar arbetar den sig ner genom att ersätta datans element som svarar mot första nyckeln i path och ersätter det uppdaterat med resten av path.

Om funktionen anropas med coll, path, update och mer ropar den på sig själv med den uppdaterade informationen (multi-update coll path update) och de resterande argumenten.

Allt detta kanske låter bökigt men hela problemet är faktiskt ganska komplicerat. Hade samma problem lösts traditionellt objektorienterat hade en mängd klasser behövts för att klara av typsäkerheten (BaseNode, MapNode, ListNode, ValueNode, Path, BaseUpdate, SetUpdate och LambdaUpdate). Dessa nodklasser skulle ha var sin metod Update(Path path, Update update) som skulle innehålla den faktiska koden som gjorde något. Grymt mycket boiler plate-kod. Otypat skulle man kunna göra en rekursiv static-metod som jobbar på Dictionary<object, object> och List<object>, men den hade inte varit så särdeles elegant eller användbart.

Den objektorienterade varianten skulle dessutom få välja mellan att ändra hela listan eller kopiera hela listan. En ändring hade varit helt omöjligt att backa, att kopiera allt ett enormt resursslöseri. I Clojure-fallet får man ett nytt objekt men bara de ändrade noderna måste kopieras. De oförändrade noderna refereras till då de ju ändå aldrig kan ändras. Allt detta sköter Clojure om i bakgrunden.

Clojure vinner på alla fronter!

En liten funtionell reflektion

Första gången jag såg yield return i C# tyckte jag att det var lite larvigt. Nu har jag provat det lite grann och kommit på att jag gillar det. Det fina är att man nu kan använda Linqs extensions till IEnumerable till att göra saker riktigt funktionellt. Man kan använda IEnumerable till exekveringslogik på ett sätt man inte kunde tidigare.

Låt säga att man vill sortera kommaseparerade ord givna i konsolen. I traditionell C# något i stil med:

static void Main(string[] args)
{
  var elements = new List();
  string input;
  while (!string.IsNullOrEmpty(input = GetInput()))
     foreach (var element in input.Split(','))
        elements.Add(element.Trim());
  elements.Sort();
  Console.WriteLine(string.Join(", ", elements.ToArray()));
  Console.Read();
}

static string GetInput()
{
  Console.Write("Input: ");
  return Console.ReadLine();
}

Detta är lättläst i den bemärkelse att man är van vid det. Det är så man alltid skrivit. Problemet med denna kod är att man i detalj får ange hur man ska göra saker. En lista ska skapas, vi stegar igenom var inmatning tills den är tom... osv. Koden är imperativ om man så vill.

En helt annan angreppspunkt som gör exakt samma sak är denna:

static void Main(string[] args)
{
Console.WriteLine(string.Join(", ",
                 Inputs().
                 TakeWhile(s => !string.IsNullOrEmpty(s)).
                 SelectMany(s => s.Split(',')).
                 Select(s => s.Trim()).
                 OrderBy(s => s).
                 ToArray()));
Console.Read();
}

static IEnumerable Inputs()
{
  while (true)
     yield return GetInput();
}

static string GetInput()
{
  Console.Write("Input: ");
  return Console.ReadLine();
}

Sådärja, inte nog med att koden blev obegriplig, det blev fler rader. Vad har vi vunnit på detta?

Till att börja med kan jag förklara vad som händer. Funktionen Inputs() kommer att generera en oändlig uppräkning av inmatade strängar. TakeWhile(...) kommer att ta dessa strängar tills någon är tom. SelectMany(...) delar upp var inmatning efter kommatecken. Select(...) skalar bort mellanslag i vart element. OrderBy(...) sorterar alla element. Resten av logiken finns är i princip identisk med foreach-varianten ovan.

Återigen: Vad har vi vunnit? För att nämna några saker:

1. Koden beskriver vad som ska göras mer än hur. Vi ber om alla inmatningar fram till den första tomma; dessa vill vi ha uppdelade, trimmade och sorterade. Vi säger inget om hur detta ska göras.
2. Alla operationer vi gör är i princip lika; de är filter i en filterkedja. Att logiken för att avsluta vid tom inmatning och logiken för att dela upp var inmatning i kommaseparerade element har en så påfallande lik struktur syns inte alls i foreach-exemplet.
3. Inga lokala variabler behövs. Vi behöver inte spara någon variabel för att samla i en lista eller lagra inmatning. Detta gör var rad isolerad i betydelse. Ingen logik är spridd över hela beskrivningen (som listan element som initieras, fylles och presenteras).
4. Koden blir mer återanvändbar. Man kan bryta ut en funktion som tar en IEnumerable som filtrerar som ovan så att f(Inputs()) ger vårt resultat men även f(textFile.GetRows()) skulle fungera. Detta skulle vara knöligt i foreach-fallet.
5. Den senare lösningen är enormt mycket mer kraftfull vad gäller utökningar av logiken. Detta visar jag i några exempel nedan.

Låt säga att vi vill ta bara 5 inmatade rader (om inte användaren matat in en tom rad dessförinnan). I foreach-fallet skulle vi behöva definiera en räknare som avbryter while-loopen. Låt oss säga att vi dessutom bara vill ha totalt 25 inmatade element (var rad kan ha fler element). I foreach-fallet får vi då se till storleken på elements och avbryta while-loopen. I det senare fallet betyder det att vi vill ta 5 respektive 25 element ur kedjan. På engelska och i C# heter detta Take(5) respektive Take(25). Se koden nedan för var de ska in i kedjan. Även om man skulle vilja ta max 8 element per rad kan detta göras med en Take(8) på rätt ställe.

Ett annat exempel är att man kanske vill gruppera alla inmatade ord efter deras längd. I foreach-fallet skulle vi förmodligen tvingas skapa en ny klass för att samla på sig den logiken. De extrafunktioner man får från Linq gör att det inte behövs i det senare fallet. Denna kod gör just detta:

Console.WriteLine(string.Join(", ",
            Inputs().
            Take(5).
            TakeWhile(s => !string.IsNullOrEmpty(s)).
            SelectMany(s => s.Split(',')).
            Take(25).
            Select(s => s.Trim()).
            GroupBy(s => s.Length).
            OrderBy(p => p.Key).
            Select(p => p.Key + ": " + string.Join(", ", p.OrderBy(s => s).ToArray())).
            ToArray()));

Min gissning är att den logiken skulle bli synnerligen besvärlig i foreach-fallet. Om du orkar och kan göra det smidigt kan du gärna klippa in koden i en kommentar.

Varför ska du också blogga, Martin?

I mitt förra förvärv forskade jag i fysik. Trots det bad somliga personer mig förklara vad jag forskade om. Jag hade en liten, muntlig, snabb prototyppresentation som jag ganska snabbt tröttnade på. Efter att ha skrivit ned den (Kapitel ett i denna PDF om du är nyfiken på strängteori) kunde jag hänvisa dit. Det var skönt.

Nu har jag programmerat tillräckligt länge för att ha reflektioner över detta och tänkte ha samma strategi igen. Om jag berättar samma sak för fler personer än tre ska jag försöka skriva ett inlägg om det.