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.

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 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.