Kurs på Coursera om Scala

Jag tar den, kul kurs än så länge!

På en höft verkar den handla ungefär lika mycket om generell funktionell programmering som Scala. Jag tror säkert att man kan ha nytta av det man lär sig i andra språk, men huvudvikten och syntax ligger naturligtvis på Scala.

Man ges en god inledning i kursen. Det finns tutorials för installation av mjukvara, hur man lämnar in uppgifter, support av Coursera-plattformen och så vidare. Mötet med Scala sker lite för hastigt, och om man inte har så mycket tidigare erfarenhet av programmering kan det vara svårt att hänga med. Det märks även att Martin Odersky i första hand är akademiker; han är pedagogisk och väldigt kunnig, men aningen.. torr. Jag har iofs sett andra talks med honom där han har mer gnista.

Gillar man sånt här bör man hursomhelst ta sig en koll, även om man inte är insatt i Scala.

Var tvungen att kolla in denna kurs jag också Har redan läst "Programming in Scala" av Martin Odersky, så det borde ju vara hyfsat lätt ett tag...

Men han försökte verkligen slå knut på sig själv när han skulle ge exempel på vilka språk som är funktionella. Med den definition han gav, funktioner ska vara första ordningens objekt, så är även C++ (nya standarden) och senaste versionen av Objective C också funktionella språk...

De flesta puritaner inom funktionella språk brukar peka på "pattern matching" (av funktionsargument) som den avgörande finessen som ett "riktigt" funktionell språk måste ha, men då faller ju allt utom Haskell, ML, Ocaml, F# och Erlang bort från hans lista så det fungerar ju inte när han vill pusha för Scala

Sedan gjorde han missen som nästan alla som pushar för funktionella språk gör: hävdar att funktionella språk är väldigt bra för "parallel programming" vilket är helt fel då de flesta funktionella språk suger på detta jämfört med t.ex. C. Däremot är språk som använder immutable data, vilket i princip alla funktionella språk gör som förval, väldigt bra för "concurrent programming".

Parallel programming = effektivt utnyttja flera CPU-kärnor för att snabbare lösa ett givet problem
Concurrent programming = ett sätt att konstruera sitt program genom att ha flera samtida aktiviteter som helt eller delvis kan köra oberoende av varandra

Sådana här kurser brukar definitivt vara värd tiden det tar att gå igenom dem, även om man har hyfsad koll på språket / problem-domänen redan innan, då man alltid snappar upp saker man inte sett eller tänkt på tidigare. Så tack för länken!

Jag tycker han gör distinktionen ganska klar mellan (vad han anser vara) pure functional programming och andra varianter. CLisp saknar så vitt jag vet stöd för pattern matching, så vad tillhör det egentligen för paradigm om det inte är funktionellt?

Som han säger menar vissa andra att ett rent funktionellt språk helt saknar state, vilket skulle plocka bort bland annat Erlang och ML-baserade språk. (Scala har förresten pattern matching som verkar vara på F#-nivå ungefär; jag är tyvärr alldeles för dåligt insatt för att kunna svara med säkerhet.)

Det han vill framhäva är en funktionell programmeringsmetodik där metoder/funktioner returnerar värden utan sideffekter, enligt regeln a + (b + c) == (a + b) + c, vilket går att göra i näst intill alla språk jag känner till. Det är däremot ovanligt att se Java- eller C#-program utan objekt som initieras och sedan matas med data genom olika ingrepp och metoder, innan de skickas vidare.

Funktionell programmering — inte nödvändigtvis funktionella språk, viktig distinktion — är bra för parallel programmering. Mitt senaste inlägg i Progblemet #1 delar en datastruktur mellan flera trådar för att räkna ut ett singulärt slutgiltigt värde, det är väl just det som utgör själva grundtanken med parallella beräkningar? Att kunna garantera att rådatan inte ändras mellan trådarna (sans reflection....) är en förutsättning för detta.

Common lisp är ett multi-paradigm språk. Faktum är att många undrar varför Lisp alltid ses som främst ett funktionellt språk, det finns varianter som trycker på de funktionella bitarna (som Scheme), men mutable-state, for/while loopar och liknande helt normalt i Lisp. Clojure trycker väldigt hårt på immutable data, men det är helt normalt att blanda sådan kod med anrop som gör sidoeffekter. Min gissning är att Lisp var en av de första, kanske det första, språk som hade stöd för anonyma funktioner.

Jag som är för dålig på F# och Ocaml, trodde dessa var mer lik ML än vad de är.
Precis, Scala en pattern matching liknande den i F# men tack vare Scalas Extractors skulle jag nog säga att Scala är mer kraftfullt på den punkten än F#. Vad dessa språk saknar är att skriva funktionsdefinition direkt enligt den matematiska definitionen

Definitionen för Fibonacci serien är

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) ; för alla positiva n

I språk som Erlang och Haskell skriva dessa funktioner exakt enligt denna definition
Erlang

F(0) -> 0;
F(1) -> 1;
F(n) when n > 0 -> F(n-1) + F(n-2).

vilket enligt puritanerna är väldigt viktigt. Notera att jag definitivt inte är en puritan vad det gäller funktionell programmering. Jag anser att funktionell programmering är ett sätt att strukturera sitt program och man man programmera funktionellt i princip alla språk. Kör man med gcc kan man även markera sina funktioner som pure (vilket här betyder: beror bara på sina argument och läser eventuellt, men skriver ej, globalt data) eller som const (resultatet beror BARA på argumenten). Gör man den markeringen så kan kompilator göra en mer aggressiv optimering i vissa fall.

Visst, håller helt med om den matematiska definitionen. Men tycker han villade bort sig lite när skulle sedan förklara hur det gör vissa språk mer funktionella än andra då det är fullt möjligt att skriva funktioner, i den matematiska termen, i princip alla språk.

Ditt senaste inlägg tycker jag visar precis den poäng jag vill göra: immutable data gör det enkelt att dela upp program i bitar som kör samtidigt, en form av "concurrent program", men det betyder inte att det är en teknik som lämpar sig för "parallel programming".

Tog Scala-programmet och körde beräkningen 10 gånger per tidsmätning och mätte sedan tiden 10 gånger så JIT:en lugnat ner sig.

Här är mitt rå-data

Scala
orginal
3.4s

.view
3.1s

.par
1/1: 5.8s x0.6
1/2: 3.7s x0.9
2/1: 3.0s x1.1
3/1: 2.2s x1.5
4/1: 1.7s x2.0
4/2: 1.2s x2.8

C
orginal
2.1s

OpenMP
1/1: 2.2s  x1.0
1/2: 1.4s  x1.5
2/1: 1.1s  x1.9
3/1: 0.74s x2.8
4/1: 0.57s x3.7
4/2: 0.38s x5.5

1/1 betyder 1 CPU-kärna 1 HT
1/2 betyder 1 CPU-kärna 2 HT
2/1 betyder 2 CPU-kärnor 1 HT
...

"orginal" är det ursprungliga enkeltrådade programmet. Lade även in varianten med ".view" som ökade prestanda något, men använde originalet som utgångspunkt. Kolla in overhead:en att gå från ett "vanligt" program till ett program som har möjligheten att utnyttja flera CPU-kärnor. C (OpenMP) totalt demolerar Scala här. C programmet är marginellt långsammare på en CPU-kärna, Scala programmet nära nog halverar hastigheten.

Så i slutändan så får C programmet en boost på en faktor 5.5 att gå från det enkeltrådade programmet till versionen som kan använda flera kärnor körandes på alla 4 kärnor och båda HT medan Scala bara får en ökning på en faktor 2.8 (men den använder 100% av alla trådar!!!). Tittar man BARA på hur Scala skalar i det program som kan använda flera kärnor så ser det väldigt fint ut, men om man ger sig på denna typ av optimeringar så vill man pressa maximalt ut ur systemet och då ska man jämföra med det ursprungliga programmet då detta faktiskt lämnar de övriga 7 CPU-trådarna lediga som då skulle kunna användas till andra saker.

Det är verkligen en bra kurs, ska definitivt testa på fler kurser på den sidan!

Men tycker ändå att det är lite skrämmande att sättet man uppmuntrar att man ska lösa 2:a veckans uppgifter dels innehåller minnesläckor (tänk hur detta set är implementerat så inser du att union, intersect, diff och filter alla bara allokerar mer och mer minne så länge man applicerar dessa på samma set) och dels har horribel tidskomplexitet för ett set O(N), normalt är O(log(N)) för alla operationer alt. O(1) för normalfallet och O(N) i undantagsfall för insättning/borttagning.

Tänk bara vad som händer om du tar din implementation av union(s: Set, t: Set): Set och gör följande

  test("horrible implementation") {
    var s = singletonSet(0)
    for (i <- 1 to 10000)
    	s = union(s, singletonSet(i))
    assert(contains(s, 10))
    assert(!contains(s, -1))
  }

Detta kommer krascha p.g.a stack overflow.

Det positiva man kan säga om FunSets är man verkligen kan ta den matematiska definitionen an union, intersection samt diff och bara skriva den rakt upp och ner som kod, det är riktigt snyggt.