Archive for the 'Interpreter' Category

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.

Of all of the design patterns I’ve seen, this one has the most loose ends. Any statement put into a string and then interpreted generally requires some kind of parsing. GoF note the need for parsing and point out it can be from a table driven source, a recursive descent (or some other hand-crafted parser) or in the Client. The Context class is used as a global entry point for the Interpreter. It’s probably heresy to do so, but I decided to put the parser in the Context. The Client sends the request to the Context and indirectly to the IAbstractExpression. The Context class still acts as a global entry point, but it also parses the data (statement in PostScript notation), but the Terminal Expression class acts more as a residual error-catcher than a terminal for multiple interpreted segments of a phrase. I don’t see it as adding tighter coupling. (If the parser were placed in the Client, I suppose it would be a purer version of the design pattern. The Client does, however, convert the string into an array using the preg_split() function; so, some partial parsing is done by the Client. The operators are treated as separate NonterminalExpression objects used to calculate the previous two elements on the stack (array). As such, they act as one-word interpreters.

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:

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.
Continue reading ‘PHP Interpreter Design Pattern’