@Crell

• Senior Architect, Palantir.net
• Drupal Association Advisor
• Web Services & Context Initiative Owner
• Co-Author,
  Drupal 7 Module Development,
  Packt Publishing
• Architectural Gadfly
• Nerf Gunslinger

What we do

Warning, hard core geek action

Please pardon the nerd

But first, a little history...

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

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 defines
how a program should work.

Declarative Programming

Declarative Programming defines
what a program should accomplish.

John Backus

• 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

Algorithm-first

Functional Programming

Functional Programming

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

Pure functions

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

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

Benefits

• Easy testability
• Thread-safe
• Self-evident
• Idempotent

First-class functions

• Functions can be a variable
• Functions can be a parameter
• Functions can be a return type

      $function = function($value) {
        return $value * 5;
      };
      $function($a);
    

Benefits

• Strategy pattern
• Partial evaluation / Currying
• Lazy-evaluation

Immutable variables

• Variables may not change value
• New function, new scope

Benefits

• Don't worry about data changing out from under you
• No need to copy
• Forces stateless-think

Recursion

• "To understand recursion you must first understand recursion."
• Function that calls itself
• Can replace loops

      function factorial($a) {
        if ($a == 1) {
          return 1;
        }
        return $a * factorial($a - 1);
      }
    

Benefits

• Divide-and-conquer
• Stateless

Put it all together

The Fibonacci series

      function fibonacci($a) {
        if ($a == 0) {
          return 0;
        }
        if ($a == 1) {
          return 1;
        }
        return fibonacci($a - 1) + fibonacci($a - 2);
      }

      $fib = fibonacci(5);
    

Strictly functional languages

• ML
• Haskell
• Erlang
• Many others...

Functional PHP

<troll>PHP is as functional as LISP</troll>

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

First-class functions in action

$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 ($card1->value == $card2->value
          || $is_wild($card1)
          || $is_wild($card2));
};

$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->conn_info);
};
$container->conn_info = function() { return array('user' => 'me', 'pass' => 'hi'); };

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

    

Hey, look, a Dependency Injection Container!

Lexical scoping

Lame...

function double($a) {
  return $a * 2;
}
function something_important(array $arr) {
  $arr = array_map('double', $arr);
  // ...
}
  

function multiply($a) {
  return $a * $GLOBALS['factor'];
}
function something_important(array $arr, $factor) {
  $GLOBALS['factor'] = $factor;
  $arr = array_map('multiply', $arr);
  // ...
}
    

function something_important(array $arr, $factor) {
  $arr = array_map(function ($a) use ($factor) {
    return $a * $factor;
  }, $arr);
  // ...
}
    

Drupal example

  public function onKernelControllerLegacy(FilterControllerEvent $event) {
    $request = $event->getRequest();
    $router_item = $request->attributes->get('drupal_menu_item');
    $controller = $event->getController();

    // This BC logic applies only to functions. Otherwise, skip it.
    if (is_string($controller) && function_exists($controller)) {
      $new_controller = function() use ($router_item) {
        return call_user_func_array(
          $router_item['page_callback'],
          $router_item['page_arguments']);
      };
      $event->setController($new_controller);
    }
  }
  

Currying

Haskell Curry

1900 - 1982

Yet another crazy smart mathematician

Currying

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

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

$adder = $add(variable_get('increment_amount'));
$x = $adder($y);
    

Partial-application

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

$adder = $add(variable_get('increment_amount'));

$values = array_map($adder, $array);
  

Memoization

• Fancy name for result caching
• Pure functions are pure: Same I, same O
• Drupal does this

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
    

Pure functions are awesome!

You must separate your logic from your I/O!

You should be doing that anyway...

The Functional Way(tm)

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

Fold

• "Analyze a recursive data structure and recombine through use of a given combining operation the results of recursively processing its constituent parts, building up a return value."
  --Wikipedia
• Iterate over a list and turn it into a single result

•       $sum = sum([1, 2, 3, 4, 5]);
        

•       foreach ($array as $element) {
          $result = sum($result, $element);
        }
        

•       array_reduce($array, $function);
  
        $initial = array_shift($array);
        array_reduce($array, function ($result, $item) {
          return $result + $item;
        }, $initial);
        

Filter

• Reduce a dataset to relevant elements
• Similar to Map (apply process to set in parallel)

•       $result = array_filter($array, $filter_function);
        

•       $array = [1, 2, 3, 4, 5, 6, 7];
        $result = array_filter($array, function ($val) {
          // Only odd numbers.
          return ($var & 1);
        });
        

•       $array = [0, 4, -4, 'foo', FALSE, NULL];
        $result = array_filter($array);
        // [4, -4, 'foo']
        

The take aways...

• Pure functions are awesome... most of the time
• Separate purity from impurity
• Anonymous functions rock. Don't let anyone tell you different.
• Think in logic, not state.