Two views of computing

Alonzo Church

1903-1995

• Lambda Calculus
• Relationship between math functions

Alan Turing

1912-1954


• Turing Machine
• An abstract state machine

Von Neumann Architecture

John Von Neumann

1903-1957

• Mathematician, Physicist
• Set theory, Operator theory, quantum theory, nuclear physics...

• ENIAC, 1948
• EDVAC, 1949
• Real-world implementations of a Turing Machine!

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
• Immutable variables
• Higher-order functions / First-class functions

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

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

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 ($c1, $c2) use ($is_wild) {
  return ($c1->value == $c2->value || $is_wild($c1) || $is_wild($c2));
};

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

Where have we seen this before...?

Delayed execution

use Symfony\Component\HttpFoundation\StreamedResponse;

class MyController {
  public function helloCsv() {
    $lots_of_data = get_lots_of_data();

    $response = new StreamedResponse();
    $response->headers->set('Content-Type', 'text/csv');

    $response->setCallback(function() use ($lots_of_data) {
      foreach ($lots_of_data as $record) {
        print implode(', ', $record) . PHP_EOL;
      }
    });

    return $response;
  }
}
            

Unordered dependencies

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

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);

            

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);

$result = array_map([$obj, 'aMethod'], $array);
            

foreach(), but separates application from loop

Declarative PHP

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

function apply($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);
            

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

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

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

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

$x = $add5($y);

$adder = partial_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(1372914000);
            

2013-07-04 12:00:00

Bring it all together

Layering functions: Revisited

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

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

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

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

Testable functions

function is_equal($a, $b) {
  return $a->value == $b->value && $a->suit == $b->suit;
}

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

$wild_checker = partial('is_equal', new Card('5H'));
$pair_checker = partial('find_pair', $wild_checker);

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

$cached_checker = memoize($pair_checker);

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

Build from atomic pieces

function is_three_kind($find_pair, array $cards) {
  return $find_pair($cards[0], $cards[1]) && $find_pair($cards[1], $cards[2]);
}

$three_checker = memoize(partial('is_three_kind', $pair_checker));
            

And keep on going...

Pure functional languages have this advantage: all flow of data is made explicit. And this disadvantage: sometimes it is painfully explicit.

—Philip Wadler

Take-aways

• Make data flow explicit (90% of the time)
• Pure functions enable awesomeness
• Think in terms of what, not how
• Separate the what from how
• Isolate your impurities, like I/O
• Single-Responsibility Principle on steroids
• State is where bugs come from

Functional programming isn't a language

It's just good code