Accumulator passing

Intent

Use of an accumulator variable to allow the finer control over the assembly of the final result of an algorithm

Motivation

We want to use method-chaining, but we need to return values from some of the methods

Implementation

Use an accumulator variable

Example

a simple IFS( iterative function system )
x(t+1) = x(t) + f[random(1..i)]( 1/(t+1) )
note: the implementation is quite naive and not foolproof at all.

<php
class example {
  private $ifs = array( 'sin', 'cos' );  

  function x( &$acc ) {
    $acc['t'] += 1;
    $acc['x'] = $acc['x'] + $this->ifs[ rand(0,1) ]( 1/ $acc['t'] );
    return $this;
  }
}

$ex = new example();

$something = array('t'=>0, 'x' => 0 );
$ex->x($something) -> x($something) -> x($something);
print 't: ' . $something['t'] . ' x: ' . $something['x'] . "\n";
?>

and when you run it:

vlado@cow:~/php design patterns$ php  php accumulator_passing.php
t: 3 x:1.34692254127
vlado@cow:~/php design patterns$ php accumulator_passing.php
t: 3 x: 1.64809122021
vlado@cow:~/php design patterns$ php accumulator_passing.php
t: 3 x: 2.66401049301

Closure

Intent

Close over the free variables of a function. Save the state for future use.

Motivation

We want to maintain the history of computation, an maybe save and reuse the computation

Implementation

php 5.3 implements anonymous functions, albeit verbously, with explicit declaration of variables to close over

Example

$y = ...;
x = function() use ($y){
   ....
}

Note

In some sense, closures and objects are dual, compare behaviour with state and state with behaviour

Yet another note:

Alternatively have a look at this implementation or my emulating closures in php blurb

Control abstraction

Intent

Replace loops with named function

Motivation

find the best value in an array

Implementation

A simple loop over the array, keeping track of the best element value and index

Examples

function find_best($better, $coll) {
  foreach($coll as $key=>$value) {
    if( is_null($best) || $better($value,$best[1]) ) {
      $best = array($key, $value);
    }
  }
  return $best;
}

Coroutines (generator based)

Intent

Abstract out naturally parrallel evaluation

Motivation

Merge two functional streams

Implementation

The coroutines can be implemented using generators. The example shows an example application

Examples

//if gen and gen2 are generators
function merge_data() {
  try {
    do {
      $data[] = 10*gen() + 5 + 4*gen2();
      ...
    } while( some_condition( ... ) );
  } catch ( $e ) { .... }
  return $data;
}

Curried function

Intent

Produce a new function, by caching one or more of the original arguments

Motivation

Very often we use a function with one of it's complex arguments over and over again. We want to speed the avaluation.

Implementation

return an anonymous function

Example

$x = function($y) {
   return some_function($x,$y);
}

Dynamic dispatch

Intent

dispatch the control based on the environment, but delay enumerating the cases

Motivation

we don't know at the time of writing the code what are the different cases to dispatch on

Implementation

(nearly) invisible in php

Examples

$case($arg);
$object->$method($arg);
call_user_func($calleable, $arg1, $arg2);


Note

A more elaborate form of dynamic dispatch is Method Chaining

Dynamic loading

Intent

Keep working set small and mainatin fast start time by loading features as required

Implementation

use __autoload()

Example

function autoload( $classname) { list($path,$file) = loadpath( $classname ); require_once "$path/$file"; }

Notes

• we are loading a file, based on some conventions interpreted in loadpath
• This can be used to implement module-like system, but the lack of subclasses or similar tools makes the 'module' bindings always transparent

Facade

Intent

provide a simple interface to a subsystem.

Motivation

a complex system can have many parts that need to be exposed, but it could be confusing ergo - provide a simple interface to the system. For example a read-evaluate-print process of an interpreter

Implementation

Hide the construction of the required objects inside the facade

Example

class rep_facade {
   function __construct() {
     $this->firewall = new firewall();
     $this->reader = new reader();
     $this->evaluator = new evaluator();
     $this->printer = new printer();
   }

   function rep($text) {
     $text = $this->firewall($text);
     $ts   = $this->reader($text);
     $result = $this->evaluator($ts);
     return $this->printer($result);
   }
 }

Complications

The lack of modules and/or nested classes in php means that this is a comfort interface, not an enforcing interface

Factory and Abstract Factory

Intent

Creating objects (products) without specifying the exact class(type) of object that will be created.

Motivation

We want our program logic to determine the type of logger to be used

Implementation

Classes in php can be considered (weak) runtime objects, the nessessity of the dual factory/product heirarchy is diminished

Invisible in php

Might still want factory objects to handle families of similar objects

Examples

$product_type = which_product(); $probuct = new $product_type();

Fluent Interfaces/ Method chaining

Intent

return the next context of computation, enable simple and flexible sequencing of computation

Motivation

We want to provide a small domain specific language to improve the readability of the code

Implementation

return the next expected object (state)

Examples

class fluent_class {
  var $state_var;
  function self_next( $arg ) {
    ....
    return $this;
  }
  function other_next( $arg ) {
    ....
    return $this->another;
  }
}

$obj = new fluent_class();
$obj->self_next(1)
    ->self_next(2)
    ->other_next(3)
    ->something_else(4);

Note

This is an awkward idea to explain in words. Essentially you are delegating the desision what is the next object in the chain to the executable methods. It probably should be combined with weaving the values, which we would otherwise return, using accumulator style passing, or some other store method.

Have a look at Jonnay's post for better and more sensible code examples and the Fluenter class.

I sometimes look at this as the imperative "version" of continuation passing, but let's not even get there.

Generator (iterator protocol based)

Intent

Define a (stream like) value producer

Motivation

We want to be able do define functional streams

Implementation

Any object implementing an iteration protocol (interface) can be a base for a generator.

Examples

//a generator implemented with iterators
function generator($it=null, $cb=null) {
  static $itor;
  static $callback;

  if(!isset($itor)) ($itor = $it; $callback=$cb; }

  if($valid()) { $out = $callback($current); $next(); return $out; }

  //or if you are not sure about the type of the above callables ($valid, $next,..)
  if( call_user_func($valid) ) { 
    $out = call_user_func( $callback, $current); 
    call_user_func( $next ); 
    return $out; 
  }

  else throw( new some_exception );
}

Generic function

Intent

A high-order function/algorithm implementation

Motivation

a generic select->update->eval function with one argument, whose instances/application differ for different (argument, result) types required

Implementation

Simply cache the result into an array or other appropriate type

Examples

class algorithm { var $parameters=array(); function __construct( $select, $update, $eval) { $this->parameters['select'] = $select; $this->parameters['update'] = $update; $this->parameters['eval'] = $eval; } function run($arg) { $selections = $this->parameters['select']($arg); $updates = $this->parameters['update']($selections); return $this->parameters['eval']($updates); } } //or with more syntax, not the parametrisation function algorithm( $select, $update, $eval ) { $args = func_get_args(); $args = array_slice($input, 3); $selections = call_user_func_array( $select, $args); $updates = call_user_func_array( $update, $selections); return call_user_func_array( $eval, $updates); }

Hooks

Intent

Build a function/method from multiple components

Motivation

Very often we need to decouple or delay definitions until run time

Implementation

Implement a methods that allows executing a set of functions at predefined times

Example

class hooks {
  private $cache = array();

  function run( $func, $arg ) {
    foreach(array('before','at','after') as $hook)
      foreach($this->cache[$func][$hook] as $f) { $f($arg);  }
  }

  function hook($hook, $func, $cb) {
    $this->cache[$func][$hook][]=$cb
  }

  function before($func, $cb) {
    $this->cache[$func]['before'][]=$cb
  }
  
  function at($func, $cb) {
    $this->cache[$func]['at'][]=$cb
  }
  
  function after($func, $cb) {
    $this->cache[$func]['after'][]=$cb
  }
  
  function around($hook, $func, $cb) {
    $this->cache[$func]['around'][]=$cb
    $this->cache[$func]['after'][]=$cb
  }

}

//and usage
$hs = new hooks();
$hs->hook('before','label','before_a_func');
$hs->hook('at','label','core');
$hs->run();

//or using the individual methods
$hs = new combinator();
$hs->before('label','before_a_func');
$hs->around('label','tracer');
$hs->run();

Interpreter

Intent

given a language, interpret sentences

Motivation

request (path) parser in a web application

Implementation

• a class for each expression type, interpret method for each type
• a class and object to store state (context)
• each expression class is resposible for building it's own parse tree

Example

class tag {
  //ts is the current token stream
  //this is a variant of partial evaluation
  var $args;
  function __construct( &$ts) { 
    while( not_class($arg = next($ts)) ) {
      $this->args[] = $arg;
    }
  }
  //evaluate the 
  function run( &$context) { ... }
}

//example usage
$ts = array("tag","php","design patterns");
$op = current($ts);
$prog = new $op();
$prog->run( new context() );

notes

• the expression types can be possibly parametrized if their run an construct methods follow, particular 'typical' shapes
• not_class is a language dependent function

Iterator (based on protocol method)

Intent

Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation.

Motivation

We want to be able to postpone the effects of a computation, for example delay printing from a function to webserver output until whole web-page is assembled

Implementation

This is an alternative implementation based on protocol method, rather than interfaces

Examples

class alt_iterator {
  private $st = array();

  function next() { ... }
  function current() { ... }
  function valid() { ... }
  //... put the rest here

  function protocol() {
    return array(
             array($this,'next'),
             array($this,'current'),
             array($this,'valid'),
	     .....
	     );
  }
  
}

//an example use
function do_them($itor, $callback ) {
  list($next, $current, $valid, ...) = $itor->protocol();
  while($valid) {
    $callback( $current );
    $next();
  }
}

Lazy evaluation

Intent

A function/method call results in a promise for future computation

Motivation

We want to be able to postpone the effects of a computation, for example delay printing from a function to webserver output until whole web-page is assembled

Implementation

Instead of evaluating a function, we deliver a promise - a callable with no arguments, which when forced is executed

Examples

//for simplicity handle only functions with one argument 
class promise { 
  private $args = null;
  private $func = null;
  function __construct($func, $args) { 
    $this->func = $func; 
    $this->args = $args;
  } 
  function evaluate() { 
    call_user_func($this->func,$this->args);
  } 
} 

function delay( $func, $arg ) {
  return array(new promise($func, $arg), 'evaluate'); 
}

//example use
...
$chunks[] = delay('a_printer',$a_variable);
...
foreach($chunks as $chunk ) {
  if(is_callable($chunk)) {
    $chunk(); //force - this does it's own printing in this example
  } else {
    print $chunk;
  }
}

Memoization

Intent

Cache result after computing it.

Motivation

Eliminate repeated database queries

Implementation

Simply cache the result into an array or other appropriate type

Examples

with functions

function db_get_something( $x ) {
  static $cache = array();

  if(empty($cache[$x])) { 
    $cache[$x] = //some db query result;
  }
  return $cache[$x];
}

with objects

class db_get_somethning {
  private $cache = array();

  function func() {
    if(empty($this->cache[$x])) 
this->cache[$x] = //some db query result;
    return $this->cache[$x];
  }
}

Complications

cache lifetime, size, invalidation

Nested scope

Intent

Create a composable runtime hierarchy of data and behaviour

Motivation

We want dynamic means of modifying complex runtime structures

Implementation

Use php magic to dynamically dispatch requests to parent methods

Examples

class scope {
  var $parent;
  function __call( $name ) {
    if(isset($parent[$name]) { return $parent[$name](); }
    throw( new someException() );
  }

  function let( $name, $value ) {
    if(is_object($value)) { 
      //hygiene
      if(isset($this->$name)) { $this->$name->parent = null; }
      $this->$name = $value;
      $this->$name->parent = $this;
  }
}

//alternative let
function let($parent, $name, $class) {
  $parent->$name = new $class();
  $parent->$name->parent = array($parent,$name);
}

?>

Notes

• A concept related to and very often mistaken (mixed) (by me) with (for) closures
• the let method can be folded into __set if we want this behaviour to the default for assignments to object fields

Observer

Intent

When an object changes, notify all interested parties

Motivation

events, synchronisation, ...

Implementation

Use hooks pattern at and after to implement the observer

No implementation needed in the Subject class

Example

//initialisation
$hs = new hooks();
$observer = new interested_party();
$change_method = array($object, 'setter');

//setup change point(can be done externally from $change method)
$hs->at('change', $change_method);

//express interest
$hs->after('change', array($obesrver, 'callback'));

$hs->run($arg);

Note

The precise implementation of the hooks may differ, depending on functionality, abstraction, sugar, ... Have a look at the drupal hooks as well.

Protocol method

Intent

Implement a set of related operations

Motivation

Define different iteration strategies, across different inheritance hierarchies, similar to interface, but allows for differnt fuctions to implement the interface specification

Implementation

Define a method returning the required functions by the interface

Examples

class alt_iterator {
  private $st = array();

  function next() { ... }
  function current() { ... }
  function valid() { ... }
  //... put the rest here

  function protocol() {
    return array(
             array($this,'next'),
             array($this,'current'),
             array($this,'valid'),
	     .....
	     );
  }  
}

//an example use: iterator protocol
function do_them($itor, $callback ) {
  list($next, $current, $valid, ...) = $itor->protocol();
  while($valid) {
    $callback( $current );
    $next();
  }
}

Proxy

Intent

Provide a surrogate or placeholder for another object to control access to it

Motivation

We want to provide a wrapper around a set of classes to unify their access protocols

Implementation

• Provide a wrap method
• intercept calls to the wraper object and forward them accordingly, may change the protocol

Example

class Fluenter
{
        private $obj;

        function __construct($obj)
        {
                $this->obj = $obj;
        }
        static function MakeFluent($obj)
        {
                if ($obj instanceof fluent)
                        return $obj;
                else
                        return new fluenter($obj);
        }
        function __call($method, $args)
        {
                $result = call_user_func_array(array($this->obj, $method), $args);
                if (is_null($result))
                        return $this;
                else if (is_object($result) and ($result instanceof $fluent))
                        return $result;
                else
                        throw new RuntimeException(
                                                "Fluent::__call called method $method ".
                                                "and expected a null return or a non-fluent object, ".
                                                "got (".gettype($return).") $return instead.");
        }
}

notes

• This code is an unaltered copy from Making Fluent Interfaces Readable in PHP, I hope Jonnay doesn't mind that
• You might want to check out fluent interfaces( method chaining) and accumulator passing

Singleton

Intent

enforce the existance of a single object of a specified type

Motivation

Application needs one, and only one, instance of an object. Additionally, lazy initialization and global access are necessary.

Implementation

• use the memoize pattern to implement a singleton

Examples

with functions

function &get_instance() {
  static $instance;
  if(empty($instance)) {
    $instance = new SingletonClass();
  }
  return $instance;
}

with objects

class Singleton {
  private static $instance = null;

  private static function __construct() {  }

  public  function get_instance() {
    if(empty(self::$instance) { self::$instance = new Singleton(); }
    return self::$instance;
  }
}

Complications

The function based version implements the code equivalent of security by obscurity. It doesn't really enforce a single instance of a class, but a revised version can be used to abstract out singleton creation

State

Intent

Allow an object to alter its behavior when its internal state changes.

Motivation

An article in a typical editorial workflow exibits different behaviours in different publication stages. We want an object that hides the complex logic.

Implementation

Similar to the strategy pattern. Need to handle state change and behaviour change.

Examples

$new_state="edit"; $new_protocol="edit"; //change the behaviour list($view,$update,$get, $set) = $object->protocol($new_protocol);

Related patterns

Protocol Method, Builder, Strategy

Note

Too many different implementations exists. This means that there is probably a need to clean up the intent.

Strategy Pattern

Intent

Select algorithms on-the-fly at runtime.

Motivation

Write different loggers

Implementation

• a strategy is a variable whose value is a function or method
• No need for separate classes that differ in a few well understood ways
• Strategy objects are not a no-no, but there is no inherent need for separate classes for each strategy instance

Examples

with functions
$logger = "a_logger_function"; $logger($message);

with objects
$strategy = "a_logger_class"; $log_object = new $strategy; $log_object->log(message);

Problems of active record and friends

After a lot of silence caused by lot's of work (good, my bills are happy) and a continuous diversion into scheme, haskell, dylan and other interesting languages, I'm back into php speaking land. Funny feeling that. So here comes the beginning of something I've been continuously rubbing my (leftovers of) brains against.

copout This is not php specific, but since it discusses frequent problems occuring in php apps, I've labeled it with as php related as well. Makes it easier maintaining the site you see.

I have a problem with active record as a pattern. It is a logical one. Essentially it turn a (SQL) database row into an object. The class of the object represents the SQL table or view. Of course you can add behaviour to those classes and objects, i.e. activating those records.

All that is nice and dandy, but when you start talking about relations and constructing dynamically queries and corresponding objects, we start hitting the limitations of what I will call from now on the naive active record.

The problem is not trivial at all. It boils down to how to make peace between the host language type system (for example classes) and the SQL's dynamic compound types - the relations expressed as SELECT variants for example. It gets even harder when we decide to reverse the direction, so that we actulally want to update the database. Yuk! As though somebody actually does that!

A first look into the meaning of SQL higher types

What are the SQL tables, views and joins?

Records actually. The sql tables are simple records with named fields. The name of the record type is the name of the table. The type definition is the table definition. In SQL you have the usual projectsion operators, like table.filed_name. More interestingly you can actually construct new temporary record types. For example in the statement:
SELECT n.one, n.two, n.three FROM n;
We construct a new (anonymous) type whose slots inherit the names from the record where they are copied from. Well, you could assign a different name if you so desire.

Joins

If we think of tables as record types and rows as records, then JOIN is an operator on record types not records. It is more complicated than that, but for the time being let's stick to this meaning.

Consider the following example:
A::{ a, b, c} JOIN B::{b, c, d} -> {A.a, A.b, A.c, B.b, B.c, B.d}
as used in
SELECT A.*, B.* FROM A,B
;; alternatively
SELECT A.*, B.* FROM A CROSS JOIN B;


The result type is a union, or more precisely a cartesian product, of the arguments of the JOIN op. This resembles multiple inheritance, with a crucial difference - you preserve all ops of the parents (the tables arguments of the JOIN). This causes one of the majour problems with active record - we don't have a language, let alone php doing it, that allows us to naturally model this using the language itself, rather than constructing strange hacks ourselves. The opposite direction - folding inheritance and friends into SQL meets similar kinds of problems.

The rest of the JOINS are essentially specialised products (unions) which can be modelled with some extra operators on types, which are dutifully skipped for the time being.

Views are 'named' joins, so they are not much more interesting. What is interesting is the fact that you can use anywhere, where you can use tables.

So what do we have? Some kind of a mental model, meta-language, if you like, expressing how to construct records, or what are these records made of, (which is the same). If we were to implement that language, mapping as much as possible native language constructs, we would have the means to reason about our objects and automagically construct database queries of the appropriate kind. Maybe even optimise the queries with respect of what is required for our application, rather that simply relying on the generic SQL optimiser or a handy local SQL guru.

Active record comes to play after we know the record. The question is how to get to that point. The answer lies in the tools of the native language. I'll describe later some possible approaches in php, probably not good, but you are welcome to improve them and tell me how to do it better.

First sketches

Ok, Let's recap:

• Relational database (SQL) tables are records. We can view them (in our heads) as record type definitions.
• JOINS define (some kind of) derived union types.
• SQL CROSS JOINS are full cartesian products, i.e. union types where no name folding/aliasing is done by the imaginary type system

How can we model that in php?

Classes (and objects) are records. Arrays are records too. Both are candidates for doing the job. We need to be able to somehow represent this (meta) type information and manipulate it. The aim is to have a natural feeling/looking abstraction of the database in php. It should be flexible enough, for us to modify the relations at runtime, as we need. It should allow us in the long run to have a near optimal speed and not too much complications in the end code. That is a tough cookie.

pre 1: table A is - A::{ a, b, c}
pre 2: table B is - B::{ b, c, d}
case 1: view C is - C::{ A.a, A.b, A.c, B.a, B.b, B.c } , i.e. a cross join of A & B
case 2: view D is - D::{ A.a, A.b, A.c, B.c | A.b = B.b }, same as above with a guard

Let's use the above cases as basis for reasoning about building our php models. We can extend them with extras later.

table as active record


class A_Record {
var a,b,c ;
.....
}
function load_A {
$result = db_query('SELECT * from A');
while( $a[] = new( db_get( $result) );
return $a;
}


Skipping most of the details, the above code outlines the basic idea of aquiring/loading into memory all values of type A, make sure it is not an endless loop, the real life implementation of the database abstraction layer you are using. The methods of the A_record class will implement the behaviours of these records, making it an active record. load_A is external to the class for obvious reasons - it is a type property, as opposed to a class one. It belong to the type. We could, in theory make it a static method, but it's not clear what benefits this will give. At least for now.

First attempts at joins

//case 2: C = A JOIN B -> C::{ A.a, A.b, A.c, B.a, B.b, B.c }
class C_Record {
var a_a, a_b, a_c;
var b_a, b_b, b_c;
...
}
//load similar to previous example, just add sql join


The problems with this approach are that it is hardcoded, inflexible, hard to maintain.
The good side is that it is simple and straightforward. Assuming that we can recognise (and we can using reflection) we can use a polymorphic call to load.

Let's go for take 2 (we can't use inheritance =( ):
class C_record {
private A; //we need to ensure that only variables of A_record can end up here
private B; //we need to ensure that only variables of B_record can end up here
....
//use your bag of tricks to keep objects of this class type safe:
// mostly _call(), _get(), _set() and various design patterns :)
}

Essentially we implement the association (join) operation using a special class. This is fine, but we now introduce an indirection via A and B and the extra calls to _call, _get or _set, which will slow down the whole thing.

Time for take 3.
$op['product'][] = 'A_record';
$op['product'][] = 'B_record';
....
$res = op_eval($op);
// Array('fields' => Array( ... ),
// 'load' => 'SELECT a.*, b.* FROM a,b',
// 'insert' => ..., 'update' => ... );

Basically we (somehow) build the type ops AST, produce load, update, insert, delete, .... SQL code. Cons - slow, but we can cache the result array for reuse, which will make the whole execution times faster, at least competitive with takes 1&2. Pros - flexible.

Take N. I might add more of these later.

The choice depends on the problem and flexibility at hand. There is no 'best' solution.