Functional Programming Lecture Notes PDF

Functional Programming Radu Răzvan Slăvescu Technical University of Cluj-Napoca Department of Computer Science Outline Functional Programming Definition of Functional Programming Where is FP used? Brief history Administrativia Course overview Bibliogra...

Functional Programming Radu Răzvan Slăvescu Technical University of Cluj-Napoca Department of Computer Science Outline Functional Programming Definition of Functional Programming Where is FP used? Brief history Administrativia Course overview Bibliography Evaluation Defining functions if-then-else and Pattern Matching Recursion Looping via recursion Tail recursion Administrativia Lectures Assoc. prof. dr. eng. Radu Răzvan Slăvescu Course Materials 1. Lecture slides (in English) + lab documents posted on moodle every week 2. Enrollment key provided by the TA You MUST use the key of your group! Definition Functional Programming (FP) = a style of programming which employs functions applied to arguments as basic blocks for building programs. The arguments themselves can be function calls, so complex programs are built via function composition. Observation The functional paradigm belongs to declarative programming: you specify what the program does, not how it does it. Definition Program = Function Principles of (pure) Functional Paradigm I Functions are ”first class citizens” (can be passed as arguments, returned by other functions, stored in lists etc.) I Functions have no side effects (or they’re highly controlled) I Functions do not depend on global variables I Expressions (= get evaluated to some value), not statements (= perform some action) I No sequential execution of code, just combining functions I Immutable variables: their value does not change over time I There is no ”state of the program” I There are no loops, just recursive calls What is FP? Features of the FP languages we will study I strongly typed: every entity has a type attached I statically typed: type detected at compile time I perform type inference: each entity’s type is automatically deduced Language vs. implementation Language: Haskell. Implementation: ghc (software toolkit) Why FP? Modern software challenges... 1. complexity increases 2. time of development should decrease 3. number of errors should decrease...and solutions offered by Functional Programming 1. supports writing highly abstracted, clear and concise code 2. allows software reuse and rapid prototyping 3. permits reasoning about the program’s corectness 4. permits easy parallelization of the code Where if FP used? Functional Programming - some application domains 1. Erlang: WhatsApp (50 engineers, 900M users) 2. Haskell: IOG (Cardano - third-gen blockchain platform) 3. Haskell: Facebook (the Sigma anti-spam system) 4. Artificial Intelligence tools and languages: I Google JAX, a Python library for high-performance numerical computing, used in Machine Learning research I Isabelle and Agda: proof assistants I CLIPS, a rule based expert system shell A little bit of history Lambda calculus: 1930s I Lambda calculus - a theory by Alonzo Church about what functions are able to compute I could be seen as a minimalist programming language I virtually every functional language is based on this theory I useful in many fields, e.g. expressing semantics of text A little bit of history LISP (LISt Processing): 1950s, John McCarthy I functional language with ideas from lambda calculus I basic blocks: atoms, lists, forms I allows variable change (unfortunately!) I nowadays dialects: 1. Common LISP 2. Scheme 3. Racket 4. Clojure (integrated with Java platform) 5. Hy (integrated with Python) I implementations 1. gcl (GNU Common LISP) 2. CLISP 3. Steel Bank Common LISP 4. Allegro CL A little bit of history ML (Meta Language): 1970s, Robin Milner I featuring polymorphic types and type inference I implementations: 1. sml (Standard ML) 2. polyML 3. Caml 4. Objective Caml A little bit of history Miranda family Miranda means ”Admirable” A little bit of history Miranda family: Haskell (after Haskell Curry): 1987 I purely functional, with lazy evaluation I standard: Haskell 2010 report (succeeding Haskell 98) I implementation (de facto standard): ghc (Glasgow Haskell Compiler) Multiparadigm programming languages featuring FP Multiparadigm laguages Scala immutability, lazyness. Compiles to bytecode Rust expressions, types, concurrency F# (for.NET) OO + FP (Caml-like) C# immutability, function composition Python lambdas, higher-order functions, lazy objects Objectives After completing this course you should be able to: I write idiomatic, efficient functional code I understand and be able to use the basic concepts of FP I develop a basic understanding of Lambda calculus Lectures overview Basics of programming in Haskell I primitive data types I functions and recursion I evaluation (call-by-value, call-by-name, call-by-need) I type inference I lists and list comprehensions Lectures overview FP specific elements I higher-order functions HOFs (incl. anonymous functions, partial application) I infinite data and lazy evaluation I transformation and reasoning on programs I elements of Lambda calculus Lab overview Lab materials (+ related lectures) must be read in advance Elm lab: weeks 1 - 6 I basics of Elm I defining Elm functions by recursion I write a demo application Haskell: weeks 8 - 13 I practice writing Haskell code Bibliography R. R. Slăvescu Functional Programming - lecture notes. Technical University of Cluj-Napoca, 2024. G. Hutton Programming in Haskell, 2nd edition. Cambridge University Press, 2016 slides available from the course web page M. Lipovača. Learn you a Haskell for Great Good. http://learnyouahaskell.com Bibliography Haskell wiki page www.haskell.org I. A. Leţia, L. A. Negrescu, L. Negrescu Programare funcţională, vol. I. Ed. Albastră, Cluj-Napoca, Romania, 2006 Evaluation How is your mark computed? Weighted average: I Final examination: 50% (written/moodle) I Lab activity 50% I week 4 (Elm): Lab test 1: 10% I week 6 (Elm): Assignment 1: 30% + Lab test 2: 10% I week 11 (Haskell): Lab test 3: 10% I week 14 (Haskell): Lab test 4: 40% I lab code evaluation: 60% tests known in advance; 20% new tests; 20% code style Evaluation Bonuses: I Challenges I Kahoot Yellow Jersey competition (1 point per competition winner + 1.5, 1.4,... , 0.6 for the global standings) If Kahoot is available I outstanding activity during lectures/labs Condition for passing Lab: average(tests) ≥ 20% AND average(assignments) ≥ 30% AND average(testsAndAssignments) ≥ 50% Exam: average(exam) ≥ 5.00 AND average incl bonuses ≥ 5.00 Final Exam Exam I 50 % of the final mark I quick questions + problem I If failed: repeated during the next session of exams A couple of small Haskell examples Computing reciprocal (→ partial application) (1/) Sorting lists (→ list comprehension + HOF) q [] = [] q (h:t) = q [s | s Double area r = 3.14 * r * r Example (Haskell, REPL) Prelude> area r = 3.14 * r * r Prelude> area 3 28.259999999999998 How do we know the type of a function? Example (square of an integer: sq) Prelude> sq :: Int -> Int; sq x = x * x Prelude> :type sq sq :: Int -> Int Example (Most general solution for sq type) Prelude> sq x = x*x Prelude> :type sq sq :: Num a => a -> a How do we call a function? Calling functions Math: f(x, y*z, g(t)) FP: f x (y*z) (g t) Note 1. as a rule, no parentheses separate the function name and its arguments; 2. pay attention to the precedence: fact n - 1 versus fact (n-1); if not sure, use parentheses if expression (not statement) if-then-else if E then ET else EF: 1. E gets evaluated, then... 2. either ET or EF is evaluated, but never both of them 3. else is mandatory (Why?) Pattern matching mechanism Example (Product of elements in a list) prodl [] = 1 --equation 1 prodl (n:ns) = n * prodl ns --equation 2 Observations 1. each equation defines a pattern, telling what the function returns when its argument looks in a specific way (it matches that pattern) (→ declarative style) 2. pattern order does matter 3. pattern matching leads to variable binding: I n:ns matched on [1,2,3] binds n to 1 and ns to [2,3] I 1:ns matched on [1,2,3] binds ns to [2,3] I 1:ns fails when trying to match [2,3] (different list heads) I n:_:ns matched on [1,2,3] binds n to 1 and ns to Pattern matching mechanism Example (Product of elements in a list using case) prodl xs = case xs of [] -> 1 (n:ns) -> n * prodl ns Example (Product of elements in a list: no patterns) prodl ns = if null ns then 1 else (head ns) * prodl (tail ns) Observations 1. using patterns increases code clarity... 2.... and allows a better analysis of cases, thus leading to a better performance of the generated code Recursion: a function calls itself in its body Ouroboros snake (with permission from Wikimedia Commons) Recursion: main mechanism to implement loops Definition Linear recursive function It has only one recursive call to itself each time it runs. Example (Greatest common divisor: Euclid’s Algorithm) euclidgcd m n = if (m == 0) then n else euclidgcd (n ‘mod‘ m) m Example (Power, linear) power m n = if (m==0) then 0 -- what if n==0 else if n==0 then 1 else m * (power m (n-1)) Recursive functions Example (Fibonacci F0 = 0, F1 = 1, Fn = Fn−1 + Fn−2 ) fib n = if n==0 then 0 else if n==1 then 1 else fib (n-1) + fib (n-2) Example (Ackermann-Péter function) ack m n = if m==0 then (n+1) else if n==0 then ack (m-1) 1 else ack (m-1) (ack m (n-1)) Remark The number of recursive calls of this function increases extremely rapidly with its arguments. Recursive functions Definition A function is tail recursive if it returns either something computed directly or something returned by its recursive call (the last thing it does is to call itself) Example (A tail recursive function) iseven n = if (n==0) then True else if (n==1) then False else iseven (n-2) Recursive functions Example (factorial - a not tail recursive version) fact n = if (n == 0) then 1 else n * fact (n-1) Example (factorial - a tail recursive version) factacc n a = if (n==0) then a else factacc (n-1) (n*a) fact: successive calls waste stack space and time Example fact 3 = 3 * fact 2 = 3 * (2 * fact 1) = 3 * (2 * (1 * fact 0)) = 3 * (2 * (1 * 1)) = 3 * (2 * 1) fact 0 ↓1 = 3 * 2 fact 1 ↓1 = 6 fact 2 ↓2 factacc: no space and time wasted Example factacc 3 1 = factacc (3-1) (3*1) = factacc (2-1) (2*3) = factacc 0 6 6 factacc (1-1) (1*6) = factacc 1 6 6 factacc 2 3 Remark Each call can overwrite the stack frame of the previous one, hence no need for extra space or stack processing time factacc: no space and time wasted Example factacc 3 1 = 6 factacc (3-1) (3*1) = factacc (2-1) (2*3) = factacc (1-1) (1*6) = 6 Remarks 1. a tail recursive function is equivalent to an iteration and can automatically be re-written this way by the compiler 2. writing recursive functions in this manner helps saving stack space (constant!) and time (stack manipulation) Don’t Repeat Yourself: Local declarations in Haskell Example (Top-down approach: where) f x y = (sq x + sq y) < 1.0 where sq z = z * z -- square Prelude> f 0.4 0.0 True Indentation matters! Don’t Repeat Yourself: Local declarations in Haskell Example (Bottom-up approach: let... in...) f x y = let sq z = z * z -- square in (sq x + sq y) < 1.0 Mutually Recursive Functions Haskell: define either before or after use Example (Order not important) isevn n = if (n==0) then True else isodd (n-1) isodd n = if (n==0) then False else isevn (n-1) or Example (Order not important) isodd n = if (n==0) then False else isevn (n-1) isevn n = if (n==0) then True else isodd (n-1) Summary I FP is a style of programming which employs functions applied to arguments as basic blocks for building programs I We use functions and functions alone I No side effects. No variable change. No program state. No sequences of instructions. No statements. No loops. I Many functional languages/implementations available; among them, Haskell/ghc and Elm I Pattern Matching is used to express alternatives. I Recursion and function composition are employed for writing complex functional programs I Tail recursion improves performance Further reading Learn more LYHFGG: Chapter 1, Chapter 2 up to ”Texas Ranges” Programming in Haskell: Chapter 1 and Chapter 2 Why haskell in Cardano? https://www.youtube.com/watch?v=1HGUu-EIb5g Functional Programming Applications - further info 1. galois.com (critical systems) 2. commercial users of FP: http://cufp.org 3. https://www.lightbend.com/case-studies