Monthly Archive for July, 2014

PHP Recursion: The Fundamentals

Published on July 27, 2014 by Bill Sanders in Algorithms, Beginning PHP OOP, Iterating through Objects and Recursion. 0 Comments Tags: , , , , , .

recursionNailing Down Recursion

On more than one occasion on this blog, I’ve wandered off into the land of operations to examine recursion. In looking over past recursion posts and recursion discussions on the Web, I found a lot of bad information, partial information and helpful information. Likewise, I consulted some programming books, especially Robert Sedgewick’s and Kevin Wayne’s 2011 edition (4th) of Algorithms. Also, I found a great and detailed article on recursion by David Matuszek. Robert Sedgewick and Kevin Wayne are professors at Princeton and David Matuszek is a professor at the University of Pennsylvania. Not surprisingly, their focus is on larger conceptual and mathematical issues surrounding computer programming and the role that recursion plays in that context.

However, I also wanted to get a non-academic view from developers, and I found two very good posts on Martin Fowler’s Refactoring site by Dave Whipp and Ivan Mitrovic. For those of you not familiar with Martin Fowler, he’s written books and articles on computing and is one of the founders of the Agile Movement in program development. He is a primary consultant to businesses and institutions who want to optimize their programs for efficiency and effectiveness. Among PHP developers the Agile approach to programming is quite popular.

What is Recursion?

In a nutshell,

Recursion in computer programming occurs when a method calls itself.

While that definition is a starting point, a more detailed and useful one is provided by Sedewick and Wayne. They spell out three features in a good recursive method:

  1. A recursion begins with a conditional statement with a return. This is called the base case (or halting case), and it supplies the criterion which will stop the recursive operation.
  2. Recursive calls to sub-problems converge to the base case. Each call must bring the values in use closer to the halting conditions.
  3. Called sub-problems should not overlap.

You can find a lot of discussions and debate about the definition and use of recursive methods in programming, but the fundamental fact remains that recursion is one of the central ideas in computer science. As a professional programmer, you need to know about recursion and you should use it. This does not mean you have to use it all the time, but you need to understand what you can do with it and its limitations and advantages. Start off with the following implementations and download the code:
PlayDownload

In PHP and other computer programs, recursion and the need for it arise all the time. So you should have some sense of how to use it and when. Like other computing concepts, you may not use it all the time, but when you need it, you really need it.

World’s Easiest Recursive Function

To get started we’ll look at a simple recursive call. It is a version of what kids do when you take them on a trip. (And what you did when you were a kid on a trip…) You’d ask the reasonable question,

Are we there yet?

If you kept calling the same query as soon as you’d received a negative response, it has recursive-like qualities. The “No!” is the base case, and the car moving to the objective (“there”) is the change that occurs between each call to the query, “Are we there yet?”

?View Code PHP 
//Recursion.php
< ?php
class Recursion
{
    private $ask="Are we there yet?
";
    private $answer="No!
";
    private $counter=0;
    public function __construct()
    {
        $this->thereYet();
    }
    private function thereYet()
    {
        //Base case (also called 'halting case')
        if($this->counter < =10)
        {
            echo $this->ask;
            echo $this->answer;
            $this->counter++;
            //Recursive call
            return $this->thereYet();
        }
        else
        {
            echo "
" . $this->ask;
            $this->answer="Yes! We are there!" ;
            echo $this->answer;
        }
    } 
}
?>

The return value calls for a recursive event inside the thereYet() method. With each call, the counter variable’s value moves toward convergence with the base case. After 10 calls, the counter variable exceeds the base case and no more self-calls are made by the thereYet() method.

While that example could be handled by iteration in a loop; it provides another way to accomplish a task. It’s easy to understand and meets the criteria set up for recursion. (Click below to see more.)
Continue reading ‘PHP Recursion: The Fundamentals’

PHP Bridge Pattern CMS

Published on July 21, 2014 by Bill Sanders in Bridge, CMS, How to Select Design Pattern, JavaScript and PHP, JSON and PHP, Loose Coupling and Static properties & methods. 0 Comments Tags: , , , .

bridgeCMSA Flexible CMS

The previous post on the PHP Bridge Design pattern shows how a Bridge pattern has two connected but independent interfaces to make design flexibility for different online devices. This post explores how that same flexibility extends to making a Content Management System (CMS). Most of the Bridge participants in the design are unchanged or only slightly changed.

The major change in the Bridge design pattern actually makes it more in line with the original intention of the Bridge. The RefinedAbstraction participant (RefinedPage) no longer includes concrete content for the page. Instead, it provides the parameters for a client to add the content. This change adds flexibility and gives the developer more options than the original StandardPage class.

Two UIs and Multiple Clients

In order to make a decent CMS, you need to have at least two UIs:

  1. An Administrative UI for previewing and adding new content
  2. A User UI for viewing but not changing content

In creating the Administrative UI (HTML5/PHP/JavaScript), I had to use two PHP clients. One client is to preview the new data entered by the admin and the other client is to store the new data (after previewing and possibly editing it). Figure I provides a general overview of the UIs and the Clients that will use the Bridge pattern for a CMS:

Figure 1: User Interfaces and Clients

Figure 1: User Interfaces and Clients

The Administrative UI (BridgeCMSAdmin.html) uses the BridgeCMSAdminClient class for displaying different content and the StoreDataClient class for storing the information in a JSON file. An important condition to remember is that when using JSON files, you need to make their permissions available for reading and writing. (See the Memento II post and the special mini-post on setting permissions on Raspberry Pi systems.) Thus, the need for two clients; one for previewing new material and another for storing it in a JSON file. A lot of files are involved in this CMS; so take a look at the two different UIs and download the files for everything:
PlayPlayAdminDownload

To use the Administrator Module, follow these steps in the listed order:

  1. Type in Header data, select a graphic from the drop down menu, and then type in text for the body.
  2. Click a Desktop, Tablet or Phone radio button and then click Preview Page
  3. When you have everything the way you want it, First click Transfer to Storage and next click Store Data
  4. Now click the Play button and see the page you created.

In the admin UI, I used a drop down menu with only three selections for the graphic file since only three were set up. However, it would not be difficult to upload graphics and their file names. (See the post on uploading graphics using the Template Method.)

The UIs and their Clients

The main feature in creating a CMS is the Administrative UI. It calls two different clients for dealing with previews and persistent data storage. Unless you’re planning on a fairly long body text entry, the JSON file works fine. Look at the code below, and you can see that one of the issues is that the data that is entered for the preview must be transferred to a different form. It transferring the data is a simple task with a little JavaScript. The following script is all it takes:

?View Code JAVASCRIPT 
function transferData(formNow)
{
    formNow.header.value = bridgeWork.header.value;
    formNow.graphic.value = bridgeWork.graphic.value;
    formNow.bodytext.value = bridgeWork.bodytext.value;
}

Stored in an external JS file, it was used only when the data was going to be stored; however, before storing it, it had to be transferred from the bridgeWork form to the dataStore form.

?View Code HTML 
< !DOCTYPE html>


    
    
    CMS Admin Bridge


    
Enter Update Data

    

         Header

        
        

        Enter the text for the body below:

        

        
Preview New Data

         Desktop

         Tablet

         Phone

        
    

 
    
Store New Data

    

        
        
        
        
        
    

 

Then using build-in PHP JSON json_encode() method, the data were placed into an array and stored in the JSON file. This was done using the StoreDataClient class:

?View Code PHP 
< ?php
class StoreDataClient
{
    private static $dataStorage=array();
    private static $jsonFile="content.json";
    //Client stores data
    public static function store()
    {
        if (isset($_POST['jsonstore']))
        {   
            self::setStore();
        }
      file_put_contents(self::$jsonFile,json_encode(self::$dataStorage,JSON_UNESCAPED_UNICODE));
    }
 
    private static function setStore()
    {
        //Pushes data from HTML to array
        array_push(self::$dataStorage,$_POST['header'],$_POST['graphic'],$_POST['bodytext']);
    }
}
StoreDataClient::store();
?>

Just in case you’re wondering why a single PHP client class was not used for both preview and storage, it’s simple:

OOP Principle: Each class should have only a single responsibility.

We don’t want to cram classes; so each responsibility has its own class. (Click below to see the other client and the rest of the CMS.)
Continue reading ‘PHP Bridge Pattern CMS’

PHP Bridge Design Pattern

Published on July 16, 2014 by Bill Sanders in Bridge and Design Patterns. 0 Comments Tags: , .

armeniaTwo Interfaces

The intent of the Bridge pattern is to decouple an abstraction from its implementation so that the two can vary independently. (GoF 151) If you don’t think about that much, it sounds like a good idea to keep an application from grinding its gears when a change is made in either the abstraction or implementation. The Freemans (Head First Design Patterns, pp. 612-613) have a great example—a universal remote control. The remote control is the abstraction and a TV set is the implementor. Concrete implementors are the different brands of TVs. As new technology arises, the remote control can be updated with new gizmos. Likewise, the TV sets can also be updated and different brands will have their own unique features. A good Bridge design will allow each to be changed without breaking the other. So far so good.

An Abstraction Has-A Implementor

About six years ago, I started looking at different Bridge design pattern examples. I ran into examples that were examples of something but did not seem to be Bridge patterns. (One was nothing more than a single interface with two different implementations. The coder explained, See, that’s a bridge. I sat there with question marks floating above my head like some cartoon character.) The GoF intent statement and Freeman example were quite clear. However, the Abstraction interface and the Implementor interface, either of which could be an abstract class or interface structure, were bridged by the abstraction having-a implementor. To fully understand a Bridge pattern, you need to understand the relationship known as a bridge between the Abstraction and Implementor participants. First, though, see what the results are by pressing the Play button and Download the files:
PlayDownload

For an overview, take a look at Figure 1. The top half is the structure laid out by The Gang of Four—the generic class diagram for a Bridge pattern. The bottom half is the PHP implementation that addresses a common issue: Variation in the content of a Web page and the structure of a Web page. By having two interfaces, either can change independently of the other. The example shows a Web page with variable content that is displayed in desktop and mobile devices.

Figure 1: Bridge Class diagrams

Figure 1: Bridge Class diagrams


One of the important features of the Bridge pattern turns out to be quite subtle and easily overlooked.

The key method (Operation()) in the Abstraction participant is a concrete one.

In the example for this post, the IPage abstract class includes the buildPage() method. The buildPage() method uses a concrete implementation of the Implementor participant, (IDevice). You can see how the method is implemented in the IPage abstract class:

?View Code PHP 
< ?php
abstract class IPage 
{
    //Low-level
    abstract function doDevice(IDevice $deviceNow);
    //High-level
    protected function buildPage()
    {
        echo $this->deviceSelected->buildDevice($this->header,$this->graphic,$this->body);
    }
    //Properties
    protected $header, $graphic, $body, $deviceSelected;
}
?>

As you can see, the abstract function doDevice() expects an IDevice object as a parameter. The $deviceSelected property is one that will be assigned a concrete Implementor (IDevice). So, in the sense that both an abstract reference using code hinting and a concrete use of an implemented IDevice are part of the IPage abstract class, it can be said to “have a” Implementor (IDevice). (Click below to see the rest of the Bridge pattern.)
Continue reading ‘PHP Bridge Design Pattern’

PHP For Academic and Practical Development: A False Dichotomy

Published on July 14, 2014 by Bill Sanders in Beginning PHP OOP. 0 Comments

AcademicPracticalA Dumb Argument

A few years ago Manuel Lemos wrote a post on the PHP Class blog about the wrong ideas that people have about PHP. It was largely in response to the general rejection of PHP by academics and others who hold themselves as the high priests of computing. It’s not that PHP is not taught in some universities, it’s just that getting a paper accepted at computer science conference in PHP is difficult. (By the way, Harvard University includes PHP in one of their introductory computer courses, and more than a few universities offer PHP as part of changing curricula that responds to the world around them.) Coming from academia myself, I’ve known CS faculty who act like teenage drama queens at the mention of PHP. However, I’ve also known academics who embrace PHP as they’ve come to realize that it is indeed an object oriented language and light years away from the original “Personal Home Page” intended for modest personal use. Besides, PHP is a server-side language and can communicate with an Internet-based data bases like MySQL and it’s open source.

The other side of the coin contains the legions of developers who have a job with a PHP-coded product to get out the door. They may not have a degree in computer science, or even a college degree of any sort. They have learned programming on their own and have settled on PHP as a language of choice. Generally, they also know HTML, JavaScript, CSS, MySQL and supporting Internet technologies. They see and use PHP as a practical tool to accomplish a set of goals. Their coding practices range from hacks to fully developed professional coding. Learning how to code is like learning how to write or do math; some do it well and some just enough to get by. Many such coders learn to code at work. Their job environment sets up the protocols for coding, and they follow the protocol whether they have a college degree or not. For example, one coder I know was working at a company whose new boss set up a Model View Controller (MVC) and showed everyone how to work with it. The coder learned MVC at work.

Same Goal; Different Paths

The stereotype of academics by non-academic coders is often one of fussy hair-splitters who accomplish nothing practical. The academics, on the other hand, see non-academic coders as hacks who throw together code that is a rat’s nest of statements that cannot be unraveled or re-used; they just hack out another rat’s nest. Their priorities center around an idiosyncratic and often eclectic collection of ideas, many of which are misguided or used out of context.

Both stereotypes, of course, are dead wrong. In fact, academics and practical computing have the same goals, and the goals are often from the same sources. Object oriented programming (OOP) has its origins in the practical realm of making large programming projects more manageable supported by both business and academic interests. For business, this means a more effective and efficient use of programmers’ time and the capacity to re-use the code and for programmers to work in teams that achieve a division of labor for faster development. The larger the project the more important this becomes. For academics, OOP represents a more efficient and effective programming paradigm. What’s the difference? Not much that I can see.

Different Roles: Programmers and IT Techs

suzyQprogrammerA while back my email was hacked through our university mail server. I was informed of the attack, and I had to go through the process of changing passwords and other hassles to get it fixed. The IT office sent an IT Tech up to help me get everything reset, and we got to talking shop.

Much to my surprise, he told me that he really didn’t like to program. For some reason, I simply assumed that if a person was into IT, he/she would also like to program. However, I should have known better. The most loathsome chore for me is mucking about with set-ups. When I update PHP or install a new version of MySQL, there’s a lot of tweaking that I have to do so that everything I’ve done still works. If there’re any commands I have to issue via the terminal, it depends on whether I’m working with Windows (and which version), Mac OS X (and which version) or Linux (and which flavor). Further there are PHP files (like php.ini) that must be tweaked as well. Every time I have to look up the different commands on the different OS platforms, and it differs for the language, database and what I consider the fickle whim of the person who wrote the blasted parameters in the first place. So, no, I do not like IT work or system administration.(However, I love IT Techs and System Administrators who keep everything humming along.)

Problems seem to arise when IT Techs, who are not also programmers, make pronouncements about programming. One guy I ran into who was super helpful in getting my Raspberry Pi configured with a Raspbian OS (a Linux version of Debian OS configured for the Raspberry Pi) turned into a jerk when I was helping Raspberry Pi users ease into PHP. He started mouthing off about PHP and OOP, and it was clear that he had no idea what he was talking about. He figured that since he knew how to issue short Linux commands, he was an expert on all things programming. For a newbie, these characters can cause a lot of damage because noobs probably cannot distinguish between programming and system administration. (By the same token, just because a person is a good programmer does not mean that she can help you set up the right flags and settings on your OS.)

Whether you’re an IT Tech or a programmer (or both), it’s important to realize that system administration and programming live on two different planets. I fully realize that there is some overlap, but each requires a different mindset. Good IT Techs know which terminal/OS commands to issue and the order to issue them in. Programmers, on the other hand, really work in an environment where they both create the structures and write code for the structures they create. Classes and methods along with arrays, loops, conditionals and a host of data types and properties need a different kind of orchestration. Keeping them separate is essential to excelling in both.

PHP OOP & Algorithms II: What to Use

Published on July 3, 2014 by Bill Sanders in Algorithms, Factory Method, Iterating through Objects, Object Communication, Recursion and Strategy. 0 Comments Tags: , , , , .

algorithm2What Are the Guidelines?

Like just about everything else in computing, there’s a certain amount of empirical testing. More importantly, however, are the general principles derived by both empirical and mathematical calculations. In the first post on algorithms and OOP, you saw an example that showed how many operations were necessary to find “Waldo,” a name near the end of an array of over 1,000 elements. One used a straight up loop and the other a binary search algorithm. Both were pretty quick; in fact it was hard to tell the difference in speed, and without seeing the little dots, you would not have seen the number of iterations required in each algorithm. You also saw that quadratic algorithms grew at rates that can quickly reach a point where processing comes to a crawl.

A Table Guide

Table 1 is derived from the 4th Edition of Algorithms (2011, p. 187) by Robert Sedgewick and Kevin Wayne. I’ve summarized it further. (Examples in the book are all in Java.) It is a rough but useful guide, and I have found it handy for a quick look-up.

Table 1: Algorithm Order of Growth

Name Order of Growth Description Example
 constant  1 statement    2 + 7
 logarithmic  log N divide in half    binary search
 linear  N loop    find max
 linearithmic  N log N divide & conquer    mergesort
quadratic  N² double loop    check all pairs
cubic  N³ triple loop    check all triples
exponential 2N exhaustive search    check all subsets

Fortunately, most of the time our algorithms are pretty simple statements, single loops or recursive calls. All of the models in green are algorithms we should try and stick with. You should avoid the reds ones if possible.

What About Recursive Algorithms?

Those who love to profess a little knowledge like to say that recursion is slower than a loop. As indicated, we really don’t want to end up paying attention to small costs. Recursion is important, and using recursive algorithms is cost effective, especially since the difference in running time is negligible.

We often use recursive implementations of methods because they can lead to compact, elegant code that is easier to understand than a corresponding implementation that does not use recursion.
~Robert Sedgewick and Kevin Wayne

(A recursive example of a logarithmic algorithm is not included here, but you can find a recursive binary search in the post on binary searches.) What we need to pay attention to are the order-of-growth issues. For example, quadratic algorithms on the lower end of the scale are not really that bad, but when the N increases at a squaring rate, it’s easy to run into problems. So if you avoid quadratic algorithms, you’ll be better off when the N increases. On the other hand, whether you’re using a recursive method for a binary search, you’ll not see that much of a difference as the N increases compared to non-recursive methods.

A Strategy Design Pattern Handles Algorithms

This blog has lots of posts detailing the Strategy design patterns; so if you’re not familiar with a PHP implementation of the Strategy pattern, you might want to take a quick look at the code. To get started, play the example and download the code.
PlayDownload

In the last post on algorithms, the program used a Factory Method pattern to produce an array, and in this post, the same pattern is used and two additional array products have been added. However, instead of having the algorithm classes be more or less on their own, all of the algorithm classes have been organized into a Strategy design pattern. Figure 1 is a file diagram of the objects in the application:

Figure 1: Object groupings with Strategy and Factory Method patterns

Figure 1: Object groupings with Strategy and Factory Method patterns

If Figure 1 looks a bit daunting, it is only three object groupings. The HTML and PHP Client make a request for one of seven algorithm implementations through a Strategy pattern. The concrete strategy implementations all get their data from a “data factory.” Figure 2 provides an easier (and more accurate) way to understand what’s going on.

Figure 2: Overview of the main purposes of the objects.

Figure 2: Overview of the main purposes of the objects.

So instead of having a complex task, you only have three groupings of classes and interfaces: Those making a request (Clients), those executing operations on data (Algorithms) organized as a Strategy pattern and the data itself organized with a Factory Method (Data.)

Figure 2 shows a simplified version of what the program does. The Context class considerably eases the requesting process. The HTML UI passes the name of the requested concrete strategy to the Client, and the Client uses the name as a parameter in a Context method. The Client is not bound to any of the concrete strategies because the strategy classes are handled by a Context object and method. (Click continue to see the PHP implementations of the algorithms.)
Continue reading ‘PHP OOP & Algorithms II: What to Use’