Von Neumann Architecture

• John Von Neumann, 1903-1957
• Mathematician, Physicist, all-around genius
• Set theory, Operator theory, quantum theory, nuclear physics...
• One of those ridiculously smart people who don't get enough credit for how much they change the world.

Von Neumann Architecture

Von Neumann Architecture

• A program is just data: "Stored Program" concept
• A program is a series of steps
• Steps execute in linear sequence
• Steps alter memory registers
• Steps can alter the next step

Imperative Programming

• Imperative "mood"
• Series of precise commands
• State: values that get changed over time by commands
• The purpose of commands is to alter state

This is what all modern hardware does

Imperative Programming is following a recipe for a cake

Procedural Programming

• Imperative Programming: Evolved
• Procedure = subroutine = reusable series of commands
• Structured Programming: High-level abstractions
  • if-then
  • while
  • for

Var MyList [5, 7, 2, 9, 2]
Var Biggest
Procedure FindBiggest
  For MyList As Item
    If Item > Biggest Then
      Biggest = Item
    End If
  End For
  Return
End Procedure

Call FindBiggest
Print Biggest

Imperative Programming is following a recipe for a cake

Procedural Programming is singing a song with a refrain

Declarative programming

Declarative Programming defines
what a program should accomplish.

Functional Programming

• John Backus, 1924-2007
• Invented FORTRAN, 1953
• As penance...
  • Developed Backus-Naur Form (BNF)
  • Co-developed Algol
  • Function-level Programming (FP), 1977

"Can Programming Be Liberated From the von Neumann Style? A Functional Style and its Algebra of Programs"

Functional programming

Declare your algorithm

The compiler optimizes for you

Functional programming

• Pure functions
• Higher-order functions / First-class functions
• Immutable variables

Imperative Programming is following a recipe for a cake

Procedural Programming is singing a song with a refrain

Functional Programming is expressions in a spreadsheet

So what?

This is PHP!

Functional languages enforce what is
simply "good code" in other languages

Pure functions

• No side-effects (including I/O)
• Explicit function input/output
• Stateless
• Takes clear input, gives clear output: that's it

Pure functions

function theme_list(array $items, $type = 'ul') {
  $output = '';
  foreach ($items as $item) {
    $output .= '
' . $item . '
';
  }
  return "<{$type}>" . $output . '<' . '/' . $type . '>';
}
            

Pure functions

• Easy testability
• Not SAD (Spooky Action at a Distance)
• Self-contained
• No I/O
• Idempotent

Where have we seen this before...?

Service objects

• Stateless
• Single-purpose
• Idempotent (usually)
• No non-I/O side-effects

Good service objects are pure functions

Anonymous functions

$find_pair = function ($card1, $card2) {
  return ($card1->value == $card2->value);
};

$is_pair = $find_pair(new Card('2H'), new Card('8D'));

class FindPair {
  public function __invoke($card1, $card2) {
    return ($card1->value == $card2->value);
  }
}

$find_pair = new FindPair();
$is_pair = $find_pair(new Card('2H'), new Card('8D'));

Closures

$wild = new Card('5H');
$find_pair = function ($card1, $card2) use ($wild) {
  return ($card1->value == $card2->value
    || $wild->value == $card1->value && $wild->suit == $card1->suit
    || $wild->value == $card2->value && $wild->suit == $card2->suit);
};

$is_pair = $find_pair(new Card('2H'), new Card('8D'));

$wild = new Card('5H');
class FindPair {
  protected $wild;
  public function __construct($wild) {
    $this->wild = $wild;
  }
  public function __invoke($card1, $card2) {
    return ($card1->value == $card2->value
      || $this->wild->value == $card1->value && $this->wild->suit == $card1->suit
      || $this->wild->value == $card2->value && $this->wild->suit == $card2->suit);
  }
}
$find_pair = new FindPair($wild);
$is_pair = $find_pair(new Card('2H'), new Card('8D'));

Layering functions

$wild = new Card('5H');

$is_wild = function($card) use ($wild) {
  return $wild->value == $card->value && $wild->suit == $card->suit;
}

$find_pair = function ($card1, $card2) use ($is_wild) {
  return ($c1->value == $c2->value || $is_wild($c1) || $is_wild($c2));
};

$is_pair = $find_pair(new Card('2H'), new Card('8D'));

Delayed execution

class Container {
  protected $factories = array();

  public function __set($key, $func) {
    $this->factories[$key] = $func;
  }

  public function __get($key) {
    return $this->factories[$key]($this);
  }
}

$container = new Container();
$container->conn = function($c) {
  return new DatabaseConnection($c->info);
};
$container->info = function() { return ['user'=>'me', 'pass'=>'hi']; };

$conn = $container->conn;
$conn->query('...');

Hey, look, a Dependency Injection Container!

Importing

abstract class Importer {
  public function __construct(MapInterface $map) { $this->map = $map; }
  public function mapData($source) {
    $dest = $this->repository->create('someType');
    foreach ($this->map->mapping() as $field => $callback) {
      $dest->$field = $callback($source);
    }
    return $dest;
  }
}

class MyMapper implements MapInterface {
  public function mapping() {
    $proc = $this->someUtilityService;
    $map['title'] = function($source) use ($proc) {
      return strip_tags($proc->extract('label', $source));
    };
    $map['body'] = function($source) { return $source->body; };
    $map['extra'] = function($source) { return "Some hard coded value"; };
    return $map;
  }
}

$importer = new Importer(new MyMapper());
$my_object = $importer->mapData($fancy_external_data_object);

The Functional Way

Map/Reduce

• "Embarrassingly Parallel" Problems
• Map
  1. Divide a problem into (identical) sub-problems
  2. Distribute to separate workers
• Reduce
  1. Collect answers
  2. Combine back together
• Really useful for epically huge data sets

Map/Reduce

• Could get very complicated, or...

• $result = array_map($callback, $array);
  
  $result = array_map(function($a) {
    // Your logic here.
  }, $array);
  
  $result = array_map(function($a, $b) {
    // Your logic here.
  }, $array1, $array2);
                  

• foreach(), but separates application from loop
• Slightly slower, but not enough to care

Declarative PHP

$importer = new Importer(new MyMapper());
foreach ($array_of_external_objects as $object) {
  $my_objects[] = $importer->mapData($object);
}

$apply = function($callback, Iterator $i) {
  $ret = [];
  foreach ($i as $object) {
    $ret[] = $callback($object);
  }
  return $ret;
}

$importer = new Importer(new MyMapper());

$my_objects = $apply([$importer, 'mapData'], $iter_of_objects);

Immutable variables

• Once set, may not be changed
• Allows for memory optimization
• Reduces SAD
• State is where bugs come from
• Forces small functions

Value Objects

• Easier testing
• Less SAD
• Often easier to read
• Reuse an object safely

Problems with mutation

function foo(Something $a, Formatter $formatter) {
  $bar = get_bar($a, 'bar');
  $formatted = $formatter->format($a);
  $a = make_changes($a, $bar);
  Output::send($formatted);
}
$a = new Something();
$a->bar = 'value1';

foo($a);
print $a->bar . PHP_EOL;

lulz

Memoization

• Fancy name for result caching
• Pure functions are pure: Same I, same O
• You've probably done this before...

Memoization

function expensive($key) {
  static $keys = array();

  if (empty($keys[$key])) {
    $keys[$key] = /* some expensive operation */
  }

  return $keys[$key];
}

Memoization

$factorial = function($a) use (&$factorial)  {
  print "Called function with $a" . PHP_EOL;
  if ($a == 1) {
    return 1;
  }
  return $a * $factorial($a - 1);
};

print "Result: " . $factorial(3) . PHP_EOL;
print "Result: " . $factorial(4) . PHP_EOL;

Called function with 3
Called function with 2
Called function with 1
Result: 6
Called function with 4
Called function with 3
Called function with 2
Called function with 1
Result: 24

Memoization

function memoize($function) {
  return function() use ($function) {
    static $results = array();
    $args = func_get_args();
    $key = serialize($args);
    if (empty($results[$key])) {
      $results[$key] = call_user_func_array($function, $args);
    }
    return $results[$key];
  };
}

$factorial = memoize($factorial);

print "Result: " . $factorial(3) . PHP_EOL;
print "Result: " . $factorial(4) . PHP_EOL;

Called function with 3
Called function with 2
Called function with 1
Result: 6
Called function with 4
Result: 24

What about objects?

interface FancyInterface {
  public function compute($key);
}
class Fancy implements FancyInterface {
  public function compute($key) { }
}

class FancyCache implements FancyInterface {
  public function __construct(FancyInterface $wrapped) {
    $this->wrapped = $wrapped;
  }
  public function compute($key) {
    if !($this->cache[$key]) {
      $this->cache[$key] = $this->wrapped->compute($key);
    }
    return $this->cache[$key];
  }
}

$fancy = new FancyCache(new Fancy());
$fancy->compute();
$fancy->compute();

Memoize any callable

interface FancyInterface {
  public function compute($key);
}
class Fancy implements FancyInterface {
  public function compute($key) { }
}

$f = new Fancy();
$callable = [$f, 'compute'];
$f_cached = memoize($callable);

// And it really really works.
$f_cached($key);

Currying

Haskell Curry

1900-1982

Yet another crazy smart mathematician

Currying

Splitting a multi-parameter function
into multiple single-parameter functions

A special case of partial-application

Partial-application

$add = function ($a, $b) {
  return $a + $b;
};

$add = function ($a) {
  return function($b) use ($a) {
    return $a + $b;
  };
};

$add1 = $add(1);
$add5 = $add(5);

$x = $add5($y);

$adder = $add(get_config_value('increment_amount'));
$x = $adder($y);
$values = array_map($adder, $array);

Practical Partials

function partial($func, $arg1) {
  $func_args = func_get_args();
  $args = array_slice($func_args, 1);

  return function() use($func, $args) {
      $full_args = array_merge($args, func_get_args());
      return call_user_func_array($func, $full_args);
  };
}
$date_formatter = partial('date', 'Y-m-d h:i:s');
print $date_formatter(1372636800);

2013-07-01 00:00:00

$dates = [1372636800, 1372896000, 1383004800,1384009200];

print implode(PHP_EOL, array_map($date_formatter, $dates)) . PHP_EOL;

2013-07-01 00:00:00
2013-07-04 00:00:00
2013-10-29 00:00:00
2013-11-09 15:00:00

Algorithm-first design

Purity is awesome

Think in terms of what, not how

(You should be doing that anyway)

Separate the what from how

(You should be doing that anyway)

Encapsulate your impurities, like I/O

(You should be doing that anyway)

State is where bugs come from

(Does that make me an enemy of the state?)

Functional programming isn't a language

It's just good code