16.7 Building Runtime Functions

Building Parsers with Java
By Steven  John  Metsker

Table of Contents
Chapter  16.   Parsing an Imperative Language


When you create an imperative language, you often want to provide your users the ability to compose functions in your language. For example, Sling allows a user to type an expression such as abs(sin(2*pi*t)) . One way to represent this function is as a new method ”say, absSin2PiT() ”that accepts a variable t and returns Math.abs(Math.sin(2*Math.PI*t)) . The Sling environment does not create a new method but rather creates an object that represents this new function.

16.7.1 Function Wrapping

The desire to create new functions while a parser is running creates a paradox: You want to create a new method at runtime, but you must know all method names at compile time. A resolution to this paradox is as follows :

  • Design principle 1: Represent each known function with a class that implements the method f() .

The package sjm.examples.sling includes a hierarchy of function classes that implement f() , as Figure 16.24 shows.

Figure 16.24. The SlingFunction hierarchy. Each of these classes (from sjm.examples.sling ) implements the function f() , applying a function that corresponds to the class name .


Each class in the hierarchy in Figure 16.24 provides a known function. The one exception is Variable , which we discuss shortly.

A simpler example might be a string language, which could use classes such as Trim and LowerCase to provide string functions. The package sjm.examples.string contains a collection of classes that subclass an abstract class StringFunction . This abstract class has an abstract method f() , which Trim , LowerCase , and other subclasses implement. Figure 16.25 shows the function hierarchy in sjm.examples.string .

Figure 16.25. The StringFunction hierarchy. Each of these classes (from sjm.examples.string ) implements the function f() , applying a function that corresponds to the class name.


The method signatures of StringFunction.f() and SlingFunction.f() are different because they are hierarchies of string and mathematical functions, respectively. Each function subclass in these hierarchies implements f() according to the superclass's signature, and each class applies a function that corresponds to its name.

To implement the Trim class, for example, you might think of writing f() as

 String f(String s) {      return s.trim(); } 

This is the right idea in that Trim is implementing a standard interface in a way that supports the function that the name Trim implies. However, this implementation does not allow a Trim object to wrap itself around another function. You must set up Trim and any other function class so that it follows the decorator pattern [Gamma et al.], which is also known as wrapping. The design principle is as follows:

  • Design principle 2: Write f() for each function class so that wraps its function around other function objects. Require that these objects be supplied to the class constructor.

For example, the Trim class accepts in its constructor another StringFunction object that the constructor saves as the variable source . Here is the method Trim.f() :

 public String f(String s) {      return source.f(s).trim(); } 

This method applies String.trim() to the result of source.f(s) . In other words, the Trim class wraps a trim() function around another function. Consider an instance of Trim with a source that is an instance of LowerCase :

 package sjm.examples.string;  /**  * Create and use a string function at runtime.  */ public class ShowStringFunction { public static void main(String[] args) {     StringFunction func = new Trim(new LowerCase());     System.out.println( ">" + func.f(" TAKE IT EASY ") + "<"); } } 

This program creates a func object, which represents the new function trim(lower(s)) . The program applies the function to a string and prints

 >take it easy< 

Like the string functions in this example, the functions in Sling implement the design principles this section has discussed so far. The package sjm.examples.sling includes a family of function classes that subclass an abstract SlingFunction class. Each subclass implements f() , and each subclass has a constructor that accepts other functions that the new function wraps. Before examining these implementations , let's address principles for datatypes.

16.7.2 Umbrella Types

The signature of the common function f() depends on the domain of your functions. As the previous examples show, the signature of f() for classes in sjm.examples.string is

 String f(String s) 

String functions accept and return strings.

In the Sling environment, the input argument to f() is always time, which you define as varying from 0 to 1 as a plot unfolds. Time is a number, and the parameter signature of f() is f(double t) .

You might think that functions in Sling would have different types of return values. For example, you might expect two-dimensional functions, such as cartesian , polar , and sling functions, to have f(t) return a point (something they do, in fact). You might also expect the mathematical functions abs , sin , cos , ceil , and floor to have f(t) return a single number. In fact, these functions and all functions in sjm.examples.sling return a point as the value of f() .

To provide an environment that does not require a user to declare variable datatypes, it is useful to declare at a design level that everything is an instance of some overarching, or umbrella, type. In addition to cartesian , polar , and sling , all the functions in the sling package are two-dimensional functions of time. This practice simplifies development and reduces chances for errors in implementing the environment. For example, because everything in Sling is a two-dimensional function of time, the following Sling expression is well defined:

 sling(1, 1) + sin(8*pi*t) 

If the sling function returned a Point object and the sin function returned a single number, the arithmetic function would have to have some way to coerce the two types to be compatible for addition. Sling avoids this problem by following this principle:

  • Design principle 3: Define the signature of f() to be broad enough to encompass all the functions in a language.

In Sling, the signature of f() is

 Point f(double t) 

This third design principle is optional. When you implement your own languages, you may decide to allow different return types of functions. The difficulty of such an approach is that managing the interplay of different types will permeate your environment. Using a single return type moves the problem of datatype coercion to function constructors. This requires the following corollary:

  • Design principle 3.1: Establish policies for widening all datatypes to fill the return value of f() .

Sling implements this principle with the following policy:

  • In Sling, any function class that would naturally return a single number y will instead return a Point object (t, y) .

Sling functions insert time as the x value of single-valued functions. For example, the mathematical sin function returns a single number. If you call that number y , then Sin.f(t) returns the Point object (t, y) . This policy is more useful than, say, just inserting 0 as the x value, because using time as the default x dimension has desirable effects. For example, the program

 plot sin(2*pi*t); 

plots a sin-wave because this program is equivalent to

 plot cartesian(t, sin(2*pi*t)); 

The policy of inserting time as the x component moves the coercion of types away from arithmetic and other areas where different types might come together. The problem of coercion is pushed to the function constructors, where a simple policy defines how functions are widened to the broadest possible type.

16.7.3 Runtime Functions in Sling

The design principles of this section determine the code for SlingFunction subclasses. For example, the code in Sin.java (with comments removed) is as follows:

 package sjm.examples.sling;  public class Sin extends SlingFunction { public Sin(Function source) {     super(source); } public Point f(double t) {     return new Point(t, Math.sin(source[0].f(t).y)); } } 

This code exemplifies all of the design principles for Sling functions:

  • Design principle 1: Sin implements the common function f() .

  • Design principle 2: Sin provides a constructor that accepts another function as its source. The SlingFunction superclass stores the source function in an array because a function may have more than one source. The source function for a Sin object is thus available as source[0] . The f() method calculates and uses the source function's value at time t .

  • Design principle 3: The source function, like any function, returns a point as a function of t . The method Sin.f() ignores the x value of this point, wrapping Math.sin() around the y value of the source function's point. The y value for f() to return is thus Math.sin(source[0].f(t).y) . The mathematical sin function is a single number, and so f() returns a Point with t as its x value.

By following these principles, the functions in sjm.examples.sling meet the objectives of allowing runtime composition of functions and of using an umbrella type.

16.7.4 Execution Phases

To create a working environment for your language, you must parse a program into a command object and then execute the object. The Sling environment includes a third phase for drawing a program's functions. The phases of the Sling environment are as follows:

  1. Parse the user's program, building a command object that represents the program.

  2. Execute the command, creating the collection of functions requested by the user's program.

  3. Draw the functions.

For example, consider the Sling program

 for (r, 1, 4) {      plot sling(r, 1) + sling(s1, 5); } 

This program uses the value of the first slider, s1 . When a user types this program and clicks Go!, a Sling parser object parses the text and builds a composite command that represents the program. Next, the environment executes the command. Each pass through the for loop creates one new function to plot. The plottable functions are

 +(sling(1, 1), sling(s1, 5))  +(sling(2, 1), sling(s1, 5)) +(sling(3, 1), sling(s1, 5)) +(sling(4, 1), sling(s1, 5)) 

At this point, the Sling environment has four function objects to plot. After creating these functions, the environment plots them using the current value of the slider s1 . Each time the slider moves, the environment plots the functions again ”without re-parsing the text and without reexecuting the command. To let the display keep up with a slider's movement, it is important that the Sling environment replot the functions for each new slider value without reexecuting the command.

The variable r and the slider s1 in the preceding program may look similar to a user, but they have different roles in the Sling environment. The slider s1 refers to the value of the slider in the Sling user interface, and this reference persists even after the command executes and creates the command's functions. When the environment draws a program's functions, it looks up the current value of the slider. The variable r does not survive to the function-plotting phase. Variables melt away as the command executes. The for command in the preceding program uses the variable r . As the for command executes, it evaluates r and bakes the value of r into the functions that the plot command creates.

Functions in Sling and in most imperative languages must be able to contain variables and to evaluate themselves . For example, the function

 +(sling(r, 1), sling(s1, 5)) // object 1 

must be able to evaluate itself to create a corresponding but unvarying function. If the value of r is 3 (for example) at the moment of evaluation, the function must create a new version of itself as

 +(sling(3, 1), sling(s1, 5)) // object 2 

There is a difference between these two objects. The first object may contain variables; the second may not. However, the second object is so similar to the first object that you can use a prototyping strategy.

16.7.5 Prototyping

The idea of the prototype pattern [Gamma et al.] is to specify the kind of object to create using a prototypical instance. Every function in Sling needs three similar types of object: assemblers, terms, and functions. You might think that you need to create a SlingAssembler class, a SlingTerm class, and a SlingFunction class. With this approach, you would also have to create a SinAssembler class, a SinTerm class, and a SinFunction class. In addition, you would need three similar classes for each function that the Sling language supports. However, you can do without these classes by applying the prototype pattern.

The package sjm.examples.sling implements each function of the Sling language with a single class. For example, the only class in sjm.examples.sling that relates to the sin function is the class Sin , which extends SlingFunction . Similarly, the only class that relates to the sling function is the class Sling . The Sling environment uses one instance of this class as an assembler, uses other instances for each sling term in a Sling program, and uses other instances each time a sling term evaluates into a sling function. To see the different roles that a Sling object can play, it is useful to count the number of assembler, term, and function objects in a sample program. Consider the program

 for (r, 1, 4) {      plot sling(r, 1) + sling(s1, 5); } 

To execute this program, the Sling environment uses 11 copies of a Sling object: one for the assembler, two for terms, and eight for the plottable functions. Ten of these objects are copies (that is, clones ) of the initial object that the environment uses as an assembler.

When the Sling parser parses a program, it uses a FunctionAssembler object as the assembler for all Sling functions, including sin , cos , , and sling . The constructor for FunctionAssembler requires a SlingFunction object; the assembler uses this object as a prototype. For example, the Sling parser associates an assembler with the sling() function; this assembler is a FunctionAssembler object that has a Sling object as its prototypical function.

Each time the parser sees a sling() function, the parser asks a FunctionAssembler object to "work on" the assembly that the parser is parsing. The assembler pops arguments from the stack to use as the new object's source functions. The number of arguments the assembler pops is equal to the number of source functions the prototype has. For example, a prototype for the sling() function has two source functions, so a FunctionAssembler object that uses this prototype pops two arguments as sources. The assembler then makes a copy of its prototype, sets the copy's sources to be the popped functions, and stacks the new object.

When the parser is finished with the preceding program, it will have created one Sling object to use as an assembler, and two copies of this object to act as terms in a command.

The Sling environment then asks the command that represents the user's program to execute. When the plot command executes, it evaluates the function it is plotting. During evaluation, the sling terms copy themselves.

For example, on the second pass of the for loop, sling(r, 1) term copies itself and sets the copy's source function to be the value of r , which is 2 . The sling(s1, 5) term also copies itself, although this is not strictly necessary because this term has no variables to evaluate. Each pass of the for loop creates a new sum that includes two new instances of Sling .

After the command representing the user's program executes, the mediator sends its plottable functions to a SlingPanel object. The SlingPanel class, a subclass of JPanel , knows how to plot SlingFunction objects.

16.7.6 Function Evaluation

All functions other than variables evaluate themselves in the same way, deferring to SlingFunction.eval() :

 public SlingFunction eval() {      SlingFunction f = fresh();     for (int i = 0; i < source.length; i++) {         f.source[i] = source[i].eval();     }     return f; } 

This method creates a copy of the object using fresh() , which is a clone() method that does not clone the object's source functions. The eval() method establishes the new object's sources as evaluations of the receiving object's sources.

Design principle 2 requires that you compose functions from functions. To allow variables in the composition of a function, variables themselves must be functions. The Variable class is the only subclass of SlingFunction that overrides eval() , using

 public SlingFunction eval() {      if (source[0] == null) {         throw new UnassignedVariableException( "> Program uses " + name + " before assigning " +             "it a value.");     }     return source[0].eval(); } 

Variables expect to hold some function at evaluation time. For example, the following assignment can work only if x has a value at the time the assignment command executes:

 y = sin(x); 

In the Sling environment, an AssignFunctionCommand object represents this statement. The command holds the variable y and a function object that represents sin(x) . When the command executes, it evaluates sin(x) . If the variable x has no value, Variable.eval() throws an exception. Otherwise, the evaluation completes successfully, and the assignment command sets the value of y to the value of sin(x) .


Building Parsers with Java
Building Parsers With Javaв„ў
ISBN: 0201719622
EAN: 2147483647
Year: 2000
Pages: 169

Similar book on Amazon

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net