Presentation of GetTogether on Functional Programming

Functional Programming Putting the fun in programming At least I think so Kris.Aerts@kuleuven.be

Me, Myself & Functional Programming • 1991: Prolog • 1992: sociology in LLN • 1993: Haskell • 1994: paper of Hudak • 1999: paper Games provide fun(ctional programming • tasks) in Functional and declarative programming in education, FDPE’99 • 2001: finished my PhD and started at KHLim Diepenbeek • Teaching ICT in master in industrial sciences (ing.) o Capable in Java, not so much in .NET o Bit of functional programming in master 2/72

Hudak’s Paper • Experiment in 1994 3/72

A Military Radar System Prototyped 4/72

Research in Functional Programming • Dia van Tom’s inaugurale • Lisp: 1958 • Haskell: • Erlang • Common Lisp: 1e ANSI gestandaardiseerde taal met OO + FP 7/72

Key Challenges Programming Languages Computer Science Society More Software More Software Agoria: ’9300 unfilled ICT positions'Agoria: ’9300 unfilled ICT positions' ProductivityProductivity ReliabilityReliability ANP: ‘Software bugs cost 1.6 billion € a year’ ANP: ‘Software bugs cost 1.6 billion € a year’ Bug-Free Software Bug-Free Software

Meeting the Challenges Incremental Research Mainstream languages Fundamental Research A different approach to languages Mainstream languages

Historical Evolution imperative languages object orientation mathematics hardware mainstream alternative declarative languages 1 1953 Fortran 1958 Cobol 1969 CAlgol 1959 1971 Smalltalk Eiffel 19851983 C++

Declarative Languages Functional Programming Haskell Logic Programming Prolog Constraint Programming MiniZinc

Recent Developments imperative languages object orientation mathematics hardware mainstream declarative languages research

Anonymous Functions λ calculus 1936 Alonzo Church 1958 Lisp John McCarthy 1973 ML Robin Milner 1987 Haskell Haskell Committee 2014 Java 8 Swift 2011 C++11 Functional Languages Mainstream 2007 C#

Early Adopters Haskell Language + GHC CompilerHaskell Language + GHC Compiler Finance Many OthersTelecom

Productivy and Functional Programmin • http://simontylercousins.net/does-the-language-you-use- make-a-difference-revisited/ • The problem 17/72

Rest of the presentation • Some concepts of Functional Programming o With examples in Haskell, F# and C# 23/72

Declarative Programming What • Derivation from ‘input’- values to ‘output’-values • Or expressing properties o Often mathematically sound • (but still fun to do ;-) • Intelligent execution o verifiable How • What machine to use • When to use which features of machine • What steps to set • Programmer considered intelligent o Mostly not verifiable Describing the what instead of the how 24

Declarative Programming What • SQL • Linq (mostly) • Logic Programming o Constraint Programming • Functional Programming Different mindset! How • Imperative programming • Manipulation of v ariables • What machine to use o von Neumann architecture • When to use which features of machine o Variables = registers • What steps to set o Order of execution o Outer loops (for, while) Examples = Statements= Expressions 25

Logic Programming = Prolog (1a) ancestor(x,y) :- parent(x,y). ancestor(x,y) :- ancestor(x,z), parent(z,y). femaleAncestor(x,y) :- ancestor(x,y), female(x). ?- femaleAncestor(Kris,Lars). => no ?- femaleAncestor(Celine,Lars). => yes ?- femaleAncestor(x,Lars). => Celine, Liesbet 26/72

Logic Programming = Prolog (1b) female(Celine). female(Liesbet). female(Hanne). male(Kris). male(Lars). parent(Celine,Kris). parent(Kris,Lars). parent(Liesbet,Lars). 27/72

Logic Programming = Prolog (2) evenNumber([]). even([_,_|T]):- evenNumber(T). palindrome(L):- reverse(L,L). reverse([],[]). reverse([H|T],R):- reverse(T,T1),append(T1,[H],R). 28/72

(Pure) Functional Programming • Much closer to “real” programming o Logic Programming = (partial) instantation = more magic o Functional Programming • functions with parameters returning values • Much like functions and/or methodes • But o No side effects • Referential transparency • An expression is a value with always the same value • “no (hidden or far distant) state messing with things” • Strongly typed with type inference o “Strongly typed programs can’t go wrong” • Polymorf: a function can have many types 29/72

Lambda calculus • Each expression has a never-changing-value o z = 18 o y = sin(z) • Complex expressions are calculated by evaluating and substituting subexpressions o (z + sin(z))*(y+cos(y)) • Function calls behave exactly the same o Always call by value o Always return value o No pointer- or out variables 30/72

Lambda Calculus (2) • f x = g(3+x)+x • g y = y+1 • z = 5 • f z + g z 31/72

How to express new state? • Never o No mutable variables! (in pure FP-languages) • in general no side effects o Confusing for imperative programmers • F# allows for explicit declaration of mutable variables • C# allows for explicit declaration of readonly (instance) variables • But actually always o A new state is a new value • May be stored explicitly in a variable • Or may be stored temporarily in memory 32/72

Explicit new values! let y = a + b yPlus1 = y + 1 f x = (x+y)/yPlus1 in f a + f b No confusion between x++ and ++x etc. 33/72

Advantages of having no mutable variables • Referential transparancy o A reference always refers to the same value o Mathematically sound • Implicit parallellism o Order of execution can be chosen, both at compile and run time o Synchronisation: locking issues when dependencies • Formal reasoning o Automated correctness and equivalence proofs o More transparant code o No underlying dependency from mutable states 34/72

Side Effects Traditional Mainstream Languages Oops, unexpected interference Oops, unexpected interference

No Side Effects Traditional Declarative Languages No Side-Effects, No Problem Traditional Mainstream Languages No Side-Effects, No Party Mathematical Elegance Predictable No Interference ✓ ✓ ✓

Explicit Side Effects State-of-the-Art Declarative Languages Explicit Side-Effects, No Problem Mathematical Elegance Predictable Explicit Interference ✓ ✓ ✓

How to return many values? • Imperative programs o Return 1 value from function o And others as ‘out’ parameters (using call by reference) • OO programs using only call by value o Define a container class for each combination of types o Cumbersome… • FP-languages use tuples (x,y) , (x,y,z) , (a,b,c,d), … o Flexible in number of elements o Flexible in composing types 38/72

Recursion = “looping” (1) From definition to code n! = n*(n-1)! With base case 1! = 1 • Haskell o fac 1 = 1 o fac n = n * fac (n-1) • Non-recursive C# public long fac(int n) { long value = 1; for (int i=2; i<=n; n++) { value = value * i; } return value ; } 39

Recursion = “looping” (2) From definition to code n! = n*(n-1)! With base case 1! = 1 • F# let rec fact x = if x < 1 then 1 else x * fact (x - 1) • Recursive C# public long fac(int n) { if (n==1) return 1; return n * fac (n-1); } 40

Recursion = “looping” (3) StackOverFlow error? •“Real” functional languages use more optimisation techniques for recursive programs • F# let rec fact x = if x < 1 then 1 else x * fact (x - 1) • Recursive C# public BigInteger fac(int n) { if (n==1) return 1; return n * fac (n-1); } 41

Tail recursion Taking care of useless stack frames • Haskell fac n = fac’ n 1 fac‘ 1 acc = acc fac‘ n acc = fac’ (n-1) (n*acc) • F# let fac n = facT n 1 let rec facT n acc = if n = 1 then acc else facT (n-1) (n*acc) 42

Tail recursion (2) Taking care of useless stack frames • C# BigInteger Factorial(int n, BigInteger product) { if (n < 2) return product; return Factorial(n - 1, n * product); } 43

Exercises in my master class ;-) 1. Hermite sum 1/n + 1/(n-1)+…1/2+1/1 2. Mysterious function (presumption of Fermat) o Reduce n to1 with the following steps • Odd n => continue with 3n+1 • Even n => continue with n/2 1. Calculate numberOfDivisors and isPriem 44/72

Solutions in Haskell herm 1 = 1 herm n = 1/n + (herm (n-1)) myst 1 = [1] myst n | mod n 2 == 0 = n:(myst (div n 2)) | otherwise = n:(myst (3*n+1)) numberOfDivisors … isPrime n = (numberOfDivisors n) == 2 45/72

Recursive Programming: conclusion • Not exclusively for functional programming • But very typical for FP o And efficient • Interesting pattern also for non FP-languages! 46/72

Lists in Functional Programming • Omnipresent feature o In most languages o But very strong support in FP • Especially when combined with pattern matching • And recursive programming • Remember basic concept of recursion: 1. Define primitive/base expression(s) 2. Reduce complex expression to more simple expression • N reduces to n-1, n/2, … • List reduces to list with fewer elements 47/72

Pattern matching in Haskell fac 1 = 1 fac n = n * fac (n-1) findValue [] y = False findValue (x:xs) y = if x == y then True else findValue xs y evenElems [] = True evenElems [x] = False evenElems (x:y:ys) = evenElems ys 48/72

Pattern matching in F# findValue [] y = False findValue (x:xs) y = if x == y then True else findValue xs y let rec findValue list x = match list with | [] -> False | y::ys -> if x == y then True else findValue x ys 49/72

Pattern Matching in C# • Proposition for Roslyn in 8/2014 o https://roslyn.codeplex.com/discussions/560339 o http://www.infoq.com/news/2014/08/Pattern-Matching if (expr is Type v) { // code using v } // try-cast var c = Cartesian(3, 4); if (c is Polar(var R, *)) Console.WriteLine(R); var a = new Location(1, 2, 3); //x=1, y=2, z=3 if (a is Location(1, var y, *)) 50/72

Defining (recursive) types in Haskell • data Examenvorm = M | S | P • data Sexe= M | V • data Human = Mens Integer String Geslacht • data Point = Point Integer Integer • data GenericPoint a = Pt a a • data Tree a = Leaf a | Branch (Tree a) (Tree a) • Perfect for pattern matching! 51/72

Defining (recursive) types (2) • Comparable to structs and even classes • data Human = Human { age :: Integer, name :: String, sexe :: Sexe } • Creates automatically the following functions o Human :: Integer -> String -> Sexe -> Human o age :: Human -> Integer o name :: Human -> String o sexe :: Human -> Sexe 52/72

Insert sort in Haskell isort [ ] = [ ] isort (x:xs) = insert x (isort xs) insert x [ ] = [x] insert x (y:ys) = if (x<y) then (x:y:ys) else y:(insert x ys) Barely new syntax needed! 53/72

Insert sort in F# let rec insert x l = match l with | [] -> [x] | y::ys -> if x <= y then x::y::ys else y::insert x ys and insertsort l = match l with | [] -> [] | x::xs -> insert x (insertsort xs) Source: http://www.codecodex.com/wiki/Insertion_sort 54/72

Insert sort in C# (non-functional) static void InsertSort(IComparable[] array) { int i, j; for (i = 1; i < array.Length; i++) { IComparable value = array[i]; j = i - 1; while ((j >= 0) && (array[j].CompareTo(value) > 0)) { array[j + 1] = array[j]; j=j-1; } array[j + 1] = value; } } 55/72

Type Classes and type inference • Note the explicit IComparable[] array in function type o static void InsertSort(IComparable[] array) • In Haskell implicit and auto-detected 56/72

Polymorfic: look at the types • Typ “:i isort” at command prompt of Haskell Interpreter o isort :: Ord a => [a] -> [a] • Similar o halfList :: [a] -> [a] o findValue :: Eq a => [a] -> a -> Bool o fac :: (Num a, Eq a) => a -> a 57/72

Strongly typed programs can’t go wrong • Type inference tries to find the most general type of function o Depending on the functions that are being used • Programmer doesn’t need to define types o But a type mismatch results in a compile time error o Indicating a mistake in the reasoning o Whenever type inference succeeds most programs run correctly 58/72

Type inference in .NET • More and more available 59/72

List Comprehensions in Haskell Very declarative constructor -- give all even numbers of a list evens list = [x | x <- list, even x] inBoth list1 list2 = [x | x <- list1, findValue x list2] combine list1 list2 = [(x,y) | x <- list1, y <- list2] 60/72

List Comprehensions in Haskell Very declarative constructor -- give all even numbers of a list evens list = [x | x <- list, even x] inBoth list1 list2 = [x | x <- list1, findValue x list2] combine list1 list2 = [(x,y) | x <- list1, y <- list2] 61/72

List Comprehensions in F# [for x in collection do ... yield expr] seq { for x in 0..100 do if x*x > 3 then yield 2*x } ;; evens list = [x | x <- list, even x] inBoth list1 list2 = [x | x <- list1, findValue x list2] combine list1 list2 = [(x,y) | x <- list1, y <- list2] 62/72

List Comprehensions in C# from x in Enumerable.Range(0, 100) where x * x > 3 select x * 2 63/72

Quicksort: even more beautiful ;-) • Concept of quicksort 1. Take “a” element of the list: the “spil” 2. Split the list in two 1. Elements smaller than spil 2. Elements bigger than spil 3. Quicksort each sublist (recursively ;-) 4. Join the sorted lists together 64/72

Quicksort in Haskell qsort [] = [] qsort [x] = [x] qsort (x:xs) = let smaller = qsort([y | y <- xs, y < x]) larger = qsort([y | y <- xs, y > x]) in smaller ++ (x:larger) 65/72

Quicksort in F# let rec qsort:int list -> int list = function | [] -> [] | x::xs -> let smaller = [for a in xs do if a<=x then yield a] let larger = [for b in xs do if b>x then yield b] qsort smaller @ [x] @ qsort larger let rec qsort = function | [] -> [] | x::xs -> let smaller,larger = List.partition (fun y -> y<=x) xs qsort smaller @ [x] @ qsort larger 66/72

Higher order functions • Functions taking other functions as parameters • Simple list functions map & filter o map fac [3,6,2,4] o filter odd [1,2,3,4,5,6,7] • More Complex list functies foldr & foldl o Reduce a list to one value • Using a combining function • And a starting value o Foldr (+) 0 [1,2,3,4,5,6] 67/72

Recursion over functions repeatFun 0 f value = value repeatFun n f value = repeatFun (n-1) f (f value) bubbleSort list = repeatFun(length list) bubble list bubble [] = [] bubble [x] = [x] bubble (x:y:ys) | x < y = x:(bubble (y:ys)) | otherwise = y:(bubble (x:ys)) 68/72

Anonymous functions • Lambda abstractions 69/72

Currying • Functions of n arguments • Are actually functions of 1 argument o Returning a function of (n-1) argument • Which is actually of function of 1 argument • Returning a function of (n-2) arguments - … • Specialisation of functions contains2 = contains 2 70/72

Open your mind! • Become a Better Developer with Functional Programming o http://www.oscon.com/oscon2011/public/schedule/detail/ 19191 Questions? 71/72

More info about the TETRA-project? 72/72 • http://www.vlambda.be/ • Contact Kris.Aerts@kuleuven.be or Tom Schrijvers .NET-productiviteit verhogen met een gepast gebruikt van lambda's en F# (en natuurlijk ook in Java ;-) Vlaamse software vlamt met lambda’s

Presentation of GetTogether on Functional Programming

More Related Content

What's hot

Viewers also liked

Similar to Presentation of GetTogether on Functional Programming

Presentation of GetTogether on Functional Programming