deft/archives/pres-FP-Survey.org

#+Title: Functional Programming Overview
#+Author: Yann Esposito

 - Intro & Brief History Overview
 - Major Principles (Theory)
 - Major Languages (Practice)

* math function vs Procedures.

- *Immutable*: avoids changing-state and mutable data
- *Declarative programming*: expression or declarations instead of statements
- *Pure*:
  - Output value of a function depends *only* on the arguments that are input to the function
  - Eliminating side-effects, easier to reason about code and predict behavior
  - Evaluation order and timing are a separated concern from function results
- *Functions are first-class*:
  - functions are treated like any other values.
  - functions can be passed as arguments to other functions
  - functions can returns other functions

* Brief History Overview
** Short
- λ-Calculus, Alonzo Church & Rosser 1936
- LISP (McCarthy 1960)
- Algol 60 (Naur et al 1963)
- ISWIM (Landin 1966)
- PAL (Evans 1968)
- SASL (1973-83)
- Edinburgh (1969-80) NLP, early ML, HOPE
- Miranda (1986)
- Haskell (1992‥)
** λ-Calculus
*** λ-Calculus, Alonzo Church & Rosser 1936
Typeless theory of functions.

A syntaxic construction can be equivalent to any Turing Machine.
Mainly re-writing rules.
*** Learn λ-Calculus in less than 1 minute
*** Definitions
- =a,b,...= are variables
- =()= parenthesis to group part of an expression
- =λ= greek letter (pronounced Lambda) and the =.= to write functions.
*** Free vs Bound
- =λx.xy= the expression is open as =xy= contains a =y= and there is no =λy= that bound it.
- =λx.λy.xy= is said to be bound.

Bound expressions represent functions.
*** Rules
(α) =λx.A    → λy.[y/x]A=
(β) =(λx.A)B → [B/x]A=
(η) =λx.Ax   → A= if =x= not free in =A=

Where =[B/x]A= means substitue =B= for free occurrences of =x= in =A=.

Examples:

(α) =λx.(f x z x)  → λy.(f y z y)=
(β) =(λx.(f x y))2 → (f 2 y)=
(η) =λx.f x        → f=

*** Resume
How does that work? Simply cut and paste! That's it.

Example: =(λy.x(yz))(ab)=

So =(ab)= is an expression we apply to the function =(λy.x(yz))=.
So replace =y= by =ab= and we get: =x(abz)=.

And...

That's it.
** LISP
***  LISP (McCarthy 1960)
The first functional programming language and the second oldest programming
language stil in use (after FORTRAN).

*** LISP: S-Language
- atom which are words like X or TWO
- pairing operation written as a dot

#+BEGIN_SRC elisp
((X.Y).Z)
(ONE.(TWO.(THREE.NIL)))
#+END_SRC

List, Trees, etc..

*** LISP: M-Language
defines computations on S-exrepssions. It has
- S-expressions
- function application (=f[a;b;...]=) with primitve functions =cons=, =car=, =cdr=, =atom=, =eq=
- conditional expressions (=[ test1 -> result1 ; test2 -> result2 ; ... ]=)
- ability to define recursive functions (=first[x] = [atom [x] -> x ; T -> first[car[x]]]=)

*** LISP: Encode M-Language exprs as S-Expressions

Encoding M-Language expressions and functions as S-Expressions:

Define M-language functions =eval= and =apply= that correctly interpret these
S-expressions

Thus LISP allow meta-programming: treating program as data and vice versa

*** LISP: LISP Syntax so much parenthesis

It was intended to code use M-language in an Algol-like notation.
In practice LISPers wrote their code directly in S-expressions.
M-language became a kind of ghost... theoretically important but not used by anyone.

** History
*** 1960 → 1983
- Algol 60 (Naur et al 1963) -- /no I/O facilities/
- ISWIM (Landin 1966) -- /If you See What I Mean/
- PAL (Evans 1968) -- /Pedagogic Algorithmic Language/
- SASL (1973-83) -- /St Andrews Static Language/
*** Edinburgh (1969-80)
- NLP /strongly typed/ but no polymorphisms, call-by-value
- NLP evolved into HOPE: higher order, /strongly typed/ with explicit types and
  /polymorphic type variables/, /purely functional/.
- ML (Meta-Language) emerged as the meta-language of Edinburgh LCF, programmable verification system
- Standard ML (Milner et al. 1990) /pattern matching/ and /type inference/ but *not pure*.
*** Miranda (1986)
- Milner type discipline:

#+BEGIN_SRC
tree * :: Leaf * | Node (tree *) (tree *)
#+END_SRC

- Use of =*=, =**=, =***=, ... syntax as type variables from original ML
*** Haskell (1992...)
Similar to Miranda but richer and more redundant syntax.
+ type classes
+ monadic IO
+ module system

* Major Principles (Theoretical)
** Higher-order functions

A function can take another function as parameter.

#+BEGIN_SRC haskell
map :: (a -> b) -> [a] -> [b]
map (+2) [1,2,3] -- ⇒ [3,4,5]

filter :: (a -> Bool) -> [a] -> [a]
filter (>2) [1,2,3] -- ⇒ [3]
#+END_SRC

** Purity
*** Function vs Procedure/Subroutines
- A Function is something that doesn't have any effect.
- A Procedure/subroutine is something that can interleave effects during
  evaluation
*** Referential Transparency vs Referential Opacity
- Ability to copy/paste without changing result vs impossible
- Help the programmer but also the compiler!
- Help in proving correctness
- Help simplifying algorithms, better linters
- Optimizing by:
  - memoization
  - common subexpression elimination
  - lazy evaluation
  - parallelization
*** Extremely Easy to Parallelze
**** Evaluation strategies:
=(h (f a) (g b))= We can evaluate:

- =a= then =(f a)= then =b= then =(g b)= and finally =(h (f a) (g b))=
- =b= then =a= then =(g b)= then =(f a)= and finally =(h (f a) (g b))=
- =a= and =b= in parallel then  =(f a)= and =(g b)= in parallel and finally
  =(h (f a) (g b))=
- =h= and then evaluate =(f a)= only if needed and then =(g b)= only if needed...
     That's called non-strict evaluation (sometime lazy evaluation)
For example if: =(def h (λx.λy.(+ x x)))= we don't need to evaluate =y=, in our case =(g b)=

**** Time is Hard, purity remove time from the paradigm
Calling the same function with the same parameter twice will always results in
the same value.
*** Effects?
**** Side effects in the language
The programmer must be careful not to use impure functions in place where only
pure functions are expected.
**** Split impurity using a flag (generaly a type)
- =foo : Int -> String= declared as pure
- =foo : Int -> IO String= declared as impure (IO)
*** Exceptions / Errors?
We can't avoid the fact real world has limits! Space limit, maybe time limit,
maybe access limitations...
** Tail Recursion
Recursion is heavily used in functional programming. Functional language will
often include *tail call optimisation* to ensure that heavy recursion does not
consume excessive memory.
** Functional Programming Style and Grey area Languages

Functional Style can be achieved in most languages. For example in Perl, PHP,
C++11, Java 8 and C# 3.0. all added features to facilitate the functional style.

Scala is special as it is frequently written in a functional style but the
presence of side effects and mutable state place it in a grey area.

*** A Hole in purity, and all great properties of functional programming fall appart

This is a major point. You cannot compromise with purity without losing
everything. Extremely well explained in the SICP when he introduce the =set!=
ability to *mutate* the value associated to a variable.

*** Grey Area Languages
**** XSLT
**** R, J, K and Q
**** SQL (declarative)
**** Lex/Yacc a bit

** Meta-Programming and Macros!

If you really want to have the next power level, you can write macros, or what
is mostly called meta-programming.

A notable thing to know about are LISP Macros.

** Type System
First, If when I say static typing you think C, C++, Java... No, that's NOT THAT AT ALL!

Type Theory is a vast mathematical field, with lot of hard and incredible work.

Some language don't need type system at all. Typically most LISP are very close to a raw lambda calculus.

But there is a problem with untyped languages: ⊥

Even we provided purity, you can imagine a system that help you reason about
your code even further by adding more meta informations.

Different type systems: Hindley Milner, Martin/Lof, HoTT

- Basic Types (same as in Java)
- Parametric Types ⇒ many different polymorphisms to choose
- ADT! ⇒ Algebraic Data Types (type with algebraic properties FTW!)
- GADT! ⇒ Generalized Algebraic Data Types
- Generic Programming (be able to understand that two data structure share the same underlying structure)
- Typeclasses ⇒ Incredible ability to abstraction (Monoids, Functor, Applicative, Monads, Traversables...)

* Major Languages (Practical)

- We only talk about General purpose languages (not domain specific languages)
- Prod ready or not is only regarding our current knowledge. And by prod ready
  it won't be enough to name less than 5 company using it for small project.
- Prod ready mean used at 100% by a company earning money for some years, and
  used partially (more than 10%) by more than 10 company or having a big
  production project
** Not Pure
*** Can be used in modern production env
**** LISP Family
***** Common Lisp
***** Clojure (Generally pure as default data structure are pure)
**** Not LISP & General Purpose Languages
***** Erlang
***** Mathematica
***** OCaml
***** F#
*** Not suitable for production yet
**** LISP Family
***** Scheme
***** Racket
**** Not LISP, General Purpose Languages
***** Erlang
***** ML, Caml
** Pure
*** Prod ready
**** Haskell
**** Elm
**** Purescript
*** Not Prod ready yet
**** Idris
**** Frege
**** Eta (Haskell 7.10 on the JVM) might be used in production but really recent
**** Clean
* Practical Examples
** Bug 1 - Parallelization / pureté
   - =map=
   - =pmap=
** Bug 2 - Waiting icon
   Waiting icon
** Bug 3 - Null Pointer Exception
   No NPE with Maybe
** Helper - Non deterministic programming
   - for (for (for .... ))) pyramid of hell
   List monad