7. Functional Programming¶

¹ Lecture Notes¶

Functional Programming Languages:
- Do not have variables; as values are immutable (cannot be changed).
- Based on the lambda calculus, where functions always return the same value for the same input.
- Referential transparency: meaning that a function call can be replaced by its return value without changing the meaning of the program.
- Recursion: Do not have iteration, but instead use recursion (no for, while, do-while, etc.).
- Pattern matching: A way to select behaviors based on the structure of data, similar to using switch statements in imperative languages.
- Function Arguments: Functions accept only one argument, but tuples, lists, and records can be used to pass multiple arguments.
- Lazy Evaluation: The evaluation of an expression is delayed until its value is needed.
- Tail Recursion: A recursive function is tail recursive if the recursive call is the last thing it does.
- Higher Order Functions:
  - Functions that take other functions as arguments or return functions as results.
  - Also called Partial Application.
  - Example: map, fold, and filter functions.
- Currying: A function that takes multiple arguments can be converted into a sequence of functions that each take a single argument.

	Imperative Programming	Functional Programming
Semantics	Complex	Simple
Syntax	Complex	Simple
Efficiency	Fast (Efficient execution)	Slow (Inefficient execution)
Concurrency	Difficult (must be explicitly programmed)	Easy (automatically concurrent)

Introduction¶

Scientist	Product	Importance	Comments
Von Neumann	Von Nemann architecture	The basis for all modern computers	Updatable store (memory cells contain values that can be updated)
Alan Turing	Turing Machine	The basis for imperative programming languages	Concept of stateful computation
Alonzo Church	Lambda Calculus	The basis for functional programming languages	Concept of stateless computation

Computability of a problem: If a problem can be solved with an imperative programming language, it can also be solved with a functional programming language, and vice versa.

² Chapter 16: Functional Programming¶

Lisp (List Processing Language) is the first functional programming language (1956), although it has some imperative features.
Erlang
There are no global variables, no assignment, no pointers and hence no side effects.
Carried functions:
- Named after the mathematician H.B Curry.
- They help as workaround to pass multiple arguments to a function.
- The called function accepts the first argument and returns a function that accepts the second argument and so on.

³ Functional programming for the rest of us¶

Functional programming is a practical implementation of Alonzo Church’s ideas.
Not all lambda calculus ideas transform to practice because lambda calculus was not designed to work under physical limitations.
If java would have been a functional programming language:
- All variables would be final by default (immutable).
- We can not call them variables anymore, but symbols.
- The state is being passed around as arguments to functions (thus, the state is saved on the stack).
- Using recursion, The function would call itself passing what it has calculated so far (the previous state) as an argument.
Benefits of functional programming:
- Since every symbol in FP is final, no function can ever cause side effects.
- You can never modify things in place, nor can one function modify a value outside of its scope for another function to use (like a class member or a global variable).
- Unit testing is easier (because of the two previous points, you only evaluate the function return).
- Debugging is easier, you just need the function arguments to reproduce the error, the previous execution steps will not affect the function return value.
- You never have to worry about deadlocks and race conditions because you don’t need to use locks! No piece of data in a functional program is modified twice by the same thread, let alone by two different threads.
- Concurrency is easier, as thing do not interfere with each other, you can run them in parallel.
- Upgradeability is easier, as you can replace a function with another function that has the same signature. Thus systems can be ungraded without restarting them.
- Optimizations of Lazy evaluation: The compiler can optimize the code by removing unused code, or not evaluating code that is not needed.
Tools used in FP to control the order of execution:
- Continuations:
  - A continuation is a function that represents the rest of the computation, that is, specifying where the returned value should be used.
  - Example x = add(3,4); s = square(x); can be written as add(3,4,square) which means square(add(3,4)) or add(3,4).square().
  - In x = add(3,4); s = square(x); there is no way to know if add or square will be executed first (especially if they are in different threads).
  - But in add(3,4,square) we know that add will be executed first, then square.
- Monads: A monad is a way to structure computations by defining what it means to chain operations together.
- Uniqueness types: A uniqueness type system is a type system that tracks whether a value is used in a single location or multiple locations.

¹ ⁴ ⁵ ⁷ ⁸ Haskell¶

-- incrementor
inc n = n+1

-- filter odd numbers
filterOdds :: [Integer] -> [Integer]
filterOdds l = filter odd l

-- print
p :: Show a => a -> IO ()
p a = putStrLn(show(a))


-- fibonacci with pattern matching
fib :: Integer -> Integer
fib x | x == 0      = 0
      | x == 1      = 1
      | x > 1       = fib(x -2) + fib(x-1)
      | otherwise   = error "fib: negative argument"

-- ignoring arguments, using general tuples
first :: (a,b,c) -> a
first (x,_,_) = x

second :: (a,b,c) -> b
second (_,y,_) = y

third :: (a,b,c) -> c
third (_,_,z) = z


-- extract the first element of a list and the rest of the list
listHead :: [a] -> a
listHead (x:xs) = x

listTail :: [a] -> [a]
listTail (x:xs) = xs



-- main function, program entry point
main = do
    p "Hello, everybody!"
    p ("Please look at my favorite odd numbers: ")
    p (filterOdds [10..20])
    p (inc 3)
    p("__fib__")
    p(fib(10)) -- 55

    p("__tuples__")
    p(first(1,"2",3.0)) -- 1
    p(second(1,"2",3.0)) -- "2"
    p(third(1,"2",3.0)) -- 3.0


    p("__lists__")
    p(listHead([1,2,3])) -- 1
    p(listTail([1,2,3])) -- [2,3]

⁶ Haskell: Purely Functional Programming Language¶

Non-Strict: denotes the use of lazy evaluation.
Pure: denotes the absence of side effects.
Statically Typed: denotes the use of static type checking (type checking is done at compile time).
Strongly Typed: denotes the use of strong type checking (type casting is not implicit, refuse operations on different types).
Haskell was introduced in 1987.
Haskell 98 was the first stable version of the language.
Named after Haskell Brooks Curry, an American mathematician and logician.
Compilers: Hugs (standard interpreter), GHC (Glasgow Haskell Compiler, open source).
Pattern matching: provide different definitions (signatures) for a function; and the compiler will choose the correct one based on the arguments supplied.
Execution mode: Eval/Apply (E/A) machine, that is, all computations are done by evaluating expressions to yield values.
The Haskell 98 report, an overview of Haskell’s main features are as follows: Haskell provides higher-order functions, non-strict semantics, static polymorphic typing, user-defined algebraic datatypes, pattern-matching, list comprehensions, a module system, a monadic I/O system, and a rich set of primitive datatypes, including lists, arrays, arbitrary and fixed precision integers, and floating-point numbers.
Monads:
- Used to control the order of execution.
- A monad is a class (container type) with two functions:
  - return (or lift): takes a value and returns a monad containing that value (puts the value in the container)
  - bind (or pipe) takes a monad and a function that takes a value and returns a monad (extracts the value from the container, applies the function to it, and returns the resulting monad).
- Use the keyword do to sequence monadic operations.

class Monad m where
    return :: a -> m a -- success
    fail :: String -> m a -- failure
    (>>=) :: m a -> (a -> m b) -> m b -- bind/augment
    (>>) :: m a -> m b -> m b -- then

-- monadic operations are sequenced using the keyword do --
main :: IO ()
main = do
    putStrLn "What is your name?"
    name <- getLine
    putStrLn ("Nice to meet you, " ++ name ++ "!")
-- Syntax note: ++ concatenates strings

⁹ ¹⁰ Higher Order Functions¶

Higher-order functions (HOF) are functions that take other functions as arguments or return functions as results.
Curried Functions (CF): functions that take their arguments one at a time, that allows partial application of functions, that is, passing multiple arguments to a function one at a time, returning a new function with one less argument.

References¶

UoPeople. (2023). CS4402: Comparative Programming Languages. Lecture Notes. ↩↩
Ben-Ari, M. (2006). Understanding programming languages. Weizman Institute of Science. Chapter 16: Functional Programming. ↩
Functional programming for the rest of us, article available at http://www.defmacro.org/ramblings/fp.html ↩
Learn You a Haskell for Great Good! available at http://learnyouahaskell.com/chapters ↩
Learn Haskell Hard and Easy available at http://yannesposito.com/Scratch/en/blog/Haskell-the-Hard-Way/#lists ↩
Read a Brief Introduction To A Non-Strict Purely Functional Programming Language Copyright © 2006 by Peter Bui of the University of Notre Dame available at http://www.cse.nd.edu/courses/cse60431/www/BasicPage/lang_papers/haskell.pdf ↩
A Gentle Introduction to Haskell 98 by Paul Hudak, Yale University, John Peterson, Yale University, and Joseph Fasel, Los Alamos National Laboratory available at: http://www.haskell.org/tutorial/index.html ↩
Learn Haskell Now https://yannesposito.com/posts/0010-Haskell-Now/index.html ↩
Higher order functions http://learnyouahaskell.com/higher-order-functions ↩
Haskell Playground https://play.haskell.org/ ↩

7. Functional Programming¶

1 Lecture Notes¶

Introduction¶

2 Chapter 16: Functional Programming¶

3 Functional programming for the rest of us¶

1 4 5 7 8 Haskell¶

6 Haskell: Purely Functional Programming Language¶

9 10 Higher Order Functions¶

References¶

¹ Lecture Notes¶

² Chapter 16: Functional Programming¶

³ Functional programming for the rest of us¶

¹ ⁴ ⁵ ⁷ ⁸ Haskell¶

⁶ Haskell: Purely Functional Programming Language¶

⁹ ¹⁰ Higher Order Functions¶