PHP Interpreter Design Pattern

Interpreting Postfix

Even though we may not realize it, one of the most common computer languages we use is Adobe’s PostScript. PostScript printers contain a language called PostScript, a postfix language based on a stack analogy. (Postfix also is called reverse Polish notation after the Polish mathematician Jan Łukasiewicz who developed the mathematical notation placing of the operator after the operands.)

Stack operations are compared to a cafeteria stack of trays. The last tray added to the stack is the first one to pop off. Imagine each tray with a value and each third tray with a mathematical operator. The bottom most tray is to the far left and the top tray is to the far right. With three trays, reading from left to right, we might find the first and second trays to be operands (numbers) and the third one to far right (top) an operator. So if the first operand is 5 and the second operand is 4 and the operator is add or (+), the three trays would be removed and replaced by a single tray with a value of 9—the sum of 5 and 4.

The following shows an example of this notation:

30 2 *
Result: 60

In order to correctly interpret a postfix expression as an infix one (the kind we’re used to using in PHP, like $total = 5 + 4;), this post uses an Interpreter design pattern that interprets a postfix expression so that PHP understands what to do with it as a math operation. The implementation of the Interpreter pattern is very simple and may lack some of the more subtle aspects of the pattern. However, it is one implementation that uses all of the pattern’s participants and should be easy to understand.

Using a simplified version of the Interpreter design pattern, you can practice math operations using a postfix calculator that interprets PostScript operations as PHP math operations. If the operation reminds you of certain of your calculator’s behavior, it’s probably because a lot of calculators use postfix to solve problems.

A further simplification is that this “calculator” only returns the results of a single two-operand calculation. A more common postfix expression may have several operators such as the following:

1 5 + 2 * 6 / result=2
1 and 5 add = 6
6 and 2 multiply = 12
12 and 6 divide = 2

This interpreter could be modified to take more complex expressions, but to get started, this one is simple by design. Click the play button to see how the program works and download the source code:

Try some different entries using postfix notations with the caveat that all operators are spelled out—add instead of + and mod instead of %.

Interpreting Differences

The Interpreter design pattern as described by Gamma, et al can be used to express instances of a recurring problem as sentences. Interpreting the sentences then solves the problem. Right off the bat I was thinking, ¿Como está usted? translates to How’s it going?, but that’s not exactly what GoF had in mind. Any spoken language is a bit too big for this kind of interpreter. Instead, the pattern describes how to define a grammar for simple languages. Gamma and his associates use the example of regular expressions, so loved by Perl programmers.

So when I went looking at some Interpreter examples, besides regular expressions, I found converters from Roman numerals to regular numbers, a Boolean language, a musical note interpreter from do, rey, me, fa, so, la, ti to Hertz (Hz) values, calculations using postfix notations and some other fairly modest examples. Because of my experiences with postfix languages, I decided to do one that set up as a PostScript data entry that would resolve to an outcome (solution) to the results of a postfix statement. I decided on PostScript whose math operators are word-like and not symbols. (e.g., Instead of using / for division, it uses div.) Besides, most laser ink-jet printers are PostScript. This would be a little more than the usual minimalist example since the user can use it to practice and learn PostScript math entries.

Interpreter Design Pattern Formal Features

Figure 1 provides an overview of the Interpreter pattern. Note that the Client is part of the pattern (instead of implied or not at all). Also note that the Client holds references to both the Context class and AbstractExpression interface.

Figure 1: Interpreter Class Diagram

The good news is that this implementation of the design pattern is wonderfully flexible and easy to update. If I wanted to change the language example from a postfix one to something like Scheme, the pattern would be able to handle it with ease. Of course, the purpose here is to examine the pattern with an illustration of its use, and while this implementation is basic, it’s a starting point.

Building a PostScript Learning Tool

The basic sequence for this little PostScript calculator is based on each the request passed from the HTML UI to the Client. It has the following sequence:

1. User enters a string of two numbers and an operator in HTML UI.
2. Client passes string to private variable and unsets superglobal
3. Client converts string into a 3-element array and passes it to Context
4. Context determines the correct expression class and returns class instance to Client
5. Client removes the operator from the array and passes array through interpret() method of the object received from the Client.
6. The expression class (IAbExpression implementation) carries out PHP (infix) math operation and returns result to Client
7. Output displayed in iframe of HTML UI

Now having seen the sequence, Figure 2 shows the file diagram of the application:

Figure 2: File Diagram of Interpreter implementation

I set the ValueTermExp.php file off to the side since it’s implemented more as an error message sender than its true role as a terminal expression. With a more sophisticated PostScript calculator (one that can handle a series of expressions), it can be upgraded to return the full calculation of the multiple NonTerminal classes.

The Client and Context

Since the Client has a key role in the Interpreter, we’ll start with it. It is used as a “gateway” in that it is instantiated from within the file that holds the class. It also has the code to insure that all error messages are received and that all classes will be called without having to add include() statements.

error_reporting(E_ALL | E_STRICT);
ini_set("display_errors", 1);
// Autoload given function name.
function includeAll($className)
{
    include_once($className . '.php');
}
//Register
spl_autoload_register('includeAll');
class Client
{
    //client request
    private static $calcExpression=array();
    public static function request()
    {
      //Get the input string
      $calc=$_POST['calc'];
      unset($_POST['calc']);
 
      //Convert string to array split at space
      self::$calcExpression= preg_split("/[\s]/", $calc);
 
      //Call Context
      $context=new Context();
      $contextObject=$context->getContext(self::$calcExpression);
 
      //Make request for interpretation
      array_pop(self::$calcExpression);
      echo $contextObject->interpret(self::$calcExpression); 
    } 
}
Client::request();
?>

In the sequence, the Client first calls the Context to get the correct interpreter class. The Client sends the expression it wants it to examine to determine which interpreter class will process it with PHP’s infix math. So take a look at the Context to see its role in the process:

class Context
{
     private $postarray=array();
 
     public function getContext(array $expression)
     {
          $this->postarray= $expression;
          switch (array_pop($this->postarray))
          {
               case "add" :
                    $math=new AddTermExp();
                    return $math;
               case "sub" :
                    $math=new SubtractTermExp();
                    return $math;
               case "div" :
                    $math=new DivideTermExp();
                    return $math;
               case "mul" :
                    $math=new MultiplyTermExp();
                    return $math;
               case "mod" :
                    $math=new ModTermExp();
                    return $math;
               default :
                    $math=new ValueTermExp();
                    return $math;
          }
     }
}
?>

You may have noticed that when the Client calls the expression classes (NonTerminalExpression types), it does not include a Context instance as a parameter for the interpret() method shown in Figure 1. In this implementation (as well as the one used by The Gang of Four in their book, pg. 244), the a Context instance is not included. Instead of the Context in the instance parameter, the Context is assumed in the class instance used. The operands in the expression are passed by the Client’s operation that removes the operation by popping it off the top of the array being sent through the interpret() method.

The Expression Implementations

The interpret operations are fairly simple. All each class does is to use an infix operation in PHP that the PostScript calculation displays as postfix. Each one interprets a single operation.

//AddTermExp.php
class AddTermExp implements IAbExpression
{
     public function interpret(array $calcExpression)
     {
          $result=array_pop($calcExpression) + array_pop($calcExpression);
          return $result;
     }
}
?>
 

//SubtractTermExp.php
class SubtractTermExp implements IAbExpression
{
     public function interpret(array $calcExpression)
     {
          $s2=array_pop($calcExpression);
          $s1=array_pop($calcExpression);
          $result=$s1 - $s2;
          return $result;
     }
}
?>
 

//MultiplyTermExp.php
class MultiplyTermExp implements IAbExpression
{
     public function interpret(array $calcExpression)
     {
        $result=array_pop($calcExpression) * array_pop($calcExpression);
        return $result;
     }
}
?>
 

//DivideTermExp.php
class DivideTermExp implements IAbExpression
{
     public function interpret(array $calcExpression)
     {
          $s2=array_pop($calcExpression);
          $s1=array_pop($calcExpression);
          $result=$s1 / $s2;
          return $result;
     }
}
?>
 

//ModTermExp.php
class ModTermExp implements IAbExpression
{
     public function interpret(array $calcExpression)
     {
          $s2=array_pop($calcExpression);
          $s1=array_pop($calcExpression);
          $result=$s1 % $s2;
          return $result;
     }
}
?>

Each class has two operands in the array passed from the Client. Depending of which class has been selected by the Context, the appropriate operation generates appropriate results that are returned for output by the Client.

The only exception is the terminal expression. Here it is used to let the user know that the operator is unrecognized.

//ValueTermExp.php
class ValueTermExp implements IAbExpression
{
     public function interpret(array $calcExpression)
     {
          return "Unknown operator.";
     }
}
?>

This example is a fairly peripheral implementation of the interpreter, but it works with the general spirit of the pattern to take one expression and interpret it to another.

More than Meets the Eye

The Interpreter pattern is a less-used used but includes important concepts and ideas. Even the GoF examples is a bit unclear, especially when compared to the class Interpreter’s class diagram. Most of the examples in any language (including mine) reminded me of some lines from an old Jim Croche song, Bad, bad, Leroy Brown. To wit:

Leroy [The Interpreter] looked like a jigsaw puzzle
With a couple of pieces gone

This is one of those design patterns to which I would like to return and spend more time with. Much of the core of the pattern lies in the parser, and I’d like to better flesh out the non-terminal expression, both as a concept and as a class. Most likely I would add the parser to the Client, and because the Client is a full participant in the Interpreter pattern, there’s no reason not to do so. Any code or concepts from the readers on this aspect of the Interpreter would be most welcome.

Getting Started in PostScript

Writing code in PostScript is not easy, but it’s an interesting programmer challenge. If you want the full PostScript language tutorial, you can download the book (free) published in 1985 by Adobe at:

http://www-cdf.fnal.gov/offline/PostScript/BLUEBOOK.PDF

Then, as long as you stick with simple math operations, you can practice your PostScript skills here.

The rules are simple; you add one or two operands and an operator. The operands and operator are popped from the stack and the result is pushed onto the stack. The results you see in the output window are pushed onto the stack until your pop them off or you have a new operator that combines the values with previous numbers and creates a new result.

Copyright © 2015 William Sanders. All Rights Reserved.