yogsototh/deft
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
deft/archives/pres-FP-Survey.org
Yann Esposito (Yogsototh) 5138e54776
updated files
2019-04-24 21:27:19 +02:00

9.5 KiB
Raw Permalink Blame History

Functional Programming Overview

  • 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
((X.Y).Z)
(ONE.(TWO.(THREE.NIL)))

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:
tree * :: Leaf * | Node (tree *) (tree *)
  • 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.

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

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

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