Functional Programming
Functional ProgrammingFunctional ProgrammingRalf HinzeUniversität KaiserslauternApril 2019Universität Kaiserslautern — Ralf Hinze0.0/1-73
Functional ProgrammingPart 0OverviewUniversität Kaiserslautern — Ralf Hinze0.0/2-73
Functional tentsWhat’s it all about?LiteratureUniversität Kaiserslautern — Ralf Hinze0.0/3-73
Functional Programming0.1AimsAims functional programming is programming with values:value-oriented programming no ‘actions’, no side-effects — a radical departure fromordinary (imperative or OO) programming surprisingly, it is a powerful (and fun!) paradigm ideas are applicable in ordinary programming languages too;aim to introduce you to the ideas, to improve yourprogramming skills (I don’t expect you all to start using functional languages) we use Haskell, the standard lazy functional programminglanguage, see www.haskell.orgUniversität Kaiserslautern — Ralf Hinze0.1/4-73
Functional Programming0.2MotivationMotivationLISP is worth learning [because of] the profoundenlightenment experience you will have when you finallyget it. That experience will make you a better programmerfor the rest of your days, even if you never actually useLISP itself a lot.Eric S. Raymond, American computer programmer (1957–)How to Become a Hackerwww.catb.org/ esr/faqs/hacker-howto.htmlYou can never understand one language until youunderstand at least two.Ronald Searle, British artist (1920–2011)Universität Kaiserslautern — Ralf Hinze0.2/5-73
Functional Programming0.2MotivationFP and OOPOOP features originating in FP: generics e.g. Tree Elem Haskell: parametric polymorphism Tree elem type inferenceenjoy the benefits of static typing without the pain lambda expressions e.g. p p.age() 18the core of Haskell \p age p á 18 immutable classes and value classespurity is at the heart of Haskell language integrated query languagesHaskell’s list comprehensions garbage collectionyou don’t want to do withoutSee Java, C#, F#, Scala etcUniversität Kaiserslautern — Ralf Hinze0.2/6-73
Functional Programming0.2MotivationFP in industrySome big players: facebook: Haskell for spam filtering Intel: FP for chip design Jane Street, Credit Suisse, Standard Chartered Bank: FP forfinancial contracts etcSome specialist companies: galois: FP for high assurance software Well-Typed: Haskell consultantsUniversität Kaiserslautern — Ralf Hinze0.2/7-73
Functional Programming0.3OrganizationOrganizational matters Website: https://pl.cs.uni-kl.de/fp19 your goal: obtain a good grade (my goal: get you interested in FP) how to achieve your goal:ñññmake good use of me i.e. attend lecturesmake good use of my teaching assistant: Sebastian Schweizerobtain at least a sufficient grade for 75% of the exercisesññññwork and submit in groups of 3–4submission: Tuesday 12:00 noonexercise session: Thursday, 11:45 - 13:15, Room 48-453pass the final exam a gentle request and a suggestion:keep the use of electronic devices to a minimum;make notes using pencil and paperUniversität Kaiserslautern — Ralf Hinze0.3/8-73
Functional Programming0.4ContentsContents: part one1. Programming with expressions and values2. Types and polymorphism3. Lists4. List comprehensions5. Algebraic datatypes6. Purely functional data structures7. Higher-order functions8. Case study: parser combinators9. Type classes10. Case study: map-reduce11. Reasoning and calculating12. Algebra of programmingUniversität Kaiserslautern — Ralf Hinze0.4/9-73
Functional Programming0.4ContentsContents: part two13. Lazy evaluation14. Infinite data structures15. Imperative programming16. Functors and theorems for free17. Applicative functors18. Monads19. Type system extensions20. Class system extensions21. Duality: folds and unfolds22. Case study: a duality of sorts23. Case study: turtles and tesselationsUniversität Kaiserslautern — Ralf Hinze0.4/10-73
Functional Programming0.5What’s it all about?Expressions vs statements in ordinary programming languages the world is divided intoa world of statements and a world of expressions statements:ññx : e, s1 ; s2, while e do sexecution order is importanti : i 1 ; a : a i a : a i ; i : i 1 expressions:ña b c, a and not bevaluation order is unimportant: inñevaluate either parenthesis first (or both simultaneously!)(assumes no side-effects: order matters in x x )ñ(2 a y b) (2 a y c)Universität Kaiserslautern — Ralf Hinze0.5/11-73
Functional Programming0.5What’s it all about?Referential transparency useful optimizations:ñreordering: ñcommon sub-expression elimination: ñx : 0 ; y : e ; if x 0 then . . . endx : 0 ; if x 0 then . . . end ; y : ex : 0 ; y : ez : (2 a y b ) (2 a y c )t : 2 a y ; z : (t b) (t c)parallel execution: evaluate sub-expressions concurrently most optimizations require referential transparencyññññall that matters about the expression is its valuefollows from ‘no side effects’. . . which follows from ‘no : ’with assignments, side-effect-freeness is hard to checkUniversität Kaiserslautern — Ralf Hinze0.5/12-73
Functional Programming0.5What’s it all about?Programming with expressions expressions are much shorter and simpler than thecorresponding statements e.g. compare using expression:z : (2 a y b ) (2 a y c )with not using expressions:ac : 2 ; ac a ; ac y ; ac b ; t : ac ;ac : 2 ; ac a ; ac y ; ac c ; ac t ;z : ac but in order to discard statements, the expression languagemust be extended functional programming is programming with an extendedexpression languageUniversität Kaiserslautern — Ralf Hinze0.5/13-73
Functional Programming0.5What’s it all about?Comparison with ‘ordinary’ programming insertion sort quicksort binary search treesUniversität Kaiserslautern — Ralf Hinze0.5/14-73
Functional Programming0.5What’s it all about?Insertion sort: Modula-2PROCEDURE InsertionSort ( VAR a : ArrayT ) ;VAR i , j : CARDINAL ;t : ElementT ;BEGINFOR i : 2 TO Size DO(* a[1.i-1] already sorted *)t : a[i ] ;j : i ;WHILE ( j 1) AND ( a [ j 1] t ) DOa [ j ] : a [ j 1]; j : j 1END ;a[j] : tENDEND InsertSort ;Universität Kaiserslautern — Ralf Hinze0.5/15-73
Functional Programming0.5What’s it all about?Insertion sort: HaskellinsertionSort [ ] []insertionSort (x : xs) insert x (insertionSort xs)insert a [ ] [a]insert a (b : xs) aàb a : b : xs otherwise b : insert a xsUniversität Kaiserslautern — Ralf Hinze0.5/16-73
Functional Programming0.5What’s it all about?Quicksort: Cvoid quicksort ( int a [ ] , int l , int r ){if ( r l ){int i l ; int j r ;int p a [ ( l r ) / 2 ] ;for ( ; ; ) {while ( a [ i ] p ) i ;while ( a [ j ] p ) j ;if ( i j ) break ;swap(&a [ i ] , &a [ j ]);};quicksort ( a , l , j ) ;quicksort ( a , i , r ) ;}}Universität Kaiserslautern — Ralf Hinze0.5/17-73
Functional Programming0.5What’s it all about?Quicksort: HaskellquickSort [ ] []quickSort (x : xs) quickSort littles [x] quickSort bigswhere littles [a a xs, a x]bigs [a a xs, x à a]Universität Kaiserslautern — Ralf Hinze0.5/18-73
Functional Programming0.5What’s it all about?Binary search trees: Javapublic class BinarySearchTree Elem {private Tree Elem root ;public BinarySearchTree ( ) {root new Empty ( ) ;}public void inorder ( ) {root . inorder ( ) ;}public void insert ( Elem e ) {root root . insert ( e ) ;}}public interface Tree Elem {void inorder ( ) ;Tree insert ( Elem e ) ;}Universität Kaiserslautern — Ralf Hinzeclass Empty Elem extends Comparable Elem implements Tree Elem {public void inorder ( ) {}public Tree insert ( Elem k ) {return new Node( new Empty ( ) , k , new Empty ( ) ) ;}}class Node Elem extends Comparable Elem implements Tree Elem {private Elem a ;private Tree l , r ;public Node ( Tree l , Elem a , Tree r ) {this . l l ; this . a a ; this . r r ;}public void inorder ( ) {l . inorder ( ) ;System . out . println ( a ) ;r . inorder ( ) ;}public Tree insert ( Elem k ) {if ( k . compareTo ( a ) 0)l l . insert ( k ) ;elser r . insert ( k ) ;return this ;}}0.5/19-73
Functional Programming0.5What’s it all about?Binary search trees: Haskelldata Tree elem Empty Node (Tree elem) elem (Tree elem)inorder Empty []inorder (Node l a r) inorder l [a] inorder rinsert k Empty Node Empty k Emptyinsert k (Node l a r) kàa Node (insert k l) a r otherwise Node l a (insert k r)Universität Kaiserslautern — Ralf Hinze0.5/20-73
Functional Programming0.6LiteratureLiterature Miran Lipovaca, Learn You a Haskell for Great Good!: ABeginner’s Guide, No Starch Press, 2011. Richard Bird, Thinking Functionally with Haskell, CambridgeUniversity Press, 2015. Paul Hudak, The Haskell School of Expression: LearningFunctional Programming through Multimedia, CambridgeUniversity Press, 2000. Graham Hutton, Programming in Haskell (2nd Edition),Cambridge University Press, 2016. Bryan O’Sullivan, John Goerzen, Don Stewart, Real WorldHaskell, O’Reilly Media, 2008. Simon Thompson, Haskell: The Craft of FunctionalProgramming (3rd Edition), Addison-Wesley Professional,2011.Universität Kaiserslautern — Ralf Hinze0.6/21-73
Functional ProgrammingLiteraturePart 1Programming with expressions and valuesUniversität Kaiserslautern — Ralf Hinze1.0/22-73
Functional Programming1.0LiteratureOutlineScripts and rsität Kaiserslautern — Ralf Hinze1.0/23-73
Functional Programming1.1Scripts and sessionsCalculators functional programming is like using a pocket calculator user enters in expression, the system evaluates theexpression, and prints result interactive ‘read-eval-print’ loopiiii product [1 . . 0iiii sort "hello, world\n""\n ,dehllloorw" powerful mechanism for defining new functions we can calculate not only with numbers, but also with lists,trees, grammars, pictures, music . . .Universität Kaiserslautern — Ralf Hinze1.1/24-73
Functional Programming1.1Scripts and sessionsScripts and sessions we will use GHCi, an interactive version of the GlasgowHaskell Compiler, a popular implementation of Haskell a program is a collection of modules a module is a collection of definitions: a script running a program consists of loading script and evaluatingexpressions: a session a standalone program includes a ‘main’ expression scripts may or may not be literate (emphasis on comments)Universität Kaiserslautern — Ralf Hinze1.1/25-73
Functional Programming1.1Scripts and sessionsAn illiterate script (.hs suffix)-- compute the square of an integersquare :: Integer - Integersquare x x * x-- smaller of two argumentssmaller :: (Integer, Integer) - Integersmaller (x, y) if x y then x else yUniversität Kaiserslautern — Ralf Hinze1.1/26-73
Functional Programming1.1Scripts and sessionsA literate script (.lhs suffix)The following function squares an integer. square :: Integer - Integer square x x * xThis one takes a pair of integers as an argument,and returns the smaller of the two as a result.For example,smaller (3, 4) 3 smaller :: (Integer, Integer) - Integer smaller (x, y) if x y then x else yUniversität Kaiserslautern — Ralf Hinze1.1/27-73
Functional Programming1.1Scripts and sessionsLayout elegant and unobtrusive syntax structure obtained by layout, not punctuation all definitions in same scope must start in the same column indentation from start of definition implies continuationsmaller :: (Integer, Integer) Integersmaller (x, y) ifxàythenxelsey leave blank lines around code in literate script! use spaces, not tabs!Universität Kaiserslautern — Ralf Hinze1.1/28-73
Functional Programming1.1Scripts and sessionsA sessioniiii 4242iiii 6 742iiii square 7 smaller (3, 4) square (smaller (2, 3))42iiii square 12345678901524157875019052100Universität Kaiserslautern — Ralf Hinze1.1/29-73
Functional Programming1.2EvaluationNotation: evaluation of expressions we use the following layout for evaluationsexpr1 { why? }expr2 { why? }expr3Universität Kaiserslautern — Ralf Hinze1.2/30-73
Functional Programming1.2EvaluationEvaluation interpreter evaluates expression by reducing to simplestpossible form reduction is rewriting using meaning-preservingsimplifications: replacing equals by equalssquare (3 4) { definition of ‘ ’ }square 7 { definition of square }7 7 { definition of ‘ ’ }49 expression 49 cannot be reduced any further: normal form applicative order evaluation: reduce arguments beforeexpanding function definition (call by value, eager evaluation)Universität Kaiserslautern — Ralf Hinze1.2/31-73
Functional Programming1.2EvaluationAlternative evaluation orders other evaluation orders are possible:square (3 4) { definition of square }(3 4) (3 4) { definition of ‘ ’ }7 (3 4) { definition of ‘ ’ }7 7 { definition of ‘ ’ }49 final result is the same: if two evaluation orders terminate,both yield the same result (confluence) normal order evaluation: expand function definition beforereducing arguments (call by need, lazy evaluation)Universität Kaiserslautern — Ralf Hinze1.2/32-73
Functional Programming1.2EvaluationValues in FP, as in maths, the sole purpose of an expression is todenote a value other characteristics (time to evaluate, number of characters,etc) are irrelevant values may be of various kinds: numbers, truth values,characters, tuples, lists, functions, etc important to distinguish abstract value (the number 42) fromconcrete representation (the characters ‘4’ and ‘2’, the string“XLII”, the bit-sequence 0000000000101010) evaluator prints canonical representation of value some values have no canonical representation (e.g. functions),some have only infinite ones (e.g. π)Universität Kaiserslautern — Ralf Hinze1.2/33-73
Functional Programming1.3FunctionsFunctions naturally, FP is a matter of functions script defines functions (square, smaller) (script actually defines values; indeed, in FP functions arevalues) function transforms (one or more) arguments into result deterministic: same arguments always give same result may be partial: result may sometimes be undefined e.g. cosine, square root; distance between two cities; compiler;text formatter; process controllerUniversität Kaiserslautern — Ralf Hinze1.3/34-73
Functional Programming1.3FunctionsFunction types type declaration in script specifies type of function e.g. square :: Integer Integer in general, f :: A B indicates that function f takes argumentsof type A and returns results of type B the interface of a function is manifest apply function to argument: f x sometimes parentheses are necessary: square (3 4)(function application is an operator, binding more tightly thanthe operator )Universität Kaiserslautern — Ralf Hinze1.3/35-73
Functional Programming1.3FunctionsLambda expressions notation for anonymous functions (inventing names is hard) e.g. \x x x as another way of writing square x is the formal parameter; x x is the body of the function ASCII ‘\’ is nearest equivalent to Greek λ from Church’s λ-calculus theory of computability (1941)Universität Kaiserslautern — Ralf Hinze1.3/36-73
Functional Programming1.3FunctionsLambda expressions notation for anonymous functions (inventing names is hard) e.g. \x x x as another way of writing square x is the formal parameter; x x is the body of the function ASCII ‘\’ is nearest equivalent to Greek λ from Church’s λ-calculus theory of computability (1941) evaluation rule for λ-expressions (β-rule)(\x body) arg body {x : arg} function applied to argument reduces to function body, whereevery occurrence of the formal parameter is replaced by theactual parameter e.g.(\x x x) 47 x x {x : 47} 47 47 94Universität Kaiserslautern — Ralf Hinze1.3/36-73
Functional Programming1.3FunctionsOperators functions with alphabetic names are prefix: f 3 4 functions with symbolic names are infix: 3 4 make an alphabetic name infix by enclosing in back-quotes:17 ‘mod‘ 10 make symbolic operator prefix by enclosing it in parentheses:( ) 3 4 extend notion to include one argument too: sectioning e.g. (1/) is the reciprocal function, ( 0) is the positivity testUniversität Kaiserslautern — Ralf Hinze1.3/37-73
Functional Programming1.3FunctionsAssociativity why operators at all? why not prefix notation? there is a problem of ambiguity:x y zwhat does this mean: (x y) z or x (y z)? sometimes it doesn’t matter, e.g. addition(x y) z x (y z)the operator is associative recommendation: use infix notation only for associativeoperators the operator has also a unit elementx 0 x 0 x 0 and form a monoid (more later)Universität Kaiserslautern — Ralf Hinze1.3/38-73
Functional Programming1.3FunctionsAssociation some operators are not associative ( , /, ˆ) to disambiguate without parentheses, operators may associateto the left or to the right e.g. subtraction associates to the left: 5 4 2 1 function application associates to the left: f a b means (f a) b function type operator associates to the right:Integer Integer Integer meansInteger (Integer Integer) not to be confused with associativity, when adjacentoccurrences of same operator are unambiguous anywayUniversität Kaiserslautern — Ralf Hinze1.3/39-73
Functional Programming1.3FunctionsPrecedence association does not help when operators are mixedx y zwhat does this mean: (x y) z or x (y z)? to disambiguate without parentheses, there is a notion ofprecedence (binding power) e.g. has higher precedence (binds more tightly) than infixl 7 infixl 6 function application can be seen as an operator, and has thehighest precedence, so square 3 4 13Universität Kaiserslautern — Ralf Hinze1.3/40-73
Functional Programming1.3FunctionsComposition glue functions together with function composition defined as follows:(g f) x g (f x) equivalent definitions: g f \x g (f x) and( ) g f x g (f x) e.g. function square double takes 3 to 36 associative, so parentheses not needed in f g hUniversität Kaiserslautern — Ralf Hinze1.3/41-73
Functional Programming1.4DefinitionsDeclaration vs expression style Haskell is a committee language Haskell supports two different programming styles declaration style: using equations, patterns and expressionsquad :: Integer Integerquad x square x square x expression style: emphasizing the use of expressionsquad :: Integer Integerquad \x square x square x expression style is often more flexible experienced programmers use both simultaneouslyUniversität Kaiserslautern — Ralf Hinze1.4/42-73
Functional Programming1.4DefinitionsEvaluation of expressions: definition style e.g. given (declaration style)spread f g x (f x) (g x)kill ax a we calculatespread kill kill 4711 { definition of spread }(kill 4711) (kill 4711) { definition of kill }4711 definitions are applied from left to rightUniversität Kaiserslautern — Ralf Hinze1.4/43-73
Functional Programming1.4DefinitionsEvaluation of expressions: expression style e.g. given (expression style)spread \f \g \x (f x) (g x)kill \a \x a we calculatespread kill kill 4711 { definition of spread }(\f \g \x (f x) (g x)) kill kill 4711 { β-rule }(\g \x (kill x) (g x)) kill 4711 { β-rule }(\x (kill x) (kill x)) 4711 { β-rule }(kill 4711) (kill 4711).Universität Kaiserslautern — Ralf Hinze1.4/44-73
Functional Programming1.4DefinitionsDefinitions we’ve seen some simple definitions of functions so far can also define other kinds of values:name :: Stringname "Ralf" all definitions so far have had an identifier (and perhapsformal parameters) on the left, and an expression
Functional Programming Aims 0.1 Aims functional programming is programming with values: value-oriented programming no ‘actions’, no side-effects — a radical departure from ordinary (imperative or OO) programming surprisingly, it is a powerful (and fun!) paradigm ideas are applicabl
Numeric Functional Programming Functional Data Structures Outline 1 Stuff We Covered Last Time Data Types Multi-precision Verification Array Operations Automatic Differentiation Functional Metaprogramming with Templates 2 Numeric Functional Programming Advanced Functional Programming with Templates Functional Data Structures Sparse Data Structures
Functional programming paradigm History Features and concepts Examples: Lisp ML 3 UMBC Functional Programming The Functional Programming Paradigm is one of the major programming paradigms. FP is a type of declarative programming paradigm Also known as applicative programming and value-oriented
functional programming style. Adding functional programming facilities to Prolog results in a more powerful language, as they allow higher-order functional expres-sions to be evaluated conveniently within the logic programming environment. And, as will be shown in this thesis, the efficiency of functional programming in logic is
Introduction to Functional Programming in Java 8 Java 8 is the current version of Java that was released in March, 2014. While there are many new features in Java 8, the core addition is functional programming with lambda expressions. In this section we describe the benefits of functional programming and give a few examples of the programming .
What is Functional Programming? Functional programming is a style of programming that emphasizes the evaluation of expressions, rather than execution of commands Expressions are formed by using functions to combine basic values A functional language is a language that supports and encourages programming in a functional style
Welcome to Functional Programming in R! I wrote this book, to have teaching material beyond the typical introductory level most textbooks on R have. This book is intended to give an introduction to functions in R and how to write functional programs in R. Functional programming is a style of programming, like object-oriented programming,
Functional Programming In a restricted sense, functional programming (FP) means programming without mutable variables, assignments, loops, and other imperative control structures. In a wider sense, functional programming means focusing on the functions. In particular, functions can be values that are produced, consumed, and composed.
Artificial Intelligence – A European approach to excellence and trust. It outlines the main principles of a future EU regulatory framework for AI in Europe. The White Paper notes that it is vital that such a framework is grounded in the EU’s fundamental values, including respect for human rights – Article 2 of the Treaty on European Union (TEU). This report supports that goal by .
