Functional Programming

• Functional programming is a programming paradigm where the building block of computations is the application of functions to arguments
• Functional programs specify a data-flow to describe what computations should proceed
• Functional programming is an algebraic programming style, dominated by function application and composition
• Imperative programming is a programming paradigm where the building block of computation is the modification of stored values
• Imperative programs specify a control-flow to describe how computations should proceed
• Imperative programming is an algorithmic style paradigm, dominated by variable assignments, loops and conditional statements
• A side effect is a hidden state change that results from a function modifying or relying upon objects external to its parameter list (e.g. global variables)
• A pure function is one that takes all its inputs as arguments and produces all its outputs as results
• A pure function is a function without side effects
• A functional programming language supports and encourages a programming style with function application and composition as basic building blocks
• A functional programming language forbids variable assignment and side effects
• Functional programming languages make reasoning about code simpler for humans and compilers
• It is possible to write in a functional style in C/Java/Python etc. but these languages do not enforce the functional style
• Haskell is a purely functional, side-effect free language, built from scratch for functional programming
• Label this image

  A) Functional style code

  B) Imperative style code

  
• Machine code is explicit about what is happening, but obfuscates the algorithm from the implementation. It is also not portable, easy to modify or succinct
• High level programming languages allow writing code to an abstract machine model - a translator of some kind (e.g. a compiler) transforms this code into something that executes on a machine (which can either be a physical processor or a virtual machine. Some take a hybrid approach and do just-in-time compilation.
• High level languages abstract from machine code
• Functional programming languages don't map directly onto the hardware that they run upon - as such, a Haskell interpreter or compiler maps from one paradigm to the other.
• This Haskell code computes the factorial of an integer

  
• Semantics of code fragments in Haskell are given implicitly, and the reader will have to reconstruct them
• Haskell code can be made more readable by adding type annotations and comments
• The Haskell standard library is called "Prelude"
• Operators in Haskell are special functions
• Variables are immutable in Haskell
• A type is a collection of related values
• A type can be described by specifying the set of data elements it covers and the operations it supports
• Integer -> Integer is the set of all functions that take an Integer as an input and produce an Integer as an output
• We need types to:

  • Tell us how to interpret a variable,
  • Provide restrictions on valid operations
• In statically typed languages, type safety is checked at translation time. This means that invalid types result in a translation error
• Invalid types in statically typed languages result in a translation error
• The'+' operator is not defined for all types


  Explain why this is invalid

  
• In dynamically typed languages, type safety is checked at run time. In this case, invalid types are only detected as soon as they are used
• Types can be:

  • Explicitly annotated by the programmer
  • Inferred for each variable based on the operations used (Haskell can do this)
  • Understood with duck typing - runtime just tries the operation, and if it succeeds it is valid (Python)
• Haskell is strongly, statically typed
• Because Haskell is strongly, statically typed, every well-formed expression has exactly one type, and these are known at compile time
• The first line of this program states that "e is of type T"

  
• Every valid expression is Haskell must have a valid type
• Functions in Haskell have types
• Haskell makes the types of functions particularly explicit compared with other programming languages