Thesis Proposal
Aspect Oriented Programming (AOP) is becoming prominent in the field of Computer Science. The tools that allow programmers to use AOP methodologies to improve their productivity have been around for quite sometime. The purpose of this research is to understand the fundamental concepts behind these Aspect Oriented Programming Tools, how those concepts are applied in different Aspect Oriented Programming tools, and create a coherent model of AOP concepts that would allow us to make informed decisions about how these concepts could be applied in novel ways.
First, we will investigate the fundamental concepts that are evident in AspectJ, DJ, and Branch Oriented Programming. These tools use the concepts of predicated execution, advice and traversal in different ways. AspectJ uses predicated execution and advice concepts on a program’s control flow graph. Branch Oriented Programming attempts to define the program’s control flow graph using the predicated execution and around concepts. DJ uses traversals and advice for data structures. Some of these tools have been around for years, but we still do not understand how these tools and their concepts are related. We will investigate these relations and determine their usability for AOP tool analysis.
One way to explore these relations is to attempt to implement concepts from one tool to another. The simple implementation of factorial function written in Fred and AspectJ with Branches shown below illustrate how one can apply the concepts of branches using AspectJ.
Factorial example in Fred:
(define-msg fact)
(define-branch
(and (eq? (dp-msg dp) fact)
(= (car (dp-args dp)) 1))
1)
(define-branch
(eq? (dp-msg dp) fact)
(let ((x (car (dp-args dp))))
(* x (fact (- x 1)))))
Factorial Example in AspectJ with
Branches:
class FactClass {}
aspect FactExample {
static int FactClass.fact(int x) {
return 1;
}
pointcut factBase(int x):
args(x) && call(static int FactClass.fact(int))
&& if(x==1);
int around(int x) : factBase(x) {
return 1;
}
pointcut factRecursion(int x):
args(x) && call(static int FactClass.fact(int))
&& if (x > 1);
int around(int x) : factRecursion(x) {
return x * FactClass.fact(x-1);
}
}
In this implementation, the FactClass is empty and the factorial method is defined within the FactExample aspect. The two pointcuts and the corresponding around advices are the two possible branches from the method fact().
The close correspondence between the Fred implementation and the branches with AspectJ implementation of the factorial function is very clear in this example. There’s almost one to one correspondence between the two implementations. This illustrates the possibility of implementing the Branch Oriented Programming concept using AspectJ and this process of was relatively trivial.
In order to find more of these relationships, a consistent view that one can take to make all of the AOP approaches more clear would be useful. One way to accomplish this is to view these ideas as abstracting the different parts of a program into graphs. The nodes and edges are different, but the basic theme is the same. This allows us to think of all of the different things that one can do with graphs, traversals, mapping, grouping of nodes, sub-graphs, etc. If we apply these graph concepts to the different graphs evident within programs that is consistent with the different implementations of Aspect Oriented Programming Tools, we maybe able to find possibilities for future development of those Aspect Oriented Programming Tools.
This idea of abstracting AOP concepts into generic graphs will be explored by attempting to implement an idea from a graph operation to different tools. In the previous example, we are looking at the case in which one wants to have access to some node or context that the entity doing the traversal has seen before.
In AspectJ, you would use the pointcut to specify the specific join point that you want to expose to the join point encountered later in the traversal of the dynamic call graph. In the example, we want to expose the Caller c to all of the Workers w.
pointcut perCallerWork(Caller c, Worker w):
cflow(invocations(c)) && workPoints(w);
With traversal strategies specified in [19 Lieberherr et al.] we would specify a strategy and a NodesOf operator:
NodesOf(from Caller to *)
and we would intersect this set of classes with the set of classes in set Worker:
NodesOf(from Caller to *) intersect Worker
When the NodesOf operator is applied to a graph, it returns all the nodes in the graph. It would be useful to extend AspectJ with strategies and NodesOf to define AspectJ type patterns more flexibly. In DJ, one would use the ContextVisitor to expose the stack of objects that the visitor has encountered thus far in the object graph during a traversal of the object graph. In all of these cases, the program can expose parts of the graph that was traversed earlier during the current traversal. This is a fundamental concept that is evident in AspectJ, DemeterJ and DJ. This thesis will attempt to find and categorize these types of commonalities between AOP tools and integrate them into a consistent view of Aspect Oriented Programming Concepts.
The relevant experiments for this thesis include using AspectJ to implement the concepts from other AOP tools, integrating AspectJ and AP Library and implementing a real-world application using the tool from the integration work. The purposes of the first experiments are to find out the relationship between AspectJ and other tools. Examples of these experiments were presented above.
The focus of these experiments, integrating AspectJ and AP Library, is to find out how well these tools interact with each other. The last experiment will measure the effectiveness of the integration experiment. All of these experiments have only one purpose, to direct the shaping of the consistent view of Aspect Oriented Programming that integrate concepts from AspectJ and Demeter.
The consistent view of Aspect Oriented Programming that will be shaped by the proposed experiments should be based on abstracting Aspect Oriented Programming concepts into graphs and the manipulation of these graphs as mentioned previously. This new view should be a starting point for a new way of analyzing Aspect Oriented Tools, i.e. Aspect Oriented Tool Analysis. This new type of analysis should expand the current understanding of Aspect Oriented Programming tools and concepts that will lead to future development of those tools and concepts.
Introduction to AOP Tools
This Master's Thesis started with vague notions that there has to be better ways of expressing what a user would want the computer to accomplish on behalf of the user. A quick survey of latest Aspect Oriented Programming Languages were taken. The languages surveyed were [DemeterJ], [DJ], FRED, and [AspectJ]. DemeterJ and DJ were developed at Northeastern University and was a natural selection as a graduate student there. FRED was developed by Doug Orleans as a part of his Ph.D. Dissertation and its close ties with AspectJ made it prime candidate. AspectJ was selected for its popularity among the AOP community. These four AOP Tools were determined to be the tools that we will be used in our experimention and analysis.
FRED
FRED [Orleans02], developed by Doug Orleans, is a language that integrates Aspect Oriented Programming and Predicate Dispatching, implemented in [MzScheme]. The main components in FRED are Message, Branch, and Decision Point. In order to simplify these terminologies, we will map these components to components from functional programming. A Message maybe thought of as a function. Defining a Message is equivalent to declaring a function. Then, a Branch is analogous to a function call. It is actually more complicated than that, but we will just use this analogy for simplicity sake. The Decision Point is where a decision is made about which Branch should be invoked. This requires that a predicate is associated with each Branch. FRED follows the Branch that satisfies FRED's rules about predicates.
In order to understand how this works, we will present a simple factorial example. In FRED, a programmer defines a Message by calling the function define-msg. In Figure 1, the first statement defines a Message called fact. Next, we define some Branches for this Message, fact. First, we will handle the base case where the first argument is equal to one. This is expressed in FRED in Figure 1 by the second MzScheme statement. We used the function define-branch to define a new Branch that executes its body when the Message is equal to fact and the first argument is equal to one. Within this body, we return one, which is what would happen if we called the function factorial with one as the argument. Next, we handle the recursive case by defining another Branch as represented by the third MzScheme statement in Figure 1. It defines a Branch that is invoked when the Message is fact. In the body of the Branch, we make a recursive call to fact with x - 1 as the argument and multiply that by x. Then, we return the result of the multiplication.
Figure 1: Factorial Example in FRED
There is some complex situation reguarding the predicates for the two Branches. The predicates for both of these Branches maybe true for the case (fact 1). What does FRED do in this case? FRED determines the more specific predicate and invokes that Branch. Thus, when (fact 1) is interpreted, FRED invokes the first Branch instead of the second Branch. The rationalization for this decision is that first predicate is more specific than the second predicate. Thus, FRED always selects the more specific predicated Branch. For all other cases for the call to the function fact, the second Branch is invoked. This gives us the behavior that we want from FRED in implementing the factorial function.
Demeter Concepts
Next, we will introduce Demeter concepts and how these concepts are implemented in DemeterJ and DJ. The main concepts of Demeter are Class Graph, Strategy, Visitor, and Advice. The Class Graph is the schema of the data structures used within a program. It defines all the possible manifestations of Object Graphs created during an execution of a program. A Strategy is a direction on how to traverse the Object Graph. Strategy such as "from Company to Employee" and "from Top to Bottom via Middle" combined with a Class Graph yields a Traversal Graph. It is a sub-graph of the Class Graph that includes all possible paths defined by the given Strategy. The Visitor is the one that traverses the Traversal Graph. It has Advices that are invoked for particular types of nodes in the Traversal Graph. Thus, a task within Demeter requires the programmer to specify at least the Class Graph, Strategy and Visitor. This Demeter Process is shown in Figure 2.
DemeterJ
The way in which the programmer specifies the three components Class Graph, Strategy and Visitor is different for DemeterJ and DJ. In DemeterJ, the Class Graph is described within the Class Dictionary. The syntax of the Class Dictionary is a modified Backus Naur Form (BNF) that allows programmers to describe the Class Graph efficiently. The Visitor is declared within the Class Dictionary as well, since it is implemented as a Java Class. The Strategy and the definition of the Visitor are specified in Behavioral Files.
Figure 2: Demeter Process Overview
We will go through the Basket Example to illustrate how DemeterJ is used to implement programs. The Class Graph of the example is shown in Figure 3. The Basket Class may contain three objects, one Pencil and two Fruit. A Fruit may also be an Orange. Every Fruit has Weight, which is an integer and an Orange has Color which is represented by a String. In this example, we will count the integer Weights within a Basket.
Figure 3: Class Graph of the Basket Example
In DemeterJ, we first need to specify the Class Graph in a Class Dictionary. We specify all of the relationships within the Class Graph using the modified BNF as shown in Figure 4. The identifier on the left is the class being defined. The "=" can be interpreted as "has-a" in Object Oriented Programming terminology. The identifier within "<" and ">" are labels for these "has-a" edges within the Class Graph. The "is-a" relationship is defined by the ":" symbol. The "*common*" indicates that the Class Fruit has a "has-a" relation ship with Weight with label "w". In the classic case of inheritance, all of the Classes that have "is-a" relationship with Fruit will inherit this "has-a" relationship. Lastly, the period ends the sentence within the Class Dictionary.
Figure 4: Class Dictionary of the Basket Example
Because of the way DemeterJ implements alternation class as abstract class, we need to change the way inheritance is expressed between Fruit and Orange. If want the Fruit Class to be concrete instead of abstract, we need to use "extends" instead of the Alternation with ":". The modified Class Dictionary is shown in Figure 5. The ":" for Fruit has changed to "=" and the string "extends Fruit" was added to the definition of Orange. This also signifies that Orange inherits from Fruit.
Figure 5: Class Dictionary of Basket Example with Fruit as Concrete Class instead of Abstract Class
Next, we need to specify the Strategy for the traversal. Since we want to count all of the Weight object within the Basket, we need to traverse from the Basket Class to Weight. Therefore, the Strategy becomes "from Basket to Weight". The resultant Traversal Graph from applying this Strategy to the Basket Example Class Graph is shown in Figure 6.
Figure 6: Traversal Graph as a result of applying the Strategy "from Basket to Weight" to the Basket Example Class Graph
Now that we have a Traversal Graph, we need define the traversal and Visitor to traverse the Class Graph and count the integers stored within each Weight object. We accomplish this by defining the traversal and the Visitor within the Behavioral file. However, we have not actually declared the Visitor in the Class Dictionary. We may accomplish thiss by adding the line shown in Figure 7 to the Class Dictionary.
Figure 7: Declaration of the CountWeightVisitor in the Class Dictionary
Now, were ready to define the traversal and the Visitor in the Behavioral file. When defining the traversal, you have to first specify the starting node of the traversal in our strategy, i.e. Basket. Then, we type in "{" to start the scoping of "code" to be added to the Class Basket. We start the definition with the key word "traversal" then the name of the traversal. Next, we have the Visitor name with parenthesis around it. Then, another "{" to start specifying the rest of the Strategy. We add the keyword "to" and then the destination, Weight. We are finished with this definition, so we signifying the end of the Stategy with ";" and "}". Then close the scope of the Class Basket with another "}". This traversal definition is shown in Figure 8.
Figure 8: Definition of the Traversal with Strategy "from Basket to Weight" with the CountWeightVisitor and the definition of CountWeightVisitor.
The definition of the CountWeightVisitor is similar. We start with the scoping by having the name of the Class CountWeightVisitor and "{". Then, we specify two methods and an Advice. The two methods are start() and getReturnValue(). The state() method initializes the running total of the weights, while getReturnValue() returns the total weight counted. The definition of these methods looks exactly like Java code, except for the double curly-braces. This is used to signify pure Java code to the DemeterJ weaver.
The Advice specified within CountWeightvisitor is a Before Advice. It is executed before Visiting all the "children" of the node Weight. Within the Advice, there's a keyword "host", which is similar to "this" in Java. However, it refers to the object of type Weight we are currently visiting in this case. The accessor method get_i() in the Advice is generated automatically for us by DemeterJ. This Advice is executed every time we encounter an object of type Weight and add the integer within Weight to the total.
This does seem like a lot of work, so the designers of DemeterJ created a way of specifying the Strategy and the Visitor at the same time using in lined Visitor. This is useful for small traversals, such as accessor traversals that retrieve one object from a complicated Object Graph. In this method, we do not need to declare the Visitor as a class in the Class Dictionary. This usage of the in lined Visitor is illustrated in Figure 9 below.
Figure 9: Definition of Strategy and an Inline Visitor for Counting Total Weight within a Basket
The body of the method getTotalWeight looks almost exactly like the CountTotalWeight Visitor. The difference is that the method has the string "to Weight" to specify the Strategy "from Basket to Weight". Next, we have the statement "{{ in total=0;}}" which defines and sets the running total of the weights for the in lined Visitor. We specify the Advice similar to the one in Figure 7. Then, we specify the return value total and the return type to be int. This in line Visitor is very useful if you do not have complicated Visitors that you want to reuse.
Another significant feature of DemeterJ is its ability to generate a parser for the Class Dictionary. As an example, we will convert the Class Dictionary in Figure 4. We will convert it in a way that the grammar will specify a language that reads in XML as input and creates an Object Graph. In order accomplish this task, we add the appropriate XML tags around the statements in the Class Dictionary as shown in Figure 10.
Figure 10: Class Dictionary of Basket Example Converted to Generate a XML Parser for the Schema Specified by the Class Dictionary
This parser generation feature of DemeterJ is significant, because it allows programmers to add minimal amount of strings to specify an input file language. DemeterJ also generates default Visitors and traversals to print and display the Object Graph parsed from an input file. This maybe used for internal testing of the application being developed.
DJ
The next implementation of the Demeter Concepts is DJ. This is a set of Java libraries that allow programmers to specify Class Graph, Strategy, and Visitor through an API. This is useful for programmers that do not want to learn a new language and use an experimental tool. They may include the library in their program and obtain the full capabilities of these concepts.
As in DemeterJ, there has to be a way of specifying the Class Graph in DJ. While DemeterJ uses Class Dictionary to specify the Class Graph, DJ uses Java's Reflection to construct the Class Graph. DJ also provides an API to access this functionality. The class ClassGraph in the AP Library [APLib], allow programmers to obtain the Class Graph and use it to traverse Object Graphs.
Figure 11: Definition of the Basket Example Class Graph in Figure 3
The actual specification of the Class Graph is pure Java code as shown in Figure 11. The class ClassGraph only allows the programmers to access the Class Graph and the relevant methods. Thus, the definition of the Class Graph is accomplished by the usual method of specifying classes and their definitions in Java. The DJ's ClassGraph class provides the reference to the Class Graph defined by the programmer. The Java code to specify the Basket Example Class Graph in Figure 3 is shown in Figure 11. It uses the usual method of data member variables for "has-a" relationships and uses the "extends" keyword for the "is-a" relationships. This Java code would have been generated from the Class Dictionary in DemeterJ.
Figure 12: Obtaining a Reference to the Class Graph via Constructor Call for Class ClassGraph in DJ
Obtaining the reference to this Class Graph is simple as call the constructor to the class Class Graph as shown in Figure 12. DJ uses Java Reflection to construct the graph representation from the current running program. This allows programmers to adapt their existing applications to use DJ.
Figure 13: Definition of the CountWeightVisitor for DJ
Next, we define a Visitor to count the weights within the Basket as shown in Figure 13. The actual Java code is very similar to the definition for DemeterJ in Figure 8, except for minor syntactic differences. Thus, we can conclude that DemeterJ's syntax for the Behaviorals files are very close to the Java equivalents.
Lastly, we need to invoke the traversal with the Object Graph, Strategy and Visitor. This Object Graph is created by calling constructors for the classes in the Class Graph. We also need to instantiate an instance of the CountWeightVisitor to visit the nodes in the Object Graph. Then, we call the method traverse() for class ClassGraph with the "root" of the Object Graph, the Strategy and the Visitor. The actual Java code showing how all of these components come together is shown in Figure 14.
Figure 14: Java Code Showing How Demeter Concepts Work Together in DJ
These examples of DemeterJ and DJ illustrate how Demeter Concepts are implemented. We have only presented the major features of these tools, however they are powerful in their concept and application.
AspectJ
The last AOP Tool that we will be discussing is AspectJ. It extends the Java Language to allow programmers to express crossing cutting concerns. The major feature of AspectJ that we are concerned with are Introduction, Join Point, Pointcut, and Advice. Introductions allow programmers to define classes, data members, inheritance relationships and methods to be organized in a different manor than in Java. Join Point allows programmers to specify a point within the execution of an application. Pointcut specifies a set of Join Points. Finally, the Advice is executed when the Pointcut for it holds true. This description of programs using Join Point is called a Join Point Model.
We will show these concepts in action with the Basket Example. As with other examples, we need to present how the data structures, i.e. the Class Graph, is specified. We may accomplish this as with the DJ example using Java, however will use AspectJ's Introduction feature to demonstrate the power of AspectJ.
Figure 15: Defining Classes for the Basket Example
First, we define empty classes as shown in Figure 15. Then, we use the AspectJ Introductions to introduce the data members and the inheritance relationship as shown in Figure 16. There are no requirements for the location of these Introduction statements, except that they have to be within the scope of an Aspect. These Aspects allow the programmer to organize the different aspects of an application and all of the AspectJ extensions to Java are within the scope of these Aspects.
Figure 16: Defining Relationships for the Basket Example Class Graph
Next, we define constructor and accessor methods for the classes within the Basket Example. In Figure 17, we accomplish this by introducing the constructors by defining the method new() for the classes and accessor method for Weight's integer, i. Note that we need to type more, because we need to specify the class names for each method introduced.
Figure 17: Definition of Constructors and Methods for the Basket Example
Now, we specify the code to count the integer values within Weight objects in Figure 18. This specification is similar to the CountWeightVisitor for the Demeter implimentations. We declare a static integer to be used within all of the methods to count the Weights. We define the method getTotal() for Basket, Fruit, and Weight. These methods are used to access the Weight objects.
In order to add the Weights, we have declared a Pointcut weightpc(). It specifies the Join Points of all method calls to getTotal() and the target of the method call is to an object of type Weight. The after Advice is executed every time the Pointcut holds true. The "arguments" to the Pointcut and the Advice allows data passing from the references accessible at the Join Point to the Advice body. We did not have to use the Pointcut and the Advice, but we wanted to demonstrate a simple use of these AspectJ features.
This Aspect has the same semantics as the implicit Visitor in Figure 9. The methods getTotal() defined for Basket and Fruit are generated by DemeterJ. While in DJ, the call to traverse() takes care of this function.
Figure 18: CountWeight Aspect of Basket Example
Lastly, we define the main method to create an instance of Basket and then call getTotal() to obtain the total Weight within the Basket in Figure 19. Then, we print out the result to the screen.
Figure 19: Code for Testing the AspectJ Basket Example
From this example, we can see that in order to use the Join Points, we need to have some Java code to have meaningful Pointcuts. From this we can create a conceptual model with two different "planes" of execution as shown in Figure 20. One plane is the original Java program and the other is where the bodies of Advices in AspectJ are executed. That Advice body, in turn, may contain method calls to the "Java Plane." In this manner, we can have "ping-ponging" back and forth between the two planes of execution.
Figure 20: A Conceptual Model of AspectJ
We have introduced the AOP Tools FRED, DemeterJ, DJ and AspectJ. Examples of how these tools are used to specify a program have been presented. It is important to understand the fundamental concepts behind these tools for our exploration of the Aspect Oriented Programming Tools concepts. In this exploration we will attempt to understand the strengths of these concepts in the subsequent chapters.
In the subsequent chapters, we will translate some examples of FRED to better understand the semantics FRED. Then, we will attempt to translate Demeter traversals to AspectJ and explore the possibility of translating AspectJ programs to DemeterJ. This leads us to the analysis of Join Point Model and the "Program as a Journey" metaphors. Next, we introduce DAJ that integrates Demeter concepts with AspectJ. In order to find the performance of DAJ, DemeterJ and AspectJ+DJ, we present an implementation of a simple HTTP server for each these tools. From the discussions and experiments presented, we apply the Graph Theoretical View to develop an analysis methodology for Aspect Oriented Programming Tools with a Four Graph Model of Programs. Finally, we conclude with conclusions and suggestions for further research.
Translating FRED
FRED [1 Orleans02] is an extension to Scheme that allows programmers to program incrementally using decision points developed by Doug Orleans. We will attempt to translate some example code to a Graphical Notation and AspectJ, as a starting point of this thesis. The translation process from FRED to a Graphical Notation will bring out implicit semantics within the language, while translating it to AspectJ will allow us to explore the power of AspectJ. Because this is an exercise to learn about FRED's semantics, it is not necessary to create a perfect Graphical Notation for FRED.
Translating FRED to a Graphical Notation
The idea behind the Graphical Notation for FRED arose out of the fact that many people like to visualize their programs. Languages such as UML arose out of this need for visualization of programs. The purpose of this exercise is to discover the semantics of FRED that is not immediately apparent.
Figure 21: Primitives for Graphical Expression of FRED
In order to describe FRED, we have broken down what actually happens within each function in Figure 21. We have a circle with the name of the function within it. This is a node within our Graphical Representation. Next, we need a way to connect these nodes together and the arrow signifies a Branch or a function call. Since each Branch may have a predicate, a Scheme style predicate without the parenthesis is one of the labels for the Branch. We also need to deal with parameters and return values. A variable with a box around it signifies parameters passed to the function. The dollar sign with a box around it signify the value returned from a function call. This is used for the Branch that is visited after a return from the original Branch. You can think of this as a "side trip" to another node during the return trip. Lastly, we need something to signify that the trip has ended so a Termination Branch was added.
As an example, we have translated a simple factorial example in Figure 22 using the primitives that are listed in Figure 2. The Scheme expressions are shown on the left and the graphical equivalent is shown on the right. The first Scheme expression, (define-msg fact) defines a node named fact. The second, defines the Termination Branch on the left with the predicate (= x 1). If this predicate is true, the "traveler" should stop and start its return trip. The last Scheme expression, specifies the Branch on the right. Since, this is a recursive function, the Branch goes to the function fact back to itself with (- x 1) as the parameter. The Return Branch is also specified in the last Scheme expression. The Return Branch goes to the plus function with the parameters x and the value returned from the original branch. This is how we translate FRED code to the Graphical Notation.
Figure 22: Graphical Translation of Factorial Example
From this translation process, we can make several observations. First, FRED does not have any mechanism to group the branches that are associated with a message. FRED associates the Branches with Messages by using the predicates such as (eq? (dp-msg dp) fact). Because of this feature, a programmer can reuse branches for different Messages or Nodes by OR'ing the Message name matching predicates.
Another ramification of this feature is that the programmer is able to place the branches anywhere. There is no requirement or scoping of the Branches as you would in programming languages such as C++. Thus, it is upto the programmer to organize these Branches and Messages in anyway that is optimal for a particular application.
The second observation to make is that the mechanism to describe the return value is quite clumsy in the Graphical Notation. It is not very intuitive and it is hard to understand what is happening. This is because the ordering of the Return Branches is not clear from the Graphical Notation. In addition, the dollar sign for the return value is not intuitive. This awkwardness arises from the fact that Scheme is Forward Centric, meaning that we describe explicitly what is happening during the one-way trip and the things that are happening during the return trip is implicit. Many of the programming languages are forward centric, i.e. explicit syntax for invocation of functions and implicit syntax for handling values that are returned. This makes it difficult to describe the events during the return trip.
The third observation to make is that the function factorial is a schema for all of the call frames that are generated during run-time. This is the same relationship as the Class Graph - Object Graph relationship. It implies that the Static Call Graph is a schema for the Dynamic Call Graph and the CPU is managing the Dynamic Call Graph using the Static Call Graph and the inputs. Since the behavior of any programs maybe described in this manor, it maybe possible to describe all programs using the Demeter concepts.
From these three observations from the simple factorial example, we can see the usefulness of this experiment. We have hit upon some fundamental assumptions evident in programming languages and we can explore further, the semantics of and the trade-offs made for programming languages.
We will take a look at a more complex example of the Graphical Notation for FRED to explore these observations further. In the next example, we are translating a FRED implementation of string. We will explore the function concat, len, and ref that concatenate two strings, find the length of a string and retrieve the nth character of a string respectively. For the sake of simplicity, we will assume that other predicates and methods such as flat-cord?, make-cord, etc. are defined and concentrate on these three functions.
First, we will present and analyze the function concat that concatenate two strings. In this example, the method define-method is used. This is collapsing the two methods define-node and define-branch. Therefore, it has three parameters: name of the method, predicate for the Branch, and a Scheme expression as the body of the Branch. As in the factorial example, the FRED code that we are translating is shown on the left and the translated Graphical Notation shown on the right in Figure 3.
Figure 23: Graphical Notation for concat
In Figure 3, the first define-method statement handles the case where the first parameter is of type string. In this case, we make a flat-cord, an internal data structure, and calls itself recursively. The left Branch from concat to make-flat-cord is the translation of this Scheme statement in the Graphical Notation. The "string? l" signifies the predicate that checks for the data type of the first argument "l" to be of type string. The Return Branch, with the $ as the first argument and the "r" as the second argument, sig