Functional programming

Functional Programming Ian Duggan

Styles of Programming There are many styles of programming, depending on the dimension you look at and the features available in the language ● Imperative vs Functional ● Compiled vs Scripting ● Static vs Dynamic ● Implicit vs Explicit type conversion ● Managed vs Unmanaged (memory)

Programming Paradigms Imperative - how to solve ● Procedural ● Object-oriented Declarative - what to solve ● Functional ● Logic

The “Blub Paradox” ● Paul Graham, Beating the Averages ○ http://www.paulgraham.com/avg.html ● Imagine all languages on a line from the left to the right ● Less powerful languages on the left, More powerful languages on the right ● It is not possible to fully understand languages to the right of the “best” language you know. ○ They have features difficult to grasp the usefulness of before you use them (recursion, first-class functions, monads, actors macros, etc…)

Object-Oriented Programming ● Encapsulation by classes/objects ● Polymorphism through inheritance, etc. ● Mutable data (object state changes)

Functional vs Object-Oriented ● They are orthogonal concepts, not opposites ● Alan Kay, inventor of Smalltalk, said OO is about message passing and isolation, not about objects, classes, inheritance, etc. ● Erlang is the “most object-oriented language” ● http://bit.ly/1vFSqdk

Functional Programming ● Doesn’t have a precise definition ● Is more than a style of programming ○ I.e. you can do functional programming in any language, it’s just that some languages push you toward this style ● Treat computation as evaluation of mathematical functions

Functional Programming ● Often focuses on immutable data ● Data and Functions ● Declarative programming style ● Expressions (as opposed to statements)

Functional Programming ● Referential transparency ○ (same input, same output) ● Focus on eliminating “side effects” ● Has its origins in the “lambda calculus”

Lambda Calculus ● Formal system in mathematics for expressing computation ● Developed by Alonzo Church in 1930s ● Based on abstraction and application using binding and substitution ● Universal model of computation

Maxwell’s Equations ● Define electromagnetism ● Compact and precise ● Easy to work with ● “Cosmically spiritual” to a physicist ● God is in this

“Maxwell’s Equations” of Programming ● You can implement a LISP from 7 basic primitives ● Hints at the “mathematical” nature of functional programming ● Strip away all the “junk” and this is computation in its “pure” form. ● Mentally relate this to building a computer in Minecraft ● God is in this

First-Class Functions ● Functions are no different than data ● They can be ○ assigned to variables ○ passed as arguments ○ returned from functions

Higher-Order Functions ● Functions that operate on functions ● Take a function as input, return a new function as output ● The derivative, d/dx is a familiar example from math

Pure Functions ● Referentially transparent ● Have no side effects ● Memoization ● If value is not use, there is no effect in removing the function ● Since they can’t affect each other, it is trivial to call them in different orders or automatically parallelize their application

Referential Transparency ● An expression is “referentially transparent” if it can be replaced with its corresponding value. ● Substitution-model of computation ● Requires internals of computation to be “side effect free” ○ No screen output ○ No setting of variables elsewhere ○ No writing to disk ○ No launching of missles

Recursion ● Looping is not a thing in functional languages ○ looping requires updating a loop value) ● Tail-call optimization ○ Return from function replaced with jump to beginning ● Continuation passing style

Tail-Call Optimization ● Makes infinite recursion not blow up ● Converts a recursive call to iteration ● Replaces call to function at “tail” into a “jmp” back to the start of the function

Currying ● Translating a function that takes multiple arguments into the composition of functions of one argument. ● Makes use of closures

Partial Application ● Passing fewer than all of the arguments to a function ● Results in a function that is “partially applied” ● Can be used to call “half of a function”

Partial Application (Javascript)

Pattern Matching ● Like smart “case” statements in Ruby ● Compiler works to make statement “true” by binding LHS values, as appropriate ● “Destructuring assignment” from javascript, but on steroids

Piecewise Function Definition ● You may recall piecewise function definitions from math ● We can do this in many functional languages as well

Piecewise functions (with guards)

Immutable Data ● Once a value is set, it cannot be changed ● Makes it really easy to write durable code ○ You can be sure your values won’t change out from under you ● Makes concurrency stupidly-simple ○ Your values can’t change, so read away with abandon

Immutability : How do change state? ● Basically, you pass new state into a new function ● That function can be yourself ● Special values marked as mutable ○ Keep internal to a function or closure, and just be very careful when you update (Clojure, Lisp, etc.) ● Monads (I won’t talk about these today) ○ Haskell ● Actor Model ○ Erlang/Elixir

Actor Model An actor is a computational entity that, in response to a message it receives, can concurrently: ● send a finite number of messages to other actors ● create a finite number of new actors ● designate the behavior to be used for the next message it receives.

Actor Model Each actor runs in it’s own thread

Actor Model ● An Actor has a mailbox ● Actors communicate with other Actors by sending them immutable messages ● Messages are put into the Actor’s mailbox

Actor Model ● When an Actor’s mailbox has a message, code is run with that message as an argument. This code is called serially. ● When an Actor encounters an error, it dies. ○ “Let it crash” ● Actors can supervise other Actors, and if the supervised Actors die, the supervisor is sent a message. If this message isn’t handled, the supervisor dies.

OTP/Supervisors ● Actors watch other actors ● “Let it crash” ● Supervisor restarts ● Allows for “happy path programming”

Elixir (also) Using pure anonymous functions

Functional programming

In this document

More Related Content

What's hot

Similar to Functional programming

Recently uploaded

Functional programming