Functional Programming – Introduction

Prologue

  • Where first class citizens Java and C++ where objects, in functional programming they are functions.
  • Complexity is managed through functional composition.
lambda Thinking in functional style torques your brainIt feels really good, like a hard workoutBut it hurts like a hard workout too

λ Function

In functional programming, functions are “first class citizens” among language constructs.

Values can be functions. Functions can return functions. Functions can take functions as arguments. Complexity is managed through functional composition.

Off the bat, there is room for misunderstanding. Function to a programmer means procedure, top down decomposition, C style code. Function to a mathematician means calculation, expressions, equations and therefore equality.

Before:

x = x + 1
  • An imperative
  • A programmers bread-and-butter construct, yet…
  • Mathematically wrong. There is precisely no case where  x equals x + 1.

After:

let plusone x = x + 1
  • An expression or a  declaration
  • Doesn’t modify X itself ; x is symbol not a variable; no side effects (think const in C++ or final in Java)
  • Can be mathematically reasoned about (“plusone” on LHS must equate to “+1” on RHS )
  • Therefore can be proven & optimized
  • Static types are inferred by the platform, greatly reducing the amount of boiler plate code !

ocaml3

λ Declaration, not Imperative

Before:

x = x + 1
  • Allocates a chunk of memory dereferenced by ‘x’

After:

let plusone x = x + 1
  • Creates a let binding, no memory location for ‘x’, nothing to dereference via ‘x’

 

Analogy:  Artificial Intelligence language Prolog.

Prolog builds rules using predicates and a program is initiated by running a query.

Rule example:  cat(tom) :- true

Query

Is tom a cat?

:  ?- cat(tom)

Yes

Query

What things are cats?

?- cat(X).

X = tom

A functional let binding can be thought of a symbol entry in the program’s dictionary — like a rule in Prolog — that is evaluated when queried.  As per our previous example :

ocaml2

Logic Understood…and Corrected

ocaml3

  • Note –  types inferred again as Cartesian product Boolean x Boolean
  • 3 lines of code
  • Equivalent  Java construct:

java

  • Java compiler does not “get” that something is amiss.
  • Java compiler verifies syntax only
  • Java boiler plate code about 4x as verbose

History

pic1pic2

  • The setting:  1930s, The Great Depression
  • Alonzo Church @ Princeton University
  • Contemporaries:  Alan Turing & John von Neuman
  • Alonzo Church doctoral advisor of Alan Turing
  • The two men developed parallel formalisms
  • Lambda Calculus & Turing Machine
  • Both formalisms were later proven to be of equivalent computing power
  • Thus any Turing Complete problem can be expressed in Lambda calculus

pic3

  • 1949 EDVAC (Electronic Discrete Variable Automatic Computer), effectively first example of Turing Machine on von Neuman architecture
  • Not until 1973 did MIT’s Artificial Intelligence Lab build a Lisp Machine, effectively a hardware implementation of the Lambda Calculus
  • C had already been invented in 1972 by Dennis Ritchie, laying the foundations for languages such as C++ and Java
  • Despite superior expressiveness, Lambda calculus had effectively lost the race for the mainstream against C style languages, until…
  • World War II: U.S. Army needed more advanced ballistic tables for artillery
  • Race produced IBM Mark-1, a 5 ton behemoth capable of 3 calculations / second

Until…Massive Parallelism

gpu

Rewrites traditional von Neuman architecture

Amdahl’s law, limits maximum expected improvement to an overall system when only part of the system is improved.  In practice, the inability to reason about imperative languages in a mathematical fashion, their fondness of side effects and consequent tendency towards shared memory state locking limits the benefit imperative languages will draw from parallelism. This means imperative languages hit the Amdahl’s law barrier will hold true despite token efforts such as OpenMP in C++ and parallel containers classes in J2EE & .NET.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s